Файл: Отчет по лабораторной работе. Отчет по работе включает следующие пункты.pdf

Здесь начало или конец очереди можно сделать как вначале, таки в конце списка.
Кроме рассмотренных вариантов простых очередей существует понятие очереди с приоритетом. Элемент такой очереди имеет не только значение, но и весили приоритет этого значения. При включении элемента в очередь с приоритетом сначала отыскивается место элемента в соответствии сего приоритетом. Элемент с наивысшим приоритетом помещается в начало очереди, элемент с низшим весом вконец очереди. Такой очереди наилучшим образом отвечает двусвязный циклический список.
Основные операции над очередью аналогичны операциям со стеком (с учетом особенностей этой структуры.
Еще одной разновидностью этих структур данных является дек. Дек это список, у которого обе позиции начало и конец списка доступны для добавления и взятия элемента. Таким образом, дек может быть и стеком, и очередью, и комбинацией этих структур. Наиболее часто дек представляется структурой с ограничением на входили выход дек с ограниченным входом (только одна позиция доступна для добавления элемента) и дек с ограниченным выходом (только одна позиция доступна для взятия элемента из дека.
2. Контрольные вопросы
1. Понятие структуры данных стек, очередь, дек.
2. Представление в памяти структур данных стек, очередь, дек.
3. Задание структур данных стек, очередь, дек.
4. Основные операции над структурами данных стек, очередь, дек.
5. Достоинства и недостатки различного представления в памяти структур данных стек, очередь, дек.
6. Использование структур данных стек, очередь для решения задач.
3. Варианты задания
Данная лабораторная работа состоит в выполнении варианта задания из пункта 1 и пункта 2.
1. Написать операции работы с заданной структурой данных, включив их в один модуль (файл. К основным операциям (см. таблицу 1) добавить операцию, показывающую содержимое структуры после выполнения какого-либо действия с ней. Эту операцию реализовать на основе базовых операций а) основные операции над статическим стеком б) основные операции над динамическим стеком в) операция принадлежит ли заданный элемент ” статическому стеку г) операция принадлежит ли заданный элемент ” динамическому стеку д) основные операции над статической очередью (вид очереди а, б, в, г е) основные операции над динамической очередью (вид очереди а, б ж) операция добавить элемент в очередь для статической очереди с приоритетом (вид очереди а, б, в, г. На вход такой очереди подается элемент и

его приоритет, определяющий место элемента в очереди. В очереди с приоритетом элементы должны располагаться в порядке возрастания или убывания приоритетов з) операция добавить элемент в очередь для динамической очереди с приоритетом (вид очереди а, б) см. ж и) операция принадлежит ли заданный элемент ” статической очереди (вид очереди а, б, в, г к) операция принадлежит ли заданный элемент ” динамической очереди (вид очереди а, б л) основные операции над статическим деком; м) основные операции над динамическим деком.
2. Написать программу, демонстрирующую выполнение операций, над заданной структурой данных. Эту программу надо поместить в свой модуль (файл. Модуль с основными операциями включать в программу, используя директиву include.

ЛАБОРАТОРНАЯ РАБОТА СТРУКТУРЫ ДАННЫХ ДЕРЕВЬЯ
Цель работы изучить основные алгоритмы работы с деревьями получить практические навыки разработки и использования этих структур и алгоритмов для решения задач.
1. Методические указания
1.1. Понятие дерева. Виды деревьев Дерево – это конечное множество T , возможно пустое, в противном случае, состоящее из одного или более элементов (узлов или вершин дерева) таких, что а) имеется один специально обозначенный элемент, называемый корнем данного дерева б) остальные элементы содержатся в m >0 попарно непересекающихся множествах T
1
, . . . ,T
m
, каждое из которых в свою очередь является деревом деревья T
1
, . . . , T
m называются поддеревьями данного корня (риса. а б
Рис
Если имеет значение относительный порядок поддеревьев T
1
, . . . ,T
m , то говорят, что дерево является упорядоченным. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом (или листом или терминальным узлом, все остальные элементы – внутренние узлы (нетерминальные). Максимальная степень всех вершин называется степенью дерева. Корень дерева имеет уровень равный 0. Остальные вершины имеют уровень на единицу больше уровня непосредственного предка. Максимальный уровень какой-либо из вершин называется глубиной или высотой дерева. Минимальная высота при заданном числе вершин достигается, если на всех уровнях, кроме последнего, помещается максимально возможное число вершин. Максимальное число вершин в дереве высотой h достигается в том случае, если из каждой вершины, за исключением уровня h, исходят d поддеревьев, где d –
A
B
C
E
F
H J
D
G

степень дерева нам уровне 1 вершина, нам потомков, нам потомков, нам уровне d
3
потомков и т.д.
Наиболее широко используются двоичные (бинарные) деревья (рис.4.1.б). Бинарное дерево это конечное множество элементов, которое либо пусто, либо состоит из корня и из двух непересекающихся бинарных деревьев, называемых левыми правым поддеревьями данного корня. Таким образом, каждый элемент бинарного дерева имеет 0, 1 или 2 поддерева. Бинарное дерево – упорядоченное дерево, так как в нем различают левое и правое поддеревья.
Дерево поиска – это двоичное дерево, в котором выполняются следующие условия (см. риса) для всех вершин u, v, если вершина u находится в поддереве, корень которого – левый преемник v; б) l(u) > l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого – правый преемник v; в) для всякого значения a
∈ S существует единственная вершина v, для которой l(v) = a (S – множество значений, допускающих сравнения.
Рис
Определение структуры дерева, данное выше, является рекурсивными отражает рекурсивную природу самой структуры.
Структуру данных – дерево можно представить как в статической, таки в динамической памяти. В статической памяти дерево можно представить массивом, для которого определено понятие пустого элемента struct stree
{ type elem [ N ]; } stree d; или type d [ N ];
0 1 2 N-1
S
M
A
D
T
Z
X
N корень левый потомок корня правый потомок корня
. . .

Вершины двоичного дерева располагаются в массиве следующим образом если k – индекс вершины дерева, то ее потомки находятся в элементах массива с индексами 2k + 1 и 2(k + 1); корень дерева находится в элементе с индексом 0 при индексации в массиве от 1 до N индексы потомков ой вершины 2k и 2k + 1, корень имеет индекс 1).
В динамической памяти дерево представляется иерархическим списком. Задать элемент двоичного дерева можно как элемент списка стремя полями два ссылочных поля, содержащие указатели на его левое ( L ) и правое ( R ) поддеревья, и информационное поле ( E ):
Определение типа элемента бинарного динамического дерева struct btree
{type elem; btree *left, *right;} Здесь type – тип информационного поля (если информационное поле имеет сложную структуру, то type может быть типом - указатель на объект, содержащий значение элемента дерева.
Чтобы определить дерево как единую структуру, надо задать указатель на корень дерева btree * d ;
На рис представлено двоичное динамическое дерево d в cоответствии с определением типа элемента, сделанным выше. Элементы дерева со степенью 0 и 1 имеют два или одно ссылочное поле со значением равным пустому указателю
(NULL). d Рис
E L R
NULL
NULL NULL
NULL NULL
NULL
NULL NULL

Обрабатывая дерево, приходится просматривать его элементы – эта операция называется обход дерева (или прохождение дерева.
Обход дерева – это способ методичного исследования его узлов, при котором каждый узел проходится точно один раз. Полное прохождение динамического дерева дает линейную расстановку его узлов.
Возможны два способа прохождения бинарного дерева (если дерево не пусто а) в глубину
- прямой (префиксный) порядок корень, левое поддерево в прямом порядке, правое поддерево в прямом порядке (линейная расстановка узлов дерева, представленного на рис.4.1.б: ABDCEGFHJ );
Алгоритм прямого обхода
{ S = NULL; while ( d != NULL)
{ обработка ( d ); if ( d->left != NULL && d->right != NULL)
{встек (S, d->right); d = d->left;} else if ( d->left = = NULL && d->right = =NULL) if ( S!= NULL) изстека (S, d); else d = NULL; else if (d->left != NULL) d = d->left; else d = d->right;
}
}
Рекурсивное описание алгоритма прямого обхода пр_обход ( btree *d)
{ if ( d != NULL ) { обработка ( d ); пр_обход ( d->left ); пр_обход ( d->right ); }
}
- обратный (инфиксный) порядок левое поддерево в обратном порядке, корень, правое поддерево в обратном порядке (линейная расстановка узлов дерева, представленного на рис.4.1.б: DBAEGCHFJ);
Алгоритм обратного обхода
{ S = NULL; F = 1; while ( F )
{ while ( d != NULL )
{ встек ( S, d ); d = d->left; } if ( S != NULL ) { изстека ( S, d ); обработка ( d ); d = d-right;} else F = 0;
}
}
Рекурсивное описание алгоритма обратного обхода обр_обход ( btree *d )
{ if ( d != NULL ) { обр_обход ( d->left ); обработка ( d ); обр_обход ( d->right ); }
}

- концевой (постфиксный) порядок левое поддерево в концевом порядке, правое поддерево в концевом порядке, корень (линейная расстановка узлов дерева, представленного на рис.4.1.б: DBGEHJFCA);
Алгоритм концевого обхода
{ S = NULL; do while ( d != NULL )
{ встек ( S, d, 0 ); d = d->left; } if ( S != NULL )
{ do изстека ( S, d, F ); if ( F ) обработка ( d ); while ( F && S != NULL ); if ( ! F ) { встек ( S, d, 1 ); d = d->right; } while ( S != NULL );
}
Рекурсивное описание алгоритма концевого обхода конц_обход ( btree *d )
{ if ( d != NULL ) { конц_обход ( d->left ); конц_обход ( d->right ); обработка ( d ); }
} б) в ширину узлы дерева посещаются слева направо, уровень за уровнем вниз от корня (линейная расстановка узлов дерева, представленного на рис.4.1.б:
ABCDEFGHJ).
Алгоритм обхода в ширину
{ Q = NULL; if ( d != NULL ) { в_очередь ( Q, d ); do из_очереди ( Q, d ); обработка ( d ); if ( d->left != NULL ) в_очередь ( Q, d->left ); if ( d->right != NULL ) в_очередь ( Q, d->right ); while ( ! пуста_очередь ( Q ) );
}
}
Основные операции при работе с деревьями а) поиск элемента в дереве. Операция заключается в прохождении узлов дерева водном из рассмотренных выше порядке. При прохождении дерева поиска достаточно пройти только то поддерево, которое возможно содержит искомый элемент б) включение элемента в дерево. Операция заключается в добавлении листа исключая сбалансированное дерево – включение элемента в сбалансированное дерево приводит, как правило, к его перестройке) в какое-то поддерево, если такого элемента нет в исходном дереве. При включении нового элемента в дерево поиска лист добавляется в то поддерево, в котором не нарушается отношение порядка

в) удаление элемента из дерева. Операция заключается в изменении связей между дочерними и родительскими, по отношению к удаляемому, элементами (исключая сбалансированное дерево – удаление элемента из сбалансированного дерева приводит, как правило, к его перестройке здесь необходимо рассматривать три случая удаление листа (см. риса, удаление элемента с одним потомком (см. рис.4.4.б), удаление элемента с двумя потомками (см. рис.4.4.в).
При удалении элемента степени 2 из дерева поиска изменять связи необходимо так, чтобы не нарушалось установленное в дереве отношение порядка. Лучшим вариантом в этом случае будет перемещение на место удаляемого элемента либо самого правого листа из левого поддерева удаляемого элемента, либо самого левого листа из правого поддерева удаляемого элемента а б в
Рис г) сравнение деревьев (проверка деревьев на равенство. Операция заключается в прохождении обоих деревьев водном порядке до тех пор, пока либо не будут пройдены оба дерева, либо одно из них, либо соответствующие элементы окажутся неравными, либо водном из деревьев не будет обнаружено отсутствие соответствующего элемента. Только в случае равенства деревьев оба дерева будут пройдены одновременно д) копирование дерева. Операция заключается в прохождении исходного дерева и построении нового дерева с элементами, информационные поля которых равны информационным полям соответствующих элементов исходного дерева.
1.2 . Ввод дерева
Чтобы ввести дерево надо выбрать какой-то способ перечисления его узлов. Одним из возможных способов является так называемая списочная запись представление. Список – это конечная последовательность атомов либо списков, число которых, может быть и равно нулю (атом – это понятие, определяющее элемент из любого множества предметов. Используя скобки, список можно задать перечислением через запятую его атомов (порядок перечисления атомов x
x x

определяет их упорядочение. Таким образом, дерево, представленное на рис.4.1.б можно записать в виде следующего списка
( A, ( B, ( D, 0, 0 ), 0 ), ( C, ( E, 0, ( G, 0,0 ) ), ( F, ( H, 0, 0 ), ( I, 0, 0 ) )))
Ввод дерева, представленного таким списком, можно описать рекурсивной функцией (тип дерева btree описан выше, здесь type – тип информационного поля элемента – с btree * build_tree ( )
{ char sym; btree *d; scanf (“%c”, &sym ); switch ( sym )
{case ‘ (‘ : { d = new btree; scanf (“%c”, &sym ); d->elem = sym; d->left = build_tree ( ); d->right = build_tree ( ); scanf( “%c”, &sym ); return d ; } case ‘0’ : return NULL ; case ‘,’ : d = build_tree ( ); break ;
}
} Контрольные вопросы
1. Понятие дерева, двоичного дерева, упорядоченного дерева, дерева поиска.
2. Способы задания дерева.
3. Способы обхода дерева (в глубину прямой, обратный, концевой в ширину.
4. Показать, что бинарное дерево можно построить, если заданы прямой и обратный порядки расположения его узлов. Можно ли это сделать, если заданы прямой и концевой порядки Если заданы обратный и концевой порядки
5. Найдите все бинарные деревья, узлы которых располагаются точно водной и той же последовательности а) в прямом и обратном порядках б) в прямом и концевом порядках в) в обратном и концевом порядках.
6. Каково наибольшее число вершин, находящихся одновременно в стеке при обходе двоичного дерева, содержащего n элементов а) в прямом, б) обратном, в) концевом порядках
2. Варианты задания
Во всех задачах тип значений элементов дерева простой. Исходное дерево после ввода распечатать водном из порядков.
1. В заданном бинарном дереве подсчитать число его листьев и напечатать их значения а) при прямом обходе дерева

б) при обратном обходе дерева в) при концевом обходе дерева г) реализуя обход, рекурсивно.
2. В заданном бинарном дереве найти первое вхождение заданного элемента и напечатать пройденные при поиске узлы дерева а) при прямом обходе дерева б) при обратном обходе дерева в) при концевом обходе дерева г) реализуя обход, рекурсивно.
3. В заданном непустом бинарном дереве найти длину (число ветвей) пути от корня до ближайшей вершины со значением равным заданному : а) при прямом обходе дерева б) реализуя обход, рекурсивно.
4. В заданном непустом бинарном дереве подсчитать число вершин на n- ом уровне, считая корень вершиной го уровня.
5. Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента.
6. Распечатать все элементы заданного непустого бинарного дерева по уровням сначала из корня дерева, затем (слева направо) из вершин, дочерних по отношению к корню, затем (слева направо) из вершин, дочерних по отношению к этим вершинами т.д.
7. Формулу вида
< формула > ::= < терминал >
⏐(< формула > < знак > < формула >)
< знак > ::= +
⏐ - ⏐ *
< терминал > ::= 0
⏐1⏐2⏐3⏐4⏐5⏐6⏐7⏐8⏐9 можно представить в виде двоичного дерева (дерева – формулы ‘):
- формула из одного терминала (цифры) представляется деревом из одной вершины (корнем) с этим терминалом
- формула вида ( f
1
s f
2
) - деревом, в котором корень – это знака левое и правое поддеревья – это соответствующие представления f
1
и f
2
: а) по заданной формуле построить дерево – формулу, обходя дерево – формулу в прямом, обратном, концевом порядке, напечатать его элементы и вычислить как целое число) значение б) проверить, является ли заданное двоичное дерево (с элементами типа char) деревом – формулой и напечатать его элементы в порядке прямого, обратного, концевого обхода в) пусть в дереве – формуле в качестве терминалов используются не только цифры, но и буквы, играющие роль переменных преобразовать заданное дерево – формулу, заменяя в нем все поддеревья, соответствующие формулами) на поддеревья, соответствующие формулами f
3
) ); распечатать преобразованное дерево в прямом, обратном, концевом порядке

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

ЛАБОРАТОРНАЯ РАБОТА УПРАВЛЕНИЕ ТАБЛИЦАМИ
Цель работы получить практические навыки организации таблиц, обработки таблиц и их использования при решении задач.
1. Методические указания
Таблица – это список состоящий из конечного множества элементов, причем каждый элемент характеризуется рядом признаков (свойств. Один из признаков, называемый ключом, позволяет отличить один элемент от другого идентифицировать элемент. Ключ может однозначно определять элемент таблицы ключи всех элементов различны) или неоднозначно (в таблице есть элементы с равными ключами.
Все действия над элементами выполняются в соответствии сих ключами по ключу элементы выбираются из таблицы и добавляются в нее.
Таблицы можно хранить как в статической, таки в динамической памяти. В данной работе рассматриваются статические таблицы. Статическая таблица отображается массивом. Статическую таблицу можно представить следующим образом (см. рис признак 1 признак 2 . . . признак m
Рис где N - максимальное количество элементов в таблице (размер таблицы n - фактическое количество элементов в таблице. Если n = N , таблица полна, если n < N , в таблице есть свободные позиции. Вместо задания n можно ввести, если это возможно, понятие пустого элемента. Пустой элемент будет определять
Либо таблицу можно представить массивом, для которого определено понятие пустого элемента. Это используется в хеш-таблице.
Задать таблицу можно следующим образом struct table
{ type elem [ N ]; int n; } элемент 1 элемент 2 элемент n
N

table T; или во втором случае type T [ N ];
Здесь type – тип элемента таблицы, который, как правило, является сложным типом.
Неупорядоченная таблица – это таблица, элементы которой располагаются в порядке их поступления в таблицу.
Упорядоченная таблица – это таблица, между элементами которой установлено отношение порядка. Это отношение, как правило, устанавливается на признаке ключ. Поэтому говорят, что таблица упорядочена по ключам элементов. Таблица упорядочена по возрастанию значений ключа, если ключ T
i
) < ключ T
i+1
) для всех i = 1, 2 , . . . , n-1
( здесь T
i
- i -й элемент таблицы T). Таблица упорядочена по убыванию значений ключа, если ключ T
i
) > ключ T
i+1
) для всех i = 1, 2, . . . , n-1.
Основные операции
1. Поиск в таблице элемента с заданным ключом.
2. Включение заданного элемента в таблицу.
3. Исключение из таблицы элемента с заданным ключом.
Различные способы организации таблиц принято сравнивать повремени выполнения в них основных операций и прежде всего повремени поиска. В неупорядоченной таблице поиск элемента в среднем будет выполнен за n/2 сравнений, так как поиск заключается в последовательном просмотре элементов таблицы ( максимальное число сравнений n ). В упорядоченной таблице кроме последовательного просмотра можно применять бинарный поиск ( поиск делением пополам ), максимальное число сравнений при котором 1 + log
2 n.
Включение элемента в неупорядоченную таблицу заключается в добавлении элемента в таблицу ( если n < N ) на очередное свободное место. Включению элемента в упорядоченную таблицу предшествует поиск места k для нового элемента с учетом отношения порядка, затем освобождение этого места ( если оно занято ) смещением всех последующих элементов, начиная с го вниз на одну позицию. Таким образом, включение в упорядоченную таблицу требует больше времени, чем в неупорядоченную таблицу.
Исключению элемента из таблицы также предшествует поиск по ключу элемента и, если элемент в таблице есть, то исключение заключается в смещении всех последующих элементов на одну позицию вверх.
Таблица с вычисляемым входом ( хеш-таблица ) – это таблица, элементы которой располагаются в соответствии с некоторой функцией расстановки
( хеш-функцией ). Функция расстановки f (ключ) вычисляет для каждого элемента таблицы по его ключу номер ( позицию ) элемента в массиве. Таким образом, диапазон значений функции f (ключ) –
0
÷ N-1 или 1 ÷ N.
Если ключ T
i
)
≠ ключи ключ ( T
i
) )
≠ f ( ключ ( T
j
) ) при i
≠ j , для всех i и j = 0, 1, 2, . . . , n , то элементы таблицы взаимно - однозначно отображаются в элементы массива. Организованная таким образом таблица

называется таблицей с прямой адресацией. Прямая адресация применима, если количество возможных ключей невелико. Если в такой таблице число реально присутствующих элементов мало по сравнению сто в таблице много пустых элементов (темного памяти тратится зря.
Если ключ ( T
i
)
≠ ключа ключ ( T
i
) ) = f ( ключ ( T
j
) ) при i
≠ j
, тонет однозначного отображения элемента таблицы в элемент массива. Эта ситуация называется коллизией (столкновением. Если заранее неизвестен диапазон значений ключа, то выбрать функцию расстановки, дающую однозначное отображение практически невозможно. В таких таблицах возникает проблема разрешения коллизий, которая включает две задачи
1) выбор функции расстановки
2) выбор способа разрешения коллизий (способа рехеширования).
Функция расстановки подбирается в каждом случаев зависимости от ключа так, чтобы алгоритм ее вычисления был несложным. Функцию расстановки подбирают из условия случайного и возможно более равномерного отображения перемешивания) ключей в адреса хранения, но случайная хеш-функция должна быть детерминированной в том смысле, что при ее повторных вычислениях с одними тем же ключом, она должна давать одно и тоже значение.
Известно несколько методов получения хеш-функции, при этом обычно предполагают, что область определения хеш-функции – целые неотрицательные числа, если ключи не являются такими их всегда можно преобразовать к целому типу а) метод деления ключу ставится в соответствие остаток отделения назначение функции вычисляется по формуле f ( ключ ) =
ϕ ( ключ ) mod N, здесь
ϕ ( ключ ) – функция, преобразующая ключ элемента в целое число
( mod N) - означает по модулю N, те. остаток отделения на N. Здесь хорошо задавать N простым числом, плохо, если N = 2
P
или N = 10
P
б) метод умножения значение хеш-функции – это какая-то часть преобразованного значения ключа, либо часть самого значения ключа. Значение хеш-функции вычисляется по формуле f (ключ) = [N · ( ключ mod 1 )], здесь А – константа из интервала (0,1). Выбор константы зависит от исходных данных, но любое значение константы дает неплохие результаты. Выражение ( ключ mod 1 ) – это дробная часть ключ. Квадратные скобки – это взятие целой части N · (ключ mod 1). Если N = 2
m
, (степень двойки) или N = 10
P
, то операция умножения на N – сдвиг значения на m (или p) разрядов. Таким образом, значением хеш-функции будет m или p) разрядов выражения (ключ mod 1). В некоторых случаях при N = 2
m в качестве значения функции можно взять m - разрядное двоичное число либо методом выделения каких-либо m битов из значения ключа, либо применяя логическую операцию над некоторыми частями ключа, либо, разделив ключ на m частей, просуммировать их ив качестве значения функции взять младшие m разрядов (это допустимо, если эта часть ключа уникальна или повторяется редко.

Разрешать коллизии можно в исходной или в дополнительной таблице. Если в исходной, то такая таблица называется таблицей с перемешиванием или с открытой адресацией. Таблица с перемешиванием должна быть инициирована, чтобы элементы таблицы получили вначале значение пусто (при взятии элемента из такой таблицы надо различать еще одно состояние элемент удален из таблицы. В таблицах с перемешиванием применяют линейное (метод последовательных испытаний или проб, случайное или квадратичное рехеширование. Наиболее простой метод - линейное рехеширование, который заключается в том, что функция вторичной расстановки f
⎥
определяется как f
⎥
(ключ, i) = ( f (ключ) + i ) mod N , здесь значение i равно 1, 2, . . . , а f (ключ) это значение, дающее коллизию.
Рехеширование продолжается до тех пор, пока очередная позиция массива с номером f
⎥
(ключ, i) не окажется пустой или равной снова своему начальному значению ( в этом случае таблица полна ). Линейное рехеширование применяют, если таблица никогда не бывает полностью заполненной (лучше, если она заполнена не более чем на 70%).
В случае разрешения коллизии в дополнительной таблице удобно использовать хеширование с цепочками. В таких таблицах элементы, которым соответствует одно и тоже хеш-значение, связываются в цепочку – список, а в самом элементе таблицы хранится ссылка на список (см. рис.
Время поискав хеш-таблице без коллизий постоянно – это время вычисления функции расстановки. Время поискав таблицах с перемешиванием для метода линейного рехеширования зависит от коэффициента загрузки таблицы k = n/N, среднее число сравнений e = ( 1 - k/2 ) ( 1 - k). пусто пусто.