Неупорядоченные таблицыЭто простейший вид организации таблиц. Элементы располагаются непосредственно друг за другом, без пропусков. Процесс поиска нужного элемента выполняется очень просто — последовательным перебором элементов таблицы начиная с первого. При этом анализируется ключевое поле и в случае удовлетворения его условию поиска нужный элемент локализуется. Такой способ поиска называется последовательным, или линейным. Для добавления нового элемента необходимо найти первое свободное место, после чего выполнить операцию добавления. Процесс удалени я можно реализовать следующим образом. После локализации нужного элемента его поле текущего состояния необходимо установить в состояние «элемент удален». Тогда процесс поиска места для добавления нового элемента будет заключаться в поиске такого элемента, у которого поле текущего состояния элемента имеет значение «элемент удален» или «элемент свободен». Можно еще более оптимизировать работу с неупорядоченной таблицей путем введения в начале таблицы (или перед ней) дескриптора, поля которого содержали бы информацию о размере таблицы, положении первого свободного элемента и т. д.
29) Структуры данных. Хеш таблица с открытым перемешиванием. Структуры данных (абстрактные структуры) – это математические модели, предназначенные для представления информации об объектах и о процессах. Структуры хранения данных – это структуры представления информации в компьютере, с помощью которых представляются структуры данных. Структура данных является линейной, если для любого элемента структуры, кроме первого и последнего, имеется только один последующий и только один предыдущий элемент, и первый элемент имеет только один последующий, а последний – только один предыдущий. В противном случае структура нелинейная. ХЕШ-таблицу можно рассматривать как модификацию неупорядоченной таблицы с целью повышения эффективности поиска.
Операция поиска Выполняется по массиву записей, начиная с группы, указанной ХЕШ-функцией. Операция завершается в трех случаях:
Массив записей закольцован, поэтому после просмотра последней записи осуществляется переход к первой.
30) Структуры данных. Хеш таблицы с цепочками переполнения. Структуры данных (абстрактные структуры) – это математические модели, предназначенные для представления информации об объектах и о процессах. Структуры хранения данных – это структуры представления информации в компьютере, с помощью которых представляются структуры данных. Структура данных является линейной, если для любого элемента структуры, кроме первого и последнего, имеется только один последующий и только один предыдущий элемент, и первый элемент имеет только один последующий, а последний – только один предыдущий. В противном случае структура нелинейная. ХЕШ-таблицу можно рассматривать как модификацию неупорядоченной таблицы с целью повышения эффективности поиска. ХЕШ-таблица с цепочками переполнения состоит из первичной таблицы и цепочек переполнения, которые реализуются динамическим списком или вторичной таблицей. Размер первичной таблицы равен числу групп. В этой таблице для каждой группы есть только одна запись. Таблица имеет три поля: ключ, информация и указатель на цепочку.
Преимуществом таблицы является обработка элементов заданной группы, а также простое удаление элемента из таблицы (удаление из списка). Недостаток: больший расход оперативной памяти, т.к. каждый элемент кроме информации содержит указатель, а в случае динамического списка к элементу добавляется служебная информация ОС.
32. Структуры данных. Операции с деревьями 1. поиск вершины 2. добавление в. 3. удаление в. 4. получение полного списка вершин дерева (обход дерева) Существует три способа обхода бинарных деревьев: 1) в прямом порядке: попасть в корень, пройти левое поддерево, пройти правое поддерево; 2) в обратном порядке: пройти левое поддерево, попасть в корень, пройти правое поддерево; 3) в концевом порядке: пройти левое поддерево, пройти правое поддерево, попасть в корень. 5. получение списка предков вершины 6. получение списка потомков вершины
Структуры данных. Древовидная таблица Дерево – это набор вершин и связей между ними (дуг), которые удовлетворяют следующим правилам:
Вершина дерева может иметь несколько или не иметь потомков. Степень вершин – количество потомков. Лист – вершина без потомков. Степень дерева – максимальная степень его вершин. Вершины дерева располагаются по уровням. Уровень – расстояние от вершины до корня. Глубина (уровень) – максимальный уровень вершины. Древовидная таблица строится на основе двоичного упорядоченного дерева, в котором ключ является кодом вершины и вершина имеет поле для хранения информации. может строится на основе динамического списка и на основе массива записей, в котором имеются поля:
33. Структуры данных. Двоичные деревья. Двоичное дерево – дерево со степенью два. Для построения дерева используется следующий типовой элемент:
Наиболее широкое распространение получило двоичное упорядоченное дерево, оно имеет упорядоченность вершин. Для каждой вершины выполняется правило: код текущей вершины больше всех вершин левого поддерева (ЛП) и меньше всех кодов вершин правого поддерева (ПП). Поиск вершины. Алгоритм поиска k – код вершины; р – указатель на текущую вершину; х – код текущей вершины; t – указатель на корень дерева. 1. p присвоить значение t. 2. Если р – пустой указатель, то вершина отсутствует, Конец 3. Значение кода текущей вершины сравнивается с искомым кодом: а) k = x, вершина найдена, Конец; б) k < x, указатель на левое поддерево; в) k > x, указатель на правое поддерево. п.2
|
Таблица создается на базе массива записей, который распределяется для всех групп таблицы. В группу выделяется определенное множество ключей. Разделение ключей по группам выполняется с помощью ХЕШ-функции. Аргументам функции является ключ, результат – номер группы (в некоторых случаях номер первой записи в массиве). ХЕШ-функция задается жестко и не изменяется в процессе работы с таблицей. ХЕШ-функция должна быть подобрана таким образом, чтобы ключи равномерно распределялись по группам, а для этого необходимо знать закон распределения ключей в процессе работы, что бывает очень редко. Если закон неизвестен, считают, что ключи следуют по равномерному распределению.
Операция поиска начинается с записи в первичной таблице или если имеется указатель на цепочку, продолжается в элементах списка. Операция может завершиться, если запись содержит искомый ключ или обнаружен конец цепочки, на что указывает пустой указатель элемента.
