当前位置：首页 > news >正文

C语言之数据结构：链表（一）

news 2025/3/19 21:10:05

个人主页：云纳星辰怀自在

座右铭：“所谓坚持，就是觉得还有希望！”

1. 链表（Linked List）

定义：链表是一种动态数据结构，由一系列节点（Node）组成，每个节点包含数据域和指针域。链表的节点在内存中不必连续存储，通过指针将节点连接起来。是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。

1.1 链表的分类

链表可以根据指针的方向和节点的连接方式分为以下几类：

1.1.1 单链表（Singly Linked List）

每个节点包含一个指向下一个节点的指针。
只能从头节点开始单向遍历。

1.1.2 双向链表（Doubly Linked List）

每个节点包含两个指针，分别指向前一个节点和后一个节点。
可以双向遍历。

1.1.3 循环链表（Circular Linked List）

单链表或双向链表的变种，尾节点的指针指向头节点。
形成一个循环结构。

基于不同组合，可以实现以下方式

单向链表和双向链表
带头链表和无头链表
循环链表和非循环链表
……

实际中最常用的还是这两种结构：无头单向非循环链表和带头双向循环链表。

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。

1.2 链表的结构

1.2.1 链表的基本结构

链表的基本结构包括：

节点（Node）：包含：数据域和指针域，存储数据和指针。节点在运行时动态生成（malloc）。

    struct Node {int data;           // 数据域struct Node *next;  // 指针域（单链表）};

头指针（Head）：指向链表的第一个节点。
尾节点（Tail）：链表的最后一个节点，其指针指向NULL（单链表）或头节点（循环链表）。

struct Node {int data;struct Node *next;
};struct Node *head = NULL;
head = (struct Node *)malloc(sizeof(struct Node));
head->data = 10;
head->next = NULL;

区别：链表可以动态扩展，但访问元素需要遍历。

注意事项：注意内存管理，避免内存泄漏。

1.2.2 链表的物理结构

链表的物理结构指的是链表在计算机内存中的实际存储方式，特点：

非连续存储：链表的节点在内存中不必连续存储，每个节点可以分散在内存的不同位置。
动态分配：链表节点通过动态内存分配（如malloc）创建，内存大小可以根据需要动态调整。
指针连接：通过指针将各个节点连接起来，形成逻辑上的线性结构。

Table 1 物理存储

No.	内存地址	数据	指针
1	0x1000	10	0x2000
2	0x2000	20	0x3000
3	0x3000	30	NULL

头指针指向0x1000。

每个节点的指针指向下一个节点的内存地址。

1.2.3 链表的数据结构

链表的数据结构指的是链表的逻辑组织形式，包括节点定义和操作方式。

1.2.3.1 链表节点定义

参考链表的基本结构中节点定义。

1.2.3.2 链表的逻辑结构

链表的逻辑结构是节点通过指针连接形成的线性序列。例如，单链表的逻辑结构如下：

Head -> [10] -> [20] -> [30] -> NULL

1.2.4 物理结构与数据结构的关系

物理结构是基础：链表的物理结构决定了链表的存储方式和内存分配方式。非连续存储和动态分配是链表灵活性的基础。

数据结构是逻辑组织：链表的数据结构定义了节点的逻辑组织方式和操作方式。通过指针连接节点，形成逻辑上的线性序列。

物理结构：节点分散在内存中，通过指针连接。
数据结构：节点通过指针形成逻辑上的链表。

1.3 链表的操作

链表的基本操作包括：

插入：在链表的头部、尾部或指定位置插入节点。
删除：删除链表的头部、尾部或指定位置的节点。
遍历：访问链表中的每个节点。
查找：在链表中查找指定数据的节点。
释放：释放链表占用的内存。

1.4 链表的实现

以“无头单向非循环链表”为例，定义一个结构体变量作为我们链表的每一个单元。那么链表的内容大致可以分为两部分，一部分是根据实际需求所要存储的信息，另一部分则是指向下一个结点【内存单元】的指针变量。为了提高链表的灵活性，我们还对存储信息的类型进行了重定义，方便后期的修改。具体代码如下：

struct NoHeadSingleListNode {int data;                           // 数据域，存储节点的数据struct NoHeadSingleListNode *next;  // 指针域，指向下一个节点
};

1.4.1 动态节点申请

动态分配内存，创建一个新的链表节点。无论是对链表内容的头插、尾插、以及指定位置的插入都需要对结点的申请，因此定义一个函数专门用来动态申请一个结点，避免代码在多个函数中的重复。首先就是像内存申请一个结构体大小的内存，注意在申请后一定要对内存函数返回的参数进行判断，若是为空则说明结点的内存空间开辟失败，最后就是对所开辟空间的内容修改了，主要是依据个人需求来编写，具体代码实现如下：

struct NoHeadSingleListNode *createNode(int data) {struct NoHeadSingleListNode *newNode = (struct NoHeadSingleListNode *)malloc(sizeof(struct NoHeadSingleListNode)); // 动态分配内存if (newNode == NULL) { // 检查内存分配是否成功printf("Memory allocation failed!\n"); // 分配失败时输出错误信息exit(1); // 退出程序}newNode->data = data; // 初始化节点的数据域newNode->next = NULL; // 初始化节点的指针域为NULLreturn newNode; // 返回新创建的节点
}

1.4.2 单链表尾插

在链表的尾部插入一个新节点。先要找到链表的最后一个结点并将其中的指针修改为所插入结构体的指针，这样便能通过这个指针找到新插入的指针。大致就是找尾和插入这两部分，要注意的是如果链表的内容为空时就无需经过找尾这个过程，直接插入便可以了。具体代码实现：

void insertAtTail(struct NoHeadSingleListNode **head, int data) {struct NoHeadSingleListNode *newNode = createNode(data); // 创建新节点if (*head == NULL) { // 如果链表为空*head = newNode; // 新节点作为头节点return; // 结束函数}struct NoHeadSingleListNode *temp = *head; // 创建一个临时指针，指向头节点while (temp->next != NULL) { // 遍历链表，直到找到最后一个节点temp = temp->next; // 移动临时指针到下一个节点}temp->next = newNode; // 将新节点插入到链表尾部}

1.4.3 单链表头插

在链表的头部插入一个新节点。只需将链表的首个指针修改成所要插入的结构体的指针，并将其指向原首个结点，代码实现：

void insertAtHead(struct NoHeadSingleListNode **head, int data) {struct NoHeadSingleListNode *newNode = createNode(data); // 创建新节点newNode->next = *head; // 新节点的next指向当前头节点*head = newNode; // 更新头指针，使其指向新节点}

1.4.4 单链表头删

删除链表的头节点。将第二个结点作为第一个结点，而将第一个结点的空间释放也无需尾删复杂，传来的参数就能直接找到第一个结点。不过要注意的一点依旧是链表的内容是否为空。与下面的尾删类似。

void deleteAtHead(struct NoHeadSingleListNode **head) {if (*head == NULL) { // 如果链表为空printf("List is empty, cannot delete!\n"); // 输出提示信息return; // 结束函数}struct NoHeadSingleListNode *temp = *head; // 保存头节点*head = (*head)->next; // 更新头指针，使其指向下一个节点free(temp); // 释放原头节点的内存}

1.4.5 单链表尾删

删除链表的尾节点。

步骤如下：

在进行尾删的处理时先要判断链表是否为空，如果为空的话尾删就没有任何意义了。
在链表不为空的情况下，再进行尾删的处理。这一部分有几种思路，无论是哪种思路，共有的部分就是将释放最后一个结点空间，主要区别在于寻找这个结点的过程不同。其中一种思路，就是找到倒数第二个结点，将其指向最后一个结点的指针置空并释放其所指向的空间也就是最后一个结点的空间。

void deleteAtTail(struct NoHeadSingleListNode **head) {if (*head == NULL) { // 如果链表为空printf("List is empty, cannot delete!\n"); // 输出提示信息return; // 结束函数}if ((*head)->next == NULL) { // 如果链表只有一个节点free(*head); // 释放头节点的内存*head = NULL; // 将头指针置为NULLreturn; // 结束函数}struct NoHeadSingleListNode *temp = *head; // 创建一个临时指针，指向头节点while (temp->next->next != NULL) { // 遍历链表，直到找到倒数第二个节点temp = temp->next; // 移动临时指针到下一个节点}free(temp->next); // 释放尾节点的内存temp->next = NULL; // 将倒数第二个节点的next置为NULL}

1.4.6 遍历链表

打印链表中所有节点的数据。代码实现：

void printList(struct NoHeadSingleListNode *head) {struct NoHeadSingleListNode *temp = head; // 创建一个临时指针，指向头节点while (temp != NULL) { // 遍历链表，直到链表结束printf("%d -> ", temp->data); // 打印当前节点的数据temp = temp->next; // 移动临时指针到下一个节点}printf("NULL\n"); // 打印NULL，表示链表结束}

1.4.7 释放链表

释放链表中所有节点的内存。代码实现：

void freeList(struct NoHeadSingleListNode *head) {struct NoHeadSingleListNode *temp; // 创建一个临时指针while (head != NULL) { // 遍历链表，直到链表结束temp = head; // 保存当前节点head = head->next; // 移动头指针到下一个节点free(temp); // 释放当前节点的内存}}

1.5 完整代码

1.5.1 <no_head_single_list.h>

#ifndef NO_HEAD_SINGLE_LIST_H
#define NO_HEAD_SINGLE_LIST_H#include <stdio.h>
#include <stdlib.h>// 链表节点结构定义struct NoHeadSingleListNode {int data;                           // 数据域，存储节点的数据struct NoHeadSingleListNode *next;  // 指针域，指向下一个节点};// 函数声明struct NoHeadSingleListNode *createNode(int data);                  // 动态节点申请void insertAtHead(struct NoHeadSingleListNode **head, int data);    // 单链表头插void insertAtTail(struct NoHeadSingleListNode **head, int data);    // 单链表尾插void deleteAtHead(struct NoHeadSingleListNode **head);              // 单链表头删void deleteAtTail(struct NoHeadSingleListNode **head);              // 单链表尾删void printList(struct NoHeadSingleListNode *head);                  // 遍历链表void freeList(struct NoHeadSingleListNode *head);                   // 释放链表#endif // NO_HEAD_SINGLE_LIST_H

1.5.2 <no_head_single_list.h>

#include "no_head_single_list.h"// 动态节点申请struct NoHeadSingleListNode *createNode(int data) {struct NoHeadSingleListNode *newNode = (struct NoHeadSingleListNode *)malloc(sizeof(struct NoHeadSingleListNode)); // 动态分配内存if (newNode == NULL) { // 检查内存分配是否成功printf("Memory allocation failed!\n"); // 分配失败时输出错误信息exit(1); // 退出程序}newNode->data = data; // 初始化节点的数据域newNode->next = NULL; // 初始化节点的指针域为NULLreturn newNode; // 返回新创建的节点}// 单链表头插void insertAtHead(struct NoHeadSingleListNode **head, int data) {struct NoHeadSingleListNode *newNode = createNode(data); // 创建新节点newNode->next = *head; // 新节点的next指向当前头节点*head = newNode; // 更新头指针，使其指向新节点}// 单链表尾插void insertAtTail(struct NoHeadSingleListNode **head, int data) {struct NoHeadSingleListNode *newNode = createNode(data); // 创建新节点if (*head == NULL) { // 如果链表为空*head = newNode; // 新节点作为头节点return; // 结束函数}struct NoHeadSingleListNode *temp = *head; // 创建一个临时指针，指向头节点while (temp->next != NULL) { // 遍历链表，直到找到最后一个节点temp = temp->next; // 移动临时指针到下一个节点}temp->next = newNode; // 将新节点插入到链表尾部}// 单链表头删void deleteAtHead(struct NoHeadSingleListNode **head) {if (*head == NULL) { // 如果链表为空printf("List is empty, cannot delete!\n"); // 输出提示信息return; // 结束函数}struct NoHeadSingleListNode *temp = *head; // 保存头节点*head = (*head)->next; // 更新头指针，使其指向下一个节点free(temp); // 释放原头节点的内存}// 单链表尾删void deleteAtTail(struct NoHeadSingleListNode **head) {if (*head == NULL) { // 如果链表为空printf("List is empty, cannot delete!\n"); // 输出提示信息return; // 结束函数}if ((*head)->next == NULL) { // 如果链表只有一个节点free(*head); // 释放头节点的内存*head = NULL; // 将头指针置为NULLreturn; // 结束函数}struct NoHeadSingleListNode *temp = *head; // 创建一个临时指针，指向头节点while (temp->next->next != NULL) { // 遍历链表，直到找到倒数第二个节点temp = temp->next; // 移动临时指针到下一个节点}free(temp->next); // 释放尾节点的内存temp->next = NULL; // 将倒数第二个节点的next置为NULL}// 遍历链表void printList(struct NoHeadSingleListNode *head) {struct NoHeadSingleListNode *temp = head; // 创建一个临时指针，指向头节点while (temp != NULL) { // 遍历链表，直到链表结束printf("%d -> ", temp->data); // 打印当前节点的数据temp = temp->next; // 移动临时指针到下一个节点}printf("NULL\n"); // 打印NULL，表示链表结束}// 释放链表void freeList(struct NoHeadSingleListNode *head) {struct NoHeadSingleListNode *temp; // 创建一个临时指针while (head != NULL) { // 遍历链表，直到链表结束temp = head; // 保存当前节点head = head->next; // 移动头指针到下一个节点free(temp); // 释放当前节点的内存}}

1.5.3 <main.c>

#include "no_head_single_list.h"int main() {struct NoHeadSingleListNode *head = NULL; // 初始化链表为空// 尾插节点insertAtTail(&head, 10); // 在链表尾部插入10insertAtTail(&head, 20); // 在链表尾部插入20insertAtTail(&head, 30); // 在链表尾部插入30printf("尾插后链表: ");printList(head); // 输出: 10 -> 20 -> 30 -> NULL// 头插节点insertAtHead(&head, 5); // 在链表头部插入5insertAtHead(&head, 1); // 在链表头部插入1printf("头插后链表: ");printList(head); // 输出: 1 -> 5 -> 10 -> 20 -> 30 -> NULL// 头删节点deleteAtHead(&head); // 删除链表头部节点printf("头删后链表: ");printList(head); // 输出: 5 -> 10 -> 20 -> 30 -> NULL// 尾删节点deleteAtTail(&head); // 删除链表尾部节点printf("尾删后链表: ");printList(head); // 输出: 5 -> 10 -> 20 -> NULL// 释放链表freeList(head); // 释放链表占用的内存head = NULL; // 将头指针置为NULLreturn 0;
}