Основи
програмування
Національний
технічний університет України
«Київський
політехнічний інститут »
Факультет
інформатики та обчислювальної техніки
Кафедра
обчислювальної техніки
Київ 2000
Динамічне розподіл
пам'яті. Спискові структури. Технічні характеристики пропонованого модуля
для роботи з односвязним списком. Лістинг модуля Dinamo. Лістинг програми, при написанні якої був використаний
модуль Dinamo.
У мові програмування
Паскаль, як і в інших мовах, завжди багато використовуються змінні. У Паскалі
всі змінні, які ми використовуємо в програмі, повинні бути попередньо описані,
тобто, повинен бути зазначений їх тип: ціле число, рядок і т.п. Але часто не
можливо заздалегідь знати, якого типу мінлива нам буде потрібна. Для цих цілей
і служать динамічні змінні, або покажчики. Для їх створення слід перед
ідентифікатором вставити спеціальний символ ^. Перед тим, як в програмі можна
буде використовувати динамічні змінні, слід виділити пам'ять, куди будуть
накопичуватися значення відповідного типу. Тільки після цього покажчик
буде містити дійсну адресу пам'яті. Розміщення динамічних змінних
проводиться в спеціальній області пам'яті Heap.
Динамічні змінні нічим не відрізняються від звичайних змінних. Над ними
можна робити всі дії, що і з звичайними змінними. Для роботи з
динамічним розподілом пам'яті дуже зручно використовувати пов'язані
структури даних, наприклад односвязние списки.
Найпростішим прикладом списку
є масив, в якому послідовно розташовані всі його елементи. Але у
такого подання є істотний недолік - потрібно заздалегідь точно
вказати кількість елементів масиву. Тому краще скористатися більш
гнучким механізмом - динамічними змінними. Наочно це виглядає так:
Перший елемент
Останній елемент
У схемі кожен елемент розбитий на
два логічних поля: Curr - позначає всі змістовні
дані, і Next - покажчик на наступний елемент списку. В останнього
елемента покажчик встановлений в Nil, що використовується
для ініціалізації не розподілених динамічних змінних. Даний список
називається односвязним, оскільки рух від елемента до елемента в ньому
відбувається тільки в одному напрямку. Односвязний список використаний в модулі Dinamo як один з варіантів роботи з динамічними структурами.
Як відбувається робота з елементами
односвязного списку, наприклад, вставка нового елемента? Найкраще це можна
проілюструвати наступним малюнком на прикладі односвязного списку з трьох
елементів.
Як ми бачимо, перші дією
вказівником нового елемента присвоюється значення покажчика другого елементу (на
останній елемент списку), другий дією розривається зв'язок між другим і
останнім елементом, а замість цього покажчик другого елементу зв'язується з
новим елементом списку.
У даній програмі для роботи з
динамічно розподіляє областю використовуються процедури New (Var P
: Pointer) і Dispose (Var P: Pointer). Перша дозволяє створити в Heap-області
нову динамічну змінну, використовуючи при цьому весь вільний кількість
пам'яті, яке потрібно для значення заданого типу даних. Процедура Dispose звільняє динамічну змінну, виділену для Р за
відповідному викликом New. Після виклику Dispose будь-які звернення до значення Р ^ можуть призвести до помилок. Те
Тобто, кожному викликом New повинен відповідати виклик Dispose.
У розробці запропонованої
програми і модуля також був використаний процедурний тип даних. Процедурні
типи даних дозволяють інтерпретувати процедури та функції як об'єкти, які
можна використовувати при визначенні змінних і передачі параметрів. У
програмі при виклику такої змінної з відповідними їй параметрами
відбувається виконання призначеної їй процедури або функції. Синтаксис запису
опису процедурного типу відповідає синтаксису звичайного заголовка
процедури або функції.
Технічні характеристики
пропонованого модуля для роботи з односвязним списком.
У даному модулі реалізовані всі
основні функції, які необхідні для якісної роботи з даними, а
саме: створення, вставка, пошук, видалення або перегляд інформації, що міститься
в односвязном списку.
У процедурі, яка дозволяє
створювати нові записи, можливий безпосереднє введення інформації з клавіатури.
Це забезпечує певну мобільність програми.
Процедура вставки забезпечує
запис нового, введеної з клавіатури, елемента в те місце списку, яке
користувач вважає за необхідне.
Процедура видалення також
забезпечує видалення елемента, попередньо знайденого у списку, в якому б
місці списку він не перебував.
Перегляд забезпечує
послідовний, починаючи з першого елементу, перегляд всіх елементів,
що містяться в списку. Управління переглядом здійснюється клавішею
"пробіл".
Даний модуль зручний у
використанні, управління окремими процедурами вимагає певної
попередньої типізації.
Лістинг
програми program dinamo 11;
uses Crt, Graph;
type
pitem = ^ adresses;
adresses = record
inf: string;
next: pitem;
prev: pitem;
end;
var
tcurr, tfirst, tlast, dont, temp: pitem;
r:
char;
adre: string;
a
: Integer;
Procedure Novoe;
begin
if tfirst = Nil then
begin
new (tcurr);
writeln ( 'Адреса');
readln (adre);
tcurr ^. inf: = adre;
tcurr ^. next: = nil;
tfirst: = tcurr;
end
else
begin
writeln ( 'adresses');
readln (adre);
new (tcurr ^. next);
tcurr: = tcurr ^. next;
tcurr ^. inf: = adre;
end;
tcurr ^. next: = nil;
dont: = tcurr;
end;
Procedure Prosm;
begin
tcurr: = tfirst;
while tcurr <> nil do
begin
writeln (tcurr ^. inf);
repeat
r: = readkey;
until r in [# 32];
tcurr: = tcurr ^. next;
end;
tcurr: = dont;
repeat
until keypressed;
end;
Procedure Poisk;
begin
a: = 0;
writeln ( 'Chto iskat ?');
readln (adre);
tcurr: = tfirst;
while tcurr <> nil do
begin
if
tcurr ^. inf <> adre then
tcurr: = tcurr ^. next
else
begin
writeln (tcurr ^. inf);
tcurr: = nil;
a: = 1;
end;
end;
if a = 0 then
begin
writeln ( 'Not found');
end;
tcurr: = dont;
repeat
until keypressed;
end;
Procedure Vstavka;
begin
a: = 0;
writeln ( 'Posle chego vstavka ?');
readln (adre);
if adre = '-' then
begin
new (temp);
writeln ( 'Chto ?');
writeln ( 'adresses');
readln (adre);
temp ^. inf: = adre;
temp ^. next: = tfirst;
tfirst: = temp;
end
else
begin
tcurr: = tfirst;
begin
while tcurr <> nil do
begin
if tcurr ^. inf <> adre then tcurr: = tcurr ^. next
else
if (tcurr ^. next = nil) and (a = 0) then
begin
Novoe;
a: = 1;
tcurr: = nil;
end
else
if (tcurr <> nil) and (a = 0) then
begin
new (temp);
writeln ( 'Chtooo ?');
writeln ( 'adresses');
readln (adre);
temp ^. inf: = adre;
temp ^. next: = tcurr ^. next;
tcurr ^. next: = temp;
tcurr: = dont;
a: = 1;
end;
end;
end;
end;
if a = 0 then writeln ( 'Not found');
repeat
until keypressed;
tcurr: = dont;
end;
Procedure Deleting;
begin
writeln ( 'Chto deletet ?');
readln (adre);
tcurr: = tfirst;
temp: = tfirst;
while tcurr <> nil do
begin
if
tcurr ^. inf <> adre then
begin
temp: = tcurr;
tcurr: = tcurr ^. next;
end
else
begin
if tcurr = tfirst then
begin
tfirst: = temp ^. next;
tcurr: = dont;
end
else
if tcurr ^. next = nil then
begin
temp ^. next: = tcurr ^. next;
tcurr: = temp;
tcurr ^. next: = nil;
dont: = tcurr;
end
else
begin
temp ^. next: = tcurr ^. next;
tcurr: = temp;
end;
end;
end;
tcurr: = dont;
writeln ( 'Alles');
repeat
until keypressed;
end;
begin
(programmka)
tfirst: = nil;
repeat
(clrscr;)
writeln ( '(С) оздавать, (П) росмотр, (У) даленіе, По (и) ск, (B) ставка');
repeat
r: = readkey;
until r in [ 'c', 'g', 'b', 'd', 'e', # 27];
case r of
'c': Novoe;
'g': Prosm;
'b': Poisk;
'd': Vstavka;
'e': Deleting;
end;
until r = # 27;
(dispose (tcurr);
dispose (temp );}
end.
Модуль
DINAMO
unit Dinamo;
Interface
uses Crt;
type
pitem = ^ tlist;
tlist = record
inf: pointer;
next: pitem;
end;
taction = procedure (p: pointer);
t_test = function (p: pointer): boolean;
Function New_item (p: pointer): pitem;
Function Make_item (dont: pitem;
p: pointer): pitem;
Procedure Prosm (first: pitem; act: taction);
Function Find (first: pitem; test: t_test;
act: taction): pitem;
Procedure
Deleting (first: pitem; test: t_test);
Function Deleting_f_end (first: pitem;
test: t_test): pitem;
Function
Insert_head (first: pitem; p: pointer): pitem;
Procedure Insert (first: pitem; test: t_test;
p: pointer);
Implementation
Function New_item (p: pointer): pitem;
var tcurr: pitem;
begin
new (tcurr);
tcurr ^. inf: = p;
tcurr ^. next: = nil;
end;
Function
Make_item (dont: pitem; p: pointer): pitem;
var tcurr: pitem;
begin
new (tcurr ^. next);
tcurr: = dont;
tcurr: = tcurr ^. next;
tcurr ^. inf: = p;
tcurr ^. next: = nil;
end;
Procedure Prosm (first: pitem; act: taction);
var tcurr: pitem;
begin
tcurr: = first;
while tcurr <> nil do
begin
act (tcurr ^. inf);
tcurr: = tcurr ^. next;
end;
end;
Function Find (first: pitem; test: t_test;
act: taction): pitem;
var tcurr: pitem;
begin
tcurr: = first;
while tcurr <> nil do
begin
if
test (tcurr ^. inf) = false then
tcurr: = tcurr ^. next
else
begin
if test (tcurr ^. inf) = true then
begin
act (tcurr ^. inf);
tcurr: = tcurr ^. next;
end;
end;
end;
end;
Procedure Deleting (first: pitem;
test: t_test);
var tcurr, temp: pitem;
begin
tcurr: = first;
temp: = first;
while tcurr <> nil do
begin
if
test (tcurr ^. inf) = false then
begin
temp: = tcurr;
tcurr: = tcurr ^. next;
end
else
begin
if tcurr = first then
begin
first: = temp ^. next;
end
else
begin
temp ^. next: = tcurr ^. next;
tcurr: = temp;
end;
end;
end;
end;
Function Deleting_f_end (first: pitem;
test: t_test): pitem;
var tcurr, temp: pitem;
begin
tcurr: = first;
temp: = first;
while tcurr <> nil do
begin
if
test (tcurr ^. inf) = false then
begin
temp: = tcurr;
tcurr: = tcurr ^. next;
end
else
if tcurr ^. next = nil then
begin
temp ^. next: = tcurr ^. next;
tcurr: = temp;
tcurr ^. next: = nil;
end;
end;
end;
Function
Insert_head (first: pitem; p: pointer): pitem;
var tcurr, temp: pitem;
begin
new (temp);
temp ^. inf: = p;
temp ^. next: = first;
first: = temp;
end;
Procedure Insert (first: pitem; test: t_test;
p: pointer);
var tcurr, temp: pitem;
begin
if test (tcurr ^. inf) = true then
begin
new (temp);
temp ^. inf: = p;
temp ^. next: = tcurr ^. next;
tcurr ^. next: = temp;
end;
end;
begin
end.
Програма,
використовує модуль DINAMO
program DODAVANNYA;
uses Dinamo, Crt;
type
pdata = ^ tdata;
tdata = record
a: string [20];
end;
var
r: char;
dont, first, ptemp: pitem;
b: string [20];
tmp: pdata;
Procedure Novoe; far;
begin
new (tmp);
writeln ( 'Vvedite zifru');
read (b);
if first = nil then
begin
with tmp ^ do a: = b;
dont: = new_item (tmp);
first: = new_item (tmp);
end
else
begin
with tmp ^ do a: = b;
dont: = make_item (dont, tmp);
end;
end;
Procedure Print (p: pointer); far;
begin
with pdata (p) ^ do
begin
writeln (a);
writeln ('<>< <> <<><');
end;
repeat
r: = readkey;
until r in [# 32]
end;
Function test (p: pointer): boolean; far;
var t: boolean;
begin
with pdata (p) ^ do t: = a = b;
end;
Procedure ToBeFound; far;
begin
new (tmp);
writeln ( 'What must I to find ?');
read (b);
Find (first, test, Print);
repeat
until keypressed;
end;
Procedure Vstav; far;
begin
new (tmp);
writeln ( 'Posle chego ?');
read (b);
if b = 'h' then
begin
writeln ( 'Chto ?');
readln (b);
with tmp ^ do a: = b;
first: = Insert_head (first, tmp);
end
else
begin
ptemp: = Find (first, test, Print);
if ptemp <> nil then
begin
writeln ( 'Chto ?');
readln (b);
with tmp ^ do a: = b;
Insert (ptemp, test, tmp); (Type mismatch)
end;
if ptemp = nil then
begin
writeln ( 'Chto ?');
readln (b);
with tmp ^ do a: = b;
dont: = new_item (tmp);
end;
end;
end;
begin (programmka)
first: = nil;
repeat
(clrscr;)
writeln ( '(С) оздавать, (П) росмотр, (У) даленіе, По (и) ск, (B) ставка');
repeat
r: = readkey;
until r in [ 'c', 'g', 'b', 'd', 'e', # 27];
case r of
'c': Novoe;
'g': Prosm (first, Print);
'b': ToBeFound;
'd': Vstav;
( 'e': Delet;)
end;
until r = # 27;
dispose (tmp);
end.
