抽象数据类型(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语言实现> P3