Понятие «структура» входит в программу не только на уровне общего ее построения, но и предусматривает структурирование самой логики и оперируемых данных. Прежде всего, данный принцип нашел свое применение в типизации языка Паскаль, т.е. наделении его строгой системой предопределенных типов, комбинируя которые программист мог создавать свои собственные типы, причем уже не только простые, но и представляющие собой сложные конструкции – структуры данных.
Моделирование приводило к абстракции, т.е. к упрощенному (или обобщенному) представлению объектов, их свойств и отношений в зависимости от поставленной задачи.
Некоторые такие абстрактные объекты из-за своих полезных качеств стали необычайно «популярны». Они получили точную спецификацию и с тех пор стали называться абстрактными типами данных (или АТД).
Т.е. абстрагирование от многих несущественных факторов, в том числе и от того, как этот абстрактный объект представить в ЭВМ.
Этим собственно и занялись языки программирования, которые и являются неким переходником между идеями человека и возможностями машины.
К АТД относятся: массив, запись, записи с вариантами, стек, очередь, дек, отображение
Массив– это одно- или многомерная таблица данных одного типа. В одномерном случае каждая ячейка таблицы имеет свой индекс. В многомерном набор индексов рис. 1.
В11
В12
…
В1n
В21
В22
…
В2n
В31
В23
…
В3n
В41
В24
…
В4n
Рис. 1 – Структура массива
Массив называют структурой данных со случайным доступом, поскольку к любому элементу массива можно обратиться, просто указав его индексы, т.е. все элементы одинаково доступны в любой момент времени. Массив определяется, прежде всего, общим типом его элементов и их количеством.
Количество элементов массива, определяется количеством индексов и диапазоном их изменения.
Для доступа к элементу двумерного массива необходимо значения пары индексов (номер строки и номер столбца, на пересечении которых находится элемент). На физическом уровне двумерный массив выглядит так же, как и одномерный (вектор), причем трансляторы представляют массивы либо в виде строк, либо в виде столбцов
Запись – связанная структура, состоящая из нескольких элементов (полей) разных (можно и одинаковых) типов.
Запись очень похожа на одномерный массив, но с элементами разных типов, кроме того, доступ к конкретному полю записи осуществляется уже не через индекс, а указанием идентификатора (т.е. имени) этого поля.
Например:
Петров С. П
КТАС
07-К-ПО1
Эту запись можно представить в логическом и графическом виде рис. 2, рис.3
номер
фамилия
факультет
группа
Рис. 2 - Логическая структура
рис. 3 – графическая структура
Элемент записи может включать в себя записи. В этом случае возникает сложная иерархическая структура данных
Операции над записями:
1. Прочтение содержимого поля записи.
2. Занесение информации в поле записи.
Все операции, которые разрешаются над полем записи, соответствующего типа
Стек –структура данных, представляющая собой последовательность элементов. Добавление и удаление элементов происходит только с одного конца последовательности, т.е. при изменении структуры предыдущая последовательность остается неизменной.
В силу указанной дисциплины обслуживания, в стеке доступна единственная его позиция, которая называется вершиной стека- это позиция, в которой находится последний по времени поступления в стек элемент.
Графически стек можно представить следующим образом:
EN
Вершина стека
…
…
E2
E1
Нижняя граница стека
Рис. 4 – Графическое изображение стека
Первый элемент заносится вниз стека. Выборка из стека осуществляется с вершины, поэтому стек является структурой с ограниченным доступом.
АТД «стек» использует следующие пять операторов:
1. MAKENUL – делает стек пустым.
2. TOP – возвращает копию элемента из стековой вершины.
3. POP – достаёт элемент из вершины стека. Иногда реализует возвращение удаляемого элемента.
4. PUSH – помещает элемент в стек, делая его вершиной, а предыдущую вершину вторым элементом.
5. Stacktop(S) -Прочтение элемента без его выборки из стека.
- Реализация стека посредством массива.В низу массива зафиксиhetz дно стека max и стек «растет» вверх по массиву к ячейки с наименьшим индексом. На вершину стека будет указывать курсор с именем top, который определяет текущее положение первого элемента стека. Данное представление стека показано на рисунке 5.
Реализация стека с помощью указателей. Стек это специальный тип списка. Внешний вид ячеек и их способ соединений схожи, а характер и последовательность присоединения элементов отличается.
Оператор PUSH добавляет элемент лишь в вершину стека. Добавление элемента происходит следующим образом: создаётся новая ячейка, в поле next записывается указатель на прошлую вершину стека, а указатель на новую ячейку становится новым указателем на вершину стека (рис.6).
рис. переделать.
Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание
Очередь – это структура данных, представляющая собой последовательность элементов.
Добавление элементов происходит с одной стороны последовательности, удаление – с другой. Рис. 7.
Рис. 7 – Графическое изображение очереди
Заказ поступает в очередь первым, выбирается первым для обработка (и удаляется из очереди тоже первым) называется FIFO (первым пришел, первым ушел). Такая очередь открыта с обеих сторон.
Для работы с очередями используются следующие операторы:
1. MAKENUL– делает очередь пустой.
2. FRONT– возвращает копию элемента из начала очереди.
3. ENQUEUE – эта процедура вставляет новый элемент в конец очереди.
4. DEQUEUE– осуществляет удаление первого элемента из очереди.
5. EMPTY – возвращает значение true, если очередь пуста, и значение false, если в ней есть элементы
Реализация очередей с помощью циклических массивов.Во время представления очередей с помощью массивов (рис.8) возникает трудность, связанная с определением пустоты очереди, так как по взаимному расположению указателей конца и начала не возможно определить, когда очередь пуста, а когда заполнила весь массив.
Реализация очередей с помощью указателей.Так же как и «стек», «очередь» является специальным типом списка и, имея похожую структуру, обладает рядом отличий при добавлении рис. 9 и удалении элементов рис. 10
Вставка элемента осуществляется оператором enqueue((по)ставить в очередь) осуществляется добавление элемента следующим образом: создаётся новая ячейка, и указать на неё записывается вместо nil в поле next конечного элемента очереди, т.е. указатель P4 был записан вместо nil в поле next ячейки, на которую указывает указатель P3 (рис. 9а, 9б)
Dequeue (выводить [исключать] из очереди), удаляя первый элемент из очереди, отсоединяет от очереди прежнее начало, в результате чего новая ячейка становится первым элементом списка. Указатель на начало очереди P0 присваивается новое значение – P2, что исключило из очереди прежнее начало, т.е. элемент a с указателем на него P1.(рис. 10а, 10б)
