C语言数据结构实例讲解单链表的实现

单链表是一种线性的数据结构，它由一系列节点组成，每个节点都包含一个数据域和一个指向下一个节点的指针域。单链表常用于需要频繁插入删除元素的场景中。

单链表的数据结构设计

在C语言中，我们可以使用结构体来定义单链表的节点：

typedef struct node {
    int data;          // 数据域
    struct node* next; // 指针域
} Node;

其中，data表示节点存储的数据，next表示指向下一个节点的指针。

常见的单链表操作包括创建链表、插入节点、删除节点、遍历链表等。

创建链表

创建一个空链表可以使用以下代码：

Node* createList() {
    Node* head = (Node*)malloc(sizeof(Node)); // 创建头节点
    head->next = NULL;                        // 头节点不存储数据，指向NULL
    return head;
}

在创建链表时，我们首先需要创建一个头节点，通常情况下头节点不存储数据，只是为了方便操作链表。创建头节点后，将其指向NULL即可。

插入节点

可以通过以下代码在链表的指定位置插入一个节点：

int insertNode(Node* head, int index, int data) {
    Node* p = head;
    int i = 0;
    while (p && i < index - 1) { // 找到要插入位置的前一个节点
        p = p->next;
        i++;
    }
    if (!p || i > index - 1) {   // 没有找到指定位置，插入失败
        return 0;
    }
    Node* node = (Node*)malloc(sizeof(Node)); // 创建新的节点
    node->data = data;
    node->next = p->next;        // 插入节点
    p->next = node;
    return 1;
}

该函数接受三个参数：head表示链表的头节点，index表示要插入的位置，data表示要插入的数据。

在插入节点时，我们需要找到要插入位置的前一个节点，并将新节点插入前一个节点和后一个节点之间即可。

删除节点

可以使用以下代码删除链表中的指定节点：

int deleteNode(Node* head, int index) {
    Node* p = head;
    int i = 0;
    while (p && i < index - 1) { // 找到要删除节点的前一个节点
        p = p->next;
        i++;
    }
    if (!p || !p->next || i > index - 1) { // 没有找到指定节点，删除失败
        return 0;
    }
    Node* q = p->next;  // 删除节点
    p->next = q->next;
    free(q);
    return 1;
}

该函数接受两个参数：head表示链表的头节点，index表示要删除的节点位置。

在删除节点时，我们需要找到要删除节点的前一个节点，并将其指向要删除节点的下一个节点即可。

示例说明

下面通过两个示例来说明如何使用单链表实现数据结构。

示例1：实现栈

栈是一种后进先出的数据结构，通常可以使用单链表来实现。我们可以使用链表头作为栈顶。

创建栈：

Node* createStack() {
    return createList();
}

入栈操作：

void push(Node* stack, int data) {
    insertNode(stack, 1, data); // 在头节点后插入节点
}

出栈操作：

int pop(Node* stack) {
    int data = stack->next->data;
    deleteNode(stack, 1);  // 删除头节点后面的节点
    return data;
}

示例2：实现队列

队列是一种先进先出的数据结构，通常可以使用单链表来实现。我们可以使用链表尾作为队尾。

创建队列:

Node* createQueue() {
    return createList();
}

入队操作：

void enqueue(Node* queue, int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    Node* p = queue;
    while (p->next) { // 找到链表的尾部
        p = p->next;
    }
    p->next = node;  // 将节点插入到尾部
}

出队操作：

int dequeue(Node* queue) {
    int data = queue->next->data;
    deleteNode(queue, 1); // 删除头节点后的节点
    return data;
}

总结

单链表是一种重要的数据结构，对于程序员来说是必备的技能。掌握了单链表的实现原理，可以为后期的编程工作提供很大帮助。