Краткие теоретические сведения. Записи списка обычно упорядочены

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

Чтобы добавить узел в упорядоченный список, нужно найти узел, за которым должен следовать элемент, а указатель нового узла установить на узел, перед которым он вставляется, (рис. 11).

 

… …

 

 

… …

 

Рис. 11

 

Решение:

Program dinsort1;

type

p_stud=^student;

student=record;

name: string[20];

next: p_stud;

end;

var

head: p_stud; {указатель на первый элемент списка}

cur: p_stud; {текущий элемент списка}

p: p_stud; {элемент, после которого вставляем новый узел}

name: string[20]; {фамилия, вводимая с клавиатуры}

node: p_stud; {новый узел списка}

begin

repeat

write (‘фамилия-> ’);

readln (name);

if length (name) < > 0 then begin

{введена строка символов}

new (nod); {создадим новый элемент списка}

node^. name: =name;

node^. Next: =nil;

{ищем место для вставки нового элемнта}

cur: =head;

p: =nil;

{будем сравнивать введенное значение со значением текущего узла}

while (name> cur^. name) and (cur < > nil) do begin

{введенное значение больше текущего}

p: =cur;

cur: =cur^. next; {к следующему узлу}

end;

if p=nil then begin

{узел в начало списка}

node^. next: =head;

head: =node;

end

else begin

node^. next: =p^. next;

p^. next: =node;

end;

end;

until lenfth (name)=0; {фамилия не введена, нажата клавиша < Enter> }

{распечатаем введенный список}

cur: =head;

writeln (‘**Список студентов’);

while cur < > nil do begin

writeln (cur^. name);

cur: =cur^. next;

end;

writeln (‘**’);

readln;

end.

Пример работы программы:

Фамилия-> Иванов

Фамилия-> Яковлев

Фамилия-> Алексеев

Фамилия-> Петров

Фамилия->

**Список студентов**

Алексеев

Иванов

Петров

Яковлев

**

Чтобы удалить узел, надо скорректировать указатель узла, который находится перед удаляемым узлом, (рис. 12).

 

… …

 

 

… …

 

 

рис. 12

 

Узел – это динамическая область, которая теперь не нужна; поэтому после исключения узла из списка надо освободить память, занимаемую этой переменной. Освобождение динамической памяти, или как иногда говорят, уничтожение переменной, выполняется вызовом процедуры free. У процедуры free один параметр – указатель на переменную, память которой должна быть освобождена. Например, в программе

Var

p: ^integer;

begin

new (p);

{инструкции программы}

free (p);

end.

 

Создается динамическая переменная, затем она уничтожается. Освободившуюся память смогут использовать другие переменные. Если этого не сделать, то, возможно, в какой-то момент времени программа не сможет создать очередную динамическую переменную.