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


 

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

44312. Влияние новых видов заквасок на качество ржано-пшеничного хлеба 6.78 MB
  Управление процессом приготовления закваски:. Регулирование температуры выведения закваски. Регулирование влажности закваски Регулирование соотношения выброженной закваски и питательной смеси.
44315. Высшая мера наказания в Советской России и Российской Федерации 431.5 KB
  Происхождение понятие и эволюция смертной казни в России с древнейших времен до XVIII века. Происхождение и понятие смертной казни Смертная казнь в Российской Федерации Среди множества проблем активно обсуждаемых сегодня в нашем обществе стоит вопрос о высшей мере наказания смертной...
44316. Разработка автоматизированной информационной системы учета основных средств 6.72 MB
  Основной особенностью системы 1С: Предприятие является её конфигурируемость. Собственно система 1С: Предприятие представляет собой совокупность механизмов, предназначенных для манипулирования различными типами объектов предметной области.
44317. Особенности технологического процесса получения керамики из продукта химического диспергирования сплава Al-Si (12%масс.) 9.97 MB
  Другой проблемой является создание мембран и фильтрующих керамических элементов с многослойной структурой с высокими прочностными свойствами. Одним из решений этой проблемы может стать использование нанокристаллических порошков, в процессе спекания которых, происходит формирование особых многозеренных нанокристаллических структур с высокой прочностью связи на границах зерен
44319. Автоматизация бизнес-процессов телефонного маркетинга 5.04 MB
  Необходимо понимать разницу между компьютерами и информационными системами. Компьютеры, оснащенные специализированными программными средствами, являются технической базой и инструментом для информационных систем. Информационная система немыслима без определения ее миссии, задач, архитектуры, инфраструктуры, конфигурации, средств телекоммуникаций и персонала, взаимодействующего с компьютерами
44320. Методические рекомендации. Социология 237.5 KB
  Подготовка выпускной квалификационной работы студентами позволяет преподавателям выявить уровень освоения методики проведения экспериментальной работы во время прохождения практик; осуществить контроль за качеством профессиональной подготовки студентов по специализации