36221

Очередь. Работа с динамической очередью

Доклад

Информатика, кибернетика и программирование

Например: Работа с очередью Для создания очереди и работы с ней необходимо иметь как минимум два указателя: на начало очереди возьмем идентификатор BegQ; на конец очереди возьмем идентификатор EndQ. Установка указателей BegQ и EndQ на созданный первый элемент: Удаление элемента очереди 1. Перестановка указателя начала очереди BegQ на следующий элемент используя значение поля Link которое хранится в первом элементе. После этого освобождается память начального...

Русский

2013-09-21

246 KB

1 чел.

Очередь. Работа с динамической очередью

Очередь – структура данных, для которой разрешены только два действия: добавление элемента в конец  (хвост) очереди и удаление элемента из начала (головы) очереди.

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

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

Правило последовательности описаний в Turbo Pascal требует, чтобы каждый идентификатор был описан, прежде чем он будет использоваться для других объявлений. Однако для создания динамического списка такой порядок невозможен. Поэтому для описания типов элементов динамических структур данных сделано исключение. Тип указателя на элемент динамической структуры данных может и должен быть описан перед описанием типа этого элемента.

Например:

Type

Yk  :=^TElem ;

TElem = record

Inf  : integer;

Link : Yk

end;

Работа с очередью

Для создания очереди и работы с ней необходимо иметь как минимум два указателя:

• на начало очереди (возьмем идентификатор BegQ);

• на конец очереди (возьмем идентификатор EndQ).

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

Создание очереди

1. Исходное состояние:

2. Выделение памяти под первый элемент очереди:


3. Занесение информации в первый элемент

4. Установка указателей BegQ и EndQ на созданный первый элемент:

Удаление элемента очереди

1. Исходное состояние:

2. Печать информации из удаляемого элемента и установка на него вспомогательного указателя P:

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


BegQ:= nil;

EndQ:= nil;

P

nil

EndQ

BegQ

nil

nil

nil

P

nil

EndQ

nil

BegQ

New (p);

Int

Link

     ?

?

nil

P

nil

EndQ

nil

BegQ

p^.Int:= 3;

p^.Link:= nil;

Int

Link

     3

nil

BegQ

EndQ

Int

Link

     3

nil

BegQ:= p;

EndQ:= p;

BegQ

2

4

3

EndQ

Очередь, в которой содержатся элементы (2, 4 и 3) и указатель Р, значение которого пока неопределенно.

P

?

печать

BegQ

2

4

3

EndQ

Р

Writeln ( BegQ^.inf);

Р := ( BegQ^.Link);  { это делается

для того, чтобы впоследствии можно было освободить память}

2

4

10

EndQ

Р

BegQ := BegQ^.Link);

Dispose (Р); {освобождение памяти}

BegQ


 

А также другие работы, которые могут Вас заинтересовать

82020. Деятельность интернет-подразделения в организации ООО “АСК-2” 221.77 KB
  Целью дипломной работы является создание и продвижение проекта, изучение специфики и особенности интернет-бизнеса, основные проблемы в данной сфере, разработка интернет-подразделения в компании и оценка экономической целесообразности проекта.
82021. Изображение социальной манипуляции в романе М. Е. Салтыкова-Щедрина «Господа Головлевы» 274.58 KB
  Целью нашей работы, прежде всего, является выявление социальных манипуляций среди персонажей романа «Господа Головлевы». На примере романа осуществляется попытка показать, как в литературном произведении осуществился процесс манипуляции, какими возможностями его изображения обладает художественный текст.
82022. ВИДЫ КОНТРОЛЯ И ДВИЖЕНИЯ ФИНАНСОВ 124.21 KB
  В данной дипломной работе представлено основные виды регламентирующих документов, федеральных законов и форм по управлению финансовом потоком во 2-м отряде федеральной противопожарной службы Министерства Российской Федерации по делам гражданской обороны, чрезвычайным ситуациям и ликвидации последствий стихийных бедствий.
82023. Проектирование базы данных. Защита информации 429.13 KB
  Концептуальное (инфологическое) проектирование — построение семантической модели предметной области, то есть информационной модели наиболее высокого уровня абстракции. Такая модель создаётся без ориентации на какую-либо конкретную СУБД и модель данных.
82024. Основы работы в программе Excel. Построение Диаграмм и графиков с помощью Excel 1.69 MB
  Существует специальная область информатики, изучающая методы и средства создания и обработки изображений с помощью программно-аппаратных вычислительных комплексов, – компьютерная графика. Она охватывает все виды и формы представления изображений, доступных для восприятия человеком либо на экране монитора...
82025. Роль фельдшера в организации специфической профилактики инфекционных заболеваний у детей 148 KB
  Иммунопрофилактика инфекционных болезней – это система мероприятий, осуществляемых в целях предупреждения, ограничения распространения и ликвидации инфекционных болезней путем проведения профилактических прививок согласно Национальному календарю профилактических прививок...
82026. БУХГАЛТЕРСКИЙ УЧЕТ И АНАЛИЗ ОСНОВНЫХ СРЕДСТВ ОРГАНИЗАЦИИ 531.24 KB
  Основные средства играют большую роль в воспроизводственном процессе труда, так как они образуют производственно-техническую базу и определяют производственную мощь предприятия, именно поэтому тема дипломной работы является актуальной на сегодняшний день.
82027. Взаимосвязь межличностных отношений и учебной мотивации детей младшего школьного возраста 496.5 KB
  Теоретические основы взаимосвязи межличностных отношений и мотивации учебной деятельности младших школьников. Мотивация учебной деятельности младших школьников. Влияние межличностных отношений на мотивацию учебной деятельности младших школьников.
82028. Интернет-коммуникации в деятельности предприятия (на примере проекта «Инфодонск» (ИП Кузнецова Г. В.)) 4.81 MB
  Интернет объединил в себе интерактивный характер коммуникации, гипермедийную природу и возможность построения индивидуального взаимодействия. Глобальная компьютерная сеть является одновременно и новой средой общения, и рынком с десятками миллионов потенциальных клиентов, обладающих достаточно высоким уровнем дохода.