Реализация очереди динамическим списком

Очередь может быть реализована с помощью двунаправленного списка или однонаправленного списка и дополнительного указателя на последний элемент.

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

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

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

Операции с очередью соответствуют выборке и удалению первого/последнего элемента списка и добавлению элемента после последнего/перед первым элементом списка.

27) Структуры данных. Неупорядоченные таблицы

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

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

Над таблицей можно определить следующие операции:

• включение нового элемента путем расширения таблицы или его вставки на свободное место;

• поиск элемента для последующей его обработки;

- исключение элемента из таблицы.

Неупорядоченные таблицы

Это простейший вид организации таблиц. Элементы располагаются непосредственно друг за другом, без пропусков.

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

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

Процесс удаления можно реализовать следующим образом. После локализации нужного элемента его поле текущего состояния необходимо установить в состояние «элемент удален». Тогда процесс поиска места для добавления нового элемента будет заключаться в поиске такого элемента, у которого поле текущего состояния элемента имеет значение «элемент удален» или «элемент свободен».

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

29) Структуры данных. Хеш таблица с открытым перемешиванием.

Структуры данных (абстрактные структуры) – это математические модели, предназначенные для представления информации об объектах и о процессах. Структуры хранения данных – это структуры представления информации в компьютере, с помощью которых представляются структуры данных.

Структура данных является линейной, если для любого элемента структуры, кроме первого и последнего, имеется только один последующий и только один предыдущий элемент, и первый элемент имеет только один последующий, а последний – только один предыдущий. В противном случае структура нелинейная.

ХЕШ-таблицу можно рассматривать как модификацию неупорядоченной таблицы с целью повышения эффективности поиска.

Т аблица создается на базе массива записей, который распределяется для всех групп таблицы. В группу выделяется определенное множество ключей. Разделение ключей по группам выполняется с помощью ХЕШ-функции. Аргументам функции является ключ, результат – номер группы (в некоторых случаях номер первой записи в массиве). ХЕШ-функция задается жестко и не изменяется в процессе работы с таблицей. ХЕШ-функция должна быть подобрана таким образом, чтобы ключи равномерно распределялись по группам, а для этого необходимо знать закон распределения ключей в процессе работы, что бывает очень редко. Если закон неизвестен, считают, что ключи следуют по равномерному распределению.

Операция поиска

Выполняется по массиву записей, начиная с группы, указанной ХЕШ-функцией. Операция завершается в трех случаях:

1. Ключ обнаружен (поиск успешен).

2. Обнаружена пустая запись → ключ отсутствует и текущая запись является местом добавления ключа.

3. Просмотрены все элементы таблицы → ключ отсутствует и добавлять некуда.

Массив записей закольцован, поэтому после просмотра последней записи осуществляется переход к первой.

30) Структуры данных. Хеш таблицы с цепочками переполнения.

Структуры данных (абстрактные структуры) – это математические модели, предназначенные для представления информации об объектах и о процессах. Структуры хранения данных – это структуры представления информации в компьютере, с помощью которых представляются структуры данных.

Структура данных является линейной, если для любого элемента структуры, кроме первого и последнего, имеется только один последующий и только один предыдущий элемент, и первый элемент имеет только один последующий, а последний – только один предыдущий. В противном случае структура нелинейная.

ХЕШ-таблицу можно рассматривать как модификацию неупорядоченной таблицы с целью повышения эффективности поиска.

ХЕШ-таблица с цепочками переполнения состоит из первичной таблицы и цепочек переполнения, которые реализуются динамическим списком или вторичной таблицей. Размер первичной таблицы равен числу групп. В этой таблице для каждой группы есть только одна запись. Таблица имеет три поля: ключ, информация и указатель на цепочку.

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

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

32. Структуры данных. Операции с деревьями

1. поиск вершины

2. добавление в.

3. удаление в.

4. получение полного списка вершин дерева (обход дерева)

Существует три способа обхода бинарных деревьев:

1) в прямом порядке: попасть в корень, пройти левое поддерево, пройти правое поддерево;

2) в обратном порядке: пройти левое поддерево, попасть в корень, пройти правое поддерево;

3) в концевом порядке: пройти левое поддерево, пройти правое поддерево, попасть в корень.

5. получение списка предков вершины

6. получение списка потомков вершины