Алгоритм формирования бинарного дерева по прямой польской записи

1. Прочитать элемент ППЗ, создать корень, занести в него значение элемента.

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

Поддеревья строятся точно также, как и БД в целом.

Если выполнить обход БД (см. рис.28) в обратном порядке, то получим обратную польскую запись (ОПЗ) алгебраического выражения:

a 5 b * 3 c d * + * +

Используя ОПЗ можно сформировать БД алгебраического выражения.

Алгоритм формирования бинарного дерева по обратной польской записи

1. Пока в ОПЗ есть элементы, прочитать очередной элемент, создать корень, занести в него значение элемента.

2. Если прочитанный элемент — знак операции, то извлечь из стека адреса правого и левого поддеревьев корня.

3. Адрес корня занести в стек.

По окончании работы алгоритма стек будет содержать единственный элемент — адрес корня БД.

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

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

2. Как можно разместить бинарное дерево в памяти ЭВМ?

3. В чем заключается задача обхода бинарного дерева?

4. Опишите алгоритмы обхода бинарных деревьев.

5. Опишите алгоритмы формирования бинарных деревьев.

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

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

Л а б о р а т о р н а я р а б о т а № 8

Структуры данных «таблица» (Pascal/С)

Цель работы: изучить СД «таблица», научиться их программно реализовывать и использовать.

З а д а н и е

1. Для СД «таблица» определить:

1.1. Абстрактный уровень представления СД:

1.1.1. Характер организованности и изменчивости.

1.1.2. Набор допустимых операций.

1.2. Физический уровень представления СД:

1.2.1. Схему хранения.

1.2.2. Объем памяти, занимаемый экземпляром СД.

1.2.3. Формат внутреннего представления СД и способ

его интерпретации.

1.2.4. Характеристику допустимых значений.

1.2.5. Тип доступа к элементам.

1. 3. Логический уровень представления СД:

Способ описания СД и экземпляра СД на языке программирования.

2. Реализовать СД «таблица» в соответствии с вариантом индивидуального задания (табл.18) в виде модулей на языках Pascal и С.

3. Разработать программы на языках Pascal и С для решения задачи в соответствии с вариантом индивидуального задания (см. табл.18) с использованием модулей, полученных в результате выполнения пункта 2 задания.

Таблица 18

Варианты индивидуальных заданий

Номер варианта	Номер модуля	Задача

Окончание табл.18

Задачи

1. Текст программы на некотором алгоритмическом языке может содержать символы-разделители, служебные слова, числовые константы и идентификаторы (слова, начинающиеся не с цифры и не являющиеся служебными). Вывести все идентификаторы, которые встречаются в программе.

Исходные данные: текстовые файлы, содержащие

а) текст программы;

б) символы-разделители;

в) служебные слова.

Для хранения символов-разделителей и служебных слов использовать таблицы.

2. Текст программы на некотором алгоритмическом языке может содержать символы-разделители, служебные слова, числовые константы и идентификаторы (слова, начинающиеся не с цифры и не являющиеся служебными). Все идентификаторы, используемые в программе, должны быть описаны до первого появления в тексте программы служебного слова «BEGIN». Идентификатор считать описанным, если он встречается в тексте программы до первого слова «BEGIN», причем только один раз. Вывести все идентификаторы, которые описаны более одного раза и неописанные идентификаторы.

Исходные данные: текстовые файлы, содержащие

а) текст программы;

б) символы-разделители;

в) служебные слова.

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

3. Текст программы на некотором алгоритмическом языке может содержать символы-разделители, служебные слова, числовые константы и идентификаторы (слова, начинающиеся не с цифры и не являющиеся служебными). Проверить ошибки в записи идентификаторов и констант, парность служебных слов: «BEGIN» и «END», «IF» и «THEN», «FOR» и «DO», и скобок: «(» и «)», «[» и «]». Проверку констант выполнить с помощью стандартной процедуры VAL. Для проверки парности служебных слов и символов-разделителей использовать динамический массив из KP целочисленных элементов, где KP — количество парных служебных слов и символов-разделителей. Сначала все элементы массива обнуляются. Если встречается первое слово i-й пары, то i-й элемент массива увеличивается на единицу, а если второе слово — уменьшается. После обработки текста программы все элементы массива должны быть нулевыми. Парные служебные слова и символы-разделители хранить в таблице. Ключ элемента таблицы — парное служебное слово, информационная часть содержит +i для первого слова i-й пары и –i для второго слова. Информацию о символах-разделителях и парных служебных словах прочитать из текстовых файлов.

4. Текст программы на некотором алгоритмическом языке может содержать символы-разделители, служебные слова, числовые константы и идентификаторы (слова, начинающиеся не с цифры и не являющиеся служебными). Проверить ошибки в записи идентификаторов и констант и сочетаемость рядом стоящих служебных слов, символов-разделителей, числовых констант и идентификаторов. Например, пары «BEGIN x» и «ELSE BEGIN» — сочетаемы, а пары «x BEGIN» и «BEGIN ELSE» — несочетаемы. Проверку констант выполнить с помощью стандартной процедуры VAL. Проверку сочетаемости — с помощью таблицы сочетаемости. Ключ элемента таблицы — служебное слово или символ-разделитель, информационная часть — код служебного слова или символа-разделителя и множество кодов слов, которые могут непосредственно следовать за ключевым словом. Код константы — 0, идентификатора — 1. Для констант и идентификаторов также сформировать множества кодов слов, которые могут следовать за ними. Информацию для таблицы сочетаемости прочитать из файла.

5. Вычислить алгебраическое выражение, заданное ОПЗ. Выражение может содержать константы, вещественные переменные, знаки операций: «+», «–», «*», «/» и функции «sin(x)», «cos(x)», «arctan(x)», «abs(x)», «exp(x)», «ln(x)», «sqr(x)» и «sqrt(x)». Для хранения значений переменных использовать таблицу. Ключ элемента таблицы — имя переменной, информационная часть — значение переменной. Если текущей переменной нет в таблице, то ввести значение и включить ее в таблицу. Для вычисления значения выражения использовать стек.

ОПЗ выражения b·a + 5·(b + sin(sqr(a)) имеет вид:

b a · 5 b a sqr sin + * +

6. Написать интерпретатор языка вычисления арифметических вещественных выражений, заданных ОПЗ. В языке три оператора:

1) <оператор ввода>::= <переменная> Read

2) <оператор вывода>::= <переменная> Write

3) <оператор присваивания>::= <переменная> = <ОПЗ>

В строке текста программы записывается только один оператор. ОПЗ может содержать константы, вещественные переменные и знаки операций «+», «–», «*» и «/». Для хранения значений переменных использовать таблицу. Ключ элемента таблицы — имя переменной, информационная часть — значение переменной. Если переменной, записанной в операторе вывода или в ОПЗ нет в таблице, то ошибка, иначе определить значение переменной и включить ее в таблицу. Для вычисления выражений использовать стек.

Пример текста программы на языке вычисления арифметических вещественных выражений:

a Read

b Read

c Read

d = a b * 3.5 +

e = d d * c * a + 2 /

d = a b + 2 d * e – *

d Write

e Write

7. Написать интерпретатор языка арифметических вычислений. Язык содержит команды ввода и вывода значений вещественных переменных, команду пересылки константы или значения переменной в другую переменную, арифметические команды сложения, вычитания, умножения и деления. Команды ввода (IN) и вывода (OUT) имеют один операнд, команда пересылки (MOV) — два операнда, первый из которых — имя переменной, в которую пересылается второй операнд, арифметические команды (ADD, SUB, MUL, DIV) — два операнда, в первом сохраняется результат. В каждой строке программы — одна команда. Команды и операнды разделяются пробелами. Текст программы находится в текстовом файле. Значения переменных хранятся в таблице. Ключ элемента таблицы — имя переменной, информационная часть — значение переменной. Если операнда команды ввода или первого операнда арифметических команд и команды пересылки нет в таблице, то определить его значение и занести в таблицу. Если операнда команды вывода или второго операнда арифметических команд и команды пересылки нет в таблице, то выдать сообщение об ошибке.

Пример текста программы на языке арифметических вычислений:

IN a

IN b

IN c

MOV d a

MUL d b

DIV c a

SUB b c

MUL b 3.7

ADD d b

OUT d

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

Получил триста двадцать пять рублей пятнадцать копеек.

преобразовать в файл:

Получил 325 рублей 15 копеек.

Для преобразования чисел использовать таблицу. Ключ элемента — словесное название числа («один», «два»,..., «десять», «одиннадцать»,..., «двадцать»,..., «девяносто», «сто», «двести», «триста»,..., «девятьсот»), информационная часть — числовое значение ключа. Информацию в таблицу загрузить из текстового файла.

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

Получил 325 рублей 15 копеек.

преобразовать в файл:

Получил триста двадцать пять рублей пятнадцать копеек.

Для преобразования чисел использовать таблицу. Ключ элемента — числовое значение числа («1», «2»,..., «10», «11»,..., «12»,..., «20»,..., «90», «100», «200», «300»,..., «900»), информационная часть — словесное название ключа. Информацию в таблицу загрузить из текстового файла.

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

H2O, HCl, O2, H2SO4, O4H2S, NaCl.

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

Модули

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

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

Unit Table1;

Interface

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

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

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; SizeMem, 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(__TABLE1_H)

#define __TABLE1_H

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

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

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

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

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

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

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

Unit Table2;

Interface

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

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

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; SizeMem, 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(__TABLE1_H)

#define __TABLE1_H

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

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

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

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

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

3. Упорядоченная таблица на последовательном линейном списке. Использовать алгоритм блочного поиска (см лаб.раб.№4).

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

Unit Table3;

Interface

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

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

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; SizeMem, 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(__TABLE1_H)

#define __TABLE1_H

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

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

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

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

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

4. Упорядоченная таблица на последовательном линейном списке. Использовать алгоритм бинарного поиска(см лаб.раб.№4).

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

Unit Table4;

Interface

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

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

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; SizeMem, 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(__TABLE1_H)

#define __TABLE1_H

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

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

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

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

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

5. Упорядоченная таблица на односвязном линейном списке.

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

Unit Table5;

Interface

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

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=list;

Var TableError: 0..2;

Procedure InitTable(var T:Table; SizeMem, 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(__TABLE5_H)

#define __TABLE5_H

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

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

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

int TableError; // 0..2

void InitTable(Table *T);

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

6. Упорядоченная таблица на бинарном дереве.

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

Unit Table6;

Interface

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

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=tree;

Var TableError: 0..2;

Procedure InitTable(var T:Table; SizeMem, 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(__TABLE6_H)

#define __TABLE6_H

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

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

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

int TableError; // 0..2

void InitTable(Table *T);

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

7. Упорядоченная таблица на бинарном дереве.

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

Unit Table7;

Interface

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

Const TableOk = 0;

TableNotMem = 1;

TableUnder = 2;

Type Table=Tree;

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; SizeMem, 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(__TABLE7_H)

#define __TABLE7_H

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

const TableOk = 0;

const TableNotMem = 1;

const TableUnder = 2;

typedef List Table;

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

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

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. Тема лабораторной работы.

2. Цель работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CAR(Table) = CAR(BaseType)⁰ + CAR(BaseType)¹+… + CAR(BaseType)^max ,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

H:K®A, где

K={k₁,k₂,...,k_m} — множество значений ключа;

A={a₁,a₂,...,a_n} — адресное пространство;

m £ n.

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

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

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

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

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

1. Вычислить a_i = H₁(k_j).

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

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

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

Время выполнения операций над хеш-таблицей зависит от числа коллизий и времени вычисления значения хеш-функции, уменьшить которое можно путем использования «хорошей» хеш-функции. В случае целочисленного ключа в качестве хеш-функции часто применяется функция H₁(k) = (C₁ * k + C₂) mod n, где C₁ и C₂ — константы, взаимно простые числа. Если ключ нецелочисленный, то одним из простых методов получения хеш-функции является выделение части цифрового кода ключа. Например, пусть m £ 256, тогда H₁(k) в качестве значения может иметь целочисленное представление первого или последнего байта ключа или какие-либо восемь разрядов из середины ключа. Для улучшения равномерности распределения значений хеш-функции применяют сложение кода ключа: первая половина кода складывается со второй и из результата выбираются какие-либо восемь разрядов. Можно также разделить код ключа на байты, а затем сложить их по модулю 2⁸.

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

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

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

1. Вычислить a_i = H(k_j).

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

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

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

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

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

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

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

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

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

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

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