- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
4.2 Представление полустатических структур с помощью массивов
Представление стека
Типичное представление стека – массивом, содержащим не меньшее число элементов, чем может быть заслано в стек.
Для очередного элемента достаточно иметь один указатель t на этот элемент. Когда стек пуст, t = 0.
Описание:
const ms = 100;
var stack : array[1..ms] of tt; t : integer;
Чтобы добавить элемент в стек, нужно увеличить значение указателя на единицу, а затем занести в элемент массива с индексом t информацию из y :
t := t + 1;
stack[t] := y;
Удаление элемента из стека
y := stack[t];
t := t - 1;
При этом следует помнить, что t не может быть меньше 1 и больше MS. Следовательно, нужны проверки на пустоту и переполнение стека. If t = 0 then { }
else begin y := stack[t]; t := t - 1 end; if t = ms then { }
else begin t := t + 1; stack[t] := y end;
Представление очереди
Очередь также может быть представлена массивом, но для неё уже нужны два указателя: f – для начала и r – для конца очереди. Описание: const mq = 100; var queue : array[1..mq] of tt; var f, r : integer;
Включение в очередь производится так же, как и в стек: queue[r] := y; r := r + 1; При этом r может только расти. Исключение из очереди делается аналогично: y := queue[f]; f := f + 1; Текущая длина очереди равна r - f .
Для устранения сползания очередь замыкают в кольцо. В кольцевой очереди после queue[mq] логически следует queue[1] .Но при этом если r=f , то очередь может быть либо заполнена до конца, либо пуста. Для того, чтобы избежать неоднозначности, последний элемент не заполняют и это обстоятельство считается переполнением.
Добавление в кольцевую очередь: if r = mq then r := 1
else r := r + 1; if r = f then { }
else queue[r] := y; Исключение элемента из кольцевой очереди: if r = f then { }
else begin y := queue[r];
if f = mq then f := 1 else f := f + 1;
end; Определение числа элементов в очереди: if r < f then k := mq + r - f
else k := r - f
Контрольные вопросы
Полустатические структуры. Понятие списка.
Стек как структура данных.
Очередь и дек как структуры данных.
Представление полустатических структур с помощью массивов.
5 Линейные динамические структуры
5.1 Основные свойства динамических структур
В отличие от статических и полустатических структур динамические структуры обладают следующими свойствами:
непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе её обработки. Размер динамической структуры может изменяться от 0 до некоторого значения, определяемого спецификой задачи или доступным объемом машинной памяти;
отсутствием физической смежности элементов структуры в памяти. Логическая последовательность элементов задается в явном виде с помощью одного или нескольких указателей (связок), хранящихся в самих элементах.
В связи со вторым свойством память, занимаемая динамической структурой не представляет собой непрерывную область. Элементы динамической структуры могут быть разбросаны в памяти хаотичным образом. Следствием этого является усложнение процедуры доступа к элементам динамической структуры по сравнению со статическими и полустатическими структурами.
С другой стороны, такая схема является более гибкой и часто обеспечивает выигрыш в памяти.
Динамические структуры представляются обычно в виде связных списков, о которых уже упоминалось. Поэтому их часто называют списковыми структурами. В таком списке каждый элемент снабжается дополнительным полем, где указывается номер или адрес следующего (логически) элемента списка.
Начало
3
И
5
4
0
5
1
Рис 11
Связный список – структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом логически с помощью указателей, хранящихся в самих элементах.
Простейшие связные списки – односвязный (один указатель), двусвязные (два).
В принципе может быть и больше указателей.
В односвязном списке каждый элемент состоит из двух полей: содержательного и поля указателя.
Содержательное поле хранит данные (в общем случае это запись).
Поле указателя хранит адрес следующего элемента списка. По указателю получаем доступ к следующему элементу, от него к очередному и т.д. Поле указателя последнего элемента должно содержать специальный признак нулевого или пустого указателя, свидетельствующего о конце списка (0 в нашем примере).
Кроме того, должен быть указатель начала списка. Он является частью его логической структуры.
Сравнивая между собой две рассмотренных формы хранения информации в памяти ЭВМ (в виде последовательных и связанных списков), можно отметить:
связанные списки требуют дополнительной памяти для хранения связей. Иногда это важно. Однако часто бывает так, что свободное место для поля связи уже есть в элементе, если он не занимает весь слот целиком. Кроме того, во многих применениях несколько элементов можно объединить в один узел и тогда на них потребуется только одна связь. Гораздо важнее тот неявный выигрыш в памяти, который возникает при использовании связных списков, поскольку позволяет совмещать общие части таблиц;
легко исключить элемент, находящийся внутри связного списка. Для этого нужно лишь изменить связь (т.е. значение указателя);
легко включить элемент в связный список в любое место. Все также сводится лишь к изменению связей. (Для последовательных списков нужно перемещать часть списка);
доступ к k-му элементу связного списка возможен только с начала списка и после просмотра предыдущих элементов. (Это – плата за их разброс.);
легко осуществляется слияние двух связных списков или разбиение одного списка на части;
схема связных списков позволяет отображать более сложные структуры, чем последовательные списки.
Линейность односвязного списка вытекает из того, что все его элементы линейно логически упорядочены, т.е. для каждого элемента (кроме первого и последнего) имеется единственный предыдущий и единственный последующий элементы.
Физическая структура односвязного списка – совокупность дескриптора и одинаковых по размеру и формату записей, расположенных произвольно в некоторой области памяти и связанных друг с другом в линейно упорядоченную цепочку с помощью указателей.
Между элементами одного списка в памяти могут находиться элементы других списков.
Дескриптор односвязного списка может быть реализован в виде особой записи и содержать следующую информацию:
код списка;
имя списка;
адрес (указатель) начала списка;
текущее число элементов в списке;
описание элемента. Дескриптор может находиться в той же области памяти, в которой располагаются элементы списка, или
для него выделяется какое-либо другое место в памяти.