ЛР5 - Указатели. Связанные списки
Цель работы – овладение практическими приемами и навыками разработки программ с динамическими переменными, типа указатели.
1. Теоретические сведения
1.1. Указатели
Часто возникает необходимость использовать в программе такие структуры данных, форма и размер которых изменяются в процессе выполнения программы. В таких случаях используются динамические переменные. Явно динамические переменные не объявляются. Вместо этого используется специальная переменная, которая содержит адрес памяти, начиная с которого размещается динамическая переменная. Такая переменная называется переменной-указателем.
В объявлении типа указателя вслед за символом указателя (^ - капа) записывается идентификатор типа динамических переменных, называемый базовым типом. Если базовый тип еще не объявлен, то он должен быть объявлен в той же самой части объявления, в которой объявлен тип указателя. Например,
Рекомендуемые материалы
PersonPointer = ^PersonRecord;
PersonRecord = record
Name: String[50];
Job : String[5];
Next: PersonPointer;
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.
TCheck = record
Amount: Real;
Year: 1990..2000;
Payee: string[39];
Но при написании программы трудно предположить, с каким количеством счетов придется иметь дело. Одно из решений состоит в создании большого массива записей счетов, но это приведет к лишним затратам памяти. Более гибкое решение состоит в расширении определения записи и включении в нее указателя на следующую запись списка, что приведет к образованию связанного списка из элементов типа TCheck
PCheck = ^TCheck;
TCheck = record
Amount: Real;
Year: 1990..2000;
Payee: string[39];
Next: PCheck;
Теперь можно считать каждую запись счета из файла и выделить для нее память. Если запись находится в конце списка, поле Next следует сделать равным nil. В программе требуется отслеживать только два указателя: указатель на первый счет в списке и указатель на текущий счет.
1.3.1. Построение списка
Ниже приведена процедура, которая строит связанный список записей, считывая их из файла. Здесь подразумевается, что открыт файл записей TCheck и именем CheckFile, который содержит, по крайней мере одну запись.
var ListOfChecks, CurrentCheck: PCheck;
procedure ReadChecks;
New(ListOfChecks);
Read(CheckFile, ListOfChecks^);
CurrentCheck := ListOfChecks;
while not Eof(CheckFile) do
New(CurrentCheck^.Next);
Read(CheckFile, CurrentCheck^.Next^);
CurrentCheck := CurrentCheck^.Next;
CurrentCheck^.Next = nil;
1.3.2. Перемещение по списку
Когда список уже есть, можно легко выполнять поиск в нем конкретной записи. Ниже показана функция, которая находит первый счет с конкретной суммой и возвращает указатель на него.
function FindCheckByAmount(AnAmount: Real): PCheck;
var Check: PCheck;
Check := ListOfChecks;
while (Check^.Amount <> AnAmount) and (Check^.Next <> nil) do
Check := Check^.Next;
if Check^.Amount = AnAmount then
FindCheckByAmount := Check
1.3.3. Освобождение выделенной для списка памяти
В процедуре DisposeChecks показано, как можно перебрать список, дойдя до каждого элемента и освободив его.
procedure DisposeChecks;
var Temp: PCheck;
CurrentCheck := ListOfChecks;
while CurrentCheck <> nil do
Temp := CurrentCheck^.Next
Dispose(CurrentCheck);
CurrentCheck:= Temp;
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;
При размещении в динамической памяти объекта размещается в качестве второго параметра обращения к 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];
var npos,i,n,j :integer;
ch1,ch2 :char;
nstr,path,autstr :string;
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);
textattr := attr;
window (x1,y1,x2,y2);
Procedure DrawMenu(npos: integer);
for i:=1 to 4 do
if i=npos then drawwin(menu[i], 255) else drawwin (menu[i],29);
npos :=1;
drawmenu (npos);
ch1 := readkey;
if ch = #0 then ch2 := readkey;
case ch1 of
#0: case ch2 of
#72 : begin
if npos >1 then
drawwin(menu[npos],30);
npos := npos - 1;
drawwin (menu [npos],94);
#80: begin
if npos < 4 then
drаwwin(menu[npos],30);
npos := npos + 1;
drawwin (menu [npos],94);
#13: begin
window (1,1,80,25);
textattr := 7;
textcolor (cyan);
case npos of
writeln (menu[npos]. text);
readln (instr);
textcolor (red);
writeln (menu[npos].text);
textcolor (white);
write (‘Введите путь >> ’);
readln (path);
assign (f1, path);
readln (f1,instr);
textcolor (red);
writeln(‘Execute…’);
textcolor (white);
writeln (‘В строке содержатся цифры: ’);
searchString (instr,outstr);
textcolor (white);
writeln (outstr);
drawmenu (npos);
until (ch1=#27) or ((ch1=#13) and (npos = 4)) or (ch1 = #3)
window (1,1,80,25);
textcolor :=7;
clrscr;
Код программы модуля StSearch.pas следующий:
Unit StSearch;
procedure SearchString (st: string; var sr: string);
implementation
procedure SearchString;
var i, k :integer;
for i:=1 to length(st) do
if st[i] in [‘0’..’9’] then sr := sr + st[i];
Результатом выполнения данной программы с модулем будет меню следующего вида:
- опция ручного ввода строки,
- опция импорта строки из текстового файла,
- опция просмотра содержания числовых символов в строке, - выход из программы в среду ОС.
3. Задачи, для самостоятельного решения
Разработать модуль обработки двунаправленного линейного связного списка, интерфейсная секция которого содержит объявления не менее 5-ти процедур и функций из предложенного списка:
1. Построить список.
2. Уничтожить список.
3. Вывести список на экран.
4. Определить длину списка.
5. Определить номер узла, если задан указатель на него.
6. Определить указатель на узел по его номеру.
7. Добавить узел к "хвосту" списка.
8. Удалить последний узел списка.
9. Добавить узел к "голове" списка.
10. Удалить первый узел списка.
11. Добавить узел после указанного номера.
12. Удалить узел с указанным номером.
13. Определить вхождение в список заданного узла (номер узла или указатель на узел).
14. "Склеить" два списка.
15. Отсортировать список в порядке возрастания (убывания)
значений какого-либо поля записи.
Тип записи и файл записей взять в соответствии с вариантом к данной лабораторной работе.
Задачи 1..4. Создать типизированный файл записей, содержащих сведения о багаже пассажира. Структура записи имеет следующий вид:
type PNT=^B;
Bag = record багаж
Fio: String[20]; Ф.И.О. пассажира
Colch: Integer; количество вещей
Ves: Real; общий вес вещей [кг]
var rec, beg, endd, current: PNT;
Создать однонаправленный список записей.
1. Найти все записи, для которых средний вес одной вещи отличается не более чем на 0,3 кг от общего среднего веса вещи. Результаты записать в новый файл. Исходный и результирующий файлы распечатать.
2. Выяснить, имеется ли пассажир, багаж которого превышает багаж каждого из остальных пассажиров и по числу вещей, и по весу. Исходный файл и результат распечатать.
3. Выяснить, имеются ли два пассажира, багажи которых совпадают по числу вещей и различаются по весу не более чем на 0,5 кг. Исходный файл и результаты распечатать.
4. Дать сведения о багаже, число вещей в котором не меньше, чем в любом другом багаже, а вес вещей не больше, чем в любом другом багаже с этим же числом вещей. Исходный файл и результат распечатать.
Задача 5. Создать типизированный файл записей, содержащих сведения об автомобиле. Структура записи имеет следующий вид:
Type PNT=^A;
Auto = record автомобиль
Fio: String [20]; Ф.И.О. владельца
Marka: String[10]; марка
Number: String[14]; номер автомобиля
var rec, beg, endd, current: PNT;
Создать однонаправленный список записей.
Найти количество автомобилей каждой марки. Исходный файл и результаты распечатать.
Задача 6. Создать типизированный файл записей, содержащих сведения о книгах. Структура записи имеет следующий вид:
type PNT=^B;
Book = record книга
Fio: String[20]; Ф.И.О. автора
Name: String [60]; название
year: Integer год издания
var rec, beg, endd, current: PNT;
Создать однонаправленный список записей.
Найти авторов, издавших более одной книги, начиная с 1980 года. Исходный файл и результаты распечатать.
Задачи 7..8. Создать типизированный файл записей, содержащих сведения об учениках. Структура записи имеет следующий вид:
LerBook = record ученик
Fam: String [20]; фамилия ученика
Year: 1..10; год обучения
Ch: Char; буква (от А до К)
var rec, beg, endd, current: PNT;
Создать однонаправленный список записей.
7. Выяснить, имеются ли однофамильцы в каких-либо параллельных классах. Исходный файл и результаты распечатать.
8. Выяснить, имеются ли однофамильцы в каком-нибудь классе. Исходный файл и результаты распечатать.
Задача 9.Создать типизированный файл записей, содержащих сведения об учениках. Структура записи имеет следующий вид:
type PNT=^S;
LerBook = record ученик
Fam: String [20]; фамилия ученика
Year: 1..10; год обучения
Ch: Char; буква (от А до К)
Ozenka: array[1..5] of integer; отметки, полученные учеником в последней четверти
var rec, beg, endd, current: PNT;
Создать однонаправленный список записей.
Собрать в новом файле сведения о лучших учениках школы, т.е. об учениках, не имеющих отметок ниже четырех и по сумме баллов не уступающих другим ученикам своего и параллельных классов. Исходный и результирующий файлы распечатать.
Задача 10. Создать типизированный файл записей, содержащих сведения об экспортируемых товарах. Структура записи имеет следующий вид:
type PNT=^T;
Tovar = record товар
Name: String[20]; наименование товара
Land: String [10]; страна, импортирующая товар
Ob: Integer; объем поставляемой партии в штуках
var rec, beg, endd, current: PNT;
Создать однонаправленный список записей.
Составить список стран-экспортеров товаров с указанием числа наименований товаров для каждой страны. Исходный файл и результаты распечатать.