Методичка Программирование

procedure Delete1(var lst:pTList;E1: pTList); var tmp, tmp2:pTList;

	begin	//будет содержать адрес
	tmp:=lst;
	tmp2:=lst;	//удаляемого элемента
			//будет содержать адрес
	while (tmp<>E1) do		//элемента перед удаляемым
			//пока не дошли до
		//удаляемого элемента,
		//предполагается, что он
	begin	//в списке присутствует
		//запоминаем адрес текущего элемента
	tmp2:=tmp;
	tmp:=tmp^.Next;	//переходим к следующему
	end;
	tmp2^.Next:=tmp^.Next;//выносим удаляемый
	Dispose(tmp);		//элемент из списка
		//освобождаем память
	end;

Одной из наиболее простых операций со всеми типами списков является их прохождение, т.е. поочерёдное получение доступа ко всем элементам. Приведём процедуру, реализующую эту операцию для просмотра списка (другие возможные варианты использования прохождения – поиск данных, сохранение списка в файл и т.д.)

{ Вывод данных всего списка

lst - список, который необходимо вывести на экран} procedure PrintList(lst:pTList);

var tmp:pTList;
begin	//встаем на начало списка
tmp:=lst;
while (tmp<>nil) do	//пока список не кончился
begin
writeln(tmp^.data);
tmp:=tmp^.Next;	//переходим к следующему элементу
end;
end;

Достоинствами односвязного списка являются меньший расход памяти по сравнению с другими связными динамическими структурами данных (всего 1 указатель) и простота операций.

Недостатки односвязного линейного списка заключаются в следующем:

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

91

начинать с начального элемента, что неудобно, нерационально и усложняет алгоритмы обработки данных;

следствием первого недостатка является усложнение взаимодействия операций поиска и удаления.

Двусвязный линейный список

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

Рис. 23. Двусвязный линейный список

Элемент двусвязного линейного списка можно определить так:

type pTList=^TList;	//описываем указатель на
TList=record	//элемент списка
	//описываем элемент списка
data:integer;	//область пользовательских
//данных, например число integer
Prev,Next:pTList;	//служебная информация
	//(адрес предыдущего и

//следующего элемента, //или nil если его нет)

end;

В двусвязном линейном списке первый элемент в поле prev содержит значение nil, что указывает на отсутствие предыдущего элемента, и так же как и в односвязном линейном списке, у последнего элемента в поле next содержится значение nil.

Всё, что касалось операций добавления звена и его удаления для односвязного списка, справедливо и для двусвязного. Также должен соблюдаться правильный порядок создания (или удаления) связей между звеньями, но таких операций стало больше, т.к. должны обрабатываться 2 указателя. Кроме того, каждая из операций обладает дополнительными особенностями:

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

2.Возможность перемещаться по списку в обоих направлениях позволяет напрямую задавать удаляемое звено (без использования дополнительной переменной). Следствием этого является упрощение как операции удаления, так и операции поиска.

92

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

procedure Delete2(var lst:pTList;E1: pTList); var tmp:pTList;

begin

tmp:=lst; //будет содержать адрес удаляемого элемента

while (tmp<>E1) do	//ищем удаляемый элемент
begin	//переходим к следующему
tmp:=tmp^.Next;
end;		//для элемента перед
(tmp^.Next)^.Prev:=tmp^.Prev;
		//удаляемым указываем
(tmp^.Prev)^.Next:=tmp^.Next;		//новый следующий
		//для элемента после

	//удаляемого указываем
Dispose(tmp);	//адрес нового предшествующего
	//освобождаем память
end;

Достоинствами двусвязного списка являются:

возможность движения по списку в любом направлении;

несколько проще выполняются некоторые операции (например, удаление). Недостаток: усложняется процесс написания процедур обработки.

Кольцевые списки

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

Для двусвязного списка, кроме того, нужно заменить значение prev первого элемента с nil на адрес последнего элемента. Получится двусвязный кольцевой (циклический) список (рис. 24).

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

Рис. 24. Двусвязный кольцевой (циклический) список

Очередь

Очередь – линейный список, доступ, к элементам которого происходит по принципу FIFO (First In and First Out – первым пришел и первым ушел).

93

Для очереди существует две операции – занесение элемента в очередь и выбор элемента из очереди. В очереди доступны две позиции: начало (из этой позиции происходит выбор) и конец (в эту позицию заносится входящий элемент). Произвольный доступ к элементам, в отличие от массивов, не допускается.

Примерами применения очередей являются:

диспетчеризация задач операционной системой (системная задача);

буферизация ввода/вывода (системная задача);

моделирование процессов (прикладная задача).

Обычно для очереди применяют две подпрограммы:

queue – для добавления данных в очередь

depart – для снятия данных из очереди.

Стек

Стек – разновидность очереди (а значит и разновидность списка), но с другим правилом доступа LIFO (Last In and First Out – последним пришел и первым ушел). Ещё один термин (редко используемый) для обозначения этой структуры данных – магазин.

В стеке доступна единственная позиция – та, в которой находится последний введённый элемент (вершина). Иногда позицию, от которой стек начал заполняться данными, называют дном стека (хотя особого применения этот термин не имеет, поскольку дно стека, в котором содержится более одного элемента данных, недоступно. Одно из немногих рациональных применений термина «дно» – признак пустого стека, когда дно и вершина совпадают).

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

Области применения стеков такие же, как и у очередей: системные:

передача процедурам и функциям аргументов по значению;

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

прикладные:

стековая (магазинная) память, например в языке программирования Forth;

вспомогательные структуры данных (например, при поиске в графе).

Стек ограниченной глубины может быть реализован как с помощью массива, так и с помощью списка. Для реализации стека с помощью списка больше всего подходит односвязный линейный список. Добавление (обычно процедура push) и снятие (обычно функция pop) элемента происходит в начало списка. Если стек пустой, то первый элемент имеет значение nil.

94

Дек

Дек («двухсторонняя очередь») – это очередь, включение и исключение элементов в которой происходят на обоих концах очереди. Применение односвязного линейного списка в этом случае не рационально, т.к. любое добавление или удаление с конца будет приводить к большому количеству действий – переходу от начала к концу. Поэтому для реализации дека обычно применяют двусвязный линейный список, отдельно хранится адрес не только первого элемента, но и адрес последнего. Применение двусвязного линейного списка сводит к минимуму число операций, производимых для того, чтобы добавить или удалить элемент в деке.

Задания к лабораторной работе № 7

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

Проверить правильность работы программ по ранее составленному набору тестов.

Образец выполнения задания

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

инициализация стека;

добавление элемента с запросом ввода данных;

добавление данных, без запроса;

удаление произвольного элемента;

удаление всего списка;

вывод данных элемента;

вывод данных элементов всего списка;

процедура удаления из списка всех элементов, находящиеся между элементами Е1 и Е2, где E1 и E2 – адреса элементов списка.

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

Текст программы (результат ее работы приведен на рис. 25): type pTList=^TList; //описываем указатель на

//элемент списка TList=record //описываем элемент списка

95

data:integer; //область пользовательских

данных, например число integer

Next:pTList;//служебная информация (адрес следующего //элемента, или nil если его нет)

end; //закончили описание элемента списка

{Инициализация списка

lst - список, который необходимо инициализировать

т.к. lst изменится, то передача идет по ссылке} procedure InitList(var lst:pTList);

begin

lst:=nil; //Указываем, что элементов в списке нет. end;

{процедура добавления данных

lst - список, в который добавляем данные data - данные, которые необходим добавить

т.к. lst изменится, то передача идет по ссылке} procedure add_data(var lst:pTList;data:integer); var tmp:pTList;

begin
New(tmp);	//выделяем память под новый элемент
tmp^.data:=data;	//записываем данные
tmp^.Next:=lst;	//текущий первый делаем вторым
lst:=tmp;	//добавляемый делаем первым
end;

{процедура добавления элемента (с запросом данных) lst - список, в который добавляем элемент

т.к. lst изменится, то передача идет по ссылке} procedure add_elem(var lst:pTList);

var dt:integer; //переменная для хранения данных begin

write(Rus('Введите данные (целое число):')); //запрос

readln(dt);	// считывание введенных	данных
add_data(lst,dt);	//добавляем данные
end;

{Вывод данных одного элемента (переданного)

em - элемент, данные которого необходимо вывести} procedure PrintData(em:pTList);

begin
if (em=nil) then		// если элемент не существует, то
writeln(Rus('Данных не существует!!! указатель на
NIL!'))	//сообщаем об этом
else		// иначе

96

writeln(Rus('Данные:'),em^.data); //выводим

//информацию

end;

{ Вывод данных всего списка

lst - список, который необходимо вывести на экран}

procedure PrintList(lst:pTList);
var tmp:pTList; i:integer;
begin
tmp:=lst;		//встаем на начало списка
i:=1;	//для удобства восприятия добавляем
	//номер элемента в списке
writeln(Rus('===НАЧАЛО==='));			//указываем начало
if (tmp=nil) then			//вывода списка
		//если список пуст
writeln(Rus('Список пуст!!!'));			//поясняем это
while (tmp<>nil) do		//пока список не кончился
begin
write(i:3,') ');		//выводим номер элемента
PrintData(tmp);		//вызываем функцию вывода
tmp:=tmp^.Next;		//данных элемента
		//переходим к следующему элементу
i:=i+1;			//увеличиваем номер
end;

writeln(Rus('====КОНЕЦ===')); //указываем, что вывод

//окончен

end;

{убирает элемент из списка

lst - список, из которого необходимо удалить элемент

т.к. lst изменится, то передача идет по ссылке} procedure DestroyEm(var lst:pTList);

var tmp:pTList; //временная переменная для //хранения адреса удаляемого элемента

begin

tmp:=lst; //встаем на начало списка lst:=lst^.Next; //делаем текущим элементом следующий Dispose(tmp); //удаляем текущий элемент

end;

{ удаляет из списка все элементы

lst - список, из которого необходимо удалить все элементы

т.к. lst изменится, то передача идет по ссылке последний элемент списка в поле Next должен

содержать nil}

procedure DestroyList(var lst:pTList);

97

begin
while (lst<>nil) do	//пока список не пуст
DestroyEm(lst);	//удалить элемент
end;

{ проверяет существование элемента в списке lst - список, в котором необходимо проверить

существование

em - элемент, существование которого необходимо проверить}

function ElemExist(lst,em:pTList):boolean; var tmp:pTList;is_exist:boolean;

begin
is_exist:=false;	//Предполагаем, что
tmp:=lst;	//элемента в списке нет
	//встаем на начало списка
while (tmp<>nil) do	//пока не дошли до конца списка
begin
if (tmp=em) then	//проверяем текущий элемент,
begin	//совпадает ли он с проверяемым
is_exist:=true;	//если совпадает, помечаем
	//что он существует

break; //и выходим из цикла end;

tmp:=tmp^.Next; //переходим к следующему элементу end;

ElemExist:=is_exist; //возвращаем результат end;

{Функция для получения адреса элемента по его номеру lst - указатель на начало списка

n - номер элемента, который необходимо найти нумерация начинается с 1

если элемента в списке нет, то возвращается nil} function GetPtr(lst:pTList; n:integer):pTList;

var i:integer;tmp,rez:pTList;

begin
i:=1;	//подсчет элементов начинаем с первого
rez:=nil;	//предполагаем, что элемента нет
tmp:=lst; //встаем указателем на начало списка
while ((i<n) and (tmp<>nil)) do			//пока не дойдем до
begin		//нужного элемента, или
		//список не закончится
tmp:=tmp^.Next;		//переходим к следующему элементу
i:=i+1;		//подсчитываем кол-во элементов

98

end;

if (i=n) then //если вышли из цикла, достигнув //нужного элемента, а не конца

rez:=tmp; //списка, присваиваем адрес GetPtr:=rez; // и возвращаем результат end;

{ Удаляем из списка элементы стоящие между E1 и E2 (включительно)

lst - указатель на начало списка

E1 - элемент, с которого начинаем удаление; E2 - эл- т, которым заканчиваем удаление}

procedure RemoveBetween(var lst:pTList; E1,E2:pTList); var tmp,tmp2:pTList;

begin
if	(ElemExist(lst,E1) and ElemExist(lst,E2))=false
then	//Проверяем, что элементы существует, если нет
	exit;	//то прекращаем обработку
tmp2:=lst;			//элемент до удаляемого,
tmp:=lst;			//встаем на начало списка
			//удаляемый элемент,
while (tmp<>E1) do			//встаем на начало списка
			//пока не дойдем
			//до удаляемого элемента

begin

tmp2:=tmp; //сохраняем предыдущий элемент списка tmp:=tmp^.Next;//переходим к следующему

end;

if (E1=lst) then //Если удаляемый элемент - начало //списка, меняем адрес начала списка

lst:=E2^.Next //на элемент, стоящий после E2 else //Если E1 не начало списка, то tmp2^.Next:=E2^.Next; //просто переводим связь на

//элемент стоящий после удаляемого E2^.Next:=nil; //В удаляемом подсписке указываем конец DestroyList(tmp); //и удаляем этот подсписок

end;

{Основная программа}

var E1,E2,root:pTList; c:char;_first,_last:integer; begin

InitList(root); //инициализируем стек repeat

add_elem(root);

99

repeat

write(Rus('Повторить ввод?(y,n)')); Readln(c);

until ((c='n')or(c='y')) until(c='n');

add_data(root,1); add_data(root,2); add_data(root,3); add_data(root,4);

writeln(Rus('Удаление всех элементов между Е1 и Е2 (включительно) '));

PrintList(root); write(Rus('Введите номер E1:')); Readln(_first); write(Rus('Введите номер E2:')); Readln(_last);

if (_first<=_last) then //обязательное условие //первый удаляемы элемент //должен идти _до_ последнего

begin

E1:=GetPtr(root,_first); writeln(Rus('Вывод данных элемента:')); PrintData(E1);

E2:=GetPtr(root,_last); PrintData(E2);

if (E1<>nil) then

RemoveBetween(root,E1,E2); end;

writeln(Rus('Список после удаления элементов между E1

и E2:')); PrintList(root); DestroyList(root); end.

100