Лабораторная работа № 5
Указатели. Связанные списки
Цель работы - овладение практическими приемами и навыками разработки программ с динамическими переменными, типа указатели.
1. Теоретические сведения
1.1. Указатели
Часто возникает необходимость использовать в программе такие структуры данных, форма и размер которых изменяются в процессе выполнения программы. В таких случаях используются динамические переменные. Явно динамические переменные не объявляются. Вместо этого используется специальная переменная, которая содержит адрес памяти, начиная с которого размещается динамическая переменная. Такая переменная называется переменной-указателем.
В объявлении типа указателя вслед за символом указателя (^ - капа) записывается идентификатор типа динамических переменных, называемый базовым типом. Если базовый тип еще не объявлен, то он должен быть объявлен в той же самой части объявления, в которой объявлен тип указателя. Например,
type
PersonPointer = ^PersonRecord;
PersonRecord = record
Name: String[50];
Job : String[5];
Next: PersonPointer;
end;
var
FirstPerson, LastPerson, NewPerson: PersonPointer;
Здесь тип PersonPointer объявляется как указатель на переменные типа PersonRecord. Таким образом, переменные FirstPerson, LastPerson и NewPerson являются переменными указателями, которые могут указывать на записи типа PersonRecord.
Ссылка на динамическую переменную записывается как идентификатор переменной-указателя, за которым следует символ указателя (^). Например, FirstPerson^.
Выделение памяти для динамической переменной и сохранение адреса памяти, начиная с которого размещается динамическая переменная, в переменной-указателе выполняется при помощи стандартной процедуры New. Например, New(NewPerson);
Переменные, создаваемые при помощи стандартной процедуры New, размещаются в области памяти, которая называется “куча”. “Куча” занимает всю или часть свободной памяти, оставшейся после загрузки программы.
Освобождение памяти, ранее занятой динамической переменной, выполняется при помощи стандартной процедуры Dispose.
Например, Dispose(LastPerson);
1.2. Связные списки записей
Связные списки являются эффективным средством хранения данных в случае, когда заранее неизвестно, сколько данных надо хранить в оперативной памяти. Связные списки состоят из одного или более "узлов", размещенных в "куче". По количеству связей различают однонаправленные и двунаправленные списки. По типу связей различают линейные и кольцевые списки. Каждый узел однонаправленного списка содержит указатель на следующий узел этого списка. Указатель в последнем узле содержит nil. На рисунке приведен пример однонаправленного линейного связного списка.
Каждый узел двунаправленного списка содержит указатель на следующий узел этого списка и на предыдущий узел этого списка. Указатель на следующий узел в последнем узле содержит nil. Указатель на предыдущий узел в первом узле содержит nil. На рисунке приведен пример двунаправленного линейного связного списка.
1.3. Управление связанным списком записей (на примере)
Предположим, что необходимо написать программу для ведения личных счетов. Можно хранить все данные о счетах в записях, таких как запись типа Tcheck.
type
TCheck = record
Amount: Real;
Month: 1..12;
Day: 1..31;
Year: 1990..2000;
Payee: string[39];
end.
Но при написании программы трудно предположить, с каким количеством счетов придется иметь дело. Одно из решений состоит в создании большого массива записей счетов, но это приведет к лишним затратам памяти. Более гибкое решение состоит в расширении определения записи и включении в нее указателя на следующую запись списка, что приведет к образованию связанного списка из элементов типа TCheck
type
PCheck = ^TCheck;
TCheck = record
Amount: Real;
Month: 1..12;
Day: 1..31;
Year: 1990..2000;
Payee: string[39];
Next: PCheck; {указывает на следующую запись}
end.
Теперь можно считать каждую запись счета из файла и выделить для нее память. Если запись находится в конце списка, поле Next следует сделать равным nil. В программе требуется отслеживать только два указателя: указатель на первый счет в списке и указатель на текущий счет.
1.3.1. Построение списка
Ниже приведена процедура, которая строит связанный список записей, считывая их из файла. Здесь подразумевается, что открыт файл записей TCheck и именем CheckFile, который содержит, по крайней мере одну запись.
var ListOfChecks, CurrentCheck: PCheck;
procedure ReadChecks;
begin
New(ListOfChecks); {выделить память для первой записи}
Read(CheckFile, ListOfChecks^); {считать первую запись}
CurrentCheck := ListOfChecks; {сделать первую запись текущей}
while not Eof(CheckFile) do
begin
New(CurrentCheck^.Next); {выделить память для следующей записи}
Read(CheckFile, CurrentCheck^.Next^); {считать следующую запись}
CurrentCheck := CurrentCheck^.Next; {сделать следующую запись текущей}
end;
CurrentCheck^.Next = nil; {после последней считанной записи следующей нет}
end.
1.3.2. Перемещение по списку
Когда список уже есть, можно легко выполнять поиск в нем конкретной записи. Ниже показана функция, которая находит первый счет с конкретной суммой и возвращает указатель на него.
function FindCheckByAmount(AnAmount: Real): PCheck;
var Check: PCheck;
begin
Check := ListOfChecks; {указывает на первую запись}
while (Check^.Amount <> AnAmount) and (Check^.Next <> nil) do
Check := Check^.Next;
if Check^.Amount = AnAmount then
FindCheckByAmount := Check {возвращает указатель на найденную запись}
else FindCheckByAmount:= nil; {или nil, если таких записей нет}
end;
1.3.3. Освобождение выделенной для списка памяти
В процедуре DisposeChecks показано, как можно перебрать список, дойдя до каждого элемента и освободив его.
procedure DisposeChecks;
var Temp: PCheck;
begin
CurrentCheck := ListOfChecks; {указывает на первую запись}
while CurrentCheck <> nil do
begin
Temp := CurrentCheck^.Next {сохранить указатель Next}
Dispose(CurrentCheck); {освобождение текущей записи}
CurrentCheck:= Temp; {сделать сохраненную запись текущей}
end;
end;
1.4. Процедуры и функции для работы
с динамической памятью
Функции:
Addr(X) -возвращает результат типа Pointer, в котором содержится адрес аргумента.
Здесь Х - любой объект программы (имя любой переменной, процедуры, функции). Возвращаемый адрес совместим с указателем любого типа. Отметим, что аналогичный результат возвращает операция @.
CSeg - возвращает значение, хранящееся в регистре CS микропроцессора (в начале работы программы в регистре CS содержится сегмент начала кода программы). Результат возвращается в слове типе Word.
Dseg - возвращает значение, хранящееся в регистре DS микропроцессора (в начале работы программы в регистре DS содержится сегмент начала данных программы). Результат возвращается в слове типе Word.
MaxAvail - возвращает размер в байтах наибольшего непрерывного участка кучи. Результат имеет типа LongInt. За один вызов процедуры New или GetMem нельзя зарезервировать память больше, чем значение, возвращаемое этой функцией.
MemAvail - возвращает размер в байтах общего свободного пространства кучи. Результат имеет типа LongInt.
Ofs(x) - возвращает значение типа Word, содержащее смещение адреса указанного объекта. Х - выражение любого типа или имя процедуры.
Ptr(Seg , Ofs) -возвращает значение типа Pointer по заданному сегменту Seg и смещению Ofs. Здесь Seg - выражение типа Word содержащее сегмент, Ofs.- выражение типа Word, содержащее смещение. Значение, возвращаемое функцией, совместимо с указателем любого типа.
Seg(X) - возвращает значение типа Word, содержащее сегмент адреса указанного объекта. Здесь Х - выражение любого типа или имя процедуры.
SizEof(X) - возвращает длину в байтах внутреннего представления указанного объекта. Здесь Х - имя переменной, функции или типа. Например: вместо константы везде SizeOfReal можно было бы использовать обращение SizEof(Real).
Процедуры:
DisPose(TP) - возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за типизированным указателем.
Здесь TP - типизированный указатель. При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения. При освобождении динамических объектов можно указывать вторым параметром обращения к DisPose имя деструктора.
FreeMem(P,Size) - возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за нетипизированным указателем. Здесь Р - нетипизированный указатель. Size - длина в байтах освобождаемого фрагмента.
При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения.
GetMem(P,Size) - резервирует за нетипизированным указателем фрагмент динамической памяти требуемого размера.
За одно обращение к процедуре можно зарезервировать не более 65521 байта динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.
Mark(Ptr) - запоминает текущее значение указателя кучи HeapPtr. Здесь Ptr - указатель любого типа, в котором будет возвращено текущее значение HeapPtr. Используется совместно с процедурой Release(Ptr) для освобождения части кучи.
New(TP) - резервирует фрагмент кучи для размещения переменной. Здесь ТР - типизированный указатель. За одно обращение к процедуре можно зарезервировать не более 655521 байта динамической памяти. Если нет свободно памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.
Процедура New может вызываться как функция. В этом случае параметром обращения к ней является тип переменной, размещаемой в куче, а функция New возвращает значение типа указатель. Например:
Type Pint = ^integer;
Var P: Pint;
…
p:= New(Pint);
При размещении в динамической памяти объекта размещается в качестве второго параметра обращения к New указывать имя конструктора.
Release(Ptr) - освобождает участок кучи. Здесь Ptr - указатель, любого типа, в котором предварительно было сохранено процедурой Mark значение указателя кучи. Освобождается участок кучи от адрес, хранящегося в Ptr, до конца кучи. Одновременно уничтожается список всех свободных фрагментов, которые, возможно, были созданы процедурами DisPose или FreeMem.
2. Демонстрационные примеры
Пример 5.1. Создать программу для поиска цифровых символов в некоторой строке. Написать на языке ТР 7.1 модуль stsearch.tpu, выполняющий поиск цифровых символов. Программа должна обладать одноуровневым меню, иметь опцию импорта строки из текстового файла (файл должен существовать по указанному адресу и не использоваться другими приложениями). Выход из программы возможен по выбору определенного пункта меню, нажатии клавиши Esc, либо комбинации клавиш “Ctrl + C”.
Program StSearch1;
Uses crt, stsearch;
Type win = record
x1,y1,x2,y2: word;
text: string[20];
end;
var npos,i,n,j :integer;
ch1,ch2 :char;
nstr,path,autstr :string;
f1 :text;
const menu: array[1..4] of win =
((x1:5; y2:4; x2:21; y2:4; text: `Ввести строку' )
(x1:5; y2:5; x2:21; y2:5; text: `Импорт из файла' )
(x1:5; y2:6; x2:21; y2:6; text: `Просмотр цифр' )
(x1:5; y2:7; x2:21; y2:7; text: `Выход' ));
Procedure DrawWin(w: win; attr: byte); {изображение пункта меню}
begin
with w do
begin
textattr := attr; {устанавливает атрибуты текста}
window (x1,y1,x2,y2); {создает окно с указанными координатами}
clrscr;
gotoXY(2,1);
write(text);
end;
end;
Procedure DrawMenu(npos: integer); {последовательное изображение пунктов меню}
begin
clrcsr;
for i:=1 to 4 do
if i=npos then drawwin(menu[i], 255{94}) else drawwin (menu[i],29{30});
end;
begin {основная программа}
npos :=1; {исходная позиция выделенного пункта меню}
drawmenu (npos);
repeat
ch1 := readkey;
if ch = #0 then ch2 := readkey;
case ch1 of
#0: case ch2 of
#72 : begin {если нажата клавиша «вверх»}
if npos >1 then {если не верхний пункт меню}
begin
drawwin(menu[npos],30); {перерисовка текущего пункта- снятие выделения}
npos := npos - 1;
drawwin (menu [npos],94); {выделение следующего пункта меню}
end;
end;
#80: begin {если нажата клавиша «вниз»}
if npos < 4 then {если не нижний пункт меню}
begin
drаwwin(menu[npos],30);
npos := npos + 1;
drawwin (menu [npos],94);
end;
end;
end;
#13: begin {если нажата клавиша «Enter»}
window (1,1,80,25);
textattr := 7;
clrscr;
textcolor (cyan);
case npos of
1: begin {выбран первый пункт меню}
writeln (menu[npos]. text);
write (`>>');
readln (instr);
end;
2: begin {выбран второй пункт меню}
textcolor (red);
writeln (menu[npos].text);
textcolor (white);
write (`Введите путь >> ');
readln (path);
assign (f1, path);
reset (f1); {rewrite (f1);}
readln (f1,instr);
end;
3: begin
textcolor (red);
writeln(`Execute…');
sound (660);
delay (1500);
nosound;
textcolor (white);
writeln (`В строке содержатся цифры: ');
searchString (instr,outstr);
textcolor (white);
writeln (outstr);
outstr : = `';
readln;
end;
end;
drawmenu (npos);
end;
end;
until (ch1=#27) or ((ch1=#13) and (npos = 4)) or (ch1 = #3)
{пока не нажаты Esc, Enter или четвертый пункт меню или Сtrl + С}
window (1,1,80,25);
textcolor :=7;
clrscr; {если выход - очистить экран}
End.
Код программы модуля StSearch.pas следующий:
Unit StSearch; {модуль обеспечивает поиск чисел в строке}
Interface
procedure SearchString (st: string; var sr: string);
implementation
procedure SearchString; {интеграл функции}
var i, k :integer;
begin
k := 1; sr: = `';
for i:=1 to length(st) do
begin
if st[i] in [`0'..'9'] then sr := sr + st[i];
end;
end;
end.
Результатом выполнения данной программы с модулем будет меню следующего вида:
- опция ручного ввода строки,
- опция импорта строки из текстового файла,
- опция просмотра содержания числовых символов в строке, - выход из программы в среду ОС.
3. Задачи, для самостоятельного решения
Разработать модуль обработки двунаправленного линейного связного списка, интерфейсная секция которого содержит объявления не менее 5-ти процедур и функций из предложенного списка:
1. Построить список.
2. Уничтожить список.
3. Вывести список на экран.
4. Определить длину списка.
5. Определить номер узла, если задан указатель на него.
6. Определить указатель на узел по его номеру.
7. Добавить узел к "хвосту" списка.
8. Удалить последний узел списка.
9. Добавить узел к "голове" списка.
10. Удалить первый узел списка.
11. Добавить узел после указанного номера.
12. Удалить узел с указанным номером.
13. Определить вхождение в список заданного узла (номер узла или указатель на узел).