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

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


Сформировать файл из натуральных чисел и после каждого элемента соот-ветствующего списка вставить число 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.

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












Назад

Закрыть