Занесение элемента в очередь

Занесение элемента в очередь соответствует занесению элемента в конец списка. Рассмотрите процедуру, описанную ниже.

Procedure writeO(Var BeginO, EndO: EXO; c: integer);

Var

u: EXO;

Begin

new(u);

u^.Data:= c;

u^Next:= Nil;

if BeginO =Nil {проверяем пуста ли очередь}

then

BeginO:= u {ставим указатель начала очереди на первый созданный элемент}

else

EndO^.Next:= u; {ставим созданный элемент в конец очереди}

EndO:= u; {переносим указатель конца очереди на последний элемент}

End;

Задание. Создайте программу формирования очереди с использованием предложенной процедуры.

Извлечение элемента из очереди

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

Procedure readO(Var BeginO, EndO: EXO; Var c: integer);

Var

u: EXO;

Function FreeO(x1: EXO): boolean;

Begin

FreeO:= (x1=Nil);

End;

Begin

if FreeO(BeginO)

then

writeln('Очередь пуста');

else

begin

c:= BeginO^.Data; {считываем искомое значение в переменную с}

u:= BeginO; {ставим промежуточный указатель на первый элемент очереди}

BeginO:= BeginO^.Next;{указатель начала переносим на следующий элемент}

dispose(u); {освобождаем память, занятую уже ненужным первым элементом}

end;

End;

Задание. Напишите программу, содержащую все необходимые процедуры и функции работы с очередью.

Задание. Чтобы наглядно рассмотреть работу очереди, наберите следующую программу.

Program Demidenko;

Uses

Crt, Graph;

Type

sp=^spis;

spis=record

elem: byte;

next: sp;

End;

Var

a,

b: byte;

s: string;

gd, gm, c: integer;

head, some, x: sp;

bol: boolean;

ch: char;

Procedure OutHead(x, y: integer);

Begin

Line(x+20,y+35,x+20,y+20);

Line(x+20,y+20,x+17,y+25);

Line(x+20,y+20,x+23,y+25);

Line(x+23,y+25,x+17,y+25);

OutTextXY(x+6, y+38, 'head');

End;

Procedure OutX(x, y: integer);

Begin

Line(x+40,y-15,x+40,y);

Line(x+40,y,x+37,y-5);

Line(x+40,y,x+43,y-5);

Line(x+43,y-5,x+37,y-5);

OutTextXY(x+28,y-25,'x');

End;

Procedure wiv(x,y:integer;ss:sp);

Begin

Line(x,y,x+50,y);

Line(x,y,x,y+20);

Line(x,y+20,x+50,y+20);

Line(x+50,y,x+50,y+20);

Line(x+30,y,x+30,y+20);

if some=ss

then

Begin

Line(x+40,y-15,x+40,y);

Line(x+40,y,x+37,y-5);

Line(x+40,y,x+43,y-5);

Line(x+43,y-5,x+37,y-5);

OutTextXY(x+28,y-25,'tail');

End;

if ss^.elem<255

then

Begin

str(ss^.elem,s);

outtextxy(x+10,y+10,s);

End;

if ss^.next<>nil

then

Begin

Line(x+40,y+10,x+60,y+10);

Line(x+60,y+10,x+60,y-10);

Line(x+60,y-10,x+100,y-10);

Line(x+100,y-10,x+100,y);

Line(x+100,y,x+97,y-5);

Line(x+100,y,x+103,y-5);

Line(x+103,y-5,x+97,y-5);

Wiv(x+70, y, ss^.next);

End

else

Begin

Line(x+40,y+10,x+40,y+30);

Line(x+40,y+30,x+37,y+25);

Line(x+40,y+30,x+43,y+25);

Line(x+43,y+25,x+37,y+25);

Line(x+35,y+32,x+45,y+32);

Line(x+36,y+35,x+44,y+35);

Line(x+38,y+38,x+42,y+38);

End;

End;

Procedure InsertOch(x: byte);

Begin

Cleardevice;

OutTextXY(50,20,'NEW(SOME^.NEXT)');

new(some^.next);

some^.next^.next:=nil;

some^.next^.elem:=255;

Wiv(20,100,head^.next);

OutHead(20,100);

Delay(1000);

Cleardevice;

OutTextXY(50,20,'SOME:=SOME^.NEXT');

some:= some^.next;

some^.next:= nil;

Wiv(20,100,head^.next);

OutHead(20,100);

Delay(1000);

Cleardevice;

Outtextxy(50,20,'SOME^.NEXT:=NIL');

Str(x,s);

OutTextXY(50,40,'SOME^.ELEM:='+s);

some^.elem:= x;

Wiv(20,100,head^.next);

OutHead(20,100);

Delay(1000);

end;

Procedure DelOch;

Begin

Cleardevice;

if head^.next^.elem=255

then

Begin

OutTextXY(50,20,'Элемент не существует!');

Delay(1000);

End

else

if head^.next^.next<>nil

then

Begin

OutTextXY(50,20,'X:=HEAD');

OutTextXY(50,40,'HEAD:=HEAD^.NEXT');

Wiv(20,100,head^.next);

OutX(15,100);

OutHead(90,100);

Delay(1000);

Cleardevice;

OutTextXY(50,20,'DISPOSE(X)');

Wiv(20,100,head^.next);

OutX(20,100);

OutHead(90,100);

Setcolor(red);

Line(20,90,70,130);

Line(70,90,20,130);

Setcolor(white);

Delay(1000);

Cleardevice;

head:=head^.next;

Wiv(20,100,head^.next);

OutHead(20,100);

End

else

Begin

OutTextXY(50,20,'DISPOSE(HEAD)');

Wiv(20,100,head^.next);

OutHead(20,100);

setcolor(red);

Line(20,90,70,130);

Line(70,90,20,130);

setcolor(white);

delay(1000);

cleardevice;

OutHead(20,100);

head^.next^.elem:=255;

some:=head;

End;

End;

Begin

TextBackGround(black);

ClrScr;

bol:=false;

gD:= Detect;

InitGraph(gD, gM,'c:\tp7\bgi\');

new(head);

some:=head;

some^.next:=nil;

Repeat

OutTextXY(50,200,'1 * Добавить элемент');

OutTextXY(50,220,'2 * Удалить элемент');

OutTextXY(50,240,'Esc Выход');

ch:=readkey;

case ch of

'1': Begin

OutTextXY(50,260,'Введите число:');

Gotoxy(23,17);

readln(b);

InsertOch(b);

End;

'2': DelOch;

#27: Begin

CloseGraph;

Halt;

End;

End;

until bol;

CloseGraph;

End.

Примеры решения задач

Задание. Рассмотрите приведенные примеры задач. Наберите программы на компьютере, дополните их комментарием и протестируйте их. Имейте в виду, что уже рассмотренные выше подпрограммы в текстах задач пропущены. Будьте готовы объяснить учителю алгоритмы решения задач и продемонстрировать их графически.

Пример 1. За один просмотр файла действительных чисел и с использованием очереди напечатать элементы файла в следующем порядке: сначала – все числа, меньшие а, затем – все числа из отрезка [а, b], и наконец – все остальные числа, сохраняя исходный порядок в каждой из этих трех групп чисел. Числа а и b задает пользователь.

Program MordovskihK;

Type

EXO = ^O;

O = record

Data: integer;

Next: EXO;

End;

Var

i: Real;

Min, Vibr, Other, EndMin, EndVibr, EndOther: EXO;

f: File of real;

Stroka: string;

Procedure writeO(Var BeginO, EndO: EXO; c: real);

...

Procedure PrintO(u: EXO);

...

Begin

Min:= Nil;

Vibr:= Nil;

Other:= Nil;

EndMin:= Nil;

EndVibr:= Nil;

EndOther:= Nil;

writeln ('Введите имя файла >');

readln(Stroka);

writeln ('Введите промежуток >');

readln(a, b);

assign(f, Stroka);

reset(f);

while not Eof(f) do

begin

read(f, i);

if i<a

then

writeO(Min, x, i)

else

if (i>=a) and (i<=b)

then

writeO(Vibr, x, i)

else

writeO(Other, x, i)

end;

close(f);

writeln('Числа, меньшие ', а);

Print(Min);

writeln('Числа из промежутка [', а, b, ']');

Print(Vibr);

writeln('Числа, большие ', b);

Print(Other);

End.

Пример 2. Из заданного текста перенести все цифры в конец каждой строки, сохранив их порядок.

Program BaranovA;

Type

EXO = ^O;

O = record

Data: integer;

Next: EXO;

End;

Var

i: integer;

O1, EndO1, O2, EndO2: EXO;

f1, f2: text;

Name, NewName, Stroka, NewStroka: string;

Procedure writeO(Var BeginO, EndO: EXO; k: char);

...

Procedure readO(u: EXO);

...

ModifStr(St: string, NewSt: string);

Var

l: char;

O1:= Nil;

EndO1:= Nil;

O2:= Nil;

EndO2:= Nil;

NewSt:= '';

for i:= 1 to Length(St) do

if St[i] in ['1', '2', '3', '4', '5', '6', '7', '8', '8', '9', '0']

then

writeO(O2, EndO2, St[i])

else

writeO(O1, EndO1, St[i]);

while O1 <> Nil do

begin

readO(O1, EndO1, l);

NewSt:= NewSt + l;

end;

while O2 <> Nil do

begin

readO(O2, EndO2, l);

NewSt:= NewSt + l;

end;

End;

Begin

write('Введите имя исходного файла: ');

readln(Name);

write('Введите имя файла-результата: ');

readln(NewName);

assign(f1, Name);

assign(f2, NewName);

reset(f1);

rewrite(f2);

while not Eof(f1) do

begin

readln(f1, Stroka);

ModifStr(Stroka, NewStroka);

writeln(f2, NewStroka);

end;

close(f1);

close(f2);

End.

 

Занятие IV

Тема. Самостоятельное решение задач

Задачи для самостоятельного решения:

1. Дан текстовый файл. Проанализировав в программе содержимое файла, выберите из него числа и занесите в очередь. Выведите содержимое очереди на экран и посчитайте сумму этих чисел. Решение в программе оформляйте через подпрограммы.

2. Дан текстовый файл. Проанализировав в программе содержимое файла, выберите из него имена и занесите в очередь. Выведите содержимое очереди на экран и посчитайте количество элементов образованной очереди. Решение в программе оформляйте через подпрограммы.

3. Проверьте на равенство две очереди. Решение в программе оформляйте через подпрограммы.

4. Найдите среди трех (4, 5) очередей две одинаковые. Решение в программе оформляйте через подпрограммы.

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

6. Создайте файл символьного типа. Организовывая очереди по N элементов, cоздайте файл слов по N символов в каждом. Решение в программе оформляйте через подпрограммы.

7. Создайте файл целого типа. Проанализировав в программе содержимое файла, создайте одну очередь однозначных чисел, а вторую очередь двузначных чисел. Перемножьте соответственные элементы двух очередей и организуйте третью очередь. Результат выведите в текстовый файл. Решение в программе оформляйте через подпрограммы.

8. Используя очередь, проверьте, какие строки текстового файла являются симметричными. Решение в программе оформляйте через подпрограммы.

9. Используя очередь, проверьте на равенство два текстовых файла. Решение в программе оформляйте через подпрограммы.

10. Создайте две очереди. Проверьте, является ли одна из очередей частью другой. Решение в программе оформляйте через подпрограммы.

 

Занятие V

Тема. Кольцо. Формирование кольца. Основные операции над кольцом.

Koльцо - это вид связанного списка, в котором указатель последнего элемента ссылается на первый элемент.

Рассмотрите его графическое представление.

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

Кольцо является динамической структурой – в зависимости от пользователя программы может изменяется длина и набор составляющих его элементов.

Опишем кольцо на языке программирования:

Type

TypeCircle = ^K;

K = record

Data: integer;

Next: TypeCircle;

End;

Var

Circle1: TypeCircle;

Формирование кольца

Рассмотрите процедуру формирования кольца. Для работы этой процедуры заводятся две локальные переменные типа TypeCircle для хранения адресов промежуточного и завершающего звена списка, последним оператором преобразуемого в кольцо.

Procedure FofmK(Var u: TypeCircle);

Var

x, y: TypeCircle;

i, N: integer;

Begin

write('Введите количество звеньев кольца: ');

readln(N);

for i:= 1 to N do

begin

new(x); {выделяем память для хранения нового элемента кольца}

write('Введите данные в звено: ');

readln(i);

x^.Data:= i; {заносим информацию в поле данных}

if u=nil {если кольцо еще не создано}

then

u:= x {то указатель первого элемента ставим на новый элемент}

else

y^.Next:= x; {присоединяем новый элемент к последнему элементу}

y:= x; {переносим указатель у на последний элемент}

end;

x^.Next:= u; {преобразуем получившийся список в кольцо}

End;

Над кольцом определены три операции: занесение элемента в кольцо, извлечение элемента из кольца и обход кольца.

Задание. Составьте программу, содержащую две процедуры: процедуру занесения элемента в кольцо и процедуру извлечения элемента из кольца по какому-либо условию. (Можно воспользоваться предыдущим текстом программы.)

Обход кольца

Для того чтобы обойти кольцо и вывести на экран содержащуюся в нем информацию, необходимо в локальной переменной типа TypeCircle запомнить адрес первого выводимого элемента. В этом случае можно избежать повторения и зацикливания программы. Вывод данных можно начинать с любого элемента кольца; это зависит от адреса первого элемента, переданного в процедуру обхода.

Рассмотрите процедуру обхода кольца.

Procedure PrintК(u: TypeCircle);

Var

x: TypeCircle;

Begin

x:= u;

repeat

write(x^.Data,' ');

x:= x^.Next;

until x=u;

readln;

End;

Задание. Дополните предыдущую программу процедурой обхода кольца.

 

Занятие VI

Тема. Примеры решения задач с применением динамической структуры кольцо. Творческая работа.

Задание. Рассмотрите приведенные примеры задач, решенные с помощью динамической структуры – кольцо. Наберите их на компьютере, проверьте их действие, вставьте комментарий.

Задача 1. N ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k-го, смыкая при этом круг. Определить порядок удаления ребят из круга.

Для хранения данных об участниках игры используется список.

Наберите предложенный ниже текст программы, проверьте его работу, дополните комментариями.

Program Schitalka;

Type

Children = ^Child;

Child = record

Data: integer;

Next: Children;

end;

Var

Circl, p, Temp: Children;

i, j, NumName: integer;

text: string;

Function NumSlov(Var S: string): integer;

Var

i, d: integer;

Begin

d:= 0;

i:= 1;

while i < Length(S) do

begin

while S[i] = ' ' do

Inc(i);

while S[i] <> ' ' do

Inc(i);

d:= d+1;

end;

if S[Length(S)] = ''

then

d:= d-1;

NumSlov:= d;

End;

Procedure AddName(Var Old, Young: Children);

Begin

Young^.Next:= Old;

Young^.Prev:= Old^.Prev;

Old^.Prev^.Next:= Young;

Old^.Prev:= Young;

End;

Procedure DeleteName(Var Old: Children);

Begin

Old^.Next^.Prev:= Old^.Prev;

Old^.Prev^.Next:= Old^.Next;

End;

Begin

new(Circl);

Circl^.Next:= Circl;

Circl^.Prev:= Circl;

Circl^.Name:= '';

writeln('Считалка');

writeln('Введите текст считалки >');

readln(text);

writeln('Сколько человек в кругу? >');

readln(NumName);

if NumName>0

then

begin

write('Введите ',i,'-е имя: ');

new(p);

readln(p^.name);

temp:= head^.next;

while temp <> head do

temp:= temp^.next;

AddName(temp, p);

end;

for i:= 1 to NumName-1 do

begin

temp:= head;

for j:= 1 to NumSlov(text) do

begin

temp:= temp^.next;

if temp^.name = ''

then

temp:=temp^.next;

end;

writeln(temp^.name, '- вышел');

deleteName(temp);

end;

writeln(head^.next^.name, '- остался');

End.

Пример 2. Вывести на экран работающий светофор.

Program GrushinK;

Uses

Crt, Graph;

Type

TypeCircle = ^K;

K = record

Data: char;

Next: TypeCircle;

end;

Const

XX = 80;

R = 50;

Var

Svetofor, x: TypeCircle;

FraphDriver, GraphMode, Y: integer;

Procedure Picture;

Begin

SetViewPort(240, 1, 400, 477, ClipOff);

Line(0, 1, 0, 477);

Line(160, 1, 160, 477);

Line(0, 1, 160, 1);

Line(0, 477, 160, 477);

Line(0, 150, 156, 150);

Line(0, 330, 156, 330);

Line(-240, 480, 0, 100);

Line(400, 480, 160, 100);

Line(380, 460, 160, 460);

Line(160, 440, 368, 440);

Line(368, 440, 380, 460);

Line(-220, 460, -208, 440);

SetFillStyle(1, White);

FloodFill(375, 455, White);

FloodFill(-215, 455, White);

SetFillStyle(7, 6);

FloodFill(-230, 200, White);

SetColor(4);

Line(-240, 150, -120, -1);

Line(400, 150, 240, -1);

SetColor(15);

SetFillStyle(9, 4);

FloodFill(-240, 0, 4);

FloodFill(390, 10, 4);

SetFillStyle(1, 8);

FloodFill(-100, 470, White);

Y:= 74;

Circle(XX, Y, R);

Y:= 240;

Circle(XX, Y, R);

Y:= 405;

Circle(XX, Y, R);

SetFillStyle(9, 6);

FloodFill(5, 5, White);

End;

Procedure Yellow(Y: integer);

Begin

Picture;

Y:= 240;

SetFillStyle(1, 14);

FloodFill(XX, Y, 15);

Delay(850);

ClearViewPort;

End;

Procedure Green(Y: integer);

Begin

Picture;

Y:= 405;

SetFillStyle(1, 2);

FloodFill(XX, Y, 15);

Delay(1500);

ClearViewPort;

End;

Procedure Red Yellow(Y: integer);

Begin

Picture;

Y:= 240;

SetFillStyle(1, 14);

FloodFill(XX, Y, 15);

Delay(1500);

ClearViewPort;

End;

Procedure Red(Y: integer);

Begin

Picture;

Y:= 74;

SetFillStyle(1, 4);

FloodFill(XX, Y, 15);

Delay(2000);

ClearViewPort;

End;

Procedure Vibor;

Begin

case x^.Data of

'R': Red(Y);

'2': Red Yellow(Y);

'G': Green(Y);

'Y': Yellow(Y);

End;

Begin

GraphDriver:= Detect;

InitGraph(GraphDriver, GraphMode, '..\BGI');

new(x);

u:= x;

x^.Data:= 'R';

new(x^.Next);

x:= x^.Next;

x^.Data:= '2';

new(x^.Next);

x:= x^.Next;

x^.Data:= 'G';

new(x^.Next);

x:= x^.Next;

x^.Data:= 'Y';

x^.Next:= u;

x:= u;

while not KeyPressed do

begin

Vibor;

x:= x^.Next;

end;

End.

Задание. Придумайте интересную задачу из жизни и решите ее с помощью динамической структуры кольцо.

 

Списки

 

Занятие I

 

Тема. Список. Создание списка путем добавления элементов в конец списка. Просмотр списка.

 

Определение. Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (Nil).

 

Схематически это выглядит так:

 

 

Попробуем вместе сформировать небольшой список путем добавления элементов в конец списка.

Задача. Сформировать список, содержащий целые числа 3, 5, 1, 9.

 

Для этого сначала определим запись типа S с двумя полями. В одном поле будут содержаться некоторые данные (в нашем случае числа 3, 5, 1 и 9), а в другом поле будет находится адрес следующего за ним элемента.

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

 

Type

Ukazatel = ^S;

S = Record

Data: integer;

Next: Ukazatel;

End;

 

Таким образом, мы описали ссылочный тип, с помощью которого можно создать наш связанный однонаправленный список.

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

А теперь опишем переменные для решения нашей задачи:

 

Var

Head, {указатель на начало списка}

x {вспомогательный указатель для создания очередного элемента списка}

: Ukazatel;

 

Создадим первый элемент:

 

New(x); {выделим место в памяти для переменной типа S}

x^.Data:= 3; {заполним поле Data первого элемента}

x^.Next:= Nil; {заполним поле Next первого элемента: указатель в Nil}

Head:= x; {поставим на наш первый элемент указатель головы списка}

 

 

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

 

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

Поэтому можно записать равенства:

Head^.Next = x^.Next;

Head^.Data = x^.Data;

Head = x;

 

Выделим область памяти для следующего элемента списка.

 

New(x^.Next);

 

 

Присвоим переменной х значение адреса выделенной области памяти, иначе, переставим указатель на вновь выделенную область памяти:

 

x:= x^.Next;

 

 

Определим значение этого элемента списка, иначе, заполним поля:

 

x^.Data:= 5;

x^.Next:= Nil;

 

 

 

Итак, теперь у нас список содержит два элемента. Понятно, чтобы создать третий и четвертый элементы, нужно проделать те же самые операции.

 

Задание. Запишите в тетрадь ответы на вопросы:

 

1. Какие операции требуется выполнить для вставки в список его элемента?

2. Можно ли для построения списка обойтись одной переменной?

3. Сколько элементов может содержать список?

4. Когда прекращать ввод элементов списка?

5. Запишите в тетрадь рассмотренные операторы и дополните их операторами, создающими третий и четвертый элементы списка (1, 9).

 

Теперь попробуем подытожить наши рассуждения.Оформим создание списка в виде процедуры, в которой его элементы вводятся с клавиатуры.

 

Procedure Init(Var u: Ukazatel);

Var

x: Ukazatel;

Digit: integer; {Значение информационной части элемента списка}

Begin

Writeln('Введите список ');

Head:= Nil; {Список пуст}

Writeln ('Введите элементы списка. Конец ввода 0');

Read (Digit);

if Digit <> 0

then {Формируем и вставляем первый элемент списка}

Begin

New(x);

x^.Next:= Nil;

x^.Data:= Digit;

Head:= x

Read (Digit);

while Digit<>0 do

Begin

New(x^.Next); {Формируем и вставляем элемент в конец списка}

x:= x^.Next;

x^.Next:= Nil;

x^.Data:= Digit;

Read(Digit);

End;

Writeln;

End;

 

Рассмотрите формирование списка несколько другим способом.

 

Procedure Init(Var u: Ukazatel);

Var

x, y: Ukazatel;

Digit: integer;

Begin

Writeln('Введите список ');

Head:= Nil;

Writeln ('Введите элементы списка. Конец ввода 0');

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;

 

Задание. Перепишите эту процедуру в тетрадь, дополните ее комментарием, составьте чертеж и приготовьте учителю подробное объяснение работы данной процедуры.

 

Просмотр списка

 

Просмотр элементов списка осуществляется последовательно, начиная с его начала. Указатель р последовательно ссылается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. При этом с каждым элементом списка выполняется операция вывода на экран. Начальное значение р – адрес первого элемента списка p^. Если р указывает на конец списка, то его значение равно Nil, то есть

 

while p<>Nil do

Begin

Write(p^.Data, ' ');

p:= p^.Next;

End;

 

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

 

 

 

анятие II

 

Тема. Создание списка путем вставления элементов в начало.

 

Задание. Путем добавления элемента в начало списка получить список, изображенный на рисунке:

 

 

Эту задачу Вы решите сами немного позже, а сейчас рассмотрим как добавить в этот список некоторый элемент, например 2. То есть получить такой список:

 

Выполним следующие действия:

 

New(x); {Создание новой динамической переменной}

 

x^.Data:= 2; {Информационное поле созданного элемента}

x^.Next:= Head; {Присоединим элементы списка и к созданному элементу}

 

u:= x; {Изменим значение указателя начала списка}

 

Итак, нужный элемент вставлен. Теперь Вы можете сформировать весь данный список полностью.

 

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

 

Выберите с учителем задачи для самостоятельного решения.

 

1. Написать программу, содержащую процедуры формирования и просмотра списка и функцию вычисления среднего арифметического элементов непустого списка.

 

2. Написать программу, содержащую процедуры формирования и просмотра списка и подпрограмму проверки наличия в списке заданного числа.

 

3. Написать программу, содержащую процедуры формирования и просмотра списка и функцию, подсчитывающую количество слов списка, которые начинаются и оканчиваются одной и той же литерой.

 

4. Написать программу, содержащую процедуры формирования и просмотра списка и функцию, подсчитывающую количество слов списка, которые начинаются той же литерой что и следующее слово.

 

5. Написать программу, содержащую процедуры формирования и просмотра списка и функцию, подсчитывающую количество различных значений информационной части уже существующего списка.

 

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

 

7. Написать программу, содержащую процедуры формирования и просмотра списка со строковой информационной частью. Включите в нее функцию, которая оставляет в информационной части только первое слово находящегося там предложения.

 

8. Написать программу, содержащую процедуры формирования и просмотра списка со строковой информационной частью. Включите в нее функцию, которая оставляет в информационной части только гласные буквы находящегося там предложения.

 

9. Написать программу, содержащую процедуры формирования и просмотра списка со информационной частью являющейся произвольным массивом. Включите в нее функцию, которая удаляет из информационной части отрицательные числа.

 

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

 

Занятие III

 

Тема. Упорядочивание списка. Вставление элемента в середину списка.

 

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

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

После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо во внутрь. Первый и второй случаи мы уже рассмотрели выше. Остановимся на третьем случае.

Для того чтобы вставить в список элемент со значением 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;

 

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

 

Занятие IV-V

 

Тема. Примеры задач, решаемых с помощью списка. Решение задач.

 

Задание. Просмотрите предложенные решения задач и приготовьтесь объяснить алгоритм их решения учителю. Если необходимо, то наберите программы на компьютере и просмотрите их действие.

 

Задача 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>');

Repeat

Readln(St);

Writeln (F, St);

until St = '';

Write('Файл создан');

close (F);

Reading;

End;

 

Procedure Proverka;

Var

x, y, u: EXS;

i: integer;

Begin

Reset (F);

while not Eof (F) do

Begin

Readln (F, St[i]);

while i < Length (St) do

Begin

New (x);

x^.Next:= Nil;

if (St[i] <> '') or (St[i] <> St[Length(St)])

then

x^.Data:= x^.Data + St[i];

if u = Nil

then

u:= x

else

y^.Next:= x;

y:= x;

End;

End;

close (F);

Smotr (u);

End;

 

Begin

ClrScr;

TextColor (White);

CreateFile;

Proverka;

End.

 

Выберите с учителем задачи для самостоятельного решения.

 

1. Написать программу, содержащую процедуру, которая меняет местами первый и второй элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.

 

2. Написать программу, содержащую процедуру, которая меняет местами первый и пятый элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.

 

3. Написать программу, содержащую процедуру, которая меняет местами первый и последний элементы непустого списка. Если элементы не найдены, то выдать на экран соответствующие сообщение.

 

4. Написать программу, содержащую процедуру, которая вставляет новый элемент перед каждым вхождением заданного элемента. Если элементы не найдены, то выдать на экран соответствующие сообщение.

 

5. Написать программу, содержащую процедуру, которая вставляет новый элемент за каждым вхождением заданного элемента. Если элементы не найдены, то выдать на экран соответствующие сообщение.

 

6. Написать программу, содержащую подпрограмму, которая проверяет на равенство списки М1 и М2.

 

7. Написать программу, содержащую функцию, которая определяет, входит ли список М1 в список М2. Предполагается, что списки существуют.

 

8. Написать программу, содержащую подпрограмму, которая копирует в конец непустого списка М его первый элемент. Если элементы не найдены, то выдать на экран соответствующие сообщение.

 

9. Написать программу, содержащую подпрограмму, которая копирует в начало непустого списка М его последний элемент. Если элементы не найдены, то выдать на экран соответствующие сообщение.

 

10. Написать программу, содержащую процедуру, которая копирует в список М за каждым вхождением заданного элемента все элемента списка М1.

 

11. Написать программу, содержащую процедуру, которая объединяет два упорядоченных по неубыванию списка М1 и М2 в один упорядоченный по неубыванию список, построив новый список М.

 

12. Написать программу, содержащую процедуру, которая объединяет два упорядоченных по неубыванию списка М1 и М2 в один упорядоченный по неубыванию список, сменив соответствующим образом ссылки в М1 и М2.

 

13. Написать программу, содержащую функцию, которая проверяет, упорядочены ли элементы списка по алфавиту.

 

14. Напишите программу сортировки существующего списка по алфавиту. В программе используйте подпрограммы.

 

15. Напишите программу, которая создавала бы файл целых чисел, а затем формировала список целых чисел файла. Создайте в конце списка элемент, содержащий сумму всех чисел файла. В программе используйте подпрограммы.

 

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

 

17. Напишите программу, которая создавала бы текстовый файл, а затем формировала список строк файла. Создайте список обратных строк. В программе используйте подпрограммы.

 

18. Напишите программу, которая создавала бы текстовый файл, а затем формировала список строк файла. Создайте отсортированный список строк. В программе используйте подпрограммы.

 

19. Напишите программу, которая создавала бы файл комбинированного типа, а затем формировала список, используя какое-либо поле записи. Создайте отсортированный список. В программе используйте подпрограммы.

 

20. Напишите программу, которая создавала бы файл комбинированного типа, а затем формировала список элементов файла. Создайте отсортированный по какому-либо полю список. В программе используйте подпрограммы.

 

Занятие VI

 

Тема. Удаление элемента из списка.

 

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

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

Уточним поставленную перед нами задачу: удалить из списка элемент с заданной информационной частью.

Обозначим Head – исходный список, Digit – значение информационной части удаляемого элемента.

При исследовании списка на наличие в нем заданного элемента может встретиться три различных случая. Рассмотрим их.

 

Удаление элемента из начала списка

 

Изобразим удаление графически:

 

 

 

Напишем фрагмент программы:

 

x:= Head; {Запомним адрес первого элемента списка}

Head:= Head^.Next; {Теперь Head указывает на второй элемент списка}

Dispose(x); {Освободим память, занятую переменной x^}

 

Удаление элемента из середины списка

 

Для этого нужно знать адреса удаляемого элемента и элемента, находящегося в списке перед ним.

 

Изобразим удаление графически:

 

 

 

x:= Head; {Переменная х для хранения адреса удаляемого элемента}

{Найдем адреса нужных элементов списка}

while (x<>Nil) and (x^.Data<>Digit) do

Begin

dx:= x;

x:= x^.Next

End;

dx^.Next:= x^.Next;

Dispose(x);

 

Удаление элемента из конца списка

 

Удаление элемента из конца списка производится, когда указатель dx показывает на предпоследний элемент списка, а х – на последний.

 

Изобразим удаление графически:

 

 

 

 

{Найдем предпоследний элемент}

x:= Head;

dx:=Head;

while x^.Next<>Nil do

Begin

dx:= x;

x:= x^.Next;

End;