- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •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 Пути в бесконтурном графе
- •Литература
5.3 Кольцевой связный список
В односвязном списке для доступа к желаемому элементу необходимо просматривать список с самого начала. Это неудобно и занимает много времени.
Если замкнуть элементы списком в кольцо, т.е. в последний элемент списка поместить указатель на первый элемент, то просмотр списка можно начинать с любого элемента и просмотреть весь список. Такой список называется кольцевым.
nach
12 3
3
4
Г
2
К
1
Рис. 13
5.4 Линейный двусвязный список
Нередко при просмотре линейного списка возникает необходимость продвижения в любом направлении по цепочке элементов: как к концу списка, так и к его началу. Такую возможность обеспечивает линейный дву-связный список. Каждый элемент такого списка содержит два указателя:
прямой – на следующий элемент списка;
обратный – на предыдущий элемент списка.
Кроме указателя на начало списка в структуру двусвязного списка должен быть включен указатель на конец списка (т.е. на последний элемент). Таким образом логическая структура двусвязного списка выглядит следующим образом (на примере).
|
пас 1 |
2 3 4 |
|
d |
|з U | |
4 U 1° 1 Н 1° h 1ГгЧ h I2 | |
|
1 ^-~ |
Г | 1 |_J |
|
|
|
Рис. 14
Линейность двусвязного списка вытекает из того, что каждый из двух указателей в любом элементе списка (кроме крайних элементов) задает линейный порядок элементов, обратный порядку, устанавливаемому другим указателем.
Начало и конец двусвязного списка логически эквивалентны, т.к. доступ к элементу списка может быть осуществлен с любого конца списка. В конце каждого пути должен стоять нулевой указатель (пустой).
Наличие двух указателей в каждом элементе заметно усложняет список и приводит к дополнительным затратам памяти, но обеспечивает более эффективное выполнение операций над списком.
Дальнейшее совершенствование двусвязного списка приводит к кольцевому двусвязному списку. В нем прямой указатель последнего элемента ссылается на первый элемент, а обратный указатель первого элемента – на последний элемент.
В кольцевом двусвязном списке указатель конца не нужен.
Включение в двусвязный список
Особенность включения в двусвязный список состоит в том, что нужно модифицировать указатели не только предыдущего, но и последующего элементов списка.
Пусть нужно вставить новый элемент после элемента с индексом I. J := FREE; индекс свободного элемента
SPISOK[J].INF := C; занесение информации
FREE := SPISOK[J].LINK; индекс нового свободного элемента K := SPISOK[I].LINK1; индекс следующего элемента SPISOK[I].LINK1 := J; смена указателя предыдущего элемент
SPISOK[J].LINK1 := K; занесение информации SPISOK[J].LINK2 := I; указатель на следующий элемент
SPISOK[K].LINK2 := J;
Промоделировали динамическую структуру статической. Однако лучше все же создавать динамическую структуру. А для этого нужно рассмотреть динамическое распределение памяти.
Контрольные вопросы
Линейные динамические структуры. Связный список.
Реализация связного списка массивом.
Линейный двусвязный список.