Примеры задач

Однонаправленные списки

Сформировать файл из натуральных чисел и из соответствующего списка выбросить все элементы, меньшие 10.

Методика решения

В разделе типов описываем ссылку на звено ss=^zveno, а затем само звено в виде записи, состоящей из информационной inf:byte и ссылочной next:ss частей.

Для реализации данной программы понадобятся следующие переменные:

P– ссылка на текущее звено списка (тип ss);

U – ссылка на заглавное звено списка;

S – вспомогательная ссылка на звено;

F – файловая переменная (file of byte);

C – число типа byte.

Описываем их в разделе переменных.

Теперь формируем файл из натуральных чисел. С помощью процедуры assign связываем файловую переменную с файлом, затем открываем его для записи rewrite(f);

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

While c<>0 do…

После формирования закрываем файл и снова открываем его уже для чтения Reset(f);

Выделяем память под заглавное звено списка new(u) . Ссылочной части заглавного звена присваиваем nil. Текущий указатель в начале должен указывать на заглавное звено P:=U

Далее считываем из файла числа и заносим в список следующим образом:

Выделяем в памяти место под новое звено с адресом P^.next,

Текущий указатель переводим на новое звено P:=P^.next;

Ссылочной части этого звена присваиваем nil.

Таким же образом формируется следующее звено списка. И так пока не закончатся числа в файле.

While not eof(f) do…

Список сформирован. Теперь, по условию задачи из него необходимо исключить элементы, меньшие 10.

Для начала направляем текущий указатель на заглавное звено. Затем просматриваем все звенья списка, перемещая по нему текущий указатель, пока указатель не окажется в конце списка

While P<>nil do…

и удаляем элементы, информационная часть которых меньшие 10, т. е. если P^.next^.inf<10, то удаляем звено P^.next.

Операция удаления звена подразумевает изменение одной ссылки P^.next на P^.next^.next;, т.е. S:=P^.next; P^.next:=P^.next^.next;

Графически это выглядит так:

Теперь звено можно удалить, освобождая занимаемый им участок памяти Dispose(S);

Если же в информационной части звена P^.next^.inf находится число не меньшее 10, то просто переводим текущий указатель на следующее звено.

Для вывода элементов списка на экран текущий указатель связываем с первым звеном списка.

P:=U^.next;

Выводим на экран информационную часть звена, на которое направлен указатель Р. Затем связываемся со следующим звеном, изменив значение Р на значение P^.next. Снова выводим на экран информационную часть звена Р. Повторяем эти действия пока указатель Р не окажется в конце списка.

While P<>nil do…

Результат выведен на экран.

Листинг программы

uses crt;

type

ss=^zveno; {Описание ссылки на звено}

zveno=record {Описание звена}

inf:byte; {информационная часть}

next:ss; {ссылочная часть}

end;

var p,u,s:ss; c:byte; f: file of byte;

begin clrscr;

assign(f,'chisla.dat');

writeln(‘Введите натуральные числа (конец ввода - 0)’);

rewrite(f);

readln(c);

while c<>0 do {Добавляем числа в файл, пока не считается число, равное 0}

begin

write(f,c);

readln(c)

end;

close(f);

reset(f);

new(u); p:=u; u^.next:=nil;

while not eof(f) do {Пока не конец файла, считываем из него числа и добавляем в список}

begin

read(f,c);

new(p^.next); p:=p^.next;

p^.next:=nil; p^.inf:=c;

end;

p:=u;

while p<>nil do {Просматриваем список и удаляем элементы, меньшие 10}

begin

if p^.next^.inf<10 then

begin

s:=p^.next;

p^.next:=p^.next^.next;

dispose(s);

end

else

p:=p^.next;

end;

p:=u^.next;

while p<>nil do {Просматриваем список и выводим его элементы на экран}

begin

write(p^.inf:4);

p:=p^.next;

end;

close(f);

readkey;

end.

Запустить программу

Назад