C语言实现通用数据结构之通用链表

C语言是一门广泛应用于低级别系统编程的语言，也是数据结构和算法学习的重要工具之一，而在C语言中实现通用数据结构的方法之一就是通用链表。

通用链表是一种使用节点来组织数据的通用数据结构，每个节点包含一定量的数据以及指向链表中下一个节点的指针，因此，它可以用来实现许多不同的数据结构，例如栈、队列、树、图、哈希表等等。

具体实现通用链表的方法如下：

步骤一：定义节点结构体

首先，我们需要定义节点（Node）结构体，它包含两个变量，data表示存储的数据，next表示指向下一个节点的指针。

typedef struct Node {
    void *data;
    struct Node *next;
} Node;

步骤二：定义链表结构体

其次，我们需要定义链表（List）结构体，它包含一个头节点（head）以及链表中节点的个数（size）。

typedef struct List {
    Node *head;
    int size;
} List;

步骤三：实现节点的创建和释放函数

接下来，我们需要实现节点的创建和释放函数。create_node()函数用来创建新节点，它需要输入一个void类型的数据，返回一个新的Node类型的节点。free_node()函数用来释放一个节点的内存，它需要输入一个Node指针。

Node *create_node(void *data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

void free_node(Node *node) {
    free(node);
}

步骤四：实现链表的创建和销毁函数

然后，我们需要实现链表的创建和销毁函数。create_list()函数用来创建新链表，它返回一个新的List类型的链表。free_list()函数用来销毁一个链表及其所有节点的内存，它需要输入一个List指针。

List *create_list() {
    List *list = (List*) malloc(sizeof(List));
    list->head = NULL;
    list->size = 0;
    return list;
}

void free_list(List *list) {
    Node *node = list->head;
    while (node != NULL) {
        Node *tmp = node;
        node = node->next;
        free_node(tmp);
    }
    free(list);
}

步骤五：实现链表的增加、删除和查找函数

接下来，我们需要实现链表的增加、删除和查找函数。add_node()函数用来在链表尾部添加一个新节点，它需要输入一个List指针以及一个void类型的数据。remove_node()函数用来从链表中删除一个节点，它需要输入一个List指针以及一个Node指针。find_node()函数用来查找链表中是否存在一个包含特定数据的节点，它需要输入一个List指针以及一个比较函数指针。

void add_node(List *list, void *data) {
    Node *node = create_node(data);
    if (list->head == NULL) {
        list->head = node;
    } else {
        Node *tmp = list->head;
        while (tmp->next != NULL) {
            tmp = tmp->next;
        }
        tmp->next = node;
    }
    list->size++;
}

void remove_node(List *list, Node *node) {
    if (list->head == node) {
        list->head = node->next;
    } else {
        Node *tmp = list->head;
        while (tmp != NULL && tmp->next != node) {
            tmp = tmp->next;
        }
        if (tmp != NULL) {
            tmp->next = node->next;
        }
    }
    free_node(node);
    list->size--;
}

Node *find_node(List *list, void *data, int (*cmp)(void*, void*)) {
    Node *node = list->head;
    while (node != NULL) {
        if ((*cmp)(node->data, data) == 0) {
            return node;
        } else {
            node = node->next;
        }
    }
    return NULL;
}

步骤六：使用示例

下面，我们通过两个使用示例来说明通用链表的用法。

在第一个示例中，我们将使用通用链表来实现栈（堆栈）数据结构。首先，我们需要定义一个简单的数据结构，包含一个整型变量num。然后，我们使用通用链表来实现栈，push()函数用来将数据压入栈中，pop()函数用来从栈中弹出数据，空栈时返回NULL。

typedef struct Item {
    int num;
} Item;

void push(List *list, int num) {
    Item *item = (Item*) malloc(sizeof(Item));
    item->num = num;
    add_node(list, item);
}

Item *pop(List *list) {
    if (list->size == 0) {
        return NULL;
    } else {
        Node *node = list->head;
        while (node->next != NULL) {
            node = node->next;
        }
        Item *item = (Item*) node->data;
        remove_node(list, node);
        return item;
    }
}

在第二个示例中，我们将使用通用链表来实现哈希表（散列表）数据结构。首先，我们需要定义一个简单的数据结构，包含一个字符串变量key和一个整型变量value。然后，我们使用通用链表来实现哈希表，insert()函数用来插入一对键值对，search()函数用来查找特定键对应的值。

typedef struct KeyValue {
    char *key;
    int value;
} KeyValue;

unsigned int hash(char *key) {
    unsigned int hash = 0;
    while (*key != '\0') {
        hash = *key + (hash << 6) + (hash << 16) - hash;
        key++;
    }
    return hash;
}

void insert(List **table, char *key, int value) {
    unsigned int index = hash(key) % MAX_TABLE_SIZE;
    KeyValue *kv = (KeyValue*) malloc(sizeof(KeyValue));
    kv->key = key;
    kv->value = value;
    if (table[index] == NULL) {
        table[index] = create_list();
    }
    add_node(table[index], kv);
}

int *search(List **table, char *key) {
    unsigned int index = hash(key) % MAX_TABLE_SIZE;
    Node *node = table[index]->head;
    while (node != NULL) {
        KeyValue *kv = (KeyValue*) node->data;
        if (strcmp(kv->key, key) == 0) {
            return &(kv->value);
        } else {
            node = node->next;
        }
    }
    return NULL;
}

以上就是完整的C语言实现通用数据结构之通用链表的攻略过程，以及两个示例的说明。当然，这只是一个简单的实现，还可以不断优化和完善，例如加入迭代器、排序、合并等操作。