15.3.2. Алгоритм удаления первого элемента из очереди

Предположим,

что

очередь

создана,

т.е. begin

не

равен NULL

(рекомендуется организовать проверку на равенство NULL с

соответствующей обработкой данной ситуации).

1. Устанавливаем текущий указатель на начало очереди:

t = begin;

2. Обрабатываем информационную часть первого элемента очереди,

например, выводим на экран.

3. Указатель на начало очереди переставляем на следующий (2-й)

элемент

begin = begin->Next;

free(t);Р

4. Освобождаем память, захваченную под 1-й элемент:

5. Выводим сообщение, например, «Элемент удален!».

И

Алгоритмы

просмотра очереди

и освобождения

памяти

выполняются аналогично стеку (см. п. 15.2).

У

Г

Б

15.4. Двунаправленный линейный список

Более

универсальным

явл

тся

двун правленный

(двухсвязный)

список, в каждый элемент которого

ромеазателяу

на следующий элемент

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

аналогично очереди использу

ся два указателя – на первый и последний

элементы.

яе

Графически так й спис к выглядит следующим образом:

begin

ют

end

о

и

info (i1)

info (i2)

info (i3)

. . .

info (in)

NULL

Prev

Prev

Prev

л

Next

Next

NULL

Next

б

иВведем

структуру,

в

которой

(для

простоты,

как и

раньше)

информационнойБ частью info будут целые числа, а адресная часть состоит из двух указателей на предыдущий (Prev) и следующий (Next) элементы:

struct Spis {

int info;

Spis *Prev, *Next;

} ;

Для работы со списком декларируем Spis *begin, *end; – указатели на начало и конец списка соответственно.

137

Формирование двунаправленного списка проводится в два этапа – формирование первого элемента и добавление нового. Причем добавление может выполняться как в начало, так и в конец списка.

15.4.1. Формирование первого элемента

1. Захват памяти под текущий элемент: Spis *t = (Spis*) malloc (sizeof(Spis));

На данном этапе имеем элемент:

t								Р
		info
		Prev					И
		Next
						У
2. Формируем первый элемент списка:
а) формируем информационную часть, например, вводя с клавиатуры:
scanf(“%d”,		&t -> info);			или cin >> t -> info;
				Б
б) формируем адресные части (первоначально это NULL):
t -> Prev = t -> Next = NULL;					Г
в) указатели начала и конца спис устанавливаем на этот элемент:
begin = end = t;

После выполнения указанных действий получили первый элемент списка:
begin				е			ка
					i		info
	т
end					к
				NULL			Prev
о
				NULL			Next

			ти
15.4.2. Добавлен е элементов в конец списка
1.			л
		Нача о цик а.
2.		Захват памя под текущий элемент:
и			t = (Spis*) malloc(sizeof(Spis));
3.		Формирование информационной части:
Б	б scanf(“%d”, &t -> info);

4. Формирование адресных частей текущего элемента:

а) указателю на следующий элемент (Next) присваиваем значение NULL, т.к. добавление выполняем в конец, следующего за t нет:

t -> Next = NULL;

б) указателю на предыдущий элемент (Prev), используя указатель конца (end), присваиваем адрес бывшего последнего элемента:

t -> Prev = end;

138

5. Последним элементом был end, а должен стать t, для этого указатель на следующий элемент последнего в списке (end) устанавливаем на созданный (текущий):

end -> Next = t;

6.Переставляем указатель конца списка на созданный элемент: end = t;

7.Продолжаем цикл до тех пор, пока не обработаем признак его завершения.

15.4.3. Алгоритм просмотра списка
С начала							С конца
1. Устанавливаем текущий указатель на:											Р
начало списка t = begin;						конец списка t = end;
									И
2. Начало цикла, работающего до тех пор, пока t									!= NULL.
3. Информационную часть текущего элемента									t -> info – на печать.
										У
4. Устанавливаем текущий указатель на:
Г
следующий элемент, адрес которого						предыдущий элемент, адрес которого
находится в поле Next текущего						н ходится в поле Prev текущего
элемента						элементаБ
t = t -> Next;								t = t -> Prev;
5. Конец цикла.							а
					к
15.4.4. Алгоритм поиска эл нта в списке по ключу
				ме
Ключом может бы ь любое ин ересующее значение (в зависимости от
поставленной задачи). П э			му у очним задачу: найдем конкретное значение
info в списке и его порядк вый номер.
			т
1. Введем с клав атуры ключ поиска, т.е. искомое значение i_p.
		о
2. Установим текущий указатель на начало списка:
		и
		t = begin;
3. Счетчлементовк э			k = 1;
4. Начало цикла (выполнять пока t != NULL, т.е. не дойдем до конца).
	б
5. Сравниваем информационную часть текущего элемента с искомым:
лиа) ес они совпадают (t -> info = i_p), выводим на экран элемент, его
номер k и завершаем поиск (break);
Б

б) иначе, переставляем текущий указатель на следующий элемент и увеличиваем счетчик k на 1:

t = t -> Next; k++;

6. Конец цикла.

139

15.4.5. Алгоритм удаления элемента в списке по ключу

Удалить из списка элемент, информационная часть (ключ) которого совпадает со значением, введенным с клавиатуры.

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

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

Первый этап – поиск

1. Введем дополнительный указатель и присвоим ему значение NULL: Spis *key = NULL;

2. Введем с клавиатуры искомое значение i_p (ключ поиска).

3. Установим текущий указатель на начало списка:						Р
		t = begin;
						И
4. Начало цикла (выполнять пока t != NULL).
5. Сравниваем информационную часть текущего элемента с искомым.
5.1. Если они совпадают (t -> info = i p), тоУ(выводим на экран
сообщение об успехе);					Г
а) запоминаем адрес найденного элемента:
		key = t;			Б
б)
		завершаем поиск – досрочный выход из цикла (break);
5.2. Иначе, переставляем т ущий у з тель на следующий элемент:
		t = t -> Next;		а
				к
6. Конец цикла.			е
7. Контроль, если key = NULL , т.е. искомый элемент не найден, то
сообщаем о неудаче и э ап удаления не выполняем (return или exit) .
		и
Второй этап – удалениет
	ли
1. Ес		найденоэлемент для удаления, т.е. key != NULL, то удаляем
элемент из списка в зав симости от его местонахождения.
2. Ес		уда яемый элемент находится в начале списка, т.е. key = begin,
и
то создаем новый начальный элемент:
а) указатель начала списка переставляем на следующий (второй)
Б
элементб:
		begin = begin -> Next;

б) указателю Prev элемента, который был вторым, а теперь стал первым присваиваем значение NULL, т.е. предыдущего нет:

begin -> Prev = NULL;

3. Если удаляемый элемент в конце списка, т.е. key равен end, то:

а) указатель конца списка переставляем на предыдущий элемент, адрес которого в поле Prev последнего (end):

end = end -> Prev;

140

t = (Spis*) malloc(sizeof(Spis));

Адреса элементов:

б) обнуляем указатель на следующий (Next) элемент нового последнего элемента

end -> Next = NULL;

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

key->Prev key key->Next

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

	info				info	info
. . .	Prev				Prev	Prev
	Next				Next	Next		. . .
							Р
Порядковые	k-1				k	И
номера:
						k+1
						У
а) от k-го элемента с адресом key обратимся к предыдущему (k–1)-му
элементу, адрес которого key->Prev,				и в его поле ГNext [(key->Prev)->Next]
запишем адрес (k+1)-го элемента, значение которого key->Next:
					Б
( key -> Prev ) -> Next = key -> Next;
б) аналогично в поле Prev (k+1)-го элемента с адресом key->Next
запишем адрес (k-1)-го элемента:					а
( key -> Next ) -> Prevк= key -> Prev;
5. Освобождаем памя ь, заня ую удаленным элементом free(key);
			е
15.4.6. Алгоритм вс авки элемента в список						после элемента с
указанным ключом		т
Вставить в с с	элемент после элемента, значение информационной
	ок
пи
л

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

Этап второй – вставка

1. Захватываем память под новый элемент

2. Формируем информационную часть: scanf(“%d”, &t -> info);

3. Связываем новый элемент с предыдущим t -> Prev = key;

4. Связываем новый элемент со следующим t -> Next = key -> Next;

141