Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Динамические структуры данных
Раздел: Рефераты по информатике, программированию
Тип: лабораторная работа Добавлен 01:34:24 08 июня 2009 Похожие работы
Просмотров: 117 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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

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

Лабораторна робота №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. исключить узел слева

Если 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.

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/

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:47:40 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:53:30 28 ноября 2015

Работы, похожие на Лабораторная работа: Динамические структуры данных

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150330)
Комментарии (1830)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru