- •Содержание
- •Раздел 1.Подпрограммы Общие сведения
- •Процедуры Описание процедур
- •Вызов процедур
- •Процедуры без параметров
- •Процедуры с параметрами
- •Параметры-значения
- •Параметры-переменные
- •Параметры-константы
- •Параметры-переменные без типа
- •Параметры процедурного типа
- •Использование производных типов в качестве параметров подпрограмм
- •Принцип локализации имен
- •Функции Описание функций
- •Вызов функции
- •Рекурсивные подпрограммы
- •Директивы
- •Библиотечные модули пользователя Общие сведения
- •Структура модуля Unit
- •Особенности работы с модулями
- •Подключение к программе внешнего файла
- •Раздел 2.Простейший ввод-вывод Процедуры ввода из стандартного текстового файла Input
- •248 15 4 70 Значения 1-й строки
- •11 Значения 2-й строки
- •Процедуры вывода в стандартный текстовый файл Output
- •Раздел 3.Записи Структура записи
- •Записи без вариантной части
- •Записи с вариантами
- •Оператор присоединения With
- •Константа-запись
- •Раздел 4.Множества Общие сведения
- •Конструктор множества
- •Задание множественного типа
- •Операции над множествами
- •Ввод / вывод значения множественной переменной
- •Типизованные константы-множества
- •Раздел 5.Файлы Общие сведения
- •Процедура Assign
- •Файлы с типом
- •Процедура Assign
- •Процедура Rewrite (f)
- •Процедура Write (f, v1 [, v2, … , vn])
- •Процедура Reset (f)
- •Процедура Read (f, V [, v2, …, vn])
- •Функция Eof(f)
- •Процедура Seek (f, n)
- •Функция Filepos (f)
- •Функция Filesize(f)
- •Процедура Close (f)
- •Текстовые файлы
- •Процедура Assign (f, Name)
- •Процедура AssignСrt(f)
- •Процедура Append (f)
- •Процедура Rewrite (f)
- •Процедура Reset (f)
- •Процедура Read ([f,] v1 [, v2, …, vn])
- •Процедура Readln [([f] [,] [v1, v2, …, vn])]
- •Процедура Write ([f,] e1 [, e2, …, en])
- •Процедура Writeln([f,][e1,e2, …,en])
- •Процедура Close(f)
- •Процедура SetTextBuf (f, Buf [, Size])
- •Процедура Flush (f)
- •Сравнительная характеристика представления информации в файлах с типом и текстовых файлах
- •I. Представление числовой информации.
- •II. Представление текстовой информации.
- •Файлы без типа
- •Процедуры Reset и Rewrite
- •Процедура Blockread
- •Процедура Blockwrite
- •Проверка операций ввода-вывода
- •Раздел 6.Ссылочный тип (тип указатель) Общие сведения
- •Методы работы с динамическими переменными
- •Процедуры New и Dispose
- •Процедуры Getmem и Freemem
- •Процедуры Mark и Release
- •Раздел 7.Динамические структуры данных Динамические цепочки Структура динамической цепочки
- •Формирование цепочки
- •Поиск элемента в цепочке
- •Удаление элемента из цепочки
- •Вставка элемента в цепочку
- •Линейный однонаправленный список
- •Двунаправленные списки
- •Вставка элемента
- •Создание двунаправленного кольцевого списка с заглавным звеном
- •Удаление элемента
- •Поиск элемента
- •Очереди и стеки
- •Очередь lifo
- •Очередь fifo
- •Общие сведения
- •Способы организации таблиц
- •Однонаправленный список.
- •Однонаправленный список с упорядоченными записями.
- •Однонаправленный список с отдельным хранением текста записи.
- •Представление в виде массива.
- •Двоичное дерево.
- •Двоичные деревья Структура двоичного дерева
- •Построение дерева
- •Поиск записи в дереве
- •Включение записи в дерево
- •Удаление записи из дерева
- •Раздел 8.Оверлеи Общие сведения
- •Правила оформления оверлейных программ
- •Инициализация работы оверлеев
- •Включение администратора оверлеев
- •Обработка ошибок администратора
- •Размещение оверлейного файла в ems-памяти
- •Управление оверлейным буфером
- •Литература Основная и дополнительная литература
- •Перечень наглядных пособий, методических указаний, методических материалов и используемых в учебном процессе технических средств
Удаление элемента
Пусть в программе имеется описание типа, приведенное в примере 7.8.
Алгоритм удаления элемента:
Занесение в поле Adrpred следующего за удаляемым звена ссылки на предшествующее удаляемому звено из поля Adrpred удаляемого звена;
Занесение в поле Adrcled предшествующего удаляемому звена ссылки на следующее за удаляемым звено из поля Adrcled удаляемого звена;
Уничтожение удаляемого звена.
На двух следующих рисунках приведены схематические пояснения к удалению элемента из двунаправленного списка.
Пусть в изображенном фрагменте исходного списка удаляется звено 2 (Рисунок 7 .68).
Рисунок 7.68 – Фрагмент исходного двунаправленного списка
Результат удаления звена 2 выглядит так, как иллюстрирует Рисунок 7 .69.
Номера связей на данном рисунке соответствуют номерам этапов алгоритма удаления.
Рисунок 7.69 - Результат удаления звена 2
Пример 7.11.
Процедура удаления звена из двунаправленного списка. Номера операторов соответствуют номерам этапов алгоритма удаления звена.
Procedure Udalen (Udzv: Adr2); {Udzv – ссылка на удаляемое звено}
Begin
{1} Udzv^.Adrcled^.Adrpred := Udzv^.Adrpred;
{2} Udzv^.Adrpred^.Adrcled := Udzv^.Adrcled;
{3} Dispose (Udzv);
End;
Поиск элемента
Поиск элемента в двунаправленном кольцевом списке аналогичен поиску элемента в цепочке (см. п. 7.1.3).
Особенность поиска заключается в том, что в кольцевом списке формально нет последнего элемента, так как каждый элемент имеет ссылку на следующий. Это нужно учитывать при организации цикла поиска.
Пример 7.12.
Логическая функция поиска элемента в двунаправленном кольцевом списке с заглавным звеном. Если искомый элемент в списке есть, возвращаемое значение функции равно True, а параметру Iskadr присваивается ссылка на звено, содержащее данный элемент.
Function Poisk (Adr: Adr2; Elem: <Тип_элемента_списка>; Var Iskadr: Adr2):
Boolean; {Adr – ссылка на заглавное звено;
Elem – искомый элемент;
Iskadr – адрес искомого элемента}
Var
P, Q: Adr2; {В Р будет храниться адрес заглавного
звена, в Q – адрес текущего звена}
B: Boolean;
Begin
B := False; {B – логическая переменная (факт
наличия искомого элемента)}
P := Adr; {В P занесен адрес заглавного звена}
Iskadr := Nil;
Q:=P^.Adrcled; {В Q занесен адрес первого звена}
While (P<>Q) And Not B Do {Поиск, пока не дошли до заглавного
звена и не нашли искомый элемент}
Begin
If Q^.Element = Elem Then {Найден искомый элемент}
Begin
B := True;
Iskadr := Q {Адрес искомого элемента}
End;
Q := Q^.Adrcled {Переход к следующему звену}
End;
Poisk := B {Возвращаемое значение}
End;
Очереди и стеки
В программировании имеется структура данных, называемая очередью. Понятие очереди в программировании аналогично понятию реальной очереди из повседневной жизни.
Очередь является динамической структурой. Длина очереди и набор образующих ее элементов изменяется с течением времени.
Над очередью определены две операции:
занесение элемента в очередь (заказа на обслуживание);
выбор элемента из очереди (для его обслуживания); выбранный элемент из очереди исключается.
В очереди доступны две позиции: ее начало (из этой позиции выбирается элемент из очереди) и конец (в эту позицию помещается заносимый в очередь элемент).
Различают два основные вида очередей, отличающиеся по дисциплине (способу) обслуживания находящихся в них элементов.
В первом виде очередей заказ, поступивший в очередь первым, выбирается первым для обслуживания и удаляется из очереди. Это дисциплину обслуживания очереди называют FIFO (First In – First Out – первый в очередь – первый из очереди).
Во втором виде очередей заказ, поступивший в очередь последним, выбирается первым для обслуживания и удаляется из очереди. Эту дисциплину обслуживания называют LIFO (Last In – First Out – последний в очередь – первый из очереди).
Очередь второго вида называется стеком.