Структуры данных - это совокупность элементов данных и отношений между ними. При этом под элементами данных может подразумеваться как простое данное так и структура данных. Под отношениями между данными понимают функциональные связи между ними и указатели на то, где находятся эти данные.
Графическое представление элемента структуры данных.
Элемент отношений - это совокупность всех связей элемента с другими элементами данных, рассматриваемой структуры.
S:=(D,R)
Где S - структура данных, D - данные и R - отношения.
Как бы сложна ни была структура данных, в конечном итоге она состоит из простых данных (см. рис. 2.2, 2.3).
Уровни представления данных
Память машины состоит из миллионов триггеров, которые обрабатывают поступающую информацию.Мы, занося информацию в компьютер, представляем ее в каком-то виде, который на наш взгляд упорядочивает данные и придает им смысл. Машина отводит поле для поступающей информации и задает ей какой-то адрес. Таким образом, получается, что мы обрабатываем данные на логическом уровне, как бы абстрактно, а машина делает это на физическом уровне.
Последовательность переходов от логической организации к физической показана на рис. 2.4.
Классификация структур данных
Структуры данных классифицируются:
1. По связанности данных в структуре:
- если данные в структуре связаны очень слабо, то такие структуры называются несвязанными (вектор, массив, строки, стеки)
- если данные в структуре связаны, то такие структуры называются связанными (связанные списки)
2. По изменчивости структуры во времени или в процессе выполнения программы:
- статические структуры - структуры, неменяющиеся до конца выполнения программы (записи, массивы, строки, вектора)
- полустатические структуры (стеки, деки, очереди)
- динамические структуры - происходит полное изменение при выполнении программы
3. По упорядоченности структуры:
- линейные (вектора, массивы, стеки, деки, записи)
- нелинейные (многосвязные списки, древовидные структуры, графы)
Наиболее важной характеристикой является изменчивость структуры во времени.
Статические структуры данных
Векторы
Самая простая статическая структура - это вектор. Вектор - это чисто линейная упорядоченная структура, где отношение между ее элементами есть строго выраженная последовательность элементов структуры (рис. 2.5).
Каждый элемент вектора имеет свой индекс, определяющий положение данного элемента в векторе. Поскольку индексы являются целыми числами, над ними можно производить операции и, таким образом, вычислять положение элемента в структуре на логическом уровне доступа. Для доступа к элементу вектора, достаточно просто указать имя вектора (элемента) и его индекс.
Для доступа к этому элементу используется функция адресации, которая формирует из значения индекса адрес слота, где находится значение исходного элемента. Для объявления в программе вектора необходимо указать его имя, количество элементов и их тип (тип данных)
Пример:
M1: Array [1..100] of integer;
M2: Array [1..10] of real;
Вектор состоит из однотипных данных и количество их строго определено.
Массивы
В общем случае элемент массива - это есть элемент вектора, который сам по себе тоже является элементом структуры (рис. 2.6).
Для доступа к элементу двумерного массива необходимы значения пары индексов (номер строки и номер столбца, на пересечении которых находится элемент). На физическом уровне двумерный массив выглядит также, как и одномерный (вектор), причем трансляторы представляют массивы либо в виде строк, либо в виде столбцов.
Записи
Запись представляет из себя структуру данных последовательного типа, где элементы структуры расположены один за другим как в логическом, так и в физическом представлении. Запись предполагает множество элементов разного типа. Элементы данных в записи часто называют полями записи.
Пример:
Логическая структура записи может быть представлена как в графическом виде, так и в табличном.
Элемент записи может включать в себя записи. В этом случае возникает сложная иерархическая структура данных.
Пример:
Необходимо заполнить запись о студенте, содержащую следующую информацию: N - порядковый номер студента; Имя студента, в составе которого должны быть: Фамилия, Имя, Отчество; Анкетные данные студента: год рождения, место рождения, родители: мать, отец; Факультет; Группа; Оценки, полученные в сессию: по английскому языку и микропроцессорам.
Ниже приведены два логических представления структуры этой записи.
Получена четырехуровневая иерархическая структура данных. Информация содержится в листьях, остальные узлы служат для указания пути к листьям.
1-ый уровень Студент = запись
2-ой уровень Номер
2-ой уровень Имя = запись
3-ий уровень Фамилия
3-ий уровень Имя
3-ий уровень Отчество
2-ой уровень Анкетные данные = запись
3-ий уровень Место рождения
3-ий уровень Год рождения
3-ий уровень Родители = запись
4-ый уровень Мать
4-ый уровень Отец
2-ой уровень Факультет
2-ой уровень Группа
2-ой уровень Оценки = запись
3-ий уровень Английский
3-ий уровень Физика
Эта структура называется вложенной записью.
Операции над записями:
1. Прочтение содержимого поля записи.
2. Занесение информации в поле записи.
3. Все операции, которые разрешаются над полем записи, соответствующего типа.
Таблицы
Таблица - это конечный набор записей (рис. 2.11).
При задании таблицы указывается количество содержащихся в ней записей.
Пример:
Type ST = Record
Num: Integer;
Name: String[15];
Fak: String[5];
Group: String[10];
Angl: Integer;
Physic: Integer;
var
Table: Array [1..19] of St;
Элементом данных таблицы является запись. Поэтому операции, которые производятся с таблицей - это операции, производимые с записью.
Операции с таблицами:
1. Поиск записи по заданному ключу.
2. Занесение новой записи в таблицу.
Ключ - это идентификатор записи. Для хранения этого идентификатора отводится специальное поле.
Составной ключ - ключ, содержащий более двух полей.
Дата: 2019-12-10, просмотров: 234.
