Файл: Lektsii.doc

Заметим, что работа с нетипизированными указателями сложнее, т.к. всю ответственность за размещение структуры и её "наполнение" значением несёт только сам программист. В то же время этот вид указателей обладает большей гибкостью и способен размещать в одном и том же фрагменте памяти различные типы структур, создавая предпосылки для более эффективного использования памяти. Начинающим программистам не рекомендуется, тем не менее, работать с нетипизированными указателями.

Оператор присваивания, процедуры выделения хип-памяти и разыменование переменной-указателя составляют основной арсенал средств работы с указателями. Кроме того, для указателей (как для адресов) допустимы обычные отношения сравнения: =, <>, <, >, <=, >=. Проиллюстрируем эти средства на примере - программе работы с линейным списком - списком телефонов:

program list_tel;{создание списка телефонов}

uses CRT;

type refer=^info; {тип - Указатель на запись}

info= record name,adr,tel:string;

next:refer

end;

var first,p,pp:refer; {указатели на начало списка и текущие}

s:string;

procedure write_list(start:refer);{вывод всех элементов списка}

begin repeat with start^ do

begin writeln(name);

writeln(adr);

writeln(tel);

end; start:=start^.next

until start=nil;

end{write_list};

BEGIN TextBackground(cyan);TextColor(white);ClrScr;

window(10,5,40,20);TextBackground(green); ClrScr;

new(first);p:=first;pp:=nil;

repeat if pp<>nil then {образование очередного элемента}

begin new(p);pp^.next:=p end;

with p^ do { заполнение элемента списка}

begin write('Ф.И.О.:'); readln(name);

write('Адрес:'); readln(adr);

write('Телефон:');readln(tel);

next:=nil

end; pp:=p;readln(s)

until (s=' ');

writeln('Список телефонов создан');

write_list(first);writeln('Вывод списка завершен');

END{list_tel}.

В этой программе элементы списка телефонов создаются циклически до тех пор, пока после заполнения полей очередного элемента списка будет введён символ-пробел. Последний элемент списка имеет нулевой указатель на следующий элемент. После создания списка процедура write_list распечатывает содержимое списка.

Для возврата освободившегося участка хип-памяти используется процедура dispose (p), где p – типизированный указатель, и процедура freemem(p,k), где к – размер в байтах освобождаемого участка для нетипизированного указателя p.

В Турбо Паскале имеется ещё ряд стандартных процедур и функций, работающих с указателями. Приведем некоторые из них.

Процедура mark(ptr) - запоминает в ptr текущее значение указателя HeapPtr.

Процедура release(ptr) - освобождение участка хип-памяти от текущего указателя, сохраненного процедурой mark(ptr), до конца хип-памяти.

Функции maxavail и memavail - возвращают размер (в байтах) наибольшего непрерывного участка или общего свободного пространства хип-памяти соответственно.

Функция addr(x) - возвращает указатель, содержащий адрес аргумента x (имя переменной, процедуры, функции). Эту же функцию выполняет операция @x.

Лекции 24-25: Использование указателей для представления динамически структур данных.

1. Тип Pchar и "строки, заканчивающиеся нулем".

2. Линейные списки и очереди.

3. Кольцевые списки.

4. Использование указателей для обработки деревьев.

1. Тип Pchar и "строки, заканчивающиеся нулём".

Описанные ранее строки (называемые строками ASCII), как указывалось, могут иметь максимальную длину только 255 символов. В то же время API-функции Windows, а также язык С используют другой тип строк - "строки, заканчивающиеся нулём" (называемые ASCIIZ-строками). Это - строки, которые ꗬÁIЙ74ለ¿7474က7474Ѐ74ሢ

橢橢뎲뎲757575757575757575Й鈰 ጕ7575ﾤ75757575757575Ɠ757575ﾤ75757575ﾤ75757575ﾤ7575757575757575]7575۸757575۸75۸757575۸757575ૌ757575ૌ757575ૌ75ﾵ7575757575ૠ757575ૠ757575ૠ757575ૠ75875ଘ75ʹ75ຌ75Ό75ૠ757575ꀴ75ì75ᓤ75Ŭ75ᙐ7575ᙦ757575ᙦ757575ᙦ757575嚑75ଈ75憙75̴75操75Ɯ75锜7575锞757575锞757575锞75575镓75Ô75阧75Ô75電757575ꄠ75Ǵ75ꌔ75f75電75ह757575757575757575ૌ757575晩7575757575757575757575嘕75|75嚑757575晩757575晩757575電7575изован в версии Borland Pascal 7.0 специальным модулем Strings, в котором содержатся функции обработки таких строк и преобразований между строками ASCII и строками ASCIIZ.

Тип PChar является указателем на область памяти, где размещена строка, заканчивающаяся символом #0. Сама строка представляет собой массив вида:

array [0..K] of Char; где: K - количество символов строки.

В отличие от строки string в "строке, заканчивающейся нулем" первый символ имеет индекс 0, а последний - K-1. Символ-терминатор #0 размещен в позиции K и недоступен для прикладной программы.

Функции над ASCIIZ-строками (все они имеют префикс Str) можно разделить на три группы: аналоги функций для ASCII-строк, оригинальные функции (не имеющие аналога среди функций ASCII-строк) и функции преобразования.

Функции - аналоги: StrCopy, StrPos, StrLen, StrCat.

Оригинальные функции для ASCIIZ-строк включают функции сравнения строк (с учётом или без учёта регистра символа), инициализации строки, стирания строки, определения вхождения символа в строку (первого или последнего вхождения), специальные функции копирования и некоторые другие. Работа с этими функциями требует некоторых знаний механизма указателей.

Функции преобразования: преобразование из ASCIIZ к ASCII (StrPas), из ASCII к ASCIIZ (StrPCopy).

Чтение и запись ASCIIZ-строк поддерживается обычными стандартными процедурами: read, readln, write, writeln.

2. Линейные списки и очереди.

Одной из самых распространенных динамических структур данных, легко организуемых с помощью указателей, являются линейные списки.

Линейный список - линейная последовательность произвольного числа компонент (элементов списка), каждый из которых непосредственно связан со следующим или/и предшествующим элементом. Список однонаправленный, если в нём имеется только связь с предшествующим или только со следующим элементом. Список двунаправленный, если в нем имеется связь, как с предшествующим, так и со следующим элементом.

Построение списков с помощью указателей позволяет размещать элементы списка в динамической памяти независимо друг от друга (т.е. необязательно сплошным массивом адресов), что придает спискам бóльшую гибкость по сравнению с обычными массивами. Над такими списками легко выполнять операции включения элемента в любое место списка или удаления произвольного элемента из списка (без перемещения остальных элементов в памяти), однако, доступ к любому элементу только последовательный (через голову списка). Переменная-указатель выполняет в списке роль связи между соседними элементами.

Линейные списки часто используются для представления и обслуживания очередей. Характерным для очередей является её естественный порядок: каждый новый элемент помещается в "хвост" очереди. Различают две дисциплины обслуживания очередей:

FIFO (first input first output) - первым пришёл, первым обслуживается.

LIFO (last input first output) - последним пришёл, первым обслуживается.

Дисциплина FIFO соответствует классической очереди, однако, в ряде случаев используются очереди с дисциплиной LIFO (такие очереди распространены в приложениях информатики, например при анализе иерархически вложенных языковых конструкций, а также в некоторых технических системах - обоймы патронов в автоматическом оружии).

Очередь с дисциплиной обслуживания LIFO называется стеком, а с классической дисциплиной FIFO - магазином.

Пример программы создания очереди - FIFO был приведен выше (список телефонов). Аналогичная программа для стека телефонов (имеющая смысл для определения, кто звонил последним) приведена ниже.

program stack_tel;{создание стека телефонов}

uses CRT;

type ref=^inf; {тип - Указатель на запись }

inf= record name,adr,tel:string;

pred:ref

end;

var head,p:ref; {указатель на начало стека и текущий}

s:string;

procedure write_stack(start:ref);

{вывод всех элементов стека}

begin repeat with start^ do

begin writeln(name); writeln(adr); writeln(tel);

end; start:=start^.pred

until start=nil

end{write_stack};

BEGIN TextBackground(cyan);TextColor(white);ClrScr;

window(10,5,40,20);TextBackground(green); ClrScr;head:=nil;

repeat new(p); with p^ do {заполнение полей записи}

begin write('Ф.И.О.:'); readln(name); write('Адрес:'); readln(adr);

write('Телефон:');readln(tel);pred:=head;

end; head:=p;readln(s)

until (s=' '); writeln('Стек телефонов создан');

write_list(head); writeln('Конец вывода стека');

END{list_tel}.

Особенностью стека является то, что в вершине его находится элемент, поступивший последним, а связь посредством указателя осуществляется с предшествующим элементом. Входом в стек является его вершина. Характерными операциями для стека, помимо включения элемента в стек (продемонстрированной в этой программе), являются также выталкивание элемента из вершины стека (после его обслуживания), определение числа элементов в стеке (глубины стека).