Структура данных типа таблица

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

Понятие таблицы

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

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

Виды таблиц

Существует три вида таблиц: неупорядоченная, упорядоченная и хеш-таблица. Рассмотрим подробнее каждую из них.

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

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

Упорядоченная таблица

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

Хеш-таблица

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

В данной статье будет рассматриваться упорядоченная таблица с отображением на одномерный массив.

Операции над таблицей

  1. Инициализация
  2. Включение элемента с заданным ключом
  3. Исключение элемента с заданным ключом
  4. Проверка пустоты таблицы
  5. Проверка переполненности таблицы

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

Реализация таблицы

Что ж, с теорией думаю разобрались, на очереди или на стеке? — программная реализация на языке C

Файл Table_Array.h

/****************************************/
/*			Таблица на массиве			*/
/****************************************/
#ifndef _TABLE_ARRAY_
#define _TABLE_ARRAY_
/*Размер таблицы*/
#define SIZE_TABLE_ARRAY 10
/*Описание исключительных ситуаций*/
const int tableOk = 0;
const int tableEmpty = 1;
const int tableFull = 2;
const int tableNoKey = 3;
/**********************************/
/*Переменная ошибок*/
extern int errorTableArray;
/*Описание типов*/
typedef int tableArrayBaseType;					// Базовый тип данных таблицы
typedef int keyTableArrayBaseType;				// Базовый тип ключа таблицы
/*Описание типа элемента таблицы*/
typedef struct {
tableArrayBaseType date;					// Поле данных
keyTableArrayBaseType key;					// Поле ключа
} elementTableArray;
/*Дескриптор таблицы*/
typedef struct {
elementTableArray buf[SIZE_TABLE_ARRAY];	// Буфер таблицы
unsigned uk;								// Указатель
} TableArray;
/*******************/
/*Функции работы с таблицей*/
void initTableArray(TableArray *T);				// Инициализация таблицы
void putTAbleArray(TableArray *T, elementTableArray E);	// Включение элемента в таблицу
void getTableArray(TableArray *T, elementTableArray *E, keyTableArrayBaseType key);	// Исключение элемента из таблицы
int searchKey(TableArray *T, keyTableArrayBaseType key);// Поиск элемента с данным ключом
int isEmptyTableArray(TableArray *T);			// Предикат: Пуста ли таблица
int isFullTAbleArray(TableArray *T);			// Предикат: Переполнена ли таблица
/***************************/
#endif

Файл Table_Array.c

/****************************************/
/*			Таблица на массиве			*/
/****************************************/
#include <stdio.h>
#include "Table_Array.h"
/*Переменная ошибок*/
int errorTableArray;
/*Инициализация таблицы*/
void initTableArray(TableArray *T) {
T->uk = 0;
errorTableArray = tableOk;
}
/*Включение элемента в таблицу*/
void putTAbleArray(TableArray *T, elementTableArray E) {
/*Если таблица переполнена*/
if (isFullTAbleArray(T)) {
return;
}
/*Иначе, если ключ найден*/
int posElement;
/*Обновление данных*/
if ((posElement = searchKey(T, E.key)) != -1) {
T->buf[posElement].date = E.date;
}
/*Иначе включение элемента по указателю*/
else {
T->buf[T->uk] = E;											// Добавление данных
T->uk++;													// Сдвиг указателя
}
}
/*Исключение элемента из таблицы*/
void getTableArray(TableArray *T, elementTableArray *E, keyTableArrayBaseType key) {
/*Если таблина пуста*/
if (isEmptyTableArray(T)) {
return;
}
/*Иначе*/
int posElement;
if ((posElement = searchKey(T, key)) != -1)  {					// Ecли такой ключ найден
E->date = T->buf[posElement].date;							// Запись данных в переменную
E->key = T->buf[posElement].key;							// Запись ключа в переменную
if (posElement != T->uk - 1) {								// Если найденный элемент - не последний
T->buf[posElement] = T->buf[T->uk - 1];					// Запись на место найденного элемента последнего
}
T->uk--;													// Сдвиг указателя
}
}
/*Поиск элемента с данным ключом*/
int searchKey(TableArray *T, keyTableArrayBaseType key) {
unsigned i;
/*Для всех элементов таблицы выполнить поиск по ключу*/
for (i = 0; i < T->uk && T->buf[i].key != key;) {
i++;
}
if (i == T->uk) {												// Если ключ не был найден
errorTableArray = tableNoKey;								// Установка исключительной ситуации
return -1;													// Возврат -1
}
return i;														// Иначе возврат позиции элемента с таким ключом
}
/*Предикат: Пуста ли таблица*/
int isEmptyTableArray(TableArray *T) {
if (T->uk == 0) {
errorTableArray = tableEmpty;
return 1;
}
return 0;
}
/*Предикат: Переполнена ли таблица*/
int isFullTAbleArray(TableArray *T) {
if (T->uk == SIZE_TABLE_ARRAY) {
errorTableArray = tableFull;
return 1;
}
return 0;
}

Вот и все! Мы изучили еще одну структуру данных. Если что-то было не понятно, пишите в комментариях. А на этом все, удачи в программировании!

1 отзыв на “Структура данных типа таблица

  1. Guest

    Таблица описанная здесь упорядочена или нет?
    А то функция включения элемента вызывает сомнение.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *