Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 32 из 67

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

Предположим, что очередь создана, т.е. begin не равен NULL (рекомендуется организовать проверку на равенствоNULLс соответствующей обработкой данной ситуации).

1. 
   Устанавливаем текущий указатель на начало очереди: t = begin;
   
2. 
   Обрабатываем информационную часть первого элемента очереди, например, выводим на экран.
   
3. 
   Указатель на начало очереди переставляем на следующий (2-й)
   

элемент

begin = begin->Next;

4. 
   Освобождаем память, захваченную под 1-й элемент: free(t);
   
5. 
   Выводим сообщение, например, «Элемент удален!».
   

Алгоритмыпросмотраочередииосвобожденияпамяти

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

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

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

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

info(i₁)

NULL

Next

info(i₂) Prev Next

info(i₃) Prev Next
. . .

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

struct Spis {

int info;

Spis *Prev, *Next;

} ;

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

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

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

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

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

info

Prev

Next

t

2. 
   Формируем первый элемент списка:
   

а) формируем информационную часть, например, вводя с клавиатуры: scanf(“%d”, &t -> info); или cin >> t -> info;

б) формируем адресные части (первоначально это NULL): t -> Prev = t -> Next = NULL;

в) указатели начала и конца списка устанавливаем на этот элемент: begin = end = t;

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

begin end

i

NULL

NULL

info Prev

Next