С построенным списком можно выполнять различные операции: добавлять и удалять элементы в любом месте списка, причем в зависимости от местоположения элемента эти операции имеют свои особенности.
Алгоритм добавления элемента в начало списка:
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. Одно из возможных представлений «длинного» текста --это разделить его на участки (строки) равной длины и создать массив ссылок на эти строки:
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);
Function Kil(var cur1:mas):integer;
var i:integer;
i:=1;
while (cur1[i]<>nil) and (i<>n) do begin
i:=i+1;
kil:=i-1;
procedure chut(var cur1:mas);
var ch:char;i,j:integer;
Assign(f,'c:\f.txt');
for i:=1 to n do
cur1[i]:=nil;
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
write(ch);
Cur1[i]^[j]:=ch;
j:=j+1;
procedure Vuvod(cur2:mas);
var i,j,k3:integer;
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
Var first:mas;q:integer;cha:char;
ClrScr;
Chut(first);
readln;
Vuvod(first);
q:=kil(first);
writeln('Kilkist strok:', q);
end.
Екран результату
Контрольні розрахунки
Контрольними розрахунками містяться в самій програмі. Отримані результати легко перевірити, що підтверджує вірність роботи програми.
Описать процедуру, которая вставляет:
а) в начало списка L новый элемент E;
Алгоритм розв'язку задачі
program Kill_Bill;
uses Crt;
type nodepoint=^node;
node=record
info:integer;
next:nodepoint;
function Vvodsp(n1:integer):nodepoint;
var cur,firs:nodepoint;i:integer;
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;
write('Vvedenya elementu spusku: ');
firs:=cur;
for i:=1 to n1-1 do begin
new(cur^.next);
readln(cur^.next^.info);
cur:=cur^.next;
Vvodsp:=firs;
procedure Vuvodsp(cur1:nodepoint);
Writeln('Vuvedenya spusku');
while cur1<>nil do begin
writeln(cur1^.info);
cur1:=cur1^.next;
procedure Add_first(var cur:nodepoint;elem:integer);
var tm:nodepoint;
new(tm);
tm^.info:=elem;
tm^.next:=cur;
cur:=tm;
Procedure del(var cur2:nodepoint);
var cur:nodepoint;
while cur2<>nil do begin
cur:=cur2^.next;
dispose(cur2);
cur2:=cur;
var n,E:integer;cur,L:nodepoint;
Write('Vedit kilkist elementiv spusku: ');
readln(n);
L:=Vvodsp(n);
Vuvodsp(L);
write('Enter the element which must be added to list: ');
readln(E);
Add_first(L,E);
del(L);
16.33. Пусть L обозначает кольцевой (циклический) двунаправленный список с заглавным звеном (рис. 15) при следующем описании такого списка;
type ТЭ2=...; {тип элементов списка}
список2=^звено2;
звено2=гecord элем:ТЭ2;
пред,след:список2 end;
и пусть Е обозначает величину типа ТЭ2. Описать функцию или процедуру, которая:
г) определяет, есть ли в списке L хотя бы один элемент, который равен следующему за ним (по кругу) элементу;
ж) из списка L, содержащего не менее двух элементов, удаляет все элементы, у которых одинаковые «соседи» (первый и последний элементы считать соседями);
program wqetg;
type Nodepoint=^node;
count:integer;
before:nodepoint;
type nod=^nodepoint;
function Vvodsp(n:integer):nodepoint;
var j:integer;firs,cur1,cur:nodepoint;
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;
readln(cur1^.count);
cur:=firs^.next;
cur1^.next:=cur;
cur^.before:=cur1;
procedure Vuvodsp(head:nodepoint);
cur:=head^.next;
head:=head^.next;
writeln(head^.count);
while head<>cur do begin
function Kilkist(head:nodepoint;var cur:nodepoint):integer;
if head=nil then Kilkist:=0
else if cur^.next=head then Kilkist:=1
else kilkist:=kilkist(head,cur^.next)+1;
procedure DelEl(var cur:nodepoint);
var tm1,tm2:nodepoint;
tm1:=cur^.before;
tm2:=cur^.next;
dispose(cur);
tm1^.next:=tm2;
tm2^.before:=tm1;
procedure Del_Alike_n(var head:nodepoint);
var cur,cur2:nodepoint;b:boolean;
b:=true;
cur2:=head^.next^.next;
while (b) do begin
b:=false;
while not(cur^.next=head^.next) do
if cur^.count=cur2^.count then
DelEl(cur2);
cur2:=cur^.next;
else
cur2:=cur2^.next;
var first,cur:nodepoint;m:integer;
writeln('Vedit kilkist elementiv spusku');
readln(m);
first:=Vvodsp(m);
Vuvodsp(first);
Writeln;
cur:=first;
writeln(kilkist(first^.next,first^.next));
Del_Alike_n(first);
writeln('Spusok bez odnakovux susidiv: ');
{del(first);}
Висновок
Динамічні структури даних дозволяють гнучкіше та ширше використовувати можливості програмування. Дуже зручним у використанні є тип даних Паскаля 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/
Страницы: 1, 2
