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

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

Сформировать файл из натуральных чисел и после каждого элемента соот-ветствующего списка вставить число 100.

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

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

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

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

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

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

N – число типа longint.

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

Процедура формирования списка

Считываем из файла числа и заносим в список следующим образом: Выделяем в памяти место под новое звено с адресом P^.sled,

Текущий указатель переводим на новое звено P:=P^. sled; ссылочной части этого звена присваиваем nil.

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

While not eof(f) do…

Процедура вставки звена в список

Процедура имеет два входных параметра: p – ссылка на звено, после которого производится вставка; m – помещаемое число. Создаём новое звено q, в его информационную часть заносим число m.

Далее, ссылочную часть нового звена переносим на звено p^.sled, а ссылку p^.sled на звено q.

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

q^.sled:= p^.sled;

p^.sled:=q;

Процедура вывода списка на экран

Для вывода элементов списка на экран текущий указатель связываем с первым звеном списка. P:=U^. sled;

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

While P<>nil do…

Основная часть программы

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

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

While c<>0 do…

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

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

Далее, с помощью процедуры form, из элементов файла формируем список.

Список сформирован. Далее, по условию задачи, идет вставка в списке числа 100 после каждого соответствующего элемента списка. Указателю p присваиваем ссылку на первое звено (u^.sled). В цикле, пока указатель p не пуст, вызываем процедуру vstavka (P,100) для вставки числа 100 после звена P.

Выводим на экран измененный список с помощью процедуры print.

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

Uses Crt;

Type Tinf=Longint; {описание списка}

ss=^zveno;

zveno=Record

inf:Tinf;

sled:ss;

End;

Var f:File Of Longint; {описание файловой переменной}

u,p:ss;

n:Longint;

{Процедура формирования списка}

Procedure form(c:Tinf);

Begin

New(p^.sled);

p:=p^.sled;

p^.inf:=c;

p^.sled:=nil;

inc(u^.inf)

End;

{Процедура вывода списка на экран}

Procedure print;

Var p:ss;

Begin

p:=u^.sled;

While p<>nil Do

Begin

write(p^.inf,' ');

p:=p^.sled;

End;

End;

{Процедура вставки элемента в список}

Procedure vstavka(p:ss;m:tinf);

Var q:ss;

Begin

new(q);q^.inf:=m;q^.sled:=p^.sled;p^.sled:=q;

End;

Begin ClrScr;

{Связь с файловой переменной, открытие файла для записи}

Assign(f,'Chisla'); ReWrite(f);

Writeln('Введите натуральные числа, конец ввода 0');

Readln(n);

While n<>0 Do Begin {формирование файла}

Write(f,n);

Readln(n);

End;

Close(f);

Writeln('Исходный список:');

{Связь с файловой переменной, открытие файла для чтения}

Assign(f,'Chisla'); Reset(f);

New(u);

u^.sled:=nil;

p:=u;

While Not Eof(f) Do Begin {чтение файла, формирование списка}

Read(f,n);

form(n);

End;

Close(f);

{Вызов процедуры вывода списка на экран}

print;

Writeln;

p:=u^.sled;

While p<>nil Do Begin

vstavka(p,100);

p:=p^.sled^.sled;

End;

Writeln;

print;

Readkey;

End.

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

Назад