АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Представление очереди в виде списка

Прочитайте:
  1. Iii. Представление
  2. Все препараты списка Б, кроме препаратов отпускаемых без рецепта
  3. Все препараты списка Б, кроме препаратов отпускаемых без рецепта
  4. ИЗОБРАЗИТЕЛЬНОЕ ПРЕДСТАВЛЕНИЕ СТРУКТУРЫ ТРЕХ ВЕРХНИХ ШЕЙНЫХ ПОЗВОНКОВ
  5. Общее представление об обмене жиров. Регуляция липидного обмена.
  6. Представление информации
  7. Представление о диагнозе
  8. ПРЕДСТАВЛЕНИЕ О ДИАГНОЗЕ И ДИФФЕРЕНЦИАЛЬНОМ ДИАГНОЗЕ
  9. Представление о сахарном диабете типов I и II
  10. Представление об экономике до меркантилизма.

Можно хранить очередь в виде списка с указателями начала и конца. Операции реализуются методами обработки списков (раздел 2). Чтобы не программировать отдельным вариантом случай включения элемента в пустую очередь, можно хранить указатель начала не в виде скалярной переменной, а в поле ссылки специального фиктивного элемента в начале списка (его поле информации не используется). У пустой очереди указатель конца ссылается на этот фиктивный элемент (рис. 3.4). Можно использовать кольцевой список.

 

 

 

Рис. 3.4. Очередь в виде списка с фиктивным элементом

 

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

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

Рассмотрим описание данных и алгоритмы типовых операций для представления очереди списком, как на рис. 3.4.

 

Пример 3.5. Описание данных для представления очереди в виде списка:

struct el_och /* Тип элемента списка */

{ Тип-элемента inf; /* Информация */

struct el_och *sled; /* Ссылка на следующий элемент */

};

struct el_och f; /* Фиктивный начальный элемент */

struct el_och *uk; /* Указатель конца очереди */

Пример 3.6. Инициализация (создание) пустой очереди:

f.sled = NULL; /* Указатель начала очереди */

uk = &f; /* Указатель конца очереди */

Пример 3.7. Исключение из очереди элемента и присваивание его переменной x (обозначим эту операцию Очередь ==> x):

Тип-элемента x; /* Значение исключенного элемента */

struct el_och *i; /* Указатель исключенного элемента */

...

if (f.sled!= NULL) /* В очереди есть элементы */

{ x = f.sled->inf; /* Запоминание значения */

i = f.sled;

f.sled = f.sled->sled; /* Исключение элемента */

free (i); /* Освобождение памяти */

if (f.sled == NULL) uk = &f; /* Очередь стала пустой */

}

else... /* Очередь пуста */

Пример 3.8. Включение в очередь элемента равного x (обозначим эту операцию Очередь <== x):

Тип-элемента x; /* Включаемое значение */

struct el_och *i; /* Указатель включаемого элемента */

...

i = malloc (sizeof(struct el_och)); /* Получение памяти */

if (i!= NULL) /* Есть место */

{ i->inf = x; /* Запись информации */

i->sled = NULL; /* Запись ссылки */

uk.sled = i; /* Соединить *i с концом очереди */

uk = i; /* Новый указатель конца */

} else... /* Переполнение очереди */

Стек

Стек (stack) - это упорядоченная последовательность элементов, в которой выполняются операции включения и исключения элемента по принципу LIFO (Last-In-First-Out) - "последним пришел - первым ушел", т. е. включение и исключение всегда происходят в одном конце (рис. 3.5). Этот конец называют верхом, противоположный - дном стека. Другие названия стека: магазин (по аналогии с магазином пистолета или автомата), очередь типа LIFO.

 

  S[1]     S[2]   …   S[k]     ¾¾¾® ¾¾¾
  Дно       Верх     Включение и исключение элементов

Рис. 3.5. Стек

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

Назовем некоторые из многочисленных применений стека.

1. Переупорядочивание данных для обработки в порядке, отличающемся от порядка поступления.

2. Запоминание подзадач некоторой задачи с последующим решением подзадач в порядке, обратном порядку их возникновения (см. алгоритм обхода дерева в глубину).

3. Области локальных данных (включая параметры и адреса возврата) вложенных вызовов подпрограмм.

4. Области локальных данных вложенных блоков программы.

5. Трансляция скобочных структур: выражений, вложенных ветвлений, циклов, блоков и всей программы (см. раздел 7).

6. ЭВМ и микрокалькуляторы с безадресной магазинной памятью.

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

Типовые операции над стеком:

1. Инициализация (создание, подготовка к работе);

2. Вталкивание (включение) элемента - PUSH;

3. Выталкивание (исключение) элемента - POP;

4. Проверка пустоты стека;

5. Проверка переполнения стека;

6. Доступ к вершине (получение / изменение значения последнего поступившего элемента).


Дата добавления: 2015-09-27 | Просмотры: 427 | Нарушение авторских прав







При использовании материала ссылка на сайт medlec.org обязательна! (0.004 сек.)