СТРУКТУРЫ ДАННЫХ
Главным условием хранения информации в памяти компьютера является возможность преобразования этой самой информации в подходящую для компьютера форму. Далее, если это условие выполняется, то следует определить структуру, пригодную именно для наличествующей информации, ту, которая предоставит требующийся набор возможностей работы с ней. Здесь под структурой понимается способ представления данных, посредством которого совокупность отдельно взятых элементов образует нечто единое, обусловленное их взаимосвязью друг с другом.
Скомпонованные по каким-либо правилам и логически связанные между собой данные могут очень эффективно обрабатываться, так как общая для них структура предоставляет набор функций управления ими - одно из того, за счет чего достигаются высокие результаты в решениях тех или иных задач. Потом не каждый объект представляем в произвольной форме, а возможно и вовсе для него имеется лишь один-единственный метод интерпретации, следовательно, несомненным плюсом для программиста будет знание всех существующих структур данных. Но часто приходится делать выбор между различными методами хранения информации, и от такого выбора зависит работоспособность продукта.
Можно привести много примеров, не связанных с вычислительной техникой, в которых у информации видна явная структура. Таким примером, в частности, служат книги: они разбиты на страницы, главы, параграфы и имеют, как правило, оглавление, т. е. интерфейс для их эксплуатации.
В языках программирования также используются различные «простые» структуры данных. К ним относятся числа, строки, файлы и т. д. В данной главе будут рассмотрены «интегрированные» структуры, т. е. те, которые состоят из простых, а именно - массивы, списки, деревья, графы.
Массивы
Массив - это структура данных с фиксированным и упорядоченным набором однотипных элементов (компонентов). Доступ к какому-либо из элементов массива осуществляется по имени и номеру (индексу) этого элемента.
Количество индексов определяет мерность массива, так, например, чаще всего встречаются одномерные (векторы) и двумерные массивы (матрицы). Первые имеют один индекс, вторые - два.
Пусть одномерный массив называется .4, тогда получить доступ к его /-му элементу можно, указав название вместе с номером: Ai. В том случае, если А является матрицей, то она представляема в виде таблицы, доступ к элементам которой осуществляется по имени массива, а также по номерам строки и столбца, на пересечении которых расположен элемент: A[i, Л, тут i - номер строки,/ - номер столбца.
Обращение к компонентам массивов больших размерностей аналогично двум приведенным примерам. В разных языках программирования работа с этой структурой данных может в чем-то различаться, но основные принципы, как правило, везде одни. В языке Pascal обращение к одномерному и двумерному массиву происходит точно так, как это показано выше, а, например, в Си двумерный массив следует указывать так: А [/][/]. Элементы массива нумеруются поочередно. На то, с какого значения начинается нумерация, влияет язык программирования. Чаще всего этим значением является 0 или 1.
Массивы описанного выше типа называются статическими, но существуют также массивы, по определенным признакам отличные от них: динамические. Динамичность первых характеризуется непостоянностью размера, т. е. по мере выполнения программы размер динамического массива может изменяться. Такая возможность делает работу с данными более гибкой, но при этом в жертву приносится быстродействие, да и сам процесс усложняется.
