int **mallqc2d(int г, int с) { int **t = new int*[r]; for (int i = 0; i < r; i++)

t[i] = new int[c] ; return t;

Программа 3.17 демонстрирует использование подобной составной структуры: массива строк. На первый взгляд, поскольку абстрактное понятие строки относится к массиву символов, массивы строк следовало бы представлять в виде массивов, состоящих из массивов. Однако конкретным представлением строки является указатель на начало массива символов, поэтому массив строк также может быть массивом указателей. Как показано на рис. 3.12, эффекта перераспределения строк можно достичь простым изменением расположения указателей массива. В программе 3.17 используется библиотечная функция qsort. Реализация подобных функций рассматривается в главах 6-9 вообще и в главе 7 - особенно. Этот пример иллюстрирует типовой сценарий обработки строк: символы считываются в большой одномерный массив, указатели сохраняются в отдельных строках (ограниченных символами завершения), а затем осуществляется управление указателями.

buf- no{w\ois\o the\o time\oi f ог\оа11\о

buf->now\oi3\o thei\o tiimei\o f ог\о{а11Т

РИСУНОК 3.12 СОРТИРОВКА СТРОК

При обработке строк обычно используются указатели буфера, который содержит строки (верхняя диаграмма), поскольку указателями легче управлять, чем строками, имеющими раз.1ичную длину. Например, в результате сортировки указатели перераспределяются таким образом, что при последовательном обращении к ним возвращаются строки в алфавитном (лексикографическом) порядке.

Нам уже встречалось другое применение массивов строк: массив argv, используемый для передачи строковых аргументов функции main программ на С++. Система сохраняет в строковом буфере символы командной строки, введенные пользователем, и передает в процедуру main указатель на массив указателей строк этого буфера. Для вычисления чисел, соответствующих некоторым аргументам, используются функции преобразования. Остальные аргументы используются непосредственно как строки.

Программа 3.17 Сортировка массива арок

Эта программа иллюстрирует важную функцию обработки строк: расположение набора строк в порядке сортировки. Строки считываются в буфер, который достаточно велик, чтобы вместить их все. Для каждой строки в массиве сохраняется указатель. Затем изменяется расположение указателей, чтобы указатель на самую младшую строку помещался в первую позицию массива, указатель на следующую в алфавитном порядке строку - во вторую позицию и т.д.

Библиотечная функция qsort, которая в действительности выполняет сортировку, принимает четыре аргумента: указатель на начало строки, количество объектов, размер каждого объекта и функцию сравнения. Независимость от типа сортируемых объектов достигается за счет слепого перераспределения блоков данных, которые представляют объекты (в данном случае, указатели на строки), а также путем использования функции сравнения, принимающей в качестве аргумента указатель на void. Программа выполняет обратное преобразование этих блоков в тип указателей на указатели символов для функции strcmp. Чтобы обратиться к первому символу строки для операции сравнения, разыменовываются три указателя: один для получения индекса (который является указателем) элемента массива, один для получения указателя строки (с помощью индекса) и еще один для получения символа (с помощью указателя).

Мы используем другой метод достижения независимости от типа для функций сортировки и поиска (см. главы 4 и 6).

#include <iostreain.h> #include <stdlib.h> #include <string.h>

int conpae (const void *i, const void *3)

{ return strcmp(*(char **)i, *(char **)3); } int main(} { const int №nax = 1000; const int Mmax = 10000; char* a[Nmax]; int N; char buf[Mmax] ; int M = 0; for (N = 0; N < Nmax; N++) {

a [N] = Sbuf [M] ;

if (!(cin a[N])) break;

M += strlen(a[N])+l;

qsort(a, N, sizeof(char*), compare); for (int i = 0; i < N; i++) cout a[i] endl;

Строить составные структуры данных можно также исключительно с помощью ссылок. На рис. 3.13 показан пример мультисписка, узлы которого имеют несколько полей ссылок и принадлежат независимо поддерживаемым связным спискам. При разработке алгоритмов для построения сложных структур данных часто применяют более одной ссылки для каждого узла, но это преследует цель эффективного управления ими. Например, список с двойными связями является мультисписком, который удовлетворяет ограничению: оба выражения х->1->г и х->г->1 эквивалентны х. В главе 5 рассматривается намного больше важных структур данных с двумя ссылками для каждого узла.

Если многомерная матрица является разреженной (sparse) (количество ненулевых элементов относительно невелико), для ее представления вместо многомерного массива можно использовать мультисписок. Каждому значению матрицы соответствует один узел, а каждому измерению - одна ссылка. При этом ссылки указывают на следующий элемент в данном измерении. Эта организация снижает размер области хранения. Она теперь не зависит от максимальных значений индексов измерений, а пропорциональна количеству ненулевых записей. Однако для многих алгоритмов увеличивается время выполнения, поскольку для доступа к отдельным элементам приходится отслеживать ссылки.

Для ознакомления с дополнительными примерами составных структур данных и выяснения различий между индексированными и связными структурами данных рассмотрим структуры данных, применяемые для представления графов. Граф - это фундаментальный комбинаторный объект, который описывается набором объектов (называемых вершинами) и набором связей между вершинами (называемых ребрами). Мы уже встречались с понятием графов в задаче связности из главы 1.

РИСУНОК 3.13 МУЛЬТИСПИСОК

Связывать узлы можно с помощью двух полей ссылок в двух независимых списках, по одному на каждое поле. Здесь правое поле связывает узлы в одном порядке (например, этот порядок может отражать последовательность создания узлов), а левое поле - в другом порядке (в нашем случае это порядок сортировки, возможно, результат сортировки вставками, использующей только левое поле ссылки). Отслеживая правые ссылки от узла а, мы обходим узлы в порядке их создания. Отслеживая левые ссылки от узла Ь, мы обходим узлы в порядке сортировки.