Возможные методы хранения данных в конечном итоге определяются организацией памяти компьютера.
В большинстве современных компьютеров оперативная память построена по адресному принципу и представляет собой пронумерованную последовательность ячеек одинакового размера. Номер ячейки называется ее адресом, содержимое ячейки - машинным словом. Количество ячеек (объем, емкость памяти) обычно находится в пределах от 103 до 1010, а размер (длина) ячейки – от 8 до 64 бит.
Адресом данных, занимающих несколько соседних ячеек, считают адрес первой из них. В языках программирования адреса называют также указателями или ссылками.
Минимальным элементом хранения является бит - двоичная цифра, принимающая одно из двух значений, например, 0 или 1. Бит используется также как единица количества информации. Количество информации в битах равно минимальному числу двоичных цифр, необходимому для представления этой информации.
Машинное слово представляет собой команду или данные. Первоначально ЭВМ использовались преимущественно для обработки числовой информации. Ячейка памяти содержала одно число и имела длину от 16 до 64 бит. Это неудобно для представления символьной (текстовой) информации, т. к. код символа (байт) в зависимости от размера алфавита содержал от 5 до 8 бит, и в ячейке приходилось размещать несколько символов, что затрудняло доступ к каждому из них.
С повышением роли символьной обработки стали применять байтовую организацию памяти, когда ячейка содержит один байт, равный 8 бит, а для представления числа используются несколько соседних байтов. Байт также рассматривается как единица количества информации, равная одному символу текста.
Таким образом, оперативная память ЭВМ имеет линейную (одномерную) организацию, и для хранения многомерных массивов и других сложных структур данных их необходимо "линеаризовать".
Существуют три основные группы методов хранения структур данных.
1. Последовательное (сплошное) представление данных. Элементы структуры располагаются в памяти друг за другом без промежутков. Наиболее используемой структурой хранения является вектор.
2. Связанное (цепное) представление данных. Элементы структуры могут размещаться в памяти в произвольном порядке не обязательно подряд, причем каждый элемент содержит указатели (адреса) одного или нескольких других элементов, позволяющие отыскивать их в памяти. Основные структуры хранения - список и сеть.
3. Адресная арифметика. Элементы структуры располагаются в памяти в произвольном порядке с возможными промежутками, но существует определенная закономерность, позволяющая вычислять адрес элемента, например, в зависимости от его номера или другого параметра. Адресная арифметика может рассматриваться как обобщение последовательного и связанного представлений, в общем виде используется сравнительно редко.
Вектор - это набор элементов одинакового размера, расположенных в памяти подряд. Под набором в данном пособии понимается конечное множество. Вектор определяется базой (адресом первого элемента), длиной (количеством элементов) и размером элемента. По сути дела, вектор представляет собой одномерный массив. Главное достоинство вектора - прямой доступ к элементу по его порядковому номеру - индексу:
где V[J] - элемент с индексом J, d - размер элемента (количество ячеек, занимаемых одним элементом); для простоты считаем, что d ³ 1, целое.
Элементы вектора одинаково доступны и их можно обрабатывать в любом порядке.
Связанный список (в дальнейшем - список) - это последовательность элементов, каждый из которых, кроме других данных, содержит указатель (адрес) следующего элемента. Графически указатель изображают в виде стрелки, соединяющей элементы списка. На рис. 13.1 показан список, каждый элемент которого содержит один символ. Последний элемент списка содержит пустой указатель, равный нулю ().
Указатель
списка
Рис. 14.1. Список
Сеть (многосвязный список) - это набор элементов, каждый из которых может иметь несколько указателей (ссылок) на другие элементы. В однородной сети все элементы содержат одинаковое количество ссылок, в неоднородной - разное (рис. 14.2).
Рис. 14.2. Однородная (регулярная) сеть из трех элементов
Главное достоинство списков и сетей - простота добавления и удаления элементов; недостатки - дополнительная память для указателей и возможность только последовательного доступа к элементам (допускается движение только по ссылкам).
Программирование операций с сетями аналогично обработке списков.
Наиболее распространенным средством представления структур данных в языках программирования являются массивы. Одномерный массив (вектор), имеется в любом языке высокого уровня и легко реализуется на машинном языке. Поэтому в учебнике он рассматривается как базовая структура хранения, а многомерный массив - как абстрактная (т. е. производная) структура данных.
Современные языки включают понятие "структура" (C, PL/1 и др.) или "запись" (Pascal и др.). Структура (запись) - это совокупность именованных элементов - полей - одного или разных типов. Это понятие очень близко к понятию структуры данных и позволяет его формализовать.
Отсутствие в языке записей до некоторой степени можно компенсировать параллельными массивами. Совокупность (массив) из n однотипных записей заменяется параллельными массивами, количество которых равно количеству полей в записи. Каждый массив содержит n значений соответствующего поля всех записей.
Пример 14.1.Определение массива s из 100 записей (структур) с тремя полями sim, i, x:
struct
{ char sim; /* Символьное поле sim */
int i; /* Целочисленное поле i */
float x[10]; /* Поле x - массив из 10 вещественных чисел */
} s[100];
можно заменить определением трех параллельных массивов по 100 элементов:
char sim[100]; /* Поля sim всех 100 записей */
int i[100]; /* Поля i всех 100 записей */
float x[100][10]; /* Поля x всех 100 записей */
Тогда, например, поле sim 15-й записи
s[15].sim заменится на sim[15],
5-й элемент поля x 20-й записи
s[20].x[5] запишется как x[20][5],
но вся 40-я запись s[40] не имеет аналогичного обозначения в параллельных массивах.
Понятие структуры данных близко к понятию типа данных. Абстрактные структуры данных называют еще абстрактными типами данных. Абстрактные типы данных лежат в основе методики объектно-ориентированного программирования. Их изучение служит, в частности, базой для освоения этой современной технологии.
В языке C++ для объектно-ориентированного программирования понятие структуры обобщается и приближается к концепции абстрактного типа данных: элементами структуры могут быть не только данные, но и допустимые для них операции. Такая структура в C++ называется объектом, тип объектов - классом.
