4289

Связные списки, стеки, очереди

Практическая работа

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

Связные списки, стеки и очереди Как и массивы, связные списки представляют собой универсальную структуру данных, широко используемую многими программистами. Однако, в отличие от массивов, связные списки не входят в состав стандартного языка...

Русский

2012-11-15

237 KB

124 чел.

Связные списки, стеки и очереди

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

На основе связных списков можно легко организовать стеки и очереди - еще две простые, но эффективные структуры данных. Несмотря на то, что они, на первый взгляд, не имеют ничего общего со связными списками, их можно написать на базе односвязных списков. Начнем наше рассмотрение со связного списка и операций, которые такой список должен поддерживать.

Односвязные списки

По своей сути связный список (linked list) представляет собой цепочку элементов или объектов с некоторыми описаниями (обычно называемых узлами). При этом каждый элемент содержит указатель, указывающий на следующий элемент в списке. Такая структура данных называется односвязным списком (singly linked list) - каждый элемент имеет только одну ссылку или указатель на следующий элемент. Сам список начинается с первого узла, от которого путем последовательных переходов по ссылкам можно обойти все остальные узлы. Обратите внимание, что определение связного списка отличается от определения массива, для которого следующий элемент находится в памяти рядом с предыдущим. В связном списке элементы могут быть разбросаны по разным местам памяти, а их порядок определяется ссылками.

  Рис.1 Односвязаный список.

А каким образом помечается конец списка? Самый простой способ - установить указатель ссылки в последнем элементе списка равным nil. Это будет означать, что следующий элемент отсутствует. Второй способ - ввести специальный узел, называемый конечным узлом, и установить так, чтобы ссылка последнего узла указывала на этот узел. И третий способ - установить так, чтобы ссылка последнего узла указывала на первый элемент. В этом случае мы получим круговой связный список.

Рассмотрим, чем же связный список отличается от массива. Первое, что нужно отметить, - размер связного списка можно не устанавливать. Для массива нам всегда было нужно заранее знать, сколько элементов будет в нем храниться (чтобы можно было статически распределить непрерывный участок памяти) или разработать некоторую схему расширения массива (или его сокращения), чтобы массив мог разместить большее (или меньшее) количество элементов. В связном списке каждый узел является отдельным элементом. И в простых случаях распределение памяти под каждый узел выполняется отдельно. При необходимости добавления в список нового элемента под него распределяется память, а затем на него устанавливается ссылка из списка. При удалении узла нужно всего лишь удалить ссылки на него и освободить занимаемую им память.

Если связный список настолько удобен, почему бы его не использовать вместо массива? В чем состоят его недостатки? Первый, хотя и незначительный, состоит в том, что каждый элемент связного списка должен содержать указатель на следующий элемент. Таким образом, чтобы вставить элемент в список, его реальный размер необходимо увеличить на размер указателя (в настоящее время это 4 байта).

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

Самым большим недостатком связного списка является получение доступа к некоторому элементу п. В массиве доступ к n-ному элементу требует проведения простых арифметических вычислений, поскольку все элементы содержатся в одном непрерывном блоке памяти. С другой стороны, в списке получение доступа к элементу п требует прохождения по ссылкам от первого элемента до n-ного. Другого метода доступа не существует, мы всегда должны следовать по ссылкам.

Узлы связного списка

Перед началом описания операций со связным списком давайте рассмотрим, как каждый узел списка будет представляться в памяти. Знание структуры узла позволит нам более детально рассматривать основные операции со связными списком. Структура узла списка выглядит следующим образом:

type

PElem = ^Elem;  {Указатель на элемент списка}

Elem = record     {Элемент списка - запись}

 Data : TdataType; {Данные, хранящиеся в узле списка (тип - любой) }

   Next : PElem;  {Указатель на следующий элемент списка}

end;

Тип PElem представляет собой указатель на запись Elem, поле Next которой содержит ссылку на точно такой же узел, а поле Data - сами данные. В приведенном примере тип данных узла задан как TdataType, и должен быть описан пользователем заранее (например, для хранения в списке целых чисел можно записать Type TdataType=Integer). Для перехода по ссылке на следующий элемент нужно написать примерно следующий код:

var

NextNode, CurrentNode : PElem; {где CurrentNode – указатель на текущий элемент,

NextNode – указатель на следующий элемент}

begin

…..

NextNode : = CurrentNode^.Next;

Обращения к данным, находящимся в узле списка с адресом CurrentNode, будет записано так:   CurrentNode^.Data:=5; или writeln(CurrentNode^.Data);

 

Создание односвязного списка

В самом простом случае первый узел в связном списке описывает весь список. Первый узел иногда называют головой списка. В программе очень важно не потерять адрес начала списка, т.к. восстановить после этого список невозможно (узлы списка располагаются в памяти хаотично, образуя логическую цепочку  через поле Next). В программе, использующей связные списки, необходимо описать глобальную переменную – указатель на начало списка:

Var  HeadList : PElem;

Если HeadList содержит nil, списка еще нет. Таким образом, это начальное значение связного списка. Для определенности, в начале программы указателю на начало списка необходимо присвоить значение nil.

HeadList:=nil {инициализация связного списка}

Вставка и удаление элементов в односвязном списке

Каким образом можно вставить новый элемент в связный список? Или удалить? Оказывается, что для выполнения этих операций требуется выполнить небольшую работу с указателями. Для односвязного списка существует только один вариант вставки - после заданного элемента списка. Нужно установить ссылки так, чтобы указатель Next нашего нового узла указывал на узел после заданного, а указатель Next заданного узла - на наш новый узел. В коде это выглядит следующим образом:

var

GivenNode, NewNode : PElem; { GivenNode – указатель на заданный узел}

begin

New(NewNode);

Newnode^.Data:=15 ; {задаем значение поля Data}

NewNode ^. Next :=  GivenNode ^. Next ;

GivenNode ^. Next : = NewNode;

Рис.2 Вставка нового узла в односвязный список.

Аналогично, для удаления простейшим вариантом является удаление элемента, находящегося после заданного узла (GivenNode). В этом случае мы устанавливаем, чтобы указатель Next заданного узла указывал на узел, расположенный после удаляемого. После этого удаляемый узел уже выделен из списка и может быть освобожден. В коде это выглядит следующим образом:

var

GivenNode, NodeToGo : PElem

begin

………………

 NodeToGo := GivenNode^.Next;

 GivenNode^.Next := NodeToGo^.Next; {b}

 Dispose(NodeToGo); {c}

Указатель NodeToGo – используется как вспомогательный.

Рис.3 Удаление узла из односвязного списка

Тем не менее, для обеих операции существует специальный случай: вставка перед первым элементом списка (т.е. новый элемент становиться первым) и удаление первого элемента списка (т.е. первым становится другой элемент). Поскольку в наших рассуждениях первый элемент считается определяющим узлом всего списка, код для этих случаев нужно написать отдельно. Вставка перед первым узлом HeadList будет выглядеть следующим образом:

var

HeadList ,  NewNode : PElem;

begin

 ………….

 New(NewNode); {выделяем память под новый узел, указатель - NewNode}

NewNode^.Data:=X {заполняем поле Data для нового узла  значением Х}

NewNode^.Next : = HeadList; {связываем новый узел с первым элементом – головой списка}

HeadList: = NewNode ; {список начинается с нового элемента}

………….

а удаление будет выглядеть так:

var

HeadList, TempNode : PElem;

begin

…….

TempNode:=HeadList; {запоминаем адрес первого элемента}

HeadList:= HeadList^.Next; {начало списка переставляем на следующий элемент}

Dispose(TempNode); {освобождаем память, занимаемую бывшим первым элементом }

……………………

Обратите внимание, что код вставки элемента будет работать даже в случае, когда исходный список пуст, т.е. содержит nil (HeadList = nil, после вставки будет создан первый и единственный элемент списка), а код удаления элемента правильно установит указатель на начало связного списка HeadList в nil, если происходит удаление последнего узла.

Прохождение связного списка

Прохождение связного списка также не представляет никаких трудностей. Фактически мы переходим от узла к узлу по указателям Next до достижения указателя nil, который свидетельствует об окончании списка. Вывод на экран содержимого списка, заданного указателем на начало HeadList,  будет выглядеть следующим образом

var

HeadList, TempNode : PElem;

begin

…….

TempNode:=HeadList; {Для прохождения по списку нельзя использовать адрес первого элемента HeadList, т.к. потеряем весь список}

While TempNode <> nil do  { пока список не пустой}

 begin

 Writeln(TempNode^.Data); {печатаем значение в текущем узле}

 TempNode:= TempNode^.Next; {переставляем указатель на следующий элемент}

 end;

 …….

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

var

HeadList, TempNode : PElem;

begin

…….

While HeadList <> nil do  { Пока список не пустой}

 begin

 TempNode:=HeadList {запоминаем адрес первого элемента }

 HeadList:= HeadList ^.Next; {переставляем указатель начала списка  на следующий элемент}

 Dispose(TempNode); {удаляем предыдущий элемент }

 end;

 …….

Обратите внимание, что по окончании цикла While указатель на начало списка  HeadList будет иметь значение nil. При работе со связными списками по завершении программы или по окончании работы со списком необходимо провести очистку, и освободить динамическую память, занимаемую такой  структурой.

Теперь, когда мы научились проходить по узлам связного списка, давайте вернемся к вопросу, который, наверное, появился у вас пару абзацев назад. А что если нам нужно вставить узел перед заданным узлом? Как это сделать? Единственным решением такой задачи для односвязного списка является прохождение списка и поиск узла, перед которым мы должны вставить новый узел. При прохождении будут использоваться две переменных: одна будет указывать на текущий (This), а вторая на предыдущий узел (Pre). Когда будет найден заданный узел, у нас будет указатель на предыдущий узел, что позволит использовать алгоритм вставки после заданного узла.  Вставка нового узла будет происходить между узлами Pre и This. В коде это выглядит следующим образом:

var

HeadList ,  NewNode, Pre,This : PElem;

Found:Boolean; X, Xnew:integer;

begin

………….

Pre:=nil;

This:=HeadList;

Found:=False; {Место вставки еще не найдено}

  While (This<>nil) and not Found do {Второе условие – признак окончания поиска при обнаружении позиции вставки, например, This^.data=X. В этом случае вставка нового элемента будет сделана перед элементом со значением, равным Х.}

 Begin

 Pre:=This;

 Found:= This^.data=X;

 This:=This^.next;

End;

If  Found then  

    Begin

{Если позиция вставки найдена, то добавляем новый узел между Pre и This}

 New(NewNode); {выделяем память под новый узел, указатель - NewNode}

NewNode^.Data:=Xnew {заполняем поле Data для нового узла  значением Хnew}

Pre^.next:=NewNode; {связываем предыдущий элемент Pre  с новым NewNode}

NewNode^.next:=This; {связываем новый элемент NewNode с текущим This }

  End;

……

Рис.4 Вставка нового элемента перед заданным узлом.

Работа алгоритма продемонстрирована на Рис.4. Данная вставка не работает, если добавление должно происходить перед первым узлом списка. Для этого необходимо предусмотреть дополнительный код, проверяющий условие This=HeadList или Pre=nil. В этом случае необходимо изменить значение адреса первого узла списка. Например, так

……….

New(NewNode); {выделяем память под новый узел, указатель - NewNode}

NewNode^.Data:=Xnew {заполняем поле Data для нового узла  значением Хnew}

 NewNode^.next:= HeadList;{связываем новый элемент NewNode с первым HeadList}

HeadList:=NewNode; {связываем первый элемент HeadList с новым NewNode}

……….

Создание упорядоченного списка.

Для получения упорядоченного списка вовсе не обязательно сортировать его после построения, достаточно добавлять новый элемент таким образом, чтобы список все время оставался упорядоченным.  Такой метод позволяет иметь упорядоченный список на каждом шаге. Ключом, по которому производиться упорядочивание будем считать значение информационного поля Data. Структура узла списка выглядит следующим образом:

type

PElem = ^Elem;  

Elem = record     

 Data : Integer; {Данные, хранящиеся в узле списка –целое число}

   Next : PElem;  

end;

При добавлении нового элемента в такой список необходимо предусмотреть следующие варианты:

  1.  добавление в пустой список;
  2.  добавление в начало списка, когда новый элемент меньше существующего первого;
  3.  добавление в середину существующего списка на подходящее место (частный случай этой ситуации – добавление в конец списка).

В третьем случае требуется сначала определить место, куда следует вставить новый элемент. Для этого будем двигаться по списку до тех пор, пола либо не найдется элемент, больший или равный вставляемому, либо не будет достигнут конец списка. Воспользуемся дополнительным указателем на предыдущий элемент – Pre. Все это учтено в процедуре Insert. Параметры процедуры P -  указатель на начало списка, e - значение нового элемента.

procedure Insert(var p: PElem; e: Integer);

// p - указатель на список, e - значение нового элемента

var  Temp,Pre,This: PElem;

Found: Boolean; // признак того, что место для вставки найдено

begin

if p=nil then

begin // список пуст, создание первого элемента, вариант 1.

new(p);

with p^ do begin

Data:=e;

Next:=Nil;

end;

end

else   

begin // вставка элемента в список, варианты 2, 3

     if e<=p^.Data then

begin // вставка перед списком, вариант 2

 new(This);

with This^ do begin

  Data:=e; Next:=p

   end;

p:=This; // новое начало списка

end

else

begin // поиск места и вставка, начиная со второго элемента,  вариант 3

found:=false; // место не найдено

This:=p^.Next; // текущий элемент равен второму

Pre:=p; // предыдущий равен первому

while not found and (This<>Nil) do  // поиск места для вставки

if e<=This^.Data then

found:=true // место найдено

else

begin  // двигаемся дальше по списку, запоминая адрес

          // предыдущего элемента  в переменной Pre

Pre:=This; This:=This^.Next;

end;

// добавляем новый элемент со значение е между Pre и  This

new(Temp);

with Temp^ do begin

Data:=e; Next:=This;

end;

Pre^.Next:=Temp;

end

    end

end;

Процедура Insert корректно работает в случае, если новый элемент необходимо добавить в конец списка (при поиске  подходящего места по условию e<=This^.Data дошли до конца списка). При этом значение This=nil будет записано в поле Next последнего элемента.

Использование упорядоченного связного списка для частотного анализа данных

В качестве примера использования упорядоченного списка рассмотрим построение частотного распределения  целых чисел. Эта задача возникает при анализе данных, когда необходимо определить, сколько и какое число встретилось раз, т.е. определить  частоту появления каждого числа.

Решение заключается в следующем. Создадим список, который будет содержать числа. Если число встретилось первый раз, то оно заноситься в список. Если такое число уже есть в списке, то увеличивается счетчик появления этого числа. Поэтому внесем некоторые изменения в описание элемента списка Elem, добавив новое целочисленное поле cnt, которое будет являться счетчиком повторений. В основе алгоритма лежит процедура Add(), всегда вставляющая новый элемент в упорядоченный список. Однако теперь требуется дополнительная проверка на наличие в списке значения. В остальном процедура Add() аналогична процедуре Insert() описанной выше.

Рис.5 Блок-схема обработки значения при частотном анализе.

Листинг программы частотного анализа целых чисел.

program testsortlist;

 {$APPTYPE CONSOLE}

type

 PElem=^Elem;

 elem=record

     Data: integer; // значение

     Cnt:integer;  // число повторений данного значения

    next: pelem;

 end; {record}

var top: pelem; // указатель на начало частотного списка

   N:integer;

Procedure Lists(p:pelem); // процедура вывода списка на экран, p – указатель на начало

begin

 while p<>Nil do

begin  writeln(p^.Data,' - ',P^.cnt); p:=p^.next; end;

   writeln;

end;

Procedure Del(var p:pelem); // процедура удаления списка, p – указатель на начало

var g:pelem;

begin

     while p<>nil do

     begin  g:=p;  p:=p^.next;  dispose(g); end;

end;

Procedure add (var Head:pelem; X:integer);// добавление значения Х в список Head

var Pre,This:Pelem;

   Found:boolean;

Procedure Insert; { Процедура Insert вставляет новый элемент между Pre и This, учитывая случаи создания первого элемента и добавления в середину или конец  существующего}

var P:Pelem;

begin

   New(p);

   P^.Data:=X;

   P^.next:=This;

   P^.Cnt:=1;

    If pre= nil then

                     Head:=P //1-й элемент или добавление перед первым

                else

                    Pre^.next:=P; // середина или конец

end;

begin

  Pre:=Nil;

  This:=Head;

  Found:=False;

  While (This<>Nil) and not Found Do // Поиск подходящего места вставки

     if This.Data >= X then

                Found:=True // место найдено 

           else begin

                pre:=This;  // место не найдено, переходим к следующему элементу списка

                This:=This^.next;

                end;

  if not found then

                   Insert  // дошли до конца списка или список пуст

               else if This^.Data=X then // нашли место

                                      Inc(This^.Cnt) // значения равны – увеличиваем счетчик

                                   else

                                      Insert; // значение больше Х, вставка перед элементом This

end;

begin {Начало программы. Вводим и анализируем числа. Ввод числа 999 – признак окончания ввода значений }

  top:=Nil; {инициализациа списка}

  Repeat

     Write('Input N , (999-Exit) --> ');

      Readln(n);

     If N <> 999 then Add(top,N); {Добавление числа N в список Top}

  until n=999;

Lists(top); { Вывод частотного списка на экран}

Del(top);  {Удаление списка}

readln;

end.

Стеки

Еще одной известной и широко используемой структурой данных является стек. Стек представляет собой структуру, которая позволяет выполнять две основных операции: заталкивание для вставки элемента в стек и выталкивание с целью считывания данных из стека. Структура устроена таким образом, что операция выталкивания всегда возвращает элемент, вставленный в стек последним (самый “новый” элемент в стеке). Другими словами, элементы в стеке считываются в порядке, обратном порядку их записи в стек. Благодаря такому устройству стек известен как контейнер магазинного типа.

Рис.6 Операции заталкивания и выталкивания для стека

Написание кода стека не представляет никаких трудностей. Причем существуют два варианта реализации: первый - на основе односвязного списка, второй - на основе массива. Как и в случае со списками, будем считать, что записываться и считываться из стека будут целые числа. Рассмотрим организацию стека на базе связного списка.

В реализации стеков на основе односвязных списков операция заталкивания представляет собой вставку элемента в начало списка, а операция выталкивания - удаление элемента из начала списка и считывание его данных. Обе операции не зависят от количества элементов в списке, следовательно, их можно отнести к классу О(1).

Для работы со стеком необходимы следующие операции:

  1.  Инициализация стека, т.е. подготовка структуры.
  2.  Включение нового элемента в стек (заталкивание)
  3.  Проверка стека на пустоту.
  4.  Извлечение элемента из стека (выталкивание).

Реализовать работу стека можно в модуле, объявив в интерфейсной части минимальный набор процедур и функций:

 Procedure Push(var Top:PElem; N:integer);

Процедура Push добавляет новый элемент в стек. Параметры процедуры : Top – указатель на начало стека, N – значение нового элемента. Обратите внимание, что параметр Top является параметром-переменной, т.к. при добавлении нового элемента всегда будет меняться и адрес начала стека.

 Procedure Pop(var Top:PElem; var N:integer);

Процедура Pop извлекает из стека значение первого элемента через параметр-переменную N, удаляет первый элемент и переставляет указатель Top на следующий элемент. Параметры процедуры: Top – указатель на начало стека, N – передаваемое в программу значение первого элемента.

 Function IsEmpty(Top:PElem):Boolean

Функция IsEmpty возвращает значение true, если стек пуст (если указатель на начало стека пустой). Параметр функции: Top – указатель на начало стека.

Перед вызовом процедуры Pop пользователь должен проверить есть ли элементы в стеке с помощью функции IsEmpty. Попытка извлечения элемента из пустого стека вызовет ошибку. Приведем листинг модуля Steck. Инициализацию стека необходимо сделать в программе до использования процедур и функций из модуля.

Листинг модуля Steck

Unit Steck;

interface

type

PElem = ^Elem;  

Elem = record     

 Data : Integer;

   Next : PElem;  

end;

Procedure Push(var Top:PElem; N:integer);

Procedure Pop(var Top:PElem; var N:integer);

Function IsEmpty(Top:PElem):Boolean

implementation

Procedure Push(var Top:PElem; N:integer);

Var Temp:Pelem;

begin

new(Temp); // выделяем память под новый элемент

Temp^.Data:=N; // записываем значение N в новый элемент

Temp^.Next:=Top; // связываем новый элемент с первым

Top:=Temp;// новое начало стека – первый элемент указывает на новый

end;

Procedure Pop(var Top:PElem; var N:integer);

Var Temp:Pelem;

begin

 N:=Top^.Data; // считываем значение из первого элемента в N

 Temp:=Top; // запоминаем адрес первого элемента

 Top:=Top^.Next; // переставляем указатель на первый элемент на следующий

 Dispose(temp); // удаляем бывший первый элемент

end;

Function IsEmpty(Top:PElem):Boolean

begin

Result:=Top=nil; //

end;

end. {Steck}

Продемонстрируем использование стека из модуля Steck на примере решения следующей задачи – в текстовом файле записаны целые числа, распечатать на экране все числа в обратном порядке. Из условия задачи видно, что количество чисел в файле заранее  неизвестно, поэтому поместить их все в массив и распечатать содержимое массива обратном порядке проблематично (размер массива должен быть задан заранее). Прочитать текстовый файл в обратном порядке невозможно, так как для текстовых файлов определен только последовательный доступ к его элементам. Один из простых вариантов решения этой задачи будет последовательное чтение данных из файла и заталкивание их в стек, потом надо просто извлечь все данные из стека и вывести их на экран. Листинг программы приведен далее. Из модуля Steck в программе использованы процедуры и функции и описание указателя на элемент стека тип - PElem.

Листинг программы, использующей модуль Steck.

Program TestSteck;

 {$APPTYPE CONSOLE}

Uses SysUtils, Steck; // подключение модулей

Var   N:integer;

HeadSteck:PElem; // HeadSteck – указатель на первый элемент стека

 FileName:string; // имя файла с данными

 F:text; // файловая переменная

Count:integer; // счетчик считанных из файла чисел

begin

 HeadSteck:=nil; // инициализация стека, стек – пуст

repeat

 Write(‘Введите имя файла с данными’);

Readln(FileName);

until FileExists(FileName);  // цикл с вводом имени файла будет продолжаться до тех пор,

//пока не будет введено имя существующего файла

Assign(F,FileName); // связываем файловую переменную f с именем файла FileName

Reset(F); // открываем файл для чтения

Count:=0;

While not Eof(F) do

begin

 Read(F,N) ; // читаем из файла число в переменную N

 Inc(Count);

 Push(HeadSteck,N); // заталкиваем число N в стек

end;

Close(f);

Writeln(‘Всего считано и добавлено в стек ‘, Count, ‘ чисел);

While not IsEmpty(HeadStecK) do  // пока стек не пуст, будем извлекать данные и печатать

 begin

 Pop(HeadStecK,N);

 Writeln(N);

 end;

Readln;

end.

Очереди

Следующей широко известной  базовой структурой данных является очередь.  В то время как извлечение элементов из стека происходит в порядке, обратном тому, в котором они вносились, в очереди элементы выбираются в порядке их добавления. Таким образом, очередь относится к структурам типа "первый пришел, первый вышел" (FIFOfirst in, first out). С очередью связаны две основные операции: постановка в очередь (т.е. добавление нового элемента в очередь) и снятие с очереди (т.е. извлечение из нее самого старого элемента).

Иногда эти операции ошибочно называют заталкиванием и выталкиванием. Это абсолютно неверные термины для очереди. Ближе к истине будут слова включение и исключение.

Рис.7. Постановка в очередь и снятие с очереди

Как и стеки, очереди можно реализовать на основе односвязных списков или массивов. Тем не менее, в отличие от стеков, очень трудно добиться высокой эффективности реализации на основе массивов. Если в процессе работы очередь то очень длинная, то короткая, имеет смысл реализовать очередь с использованием динамической структуры.   К тому же организация очередей на базе связных списков очень проста. Поэтому рассмотрим построение очереди на базе односвязных списков. Фактически мы должны смоделировать обычную очередь в универмаге. С помощью списков это можно сделать очень легко, поскольку сами списки по своей сути являются очередями. Просто для моделирования очереди элементы должны добавляться с одной стороны и удаляться с другой. При использовании односвязного списка снятие с очереди будет выполняться с начала списка, а постановка в очередь - в конец списка. Очевидно, что  операции с очередью не зависят от количества элементов в ней, т.е. они принадлежат к классу О(1).

Для работы с очередью необходимы следующие операции:

  1.  Инициализация очереди, т.е. подготовка структуры.
  2.  Включение нового элемента в конец очереди.
  3.  Проверка очереди на пустоту.
  4.  Извлечение элемента из начала очереди.

При работе с очередью удобно хранить два указателя: указатель на начало очереди (голову) и указатель на последний элемент (хвост). Использование последнего указателя позволяет убрать последовательный перебор всех элементов из алгоритма добавления нового узла в конец очереди. Для определения очереди возьмем тип запись (Record) с именем Tqueue, содержащую в качестве полей два этих указателя (Head - начало, Tail - конец). В этом случае очередь будет характеризоваться только одним параметром.

Листинг динамической реализации очереди

type

PElem = ^Elem;  // описание указателя на элемент очереди

Elem = record     // описание элемента очереди

 Data : Integer;

  Next : PElem;  

end;

Tqueue =record // определение очереди

 Head,  // голова очереди

 Tail: Pelem; // хвост очереди

 end;

procedure InitQueue(var q:TQueue);        { инициализация очереди, указателю на начало очереди присвоить пустое значение}

begin

q.Head:=nil;

end;

function QueueIsEmpty(q:TQueue): Boolean; { проверка очереди на пустоту, очередь пуста, если указатель на начало равен nil}

begin

Result:=q.Head = nil;

end;

procedure InQueue(var q:TQueue; x:integer); // поставить в очередь

var P:Pelem;

begin

new(p); {создаем и заполняем  значениями новый элемент очереди}

 p^.Data:=x;

p^.next:=nil;

{Далее необходимо рассмотреть 2 ситуации:  

а) очередь пуста - добавление первого элемента очереди

б) очередь не пуста - добавление нового элемента в конец  }

 if QueueIsEmpty(q) then // очередь пуста – создаем первый элемент

 begin

  q^.Head:=p; q^.Tail:=p;

end

 else

 With q do begin

Tail^.next:=p; Tail:=p; { присоединяем новый элемент к концу очереди, присваиваем указателю на конец очереди новое значение}

end;

end;

function OutQueue(var q:TQueue):integer;    // взять из очереди

var P:Pelem;

begin

 With q do begin

 Result:=Head^.Data; // возвращаем значение поля Data  

 p:=Head;  // запоминаем адрес начала очереди

 Head:=Head^.Next; // переставляем начало очереди на следующий элемент

 Dispose(p);  // удаляем бывший первый элемент

 end;

end;

Функцию OutQueue (извлечь элемент из очереди) можно вызывать только в том случае, когда очередь не пустая. Поэтому перед извлечением очередного элемента необходимо проверять очередь на не пустоту, вызывая функцию not QueueIsEmpty.

Продемонстрируем использование очереди на решении следующей задачи. В текстовом файле записаны положительные и отрицательные числа. Вывести на экран сначала отрицательные, а затем положительные числа не изменив порядок их расположения. Выполнить данные действия необходимо за один проход по файлу.

С  использованием очереди данная задача решается очень просто. Читаем число из файла, если оно положительное, то добавляем число в очередь, иначе выводим его на экран. После чтения всех чисел из файла, отрицательные выведены на экран, а положительные находятся в очереди. После этого необходимо извлечь все положительные числа из очереди и вывести их на экран  

Листинг программы, использующей очередь.

Program ………..;

Type  ….{ описание типов для реализации очереди}

…….    

Var   N:integer;

HeadQueue: TQueue; // HeadQueue – указатели на очередь

 FileName:string; // имя файла с данными

 F:text; // файловая переменная

begin

 InitQueue(HeadQueue); // инициализация очереди

 Write(‘Введите имя файла с данными’);

Readln(FileName);

Assign(F,FileName); // связываем файловую переменную f с именем файла FileName

Reset(F); // открываем файл для чтения

While not Eof(F) do

begin 

 Read(F,N) ; // читаем из файла число в переменную N

 If N>=0 then InQueue(HeadQueue,N) // помещаем число N в очередь

   else Writeln(N); // иначе выводим на экран

end;

Close(f);

While not QueueIsEmpty(HeadQueue) do  // пока очередь не пуст, будем извлекать

// данные и печатать на экране

 begin

 Writeln(OutQueue(HeadQueue));

 end;

Readln;

end.


Задачи.

  1.   Реализовать функцию поиска элемента Е в односвязном списке L.
  2.   Реализовать процедуру обмена местами двух элементов списка SwapEtems(Pl, P2: PElem), где P1 и Р2 — указатели на элементы, путем переустановки ссылок в списке.
  3.  Подсчитать число максимальных элементов списка.
  4.  Найти среднее значение элементов списка.
  5.  Проверить, является ли список из целых чисел упорядоченным по возрастанию.
  6.  Исключить из списка элементы, содержащие заданное число.
  7.  В списке A хранится информация о людях (фамилия, имя, отчество, профессия). Имеется список В, содержащий перечень профессий. Удалить из списка А тех людей, чья профессия не указана в списке В.
  8.  Дан список штучных товаров, хранящихся на складе (наименование, цена). В списке могут присутствовать одинаковые товары. Необходимо:
  9.  составить прайс-лист на товары (список, содержащий перечень различных товаров и цен на них);
  10.  вычислить среднюю цену на каждый товар;
  11.  вывести перечень наименований товаров, чья цена ближе всего к средней.

  1.  Имеется N городов. Задан список пар городов (i,j), между которыми существует прямая дорога. Напечатать список городов, которые напрямую сообщаются с более чем тремя городами.
  2.  Дан список слов. Из каждой группы подряд идущих одинаковых слов оставить только одно.
  3.  Дан текстовый файл. Распечатать слова, имеющие максимальную длину.
  4.  Дан текстовый файл. Провести частотный анализ слов.
  5.  Дан текстовый файл с целыми числами. Распечатать сколько какое число встречается раз.
  6.  Дан список вещественных чисел. Проверить, упорядочены ли числа по убыванию.
  7.  Дан список вещественных чисел. Для каждого элемента списка напечатать число отрицательных элементов, следующих за ним.
  8.  Дан список вещественных чисел. Проверить, образуют ли числа, хранящиеся в списке арифметическую прогрессию.
  9.  Дан список вещественных чисел. Проверить, образуют ли числа, хранящиеся в списке геометрическую прогрессию.
  10.  Описать процедуру, которая вставляет в список, элементы которого упорядочены по неубыванию, новый элемент так, чтобы сохранялась упорядоченность.
  11.  Написать процедуру слияния двух упорядоченных списков из целых чисел в один упорядоченный список.
  12.  Даны два стека. Используя операции Извлечь, Занести и функцию ПустЛиСтек подсчитать общее число элементов в стеках. В качестве вспомогательных структур разрешается использование переменных целых типов. Алгоритм должен предусматривать восстановление исходного расположения элементов в стеках.
  13.  Распечатать возрастающие серии последовательности целых чисел в обратном порядке (серия — упорядоченная подпоследовательность максимальной длины).
  14.  Дан текстовый файл А. Переписать его содержимое в файл В, удалив при этом слова, длина которых меньше заданной.
  15.   Дан текстовый файл А. Переписать его содержимое в файл В, перенося при этом в конец каждой строки все входящие в нее знаки препинания.
  16.  Даны две очереди X и Y, содержащие вещественные числа. Из каждой очереди одновременно извлекается по одному числу, х и у соответственно. Если х < у, то число     (х + у) помещается в конец очереди X, иначе число (х–у) помещается в конец очереди Y. Необходимо определить число шагов, через которое одна из очередей станет пустой.
  17.  В текстовом файле записаны целые числа. Распечатать сначала положительные числа, а потом отрицательные (порядок следования должен остаться без изменения).
  18.  В текстовом файле записаны целые числа. Распечатать сначала положительные числа, а потом отрицательные (порядок следования должен стать обратным)
  19.  Проверить правильность расстановки скобок в арифметическом выражении с использованием стека. По правилам записи арифметических выражений первой должна закрываться последняя открывающая скобка, и число открывающих и закрывающих скобок должно совпадать. В выражениях используются круглые, квадратные и фигурные скобки. Предусмотреть ошибки: несоответствие скобок (a*k[d-l}) и непарные скобки (несоответствие числа открывающих и закрывающих)


 

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

41718. Технология разборки автомобильных генераторов переменного тока 512.4 KB
  Оценка технического состояния отдельных деталей генератора и его работы в целом. До введення цієї системи позначення генератора містило букву Г Г250 і тому подібне а регулятора напруги – букви РР РР24 і тому подібне.5 Технологія розбирання генератора: Отримати набір інструментів необхідних для розбирання і збирання генератора типу Г–221.
41719. АНАЛИЗ ЧАСТОТНЫХ ХАРАКТЕРИСТИК ЗВЕНЬЕВ 52.99 KB
  Определить влияние коэффициентов входящих в описание каждого звена на характеристики ЧХ. Использование пакета MtLb Построение частотных характеристик звеньев с помощью программы MtLb Построение частотных характеристик в программе MtLb 7.0 1 выполняется аналогично построению временных характеристик в той же программе.
41721. ДИОДНЫЕ ОГРАНИЧИТЕЛИ И ФИКСАТОРЫ УРОВНЯ 340.36 KB
  В зависимости от схемы включения и режима работы нелинейного элемента ограничителя различают 3 вида ограничения: по максимуму ограничение сверху –рис.5 Диод ограничителя включается между входом и выходом схемы последовательно с нагрузкой. Если напряжение входного сигнала Uвх меньше напряжения смещения Е диод работает на обратной ветви характеристики где его внутреннее сопротивление велико и разделяет вход схемы от выхода. Форма напряжений на входе и выходе схемы иллюстрируется на рис.
41722. Подготовка и проведение измерений с помощью электронного мультиметра 200.19 KB
  Испытание однофазного трансформатора при работе под нагрузкой Методическое указание Самара Самарский государственный технический университет 2008 Печатается по решению Редакционно-издательского совета СамГТУ УДК621. 313 Испытание однофазного трансформатора при работе под нагрузкой: метод. Содержат практические рекомендации по экспериментальным методам определения основных характеристик однофазного трансформатора по обработке опытных данных и оформлению отчетов а также контрольные вопросы. Этот процесс...
41723. Создание и редактирование таблиц, построение диаграмм 601.37 KB
  Рассмотрим некоторые особенности ввода текста в ячейки рабочего листа. Текст "Наименование", который вводится в ячейку А1, целиком в этой ячейке не помещается и занимает еще и ячейку В1 (рис. 2.3). Поскольку в ячейку В1 не было введено никакой информации, текст виден полностью. При вводе в ячейку В1 текста "Стоимость", текст в А1 будет виден частично, в пределах границ столбца А.Среднее количество проданного товара каждого наименования за текущий год. Общее количество проданных товаров за каждый месяц. Минимальное и максимальное количество товаров за полугодие количество максимальных продаж. Вклад в продажи сахара в общее количество проданного товара за...
41724. Частотные характеристики типовых звеньев систем автоматического управления 1.47 MB
  Построение частных характеристик типовых звеньев средствами математического пакета MATLAB и изучение зависимости этих характеристик от параметров входящих в состав передаточной функции.Построить следующие частотные характеристики: ЛАЧХ; ФЧХ; АФЧХ. Увеличив значение T в 10 раз определить как изменятся частотные характеристики. Задание 1 Используя пакет MTLB получим частотные характеристики.
41726. Исследование электрической цепи с последовательным и параллельным соединениями приёмников электрической энергии 349.01 KB
  Проверка на опыте особенностей последовательного и параллельного соединения резисторовэ,и при этом образуется неразветвленная цепь или участок цепи. Для последовательного соединения характерно то что во всех этих резисторах возникает одинаковый ток а падения напряжения на них пропорциональны сопротивлениям: Каждое сопротивление может быть найдено по формулам: Падение напряжения на всем участке цепи равно сумме падений напряжений на каждом резисторе: Эквивалентное сопротивление участка цепи равно сумме сопротивлений каждого резистора: Если же к концам участка вместо трех резисторов подключить эквивалентный...