Книжка Хабы (970988), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Задача 2. Разработать меню с указателем на нужный режим:

Для указания режима используйте клавиши ,, и ввод. Яркая стрелка первоначально указывает на первый яркий режим. Нажатие клавиши перемещает стрелку на новый режим и делает его ярким, а предыдущий становиться тусклым.

Задача 3. Меню с элементами мультипликации:

Для указания режима используйте клавиши ,, и ввод. Текущим, считается окно полностью показанное. Нажатие указанных клавиш позволяет выбирать нужный режим.

Задача 4. Написать программу двухуровневого меню, которое должно иметь вид:

1. Методы численного решения уравнений,

• метод деления отрезка пополам,

• метод Ньютона,

• метод хорд,

• метод итераций.

1. Методы численного интегрирования,

• метод прямоугольников,

• метод трапеций,

• метод Симпсона.

1. Выход.

Лабораторная работа № 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. На рисунке приведен пример однонаправленного линейного связного списка.

1

2

nil

Каждый узел двунаправленного списка содержит указатель на следующий узел этого списка и на предыдущий узел этого списка. Указатель на следующий узел в последнем узле содержит nil. Указатель на предыдущий узел в первом узле содержит 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);

Характеристики

Список файлов лекций