<< Пред.           стр. 3 (из 19)           След. >>

Список литературы по разделу

  type
  E = ...
  Queue = Array [1..MaxQ] of E;
  var
  Q: Queue;
  F, R: Integer;
  {Указатель F указывает на начало очереди. Указатель R указывает на конец очереди. Если очередь пуста, то F = 1, а R = 0 (То есть R < F – условие пустоты очереди).}
 
  Procedure Insert(I: Integer; var Q: Queue);
  begin
  Inc(R);
  Q[R]:=I;
  end;
 
  Function Empty(Q: Queue): Boolean;
  begin
  If R < F then Empty:=True Else Empty:=False;
  end;
 
  Procedure Remove(var I: Integer; Q: Queue);
  begin
  If Not Empty(Q) then
  begin
  I:=Q[F];
  Inc(F);
  end;
  end;
 
  Пример работы с очередью с использованием стандартных процедур.
  MaxQ = 5
 
 
  Производим вставку элементов A, B и C в очередь.
 
  Insert(q, A);
  Insert(q, B);
  Insert(q, C);
 
  Убираем элементы A и B из очереди.
  Remove(q);
  Remove(q);
 
  К сожалению, при подобном представлении очереди, возможно возникновение абсурдной ситуации, при которой очередь является пустой, однако новый элемент разместить в ней нельзя (рассмотрите последовательность операций удаления и вставки, приводящую к такой ситуации). Ясно, что реализация очереди при помощи массива является неприемлемой.
  Одним из решений возникшей проблемы может быть модификация операции remove таким образом, что при удалении очередного элемента вся очередь смещается к началу массива. Операция remove (q) может быть в этом случае реализована следующим образом.
 
  X = q[1]
  For I =1 to R-1
  q[I] =q[I+1]
  next I
  R =R-1
 
  Переменная F больше не требуется, поскольку первый элемент массива всегда является началом очереди. Пустая очередь представлена очередью, для которой значение R равно нулю.
  Однако этот метод весьма непроизводителен. Каждое удаление требует перемещения всех оставшихся в очереди элементов. Если очередь содержит 500 или 1000 элементов, то очевидно, что это весьма неэффективный способ. Далее, операция удаления элемента из очереди логически предполагает манипулирование только с одним элементом, т. е. с тем, который расположен в начале очереди. Реализация данной операции должна отражать именно этот факт, не производя при этом множества дополнительных действий.
  Другой способ предполагает рассматривать массив, который содержит очередь в виде замкнутого кольца, а не линейной последовательности, имеющей начало и конец. Это означает, что первый элемент очереди следует сразу же за последним. Это означает, что даже в том случае, если последний элемент занят, новое значение может быть размещено сразу же за ним на месте первого элемента, если этот первый элемент пуст.
 
  Организация кольцевой очереди.
 
 
 
  Рассмотрим пример. Предположим, что очередь содержит три элемента - в позициях 3, 4 и 5 пятиэлементного массива. Этот случай, показанный на рис. 2.17. Хотя массив и не заполнен, последний элемент очереди занят.
  Если теперь делается попытка поместить в очередь элемент G, то он будет записан в первую позицию массива, как это показано на рис. 2.17. Первый элемент очереди есть Q(3), за которым следуют элементы Q (4), Q(5) и Q(l).
  К сожалению, при таком представлении довольно трудно определить, когда очередь пуста. Условие R   Одним из способов решения этой проблемы является введение соглашения, при котором значение F есть индекс элемента массива, немедленно предшествующего первому элементу очереди, а не индексу самого первого элемента. В этом случае, поскольку R содержит индекс последнего элемента очереди, условие F = R подразумевает, что очередь пуста.
  Отметим, что перед началом работы с очередью, в F и R устанавливается значение последнего индекса массива, а не 0 и 1, поскольку при таком представлении очереди последний элемент массива немедленно предшествует первому элементу. Поскольку R = F, то очередь изначально пуста.
 
  Основные операции с кольцевой очередью:
  1. Вставка элемента q в очередь x.
  Insert(q,x)
  2. Извлечение элемента из очереди x.
  Remove(q)
  3. Проверка очереди на пустоту.
  Empty(q)
 
  Операция empty (q) может быть записана следующим образом:
 
  if F = R
  then empty = true
  else empty = false
  endif
  return
 
  Операция remove (q) может быть записана следующим образом:
 
  empty (q)
  if empty = true
  then print «выборка из пустой очереди»
  stop
  endif
  if F =maxQ
  then F =1
  else F = F+1
  endif
  x = q(F)
  return
 
  Отметим, что значение F должно быть модифицировано до момента извлечения элемента.
 
  Операция вставки insert (q,x).
  Для того чтобы запрограммировать операцию вставки, должна быть проанализирована ситуация, при которой возникает переполнение. Переполнение происходит в том случае, если весь массив уже занят элементами очереди и при этом делается попытка разместить в ней еще один элемент. Рассмотрим, например, очередь на рис. 2. 17. В ней находятся три элемента — С, D и Е, соответственно расположенные в Q (3), Q (4) и Q (5). Поскольку последний элемент в очереди занимает позицию Q (5), значение R равно 5. Так как первый элемент в очереди находится в Q (3), значение F равно 2. На рис. 2. 17 в очередь помещается элемент G, что приводит к соответствующему изменению значения R. Если произвести следующую вставку, то массив становится целиком заполненным, и попытка произвести еще одну вставку приводит к переполнению. Это регистрируется тем фактом, что F = R, а это как раз и указывает на переполнение. Очевидно, что при такой реализации нет возможности сделать различие между пустой и заполненной очередью Разумеется, такая ситуация удовлетворить нас не может
  Одно из решений состоит в том, чтобы пожертвовать одним элементом массива и позволить очереди расти до объема на единицу меньшего максимального. Так, если массив из 100 элементов объявлен как очередь, то очередь может содержать до 99 элементов. Попытка разместить в очереди 100-й элемент приведет к переполнению. Подпрограмма insert может быть записана следующим образом:
 
  if R = max(q)
 then R = 1
 else R = R+1
  endif
  'проверка на переполнение
  if R = F
 then print «переполнение очереди»
 stop
  endif
  q (r) =x
  return
 
  Проверка на переполнение в подпрограмме insert производится после установления нового значения для R, в то время как проверка на потерю значимости в подпрограмме remove производится сразу же после входа в подпрограмму до момента обновления значения F.
 
  2.4.3 Дек
  От английского DEQ - Double Ended Queue (Очередь с двумя концами)
 
  Особенностью деков является то, что запись и считывание элементов может производиться с двух концов (рис. 2.18).
 
 
 
  Дек можно рассматривать и в виде двух стеков, соединенных нижними границами. Возьмем пример, иллюстрирующий принцип построения дека. Рассмотрим состав на железнодорожной станции. Новые вагоны к составу можно добавлять либо к его концу, либо к началу. Аналогично, чтобы отсоединить от состава вагон, находящийся в середине, нужно сначала отсоединить все вагоны или вначале, или в конце состава, отсоединить нужный вагон, а затем присоединить их снова.
 
  Операции над деками:
  1. Insert - вставка элемента.
  2. Remove - извлечение элемента из дека.
  3. Empty - проверка на пустоту.
  4. Full - проверка на переполнениe.
 
 
  Контрольные вопросы
 1. Что такое структуры данных?
 2. Назовите уровни представления данных?
 3. Какова классификация структур данных?
 4. Какая статическая структура является самой простой?
 5. Перечислите основные элементы таблицы.
 6. Назовите их основные особенности.
 7. Что такое вектор?
 8. Что представляет из себя запись?
 9. Какова структура записи?
 10. К каким структурам данных относятся очереди и стеки ?
 11. Каково правило выборки элемента из стека ?
 12. Какая операция читает верхний элемент стека без его удаления ?
 13. Какую дисциплину обслуживания принято называть FIFO, а какую - LIFO ?
 14. Признак заполнения кольцевой очереди ?
 15. Признак пустой очереди ?
 16. Что называется списком?
 17. Перечислите виды списков.
 18. Назовите элементы очереди.
 19. Как организуется кольцевая очередь?
 20. Какова особенность деков?
 
 
 3. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
 
  До сих пор мы рассматривали только статические программные объекты. Однако использование при программировании только статических объектов может вызвать определенные трудности, особенно с точки зрения получения эффективной машинной программы. Дело в том, что иногда мы заранее не знаем не только размера значения того или иного программного объекта, но также и того, будет ли существовать этот объект или нет. Такого рода программные объекты, которые возникают уже в процессе выполнения программы или размер значений которых определяется при выполнении программы, называются динамическими объектами.
  Динамические структуры данных имеют 2 особенности:
  1) Заранее не определено количество элементов в структуре.
  2) Элементы динамических структур не имеют жесткой линейной упорядоченности. Они могут быть разбросаны по памяти.
  Чтобы связать элементы динамических структур между собой в состав элементов помимо информационных полей входят поля указателей (рис. 3.1) (связок с другими элементами структуры).
 
 
 
  P1 и P2 это указатели, содержащие адреса элементов, с которыми они связаны. Указатели содержат номер слота.
 
  3.1 Связные списки
 
  Наиболее распространенными динамическими структурами являются связанные списки. С точки зрения логического представления различают линейные и нелинейные списки.
  В линейных списках связи строго упорядочены: указатель предыдущего элемента содержит адрес последующего элемента или наоборот.
  К линейным спискам относятся односвязные и двусвязные списки. К нелинейным - многосвязные.
  Элемент списка в общем случае представляет собой поле записи и одного или нескольких указателей.
 
  3.1.1 Односвязные списки
  Элемент односвязного списка содержит два поля (рис. 3.2): информационное поле (INFO) и поле указателя (PTR).
 
 
 
  Особенностью указателя является то, что он дает только адрес последующего элемента списка. Поле указателя последнего элемента в списке является пустым (NIL). LST - указатель на начало списка. Список может быть пустым, тогда LST будет равен NIL.
  Доступ к элементу списка осуществляется только от его начала, то есть обратной связи в этом списке нет.
 
  3.1.2 Кольцевой односвязный список
 
  Кольцевой односвязный список получается из обычного односвязного списка путем присваивания указателю последнего элемента списка значение указателя начала списка (рис 3.3).
 
  Простейшие операции, производимые над односвязными списками
 
  1) Вставка в начало односвязного списка.
  Надо вставить в начало односвязного списка элемент с информационным полем D. Для этого необходимо сгенерировать пустой элемент (P=GetNode). Информационному полю этого элемента присвоить значение D (INFO(P)=D), значению указателя на этот элемент присвоить значение указателя на начало списка (Ptr(P) = Lst), значению указателя начала списка присвоить значение указателя P (Lst = P).
  Реализация на Паскале:
  type
  PNode = ^TNode;
  TNode = record
  Info: Integer; {тип элементов списка - может быть любым}
  Next: PNode;
  end;
  var
  Lst: PNode; {указатель на начало списка}
  P: PNode;
  Вставка в начало
  New(P); {создание нового элемента}
  P^.Info:=D;
  P^.Next:=Lst; {P указывает на начало списка, но Lst не указывает на P - новое начало}
  Lst:=P; {Lst указывает на новое начало списка}
 
  2) Удаление элемента из начала односвязного списка.
  Надо удалить первый элемент списка, но запомнить информацию, содержащуюся в поле Info этого элемента. Для этого введем указатель P, который будет указывать на удаляемый элемент (P = Lst). В переменную X занесем значение информационного поля Info удаляемого элемента (X=Info(P)). Значению указателя на начало списка присвоим значение указателя следующего за удаляемым элемента (Lst = Ptr(P)). Удалим элемент (FreeNode(P)).
  Реализация на Паскале:
  Удаление из начала
  P:=Lst;
  X:=P^.Info;
  Lst:=P^.Next;
  Dispose(P); {Удаляет элемент из динамической памяти}
 
  3.1.3 Двусвязный список
  Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от заглавного звена к последнему звену списка. Между тем нередко возникает необходимость произвести какую-либо обработку элементов, предшествующих элементу с заданным свойством. Однако после нахождения элемента с этим свойством в односвязном списке у нас нет возможности получить достаточно удобный и быстрый доступ к предыдущим элементам- для достижения этой цели придется усложнить алгоритм, что неудобно и нерационально.
  Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено списка. Динамическая структура, состоящая из элементов такого типа, называется двунаправленным или двусвязным списком.
  Двусвязный список характеризуется тем, что у любого элемента есть два указателя. Один указывает на предыдущий элемент (обратный), другой указывает на следующий элемент (прямой) (рис. 3.4).
 
 
  Фактически двусвязный список это два односвязных списка с одинаковыми элементами, записанных в противоположной последовательности.
  3.1.4 Кольцевой двусвязный список
  В программировании двусвязные списки часто обобщают следующим образом: в качестве значения поля Rptr последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Lptr заглавного звена- ссылку на последнее звено. Список замыкается в своеобразное кольцо: двигаясь по ссылкам, можно от последнего звена переходить к заглавному и наоборот.
 
 
  Операции над двусвязными списками:
  - cоздание элемента списка;
  - поиск элемента в списке;
  - вставка элемента в указанное место списка;
  - удаление из списка заданного элемента.
 
  3.2 Реализация стеков с помощью односвязных списков
 
  Любой односвязный список может рассматриваться в виде стека. Однако список по сравнению со стеком в виде одномерного массива имеет преимущество, так как заранее не задан его размер.
 
  Стековые операции, применимые к спискам
  1). Чтобы добавить элемент в стек, надо в алгоритме заменить указатель Lst на указатель Stack (операция Push(S, X)).
 
  P = GetNode
  Info(P) = X
  Ptr(P) = Stack
  Stack = P
 
  2) Проверка стека на пустоту (Empty(S))
 
  If Stack = Nil then Print “Стек пуст”
  Stop
 
  3) Выборка элемента из стека (POP(S))
 
  P = Stack
  X = Info(P)
  Stack = Ptr(P)
  FreeNode(P)
 
  Реализация на Паскале:
  Стек
 
  Вместо указателя Lst используется указатель Stack
  Процедура Push (S, X)
 
  procedure Push(var Stack: PNode; X: Integer);
  var
  P: PNode;
  begin
  New(P);
  P^.Info:=X;
  P^.Next:=Stack;
  Stack:=P;
  end;
 
  Проверка на пустоту (Empty)
 
  function Empty(Stack: PNode): Boolean;
  begin
  If Stack = nil then Empty:=True Else Empty:=False;
  end;
 
  Процедура Pop
 
  procedure Pop(var X: Integer; var Stack: PNode);
  var
  P: PNode;
  begin
  P:=Stack;
  X:=P^.Info;
  Stack:=P^.Next;
  Dispose(P);
  end;
 
  Операции с очередью, применимые к спискам.
 
  Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний элемент списка - за указатель конца очереди.
  1) Операция удаления из очереди (Remove(Q, X)).
  Операция удаления из очереди должна проходить из ее начала.
  P = F
  F = Ptr(P)
  X = Info(P)
  FreeNode(P)
  2) Проверка очереди на пустоту. (Empty(Q))

<< Пред.           стр. 3 (из 19)           След. >>

Список литературы по разделу