抽象数据类型(ADT)-表
抽象数据类型(ADT)
抽象数据类型（Abstract Data Type）是特定的数据及在这些数据上的操作组成的集合，像表，栈，队列，图等和它们上面的操作都是抽象数据类型，这篇我们讲表。
表
形如 A0, A1, …, An-1 的数据结构叫表，这个表大小为 n。大小为 0 的表为空表。对于任一非空表，Ai-1 是 Ai 的前驱，Ai+1 是 Ai 的后继。
表实现
表可以用数组、链表、双链表、数组游标等方式实现，这里我们介绍其数组，链表和数组游标的实现方式。
链表接口
我们使用 #define ELEMENT_TYPE int 来定义表中需要操作的数据类型，使用 typedef int POSITION; 来定义数据的位置，进而实现以下接口：
//表数据结构
typedef struct Table_Node {
ELEMENT_TYPE data;
POSITION next;
}tableNode;
//表头数据结构
typedef struct Table_Head {
tableNode* first;
unsigned int capacity;
unsigned int size;
}tableHead;
//通用接口
unsigned int getSize(tableHead* head);
void insert(tableHead* head, POSITION preNode, ELEMENT_TYPE data);
void delete(tableHead* head, ELEMENT_TYPE value);
POSITION find(tableHead* head, ELEMENT_TYPE value);
int initTableHead(tableHead* head, unsigned int capacity);
void disposeTable(tableHead* head);
ELEMENT_TYPE getValue(tableHead* head, unsigned int index);
其中可通用的接口有：
unsigned int getSize(tableHead* head)
{
if (head == NULL)
return 0;
return head->size;
}
表的数组实现
表的数组实现像 c++ 中的 vector 一样，访问元素时速度比较快，但是插入和删除时速度较慢，因为它要将插入/删除的元素后的项全部进行移动。具体接口实现如下：
void insert(tableHead* head, POSITION preNode, ELEMENT_TYPE data)
{
if (head == NULL || preNode >= (int)head->size || head->size >= head->capacity)
return ;
for (int i = head->size - 1; i > preNode && i >= 0; i--) {
head->first[i + 1].data = head->first[i].data;
}
head->first[preNode + 1].data = data;
head->size++;
}
void delete(tableHead* head, ELEMENT_TYPE value)
{
if (head == NULL)
return ;
POSITION index = find(head, value);
if (index == -1)
return ;
for (int i = index; i < head->size - 1; i++) {
head->first[i].data = head->first[i + 1].data;
}
head->size--;
}
POSITION find(tableHead* head, ELEMENT_TYPE value)
{
if (head == NULL || head->first == NULL)
return -1;
for (int i = 0; i < head->size; i++) {
if (head->first[i].data == value)
return i;
}
return -1;
}
int initTableHead(tableHead* head, unsigned int capacity)
{
if (head == NULL)
return -1;
head->first = (tableNode*) malloc(sizeof(tableNode) * capacity);
if (head->first == NULL)
return -1;
head->capacity = capacity;
head->size = 0;
return 0;
}
void disposeTable(tableHead* head)
{
if (head == NULL || head->first == NULL)
return ;
free(head->first);
head->capacity = 0;
head->size = 0;
}
ELEMENT_TYPE getValue(tableHead* head, unsigned int index)
{
if (head == NULL || index >= head->size)
return 0;
return head->first[index].data;
}
表的链表实现
链表实现时表的插入和删除操作就快很多了，因为它只需要修改两个指针即可。但是链表按索引访问的速度会比较慢，每次访问都要进行遍历操作。而且链表插入和删除时要进行内存的申请和释放。实现如下：
void insert(tableHead* head, POSITION preNode, ELEMENT_TYPE data)
{
if (head == NULL)
return ;
tableNode* node = (tableNode*) malloc(sizeof(tableNode));
if (node == NULL)
return ;
node->data = data;
if (preNode == NULL) {
node->next = head->first;
head->first = node;
} else {
node->next = preNode->next;
preNode->next = node;
}
head->size++;
}
void delete(tableHead* head, ELEMENT_TYPE value)
{
if (head == NULL)
return ;
POSITION preNode = NULL;
POSITION node = head->first;
for (; node != NULL; node = node->next) {
if (node->data == value)
break;
preNode = node;
}
if (node == NULL)
return ;
if (preNode == NULL) {
head->first = node->next;
} else {
preNode->next = node->next;
}
free(node);
head->size--;
}
POSITION find(tableHead* head, ELEMENT_TYPE value)
{
for (POSITION node = head->first; node != NULL; node = node->next) {
if (node->data == value)
return node;
}
return NULL;
}
int initTableHead(tableHead* head, unsigned int capacity)
{
if (head == NULL)
return -1;
head->first = NULL;
head->size = 0;
head->capacity = capacity;
return 0;
}
void disposeTable(tableHead* head)
{
if (head == NULL)
return ;
for (tableNode* node = head->first; node != NULL;) {
tableNode* next = node->next;
free(node);
node = next;
}
head->first = NULL;
head->size = 0;
}
ELEMENT_TYPE getValue(tableHead* head, unsigned int index)
{
if (head == NULL || index >= head->size)
return 0;
unsigned int idx = 0;
for (tableNode* node = head->first; node != NULL; node = node->next) {
if (index == idx)
return node->data;
idx++;
}
return 0;
}
表的数组游标实现
表的数组游标实现就是在每个数组项后添加下一个元素的数组游标，相当于把数组当做链表的形式来操作。在初始化表时会申请一定数量的数组项，将它以链表形式存储在一个未使用元素链表上，当插入一个元素时，会从未使用元素链表上取一项，相当于链表实现中的 malloc，然后将其挂载到已使用的链表上。当删除时，将其从已使用链表上摘除，挂载到未使用链表上，相当于 free。具体实现：
void insert(tableHead* head, POSITION preNode, ELEMENT_TYPE data)
{
if (head == NULL || head->freeHead == head->capacity)
return ;
int index = head->freeHead;
head->freeHead = head->first[index].next;
head->first[index].data = data;
if (preNode >= head->capacity) {
head->first[index].next = head->usedHead;
head->usedHead = index;
} else {
head->first[index].next = head->first[preNode].next;
head->first[preNode].next = index;
}
head->size++;
}
void delete(tableHead* head, ELEMENT_TYPE value)
{
if (head == NULL || head->first == NULL)
return ;
int preIndex = head->capacity;
int index = head->usedHead;
for (; index < head->capacity;) {
if (head->first[index].data == value)
break;
preIndex = index;
index = head->first[preIndex].next;
}
if (index == head->capacity)
return ;
if (preIndex == head->capacity)
head->usedHead = head->first[index].next;
else
head->first[preIndex].next = head->first[index].next;
head->first[index].next = head->freeHead;
head->freeHead = index;
head->size--;
}
POSITION find(tableHead* head, ELEMENT_TYPE value)
{
if (head == NULL || head->first == NULL)
return -1;
for (int i = head->usedHead; i < head->capacity;) {
if (head->first[i].data == value)
return i;
i = head->first[i].next;
}
return head->capacity;
}
int initTableHead(tableHead* head, unsigned int capacity)
{
if (head == NULL)
return -1;
head->first = (tableNode*) malloc(sizeof(tableNode) * capacity);
if (head->first == NULL)
return -1;
head->capacity = capacity;
for (int i = 0; i < capacity; i++) {
head->first[i].next = i+1;
}
head->size = 0;
head->usedHead = capacity;
head->freeHead = 0;
return 0;
}
void disposeTable(tableHead* head)
{
if (head == NULL || head->first == NULL)
return ;
free(head->first);
head->size = 0;
head->capacity = 0;
}
ELEMENT_TYPE getValue(tableHead* head, unsigned int index)
{
if (head == NULL || index >= head->size)
return 0;
unsigned int idx = 0;
for (int i = head->usedHead; i < head->capacity;) {
if (index == idx)
return head->first[i].data;
idx++;
i = head->first[i].next;
}
return 0;
}
参考：
<数据结构与算法分析-C语言实现> P3Gitalking ...