Динамические структуры данных (стр. 2 из 2)
Нетрудно удалить первый элемент (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. Одно из возможных представлений «длинного» текста —это разделить его на участки (строки) равной длины и создать массив ссылок на эти строки:
const d=…; {длина строки}
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;
пред,след:список2 end;
и пусть Е обозначает величину типа ТЭ2.Описать функцию или процедуру, которая:
г) определяет, есть ли в списке 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. http://distance.edu.vn.ua/metodic/pascal/
4. Будникова Н.А. Обучающий комплекс по программированию на языке ПАСКАЛЬ http://petrsu.ru/Chairs/IMO/pascal/