Создание списков в языке Паскаль

Введение
1.Типы данных в языке Паскаль
2.Списки
2.1Линейный однонаправленный ( односвязный ) список
2.2Линейные двунаправленные списки
3.Структуры данных: стеки, очереди, деревья
3.1 Стек
3.2 Очередь
3.3 Деревья
Заключение
Список литературы

Создание списков в языке Паскаль

Однако место в памяти она занимает. Это и есть пример возникновения "мусора". На схеме показано, что произошло в результате выполнения оператора P := D.В Паскале имеется стандартная процедура, позволяющая освобождать память от данных, потребность в которых отпала. Ее формат: DISPOSE(<указатель>);Например, если динамическая переменная P^ больше не нужна, то оператор DISPOSE(P)удалит ее из памяти. После этого значение указателя P становится неопределенным. Особенно существенным становится эффект экономии памяти при удалении больших массивов. Описывая в программе с помощью определений структуру данных, мы создаем так называемые статические объекты или заранее определяемые объекты. Статическая структура данных характеризуется тем что:она имеет имя, которое используется для обращения кней; ей выделяется память в процессе трансляции программы;количество элементов сложной структуры (размерность) фиксировано при ее описании;размерность структуры не может быть изменена во время выполнения программы.Динамическая структура данных характеризуется тем что:она не имеет имени;ей выделяется память в процессе выполнения программы;количество элементов структуры может не фиксироваться;размерность структуры может меняться в процессе выполнения программы;в процессе выполнения программы может меняться характер взаимосвязи между элементами структуры. Каждой динамической структуре данных сопоставляется статическая переменная типа указатель (ее значение - адрес этого объекта) посредством которой осуществляется доступ к динамической структуре. Операция new позволяет выделить свободный участок в основной памяти (динамической), размеры которого соответствуют типу данных, определяемому именем типа. В случае успешного выполнения операция new возвращает адрес начала выделенного участка памяти, таким образом, создан (порожден) динамический объект. Если участок нужного размера не может быть выделен (нет свободной памяти нужного размера), то операция new возвращает нулевое значение адреса (NIL). В случае инициализации в выделенный участок заносится значение, определяемое инициализатором, т.е. динамическому объекту присваивается начальное значение, иначе значение динамического объекта не определено.Линейный однонаправленный ( односвязный ) список Список – это множество (возможно пустое) данных, имеющих некоторый общий смысл для решаемой задачи [12]. Статический список – это множество данных, которые располагаются в списке последовательно и непрерывно друг за другом. На языке Pascal статический список можно представить неоднородной структурой [8]:TypePerson =recordn: Integer;elem: btype[k];end;Здесь элемент с именем n определяет фактическое количество данных (элементов) в списке, если n равно 0, то список пуст, если n равно k, то список полон; элемент с именем elem (в данном случае массив) определяет само множество элементов списка, btype – базовый тип элемента списка.Динамический список – это множество данных, связанных между собой указателями [12, 13]. В линейном списке у каждого, составляющего его данного (элемента списка) есть один предшествующий и один следующий элемент (это справедливо для всех элементов кроме первого и последнего). Линейный односвязный список – это динамический список, каждый элемент которого состоит из двух полей. Одно поле содержит информацию (или ссылку на нее), другое поле содержит ссылку на следующий элемент списка. Элемент списка называют «звено» списка. Таким образом, список – это цепочка связанных между собой звеньев от первого до последнего.BA NIL NULL NULL тTEРис.1. Строка символов BETA представлена в виде списка Последнее звено ( рис.1.) не ссылается на следующий элемент, поэтому поле ссылки имеет значение NIL - пустой указатель. ETBA Рис. 2. Циклический списокПоследнее звено ссылается на первый элемент списка ( рис. 2.) - это циклический список.BA NULL TE Рис. 3. Заглавное звеноСписок имеет заглавное звено ( рис. 3.), которое ссылается на первый элемент списка. Его информационное поле, как правило, не используется. Заглавное звено позволяет обрабатывать первое звено списка также как и другие его звенья.По однонаправленному списку можно двигаться только в одном направлении – от первого (или заглавного) звена к последнему. Чтобы задать динамический список надо описать его звено. Так как звено состоит из полей разных типов, то описать его можно неоднородным типом – структурой.Задание типа элемента списка:Type U = ^Zveno;Zveno = Record Inf : BT; Next: U End; Здесь BT – тип информационного поля элемента списка, поле Next – ссылка на аналогичную структуру типа Zveno.Чтобы работать со списком как с единым объектом, надо ввести в употребление статическую переменную-указатель, значение которой – это адрес первого (или заглавного) звена списка. Если список пустой, она должна иметь значение NIL.Определение статической переменной-указатель:list :U ; listBA NULLTE Рис. 4.Статическая переменная-указатель list, называемая заголовком (или головой) списка (не путать с заглавным звеном) определяет список как единый объект. Используя указатель, можно обращаться к элементам списка (для списка на рис.4.).Выделим типовые операции над списками:добавление звена в начало списка; удаление звена из начала списка; добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан); удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан); проверка, пуст ли список; очистка списка; печать списка. 1. Добавление звена в начало списка{Процедура добавления звена в начало списка; в x содержится добавляемая информация} Procedure V_Nachalo(Var First : U; X : BT); Var Vsp : U; Begin New(Vsp); Vsp^.Inf := X; Vsp^.Next := First; {То звено, что было заглавным, становится вторым по счёту} First := Vsp; {Новое звено становится заглавным} End;2. Удаление звена из начала списка{Процедура удаления звена из начала списка; в x содержится информация из удалённого звена} Procedure Iz_Nachala(Var First : U; Var X : BT); Var Vsp : U; Begin Vsp := First; {Забираем ссылку на текущее заглавное звено} First := First^.Next; {То звено, что было вторым по счёту, становится заглавным} X := Vsp^.Inf; {Забираем информацию из удаляемого звена} Dispose(Vsp); {Уничтожаем звено} End;3. Добавление звена в произвольное место списка, отличное от начала (после звена, указатель на которое задан){Процедура добавления звена в список после звена, на которое ссылается указатель Pred; в x содержится информация для добавления} Procedure V_Spisok(Pred : U; X : BT); Var Vsp : U; Begin New(Vsp); {Создаем пустое звено} Vsp^.Inf := X; {Заносим информацию} Vsp^.Next := Pred^.Next; {Теперь это звено ссылается на то, что было следом за звеном Pred} Pred^.Next := Vsp; {Теперь новое звено встало вслед за звеном Pred} End;4. Удаление звена из произвольного места списка, отличного от начала (после звена, указатель на которое задан){Процедура удаления звена из списка после звена, на которое ссылается указатель Pred; в x содержится информация из удалённого звена} Procedure Iz_Spiska(Pred : U; Var X : BT); Var Vsp : U; Begin Vsp := Pred^.Next; {Забираем ссылку на удаляемое звено} {Удаляем звено из списка, перенаправив ссылку на следующее за ним звено} Pred^.Next := Pred^.Next^.Next; X := Vsp^.Inf; {Забираем информацию из удаляемого звена} Dispose(Vsp); {Уничтожаем звено} End;Линейные двунаправленные спискиДинамический список, в котором каждый элемент (кроме возможно первого и последнего) связан с предыдущим и следующим за ним элементами называется двусвязным [14]. Каждый элемент такого списка имеет два поля с указателями: одно поле содержит ссылку на следующий элемент, другое поле – ссылку на предыдущий элемент и третье поле - информационное. Наличие ссылок на следующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении: от звена к концу списка или от звена к началу списка, поэтому такой список называют еще и двунаправленным. Пример 1 ( строка символов BETA представлена двусвязным списком):A NIL B NULLETРис.5. Двунаправленный списокПервое звено не имеет ссылки на предыдущее, последнее звено не имеет ссылки на следующее звено ( рис.5.). A T E BРис.6. Кольцевой списокТакой список ( рис.6.) называют кольцевым ( циклическим ). Здесь первое звено имеет ссылку на последнее, а последнее звено на первое. Поэтому начинать обработку такого списка можно как с первого звена, так и с последнего.Двусвязный список может иметь заглавное звено (рис.7.). T B E AРис.7. Циклический список с заглавным звеномЗаглавное звено позволяет обрабатывать первое и последнее звенья также как другие. Возможны и другие структуры двусвязных списков. Задание двусвязного списка:Type U = ^Zveno;Zveno = Record Inf : BT; Next, Prev: U End; Здесь BT – тип информационного поля элемента списка.Next – указатель на следующий элемент.Prev – указатель на предыдущий элемент.Переменная-указатель list2:U задает список как единый программный объект, ее значение - указатель на первый (или заглавный) элемент списка (см. рис.6.).Основные операции, выполняемые над двусвязным списком, те же, что и для односвязного списка [15,14]. Так как двусвязный список более гибкий, чем односвязный, то при включении элемента в список, можно использовать указатель как на элемент, за которым происходит включение, так и указатель на элемент перед которым происходит включение. При исключении элемента из списка можно использовать как указатель на сам исключаемый элемент, так и указатель на элемент предшествующий или следующий за исключаемым. Но так как элемент двусвязного списка имеет два указателя, то при выполнении операций включения/исключения элемента надо изменять больше связей, чем в односвязном списке. Поиск элемента в двусвязном списке можно вести: а) просматривая элементы от начала к концу списка,б) просматривая элементы от конца списка к началу,в) просматривая список в обоих направлениях одновременно: от начала к середине списка и от конца к середине (учитывая, что элементов в списке может быть четное или нечетное количество).Структуры данных: стеки и очередиС помощью списков можно задавать различные структуры данных, такие как очереди и стеки.Стек – это список, у которого доступен один элемент (одна позиция) [16]. Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека. Очередь – это список, у которого доступны два элемента (две позиции) начало и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала[16,17]. Стеки и очереди могут быть организованы различными способами. При этом они могут быть размещены как в статической памяти, так и в динамической. Рассмотрим динамическое представление этих структур.Динамический стек можно задать линейным односвязным списком:Type U = ^Zveno;Zveno = Record Inf : BT; Next: U End; NIL вершина стека В стеке, представленном линейным односвязным списком, вершина стека – первый элемент списка. Ввести в употребление переменную типа стек можно следующим образомStack: U;Чтобы инициализировать динамический стек, т.е. создать пустой динамический стек достаточно указателю на вершину стека задать значение NIL: Stack = NIL. Обращение к значению элемента в вершине динамического стека: S^.InfОсновные операции над стеком ( S - переменная типа stack ): Таблица 1НазваниеОперацииДинамический способ определения стекаОчистить стек(создать стек)Поместить элемент в стекВзять элемент из стекаПроверка пуст ли стек?S:= NILДобавить элемент в начало линейного списка (смотри добавление элемента в начало однонаправленного списка) Элемент = S^.Inf;Удалить первый элемент из линейного списка, сделав первым следующий элемент списка: S =^.Next; Операция определена, если стек не пуст.Пуст(S)=true, если S = NILПуст(S)=false,если S!= NILВ динамической памяти очередь можно представить: а) линейным односвязным списком с двумя указателями:Type U = ^Zveno;Zveno = Record Inf : BT; Next: U End; ch3 = Record beg, end: Uend;NULL . . . начало конец beg end Задать динамическую очередь - это определить переменную типа ch3:Q1: ch3;Чтобы инициировать очередь достаточно указателю на начало Q1^.beg и на конец Q1^.end присвоить значение NIL. При взятии единственного элемента из очереди она должна стать пустой; б) линейным двусвязным циклическим списком с одним указателем: Type U = ^Zveno;Zveno = Record Inf : BT; Next, Prev: U End;… Здесь начало или конец очереди можно сделать как в начале, так и в конце списка. Кроме рассмотренных вариантов простых очередей существует понятие очереди с приоритетом. Элемент такой очереди имеет не только значение, но и вес или приоритет этого значения. При включении элемента в очередь с приоритетом сначала отыскивается место элемента в соответствии с его приоритетом. Элемент с наивысшим приоритетом помещается в начало очереди, элемент с низшим весом в конец очереди. Такой очереди наилучшим образом отвечает двусвязный циклический список. Основные операции над очередью аналогичны операциям со стеком (с учетом особенностей этой структуры).Еще одной разновидностью этих структур данных является дек [16,17]. Дек это список, у которого обе позиции: начало и конец списка доступны для добавления и взятия элемента. Таким образом, дек может быть и стеком, и очередью, и комбинацией этих структур. Наиболее часто дек представляется структурой с ограничением на вход или выход: дек с ограниченным входом (только одна позиция доступна для добавления элемента) и дек с ограниченным выходом (только одна позиция доступна для взятия элемента из дека).Структура данных деревьяДерево – это конечное множество T , возможно пустое, в противном случае, состоящее из одного или более элементов (узлов или вершин дерева) таких, что:а) имеется один специально обозначенный элемент, называемый корнем данного дерева; б) остальные элементы содержатся в m >0 попарно непересекающихся множествах T1 , . . . ,Tm , каждое из которых в свою очередь является деревом; деревья T1 , . . . , Tm называются поддеревьями данного корня (рис.8.а) [20].DEFBCAJGH а б Рис.8а)дерево; б)бинарное деревоЕсли имеет значение относительный порядок поддеревьев T1, . . . ,Tm , то говорят, что дерево является упорядоченным. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом (или листом или терминальным узлом), все остальные элементы – внутренние узлы (нетерминальные). Максимальная степень всех вершин называется степенью дерева. Корень дерева имеет уровень равный 0. Остальные вершины имеют уровень на единицу больше уровня непосредственного предка. Максимальный уровень какой-либо из вершин называется глубиной или высотой дерева. Минимальная высота при заданном числе вершин достигается, если на всех уровнях, кроме последнего, помещается максимально возможное число вершин. Максимальное число вершин в дереве высотой h достигается в том случае, если из каждой вершины, за исключением уровня h, исходят d поддеревьев, где d – степень дерева: на 0-м уровне 1 вершина, на 1-м – d потомков, на 2-м – d2 потомков, на 3-м уровне d3 потомков и т.д. Наиболее широко используются двоичные (бинарные) деревья (рис.8.б). Бинарное дерево это конечное множество элементов, которое либо пусто, либо состоит из корня и из двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня. Таким образом, каждый элемент бинарного дерева имеет 0, 1 или 2 поддерева.