Лабораторная работа : Динамические структуры данных (работа 1) 


Полнотекстовый поиск по базе:

Главная >> Лабораторная работа >> Информатика, программирование


Динамические структуры данных (работа 1)




Міністерство освіти і науки України

Національний технічний університет України "КПІ"

Кафедра медичної кібернетики та телемедицини

Лабораторна робота №2

Тема: Динамічні структури даних

Варіант №16 (задача 17.16).

Виконав:

студент ІМ-81

Плахтій Артур Миколайович

Перевірив:

старший викладач

Зінченко Ніна Павлівна

Київ 2009

Содержание

1. Теоретическая часть

Некоторые линейные списки

Построение сложных структур в динамической памяти

Бинарные деревья

2. Условия задачи

Текст программы

Екран результату

Контрольні розрахунки

Висновок

Список літературних джерел

1. Теоретическая часть

Некоторые линейные списки

Стек создается как линейный список. Пусть 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. исключить узел слева

Если nacH2 и nacH3 указывают на два разных списка L1 и L2 (см. рис.3), то можно включить справа в список L1 весь список L2, для чего нужно выполнить присваивания, используя промежуточную переменную PP типа pointer:

Var PP: pointer {... } PP: =nacH2. link nacH2. link: =nacH3. link nacH3. 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.

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/

Похожие работы:

  • Динамические структуры данных: списки

    Реферат >> Информатика, программирование
    Динамические структуры данных: списки Введение В языках программирования (Pascal, C, ... . В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера. Работа с динамическими величинами связана ...
  • Динамические структуры данных: очереди

    Реферат >> Информатика, программирование
    Динамические структуры данных: очереди Очередь — это информационная структура, в которой для добавления элементов доступен ... vsp; } Список литературы Для подготовки данной работы были использованы материалы с сайта ...
  • Динамические структуры данных: стеки

    Реферат >> Информатика, программирование
    Динамические структуры данных: стеки Стек — динамическая структура данных, представляющая из ... организовать на базе любой структуры данных, где возможно хранение ... однонаправленных списков (см. материал "Динамические структуры данных: списки"). { Turbo Pascal, ...
  • Динамические структуры данных: стеки

    Доклад >> Информатика, программирование
    Динамические структуры данных: стеки Стек — динамическая структура данных, представляющая из ... организовать на базе любой структуры данных, где возможно хранение ... однонаправленных списков (см. материал "Динамические структуры данных: списки"). { Turbo Pascal, ...
  • Динамические структуры данных: двоичные деревья

    Реферат >> Информатика, программирование
    Динамические структуры данных: двоичные деревья Дерево — это ... отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами ... вхождение. Список литературы Для подготовки данной работы были использованы материалы с ...
  • Динамические структуры данных

    Лабораторная работа >> Информатика, программирование
    ... їв 2009 Теоретична частина 1. Динамические структуры данных Ранее изучаемые типы данных относятся к так называемым статическим ... . В языке Паскаль имеются средства создания динамических структур данных, которые позволяют во время выполнения ...
  • Динамические структуры данных

    Курсовая работа >> Информатика, программирование
    ... разделе мы ознакомимся с динамическими структурами данных и собственно стеком. Достоинства динамических структур данных Динамические структуры данных по определению характеризуются отсутствием ...
  • Динамические структуры данных: дек

    Курсовая работа >> Информатика, программирование
    ... 2008 Содержание Введение Постановка задачи Динамические структуры данных: дек Описание алгоритма Приложение 1. Текст ... дека на наличие в нем элементов. Динамические структуры данных: дек В языках программирования существует такой ...
  • Динамические структуры данных. Решение задач. Стек. Очередь. Дек

    Курсовая работа >> Математика
    ... способ распределения памяти называется динамическим. Существуют множество типов динамических структур данных, среди них, такие ... , то – последнего элемента. Заключение: Использование динамических структур данных эффективно применять при решении задач ...
  • Структуры данных

    Реферат >> Математика
    ... I: I - это отображение M -> [ 1.. |M| ]. 3. Абстрактные структуры данных. Наиболее часто встречающимися абстрактыми структурами данных являются строка, граф ... мы уже сталкивались когда рассматривали динамические структуры данных. Когда мы не можем фиксировать ...