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


 

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

48759. Полный курс высшей математики 3.49 MB
  Матрицей размера mn где m число строк n число столбцов называется таблица чисел расположенных в определенном порядке. Если число столбцов матрицы равно числу строк m=n то матрица называется квадратной. Матрица вида: = E называется единичной матрицей. Если mn = nm то матрица называется симметрической.
48760. Создание базы данных с помощью СУБД Microsoft Access 1.68 MB
  Цель курсовой работы – дать представление о современных информационных технологиях обработки данных. Задачей работы является развитие практических навыков в разработке базы данных и работы с системой управления базами данных (СУБД) MS Access.
48762. Вибір марки кабелю та розрахунок регенераційної ділянки в залежності від енергетичних та часових показників 308 KB
  Розрахунок максимальної довжини регенераційної дільниці за загасанням оптичного сигналу в кабелі на довжині регенераційної дільниці Якщо ми вибрали з таблиці максимальне допустиме значення загасання оптичного сигналу на регенераційній ділянці для вказаної системи передачі mx РД та загасання кілометричне для оптичного волокна для вибраної довжини хвилі α з таблиць 5. де: mx РД – загасання вибране з вище наведених таблиць α – коефіцієнт загасання загасання ОВ довжиною в 1 км для вибраного типу кабелю та...
48763. Задача о 8 ферзях 142.5 KB
  Задача состоит в нахождении всевозможных комбинаций расстановки восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого
48764. Темпи зростання та порівняння заробітної плати в Україні та інших країнах світу 537 KB
  З оплатою праці пов’язане розширення ємності внутрішнього ринку для стимулювання вітчизняних товаровиробників збільшення заощаджень населення як важливого джерела інвестицій в економічний розвиток. Нарешті необхідність належної збалансованості економічних інтересів учасників виробництва потребує збільшення частки оплати праці у структурі суспільного продукту. Отже для розвитку економіки збільшення інвестицій необхідне зростання рівня оплати праці.
48765. Поиск неисправностей 2.14 MB
  Методика поиска неисправностей и обозначение различных вариантов поиска Анализ неисправности на структурном уровне По структурной схеме СВ устанавливаем вероятный неисправный блок. Согласно внешним признакам проявления неисправности очевидно что неисправен может быть либо сам ПОУ СВ либо блок ВчУ структурный уровень так как только эти устройства участвуют в записи информации с ПОУ СВ на ВчУ. Анализ неисправности на функциональном уровне По функциональной схеме из альбома схем к курсу занятий по теме СВ устанавливаем вероятные...