АТД очередьОчередь (Queue)– еще один вид линейного списка. Способ доступа к элементам очереди ограничен двумя концами списка, при этом все операции вставки выполняются в конце списка, а все операции удаления – в начале. Структура обслуживается по принципу FIFO (First-In – First-Out – первый пришел – первый ушел). АТД очередь характеризуется следующими основными операциями: 1. Вставка элемента в конец очереди. 2. Удаление элемента из начала очереди. Рассмотрим реализацию АТД очередь на связных списках. Очередь характеризуется парой указателей: head – указателем на начало очереди, и tail – указателем на конец очереди. Type List=^node; Node=record Elem: integer; Next: list; End; Queue=record Head, tail: list; End;
Пустая очередь, то есть состояние, когда между началом и концом очереди нет элементов, соответствует совпадению этой пары указателей. При этом в пустой очереди мы предусмотрим фиктивный ведущий узел, который позволит эффективно реализовать операцию вставки первого элемента. Procedure QueueInit (var Q: queue); Begin New(Q.head); Q.head^.next:=nil; Q.tail:=Q.head; End;
Function QueueEmpty(Q: queue): Boolean; Begin QueueEmpty:=Q.head=Q.tail; End;
При изменении содержания очереди за счет вставки или удаления элементов меняется ее состояние и соответственно, значения указателей tail и head. При вставке элемента создается новый узел и связывается с последним существующим узлом, адрес которого определяет значение указателя tail. После этого указатель tail меняет значение на адрес нового узла. Удаление происходит из узла, следующего за фиктивным, после чего он сам становится фиктивным. Заметим, что удаляемый элемент остается в узле, но перестает быть частью очереди: Procedure Insert (x: integer; var Q: queue); Var P: list; Begin New(P); P^.elem:=x; P^.next:=nil; Q.tail^.next|:=P; Q.tail:=P; End;
Procedure remove (var x: integer; var Q: queue); Var P: list; Begin P:=Q.head; Q.head:=Q.head^.next; X:=Q.head^.elem; Dispose(P); End;
В случае, когда максимальный размер очереди известен, АТД очередь может быть реализован на массиве, длина которого a priori определяет максимальный размер очереди. В приведенной реализации очередь состоит из массива elem и указателей head, tail, которые интерпретируются как индексы массива. В начальном состоянии очередь пуста и оба указателя имеют нулевое значение: Const MaxQueueSize=; {максимальный размер очереди}
Type Queue=record Elem: array[0..MaxQueueSize-1-1] of integer; Head,tail: 0..MaxQueueSize; End;
Procedure QueueInit (var Q: queue); Begin Q.head:=0; Q.tail:=0; End;
Function QueueEmpty(Q: queue): Boolean; Begin Queyeempty:=(Q.head=Q.tail); End;
Procedure Insert (x: integer; var Q: queue); Begin Q.elem[Q.tail]:=x; Q.tail:=(Q.tail+1) mod MaxQueueSize; End; Procedure Remove (var x: integer; var Q:Queue); Begin X:=Q.elem[Q.head]; Q.head:=(Q.head+1) mod MaxQueueSize; End;
Очереди находят широкое применение в программировании, в частности, в таких приложениях, как последовательность обработки задач в операционных системах, буферизация задач принтера в системе входных и выходных потоков, организация буфера ввода с клавиатуры, моделирование процессов обслуживания клиентов и т.д.
Алгоритмы поиска. Основные понятия и определения. Задача поиска. Последовательный поиск элемента упорядоченного массива и связного упорядоченного списка. Среди алгоритмов компьютерной обработки данных особое место занимает задача поиска, связанная с нахождением какой-либо конкретной информации в большом объеме ранее собранных данных. В качестве основной структуры данных для алгоритмов поиска используется АТД таблица, представляющая собой совокупность элементов, каждая из которых идентифицируется ключом. Логической особенностью таблиц является то, что доступ к элементам таблицы производится не по позиции, а по ключу. Поэтому часто к ключу предъявляется требование уникальности в данной таблице, а случаи дублированных ключей требуют разработки особых подходов. АТД таблица поддерживает три основные операции: 1. Поиск элемента с заданным ключом. 2. Вставка элемента с заданным ключом. 3. Удаление элемента с заданным ключом. Абстрактные типы данных с перечисленными операциями называют также словарями. Из перечисленных операций основной является первая – поиск элемента с заданным ключом. Она может иметь 2 исхода: успешный, когда когда искомый элемент найден, и неуспешный, когда установлено, что элемента с заданным ключом в таблице нет. Остальные операции базируются на поиске. Классификация таблиц: - по месту хранения: внутренние таблицы хранятся в оперативной памяти, внешние – на внешних запоминающих устройствах. - по отношениям связи между элементами: линейной и нелинейной. Линейные таблицы основаны на АТД линейный список и могут быть реализованы в виде массивов или связных списков. Нелинейные таблицы основаны на АТД деревья или представлены таблицами с вычисляемыми методами. - по упорядоченности: в упорядоченной таблице элементы хранятся в соотв-ии с заданным критерием упорядоченности, в неупорядоченной таблице – произвольно. Сформулируем более точно задачу поиска для линейных таблиц. Пусть имеется линейная таблица элементов Т1, Т2…Тn, снабженных соответственно ключами К1, К2,..Кn, где >=1 – количество элементов таблицы, и ключ поиска Х. Требуется найти позицию I элемента Ti, содержащего заданный ключ x=Ki. В качестве представления линейной таблицы в программных реализациях будем рассматривать массив записей типа TBase, каждая запись состоит из ключа key и сопутствующей информации Info. Диапазон чисел от 1 до N задает тип Index, таблица описана типом Table, например: Type TBase=record Key: Tkey; Info: Tinfo; End; Index:=1..N; Table=array[index] of Tbase;
Алгоритм последовательного поиска (sequential search)в неупорядоченной таблице заключается в последовательном просмотре всех элементов таблицы, начиная с первого, до тех пор, пока либо искомый элемент не будет найден, либо не будут просмотрены все элементы таблицы в случае неуспешного поиска. Функция SeqSearch возвращает номер искомого элемента Х в случае успешного поиска или N+1, если ключ не найден. Function SeqSearch (x: Tkey; var T: Table): Index; Var i: index; Begin I:=1; While (i<=N) and (x<>T[i].key) do i:=i+1; SeqSearch:=I; End; Эффективность операции оценивается как O(N). Время выполнения зависит от количества сравнений ключей и успешности поиска: последовательный поиск производит N сравнений для каждого неуспешного поиска, и в среднем N/2 сравнений для успешного. Для успешного поиска, если мы предположим, что любой элемент имеет равную вероятность быть искомым, среднее количество сравнений равно: (1+2+…+N)/N=(N+1)/2. Известен способ существенного улучшения последовательного поиска с помощью барьерного элемента. Следует добавить фиктивную запись в конец таблицы и хранить в ней искомый ключ (в цикле while будем выполнять только 1 проверку вместо 2-х). Function QSeqSearch (x: Tkey; var T: table): Index; Var i: index; Begin I:=1; T[N+1].key:= x; While x<>t[i].key do i:=i+1; QSeqSearch:=I; End; Эмпирический анализ показывает, что при поиске по большим таблицам скорость улучшенного алгоритма QSeqSearch увеличивается до 30% по сравнению с вариантом SeqSearch.
Алгоритмы поиска. Основные понятия и определения. Задача поиска. Бинарный поиск элемента упорядоченного массива и связного упорядоченного списка. См. 27 вопрос по основным понятиям. Для упорядоченной таблицы можно предложить более эффективный алгоритм поиска, известный под названием метод бинарного или двоичного поиска (binary search). Искомый ключ сравнивается с ключом среднего элемента в таблице. Результат сравнения позволяет определить, в какой половине таблицы следует продолжить поиск: если ключи совпали, то алгоритм заканчивается успешно, если искомый ключ больше ключа среднего элемента, то для дальнейшего поиска выбирают правую половину, если меньше – левую. Затем к выбранной половине таблицы рекурсивно применяется тот же метод. Можно представить процедуру бинарного поиска в виде бинарного дерева: поиск осуществляет последовательное сравнение ключей с элементами, индексы которых представлены в узлах бинарного дерева. Последовательность индексов зависит только от размера N. Неудачный поиск приведет в один из внешних (квадратных) узлов. Для таблиц, размер которых на 1 меньше степени двойки, дерево имеет вид:
Для таблиц произвольной длины последовательность не столь симметрична, что видно на примере дерева:
Алгоритм бинарного поиска относится к рекурсивным алгоритмам типа «разделяй и властвуй». Для рекурсивного описания алгоритма левую и правую границы поиска (l и r соответственно) следует рассматривать как примеры процедуры. Для выполнения поиска необходимо при вызове процедуры задать значения ее формальных параметров l как 1 и r как N, а закончить рекурсию при условии, что левый индекс стал больше правого (l>r). Рекурсивная функция бинарного поиска RBinSearch представлена в следующем примере: Function RBinSearch (x: Tkey; var T: table; l,r: Index): index; Var i: index; Begin If l>r then RBinSearch:=N+1 Else Begin i:=(l+r) div 2; if T[i].key=x then RBinSearch:=i else if T[i].key<x then RBinSearch:= RBinSearch(x,T,i+1,r) Else RBinSearch:= RBinSearch(x,T,l,i-1); End; End; Устранение концевой рекурсии в процедуре бинарного поиска выполняется так: в нерекурсивной функции BinSearch нужная половина таблицы выбирается за счет изменения левого или правого индексов, и итерации продолжаются до тех пор, пока либо не будет найден элемент, либо левый индекс не станет больше правого.
Function RBinSearch (x: Tkey; var T: table;): index; Var i,r,l: index; Begin L:=1; r:=N; While (l<=r) and (x<>T[i].key) do Begin i:=(l+r) div 2; if x>T[i].key then l:=i+1; else r:=i-1; end; if x=T[i].key then BinSearch:=i; else BinSearch:=N+1; end;
Обе функции возвращают номер искомого ключа или N+1, если ключ не найден.
29. Деревья. Основные понятия и определения. Области применения деревьев. Обход дерева. Дерево(tree) – совокупность элементов, называемых узлами, и отношений, образующих иерархическую структуру узлов. Дерево может быть либо в нем имеется один специально обозначенный узел, называемый корнем дерева, а остальные узлы содержатся в непересекающихся множествах Т1, Т2,..Tm, каждое из которых в свою очередь является деревом. Деревья Т1, Т2,.. Tm называют поддеревьями данного корня.
Деревья. Основные понятия и определения. Поиск, добавление и удаление узла. Рекурсивные алгоритмы. } Опишем дерево как указатель на узел следующим образом: ◦ type Link = ^Node; ◦ Node = record ◦ elem: Tbase; ◦ left, right: Link ◦ end; } Узел состоит из трех полей: ◦ в поле elem хранится элемент (некоторое значение, числовое, строковое, запись и т.п.), поля left и right хранят ссылки на левое и правое поддеревья, соответственно.
Поиск по дереву: } Procedure Search(x: integer; var T: Link); } begin } if T = nil then } begin } new(T); T^.elem:=x; } T^.left:=nil;T^.right:=nil; } end } else } if x<T^.elem then search(x, T^.left) } else if x>T^.elem then search(x, T^.right); } end;
Удаление элемента: } procedure Delete(x: integer;var T:Link); } var P:Link; } procedure Del(var R: Link); } begin } if R^.right <> nil } then del(R^.right) } else begin } P:=R; R:=R^.left } end; } end;
|
