1. Задача поиска в программировании. Линейный поиск, бинарный поиск (делением пополам). Примеры на Си.
Одно из наиболее часто встречающихся в программировании действий – поиск. Дальше будем исходить из такого принципиального допущения, что группа данных, в которой необходимо отыскать заданный элемент, фиксирована. Задача данного действия заключается в поиске элемента, ключ которого равен заданному «аргументу поиска» x.
Линейный поиск.
Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева нарпаво, т. е. от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
Пример:
int LinearSearch (int *A, int l, int key);
{
int i;
for(i = 0; i < l; i++)
{
if(A[i] == key)
return i;
};
return -1; // элемент не найден
};
Бинарный поиск.
Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.
Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.
/* **** **** **** **** **** *
* читайте K&R будет вам щастие
* **** **** **** **** **** */
int BinarySearch (int ar[], int l, int key);
{
int low, high, mid;
low = 0;
high = l - 1;
while(low <= high) {
mid = (low + high)/2;
if (key < ar[mid]);
high = mid - 1;
else if(key > ar[mid])
low = mid + 1;
else
return mid;
};
return -1;
};
end;
2. Задача сортировки. Сортировки прямым выбором, прямым включением. Примеры на Си.
Сортировка – процесс перегруппировки заданного множества данных объектов в некотором определенном порядке. Цель – облегчить последующий поиск элементов.
Сортировка с помощью прямого выбора.
1) Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.
2) Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального.
3) И так далее до предпоследнего элемента.
Пример:
template<class T>
void selectSort(T a[], long size) {
long i, j, k;
T x;
for( i=0; i < size; i++) { // i - номер текущего шага
k=i; x=a[i];
for( j=i+1; j < size; j++) // цикл выбора наименьшего элемента
if ( a[j] < x ) {
k=j; x=a[j]; // k - индекс наименьшего элемента
}
a[k] = a[i]; a[i] = x; // меняем местами наименьший с a[i]
}
}
Сортировка с помощью прямого включения.
Алгоритм: элементы массива мысленно делятся на уже "готовую" и исходную последовательности. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место. В процессе поиска подходящего места для элемента х удобно, чередуя сравнения и движения по последовательности, как бы просеивать х, т. е. х сравнивается с очередным элементом aj, а затем либо х вставляется на свободное место, либо aj сдвигается вправо и процесс "уходит" влево.
Процесс просеивания может закончиться при выполнении одного из двух условий:
найден элемент aj с ключом, меньшим чем ключ у х;
достигнут левый конец готовой последовательности.
Пример:
typedef int array_type; /* или typedef char array_type;*/
void insertSort(array_type a[], int length) {
int i, j;
array_type value;
for (i = 1; i < length; i++) {
value = a[i];
for (j = i-1; (j >= 0) && (a[j] > value); j--) {
a[j+1] = a[j];
}
a[j+1] = value;
}
}
3. Понятие главного параметра и пропорциональной ему функции. Функции для оценки эффективности Алгоритма. Аннотация.
Большинство алгоритмов имеют главный параметр N который значительно влияет на время их выполнения. может быть степенью полинома, размером файла при сортировке или поиске, колвом символов в строке или некоторой другой абстрактной мерой размера рассматриваемой задачи:чаще всего он прямопропорционален величине обрабатываемого набора данных. когда таких параметров существует более одного мы часто сводим анализ к одному параметру задавая его как функцию других или рассматривая одновременно только один параметр. нашей целью является выражение ресурсных требований программ в зависимости от N с использованием математических формул.
1-большинство инструкций большинства программ запускается один раз. Время постоянно.
logN – время логарифмическое. Программа становится медленнее с ростом N.
N – линейное. Каждый входной элемент подвергается небольшой обработке
N logN – время выполнения пропорциональное N logN возникает тогда когда алгоритм решает задачу разбивая ее на меньшие подзадачи решая их независимо и затем объединяя решения.
N2 – квадратичное, полезен для практического использования для относительно небольших задач. (циклы двойного уровня вложенности?)
N3 – похожий алгоритм, который обрабатывает тройки элементов данных имеет кубическое время выполнения и применим лишь для малых задач.
2N – лишь несколько алгоритмов с экспоненциальным временем выполнения имеют практическое применение. Хотя такие алгоритмы возникают при попытке прямого решения задачи.
Главный параметр – количество данных подвергающихся операции.
О-нотация – мат запись позволяющая отбрасывать подробности при анализе алгоритмов.
Говорят что функция g(N) является o(f(N)) если существуют такие постоянные c0 и N0 что g(N) < c0 f(N) для все N> N0
Зачем:
1 чтобы ограничить ошибку возникающую при отбрасывании малых слагаемых в мат формулах
2-\\- когда не учитываются те части программы которые дают малый вклад в анализируемую сумму
3чтобы классифицировать алгоритмы согласно верхней границе их общего времени выполнения.
4. Шейкерная сортировка. Сортировка методом Шелла. Понятие устойчивой/неустойчивой сортировки.
Пузырьковая сортировка
Расположим массив сверху вниз, от нулевого элемента - к последнему.
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию...
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
template<class T>
void bubbleSort(T a[], long size) {
long i, j;
T x;
for( i=0; i < size; i++) { // i - номер прохода
for( j = size-1; j > i; j-- ) { // внутренний цикл прохода
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
}
}
}
}
Шейкерная сортировка.
Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла(особенно, если массив был отсортирован с самого начала!). Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.
Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.
Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив будет отсортирован за 1 проход, а сортировка последовательности потребует 5 проходов.
Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой".
template<class T>
void shakerSort(T a[], long size) {
long j, k = size-1;
long lb=1, ub = size-1; // границы неотсортированной части массива
T x;
do { // проход снизу вверх
for( j=ub; j>0; j-- ) {
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
k=j;
}
}
lb = k+1; // проход сверху вниз
for (j=1; j<=ub; j++) {
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
k=j;
}
}
ub = k-1;
} while ( lb < ub );
}
Сортировка методом Шелла
Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.
Рассмотрим следующий алгоритм сортировки массива a[0].. a[15].
1. Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]), ... , (a[7], a[15]).
2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).
В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т. п.
3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).
4. В конце сортируем вставками все 16 элементов.
Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Так зачем нужны остальные?
Hа самом деле они продвигают элементы максимально близко к соответствующим позициям, так что в последней стадии число перемещений будет весьма невелико. Последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.
Единственной характеристикой сортировки Шелла является приращение - расстояние между сортируемыми элементами, в зависимости от прохода. В конце приращение всегда равно единице - метод завершается обычной сортировкой вставками, но именно последовательность приращений определяет рост эффективности.
template <class T>
void Shell_sort( T a[], const int n )
{
for(int step = n/2 ; step>0 ; step >>= 1){
for( int i=0; i<(n-step); ++i ){
int j = i;
while ( (j>=0) && (a[j]>a[j+step]) ){
T tmp = a[j];
a[j] = a[j+step];
a[j+step] = tmp;
--j;
}
}
}
}
Понятие устойчивой и неустойчивой сортировки.
A 1 C 9 F 1 J 9 P 9 Z 1
Предположим, что первоначально записи были отсортированы по первому ключу.
Неустойчивая сортировка по второму ключу не сохраняет этот порядок:
A 1 Z 1 F 1 C 9 P 9 J 9
А устойчивая сортировка сохраняет порядок:
A 1 F 1 Z 1 C 9 J 9 P 9
5. Понятие стека. Постфиксная и инфиксная форма записи. Представление стека посредством указанных форм. Примеры на Си.
Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (Last In — First Out, последним пришел — первым вышел). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно взять верхнюю.
Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху), выталкивание (pop) — также только из вершины стека, при этом второй сверху элемент становится верхним.
Стеки широко используются в вычислительной технике — так для отслеживания точек возврата из подпрограмм стек вызовов, который является неотъемлемой частью архитектуры большинства современных процессоров. Языки программирования высокого уровня используют стек вызовов для передачи параметров при вызове процедур.
/* interface stack. h */
void STACKinit(int N);
void STACKpush(Item);
Item STACKpop();
int STACKempty();
int STACKfull();
/* implementation stack. c */
Item *stack;
int stackp;
int stacks;
void STACKinit(int N)
{
stack = malloc(stacks = (sizeof(Item) * N));
stackp = 0;
};
void STACKpush(Item i)
{
if(stackp < stacks)
stack[stackp++] = i;
};
Item STACKpop()
{
if(stackp > 0)
return stack[--stackp];
};
int STACKempty()
{
return stackp == 0;
};
int STACKfull()
{
return stackp == stacks;
};
6. Понятие Абстрактного типа данных. Примеры использования АТД. (магазинный стек, граф, таблицы символов)
Абстрактный тип данных (АТД) - это тип данных (набор значений и совокупность операций для этих значений), доступ к которому осуществляется только через интерфейс. Программу, которая использует АТД, называется клиентом, а программа, в которой содержится спецификация этого типа данных - реализацией.
Абстра́ктный тип да́нных (АТД) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения — в этом и заключается суть абстракции. Абстрактный тип данных определяет набор независимых от конкретной реализации типа функций для оперирования его значениями.
Примерами использования АТД являются следующие структуры данных:
Магазинный стек(операции положить, взять последнее, проверка пуст или полон)
Граф(Очень общий способ представления данных)
8. Понятие очереди. Реализация очереди посредством массива и связанного списка. Примеры на Си.
О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть dequeue, при этом выбранный элемент из очереди удаляется).
Существуют два основных способа реализации очереди на языке программирования.
Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.
Переменные start и end указывают на голову и хвост очереди соответственно. При добавлении элемента в очередь переменная end уменьшается на 1 и в q[end] записывается новый элемент очереди. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично (при извлечении элемента q[start] из очереди, переменная start уменьшается на 1).
Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке. Недостатки: ограничение на максимальное количество элементов в очереди размером массива (n).
Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление\удаление элементов идет строго с соответствующих его концов.
Преимущества данного метода: размер очереди ограничен лишь объемом памяти.
Недостатки: сложнее в разработке.
/* interface queue. h */
void QUEUEinit(N); // Для варианта с массивами
void QUEUEput(Item);
Item QUEUEget();
int QUEUEfull();
int QUEUEempty();
/* implementation stack. c (array) */
Item *queue;
int begin, end;
int queues;
void QUEUEinit(int N) // Для варианта с массивами
{
queue = malloc(queues = (sizeof(Item) * (N + 1)));
};
void QUEUEput(Item i)
{
if(! QUEUEfull())
{
if(begin == queues)
begin == 0;
queue[begin] = i;
begin++;
};
};
Item QUEUEget()
{
if(! QUEUEempty())
{
Item i = queue[end];
end++;
if(end = queues)
end = 0;
}
}
int QUEUEfull()
{
return (begin == end - 1) || ((begin == queues) && (end == 1));
};
int QUEUEempty()
{
return begin == end;
};
/* implementation stack. c (list. h)*/
typedef struct queue
{
Item it;
struct queue *next;
} Queue;
Queue qbegin;
Queue qend;
void QUEUEinit(int N)
{
qbegin = qend = NULL;
}
void QUEUEput(Item i)
{
Queue tmp = malloc(sizeof(Queue));
tmp->it = i;
if(qend == NULL)
{
tmp->next = NULL;
qbegin = qend = tmp;
} else {
tmp->next = NULL;
qend->next = tmp;
qend = tmp;
};
};
Item QUEUEget()
{
if(! QUEUEempty())
{
Item it = qbegin->it;
Queue tmp = qbegin;
qbegin = tmp->next;
if(qbegin == NULL)
qend = NULL;
free (tmp);
return it;
};
};
int QUEUEfull()
{
return 0;
};
int QUEUEempty()
{
return (qbegin == NULL);
};
9. Графы: терминология, способы представления (чертеж, матрица смежности, список смежных вершин).
Граф есть некоторое множество вершин и некоторое множество рёбер, соединяющих пару различных вершин. Граф состоящий из V вершин имеет V(V-1)/2 рёбер.
Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Способы представления.
1)Чертёж
Перенесение вершин заданного графа на плоскость и вычерчивание этих вершин и соединяющих их рёбер позволяет получить чертёж графа.
2)В виде матрицы смежности:
Представление в виде матрицы смежности:
—————-
| |
| |
| |
| |
| |
—————–
Предполагается, что вершины пронумерованы в некотором порядке 1, 2, …, |V|. В таком случае представление графа представляет собой матрицу размером |V| x |V|, такую что:
A[i][j] = 1 - если есть ребро от i до j (или наоборот, если граф неориентированный).
A[i][j] = 0 - в противном случае.
3)В виде списка смежных вершин:
Представление с помощью списка смежности обеспечивает более компактное представление разреженных графов (у которых |E| много меньше |V|^2). Представление при помощи матрицы смежности предпочтительнее в случае плотных графов (когда |E| близко |V|^2) или когда необходима возможность быстро определить, имеется ребро, соединяющее две данных вершины.
Представление в виде списка смежности для приведенного примера выглядит следующим образом:
1 | -> 2 -> 5
2 | -> 1 -> 3 -> 4 -> 5
3 | -> 2 -> 4
4 | -> 2 -> 3 -> 5
5 | -> 1 -> 2 -> 4
10. Представление графа посредствам АТД-конструкции. Примеры еа Си (матрица смежности, список смежных вершин)
Представление графа через АТД - это абстрагирование, т. е. обеспечивание пользователя интерфейсом. Пользователь может выполнять действия с графами (получение св-св графа, изменение графа, подсчет), при этом пользователь не должен задумываться и реализации.
Представление графа в виде матрицы смежности.
Такое представление - это булева матрица V на V вершин. Где 1(true) - означает что эти вершины связанны между собой ребром, а 0(false) - означает отсутствие связи.
В Си это выглядит как массив[w][v] w=v, v - это вершины графа. Массив заполнен значениями 1 и 0. Где 1(true) - означает что эти вершины связанны между собой ребром, а 0(false) - означает отсутствие связи.
Представление графа ввиде спсика смежных вершин.
Применяется когда требуется отследить все вершины, связанные с данной вершиной. Т. e. при запросе вершины, мы получаем список смежных с ней вершин.
Граф преставляется в виде массива указателей на связные списки. Когда мы обращаемся к вершине - ищем соответствующую ячейку массива, которая указывает на связный список, каждый из узлов которого является смежной вершиной к выбранной вершине.
11. Классические задачи обработки графов: гамильтонов путь, эйлеров путь, задача окраски, изоморфизм, поиск кратчайших путей, самый длинный путь, мн-во независимых вершин.
Эйлеров путь: Существует ли путь, соединяющий 2 заданные вершины, который проходит через каждое ребро графа в точности 1 раз? Путь не обязательно должен быть простым – вершины можно посещать многократно. Если пути начинается из некоторой заданной вершины и возвращается в неё же – мы имеем задачу поиска Эйлерова цикла.
 |
Эйлеров Путь
Гамильтонов путь: Существует ли такой путь, что при заданных 2-х вершинах, возможно пойти из одной в другую по простому пути (каждое ребро и каждую вершину возможно посещать только один раз). Если начальная точна совпадает с конечной – имеем задачу о Гамильтоновой цикле.
Гамильтонов путь
Изоморфизм. Два графа называются изоморфными, если можно поменять метки вершин на одном из них таким образом, что бы набор ребер этого графа стал идентичным набору ребер другого графа.
Поиск кратчайшего и самого длинного путей
Рассматривается каждый возможный последующий шаг от вершины на которой вы находитесь и просчитывается необходимый путь (наикратчайший или саамы длинный.) Алгори́тм Де́йкстры
Мно-во независимых вершин: называется любое множество попарно не смежных вершин, т. е. множество вершин, порождающее пустой подграф. Независимое множество называется максимальным, если оно не является собственным подмножеством другого независимого множества, и наибольшим, если оно содержит наибольшее количество вершин.
12. Генерация графов: k-соседний граф, Эвклидов граф с близкими связями, граф транзакций, граф вызовов функций, граф со степенями разделения, интервальный граф, граф Де Бруйна. Примеры использования графов. – смотри папку «/12» в архиве
14. Хеширование. Линейное зондирование. Двойное хеширование. Понятие коэффициента загрузки. Примеры C
Хеширование: расширенный вариант поиска с использованием индексирования по ключу.
Линейное зондирование. Если можно заранее предусмотреть кол-во элементов, которые должны быть помещены в хеш-таблицу, и при наличии достаточно большой непрерывной области памяти, в которой можно хранить все ключи при некотором остающемся свободном объеме памяти, в хеш-таблице вообще не стоит использовать какие-либо связи. Существует несколько методов хранения N элементов в таблице размером MxN, при которых размещение конфликтов основывается на наличии пустых мест в таблице. Такие методы называются методами хеширования с открытой адресацией. Простейшим метод открытой адресации – линейное зондирование: при наличии конфликта мы просто проверяем следующую позицию в таблице. Обычно подобную проверку (проверяющую, содержит ли данная позиция таблицы элемент с ключом, равный ключу поиска) называется зондированием. Линейное зондирование хар. выявлением одно из 3-х возможных исходов зондирования: если позиция таблицы содержит элемент, ключ которого совпадает с искомым, имеет место попадания при поиске, в противном случае мы просто зондируем позицию таблицы со следующим по величине индексом, продолжая этот процесс до тех пор, пока не будет найден искомый ключ или пустая позиция таблицы
A S E R C H I N G X M P
A
S A
S A E
S A E R
S A C E R
S H A C E R
S H A C E R I
S H A C E R I
G S H A C E R I N
G X S H A C E R I N
G X M S H A C E R I N
G X M S H P A C E R I N
На этой диаграмме процесс выставки ключей A, S, E, R, C, H, I, N, G, X, M, P в первоначально пустую хеш-таблицу с открытой адресацией, размер которой равен 13, при использовании показанных вверху хеш-значений и разрешения конфликта за счет применения линейного зондирования. Вначале А помещается в позицию 7, затем S в позицию 3, Е – в позицию 9, после конфликта в позиции 9, R помещается в позицию10 и т. д.. При достижении правого конца: например последним выставлялся ключ P в позицию 8, а затем, после конфликта в позициях 8выполняется зондирование позиции 5.
Лемма: При разрешении конфликтов с помощью лин. Зондирвания среднее кол-во зондирований, требуемых для поиска в хех-таблице размером М, которая содержит N=αM ключей, попадания
промахи 
Точность этих выражений уменьшается с приближением значений α к 1, но этот случай не важен, т. к. лин. зондирование не использеутся в почти заполненных таблицах. Для меньших α уравнение достаточно точное. Ниже приведена таблица обобщенных значений ожидаемого кол-ва зондирования, требуемых для обнаружения попаданий и промахов при поиске с использованием лин. зондированиея.
Коэф. загрузки α | 1/2 | 2/3 | 3/4 | 9/10 |
Попадания | 1,5 | 2 | 3 | 5,5 |
Промахи | 2 | 5 | 8,5 | 55,5 |
Двойное хеширование: Основной принцип линейноего зондирования – обеспечить гарантию того, что при поиске конкретного ключа, который отображается тем же адресов в таблице. Однако когда таблица приближается к заполненному состоянию, при использовании схемы с открытой адресацией другие ключи так же исследуются. Это явление называется кластеризацией, поскольку оно связано с процессом образования кластеров. Оно может значительно замедлить линейное зондирование для почти заполненной таблицы. Одно существует ещё один способ избежать возникновение проблемы кластеризации – двойное хеширование. Основная стратегия остается прежней, что и при лин. Зондировании. Единственное отличие состоит в том, что вместо исследования каждой позиции таблицы, следующей за конфликтом, мы используем вторую хеш-функцию для получения постоянного шага, который будет использоваться для последовательности зондирования.
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
M R X S H L P A C E N I G
A S E R C H I N G X M P L
1-е и 2-е хеширование отображается в 2х строках под этим ключом. A - в 7, S – в 3, E – в 9, а R в 1 после конфликта в 9.
Release Notes:
1 – Готово
2 - Готово
3 – Заплатка из другого ответника. Ждём нормальный
4 - Готово
5 - Готово
6 - Готово
7 – Ответа нет
8 – Готово
9 - Готово
10 - Готово
11 - Готово
12 – Скан из Седжвика в отдельной папке
13 - Ждём
14 - Готово
