Пример двухсвязанного циклического списка
Определим функции при работе со списком с пояснениями, представленными на рис. 7.1:
0 - просмотр влево (подпрограмма PRL);
1 - просмотр вправо (подпрограмма PRR);
2 - удаление (подпрограмма DEL);
3 - вставка (подпрограмма BCT);
4 - конец работы.
При проходе первого элемента переводится строка.
Рис. 7.1. Операции с узлами двухсвязанного циклического списка
Program SW_Spisok2;
{ Демонстрационный пример использования динамических переменных:
двухсвязанный циклический список }
Uses crt;
Type P=^dat;
dat=Record
INF:char; { любой нужный тип элемента списка }
L,R:P;
end;
Var Point, { указатель на начало кольца }
lef,rig,n:P;
ch:char;
Procedure PRL; { процедура сдвига влево }
Begin
rig:=lef;
lef:=rig^.l; { сдвиг указателей }
Write(lef^.inf); { вывод информационного поля }
If lef=Point then
Writeln; { начало кольца }
end;
Procedure PRR; { процедура сдвига вправо }
Begin
lef:=rig;
rig:=lef^.r;
Write(lef^.inf);
If lef=Point then
Writeln;
end;
Procedure DEL; { процедура удаления }
Begin
If lef^.l=lef^.r then { не менее 2х элементов }
Writeln('Осталось два элемента')
else
If lef=Point then
Writeln('Начало списка')
else
Begin
rig^.l:=lef^.l; { изменение указателей }
lef^.l^.R:=lef^.r;
Dispose(lef); { возвращение памяти }
lef:=Rig^.l;
end;
end;
Procedure BCT; { процедура вставки }
Begin
ch:=ReadKey; Write(ch);
NEW(n);
n^.inf:=ch;
n^.l:=lef; { связи из нового узла }
n^.r:=rig;
rig^.l:=n; { указание на новый узел }
lef^.r:=n;
rig:=n;
writeln;
end;
Begin { непосредственно сама программа }
ch:=ReadKey; Write(ch);
NEW(rig);
rig^.inf:=ch; { первый правый узел }
ch:=ReadKey; Write(ch);
NEW(lef);
lef^.inf:=ch; { первый левый узел }
rig^.l:=lef;
rig^.r:=lef;
lef^.l:=rig;
lef^.r:=rig;
Point:=lef; { начало кольца }
Repeat
Ch:=ReadKey;
Case ch of { анализируем введенную команду }
'0': PRL;
'1': PRR;
'2': DEL;
'3': BCT;
'4': Writeln('Конец')
else
Writeln('Неверный ввод')
end;
Until ch='4'; { пока не встретим команду «конец» }
end.
Указатели без типа
Турбо Паскаль содержит стандартный ссылочный тип, который позволяет не конкретизировать базового типа и считается совместимым со всеми ссылочными типами.
Var <имя_указателя> : pointer;
Работа с ними подразумевает их преобразование в указатели, ссылающиеся на значения конкретного типа, например, при необходимости организовать список, состоящий из записей различных типов.
Для создания и удаления переменных с такими указателями соответственно используются процедуры:
GetMem (<указатель>,<размер>);
FreeMem (<указатель>,<размер>);
Размер участка памяти указывается в байтах, обычно с применением функции SizeOf:
GetMem (Ptr,SizeOf(R));
Для работы с нетипизированными указателями используются дополнительные функции, здесь не рассматриваемые.