Полный обучающий курс (стр. 70 )

Графически это можно представить так:

Операторы, выполняющие данную задачу будут следующими:

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>');

repeat

readln(St);

writeln (F, St);

until St = '';

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

close (F);

readln;

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

Занятие 6. Удаление элемента из списка.

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

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

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

Обозначим 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;

{Удаляем элемент x^ из списка и освобождаем занимаемую им память}

dx^.Next := Nil;

Dispose(x);

Теперь опишем процедуру удаления элементов из списка в общем случае:

Procedure Del(Gigit : integer; Var u : Ukazatel );

Var

x, dx : UKAZATEL ;

Begin

x := Head;

while x<>Nil do

if x^.Data=Digit

then

Begin

if x=y

then

Begin

Head := Head^.Next;

Dispose(x);

x := Head;

End;

else

Begin

dx^.Next := x^.Next;

Dispose(x);

x := dx^.Next;

End;

End;

else

Begin

dx := x;

x := x^.Next;

End;

End;

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

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

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

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

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

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

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

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

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

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

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

10. Познакомившись с текстами предыдущих задач, придумайте свою задачу и решите ее.

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

Проверьте свои знания, ответив на вопросы:

1. Дайте определение динамической структуре список.

2. Сколько элементов может содержать список? Как заканчивается список?

3. Сколько полей может содержать элемент списка? От чего зависит количество полей? Приведите примеры.

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

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

6. Можно ли ссылку одного элемента направить сразу на два или больше других элемента? Как необходимо поменять тип указателя, чтобы решить эту проблему?

7. Может ли элемент списка быть такого типа, чтобы содержать несколько полей типа указателя? Если – да, то приведите пример для чего это может быть нужно.

8. Можно ли последовательно "связать" два списка разного типа и почему?

9. Можно ли одновременно работать с несколькими списками сразу?

10. Как Вы считаете, на что нужно обращать особое внимание при работе со списками?