24740

Линейные списки – стеки, очереди, деки. Набор процедур для работы со связанным стеком, очередью

Шпаргалка

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

Способы обхода бинарного дерева. Древовидная структура – это конечное множество содержащее один или более узлов n такое что: 1 имеется один специально обозначенный узел называемый корнем данного дерева. Линия связи между парой узлов дерева называется обычно ветвью. Те узлы которые не ссылаются ни на какие другие узлы дерева называются листьями или терминальными вершинами рис.

Русский

2013-08-09

1.08 MB

40 чел.

1. Линейные списки – стеки, очереди, деки. Набор процедур для работы со  связанным стеком, очередью. 

Динамические структуры представляются списковыми структурами. Список-совокупность связанных узлов. Эти узлы имеют внутреннюю структуру. Они связаны между собой, причем каждый элемент характеризуется одним и тем же набором полей. Определенный таким образом список называют также линейным списком вследствие линейной упорядоченности его элементов. Упорядоченность элементов списка может задаваться неявно путем последовательного расположения его элементов как в логической структуре, так и в памяти машины. Такой список будем называть последовательным. упорядоченность элементов может задаваться с помощью специальных указателей, располагаемых в элементах и дающих возможность для каждого элемента определить его предшественника или последователя. Такая структура называется динамически связанным списком. Разновидностью таких структур данных являются полустатические структуры, имеющие обычно переменный размер, не превышающий заранее определенного верхнего предела.

1.Связанные списки Их используют для : 1) Моделирования дискретных систем 2) Арифметических операций над многочленами 3) Топологической сортировке 4) Работе с разреженными матрицами 5) Манипулировании с алгебраическими функционалами 6) Построении компиляторов и ОС 7) В СУБД

2.Линейные списки – это частный случай списка с n >= 0 узлами. Свойства :  1.x1 – первый узел 2. Для xi, n>i>1 : xi->xi+1 3.xn –последний узел Операции : 1. Доступ к xi для работы с ним 2. Включение/исключение нового элемента 3. Объединение списков/ разбиение на списки 4. Копирование списков 6. Сортировка/ подсчет узлов списка 7. Поиск узла  

Примеры полустатических структур — очередь, стек.

Стек (магазин, список LIFOLast In First Out) — последовательный список переменной длины, включение и исключение элементов из которого производится только с одной стороны.

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

Набор процедур для работы со связанным стеком

В самом начале проги  д.б.описание типов данных

Type  ссылка = ^узел;

узел = record

данные: тип;

связь: ссылка

end;

Очистка

Type стек = ссылка;

Procedure очистить_стек (var s: стек);

Begin

s:= nil

End;

Включение

Type стек = ссылка;

Procedure вкл_стек (d: тип данных; var s: стек);

Var x: ссылка;

Begin

new (x);

with x^ do

begin

данные:= d;

связь:= s

end;

s:= x

End;

Исключение

Function искл_стек (var d: тип данных; var s: стек):boolean;

Var x: ссылка;

Begin

if  s = nil then  искл_стек:= false

else

begin

искл_стек: = true;

x:= s;

with s^ do

begin

d:= данные;

s:= связь

end;

dispose(x)

end 

End;

Переменные в процедурах:
s – указатель на вершину стека

x – вспомогательная ссылочная переменная

d – переменная для хранения данных из узла.

Очередь последовательный список переменной длины, в котором включение элементов производится с одного конца списка (с хвоста), а исключение элементов — с другого (из головы). Очередь работает по принципу FIFOFirst In First Out.

Процедуры – исключение/включение/очистка и т.п.

Недостатки – нет доступа к предшествующим элементам списка; обязательно хранить указатель на начало и конец списка для многократного обращения к нему. Выход :

  •  циклический список в котором начало и конец замкнуты и вводится маркированный элемент начала списка.
  •  двунаправленный список – элементы такого списка содержат ссылки на родителя и потомка.
  •  Коралловое кольцо – двунаправленный список , в котором нечетные элементы ссылаются через один элемент, а четные на начало.

Набор процедур для работы со связанной очередью

Type ссылка = ^узел

узел = record

данные: тип данных;

связь: ссылка

end;

l,r: ссылка

end;

Очистка

Type очередь = record

Procedure очистить_очередь (var q:очередь);

Begin

q.l = nil;

q.r = nil

End;

Включение

Procedure вкл_очередь (d: тип данных; var q: очередь);    

Var x: ссылка;

Begin

new (x);

if q.l = nil then q.l := x;

with x^ do

begin

данные:= d;

связь:= nil

end;

q.r^.связь:= x;

q.r:= x

End;

Исключение

Function искл_очередь (var d: тип данных; var q: очередь): boolean;

Var x: ссылка;

Begin

if q.l = nil then искл_очередь:= true

else

begin

искл_очередь:= false;

x:= q.l;

with x^ do

begin

d:= данные;

q.l:= связь

end;

dispose (x)

end

End;

Дек – очередь с двумя концами с обоих сторон

2. Кольцевые списки. Многосвязные списки, примеры применения.

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

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

          Вход      Голова

Рис.7.  Циклический список с заголовком

Для доступа к элементу списка необходим его просмотр «с головы» — каждый раз с начала списка, что может быть медленным. Чтобы устранить этот недостаток, делают кольцевой список, т.е. указатель от последнего элемента направляют на первый элемент. В таком случае просмотр списка можно начинать с любого элемента, а после доступа к нужному элементу в РВ надо занести адрес его последователя.

 

Характерные черты кольцевого списка:

1.из любого элемента списка можно достичь любого др.эл-та списка

2.цикл.список не имеет 1-го и последнего эл-та.Удобно исп-ть к.-л. Внешний указатель на последний

эл-т l(st), когда след.за ним эл-т становится первым

Циклический список исп-т для организации стека и очереди

1)в стеке указатель lst является ссылкой на последний элемент и явл.вершиной стека

2)для очереди:     

 

Двунаправленный связанный список – это линейный список, в котором каждый элемент содержит два указателя: один указатель указывает на предшествующий элемент, а другой – на последний.

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

 

 

Рис. 14 – Двунаправленный связанный линейный список.

  

Рис. 15 – Двунаправленный циклический список без заголовка.

Внешний указатель

на заголовок

  

Рис. 16 – Двунаправленный циклический список с заголовком.

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

Используют цикл.списки: СУБД; трансляторы, компиляторы ,ОС; мат.задачи, сложение многочлена.

Пример: Использование двух связанных двунаправленных списков для представления разреженных матриц(пример многосвязных линейных списков)

Разреженная матрица – это матрица высокого порядка, в которой большинство элементов равно нулю.

Цель состоит в том, чтобы оперировать с матрицей так, будто матрица представлена в памяти вся, но для экономии не отводить место на нулевые элементы.

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

   Влево

  Индекс

  строки

Индекс          столбца

 Значение

   Вверх

Влево, вверх: связи со следующим ненулевым элементом слева в строке или вверху в столбце.

14     0     0     0

10     0    13    0    - разреженная матрица

 0      0     0     0

-15     0   -21    2

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

При последовательном распределении памяти матрица размера 200*200 заняла бы 40000 слов, в то же время разреженная матрица 200*200 с большим числом нулевых элементов может быть представлена в вышеописанной форме в ОП, содержащей приблизительно 4000 слов (в 10 раз меньше расход памяти).
        Разреженные матрицы применяются в алгоритмах решения линейных уравнений, обращения матриц и линейного программирования (симплекс - метод).

Многосвязные списки применяются также в базах данных

3. Древовидная структура, основные понятия. Способы обхода бинарного дерева.

Древовидная структура это конечное множество, содержащее один или более узлов (n) такое, что: 1) имеется один специально обозначенный узел называемый корнем данного дерева. 2) остальные узлы содержатся в m>= 0 попарно непересекающихся множествах

T1, Т2,  … , Тm, каждое из которых в свою очередь является деревом.

3.Деревья T1, Т2,  … , Тm  называются поддеревьями данного корня.

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

Линия связи между парой узлов дерева называется обычно ветвью. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются листьями (или терминальными вершинами) (рис. 4.1, 4.2 - b,k,l,h - листья). Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной).

Дерево обычно изображается в перевернутом виде с корнем вверху, листьями внизу (рис. 12).

Дерево может быть определено как иерархия узлов с парными связями, в которой: 1) самый верхний уровень иерархии имеет один узел, называемый корнем; 2) все узлы, кроме корня, связываются с одним и только одним узлом на более высоком уровне по отношению к ним самим.

На самом верхнем уровне иерархии имеется только один узел – корень. Каждый узел, кроме корня, связан с одним узлом на более высоком уровне, называемым исходным узлом для данного узла. Каждый элемент может быть связан с одним или несколькими элементами на более низком уровне, которые называются порожденными.

Степень узла – число непосредственных потомков внутреннего узла.

В примере (рис. 12) степень узлов: A,B – 2, C – 3, E – 1; H,J,D,G,F – 0.

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

Если х находится на уровне i, то говорим, что y на  уровне i+1. Узел у, который находится непосредственно под узлом х называется непосредственным потомком х (или сыном, или подчинённым). Узел x называется непосредственным предком y (или исходным, или отцом). Считается, что корень дерева находится на уровне 1.

Уровень узла по отношению к дереву Т определяется следующим образом:   корень дерева имеет уровень 1;   корни поддеревьев, непосредственно входящих в дерево, имеют уровни 2,3, и т.д.

Глубина (высота) дерева – максимальный уровень узла дерева (в примере дерево имеет глубину равную четырем) или число уровней в дереве. Степень дерева – максимальная степень его узлов (в примере дерево имеет степень = 3, т.к. максимальная степень узла  = 3). Лист (концевой узел, терминальный элемент) – элемент не имеющий потомков – это узел степени 0. (на рис. H,J,D,G,F – листья). Внутренний узел (или узел разветвления) – это узел, не являющийся концевым (т.е. не являющийся листом). Момент – число узлов (в примере – 9). Вес – число листьев (в примере – 5). Основание – число корней. (в примере – 1) Длина пути х – число ветвей (ребер), которые необходимо пройти, чтобы продвинутся от корня к узлу х. Корень имеет длину пути 1, его непосредственный потомок – длину пути 2 и т.д. Вообще узел на уровне i имеет длину пути i. Длина пути дерева – сумма длин путей всех его узлов. Она так же называется длинной внутреннего пути.

Средняя длинна пути Рi есть:

 , где ni число узлов на уровне i.

Лес – множество (обычно упорядоченное), состоящее из некоторого (может быть равного 0) числа непересекающихся деревьев.

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

Высота сбалансированного дерева  , где n – количество узлов.

1. В виде вложенных множеств:

  1.  В виде вложенных скобок

                   (А(В(H)(J))(C(D)(E(G))(F)))

3. В виде ступенчатой записи

  1.  В виде графа:

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

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

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

Бинарное дерево – упорядоченное дерево степени 2.

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

Способы обхода бинарного дерева.

Обход дерева производится  в определенном порядке:

1.прямой порядок( процедура Preorder(префиксный) , рекурсивная процедура r_Preoder);

2.обратный порядок(процедура Inorder(инфиксный), рекурсивная процедура r_Inorder);

3.концевой порядок(процедура Postorder (постфиксный), рекурсивная процедура r_Postorder).

  1.  

  1.   A B D C E G F H J – при прохождении в прямом порядке.
  2.  При обратном прохождении заходим в корень после того, как прошли узлы одного из поддеревьев, а затем переходим к узлам другого поддерева; при этом мы проходим узлы в таком порядке, как если бы все они были спроектированы на одну горизонтальную линию:

D B A E G C H F J

  1.  D B G E H J F C A – при прохождении в концевом порядке.

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


4. Дерево поиска. Включение элементов. Удаление элементов из дерева поиска.

Бинарные деревья часто используются для представления множеств данных, элементы которых имеют ключи – некоторые значения (числовые или символьные), по которым один элемент отличается от другого.

Если дерево организованно так, что для каждого узла внутри дерева все ключи в левом поддереве меньше, чем в правом, то – это дерево поиска. Используют для зщадачи сортировки и для задачи поиска.

(Если дерево организовано таким образом, что для каждого узла Тi все ключи в левом поддереве меньше ключа узла Тi, а ключи в правом поддереве больше ключа узла Ti, то это дерево называется деревом поиска.

В дереве поиска можно найти место каждого ключа, двигаясь, начиная от корня, и переходя на левое или правое поддерево каждого узла в зависимости от значения его ключа.  N элементов можно организовать в бинарное дерево с высотой h<= log2n, поэтому для поиска среди n элементов может потребоваться не более log2n сравнений, если дерево идеально сбалансировано.)

Рассмотрим пример размещения последовательности целых чисел в виде дерева поиска. Будем считать, что в последовательности могут встречаться одинаковые элементы, поэтому в узле будем хранить ключ (само число) и счетчик.

Type ссылка =^ узел;

      Узел = record

              Ключ : integer;

              Счетчик : integer;

              Лев, прав : ссылка;

        End;

Процесс поиска представим в виде рекурсивной процедуры. Параметр процедуры Р передается как параметр-переменная, а не как параметр-значение. В случае  включения переменной должно присваиваться новое значение ссылки, которая перед этим имела значение nil.

Алгоритм поиска по дереву с включением очень часто применяется в программах работы с базами данных (в СУБД) и в трансляторах для организации объектов, которые нужно хранить и искать в памяти. Процедура “Поиск по дереву с включением”.

Type ссылка =^ узел;

      Узел = record

              Ключ : integer;

              Счетчик : integer;

              Лев, прав : ссылка;

        End;

Var i,n,k : integer;

      Дерево : ссылка;

Procedure поиск (x:integer; var p : ссылка);

Begin

      If p=nil then   {узла с ключом  х  нет  в дереве – включить}

      Begin

              New(p);   {создаётся новый узел и p-значение

              With p^ do  ссылки на него}

                      Begin ключ:=x; счетчик:=1; лев:=nil; прав:=nil

                      End

              End

              Else   {продолжать поиск}

                      With p^ do

              Begin if x<ключ then поиск(х,лев)

                      Else if x>ключ then поиск(х,прав)

                      Else счетчик := счетчик + 1;

              End

End;  {поиск}

Procedure печать_дерева(t:ссылка; h : integer);

{см. процедуру печати дерева}

Begin    

      Дерево:=nil;

      Write(‘число элементов?’); read(n);

      For i:=1 to n do

      Begin read(k); поиск(к, дерево);

      End;

      Печать_дерева(дерево,0)

End.

Способы обхода и поиска :

  1.  Попасть в корень. Попасть в левое поддерево . Попасть в правое поддерево - RAB
  2.  Попасть в левое поддерево Попасть в корень. Попасть в правое поддерево –ARB
  3.  Попасть в левое поддерево Попасть в правое поддерево Попасть в корень. – ABR

В таком случае поиск осуществляется min за n сравнений , где n – глубина дерева.

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

Процесс поиска представим в виде рекурсивной процедуры.

Параметр процедуры Р передается как параметр-переменная, а не как параметр-значение. В случае  включения переменной должно присваиваться новое значение ссылки, которая перед этим имела значение nil.

Удаление узлов из дерева заключается в переприсвоении ссылок и освобождении памяти,3 случая:

  1.  если у удаленного узла отсутствуют потомки, то ссылка на него из вышестоящего узла заменяется на ссылку данного узла, а память освобождается
  2.  если хотя бы один потомок является концевым, то потомок заменяет место удаляемого узла
  3.  если ни один потомок  не является концевым, то удаляемый узел нужно заменить:
  4.  или на самый правый элемент его левого поддерева
  5.  или на самый левый элемент его правого поддерева

5. В-деревья, их свойства, построение. Индексирование массивов данных. Индексные деревья.

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

Будем называть также поддеревья страницами. На рисунке 9 изображено бинарное дерево, разделенное на страницы, состоящее из 7-и узлов каждая

Рис 20. - Бинарное дерево, разделенное на страницы (n = 3)

Уменьшение количества обращений к диску (а теперь обращение к каждой странице предполагает обращение к диску) может быть значительным. Предположим, что на каждой странице размещается 100 узлов, тогда дерево поиска, содержащее 106 элементов потребуется в среднем log100106 = 3 обращения к страницам в место 20-ти.

При хранении дерева на диске соблюдать сбалансированность (а тем более идеальную) очень дорого. Для этого случая очень разумный критерий был сформулирован Р. Бэйером: каждая страница содержит от n до 2n узлов при заданном постоянном n. Следовательно, в дереве с N элементами и максимальным размером страницы 2n узлов наихудший случай потребует lognN обращений к страницам. А обращение к страницам составляют, как известно, основную часть затрат на поиск. Кроме того, коэффициент использования памяти состоит не менее 50%, т.к. страницы заполнены хотя бы наполовину. При всех этих преимуществах данная схема требует сравнительно простых алгоритмов поиска, включения и удаления

Рассматриваемые структуры данных называются B – деревьями и имеют следующие свойства:

  1.  Каждая страница содержит не более 2n элементов (ключей).
  2.  Каждая страница, кроме корневой, содержит не менее n элементов (n – порядок B – дерева).
  3.  Каждая страница является либо листом, т.е. не имеет потомков, либо имеет m + 1 потомок, где m – число находящихся на ней ключей.
  4.  Все листья находятся на одном и том же уровне.

На рис. 21 показано B – дерево порядка 2 с 3-мя уровнями. Все страницы содержат 2, 3 или 4 элемента. Исключением является корень, которому разрешается содержать только один элемент. Все листья находятся на уровне 3.

      Ключи расположены в возрастающем порядке слева направо, если спроецировать дерево на один уровень, вставляя потомков между ключами, находящимися на странице – предке.

.

Включение в B–дерево.

Нужно включить в это дерево элемент с ключом 22.

Включение состоит из этапов:

  1.  Выяснение, что ключ 22 отсутствует (включение в страницу С невозможна т.к. она уже заполнена).
  2.  Страница С расщепляется на две страницы, т.е. размещается новая страница D.
  3.  Количество m + 1 ключей поровну распределяется на C и D, а средний ключ перемещается на один уровень вверх, на страницу предок А.

На рис. 23 изображено B – дерево рис. 22 после включения элемента с ключом 22.

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

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

Индексные Б–деревья.Верхний (первый) уровень индекса делит весь диапазон возможных значений ключа на m крупных интервалов (3).

Каждая ячейка 1–го уровня связана с блоком (страницей) ячеек 2–го уровня индекса .Каждая ячейка каждого блока 2–го уровня связана с блоком ячеек 3–го уровня и т. д.

Блок каждого уровня, лежащего ниже, делит соответствующий диапазон значений ключа на m более мелких интервалов. Ячейки самого нижнего уровня связаны  указателями с записями основного массива. Все уровни индекса упорядочены по возрастанию значений ключа.

На рис.3 изображено индексное дерево (3 уровня, построенные для упорядоченного основного массива, записи которого имеют диапазон значений ключа от 6 до 99).

Рис. 3. Пример структуры типа Б-дерева

6. Применение бинарных деревьев. Кодирование и сжатие данных. Кодовые деревья, дерево Хаффмена.

1)Бинарные деревья применяются для поиска дубликатов в тексте. Алгоритм: считывается 1-е число и помещается в корень дерева с пустым левым и правым  поддеревьями, затем каждое след. Число  сравнивается с числом , находящемся в корне. Если значения совпадают, то это дубликат, если новое число меньше значения корня, то процесс повторяется для левого поддерева и т.д Так продолжается пока не встретим дубликат или пока не достигнем пустое дерево.

2)Для сортировки

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

3)задача поиска информации(см.дерево поиска)

4)для представления арифметических выражений

Рассмотрим метод представления выражения,содерж.операнды и операторы в виде строгого бинарного дерева.Корень содержит оператор,кот.может быть применен к результ.выражения, представлен левым и правым поддеревом.Узел представляет оператор имеет 2 непустых поддерева.При этом не требуются (), т.к.структура дерева определяет порядок операций.

5)использование индексных деревьев для индексации массивов(В-деревьев сильноветвящихся)

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

хi-i-ое значение индексир.поля

рi-указатель на вершину  содерж.значение индексир поля <или = хi, рi+1≥ хi.

n-порядок В-дерева

Листовая вершина содержит информацию о нахождении стр.в файле базы данных записями имеющ.соответ зн-ия индексир.поля.

6)задача кодирования и сжатия информации(деревья Хаффмена).Для кодирования и декодирования сообщений.

Допустим,что алфавит состоит из 4-х символов.

Символ

Код

A

010

B

100

C

000

D

111

Сообщение: ABACCDA,закодируем его 010100010000000111010-21 бит

Идея метода: найти код, кот.миним.сообщ., для этого учесть частоту появления символа, для часто встречающихся символов назначить короткий код, для редко встречающихся символов назначить более длин.код

Символ

Код

частота

код

A

010

3

0

B

100

1

110

C

000

2

10

D

111

1

111

Построение дерева Хаффмена

Такая операция подсказыв метод реализ оптимальной схемы кодирования,если известн.частота появления символа. Находим в сообщ 2 символа,появл наименее часто. Это символы B и D, будем различать по после числу кода (0 и 1), соед их в единый символ BD,появлен кот означает, что это символ B, либо D.Часто  появл. этого символа =сумме частот B и D,поэтому она=2 и т.д.

Символ          Частота          Код

Символ          Частота          Код

Символ          Частота          Код

  A                     15            111

  B                       6          0101

  C                       7          1101

  A                     12            011

  B                     25              10

  C                       4        01001

  A                       6          1100

  B                       1        01000

  C                     15              00

?

Символ ABCD содержит весь алфавит, ему в качестве обхода присваивается пустая строка бита нулевой длины.

Операция объединения двух символов в один предполагает использование структуры бинарного дерева. Каждый лист представляет символ исходного алфавита. Каждый узел, не являющийся узлом, представляет соединение символов из листов — потомков данного узла. На рис. 1a приведено бинарное дерево, построенное с использованием предыдущего примера. Каждый узел содержит символ и его частоту. На рис. 1b показано бинарное дерево, построенное по данному методу для приведенной на рис. 1c таблицы символов алфавита и частот. Такие деревья называют деревьями Хаффмена, по имени изобретателя этого метода кодирования.

Как только дерево Хаффмена построено, код любого символа алфавита может быть определен просмотром дерева снизу вверх, начиная с листа, представляющего этот символ. Начальное значение кода — пустая строка. Каждый раз, когда мы поднимаемся по левой ветви, к коду слева приписывается 0; каждый раз при подъеме по правой ветви к коду приписывается 1.

Определение кода символа

Как дерево построено, код любого символа может быть определен  след.образом: нужно поосматр дерево снизу вверх, начиная с листа, представл этот  символ.Нач. значение кода- пустая строка бита. Каждый раз, когда подним по левой ветке  дерев коду слева приписыв 0, а по правой ветви коду слева приписыв 1.

    

Декодиров сообщения

Исх. Сообщения при наличии кодировки сообщ и дерева Х может быть восстановлено след.образом:начиная с корня дерева каждый  раз,когда встреч 0 двигаемся по левой ветви, а когда 1, двиг по правой ветви. Повторяем процесс, пока не дойдем  до листа. Новый символ исх.сообщен и есть символ, соотв.закодир

11101000101110110

DACAACDAB

7. Сортировка. Методы вставок и обмена. Метод Шелла. Быстрая сортировка. Обменная поразрядная сортировка.

Сортировка – процесс перестановки объектов данного множества в определённом порядке. Цель сортировки – облегчить последующий поиск элементов в отсортированном множестве.

Существует два вида сортировки (в зависимости от вида хранения данных): 1) внутренняя (сортировка массивов); 2) внешняя сортировка (сортировка файлов).

Терминология и обозначения

Даны элементы а12,…,an. Сортировка означает перестановку элементов в таком порядке, что при заданной функции упорядочения f выполняется соотношение:                                                                             

 f(ak1) fk2) … fkn).

Обычно функция упорядочения не вычисляется по специальному правилу, а содержится в каждом элементе в виде компоненты-ключа. Поле-ключ служит для идентификации элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке.

Меры эффективности алгоритма сортировки:

С – количество сравнений ключей;

М – количество перестановок элементов.

Эти числа определяются как функции от n, где n – количество сортируемых элементов.

Хорошие алгоритмы (логарифмические) требуют порядка С~n*log10n сравнений.

Для простых (квадратичных методов):   С ~ n² .

 

Методы вставок

Сортировка простыми вставками.

Элементы условно подразделяются на готовую последовательность: а1,…,аi.

И входную последовательность аi,…,аn.

На каждом шаге, начиная с i=2 и, увеличивая i на 1, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

Пример:            

Начальные ключи | 44 | 55   12   42   94   18   06   67

 i=2    | 44   55 | 12   42   94   18   06   67

 i=3 ???????????????????????????????????????????

??i=4    | 12   42   44   55 | 94   18   06   67

 i=5    | 12   42   44   55   94 | 18   06   67

 i=6    | 12   18   42   44   55   94 | 06   67

 i=7    | 06   12   18   42   44   55   94 | 67

 i=8    | 06   12   18   42   44   55   67   94|

Метод Шелла

 Некоторое улучшение метода сортировки простыми включениями было предложено Д.Шеллом в 1959 году.

Идея метода: Сортируются группы записей, отстоящих друг от друга на заданном расстоянии(8). После сортировки всех таких групп, сортируются группы записей, отстоящих на меньшее расстояние(4) и т.д., пока не дойдём до расстояния равному 1.

Существует формула для расчёта приращений:

n – количество записей;

t – количество приращений;

t=[log3n]

t=[log3n]-1;

ht=1;

hk -1=3*hk+1,

где h – приращение.

Получаем ряд приращений 1,4,13,40,121…

Пример:

 n=27; t=3;

 h3=1; h2=4; h1=13.

Пример:

(4),(2),(1) – приращения

44  55  12  42  94  18   6  67  4 - сортировка

44  18   6  42  94  55  12  67 2 - сортировка

 

6  18  12  42 44 55 94 67  1 - сортировка

6  12  18  42  44  55  67  94   результат

Затраты, которые требуются для сортировки n элементов с помощью алгоритма Шелла пропорциональны n1,2.

Методы обмена

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

Быстрая сортировка

(обменная сортировка с разделением)

Это улучшенный метод, основанный на принципе обмена. Неожиданно оказалось, что усовершенствованный «пузырёк» даёт лучший результат из всех известных до настоящего времени методов сортировки. Он обладает столь блестящими характеристиками, что его изобретатель Хоар окрестил его “быстрой сортировкой”, QuickSort (1962г.).

В методе Бетчера последовательность сравнений предопределена; она не зависит от фактического состояния файла (т.е. от того, насколько он уже упорядочен). Разумно предположить, что метод сортировки будет эффективнее, если последовательность сравнений элементов зависит от результатов предыдущих сравнений (т.е. будет учитываться состояние файла).

Q-sort основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

Алгоритм.

массив

    

    i=1  →            ← j=N   

Пусть имеются два указателя i и j. Причём вначале: i=1, j=N.

Сравним ki и kj   (ki : kj).

Если обмен не нужен, то уменьшаем j на 1 и повторяем этот процесс.  

После первого обмена  увеличим i на 1 и будем продолжать сравнения, увеличивая i, пока не произойдёт ещё один обмен, тогда уменьшим j и т.д., пока не станет i=j. К этому моменту запись Ri(Rj) займёт свою окончательную позицию, и  исходный файл будет разделён на два подфайла:

  (R1,…Ri -1)Ri(Ri+1,…,Rn).   

Эти подфайлы надо сортировать независимо (тем же методом).

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

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

Каждый из подфайлов сортируют методом Q-sort за исключением очень коротких.

Обменная поразрядная сортировка

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

В общих чертах идея метода следующая:

I этап. Файл сортируется по старшему значащему биту ключа так, что все  ключи, начинающиеся с нуля, оказываются перед всеми ключами, начинающимися с единицы. Для этого надо найти самый левый ключ ki, начинающийся с единицы и самый правый kj, начинающийся с нуля, после чего, записи Ri и Rj меняются местами. Процесс повторяется до тех пор, пока не станет i>j.

II этап. Обозначим через F0 множество элементов, начинающихся с нуля, а через F1 – остальные. Применим к F0 обменную поразрядную сортировку  (начинаем теперь со второго бита слева) до тех пор, пока множество F0 не будет полностью отсортировано. Затем проделываем то же самое с множеством F1. Как и при быстрой сортировке, для хранения информации о подфайлах, ожидающих сортировку, можно воспользоваться стеком. Стратегию формирования стека здесь применяют другую: В стек помещать не больший из подфайлов, а правый подфайл, при этом элементы стека (r,l) означают, что подфайл с правой границей r ожидает сортировку по биту l, левую границу можно не запоминать, она всегда задана неявно, так как файл обрабатывается слева на право.

Алгоритм:

Записи от 1-й до N-й   R1,R2,…,RN  переразмещаются на том же месте. После завершения сортировки их ключи будут упорядочены

  k1≤…≤kn

Предполагается, что все ключи – это m-разрядные двоичные числа:

  а12,…,аm  .

R1 [Начальная установка.] Опустошить стек, установить l←1,                             

     rN,b←1.

R2 [Начать новую стадию.] Сортируется подфайл записей со        

     следующими границами:

  Rl≤…≤Rr  по биту b.

     По смыслу алгоритма lr; если r=l, то перейти к R10, в      

     противном случае il,jr.

R3 [Проверить ki на единицу.] Проверить бит b ключа ki на единицу.

     Если (ki)b=1, то перейти к шагу R6.

R4 [Увеличить i.] Если ij, то возвратиться к R3, иначе к шагу R8.

R5 [Проверить kj+1  на ноль.] Проверяется бит b ключа kj+1.

     Если (kj+1)b=0, то перейти к шагу R7.

R6 [Уменьшить j.] Уменьшить j на 1. jj-1.Если ij, то перейти к шагу R5, иначе к R8.

R7 [Поменять местами записи Ri  и  Rj+1.] Поменять местами Ri и Rj+1, затем перейти к шагу R4.   

R8 [Проверить особые случаи.] К этому моменту стадия разделения    

завершена, i=j+1, бит b ключей  от kl до kj равен нулю, а бит ключей от ki до kr равен единице. Увеличить b на 1. Если b<m,где m – число бит,    

     или меньше, то перейти к шагу R10. Это значит, что подфайл  

RlRr отсортирован. Если в файле не может быть равных ключей, то такую проверку можно не делать. Иначе, если j<1 или j=r, возвратиться к шагу R2 (все просмотренные биты оказались равными соответственно     

     единице или нулю).

     Если j=l, то увеличить l на 1 и перейти к шагу R2 (встретился   

     только один бит, равный нулю).

R9 [Поместить в стек.] Поместить в стек пару (r,b), затем установить   

      rj и перейти к R2.

R10 [Взять из стека.] Если стек пуст, то сортировка закончена, иначе   

       установить lr+1, взять из стека элемент (r’,b’), установить  

       rr’,bb’ и возвратиться к шагу R2.

Для хранения  “информации о границах” подфайлов,  ожидающих сортировки мы воспользуемся стеком.

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

8. Сортировка. Методы выбора и слияния. Простой, квадратичный выбор. Выбор из дерева. Двухпутевое слияние. Метод слияния списков.

Простой выбор

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

удаляет физически запись из сортируемого файла, то удаление имитируется заменой ключа на значение “∞” (∞ по предположению больше любого реального ключа.). 2). Повторить шаг 1. На этот раз будет найден ключ, наименьший из  оставшихся. 3). Повторять шаг 1 до тех пор, пока не будут выбраны все N записей.

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

Описанный метод требует N-1 сравнений, каждый раз, когда выбирается очередная запись.

Пример: Сортируемый файл                           Область вывода

Недостатки этого метода очевидны, если использовать последовательное размещение записей файла в памяти:

  •  большое число сравнений N(N-1);
  •  необходима дополнительная память.

Этот метод можно модифицировать следующим образом:

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

Квадратичный выбор.

Рассмотрим следующий метод: пусть файл содержит 16 записей. Разобьём его на четыре группы по четыре записи.

    || 14    5   18   21 ||  2    7    11    3 ||  9   26   1    8 || 13   22    6   20 ||

Найдём наибольшие элементы в каждой группе и соберём их вместе:

                   21                       11                      26                         22

Тогда наибольший среди них и будет наибольшим в файле. Чтобы получить второй по величине элемент, достаточно просмотреть оставшиеся элементы группы, содержащей 26, т.е. максимальный, и максимум из них поместить в «группу лидеров» на место 26 и т.д.

Вообще, если N - точный квадрат, то  можно разделить файл на √N групп по √N элементов в каждой. Тогда любой шаг, кроме первого, потребует не более, чем  √N – 1 сравнений внутри группы раннее выбранного элемента плюс √N – 1 сравнений в “группе лидеров”. Этот метод получил название “квадратичный выбор”.

Оказывается такой метод может быть обобщён: существует метод кубического выбора (³√N больших групп, каждая  из которых содержит ³√N малых групп по ³√N записей), выбора четвёртой степени и т.д. Если эту идею развить до её полного логического завершения, то мы придём к выбору n-й степени, основанному на структуре бинарного дерева.

Пример: Схема кубического выбора.

(n=27, ³√27=3);

max –максимальный элемент в выходную последовательность  

Выбор из дерева

Этот метод является выбором n-й степени, где n выбрано так, что размер самой малой группы минимален и равен 2.

ij  Рассмотрим, например, результаты соревнований по настольному теннису:

Рис. 3 – Дерево выбора

Сидоров побеждает Володина, а Иванов побеждает Сергеева; затем в следующем туре Иванов выигрывает у Сидорова и т.д.

На этом рисунке показано, что Иванов – чемпион среди восьми спортсменов, а для того, чтобы определить это, потребовалось 8-1=7 матчей (т.е. сравнений).

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

Метод сортировки простым выбором  основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Поиск наименьшего ключа из n элементов потребует n-1 сравнений, из (n-1) элементов – (n-2) сравнений.

Как можно улучшить эту сортировку выбором? Это можно сделать только в том случае, если получить от каждого прохода больше информации, чем просто указание на один наименьший элемент.

Например, с помощью n/2 сравнений можно определить наименьший элемент (ключ) из каждой пары, при помощи n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т.д. Наконец, при помощи n-1 сравнений можно построить дерево выбора и определить корень как наименьший ключ.

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

Элемент, оказавшийся в корне дерева, вновь имеет меньший ключ (среди оставшихся) и может быть исключён. После n таких шагов дерево становится пустым (т.е. состоит из “дыр”) и процесс сортировки закончен.

Каждый из n шагов требует log2n сравнений. Вся сортировка требует порядка n*log2n элементарных операций, не считая n шагов которые необходимы для построения дерева.

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

Сортировка слиянием

 Слияние – означает объединение двух или более упорядоченных файлов в один упорядоченный файл.  Можно, например, слить два подфайла,

 1-й –  3  6  11  21  30

 2-й -  1   4   7   9    28

получив   1  3  4  6  7  9  11  21  28  30.

Простой способ сделать это – сравнить два наименьших элемента, вывести наименьший из них и повторить процедуру.

Начав с   

получим

затем

              

и т.д.    

 

Самый простой алгоритм здесь – двухпутевое слияние.

Алгоритм.(Двухпутевое слияние).

Этот алгоритм осуществляет слияние двух упорядоченных файлов  x1 x2≤…≤xm  и  y1y2≤…≤yn в z1z2≤…≤zm+n.

М1. [Начальная установка.] Установить i←1, j←1,k←1.

М2. [Найти наименьший элемент.] Если xiyj, то перейти к шагу   

      М3, в противном случае перейти к шагу М5.

М3. [Вывести xi] Установить zkxi, kk+1, ii+1. Если im, то   

      возвратиться к М2.

М4. [Вывести yj,…,yn.] Установить (zk,…,zm+n)←(yj,…,yn) и завершить

      работу алгоритма.                        

М5. [Вывести yj.] Установить zkyj,kk+1,jj+1. Если jn, то

      возвротиться к М2.

М6. [Вывести xi,…,xm] Установить (zk,…,zm+n)←(xi,…,xm) и  

      завершить работу алгоритма.  

Рис. 6 – Алгоритм “Двухпутёвое слияние”

Общий объём работы, выполняемой алгоритмом М, по существу пропорционален m+n (отсюда слияние – более простая задача, чем сортировка). Задачу сортировки можно свести к слияниям, сливая всё более длинные подфайлы до тех пор, пока не будет отсортирован весь файл. Такой подход можно рассматривать как развитие идеи сортировки вставками: вставки нового элемента в упорядоченный файл – частный случай слияния при n=1

.  

Сортировка посредством слияния списков

Алгоритмы слияния имеют два существенных недостатка:

  1.  Большой расход памяти для вспомогательной рабочей области.
  2.  Необходимость большого числа перемещений записей.    

Эти недостатки можно устранить, создав из сортируемого файла подобие связанного списка, для чего каждая запись Ri должна иметь “поле связи” Li, в котором будет храниться № записи, следующей за данной записью в порядке возрастания ключей.                            

После сортировки L0=№ записи с наименьшим ключом.

Алгоритм L.

Предполагается, что записи R1,…,RN содержат ключи k1,…,kN и поля связи L1,…,LN, в которых могут храниться числа от -(N+1) до (N+1). В начале и в конце файла имеются искусственные записи R0 и RN+1 с полями связи L0 и LN+1. Этот алгоритм сортировки списков устанавливает поля связи таким образом, что записи оказываются связанными в возрастающем порядке.

После завершения сортировки L0 указывает на запись с наименьшим ключом, при 1≤kN связь Lk указывает на запись, следующую за Rk , а если Rk – запись с наибольшим ключом, то Lk=0. В процессе выполнения этого алгоритма записи R0 и RN+1 служат “головами”  двух линейных списков, подсписки которых в данный момент сливаются.

Отрицательная связь означает коненц подсписка, о котором известно, что он упорядочен; нулевая связь означает конец списка. Предпологается, что N≥2.

Через “|Ls|←p” обозначена операция присвоить Ls значение р или –p, сохранив прежний знак Ls.

L1. [Подготовить два списка.] Установить L0←1, LN+1←2, Li← -(i+2)

     при 1≤iN-2 и LN-1LN←0.

     Мы создаём два списка, содержащие соответственно записи

     R1,R3,R5,… и R2,R4,R6,…; отрицительные связи говорят о том,

     что каждый упорядоченный “подсписок” состоит всего лишь из

     одного элемента. Другой способ выполнить этот шаг, извлекая пользу из

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

     данных.

L2. [Начать новый просмотр.] Установить s←0, tN+1, pLs, qLt.

     Если q=0, то работа алгоритма завершена.

     При каждом просмотре p и q пробегают по спискам, которые     

      подвергаются слиянию; s обычно указывает на последнюю

      обработанную запись текущего подсписка, а t – на конец только

      что выведенного подсписка.

L3. [Сравнить kp : kq.] Если kp>kq, то перейти к L6.

L4. [Продвинуть p.] Установить |Ls|←p, s←p, p←Lp. Если p>0, то  возвратиться к шагу L3.

L5. [Закончить под список.] Установить Ls←q, s←t. Затем установить t←q и q←Lq один или более раз, пока не станет  q≤0, после чего  перейти к шагу L8.

L6. [Продвинуть q.] (Шаги L6 и L7 двойственны по отношению к L4 и  L5.) Установить |Ls|←q, s←q, q←Lq. Если q>0, то возвратиться к  шагу L3.

L7. [Закончить подсписок.] Установить Lsp, st. Затем установить

     tp и pLp один или более раз, пока не станет p≤0.

L8. [Конец просмотра.] (К этому моменту p≤0 и q≤0, так как оба

    указателя подвинулись до конца соответствующих подсписков.)

    Установить p← -p, q← -q. Если q=0, то установить |Ls|←p, |Lt|←0

    и возвратиться к шагу L2. В противном случае возвратиться к

    шагу L3.

9. Алгоритмы поиска данных. Последовательный, двоичный, блочный, интерполяционный, Фибоначчиев поиск.

В алгоритмах поиска присутствует аргумент поиска К. Задача в том, чтобы отыскать запись, имеющую К своим ключом.

Классификация: 1) группы последовательного поиска 2) поиск посредством сравнения ключей (поиск в таблице)(бинарный, Фибоначчи) 3)поиск цифровой 4) хеширование 5) поиск по вторичным ключам.

Последовательный - наиболее простой способ отыскания записи. Состоит в последовательном просмотре и сравнении их ключей с данными.

Бинарный поиск  Разыскивается аргумент К в таблице R1....RN,  у которых ключи упорядочены k1<=...<=kN.

Идея: 1) Сравнить К со средним ключом в таблице. Результат сравнения определит в какой половине находится запись. Применяя к ней туже процедуру, через log 2N будет установлено есть ли такая запись:

| 7 | 11 | 12| 15 | 18| 19 | 21 | 22 | 25 | 27 | 31 | 35 | 40 |

l              u

Метод Фибоначчи. N<Fk+1-1.

Поиск Фибоначчи 

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

Алгоритм построения дерева поиска Фибоначчи:

Если k=0 или k=1, дерево сводится к 0.

Если k>=2, корнем является Fk ; левое поддерево есть дерево Фибоначчи порядка k-1; правое поддерево есть дерево Фибоначчи порядка k-2 с числами в узлах, увеличенными на Fk.

Замечание.

Желательно, чтобы число ключей в таблице N удовлетворяло условию: N<=Fk+1 - 1 

N – количество элементов в массиве;

k – порядковый номер в дереве Фибоначчи;

Fk+1число Фибоначчи;

  1.  Если k= 0 или k= 1, то корень дерева равен 0.
  2.  Если k>= 2, то корнем является число Fk, левое Fk-1, правое Fk-2

| 0 | 1 | 1| 2 | 3| 5 | 8 | 13 | 21 | 34 |

Алгоритм предназначен для поиска аргумента К в табл записей R1,R2,…,Rn, распсположенных в порядке возрастания ключей К1<K2<…<Kn. Предполагается, что N+1 есть число Фибоначчи Fk+1.Подходящей нач.установкой данный метод можно сделать пригодным для  любого N.В алгоритме p и q-последов числа Фибоначчи.

Представьте себе, что Вы ищете слово в словаре. Если нужное слово начинается с буквы 'А', вы наверное начнете поиск где-то в начале словаря. Когда найдена отправная точка для поиска, ваши дальнейшие действия мало похожи на рассмотренные выше методы.Если Вы заметите, что искомое слово должно находиться гораздо дальше открытой страницы, вы пропустите порядочное их количество, прежде чем сделать новую попытку. Это в корне отличается от предыдущих алгоритмов, не делающих разницы между 'много больше' и 'чуть больше'. Мы приходим к алгоритму, называемому интерполяционным поиском: Если известно, что К лежит между Kl и Ku, то следующую пробу делаем на расстоянии (u-l)(K-Kl)/(Ku-Kl) от l, предполагая, что ключи являются числами, возрастающими приблизительно в арифметической прогрессии. Интерполяционный поиск работает за log log N операций, если данные распределены равномерно. Как правило, он используется лишь на очень больших таблицах, причем делается несколько шагов интерполяционного поиска, а затем на малом подмассиве используется бинарный или последовательный варианты.

Блочный поиск Если элементы упорядочены по ключу, то при сканировании списка не требуется чтение каждого элемента. Компьютер мог бы, например, просматривать каждый n-ный элемент в последовательности возрастания ключей. При нахождении элемента с ключом, большим, чем ключ, используемый при поиске, просматриваются последние n-1 элементов, которые были пропущены. Этот способ называется блочным поиском: элементы группируются в блоки, и каждый блок проверяется по одному разу до тех пор, пока ни будет найден нужный блок. Вычисление оптимального для блочного поиска размера блока выполняется следующим образом: в списке, содержащем N элементов, число просмотренных элементов минимально при длине блока, равной N. При этом в среднем анализируется N элементов.

10.  Хеширование, хеш-функции. Способы разрешения коллизий.

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

Хеширование – есть один из методов поиска. Основная проблема хеширования – это проблема однозначности, т.к. возможно совпадение адресов при несовпадающих ключах: ki≠kj.

Коллизия (h(ki)=h(kj)) – это совпадение вычисленных значений адресов в 2-х или более записях файла, имеющих различные значения ключа. Хеширование – это способ вычисления адреса, при которых функция расстановки выдаёт различные значения для различных входных данных.

Существует специальная программа разрешения коллизий

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

Хеш-функция. Предположим, что хеш-функция h(k) имеет M различных значений, удовлетворяющих условию 0≤ h(k)<М для всех k. В реальном файле очень много почти одинаковых ключей, поэтому желательно выбрать хеш-функцию, рассеивающую их по таблице. Наиболее распространённые методы: а)деления; функция хеширования определяется h(k)=k mod M, где k – ключ, М – количество свободных ячеек таблицы(не должно быть кратным 3 и не должно быть равным степени основания СИ ЭВМ). б)умножения;  h(k)=МАk/W, умножение ключа k на некоторую фиксированную константу А и выбор нескольких цифр из середины результата, W – максимальное число; А – константа не имеющая общих делителей с W, кроме 1; М равно степени 2. в) Метод середины квадрата (midsquare technique) предусматривает преобразование ключа в целое число, возведение его в квадрат и возвращение в качестве значения функции последовательности битов, извлеченных из середины полученного числа. Предположим, что ключ есть целое 32-битное число. Тогда следующая хеш-функция извлекает средние 10 бит возведенного в квадрат ключа.

При хешировании по методу середины квадрата ключ умножается сам на себя, а адрес получается отсечением битов или цифр от обоих концов произведения, которое выполняется до тех пор, пока число оставшихся битов или цифр не станет равным требуемой длине адреса. Во всех получаемых произведениях при этом должны использоваться одни и те же позиции. В качестве примера рассмотрим шестизначный ключ 113586. При возведении его в квадрат получается 12901779396. Если требуется четырёхзначный адрес, могут быть выбраны позиции 5-8, дающие адрес 1779. Метод середины квадрата подвергался критике, но его применение к некоторым наборам ключей даёт хорошие результаты.

В методе свертывания ключ разбивается на части, каждая из которых имеет длину, равную длине требуемого адреса (кроме, возможно, последней части). Чтобы сформировать адрес, части затем складываются, при этом игнорируется перенос в старшем разряде. Если ключи представлены в двоичном виде, то вместо сложения может быть использована операция исключающего ИЛИ. Существуют различные вариации этого метода, которые лучше всего проиллюстрировать на конкретном примере ключа 187249653. В методе свертывания со сдвигом складываются 187, 249 и 653, при этом получается адрес 89.

В методе граничного свертывания инвертируются цифры в крайних частях ключа и, таким образом, в нашем примере складываются числа 781, 249 и 356, что даёт адрес 386. Свёртывание является функцией хеширования, удобной для сжатия многословных ключей и последующего перехода к другим функциям хеширования.

Преобразование системы счисления является методом хеширования, в котором делается попытка получить случайное распределение ключей по адресам в адресном пространстве. Ключ, представленный в системе счисления q (q обычно равно 2 или 10), рассматривается как число в системе счисления p, где p больше q, причем p и q – взаимно простые. Это число из системы счисления с основанием p переводится в систему счисления с основанием q и адрес формируется путём выбора правых цифр (или битов) нового числа или применением метода деления.

Напр, ключ 53047610, рассматриваемый как 53047611, переводится в десятичную систему счисления с помощью следующих  вычислений:

53047611 = 5 * 115 + 3 * 114 + 4 * 112 + 7 * 11 + 6 = 84974510.

Отсечение трех левых цифр в полученном числе дает адрес 745 в адресном пространстве {0, 1, …, 999}.

Мультипликативный метод. Весьма удобной является мультипликативная функция хеширования. Для неотрицательного целого ключа x и константы с такой, что 0<c<1, эта функция определяется в виде:   H(x) = └ m (cx mod 1) ┘ + 1.

Здесь выражение cx mod 1 обозначает дробную часть величины cx, а скобки └ ┘ - наибольшее целое, не превышающее значения заключённой между ними величины. Такая мультипликативная функция даёт хорошие результаты  при правильном выборе константы c, что трудно сделать.

Повторное хеширование. Функция повторного хеширования h(p) имеет в качестве входа один индекс в массиве и выдает другой индекс. Если ячейка массива  i = h(k) уже занята некоторой записью с другим ключом, то функция h(p) применяется к значению i для того, чтобы найти другую ячейку, куда может быть помещена эта запись.

Если ячейка hp(i) также занята, то хеширование выполняется еще раз, и проверяется ячейка hp(hp(i)).

Двойное хеширование. Первая функция хеширования h1(x1) = h1(x2) = i при x1   x2.

Вторая функция хеширования  h2(x1) ≠ h2(x2) при x1 x2

Методы разрешения коллизий. 

Разрешение коллизий "открытой адресацией" состоит в том, чтобы полностью отказаться от ссылок и просто просматривать один за другим различные элементы таблицы, пока не будут найдены ключ K или свободная позиция. Не плохо было бы иметь правило, согласно которому каждый ключ K определяет последовательность проб, т.е. последовательность позиций в таблице, которые нужно просматривать всякий раз при вставке или поиске K. Если мы, используя определяемую K последовательность проб, натолкнемся на свободную позицию, то можно сделать вывод, что K нет в таблице, так как та же последовательность проб выполняется каждый раз при обработке данного ключа. Этот общий класс методов У. Петерсон назвал открытой адресацией.(метод случайного зондирования, метод линейного зондирования, метод квадратичного зондирования)

.Метод цепочек. 

В процессе хеширования возможно появление одинаковых адресов для различных ключей. Способ разрешения таких коллизий состоит в поддерживании М связанных списков по одному на каждый возможный хеш-адрес. Все связи должны содержать поля связей и нужно образовать массив ссылок, которые будут являться головами списков HEAD[i], где i÷1→М. После хеширования ключа выполняется последовательный поиск в списке с номером h(k).

Метод раздельных цепочек

Ключ k one two three four five six seven

Адрес h(k) 3  1 4 1 5 9

Метод по рассеянной таблицей со сросшимися цепочками. Этот алгоритм позволяет отыскать в таблице из N элементов ключ k. Если ключа нет и таблица не полная, то ключ k вставляется в неё. Элементы таблицы TABLE[i], где 0≤і≤М. Эти элементы могут быть 2-х типов: заняты и свободны. Занятый узел содержит ключевое поле KEY[i], поле связи LINK[i] и т.д.

Метод сросшихся цепочек    

two

seven

one

three

five

six

four

Алгоритм для этого метода: М – размер таблицы; i – массив элементов; R – вспомогательная переменная.

Алгоритм использует хеш-функцию h(k). Для облегчения поиска свободного пространства используют R (R= М+1 для пустой таблицы). Узел TABLE[0] – всегда свободен.

Метод свертывания: Ключ разбивается на части,каждая из которых имеет длину требуемого адреса

187|249|653

Затем части складываются  и не учитывается перенос в старшем разряде

187

+ 249

  653__

1089  -результат равен 89

Метод гранич свертывания:инвертируются цифры в крайних границах ключа

78

+ 24

_356__

386- результат

Метод преобразования систем исчисления: Ключ, представленный в системе исчисления q, где q=2 или 10 обычно

p>q

возьмем число: 530476 (ключ в десятичном виде)

530476=5*115+3*114+0*113+4*112+7*111=849745

Отсекаем 3 разряда в правой части

Должно попасть в интервал 000 – 999

745-попал в интервал

(ИЗ МАТЕРИАЛА 08.04.13)

Рис.8.5. Разрешение коллизий при добавлении элементов методом цепочек

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

Рис.8.6. Разрешение коллизий при добавлении элементов методами открытой
адр
есации.

Линейное опробование сводится к последовательному перебору элементов таблицы с некоторым фиксированным шагом

a=h(key) + c*i ,

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

Квадратичное опробование отличается от линейного тем, что шаг перебора элементов не линейно зависит от номера попытки найти свободный элемент

a = h(key2) + c*i + d*i 2

Благодаря нелинейности такой адресации уменьшается число проб при большом числе ключей-синонимов.

Однако даже относительно небольшое число проб может быстро привести к выходу за адресное пространство небольшой таблицы вследствие квадратичной зависимости адреса от номера попытки.

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

a=h1(key) + i*h2(key).


 

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

81965. ПРЕС-КОНФЕРЕНЦІЯ «ВОДА – НАЙВАЖЛИВІШИЙ МІНЕРАЛ» 1.29 MB
  Мета: Розширити і збагатити знання учнів про воду, дати уявлення про значення води на планеті Земля, закріпити знання про властивості води та її народногосподарське призначення, в тому числі в рідному краї. Виховувати в учнів бережне ставлення до води та бажання зберегти запаси прісної води чистими для себе і майбутніх поколінь.
81966. Вода. Кругообіг води 248 KB
  Мета: На основі вивченого матеріалу систематизувати знання учнів про властивості води, стани води, кругообіг води, значення води в природі і для людей; формувати вміння застосовувати засвоєні знання. Розвивати вміння аналізувати природні явища, робити висновки.
81967. Земля – голуба планета. Водойми України 59.5 KB
  Повторити і розширити поняття про водойми України їх різноманітність джерело річка – її будова складові частини; озеро болото море значення та охорону; продовжувати формувати вміння учнів працювати з фізичною картою зошитом підручником; розвивати уміння логічно мислити працювати у групі...
81968. Практичне заняття «Вогонь – друг, вогонь – ворог» 69 KB
  Мета: продовжити формувати уявлення про причини виникнення пожежі в побуті та її наслідки; вчити учнів правильно діяти у випадку виникнен ня пожежі в сусідів чи на інших об’єктах; розвивати навички самозахисту; виховувати розсудливість, почуття відповідальності за свої вчинки.
81969. Хай вічно горить вогонь пам’яті 42.5 KB
  Яка б річниця визволення нашої країни від німецько-фашистських загарбників не наступала, думка про те, що настала тиша, прийшов довгожданий, вистражданий, оплачений дорогою ціною мир, бентежить душу. Зараз ми послухаємо у грамзаписі спогади учасників боїв.
81970. Вогонь — друг, вогонь — ворог (Сценарій виступу) 35.5 KB
  Через необережне поводження з вогнем щорік гинуло все більше і більше людей. Вогонь — ворог! Він залишив свої криваві сліди в історії всіх епох і народів. Тисячі міст і сіл зникли в полум’ї вогню. Безцінні твори попередніх поколінь перетворились на порох. Вогонь згубив мільйони людей.
81971. УРОК ВНЕКЛАССНОГО ЧТЕНИЯ. ИГРА «ЧТО? ГДЕ? КОГДА?» 48.5 KB
  Цели урока: проверить знания учеников, развивать логическое мышление, привлечь интерес к интеллектуальным играм, воспитывать познавательный интерес, стремление к победе. Оборудование урока: вращающийся волчек со стрелкой, круг с цифрами, десять конвертов с вопросами...
81972. Захворювання статевих органів. Венеричні хвороби. СНІД 157 KB
  Зустрічаючись люди зазвичай говорят це гарне добре слово бажаючи один одному здоров’я. А що таке здоров’я За визначенням Всесвітньої організації охорони здоров’я – це не тільки відсутність хвороб але й стан повного фізичного душевного й соціального благополуччя.
81973. Доброта та жорстокість 44.5 KB
  Мета: ознайомити дітей з поняттям «доброта», «жорстокість». Розвивати вміння творити добро, усувати прояви жорстокості в своїй поведінці. Виховувати чуйне ставлення до людей і всього навколишнього світу.