Вказiвники та динамiчнi структури даних
Метою роботи є вивчення способiв оголошення та використання вказiвникiв
для роботи з оперативною пам'яттю.
1. Сегментна органiзацiя пам'ятi
Глобальнi змiннi та типованi константи програми розмiщуються в однiй
неперервнiй областi пам'ятi, яка називається сегментом даних. Локальнi змiннi
та параметри пiдпрограм зберiгаються у сегментi стека. Стек - це область
оперативної пам'ятi, в якiй останнє записане значення буде прочитане першим.
Код програми зберiгається у сегментi коду.
Довжина одного сегменту не може перевищувати 64 Кбайти. Сегменти починаються
з фiзичної адреси, кратної 16 байтiв. Область пам'ятi розмiром в 16 байтiв
називається параграфом. Сегмент адресує пам'ять з точнiстю до параграфа.
В загальному випадку програма може мати декiлька сегментiв коду та даних.
Сегменти можуть йти один за одним без промiжкiв, з iнтервалами або перекриватися.
Розмiщення у пам'ятi кожного з сегментiв визначається в процесi завантаження
програми на виконання. При роботi з вибраними сегментами коду, даних та стека їх
адреси зберiгаються вiдповiдно у регiстрах CS, DS та SS. Програма може мати ще
додатковий сегмент даних, який адресується регiстром ES.
Для доступу до даних в межах одного сегменту, крiм значення адреси сегменту,
необхiдно знати змiщення вiд початку сегменту до потрiбної змiнної. Для сегменту
коду таке змiщення визначається значенням регiстру лiчильника команд IP, для
сегменту стека - регiстром SP, для сегменту даних - одним з робочих регiстрiв або
безпосередньо у командi програми.
Таким чином, логiчна адреса елемента даних задається в програмi у виглядi
двох слiв seg:ofs, де seg - сегмент, а ofs - змiщення. У Турбо Паскалi
значення адреси можна запам'ятати у змiннiй-вказiвнику.
2. Оголошення та iнiцiалiзацiя вказiвникiв
Вказiвник - це змiнна, яка приймаї значення адреси областi оперативної
пам'ятi. Вказiвник пов'язується з деяким типом даних, який визначається при
його оголошеннi. Оголошення вказiвника здiйснюється вказанням його базового
типу, перед яким йде символ ^ (каре):
type
iм'я_типу_вказiвника=^базовий_тип;
В якостi базового типу може використовуватись довiльний
тип Турбо-Паскаля, наприклад:
type
tptr_i=^integer; {тип-вказiвник на цiлий тип}
tptr_b=^boolean; {тип-вказiвник на логiчний тип}
tptr_c=^char; {тип-вказiвник на символ}
diap=1..10;
tptr_d=^diap; {тип-вказiвник на дiапазон}
enum=(white,red,green,blue,black);
tptr_p=^enum; {тип-вказiвник на перелiковий тип}
tptr_s=^string; {тип-вказiвник на рядок символiв}
arr=array[1..10] of real;
tptr_arr=^arr; {тип-вказiвник на масив дiйсних чисел}
tmas_ptr=array[1..10] of ^real; {тип - масив вказiвникiв
на дiйснi числа}
tptr_rec=^rec1; {тип-вказiвник на запис}
rec1=record
name:string[20];
time:real
end;
Допускається оголошення базового типу даних пiсля
оголошення вказiвника на цей тип, як це має мiсце для
останнього прикладу.
Для базового типу "запис" можна визначити поле з типом
вказiвника на цей же запис, наприклад:
type
tptr_rec1=record
data:real;
next:^tptr_rec1
end;
Така конструкцiя типу використовується для розмiщення в динамiчнiй
пам'ятi зв'язаного списку елементiв - рiзного роду динамiчних структур даних.
В Турбо-Паскалi можна оголосити вказiвник, не пов'язуючи
його з конкретним базовим типом. Для цього служить ключове
слово pointer:
var
p:pointer;
Такi вказiвники називаються нетипованими i
використовуються для динамiчного розмiщення даних, структура
i тип яких мiняється в ходi роботи програми. Такi вказiвники
сумiснi по присвоєнню iз вказiвниками на iншi типи даних.
Оголошення змiнних типу "вказiвник" здiйснюється в блоцi
var, наприклад:
var
x:tptr_i;
y:^real;
z:tptr_rec;
Змiнна типу "вказiвник" зберiгається в пам'ятi як подвiйне слово
(4 байти). Старше слово визначає сегмент, а молодше -
змiщення в межах даного сегменту.
Iнiцiалiзацiя вказiвника може здiйснюватися за допомогою
операцiї @, функцiї Ptr, константи nil, процедур New та GetMem.
Наприклад:
var a:byte;
p1,p2,p3,p4:^byte;
{..........}
a:=2;
p1:=@a; {p1 приймає значення адреси змiнної a}
new(p2); {p2 приймає значення адреси iз вiльної областi
динамiчної пам'ятi}
p3:=Ptr($40,$49); {p3 приймає значення абсолютної адреси,
що задаються значеннями сегменту та змiщення}
p4:=nil; {p4 не вказує нi на який об'єкт}
Вказiвник визначає адресу першого байта пам'ятi, яка
вiдводиться пiд змiнну базового типу.
3. Розiменування вказiвникiв
Якщо ptr - змiнна типу "вказiвник на базовий тип", то
для доступу до значення, яке знаходиться по визначенiй
адресi, необхiдно виконати операцiю "розiменування вказiвника".
Дана операцiя заключається в тому, що пiсля iдентифiкатора
змiнної-вказiвника записується символ ^ (каре), наприклад:
writeln(p1^); { 2 }
p2^:=4;
Суть операцiї "розiменування" iлюструється наступною
схемою:
|---------------------|
ptr------>| ptr^ |
|---------------------|
Для прикладу розглянемо органiзацiю прямого доступу до вiдеопам'ятi
для текстового режиму роботи вiдеоадаптера за допомогою типованого вказiвника:
Type VideoArray=array[1..25,1..80] of
record
code,attr:byte
end;
Var V:^VideoArray;
Begin
V:=Ptr($B800,$0);
V^[10,20].code:=65;
V^[10,20].attr:=$5A;
End.
При застосуваннi операцiї "розiменування" до
вказiвникiв типу pointer необхiдно здiйснити явне перетворення типу,
наприклад:
Type float=real;
Var p:pointer;
x:real;
Begin
x:=Pi;
p:=@x;
writeln(REAL(p^):5:2) { 3.14}
writeln(FLOAT(p)^:5:2) { 3.14}
End.
Оскiльки в якостi базового типу вказiвника може бути
довiльний тип, то можна сформувати вказiвник на вказiвник, наприклад:
type
p1:^byte;
p2:^p1;
var x:p2; {x визначає адресу адреси даних з базовим типом byte}
Тодi для доступу до значення базового типу byte можна
використати наступну операцiю розiменування: x^^, принцип дiї
якої демонструється наступною схемою:
|---------| |---------|
x----->| x^ |----->| x^^ |
|---------| |---------|
адреса адреса значення
адреси
4. Приклади використання вказiвникiв для роботи iз
структурованими даними
4.1. Робота з одномiрними масивами
Const n=5;
Type arr=array[1..n] of integer;
ptrarr=^arr;
ptrint=^integer;
var a:arr;
p1:ptrarr;
p2:ptrint;
i:integer;
Begin
for i:=1 to n do a[i]:=i;
p1:=@a;
for i:=1 to n do write(p1^[i]:4);
writeln;
p2:=@a;
for i:=1 to n do
write(ptrint(PTR(SEG(p2^),OFS(p2^)+(i-1)*sizeof(integer)))^:4);
{ або write(ptrarr(p2)^[i]:4);}
writeln
End.
4.2. Робота з двомiрними масивами
Const n=3;
m=4;
Type arr1=array[1..m] of integer;
arr2=array[1..n,1..m] of integer;
ptrarr1=^arr1;
ptrarr2=^arr2;
ptrint=^integer;
var a:arr2;
p1:ptrarr1;
p2:ptrarr2;
p:ptrint;
i,j:integer;
Begin
for i:=1 to n do
for j:=1 to m do a[i,j]:=i-j;
p2:=@a;
for i:=1 to n do
begin
for j:=1 to m do
write(p2^[i,j]:4);
writeln
end;
writeln;
p1:=@a;
for i:=1 to n do
begin
for j:=1 to m do
write(p1^[j]:4);
p1:=PTR(seg(p1^),ofs(p1^)+sizeof(arr1));
writeln
end;
writeln;
p:=@a;
for i:=1 to n do
begin
for j:=1 to m do
write(ptrint(PTR(SEG(p^),OFS(p^)+(i-1)*m*sizeof(integer)+
(j-1)*sizeof(integer)))^:4);
{ або write(ptrarr2(p)^[i,j]:4);}
writeln
end;
writeln
End.
4.3. Робота з масивом вказiвникiв
Const n=3;
m=4;
Type arr1=array[1..m] of integer;
masptrarr1=array[1..n] of ^arr1;
ptrmasptrarr1=^masptrarr1;
arr2=array[1..n,1..m] of integer;
var a:arr2;
p1:masptrarr1;
p2:ptrmasptrarr1;
i,j:integer;
Begin
for i:=1 to n do
for j:=1 to m do a[i,j]:=i-j;
for i:=1 to n do p1[i]:=@a[i];
for i:=1 to n do
begin
for j:=1 to m do
write(p1[i]^[j]:4);
writeln
end;
writeln;
p2:=@p1;
for i:=1 to n do
begin
for j:=1 to m do
write(p2^[i]^[j]:4);
writeln
end;
writeln
End.
5. Використання вказiвникiв для розмiщення
великих масивiв даних
Розмiр масиву, розмiщеного у статичнiй пам'ятi, не може перевищувати
65520 байтiв. Iнодi буває необхiдно працювати з масивами,
розмiр яких перевищує 64 Кбайти. Для цього необхiдно використати роботу з
вказiвниками та метод пониження розмiрностi масиву, суть якого зводиться до
наступного:
1) процедурами New або GetMem у динамiчнiй пам'ятi резервується декiлька
фрагментiв, кожен з яких не перевищує 64 Кбайти. При роботi з двомiрними
масивами кожен з таких фрагментiв може визначати один рядок;
2) початок кожного фрагменту запам'ятовується в масивi вказiвникiв;
3) для доступу до елемента масиву необхiдно обчислити змiщення до цього
елемента вiд початку вiдповiдного фрагмента пам'ятi i сформувати
вказiвник на нього.
Приклад роботи з великим масивом з використанням масиву
типованих вказiвникiв:
Const n=100;
m=200;
Type t=array[1..m] of real;
Var ArrPtr:array[1..n] of ^t;
i,j:integer;
Begin
for i:=1 to n do
if MaxAvail>=m*SizeOf(real) then New(ArrPtr[i])
else begin
writeln('Недостатньо динамiчної пам''ятi');
Halt
end;
for i:=1 to n do
for j:=1 to m do
ArrPtr[i]^[j]:=0;
{...}
for i:=1 to n do
Dispose(ArrPtr[i]);
End.
Приклад роботи з великим масивом з використанням масиву
нетипованих вказiвникiв:
Const n=100;
m=200;
Var ArrPtr:array[1..n] of pointer;
i,j:integer;
Begin
for i:=1 to n do
if MaxAvail>=m*SizeOf(real) then GetMem(ArrPtr[i],m*SizeOf(real))
else begin
writeln('Недостатньо динамiчної пам''ятi');
Halt
end;
for i:=1 to n do
for j:=1 to m do
Real(Ptr(Seg(ArrPtr[i]^),Ofs(ArrPtr[i]^)+(j-1)*SizeOf(real))^):=0;
{...}
for i:=1 to n do
FreeMem(ArrPtr[i],m*SizeOf(real));
End.
6. Динамiчна пам'ять
Динамiчна пам'ять - це оперативна пам'ять комп'ютера, яка видiляється
програмi пiд час її виконання, крiм сегментiв даних, стеку та коду програми.
По змовчуванню програмi видiляється вся доступна динамiчна пам'ять. Якщо програма
забирає всю динамiчну пам'ять, то вона не зможе запустити на виконання
iншу програму. Якщо така програма завершується резидентно, то пiсля неї
не можна завантажити будь-яку iншу програму. Розмiр динамiчної пам'ятi, доступної
для програми, регулюється директивою компiлятора
{$M StackSize,MinHeap,MaxHeap},
де StackSize - розмiр сегменту стеку;
MinHeap - мiнiмальний розмiр динамiчної пам'ятi, без наявностi якої
програма не буде працювати. Якщо MinHeap=0, то програма
буде запущена завжди;
MaxHeap - максимальний розмiр динамiчної пам'ятi, яка буде видiлена
програмi. Якщо значення MaxHeap перевищує об'єм вiльної
динамiчної пам'ятi, то програмi видiляється вся доступна пам'ять.
По змовчуванню директива визначає наступнi розмiри пам'ятi:
{$M 16384,0,655560}. Значення MaxHeap=655560 визначає максимальний розмiр всiєї
динамiчної пам'ятi.
Схема розподiлу пам'ятi для програми на мовi Турбо Паскаль приведена на
рис . Динамiчна пам'ять розмiщується в старших адресах зразу за оверлейним
буфером програми. Якщо оверлейний буфер вiдсутнiй, то динамiчна пам'ять
розмiщується зразу за стеком програми.
В модулi System визначенi змiннi-вказiвники HeapOrg, HeapPtr, FreePtr, якi
визначають вiдповiдно початок, бiжучу межу вiльної та кiнець динамiчної пам'ятi,
видiленої для програми. Динамiчна пам'ять має стекову структуру, яка росте вгору
вiд її нижньої межi. При послiдовному резервуваннi динамiчної пам'ятi елементи
даних розмiщуються пiдряд без пропускiв. Якщо елементи даних звiльняються з пам'ятi
у довiльному порядку (а не точно у зворотньому порядку), то динамiчна пам'ять
буде фрагментованою. Фрагментована пам'ять складається з послiдовностi вiльних та
зайнятих блокiв.
Динамiчна пам'ять видiляється програмi окремими блоками. Адреси
вiльних блокiв та їх розмiри зберiгаються у списку вiльних блокiв, який росте
вниз вiд верхньої межi динамiчної пам'ятi. При кожному новому розподiлi
динамiчної пам'ятi у списку вiльних блокiв шукається блок потрiбного розмiру
(бiльший або рiвний потрiбному розмiру) i цей блок видiляється програмi.
6.1. Видiлення та звiльнення динамiчної пам'ятi
Для видiлення динамiчної пам'ятi по типованому вказiвнику використовується
процедура New(p), де p - типований вказiвник, наприклад:
var p:^integer;
begin
New(p);
p^:=10;
{...}
end.
Кiлькiсть байтiв, якi видiляє процедура New, визначається розмiром базового
типу вказiвника. За одне звертання до процедури New можна зарезервувати
не бiльше 64 К - $F байтiв динамiчної пам'ятi.
Для приведеного прикладу буде видiлено sizeof(integer)=2 байти
динамiчної пам'ятi. Вказiвник p прийме значення адреси видiленої областi пам'ятi.
За допомогою операцiї розiменування вказiвника p^ у видiлену область можна записати
(або прочитати) значення.
Крiм процедури New у Турбо Паскалi визначена функцiя New, призначена для видiлення
динамiчної пам'ятi. Аргументом цiєї функцiї є iм'я типу вказiвника. Функцiя повертає
значення вказiвника на видiлену область пам'ятi:
Type ptr=^integer;
Var p:ptr;
begin
p:=New(ptr);
p^:=10;
{...}
end.
Якщо об'єм вiльної динамiчної пам'ятi буде меншим вiд того, який вимагається
процедурою або функцiєю New, то значення вказiвника p буде невизначеним, але
повiдомлення про помилку не буде. Тому рекомендується
перед застосуванням процедури або функцiї New перевiряти об'єм нефрагментованої
вiльної динамiчної пам'ятi за допомогою функцiї MaxAvail, наприклад:
var p:^integer;
begin
if MaxAvail<sizeof(integer) then
begin
writeln('Недостатньо динамiчної пам'ятi');
Halt
end;
New(p)
{...}
end.
Пiсля завершення роботи з пам'яттю, видiленою процедурою або функцiєю New,
її необхiдно звiльнити за допомогою процедури Dispose(p), де p - вказiвник
на видiлену пам'ять. Пiсля звертання до процедури Dispose коректується список вiльних
блокiв i звiльнена пам'ять може бути використана для наступного розподiлу.
Процедура Dispose не змiнює значення вказiвника p. Повторне використання
цiєї процедури до цього ж вказiвника приводить до помилки часу виконання.
Для остаточного звiльнення вказiвника необхiдно йому присвоїти значення
nil.
Iнша можливiсть звiльнення пам'ятi здiйснюється процедурами Mark(p) та
Release(p), де p - вказiвник на область динамiчної пам'ятi.
Процедура Mark(p) запам'ятовує у вказiвнику p значення вказiвника HeapPtr -
нижньої межi вiльної динамiчної пам'ятi. Процедура Release(p) звiльняє динамiчну пам'ять вiд
вiд вказiвника p, визначеного процедурою Mark, до кiнця динамiчної пам'ятi.
Виклик Release знищує список вiльних блокiв, створених до цього процедурами
Dispose або FreeMem. Тому сумiсне використання обох механiзмiв звiльнення
пам'ятi в однiй програмi не рекомендується.
При нерезидентному завершеннi роботи програми закрiплена за нею динамiчна пам'ять
звiльняється для iнших програм.
Для видiлення пам'ятi по нетипованому вказiвнику використовується процедура
GetMem(p,size). Аргумент p визначає вказiвник на видiлену
область оперативної пам'ятi, а size - розмiр цiєї областi в байтах. За одне
звертання до процедури GetMem можна зарезервувати не бiльше 64 К -$F байтiв динамiчної
пам'ятi. Наприклад:
Var p:pointer;
begin
if MaxAvail>=20 then
GetMem(p,20) { Видiлено 20 байтiв динамiчної пам'ятi }
else Halt;
{...}
End.
Звiльнення динамiчної пам'ятi по непованому вказiвнику забезпечує процедура
FreeMem(p,size), яка має такi ж аргументи, як i процедура GetMem. Кiлькiсть
байтiв, якi звiльняються по вказiвнику p мають точно дорiвнювати кiлькостi
байтiв, видiлених по цьому вказiвнику:
FreeMem(p,20); { Звiльнено 20 байтiв динамiчної пам'ятi }
Процедура FreeMem не змiнює значення
вказiвника p. Повторне застосування цiєї процедури до цього ж вказiвника
приводить до помилки часу виконання.
6.2. Динамiчнi структури даних
Статичнi данi - це данi, пiд якi видiляється оперативна пам'ять
в процесi трансляцiї програми. Вiдповiднiсть мiж статичними даними i
видiленою для них пам'яттю зберiгається на протязi всього часу виконання
програми.
Динамiчнi данi - це данi, пiд якi видiляється пам'ять пiд час виконання
програми. Адреси пам'ятi, по яких зберiгатимуться динамiчнi данi наперед
не вiдомi i можуть мiнятися в процесi виконання програми. Динамiчнi данi
визначаються через тип-вказiвник.
Для зручностi доступу та обробки динамiчнi данi можуть об'єднуватись
у взаємозв'язанi структури. До таких структур належать списки, черги, стеки,
дерева та iн.
Елемент динамiчної структури даних є записом, одне або декiлька полiв
якого мiстить значення адреси iншого елемента.
1. Лiнiйнi списки. Лiнiйний список - це однонаправлена структура даних,
кожен елемент якої мiстить адресу свого сусiднього елемента. Останнiй елемент списку,
в адресному полi мiстить значення пустого вказiвника nil.
Для доступу до елементiв списку потрiбно знати лише адресу першого з них.
Елементи однонаправленого лiнiйного списку можуть мати ряд iнформацiйних полiв та одне
адресне поле. Наприклад, вони можуть визначаються за допомогою наступного типу:
type t=^s;
s=record
info:real;
next:t
end;
Поле info мiстить значення елемента списку, а поле next - адресу його сусiднього
елемента.
Пiсля оголошення типу можна визначити вказiвники на елементи списку,
якi будуть потрiбнi для створення та роботи зi списком:
var p,q,r,s:t;
Над списком визначенi наступнi операцiї:
- створення списку;
- читання списку;
- постановка елемента у список;
- витирання елемента iз списку.
7. Процедури i функцiї для роботи з динамiчною пам'яттю
1. Function Addr(var x):pointer;
Повертає адресу аргумента x. В якостi аргумента може бути будь-який об'єкт
програми - iм'я змiнної, процедури, функцiї. Аналогiчний результат дає
операцiя @.
2. Function Ptr(seg,ofs:word):pointer;
По заданих значеннях сегмента та змiщення будує вказiвник типу
pointer.
3. Function Seg(var x):word;
Повертає сегментну частину адреси аргумента x.
В якостi x може бути змiнна будь-якого типу, або iм'я процедури
чи функцiї.
4. Function Ofs(var x):word;
Повертає значення змiщення адреси аргумента x.
В якостi x може бути змiнна будь-якого типу, або iм'я процедури
чи функцiї.
5. Function CSeg:word;
Повертає бiжуче значення регiстру CS. У регiстрi CS зберiгається сегментна частина
адреси коду програми, у якiй була викликана функцiя CSeg.
6. Function DSeg:word;
Повертає бiжуче значення регiстру DS. У регiстрi DS зберiгається сегментна частина
адреси сегменту даних.
7. Function SSeg:word;
Повертає бiжуче значення регiстру SS. У регiстрi SS зберiгається
сегментна частина адреси сегмента стека.
8. Function SPtr:word;
Повертає бiжуче значення регiстра SP. Регiстр SP мiстить змiщення сегмента
стека.
9. Procedure New(var p:pointer);
Резервує фрагмент динамiчної пам'ятi для розмiщення даних. Аргумент p
повинен бути вказiвником будь-якого типу. В результатi роботи процедури
New вказiвник p приймає значення адреси початку видiленої областi пам'ятi.
Розмiр пам'ятi визначається розмiром типу,
на який вказує p. За одне звертання можна зарезервувати не бiльше 64 К -$F
байтiв.
Якщо потрiбної пам'ятi не має, то виникає помилка часу виконання.
10. Function New(typepointer):pointer;
Резервує фрагмент динамiчної пам'ятi для розмiщення даних. Аргумент
typepointer визначає iм'я типу "вказiвник". В результатi роботи функцiя
New повертає значення адреси початку видiленої областi пам'ятi.
Розмiр пам'ятi визначається розмiром базового типу typepointer.
За одне звертання можна зарезервувати не бiльше 64 К -$F байтiв.
Якщо потрiбної пам'ятi не має, то виникає помилка часу виконання.
11. Procedure Dispose(var p:pointer);
Звiльняє область динамiчної пам'ятi, яка визначається вказiвником p.
Пiсля роботи процедури Dispose значення вказiвника p стає невизначеним i його
розiменування приводить до помилки.
12. Procedure GetMem(var p:pointer; size:word);
Резервує за вказiвником p фрагмент динамiчної пам'ятi
потрiбного розмiру size. Вказiвник p може бути будь-якого типу. Розмiр size
задається в байтах. За одне звертання можна зарезервувати до 64 Кбайт.
Якщо вiльної пам'ятi немає, то виникає помилка часу виконання.
13. Procedure FreeMem(var p:pointer; size:word);
Звiльняє size байтiв областi динамiчної пам'ятi, яку визначає вказiвник
p. Розмiр size повинен бути точно рiвним розмiру пам'ятi, закрiпленої за
вказiвником p за допомогою процедури GetMem. Пiсля роботи процедури FreeMem
значення вказiвника p стає невизначеним i його розiменування приводить до
помилки.
14. Procedure Mark(var p:pointer);
Запам'ятовує бiжуче значення вказiвника HeapPtr - нижньої межi вiльної
динамiчної пам'ятi. Використовується разом з процедурою Release.
15. Procedure Release(var p:pointer);
Звiльняє фрагмент динамiчної пам'ятi вiд значення вказiвника p до її
верхньої межi. Значення вказiвника p попередньо повинно бути визначене
за допомогою процедури Mark. Процедура Release звiльняє всi динамiчнi змiннi,
якi були розмiщенi процедурами New та Dispose пiсля виклику процедури Mark.
Звертання до процедур Mark та Release не можна чергувати iз звертанням до
процедур Dispose та FreeMem.
16. Function MaxAvail:longint;
Повертає в байтах розмiр найбiльшого неперервного фрагменту динамiчної
пам'ятi.
17. Function MemAvail:longint;
Повертає в байтах розмiр загального вiльного простору динамiчної пам'ятi.
Цей простiр може бути фрагментований за рахунок видiлення та звiльнення
блокiв пам'ятi.
8. Завдання для роботи
1. Напишiть програму пошуку максимального елементу одномiрного
масиву N цiлих чисел, пам'ять пiд який видiляЇться динамiчно пiд
час роботи програми.
2. Напишiть програму, яка формуЇ однонаправлений лiнiйний список
цiлих чисел, що вводяться iз клавiатури i виконуЇ над ним опе-
рацi¦: зчитування та вивiд iнформацi¦ iз списку; постановки еле-
мента у список пiсля заданого наперед елемента; виключення еле-
мента iз списку по заданому значенню. Операцi¦ над списком
оформiть у виглядi пiдпрограм-процедур.
3. Сформувати однонаправлений лiнiйний список iз дiйсних чисел,
що вводяться iз клавiатури. Знайти максимальний елемент списку i
роздрукувати його.
4. Сформувати однонаправлений лiнiйний список iз цiлих чисел, що
вводяться iз клавiатури. Вiдсортувати цей список по зростанню
значень елементiв.
5. Cформувати лiнiйний список iз десяти чисел, отриманих за до-
помогою генератора випадкових величин, рiвномiрно розподiлених
в iнтервалi [0,1]. Написати пiдпрограму-функцiю знаходження
максимального елемента списку.
6. Заданий список iз n дiйсних чисел. Написати пiдпрогра-
му-функцiю, яка повертаЇ значення true в тому випадку, якщо
числа у списку розмiщенi в порядку зростання.
7. Написати процедуру, яка iз списку дiйсних чисел S формуЇ
список додатнiх елементiв S1 та список вiд'Їмних елементiв S2.
8. Написати логiчну функцiю, яка перевiряЇ, чи елементи списку
дiйсних чисел впорядкованi по зростанню.
9. Написати процедуру, яка об'ЇднуЇ два впорядкованих по
зростанню списки дiйсних чисел S1 та S2 в один впорядкований по
зростанню список.
10. Написати процедуру, яка формуЇ список S, включаючи в нього по
одному разу елементи, якi:
а) входять хоча б в один iз спискiв S1 або S2;
б) входять одночасно в обидва списки S1 та S2;
в) входять в список S1, але не входять до списку S2;
11. Сформуйте однонаправлений кiльцевий список елементiв типу
char та оформiть у виглядi процедур наступнi операцi¦ над ним:
а) виключити iз списку повторнi входження одного й того ж
елемента;
б) подво¦ти кожен елемент списку.
12. Написати процедуру, яка в однонаправленому лiнiйному списку S
цiлих чисел виконуЇ наступнi дi¦:
а) замiняЇ перше входження списку S1 на список S2;
б) витираЇ всi входження списку S1;
в) робить копiю списку S.
13. Використовуючи операцi¦ над списком об'Їднати подiбнi члени
многочленна
-8х^4 -74х + 8х^4 + 5 - х^3
i роздрукувати його по спаданню степенiв x.
15. Заданий невпорядковани двохнаправлений лiнiйний список нату-
ральних чисел. Роздрукувати у зворотньому порядку всi числа, що
знаходяться мiж мiнiмальним та максимальним елементами.
16. Заданий лiнiйний список рядкiв символiв. Надрукувати всi сло-
ва максимально¦ довжини.
17. Заданий кiльцевий двохнаправлений список елементiв типу char.
Написати функцiю або процедуру, яка:
а) пiдраховуЇ кiлькiсть елементiв списку, у яких однаковi
сусiднi елементи;
б) витираЇ всi елементи, у яких однаковi сусiднi елементи;
18. Сформувати файл записiв (прiзвище, група, середнiй бал) зi
структурою зв'язного списку i оформити у виглядi процедур
основнi операцi¦ роботи з файлом:
а) пошук елементiв;
б) включення елементiв;
в) витирання елементiв.
19. Многочлен
p(x)=a x^n + a x^(n-1) + ... + a x + a
n n-1 1 0
може бути представлений у виглядi однонаправленого лiнiйного
списку. Написати наступнi процедури або функцi¦ для роботи з та-
ким списком:
а) обчислити значення многочлена p у точцi x;
б) iз многочлена p сформувати многочлен q, який Ї його похiдною;
в) побудувати многочлен p, який Ї сумою многочленiв q та r.
20. Черга - це однонаправлений лiнiйний спiсок, який поповнюЇться
з кiнця, а зменшуЇться з початку. Написати процедури:
а) постановки елемента в чергу;
б) виключення елемента з черги;
в) перевiрки, чи черга пуста.
21. Стек - це однонаправлений лiнiйний список, в якому елементи
записуються i зчитуються з кiнця списку. Написати процедури або
функцi¦ , що виконують операцi¦:
а) включення елемента в стек;
б) виключення елемента iз стеку;
в) очистки стеку;
г) перевiрки, чи стек пустий.
22. Написати програму кодування цiлих чисел, що вводяться з
клавiатури, за допомогою бiнарного дерева пошуку кодiв. Дерево
будуЇться з вершин та ребер, що визначаються наступним типом:
type rebro= versh;
versh=record
liv, prav: rebro;
num, kod: inteqer
end;
Якщо для введеного числа num iснуЇ вершина дерева, то вiдповiдне
значення коду kod зчитуЇться з вершини i роздруковуЇться. В iншо-
му випадку будуЇться нова вершина визначеного типу, в яку за-
писуЇться значення num та kod. Значення коду в цьому випадку зчи-
туЇться iз файлу цiлих чисел, як запис, що маЇ номер num.
23. Довiльний вираз f1 s f2 мови Pascal можна представити у
вiглядi бiнарного дерева наступним чином: знак операцi¦ s
представляЇться вершиною верхнього рiвня (корiнь дерева), а f1 та
f2 - операнди (вирази), що представляються вiдповiдно лiвим та
правим пiддеревом. Написати пiдпрограму функцiю або процедуру,
яка:
а) обчислюЇ значення виразу;
б) будуЇ дерево-формулу, що Ї похiдною заданого дерева-формули.
24. Виконати сортування одномiрного масиву цiлих чисел за допомо-
гою бiнарного дерева пошуку.
25. Заданий список iз n натуральних чисел. Виключити iз списку
максимальний елемент.
