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


 

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

82281. Донаучные, ненаучные и вненаучные знания об обществе и культуре. Природа , общество и культура в социальном познании 36.36 KB
  Появление научного знания не отменило и не упразднило не сделало бесполезными другие формы знания. Каждой форме общественного сознания: науке философии мифологии политике религии и т. соответствуют специфические формы знания.
82282. Зарождение и формирование научных дисциплин социально- гуманитарного цикла. Социокультурная обусловленность дисциплинарной структуры научного знания 37.28 KB
  Проблема истории науки не была предметом специального рассмотрения ни философов ни ученых работавших в той или иной области научного знания и только в трудах первых позитивистов появляются попытки анализа генезиса науки и ее истории создается историография науки. Разработка истории науки началась только в XIX в. Признание истории науки как специальной научной дисциплины произошла только в 1892 г. когда во Франции была создана первая кафедра истории науки Одна из главных проблем характерных для истории науки понять объяснить как...
82283. Зависимость научных знаний от социального контекста: классическая, неклассическая и постклассическая наука 38.73 KB
  создавших принципиально новое по сравнению с античностью и средневековьем понимание мира и началась классическая наука ознаменовавшая генезис науки как таковой как целостного триединства т. Тот переворот который совершил в астрономии польский астроном Николай Коперник 1473-1543 имел огромное значение для развития науки и философии и их отделения друг от друга. характеризуется торжеством опытного экспериментального подхода к изучаемым явлениям: открытие кровообращения Гарвеем 1628 установление магнитных свойств Земли Гильбертом...
82285. Причины присоединения Казахстана к России. Последствия присоединения Казахстана к России 33.97 KB
  Последствия присоединения Казахстана к России В казахскорусских отношениях были заинтересованы обе стороны и Казахстан помощь в борьбе с джунгарами решение экономических проблем оживление торговли и Россия союзник в борьбе с сибирским ханом Кучумом; выход на рынки Средней Азии; обеспечение безопасности караванных маршрутов. над Казахстаном нависла наибольшая угроза потери независимости со стороны Джунгарского ханства это побудило казахских ханов искать помощи у России. Предметами обсуждения были: обмен пленными урегулирование...
82286. Политические партии и течения в период от февраля к октябрю 1917 года 39.16 KB
  Букейханов стал лидером партии Алаш его поддержали соратники: А. В апрелемае 1917 года прошли областные и уездные съезды партии Алаш где поднимались наиболее острые проблемы: запрещение переселения взаимоотношения с Китаем и Россией. Взаимодействие созданных главным образом под руководством участников Алаш казахских комитетов как органов национального самоуправления с коалиционными Советами после февральских событий привело к усилению недоверия и отчужденности в отношениях с входившими в них большевиками. Многие представители Алаш вошли в...
82287. Причины, характер и движущие силы революции 1916 г. в Казахстане. Основные очаги восстания 37.85 KB
  Основные очаги восстания Восстание охватило всю территорию Казахстана главными очагами восстания выступили: Тургайский Семиреченский и ЧуТаласский центры. Причины восстания стали следующие обстоятельства: усиление колониального гнета; изъятие земель; увеличение налогов и поборов; разжигание национальной розни; резко ухудшившееся положение народных масс; реквизиция скота и фуража у казахского населения. Локальными центрами восстания стали: СырДарьинская область Турар Рыскулов руководитель; Уральская область Сейткали Мендышев;...
82288. Развитие сельского хозяйства. Попытки реформирования в марте 1965 года 28.55 KB
  В марте 1965 года была разработана аграрная программа выхода сельского хозяйства из кризисной ситуации первой половины 1960х годов: 1 резкое увеличение государственных инвестиций для осуществления программ по комплексной механизации электрификации мелиорации работы направленные на улучшение свойств земель на повышение их производительности и химизации сельского хозяйства; 2 введение на 5 лет твердых и сравнительно низких планов заготовок колхозной продукции; 3 повышение закупочных цен на сельскохозяйственные культуры причем...
82289. Особенности установления советской власти в Казахстане 32.05 KB
  Советская власть в Казахстане устанавливалась неравномерно. Советская власть мирным путем была установлена в южных и северных районах Казахстана вооруженным путем в Оренбурге Семипалатинске Верном и других городах. В ноябре 1917 года атаман Дутов совершил контрреволюционный переворот и власть перешла Войсковому правительству таким же методом взяли бразды правления в свои руки Семиреченское войсковое правительство. 30 октября 1917 года была установлена советская власть в Перовске 1 ноября в результате ожесточенных боев в Ташкенте.