Главная Учебники - Разные Лекции (разные) - часть 33
Міністерство освіти і науки України Національний технічний університет України "КПІ" Кафедра медичної кібернетики та телемедицини Лабораторна робота №2
Тема: Динамічні структури даних
Варіант №16 (задача 17.16).
Виконав:
студент ІМ-81 Плахтій Артур Миколайович Перевірив:
старший викладач Зінченко Ніна Павлівна Київ 2009 Содержание 1. Теоретическая часть Некоторые линейные списки Построение сложных структур в динамической памяти Бинарные деревья 2. Условия задачи Текст программы Екран результату Контрольні розрахунки Висновок Список літературних джерел Стек
создается как линейный список. Пусть Top
- указатель на начало стека. Стек удобно строить в обратном порядке. Следующий фрагмент программы демострирует основные операции работы со стеком: Type ukaz=stak, stak=record inf: integer, next: ukaz, end, Var Top,Tek: ukaz; value: integer Procedure DobavS; Begin new (Tek) readln (Tek. inf) Tek. next: =Top Top: =Teк End Procedure UdalS Begin Top: =Top. next if Top=0 then writeln (‘нехватка элементов’) End Для организация очереди
можно использовать аналогичный ссылочный тип, при этом необходимо иметь указатели на начальный nach
и конечный kon
элементы. Очередь удобно строить в прямом порядке (рис.1). Рис.1. Пример построения очереди в прямом порядке Циклически связанный список
(циклический список) - такой список, в котором связь от последнего узла идет к первому элементу списка. На рис.2 изображен односвязный циклический список. В нем можно получить доступ к любому элементу списка, отправляясь от любой точки. Рис.2. Пример циклического списка Наиболее важные операции для односвязных циклических списков: 1. включить элемент слева 2. включить элемент справа 3. исключить узел слева Если nach1
и nach2
указывают на два разных списка L1
и L2
(см. рис.3), то можно включить справа в список L1
весь список L2
, для чего нужно выполнить присваивания, используя промежуточную переменную PP
типа pointer
: Var PP: pointer {... } PP: =nach1. link nach1. link: =nach2. link nach2. link: = PP Рис.3. Циклический список L1 + L2 Каждый элемент списка с двумя связями
содержит два указателя: на соседние слева и справа элементы (см. рис.4). По такому списку удобно двигаться вперед и назад, так как он содержит два входа в список. Для создания двусвязного списка можно использовать следующий тип: Type ptr=element element=record d: integer right,left: ptr end Рис.4. Пример списка с двумя связями (двунаправленный список) Важное преимущество двусвязного списка состоит в том, что для того чтобы удалить элемент tek,
достаточно знать только адрес этого узла, так как адреса предыдущего и следующего элементов хранятся в tek. left
и tek. right
: tek. left. right: =tek. right tek. right. left: =tek. left Здесь вы можете проверить, как вы научились работать с двунаправленным списком. Списки с полутора связями
представляют собой чередование элементов с одной и двумя связями. Их преимущество: требуют меньше памяти, чем двусвязные, но ходить по списку можно вперед и назад. Рис.5. Пример списка с полутора связями С помощью указателей можно создавать самые разнообразные структуры, в том числе более сложные, чем простые линейные списки. Это обусловлено тем, что: 1) любой узел может быть началом другого списка; 2) один и тот же узел может быть включен в несколько различных списков. Применение указателей придает памяти гибкость, необходимую для представления структур, при этом может понадобиться комбинация элементов с одной и двумя связями. На рис.1 можно видеть пример структуры, которая содержит чередование элементов с 1 и 2 связями. Рис.1. Чередование элементов с 1 и 2 связями. Для реализации сложной структуры следует описать два типа элементов: Type ptr1=element1 element1=record info: string link: ptr1 end ptr2=element2 element2=record info: integer rlink,dlink: ptr2 end Поскольку элемент с одной связью присоединяется к элементу с двумя связями (т.е. элементу другого типа), при попытке прямого построения связи компилятор выдает сообщение об ошибке на несовместимость типов. Эту сложность можно обойти, используя промежуточную переменную типа pointer
. Пусть имеются следующие описания: Var E1: ptr1 E2: ptr2 p: pointer Тогда чтобы присоединить элемент Е1
к элементу Е2
, следует исполнить: p: = E1 E2. dlink: =p В частном случае, когда адресная часть элемента Е2
ссылается всегда только на адрес элемента одного и того же типа, можно пользоваться описанием: Type ptr2=element2 element2=record info: integer rlink: ptr2 dlink: ptr1 {здесь ссылка на элемент типа ptr1} end и тогда можно выполнять присваивание: Е2. dlink: = E1.
Деревья относятся к разряду структур, которые удобно строить в динамической памяти с использованием указателей. Наиболее важный тип деревьев - двоичные (бинарные) деревья, в которых каждый узел имеет самое большее два поддерева: левое и правое. Подробнее, если имеем дерево вида (рис.1a), то ему может соответствовать в динамической памяти структура (рис.1б). Рис.1. Двоичное дерево и его представление с помощью списочных структур памяти а - двоичное дерево; б - представление дерева с помощью списков с использованием звеньев одинакового размера Для построения такого бинарного дерева используется следующий ссылочный тип: Type Ptr=Node Node=record Info=Char Llink,Rlink=Ptr End Для работы с деревьями имеется множество алгоритмов. К наиболее важным относятся задачи построения и обхода деревьев. Пусть в программе дано описание переменных: var t: ptr; s: integer; c: char; b: boolean; Тогда двоичное дерево можно построить с помощью следующей рекурсивной процедуры: procedure V (var t: ptr) var st: string begin readln (st) if st<>'. 'then begin new (t) t. info: =st V (t. Llink) V (t. Rlink) end else t: =nil end Структура дерева отражается во входном потоке данных: каждой вводимой пустой связи соответствует условный символ (в данном случае точка). Для примера на рис.1 входной поток имеет вид: A B D. G... C E. F H. J...
Существует три основных способа обхода деревьев [1]: в прямом порядке, обратном и концевом. Обход дерева может быть выполнен рекурсивной процедурой и процедурой без рекурсии (стековый обход). В приведенной ниже рекурсивной процедуре выполняется обход дерева в обратном порядке. Рrocedure PR (t: ptr) {рекурсивный обход дерева} begin if t<>nil then begin PR (t. Llink) {обойти левое поддерево} writeln (t. info) {попасть в корень} PR (t. Rlink) {обойти правое поддерево} end end Нерекурсивный алгоритм обхода дерева в прямом порядке: Пусть T
- указатель на бинарное дерево; А
- стек, в который заносятся адреса еще не пройденных вершин; TOP
- вершина стека; P
- рабочая переменная. 1. Начальная установка: TOP: =0; P: =T.
2. Если P=nil
, то перейти на 4. {конец ветви} 3. Вывести P. info.
Вершину заносим в стек: TOP: =TOP+1; A [TOP]: =P;
шаг по левой ветви: P: =P. llink
; перейти на 2. 4. Если TOP=0
, то КОНЕЦ
. 5. Достаем вершину из стека: P: =A [TOP]; TOP: =TOP-1
; Шаг по правой связи: P: =P. rlink;
перейти на 2. 17.16.
Деревом поиска, или таблицей в виде дерева, называется двоичное дерево в котором слева от любой вершины находятся вершины с элементами, меньшими элемента из этой вершины, а справа - с большими элементами (предполагается, что все элементы дерева попарно различны и что их тип (ТЭД) допускает применение операций сравнения); пример такого дерева показан на рис.21. Считая описанными тип дерево (
см. выше) и тип файл
type файл=file of ТЭД; определить функцию или процедуру, которая: а) проверяет, входит ли элемент Е
в дерево поиска Т;
б) записывает в файл f
элементы дерева поиска Т
в порядке их возрастания; в) добавляет к дереву поиска Т
новый элемент Е,
если его не было в T
; uses crt; label 1,2,3; type BT=longint; u=BinTree; BinTree=Record inf: BT; L,R: U; end; var output, input: text; s,t: string; Tree,tree2: U; k,e: BT; b: byte; procedure insiter (var T: U; X: BT); var vsp,A: U; begin new (A); A. inf: =X; A. l: =nil; A. R: =nil; if T=nil then t: =a else begin vsp: =t; while vsp<>nil do if a. inf < vsp. inf then if vsp. L=nil then begin vsp. l: =a; vsp: =a. l end else vsp: =vsp. l else if vsp. R=nil then begin vsp. R: =a; vsp: =a. R end else vsp: =vsp. R; end end; function find (T: u; x: BT): boolean; begin if t=nil then find: =false else if t. inf=x then find: =true else if x <t. inf then find: =find (t. L,x) else find: =find (t. R,x) end; begin clrscr; s: =''; b: =1; while b<>0 do begin clrscr; writeln ('vvedite el dereva'); readln (e); t: =''; str (e,t); s: =s + t + ' '; insiter (tree,e); writeln ('prodoljut? (Varianti-0) '); readln (b); end; 1: clrscr; writeln (' chto vu xotite sdelat? '); writeln (' 1 - proverka nayavnosti elementa'); writeln (' 2 - zapis v fail elementov dereva'); writeln (' 3 - dobavleniye elementa'); writeln (' 4 - po faily stroit derevo'); writeln (' 0 - vuxod iz programmu'); write (' vash vubor: '); readln (b); case b of 1: begin write ('vvedite element: '); readln (e); writeln ('nayavnost elementa-',find (tree,e)); writeln ('press any key'); readkey; end; 2: begin {printtree (tree); } writeln ('Zapisano v file OUTPUT. TXT'); writeln; assign (output,'c: \output. txt'); rewrite (output); write (output,s); s: =''; close (output); writeln ('press any key'); readkey; end; 3: begin write ('vvedite element: '); readln (e); insiter (tree,e); end; 4: begin s: =''; assign (input,'c: \input. txt'); reset (input); read (input,s); close (input); writeln (s); writeln ('press any key'); readkey; end; 0: goto 2; end; goto 1; 2: writeln ('press any key'); readkey; end. Контрольними розрахунками містяться в самій програмі. Отримані результати легко перевірити, що підтверджує вірність роботи програми. Динамічні структури даних дозволяють гнучкіше та ширше використовувати можливості програмування. Дуже зручним у використанні є тип даних Паскаля Pointer та його комбінація з типом Record, що дає змогу реалізовувати списки та будь-які деревовидні структури даних. Середовище Турбо Паскаль та Делфі дозволяє вільно працювати з цими структурами. 1. Т. Рюттен, Г. Франкен. Турбо Паскаль 6.0. Торгово-издательское бюро BHV. Грифон. - К.: 1992. - 235 с. 2. Т.П. Караванова. Основи алгоритмізації та програмування. Форум. - К.: 2002. - 286 с. 3. І. Скляр. Вивчаємо мову программування PASCAL. http://distance. edu. vn. ua/metodic/pascal/ 4. Будникова Н.А. Обучающий комплекс по программированию на языке ПАСКАЛЬ http://petrsu.ru/Chairs/IMO/pascal/
|