C语言超详细讲解数据结构中的线性表

C语言超详细讲解数据结构中的线性表完整攻略

线性表的概念和基本操作

线性表是指由同类型的数据元素构成的有限序列。即每个数据元素只有一个前驱和一个后继。线性表通常用于表示一维数组、列表、队列等数据结构。

线性表的基本操作包括：

• 初始化操作：创建一个空的线性表。
• 插入操作：在线性表中插入一个元素。
• 删除操作：删除线性表中的一个元素。
• 查找操作：查找线性表中是否存在某个元素。
• 取值操作：获取线性表中某个位置的元素值。
• 输出操作：依次输出线性表中所有元素的值。

线性表的实现方式

线性表的实现方式包括：

1. 静态数组实现：使用静态数组作为线性表的存储结构，数组的大小是固定的。插入和删除操作比较麻烦，需要移动大量元素。但是，查询和访问操作非常便捷。

2. 动态数组实现：使用动态数组作为线性表的存储结构，数组的大小可以动态变化。插入和删除操作比较容易，但是查询和访问操作较慢。

3. 链表实现：使用链表作为线性表的存储结构，链表的大小可以动态变化。插入和删除操作比较容易，查询和访问操作较慢。

单链表的实现

单链表是一种链式存储结构，它由一个个结点构成，每个结点包括数据域和指针域。其中，数据域用来存储数据，指针域用来指向下一个结点。最后一个结点的指针域为 NULL。

在 C 语言中，可以使用结构体来表示单链表中的结点。同时，为了方便操作，需要定义一个指向表头结点的指针 head。

单链表的插入操作

单链表的插入操作分为两种情况：

1. 在链表的头部插入新结点。
2. 在链表的指定位置插入新结点。

下面是在链表的头部插入新结点的示例代码：

typedef struct Node {
    int data;
    struct Node* next;
} ListNode;

ListNode* head = NULL;

void insertNodeAtHead(int value) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

以上代码首先定义了一个结构体 ListNode 来表示单链表中的结点，包括数据域 data 和指针域 next。然后，定义了一个指向表头结点的指针 head，初始值为 NULL。

接着，定义了一个 insertNodeAtHead 函数用于在链表的头部插入新结点，具体实现是：

1. 创建一个新结点。
2. 将新结点的数据域赋值为要插入的值。
3. 将新结点的指针域指向当前的表头结点。
4. 将 head 指针指向新结点。

单链表的删除操作

单链表的删除操作也分为两种情况：

1. 删除链表的头结点。
2. 删除链表的指定位置的结点。

下面是删除链表的头结点的示例代码：

void deleteNodeAtHead() {
    if (head == NULL) {
        return;
    }

    ListNode* nodeToDelete = head;
    head = head->next;
    free(nodeToDelete);
}

以上代码中，首先判断链表是否为空。如果为空，则直接返回。否则，定义一个临时指针 nodeToDelete，指向当前的表头结点。然后，将 head 指针指向下一个结点，最后释放掉原来的表头结点。

另外，需要注意的是，在删除链表中的某个结点时，需要先找到该结点的前一个结点，才能进行删除操作。

双向链表的实现

双向链表是一种每个结点都包含两个指针域的链式存储结构，它们分别指向前一个结点和后一个结点。与单向链表不同的是，双向链表可以从前向后遍历，也可以从后向前遍历。

在双向链表中，每个结点的定义需要增加一个指针域，用于指向前一个结点。同时，为了便于操作，需要定义两个指针 head 和 tail，分别指向表头结点和表尾结点。

双向链表的插入操作

双向链表的插入操作也分为两种情况：

1. 在链表的头部插入新结点。
2. 在链表的指定位置插入新结点。

下面是在链表的头部插入新结点的示例代码：

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} ListNode;

ListNode* head = NULL;
ListNode* tail = NULL;

void insertNodeAtHead(int value) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = value;

    if (head == NULL) {
        newNode->prev = NULL;
        newNode->next = NULL;
        head = newNode;
        tail = newNode;
    } else {
        newNode->prev = NULL;
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

以上代码首先定义了一个结构体 ListNode 来表示双向链表中的结点，包括数据域 data 和指针域 prev 和 next。然后，定义了两个指针 head 和 tail，分别表示双向链表的表头和表尾，初始值均为 NULL。

接着，定义了一个 insertNodeAtHead 函数用于在链表的头部插入新结点，具体实现是：

1. 创建一个新结点。
2. 将新结点的数据域赋值为要插入的值。
3. 如果链表为空，则将新结点设为表头和表尾。
4. 如果链表不为空，则将新结点的指针域 next 指向当前的表头结点，并将表头结点的指针域 prev 指向新结点，最后将 head 指针指向新结点。

双向链表的删除操作

双向链表的删除操作也分为两种情况：

1. 删除链表的头结点。
2. 删除链表的指定位置的结点。

下面是删除链表的头结点的示例代码：

void deleteNodeAtHead() {
    if (head == NULL) {
        return;
    } else if (head == tail) {
        free(head);
        head = NULL;
        tail = NULL;
    } else {
        ListNode* nodeToDelete = head;
        head = head->next;
        head->prev = NULL;
        free(nodeToDelete);
    }
}

以上代码中，首先判断链表是否为空。如果为空，则直接返回。否则，如果表头和表尾是同一个结点，则直接释放该结点，并将 head 和 tail 指针赋为 NULL。否则，定义一个临时指针 nodeToDelete，指向当前的表头结点。然后，将 head 指针指向下一个结点，并将下一个结点的指针域 prev 指向 NULL，最后释放掉原来的表头结点。