Сформируем список целых чисел упорядоченный по неубыванию, т.е. каждый следующий элемент списка должен быть больше или равен предыдущему.
Для решения этой задачи рассмотрим основные части алгоритма, который мы будем воплощать в программе.
После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо во внутрь. Первый и второй случаи мы уже рассмотрели выше. Остановимся на третьем случае.
Для того чтобы вставить в список элемент со значением Digit между двумя элементами, нужно найти эти элементы и запомнить их адреса (первый адрес – в переменной dx, второй – в рх), после чего установить новые связи с переменной, в которой хранится значение Digit.
Графически это можно представить так:
Операторы, выполняющие данную задачу будут следующими:
new(x);
x^.Data := Digit;
px^.Next := x;
x^.Next := dx;
Приведем процедуру InsInto, которая ищет место в списке и вставляет элемент, переданный ей как параметр. В результате сразу получается упорядоченный список. Адрес первого элемента списка хранится в глобальной переменной Head.
Procedure InsInto(Digit : integer; Var Head : Ukazatel );
Var
dx, px, x : Ukazatel ;
Begin
new(x);
x^.Data := Digit;
x^.Next := Nil;
if Head = Nil
then {Если список пуст, то вставляем первый элемент}
Head := x
else
{Если список не пуст, то просматриваем его до тех пор, пока не отыщется подходящее место для x^ или не закончится список}
begin
dx := Head;
px := Head;
while (px<>Nil) and (px^.Data<=Digit) do
begin
dx := px;
px :=px^.Next;
end;
if px=Nil
then {Пройден весь список}
dx^.Next := x {Элемент добавляется в конец списка}
else {Пройден не весь список}
begin
x^.Next := px;
if px=Head
then
Head := x {Вставляем в начало списка}
else
dx^.Next := x; {Вставляем внутрь списка}
end;
end;
End;
Задание. Создайте программу, формирующую упорядоченный список, вставив в нее рассмотренную выше процедуру и процедуру просмотра и вывода на экран элементов списка. Отладьте программу, добавьте комментарий, покажите учителю результат для оценки.
Примеры задач, решаемых с помощью списка
Задание. Просмотрите предложенные решения задач и приготовьтесь объяснить алгоритм их решения учителю. Если необходимо, то наберите программы на компьютере и просмотрите их действие.
Задача 1. Проверить есть ли и сколько раз встречается список М1 в списке М2.
Program BaranovA;
Uses
Crt;
Type
EXS = ^ S;
S = Record
Data : integer;
Next : EXS;
End;
Var
u, x, m1, m2 : EXS;
i, Kol : integer;
Procedure Poisk(Var x1, x2 : EXS);
Var
m3, m4 : EXS;
Begin
Kol := 0;
m3 := m1;
m4 := m2;
while m4 <> Nil do
begin
if m4^.Data = m3^.Data
then
begin
m3 := m3^.Next;
m4 := m4^.Next;
if m3 = Nil
then
begin
Kol := Kol+1;
m3 := m1;
end;
end;
else
begin
m3 := m1;
m4 := m4^.Next;
end;
end;
End;
Procedure Init (Var u : EXS);
Var
y : EXS;
Digit : integer;
Begin
writeln('Введите список. Конец ввода – 0');
u := Nil;
read(Digit);
while Digit <> 0 do
begin
new(y);
y^.Next := Nil;
y^.Data := Digit;
if u = Nil
then
u := y
else
x^.Next := y;
x := y;
read(Digit);
end;
writeln;
End;
Procedure Print(X : EXS);
Begin
while X <> Nil do
begin
write(X^.Data : 5);
X := X^.Next;
end;
readln;
writeln;
End;
Begin
ClrScr;
Init(m1);
Init(m2);
writeln('***Список 1***');
Print(m1);
writeln('***Список 2***');
Print(m2);
Poisk(m1, m2);
writeln('Список 1 встречается в списке 2 ', Kol, ' раз(а)');
readln;
End.
Задача 2. Из текстового файла, состоящего из строк, сформировать список, запросить слово и удалить это слово из списка.
Program ;
Uses
Crt;
Type
EXS = ^ Spisok;
Spisok = record
Data : string;
Next : EXS;
end;
Var
Golova_Spiska, Golova_Spiska_Udalen_ : EXS;
F : text;
S, St : string;
Procedure Smotr(x : EXS);
Begin
TextColor(LightRed);
write('Ваш список...');
while x <> Nil do
begin
writeln (x^.Data,' ');
x := x^.Next;
end;
End;
Procedure reading;
Begin
reset (F);
writeln('Ваш файл...');
while no Eof(F) do
begin
readln (F, St);
writeln (St);
end;
close (F);
End;
Procedure CreateFile;
Begin
writeln('Создание файла');
write('Введите имя файла...');
readln(S);
assign (F, S);
rewrite('Вводите текст в файл (окончание ввода - <Enter>');
