Мы уже с Вами изучили такие структуры данных, как стек, очередь и очередь с приоритетами. Однако это далеко не все структуры данных, которые можно реализовать в программе, так что не будем останавливаться на достигнутом и продолжим пополнять запас знаний. Сегодня мы будем рассматривать структуру данных типа таблица.
Таблица — набор элементов одинаковой организации, каждый из которых можно представить в виде двойки <K, V>, где K — ключ, а V — тело (информационная часть) элемента.
Ключ уникален для каждого элемента, то есть в таблице нет элементов с одинаковыми ключами. Ключ используется для доступа к элементам при выполнении операций.
Существует три вида таблиц: неупорядоченная, упорядоченная и хеш-таблица. Рассмотрим подробнее каждую из них.
Неупорядоченная таблица
Элементы такой таблицы не упорядочены по значению ключа. Для поиска элемента с заданным ключом используется алгоритм линейного или быстрого линейного поиска
Упорядоченная таблица
В такой таблице все элементы упорядочиваются по возрастанию значения ключа. Для поиска элемента с заданным ключом применяются алгоритмы линейного, бинарного или блочного поиска. После выполнения операции включения, элементы таблицы должны остаться упорядоченными, поэтому перед выполнением операции включения необходимо найти элемент, после которого нужно включить элемент.
Хеш-таблица
Хеш-таблица — это таблица, в которой положение адреса элемента определяется с помощью некоторой функции H (хеш-функции), аргументом которой является значение ключа элемента.
В данной статье будет рассматриваться упорядоченная таблица с отображением на одномерный массив.
- Инициализация
- Включение элемента с заданным ключом
- Исключение элемента с заданным ключом
- Проверка пустоты таблицы
- Проверка переполненности таблицы
Перечисленные операции — не все, которые определены над таблицей. При желании можно реализовать такие операции, как чтение, изменение элемента, а также поиск элемента по ключу.
Что ж, с теорией думаю разобрались, на очереди или на стеке? — программная реализация на языке C
Файл Table_Array.h
Файл Table_Array.c
Вот и все! Мы изучили еще одну структуру данных. Если что-то было не понятно, пишите в комментариях. А на этом все, удачи в программировании!
1 отзыв на “ Структура данных типа таблица ”
Таблица описанная здесь упорядочена или нет?
А то функция включения элемента вызывает сомнение.
