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

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

Формированиеочереди

Формирование очереди состоит из двух этапов: создание первого элемента, добавление нового элемента в конец очереди.

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

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

1. 
   ввести информацию для первого элемента (целое число i);
   
2. 
   захватить память, используя текущий указатель:
   

t = (Spis*) malloc(sizeof(Spis)); или t = new Spis;

в результате формируется конкретный адрес (А1) для первого элемента;

3. 
   сформировать информационную часть: t -> info = i; (обозначим i1 )
   
4. 
   в адресную часть занести NULL:
   

t -> Next = NULL;

5. 
   указателям на начало и конец очереди присвоить значение t: begin = end = t;
   

На этом этапе получим следующее:


Next= NULL

begin

Добавлениеэлементавочередь

Рассмотрим алгоритм добавления только для второго элемента.

1. 
   Ввод информации для текущего (второго) элемента – значение i.
   
2. 
   Захватываем память под текущий элемент:
   

t = (Spis*) malloc (sizeof(Spis)); или t = new Spis;

3. 
   Формируем информационную часть (обозначим i2): t -> info = i;
   

4. 
   В адресную часть созданного элемента (текущего) заносим NULL,
   

т.к. этот элемент становится последним: t -> Next = NULL;

5. 
   Элемент добавляется в конец очереди, поэтому в адресную часть бывшего последнего элемента endзаносим адрес созданного:
   

end -> Next = t;

бывший последний элемент становится предпоследним.

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

В результате получим

Next= NULL
begin
Для добавления в очередь любого количества элементов организуется цикл, включающий пункты 1– 6 рассмотренного алгоритма. Завершение цикла реализуется в зависимости от поставленной задачи.

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

void Create(Spis **begin, Spis **end) { Spis *t = (Spis*) malloc(sizeof(Spis)); printf(“\n Input Info ”);

scanf(“%d”, &t -> info); t -> Next = NULL;

if(*begin == NULL) // Формирование первого элемента

*begin = *end = t;

else {

}

}
(*end) -> Next = t; // Добавление в конец

*end = t;

Участок программы с обращением к функции Create для добавление необходимого количества элементов в очередь может иметь следующий вид:

…

Spis *begin = NULL, *end; int repeat = 1;

while(repeat) { // repeat=1 – продолжение ввода данных

Create(&begin, &end);

printf(“ Stop - 0 ”); // repeat=0 – конец ввода данных

scanf(“%d”, &repeat);

}

…