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


 

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

29076. Филиалы и представительства юридического лица 25 KB
  Филиалы и представительства юридического лица Представительством является обособленное подразделение юридического лица расположенное вне места его нахождения которое представляет интересы юридического лица и осуществляет их защиту. Филиалом является обособленное подразделение юридического лица расположенное вне места его нахождения и осуществляющее все его функции или их часть в том числе функции представительства. Представительства и филиалы должны быть указаны в учредительных документах создавшего их юридического лица.
29077. Зависимые и дочерние хозяйственные общества 27 KB
  Зависимые и дочерние хозяйственные общества Дочернее хозяйственное общество если другое основное хозяйственное общество или товарищество в силу преобладающего участия в его уставном капитале либо в соответствии с заключенным между ними договором либо иным образом имеет возможность определять решения принимаемые таким обществом. Дочернее общество не отвечает по долгам основного общества товарищества. В случае несостоятельности банкротства дочернего общества по вине основного общества товарищества последнее несет субсидиарную...
29078. Создание юридических Лиц 31 KB
  лица организационное единство самостоятельная имущественная ответственность выступать истцом в суде выступать в обороте от своего имени имущественная обособленность государственная регистрация Способы образования юридических лиц: 1 распорядительный порядок юридическое лицо возникает на основе одного лишь распоряжения учредителя а специальной государственной регистрации организации не требуется. 51 ГК в современной России такой порядок возникновения юридических лиц не применим; 2 нормативноявочный порядок для образования...
29079. Реорганизация юридических лиц. Правовые последствия 39.5 KB
  Правовые последствия Реорганизация юридического лица слияние присоединение разделение выделение преобразование может быть осуществлена по решению его учредителей участников либо органа юридического лица уполномоченного на то учредительными документами. При присоединении юридического лица к другому юридическому лицу к последнему переходят права и обязанности присоединенного юридического лица в соответствии с передаточным актом. При разделении юридического лица его права и обязанности переходят к вновь возникшим юридическим лицам в...
29080. Ликвидация юридических лиц. Правовые последствия 29 KB
  Правовые последствия Ликвидация юридического лица влечет его прекращение без перехода прав и обязанностей в порядке правопреемства к другим лицам за исключением случаев предусмотренных федеральным законом. Юридическое лицо может быть ликвидировано: по решению его учредителей участников либо органа юридического лица; по решению. Виды ликвидации: добровольное принудительная банкротство Порядок ликвидации юридического лица Ликвидационная комиссия помещает в органах печати в которых публикуются данные о государственной регистрации...
29081. Объекты гражданского права и их классификация. Общая характеристика источников правового регулирования 35 KB
  Объекты гражданского права и их классификация. Общая характеристика источников правового регулирования. К объектам гражданских прав относятся вещи включая деньги и ценные бумаги иное имущество в том числе имущественные права; работы и услуги; охраняемые результаты интеллектуальной деятельности и приравненные к ним средства индивидуализации интеллектуальная собственность; нематериальные блага. Объекты гражданских прав могут свободно отчуждаться или переходить от одного лица к другому в порядке универсального правопреемства...
29082. Вещи как объект гражданского права и их классификация. Особенности применения классификации вещей в различных институтах гражданского права 26.5 KB
  Особенности применения классификации вещей в различных институтах гражданского права. Классификации вещей: 1.
29083. Ценные бумаги как объекты гражданского права и их классификация. Характеристика источников правового регулирования 31 KB
  Ценные бумаги как объекты гражданского права и их классификация. Характеристика источников правового регулирования Ценной бумагой является документ удостоверяющий с соблюдением установленной формы и обязательных реквизитов имущественные права осуществление или передача которых возможны только при его предъявлении. Признаки: Письменность Легальность субъекта права Предъявление Абстрактность предъявляемого К ценным бумагам относятся: облигация вексель чек депозитный и сберегательный сертификаты банковская сберегательная книжка на...
29084. Интеллектуальная собственность как объект гражданского права. Интеллектуальные права и их виды. Характеристика источников правового регулирования 23 KB
  Интеллектуальные права и их виды. Виды интеллектуальных прав: авторское право отношения возникающие в связи с созданием и использованием произведений науки литературы и искусства смежные права исключительное право музыкантовисполнителей изготовителей фонограмм организаций эфирного вещания патентное право порядок охраны изобретений полезных моделей промышленных образцов Только обладатель интеллектуальной собственности и в первую очередь автор располагает исключительными правами на ее использование а так же то что никакое...