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

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

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

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

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

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

Варіант №16 (задачі № 16.13(а), 16.18(а),16.33).

 

Виконав:

студент ІМ-81

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

Перевірив:

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

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

Київ 2009


Теоретичначастина

 

1.Динамические структуры данных

Ранее изучаемые типыданных относятся к так называемым статическим. Память под них выделяется вовремя компиляции, количество таких объектов не меняется во время выполненияпрограммы. Однако существует ряд задач, где статические структуры неэффективны.В языке Паскаль имеются средства создания динамических структур данных, которыепозволяют во время выполнения программы:

·          образовыватьобъекты;

·          выделять для нихпамять;

·          уничтожать, когдав них исчезает необходимость.

Другое названиединамической памяти – куча.

Для получения ясногопредставления о динамических переменных надо рассмотреть структуру памяти вовремя выполнения программы на языке Паскаль (см. рис.1).

Данные в динамическойпамяти размещают с использованием указателей. Указатель — это ссылка наопределенную ячейку памяти, начиная с которой записывается значение переменной,поэтому данные такого типа называются еще и ссылочным типом данных.

Формат описанияссылочного типа данных:

Type <типуказателя> = ^ <идентификатор типа>,

то есть указатель связанс некоторым типом данных. Такие указатели называются типизированными.

Пример описанияпеременных ссылочного типа:

Type

p1=^integer;

p2=^real;

Var

A,B,C:p1;

X,Y,Z:p2;

P:char;

Cсылочные переменные A,B, C указывают на динамические объекты целого типа, X,Y,Z — вещественного, P — символьного. Значением ссылочной переменной является адрес в динамическивыделенной памяти, где хранится объект этого типа.

/>

Рис. 1. Структура памятиво время выполнения программы

Для обращения к ссылочнойпеременной используют запись “ A^ ”, что означает: ”идти по адресу, хранящемусяв A”. Память под указатели отводится на этапе компиляции.

Однако в Турбо Паскалеможно объявлять указатель и не связывать его с конкретным типом данных. Такойуказатель называется нетипизированным. Для его объявления служит стандартныйтип pointer. Структура и тип таких данных могут меняться во время выполненияпрограммы.

При работе с указателямиобязательны этапа два:

1.        объявлениеуказателя;

2.        формированиединамических данных, память которых отводится во время выполнения программы.

Для работы с указателямииспользуются следующие процедуры:

New(P) — процедура, которая создает вдинамической памяти новую переменную. Р — указатель переменной того типа,который надо создать. Каждая отдельная процедура new может создать только однудинамическую переменную.

Dispose(P) — процедура, позволяющая вернуть вкучу участок памяти, занятый объектом с указателем Р.

Параметрами процедур newи dispose может быть только типизированный указатель. Для работы снетипизированными указателями используются аналогичные процедуры:

GetMem(P,Size) — резервирование памяти;

FreeMem(P,Size) — освобождение памяти.

Здесь Р — нетипизированный указатель,Size — размер в байтах требуемой или освобождаемойчасти кучи ( до 65521 байт).

Над указателями могутбыть определены операции проверки на равенство и присваивание (рис.2):

/>

Рис. 2. Допустимоеприсваивание

Пример.

Var x,y:^integer;

Begin

new(x); {порождаемдинамический объект целого типа}

x^:=13; {по адресу xзаносим значение 13}

y:=x; {в у заносимзначение того же адреса, что и х}

writeln(y^);

end.

Ссылочной переменнойможет быть присвоенной “пустое” значение адреса, обозначенное служебным словом nil,что означает, что ссылочная переменная не указывает ни на один динамическийобъект. Это присваивание можно делать до выполнения процедуры new. Значение nil- это два нулевых слова. Оно может быть присвоено указателю любого типа.

Динамически размещенныеданные можно использовать в любом месте программы, например:

Var a, b, c =^ real;

Begina^:=sqr(b^)+c^-17;

Недопустимо писатьa:=sqr(b^), так как указателю нельзя присвоить значение вещественноговыражения.

2.Линейные списки. Стек, очередь

Указатели являютсяэффективным средством построения списковых структур, к которым относятся, вчастности, линейные списки.

Линейный список — это множество, состоящее изпеременного числа узлов X[1], X[2],…, X[n].

Структурные свойстватакого списка:

1.        Если n>0, тоХ[1] является первым узлом;

2.        Если 1<k<n,то k-му узлу Х[k] предшествует Х[k-1] и за ним следует Х[k+1];

3.        Х[n] являетсяпоследним узлом.

Среди возможных списковыхструктур выделяют некоторые специальные списки.

Стек — это линейный список, в котором всевключения и исключения (и обычно всякий доступ) делаются в одном конце списка

Наглядный пример стеков:стопка подносов в столовой, железнодорожный тупик. Стеки используются в работеалгоритмов, имеющих рекурсивный характер. Конец стека называется вершиной стека.Принцип работы стека — “последний пришел — первый вышел”. Внизу находитсянаименее доступный элемент. Часто говорят, что элемент опускается в стек.

Очередь — это линейный список, в один конецкоторого добавляются элементы, а с другого конца исключаются. Принцип работыочереди: ”первый пришел — первый вышел”.

3.Организация списков в динамической памяти

Для организации списков используютсяструктуры типа запись, состоящие из двух частей: информационной, где собственнои находятся данные, и ссылочной, содержащей указатель на следующий элементсписка (рис.1). Cоздадим в динамической памяти структуру:

/>

Рис. 1. Пример списковойструктуры

где Di — данные. Чтобыполучить доступ к данным, достаточно хранить в памяти адрес начала этого спискаnach.

В языке Турбо Паскальпоследовательно проводится принцип, согласно которому, идентификатор, перед егоиспользованием, должен быть описан. Исключение сделано только для указателей,которые могут ссылаться на еще не объявленный тип данных. Для описанияэлементов структуры подобной изображенной на рис. 3 можно использоватьследующий ссылочный тип:

Typeelement=^Ptr;

Ptr=record

d:integer;

link:element;

end;

Список в динамическойпамяти можно создавать в прямом или обратном порядке (относительно последовательностивводимых элементов).

Пример создания списка в обратном порядке(см. рис.2):

/>

Рис. 2. Пример созданиясписка в обратном порядке

Vari,n,a:integer;

tek,nach:Ptr;

Begin

tek:=nil;

readln(n);

for i:=1 to ndo

begin

readln(a);

new(nach);

nach^.d:=a;

nach^.link:=tek;{цепочка присоединяется к nach}

{*} tek:=nach;

end;

end;

Обратим внимание на вызовпроцедуры new(nach). В результате этого вызова в динамической памяти отводитсяместо для переменной типа record, которая в нашем случае состоит из двух полей:для хранения целочисленного значения и значения указателя, т.е. адреса. Здесьважно представлять, что после того, как переменная nach (или какая другая) созданав динамической памяти, тем самым имеем ее адрес, который сам является именемпеременной, т.е. nach. Если у нас имеется другая переменная того же типа, tek,то мы знаем также и ее адрес, это tek. Поэтому, если в адресную частьпеременной nach занести адрес tek, тем самым мы свяжем элементы nach и tek: nach^.link:=tek.

Алгоритм создания спискав прямом направлении:

1. Создать первый элементnach.

Ввести nach^.d; pred:=nach;

2. Создать текущийэлемент tek.

Ввести tek^.d;

Установить связьпредыдущего с текущим: pred^.link:=tek;

текущий элементстановится предыдущим: pred:=tek;

3. Если не конец списка,то перейти на 2.

Обнулить адресную частьпоследнего элемента: tek^.link:=nil.

/>

Рис. 3. Пример созданиясписка в прямом направлении

Таким образом, дляобращения к списку достаточно хранить в памяти адрес первого элемента nach.Посколькукаждый элемент хранит адрес следующего за ним элемента, можно, двигаясь отначального элемента по адресам, получить доступ к любому элементу списка.

Просмотреть элементысписка можно следующим образом:

tek:=nach;{Встали наначало списка}

while tek<>nil do

begin

wtiteln(tek^.d);{Вывестиинформационную часть}

tek:=tek^.link; {Шаг посвязи}

end;

Рассмотрим еще раз строкуtek:=tek^.link;. Ее можно интерпретировать по-другому: значению адреса tek присвоитьто, что хранится в адресной части элемента tek, а там хранится адрес элемента,следующего за tek. Вообще нотацию tek^.link следует различать в контексте еенахождения: если она стоит слева от присваивания, имеется ввиду сама адреснаячасть элемента tek, а если справа от присваивания – то, что хранится в адреснойчасти tek. Таким образом, например, tek^.link:=tek^.link будет означать: вадресную часть tek занести адрес элемента, следующего за tek.

С построенным спискомможно выполнять различные операции: добавлять и удалять элементы в любом местесписка, причем в зависимости от местоположения элемента эти операции имеют своиособенности.

Алгоритм добавленияэлемента в начало списка:

1. Создать новый элемент nov.

Ввести информационнуючасть nov^.d.

2. Построить связь: nov^.link:=nach.

3. Новый элемент сделатьначальным: nach=nov.

/>

Рис. 4. Добавлениеэлемента в начало списка

Нетрудно удалить первыйэлемент (nach:=nach^.link). Главное — не забыть физически удалить его из памяти(процедура Dispose).

Добавление элемента всередину списка: пустьпеременная tek указывает на элемент, после которого необходимо вставить всписок элемент nov. Сначала нужно заполнить связь у элемента nov:nov^.link:=tek^.link; затем соединить tek и nov: tek^.link:=nov.

/>

Рис. 5. Добавлениеэлемента в середину списка

Добавление элемента вконец списка (рис.6).Пусть переменная pos указывает на последний элемент списка, nov – добавляемыйэлемент. Тогда операция pos^.link:=nov соединяет элементы; присваивание nov^.link:=nilобнуляет адресную часть нового элемента.

/>

Рис. 6. Добавление элементав конец списка

Удаление элемента изсередины списка. Пустьпеременная pred — элемент, предшествующий удаляемому элементу. Необходимо идтипо ссылке, хранящейся в pred в поле link (адрес удаляемого элемента), затемидти по ссылке link удаляемого элемента (а это адрес следующего за удаляемым).Полученное значение записать в поле link элемента pred:pred^.link:=pred^.link^.link.

/>

Рис. 7. Удаление элементаиз списка

Исключение последнегоэлемента. Пусть pos — последний элемент, pred– предыдущий перед последним. Тогда присваивание pred^.link:=nilисключит последний элемент из цепи (рис. 8).

/>

Рис. 8. Исключениепоследнего элемента из списка

Умова задачі

16.13.Одно из возможных представлений «длинного» текста —это разделить его на участки(строки) равной длины и создать массив ссылок на эти строки:

constd=…; {длина строки}

 n=...;{максим, число строк}

type строка = array [l..d] of char,

 ссылка =^строка;

 текст =array [l..n] of ссылка;

(Если втексте менее п строк, то последние элементы массива равны nil; в начале массивассылок nil не должно быть. Если, в операции над текстом указан номеротсутствующей строки, т. е. элемент массива с этий номером равен nil, то такаяоперация не выполняется.)

Используяданное представление текста, описать:

а)      функциючислострок(Т) для подсчета числа строк в тексте Т;


Алгоритм

/>


/>


/>


/>


/>


/>


/>


/>


/>

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

program fwg;

uses crt;

const d=4;

n=40;

type stroka=array [1..d] of char;

nodepoint=^stroka;

Mas=array [1..n] of nodepoint;

Var f:text;

procedure kilkist(var k2:integer);

var ch:char;

begin

assign(f,'c:\f.txt');

reset(f);

k2:=0;

while not eof(f) do begin

read(f,ch);

k2:=k2+1;

end;

close(f);

end;

Function Kil(var cur1:mas):integer;

var i:integer;

begin

i:=1;

while (cur1[i]<>nil) and (i<>n) do begin

i:=i+1;

end;

kil:=i-1;

end;

procedure chut(var cur1:mas);

var ch:char;i,j:integer;

begin

Assign(f,'c:\f.txt');

reset(f);

for i:=1 to n do

cur1[i]:=nil;

i:=1;

while (not eof(f)) and (i<n+1) do begin

new(cur1[i]);

j:=1;

while (j<d+1) and (not eof(f)) do begin

read(f,ch);

write(ch);

Cur1[i]^[j]:=ch;

j:=j+1;

end;

i:=i+1;

end;

close(f);

end;

procedure Vuvod(cur2:mas);

var i,j,k3:integer;

begin

i:=1;

kilkist(k3);

while cur2[i]<>nil do begin

writeln;

if (cur2[i+1]=nil) and (k3 mod 4<>0) then begin

for j:=1 to (k3 mod 4) do

write(cur2[i]^[j]);

end

else begin

for j:=1 to d do

write(cur2[i]^[j]);

end;

i:=i+1;

end;

end;

Var first:mas;q:integer;cha:char;

begin

ClrScr;

Chut(first);

readln;

Vuvod(first);

writeln;

readln;

q:=kil(first);

writeln('Kilkist strok:', q);

readln;

end.

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

/>

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

Контрольними розрахункамимістяться в самій програмі. Отримані результати легко перевірити, що підтверджуєвірність роботи програми.


Умова задачі

Описатьпроцедуру, которая вставляет:

а)      вначало списка L новый элемент E;

Алгоритмрозв’язку задачі


/>


/>


/>


/>


/>


/>


/>


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

program Kill_Bill;

uses Crt;

type nodepoint=^node;

node=record

info:integer;

next:nodepoint;

end;

function Vvodsp(n1:integer):nodepoint;

var cur,firs:nodepoint;i:integer;

begin

if n1=0 then begin

Vvodsp:=nil;

end else

if n1=1 then begin

new(cur);

writeln('Vvedenya elementu spusku');

readln(cur^.info);

cur^.next:=nil;

Vvodsp:=cur;

end else

begin

new(cur);

write('Vvedenya elementu spusku: ');

readln(cur^.info);

cur^.next:=nil;

firs:=cur;

for i:=1 to n1-1 do begin

new(cur^.next);

write('Vvedenya elementu spusku: ');

readln(cur^.next^.info);

cur:=cur^.next;

cur^.next:=nil;

end;

Vvodsp:=firs;

end;

end;

procedure Vuvodsp(cur1:nodepoint);

begin

Writeln('Vuvedenya spusku');

while cur1<>nil do begin

writeln(cur1^.info);

cur1:=cur1^.next;

end;

end;

procedure Add_first(var cur:nodepoint;elem:integer);

var tm:nodepoint;

begin

new(tm);

tm^.info:=elem;

tm^.next:=cur;

cur:=tm;

end;

Procedure del(var cur2:nodepoint);

var cur:nodepoint;

begin

while cur2<>nil do begin

cur:=cur2^.next;

dispose(cur2);

cur2:=cur;

end;

end;

var n,E:integer;cur,L:nodepoint;

begin

ClrScr;

Write('Vedit kilkist elementiv spusku: ');

readln(n);

L:=Vvodsp(n);

writeln;

readln;

Vuvodsp(L);

writeln;

readln;

write('Enter the element which must be added to list: ');

readln(E);

Add_first(L,E);

Vuvodsp(L);

readln;

del(L);

end.


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

/>

Умовазадачі

16.33.Пусть L обозначает кольцевой (циклический) двунаправленный список с заглавнымзвеном (рис. 15) при следующем описании такого списка;

typeТЭ2=...; {тип элементов списка}

список2=^звено2;

звено2=гecordэлем: ТЭ2;

пред, след: список2end;

и пусть Еобозначает величину типа ТЭ2.<sup/>Описать функцию или процедуру,которая:

г)       определяет,есть ли в списке L хотя бы один элемент, который равен следующему за ним (покругу) элементу;

ж)      изсписка L, содержащего не менее двух элементов, удаляет все элементы, у которыходинаковые «соседи» (первый и последний элементы считать соседями);


Алгоритм розв’язку задачі

/>


/>


/>


/>


/>


/>


/>


/>


/>


/>


/>

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

program wqetg;

uses Crt;

type Nodepoint=^node;

 node=record

 count:integer;

 next:nodepoint;

 before:nodepoint;

 end;

type nod=^nodepoint;

function Vvodsp(n:integer):nodepoint;

var j:integer;firs,cur1,cur:nodepoint;

begin

new(cur1);

writeln('Vedit Spisok');

cur1^.count:=0;

firs:=cur1;

cur1^.before:=nil;

cur1^.next:=nil;

for j:=1 to n do begin

new(cur1^.next);

cur1^.next^.before:=cur1;

cur1:=cur1^.next;

cur1^.next:=nil;

readln(cur1^.count);

end;

cur:=firs^.next;

cur1^.next:=cur;

cur^.before:=cur1;

Vvodsp:=firs;

end;

procedure Vuvodsp(head:nodepoint);

var cur:nodepoint;

begin

cur:=head^.next;

head:=head^.next;

writeln(head^.count);

head:=head^.next;

while head<>cur do begin

writeln(head^.count);

head:=head^.next;

end;

end;

function Kilkist(head:nodepoint;var cur:nodepoint):integer;

begin

if head=nil then Kilkist:=0

else if cur^.next=head then Kilkist:=1

else kilkist:=kilkist(head,cur^.next)+1;

end;

procedure DelEl(var cur:nodepoint);

var tm1,tm2:nodepoint;

begin

tm1:=cur^.before;

tm2:=cur^.next;

dispose(cur);

tm1^.next:=tm2;

tm2^.before:=tm1;

end;

procedure Del_Alike_n(var head:nodepoint);

var cur,cur2:nodepoint;b:boolean;

begin

b:=true;

cur:=head^.next;

cur2:=head^.next^.next;

while (b) do begin

b:=false;

while not(cur^.next=head^.next) do

begin

if cur^.count=cur2^.count then

begin

b:=true;

DelEl(cur2);

cur2:=cur^.next;

end

else

begin

cur:=cur^.next;

cur2:=cur2^.next;

end;

end;

end;

end;

var first,cur:nodepoint;m:integer;

begin

ClrScr;

writeln('Vedit kilkist elementiv spusku');

readln(m);

first:=Vvodsp(m);

writeln;

readln;

Vuvodsp(first);

Writeln;

readln;

Vuvodsp(first);

writeln;

readln;

cur:=first;

writeln(kilkist(first^.next,first^.next));

readln;

Del_Alike_n(first);

writeln('Spusok bez odnakovux susidiv: ');

Vuvodsp(first);

readln;

{del(first);}

end.

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

/>


Висновок

Динамічні структури данихдозволяють гнучкіше та ширше використовувати можливості програмування. Дужезручним у використанні є тип даних Паскаля Pointer та його комбінація з типомRecord, що дає змогу реалізовувати списки та будь-які деревовидні структуриданих. Середовище Турбо Паскаль та Делфі дозволяє вільно працювати з цимиструктурами.


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

1.        Т. Рюттен, Г.Франкен. Турбо Паскаль 6.0. Торгово-издательськое бюро BHV. Грифон. — К.: 1992.- 235 с.

2.        Т. П. Караванова.Основи алгоритмізації та програмування. Форум. — К.: 2002. — 286 с.

3.        І.Скляр. Вивчаємомову программування PASCAL. distance.edu.vn.ua/metodic/pascal/

4.        Будникова Н.А. Обучающий комплекс попрограммированию на языке ПАСКАЛЬ petrsu.ru/Chairs/IMO/pascal/

еще рефераты
Еще работы по информатике, программированию