Pascal/С

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeMem, unsigned SizeEl);

inline int EmptyTable(Table *T); /* Возвращает 1 , если таблица пуста, иначе -- 0 */

int PutTable(Table *T, void *E, func f); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, void *E, T_Key Key, func f); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, void *E, T_Key Key, func f); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, void *E, T_Key Key, func f); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); //Удаление таблицы из динамической памяти

#endif

8. Хеш-таблица. Метод разрешения коллизий -- двойное хеширование.

Спецификация СД на языке Pascal:

Unit Table8;

Interface

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type ElTable=record

flag:-1..1; {flag = -1 -- элемент массива был занят}

{flag = 0 -- элемент массива свободен}

{flag = 1 -- элемент массива занят}

E:pointer;

end;

Index = 0..65520 div sizeof(ElTable);

Tbuf = array [index] of ElTable;

Tabl=record

Buf: ^Tbuf;

n: word; {количество элементов в таблице}

SizeBuf: word; {количество элементов в массиве}

SizeEl: word; {размер элемента таблицы}

end;

Func=function(var A,B: pointer):shortint; {Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах A и B. Возвращает -1, если ключ элемента по адресу A меньше ключа элемента по адресу B, 0 -- если ключи равны и +1 -- если ключ элемента по адресу A больше ключа элемента по адресу B.}

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeBuf,SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element; var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE8_H)

#define __TABLE8_H

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef ... T_Key; // Определить тип ключа

typedef struct ElTable

{

int flag; /* flag =-1 -- элемент массива был занят

flag = 0 -- элемент массива свободен

flag = 1 -- элемент массива занят */

void* E;

};

typedef struct Table

{

ElTable* Buf;

unsigned n; // Количество элементов в таблице

unsigned SizeBuf; // Количество элементов в массиве

unsigned SizeEl; // Размер элемента таблицы

};

typedef int (* func)(void*, void*); /* Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах a и b. Возвращает -1, если ключ элемента по адресу a меньше ключа элемента по адресу b, 0 -- если ключи равны и +1 -- если ключ элемента по адресу a больше ключа элемента по адресу b */

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeBuf, unsigned SizeEl);

int EmptyTable(Table *T); // Возвращает 1 , если таблица пуста, иначе -- 0

int PutTable(Table *T, void *E, func f); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, void *E, T_Key Key, func f); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, void *E, T_Key Key, func f); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, void *E, T_Key Key, func f); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); // Уничтожение таблицы

#endif

9. Хеш-таблица. Метод разрешения коллизий -- цепочки переполнения.

Спецификация СД на языке Pascal:

Unit Table9;

Interface

uses list3; {см лаб.раб. №5}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Index = 0..65520 div sizeof(List);

Tbuf = array [index] of List;

Tabl=record

Buf: ^Tbuf;

n: word; {количество элементов в таблице}

SizeBuf: word; {количество элементов в массиве}

SizeEl: word; {размер элемента таблицы}

end;

Func=function(var A,B: pointer):shortint; {Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах A и B. Возвращает -1, если ключ элемента по адресу A меньше ключа элемента по адресу B, 0 -- если ключи равны и +1 -- если ключ элемента по адресу A больше ключа элемента по адресу B.}

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeBuf,SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element; var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE -- если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE9_H)

#define __TABLE9_H

#include "list3.h" // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef ... T_Key; // Определить тип ключа

typedef struct Table

{

List* Buf;

unsigned n; // Количество элементов в таблице

unsigned SizeBuf; // Количество элементов в массиве

unsigned SizeEl; // Размер элемента таблицы

};

typedef int (* func)(void*, void*); /* Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах a и b. Возвращает -1, если ключ элемента по адресу a меньше ключа элемента по адресу b, 0 -- если ключи равны и +1 -- если ключ элемента по адресу a больше ключа элемента по адресу b */

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeBuf, unsigned SizeEl);

int EmptyTable(Table *T); // Возвращает 1 -- если таблица пуста, иначе 0

int PutTable(Table *T, void *E, func f); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, void *E, T_Key Key, func f); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, void *E, T_Key Key, func f); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, void *E, T_Key Key, func f); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); // Уничтожение таблицы

#endif

10. Хеш-таблица. Метод разрешения коллизий -- цепочки переполнения.

Спецификация СД на языке Pascal:

Unit Table10;

Interface

uses list5; {см лаб.раб. №5}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Index = 0..65520 div sizeof(List);

Tbuf = array [index] of List;

Tabl=record

Buf: ^Tbuf;

n: word; {количество элементов в таблице}

SizeBuf: word; {количество элементов в массиве}

end;

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeBuf:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе --FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE10_H)

#define __TABLE10_H

#include "list5.h" // Cмотреть лаб.раб. №5

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef ... T_Key; // Определить тип ключа

typedef struct Table

{

List* Buf;

unsigned n; // Количество элементов в таблице

unsigned SizeBuf; // Количество элементов в массиве Buf

};

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeBuf);

int EmptyTable(Table *T); // Возвращает 1 , если таблица пуста, иначе -- 0

int PutTable(Table *T, BaseType E); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, BaseType *E, T_Key Key); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, BaseType *E, T_Key Key); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, BaseType *E, T_Key Key); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); // Уничтожение таблицы

#endif

11. Хеш-таблица. Метод разрешения коллизий - дерево переполнения.

Спецификация СД на языке Pascal:

Unit Table11;

Interface

uses Tree6; {см лаб.раб. №7}

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Index = 0..65520 div sizeof(Tree);

Tbuf = array [index] of List;

Tabl=record

Buf: ^Tbuf;

n: word; {количество элементов в таблице}

SizeBuf: word; {количество элементов в массиве}

SizeEl: word; {размер элемента таблицы}

end;

Func=function(var A,B: pointer):shortint; {Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах A и B. Возвращает -1, если ключ элемента по адресу A меньше ключа элемента по адресу B, 0 -- если ключи равны и +1 -- если ключ элемента по адресу A больше ключа элемента по адресу B.}

Var TableError : 0..2;

Procedure InitTable(var T:Table; SizeBuf,SizeEl:Word);

Function EmptyTable(var T:Table):boolean; {Возвращает TRUE , если таблица пуста, иначе -- FALSE}

Function PutTable(var T:Table; El:Element; var F: Func):boolean; {Включение элемента в таблицу. Возвращает TRUE , если элемент включен в таблицу, иначе -- FALSE (если в таблице уже есть элемент с заданным ключем или нехватает памяти).}

Function GetTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Исключение элемента. Возвращает TRUE , если элемент с ключем Key был в таблице, иначе -- FALSE}

Function ReadTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Чтение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Function WriteTable(var T:Table; var El:Element; Key:T_Key;

var F: Func):boolean; {Изменение элемента. Возвращает TRUE , если элемент с ключем Key есть в таблице, иначе -- FALSE}

Procedure DoneTable(var T:Table); {Уничтожение таблицы}

Спецификация СД на языке C:

#if !defined(__TABLE11_H)

#define __TABLE11_H

#include "tree6.h" // Cмотреть лаб.раб. №7

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef ... T_Key; // Определить тип ключа

typedef struct Table

{

Tree* Buf;

unsigned n; // Количество элементов в таблице

unsigned SizeBuf; // Количество элементов в массиве Buf

unsigned SizeEl; // Размер элемента таблицы

};

typedef int (* func)(void*, void*); /* Сравнивает ключи элементов таблицы, адреса которых находятся в параметрах a и b. Возвращает -1, если ключ элемента по адресу a меньше ключа элемента по адресу b, 0 -- если ключи равны и +1 -- если ключ элемента по адресу a больше ключа элемента по адресу b */

int TableError; // 0..2

void InitTable(Table *T, unsigned SizeBuf, unsigned SizeEl);

int EmptyTable(Table *T); // Возвращает 1 , если таблица пуста, иначе -- 0

int PutTable(Table *T, void *E, func f); /* Включение элемента в таблицу. Возвращает 1 , если элемент включен в таблицу, иначе -- 0 (если в таблице уже есть элемент с заданным ключем или нехватает памяти) */

int GetTable(Table *T, void *E, T_Key Key, func f); /* Исключение элемента. Возвращает 1 , если элемент с ключем Key был в таблице, иначе -- 0 */

int ReadTable(Table *T, void *E, T_Key Key, func f); /* Чтение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

int WriteTable(Table *T, void *E, T_Key Key, func f); /* Изменение элемента. Возвращает 1 , если элемент с ключем Key есть в таблице, иначе -- 0 */

void DoneTable(Table *T); // Уничтожение таблицы

#endif

Содержание отчета

Тема лабораторной работы.

Цель работы.

Характеристика СД типа «таблица» (п.1 постановки задачи).

Индивидуальное задание.

Текст модуля для реализации СД типа «таблица», текст программы для отладки модуля, тестовые данные результат работы программы.

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

Теоретические сведения

Таблица -- это набор элементов одинаковой организации, каждый из которых можно представить в виде двойки <K,V>, где K -- ключ, а V -- тело (информационная часть) элемента. Ключ уникален для каждого элемента, т.е. в таблице нет двух элементов с одинаковыми ключами. Ключ используется для доступа к элементам при выполнении операций.

Таблица -- динамическая структура. Над таблицей определены следующие основные операции:

1. Инициализация.

2. Включение элемента.

3. Исключение элемента с заданным ключем.

4. Чтение элемента с заданным ключем.

5. Изменение элемента с заданным ключем.

6. Проверка пустоты таблицы.

7. Уничтожение таблицы.

Кардинальное число СД БД определяется по формуле

CAR(Table) = CAR(BaseType)0 + CAR(BaseType)1+… + CAR(BaseType)max ,

где CAR(BaseType) -- кардинальное число тела элемента таблицы типа BaseType, max -- количество различных ключей в таблице.

На абстрактном уровне таблица представляет собой множество.

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

Для хранения элементов неупорядоченной таблицы используется дополнительная структура данных -- линейный список (последовательный или односвязный). Элементы списка неупорядочены по значению ключа. Для поиска элемента с заданным ключем применяется алгоритм линейного или быстрого линейного поиска (в случае реализации таблицы на основе последовательного списка). При реализации таблицы на основе ПЛС включать элемент таблицы эффективнее в конец списка. Включить элемент можно только в том случае, если в таблице нет элемента с таким же ключем, поэтому операцию включения можно выполнить только после применения алгоритма поиска. Если элемента с заданным ключем в ОЛС нет, алгоритм поиска заканчивается после обработки последнего элемента ОЛС, поэтому элемент может быть включен в конец ОЛС.

Исключение элемента таблицы, реализованной на основе ОЛС вы-полняется также, как и исключение элемента ОЛС. Время выполнения операции исключения элемента в ПЛС зависит от расположения элемента. Для достижения большей эффективности при выполнении операции исключения элемента таблицы, реализованной на основе ПЛС, можно исключать последний элемент ПЛС, предварительно скопировав его на место исключаемого элемента таблицы.

Для хранения элементов упорядоченной таблицы можно использовать дополнительные структуры данных -- линейный список (последовательный или односвязный) или бинарное дерево. Если элементы таблицы расположены в линейном списке, то они упорядочиваются по возрастанию значений ключа. Для поиска элемента с заданным ключем применяются алгоритмы линейного, бинарного или блочного (в случае реализации таблицы на основе последовательного списка) поиска. После выполнения операции включения элементы списка должны остаться упорядоченными, поэтому перед выполнением операции включения необходимо найти элемент списка, после которого нужно включить элемент. При реализации таблицы на основе ПЛС включение элемента требуется перемещения всех элементов списка, расположенных правее элемента, за которым включается элемент, на одну позицию вправо. Сократить время выполнения операции включения можно путем сочетания перемещения и поиска элемента, за которым включается элемент (аналогично алгоритму сортировки вставками (см лаб.раб. №4)). Включение элемента в ОЛС не требует перемещения элементов, поэтому операцию включения элемента в таблицу можно достаточно эффективно реализовать, выполнив последовательно алгоритмы поиска и включения элемента в ОЛС.

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

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

1) вершина не имеет потомков (лист). В этом случае родитель потеряет соответствующего сына.

2) вершина имеет одного потомка. В результате исключения такой вершины сыном родителя станет потомок удаляемой вершины.

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

Алгоритм исключения:

1. Поиск подходящей легко удаляемой вершины.

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

3. Исключение из БД найденной вершины.

Хеш-таблица -- это таблица, в которой положение аi (адрес) элемента в памяти определяется с помощью некоторой функции H (хеш-функции), аргументом которой является значение ключа kj элемента. Функция хеширования определяется как отображение

H:KA, где

K={k1,k2,...,km} -- множество значений ключа;

A={a1,a2,...,an} -- адресное пространство;

m n.

Для хранения элементов хеш-таблицы может быть использована дополнительная СД -- массив, тогда аi A представляет собой индекс элемента массива. Если определена функция H(k), такая, что для любого kj, j = 1, 2,...,m, H(kj) имеет целочисленное значение из множества A, причем H(ki) H(kj), то каждый элемент таблицы с ключем k взаимнооднозначно отображается в элемент массива с индексом H(k). Доступ к записи с ключем k осуществляется в этом случае непосредственно путем вычисления значения H(k). Таблицы, для которых существует и известна такая хеш-функция, называют хеш-таблицами с прямым доступом. Время выполнения операций поиска, включения, исключения, чтения и изменения не зависит от количества элементов в таблице и определяется временем вычисления значения хеш-функции и временем доступа к элементу массива.

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

Поскольку взаимную однозначность преобразования значения ключа в индекс элемента массива в общем случае обеспечить практически невозможно (при соизмеримых значениях n и m), от требования взаимной однозначности отказываются. Это приводит к тому, что для некоторых различных значений ключа значение хеш-функции может быть одно и то же, т.е. H(ki) = H(kj). Это означает, что два элемента таблицы должны быть размещены в одном элементе массива, что невозможно. Такую ситуацию называют коллизией. Для разрешения коллизий используют различные методы. Наиболее часто используют для этого алгоритмы из двух основных групп, а именно: открытая адресация (методы двойного хеширования и линейного опробования) и метод цепочек.

В методе открытой адресации в качестве дополнительной СД используется массив, элементы которого могут содержать элементы таблицы. Каждый элемент массива имеет признак: содержит ли элемент массива элемент таблицы, содержал ли элемент массива элемент таблицы или элемент массива свободен. Для разрешения коллизий используется две хеш-функции: H1(k) и H2(a).

Алгоритм выполнения операций поиска, включения, исключения, чтения и изменения элемента таблицы с ключем kj:

1. Вычислить ai = H1(kj).

2. Если при включении в таблицу новой записи элемент массива ai или содержал ранее элемент таблицы, но в настоящее время не содержит, а при исключении содержит элемент таблицы с ключем kj, то поиск завершен. В противном случае перейти к следующему пункту.

3. Вычислить ai = H2(ai) и перейти к пункту 2.

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

Время выполнения операций над хеш-таблицей зависит от числа коллизий и времени вычисления значения хеш-функции, уменьшить которое можно путем использования «хорошей» хеш-функции. В случае целочисленного ключа в качестве хеш-функции часто применяется функция H1(k) = (C1 k + C2) mod n, где C1 и C2 -- константы, взаимно простые числа. Если ключ нецелочисленный, то одним из простых методов получения хеш-функции является выделение части цифрового кода ключа. Например, пусть m 256, тогда H1(k) в качестве значения может иметь целочисленное представление первого или последнего байта ключа или какие-либо восемь разрядов из середины ключа. Для улучшения равномерности распределения значений хеш-функции применяют сложение кода ключа: первая половина кода складывается со второй и из результата выбираются какие-либо восемь разрядов. Можно также разделить код ключа на байты, а затем сложить их по модулю 28.

В качестве функции H2(a), называемой функцией рехеширования, может быть использована H2(a) = (a + C) mod n, где C -- целочисленная константа. Если C = 1, то метод разрешения коллизий называется методом линейного опробования, иначе -- методом двойного хеширования. Недостатком метода линейного опробования является эффект первичного скучивания, который заключается в том, что при возникновении коллизии заполняются соседние элементы массива, увеличивая число проб при выполнении операции поиска. Особенностью хеш-таблиц является то, что время поиска элемента с заданным ключем не зависит от количества элементов в таблице, а зависит только от заполненности массива.

В методе цепочек элемент массива T с индексом ai содержит цепочку элементов таблицы, ключи которых отображаются хеш-функцией в значение ai. Для хранения таких цепочек элементов может быть использована дополнительная СД -- линейный список (ПЛС или ОЛС), т.о. элемент массива T представляет собой линейный список. Алгоритмы включения и исключения элементов в такую таблицу очень просты.

Алгоритм включения/исключения элемента с ключем kj в таблицу:

1. Вычислить ai = H(kj).

2. Включить/исключить элемент в линейный список T[ai].

Для ускорения поиска элементов таблицы, ключи которых отображаются хеш-функцией в одно и тоже значение ai, в качестве элемента массива может быть использована СД типа БД.

Контрольные вопросы

1. Что такое таблица? Какие операции определены над таблицами?

2. Как классифицируются таблицы в зависимости от способа размещения их элементов?

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

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

5. Что такое хеш-таблица, хеш-функция, коллизия?

6. Какие существуют методы разрешения коллизий?

7. При каком методе разрешения коллизий возможно зацикливание и как его избежать?

8. Определите порядок функции временной сложности алгоритмов выполнения операций над хеш-таблицами.



Библиографический список

1. Алексеев, В. Графы и алгоритмы. Структуры данных. Модели вычислений / В.Е. Алексеев, В.А. Талонов -- М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006. -- 320с.

2. Ахо, А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман -- М.: Изд. дом «Вильямс», 2001. -- 536 с.

3. Бакнелл, Дж. Фундаментальные алгоритмы и структуры данных в Delphi / Дж. Бакнелл -- М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006 -- 557с.

4. Вирт, Н. Алгоритмы + структуры данных = программы / Н. Вирт -- М.: Мир, 1985. - 360 с.

5. Вирт, Н. Алгоритмы и структуры данных. Новая версия для Оберона + CD : Пер. с англ. / Н. Вирт -- М.: ДМКПресс, 2010. -- 278с.

6. Зубов, В. Структуры и методы обработки данных : Практикум в среде Delphi/ В. С. Зубов, И. В. Шевченко -- М.: Информационно-издательский дом «Филинъ», 2004. -- 304с.

7. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест -- 2-е изд. -- М.: МЦНМО, 2004. -- 960 с.

8. Кнут, Д. Искусство программирования. Том 1. Основные алгоритмы: Пер. с англ. / Д. Кнут. -- 3-е изд. -- М.: Изд. дом «Вильямс», 2000. -- 720 с.

9. Кнут, Д. Искусство программирования. Том 3. Сортировка и поиск: Пер. с англ. / Д. Кнут. -- 3-е изд. -- М.: Изд. дом «Вильямс», 2000. -- 832 с.

10. Круз, Р. Структуры данных и проектирование программ : Пер. с англ. / Р. Л. Круз -- М.: Бином. Лаборатория знаний, 2008. -- 765с.

11. Седжвик, Р. Фундаментальные алгоритмы на С++. Анализ/ Структуры данных/ Сортировка/ Поиск : Пер. с англ. / Р. Седжвик -- К.: «ДиаСофт», 2001. -- 688с.

12. Хусаинов, Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си / Б.С. Хусаинов -- М.: Финансы и статистика, 2004. -- 463 с.

Размещено на Allbest.ru

...