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

【数据结构】线性表-单链表

article 2025/1/20 21:36:48

线性表-单链表

顺序表
链表存储结构
单链表
- 初始化
- 插入数据
- - 头插法
  - 尾插法
  - 在指定位置插入数据
- 遍历链表
- 删除节点
- 获取链表长度
- 释放链表

顺序表

上一篇文章

链表介绍：
在这里插入图片描述

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。
为了表示每个数据元素 Ai 与其直接后继数据元素 Ai+1之间的逻辑关系，对数据元素Ai来说，除了其本身的信息之外，还需要存储一个指示其直接后继的信息(直接后继的存储位置)。这两部分信息组成数据元素Ai的存储映像，称为节点(node)。
结点包括两个域:其中存储数据元素信息的称为数据域;存储直接后继存储位置有域称为指针域。指针域中存储的信息称作指针或链。
n个结点 [ A(1 ≤ i ≤ n)的存储映像 ] 链接成一个链表，即为线性表(A1,A2,…,An)。

链表存储结构

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

单链表

初始化

注意：
头节点：最开始的头节点
第一个节点：头节点指向的节点叫做第一个节点

在这里插入图片描述

对照这个图，完成单链表的初始化

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}

int main()
{
    Node *list = InitList(); // 初始化一个单链表
    printf("Hello World!\n");
    return 0;
}

插入数据

链表的插入数据有两种方式：头插法和尾插法

头插法

每次都在头节点后面插入数据

第一次插入数据

第二次插入数据

在这里插入图片描述
可以看到：每次都在头节点后面插入数据

讲解视频，演示动画：【《数据结构（C 语言描述）》也许是全站最良心最通俗易懂最好看的数据结构课（最迟每周五更新~~）】【精准空降到 1:31:50】 https://www.bilibili.com/video/BV1tNpbekEht/?p=3&share_source=copy_web&vd_source=8af85e60c2df9af1f0fd23935753a933&t=5510

头插法的步骤：

创建一个新的节点
在新节点的数据域存入数据e
新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
头节点的指针域指向新节点

/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}

如果后面已经有了数据，那么头插法的演示效果如下，先让新节点指向第一个节点，再让头节点指向新节点（这样就能防止后面的数据丢失）

在这里插入图片描述

对比：顺序表的插入是在数组里插入，每个元素都往后移动，链表的插入不是这样的，只改变节点之间的指向关系即可实现！！！

单链表：单个方向的链表
双向链表：知道下一个，也知道上一个
循环链表：构成一个环的链表

尾插法

找到尾NULL，尾节点地址，根据这个地址再插入数据。

在这里插入图片描述

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
    Node *p = List;         // 从头节点开始遍历
    while (p->next != NULL) // 遍历到链表末尾
    {
        p = p->next; // 移动到下一个节点
    }
    return p; // 返回尾节点
}
// 尾插法插入数据
Node *InsertTail(Node *tail, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    tail->next = p;                         // 尾节点的指针域指向新节点
    p->next = NULL;                         // 新节点的指针域为空
    return p;                               // 返回新的尾节点
}

完整的尾插法代码

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%d ", p->data); // 输出节点的数据域
        p = p->next;            // 移动到下一个节点
    }
    printf("\n"); // 换行
}

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
    Node *p = List;         // 从头节点开始遍历
    while (p->next != NULL) // 遍历到链表末尾
    {
        p = p->next; // 移动到下一个节点
    }
    return p; // 返回尾节点
}
// 尾插法插入数据
Node *InsertTail(Node *tail, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    tail->next = p;                         // 尾节点的指针域指向新节点
    p->next = NULL;                         // 新节点的指针域为空
    return p;                               // 返回新的尾节点
}

int main()
{
    Node *list = InitList(); // 初始化一个单链表
    printf("头插法插入数据1 2 3\n");
    InsertHead(list, 1); // 头插法插入数据1
    InsertHead(list, 2); // 头插法插入数据2
    InsertHead(list, 3); // 头插法插入数据3

    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表
    printf("\n");       // 换行

    printf("\n尾插法插入数据4 5 6\n");
    Node *tail = GetTail(list); // 获取尾节点地址
    tail = InsertTail(tail, 4); // 尾插法插入数据4
    tail = InsertTail(tail, 5); // 尾插法插入数据5
    tail = InsertTail(tail, 6); // 尾插法插入数据6
    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表

    return 0;
}

输出结果如下：

头插法插入数据1 2 3
遍历-链表中的元素为：3 2 1


尾插法插入数据4 5 6
遍历-链表中的元素为：3 2 1 4 5 6

请按任意键继续. . .

可以看到尾插法的数据是正确的！

在指定位置插入数据

在70和80中间插入一个new

在这里插入图片描述
一定要注意这个顺序，不能颠倒

**
 * @Description:单链表 - 在指定位置插入数据
 * @param {Node} *L     单链表的头节点
 * @param {int} pos     位置
 * @param {ElemType} e  插入的数据
 * @return {*}
 */
int InsertPosNode(Node *L, int pos, ElemType e)
{
    // 用来保存插入位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到插入位置的前驱节点
    while (i < pos - 1) // 遍历到插入位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("插入位置不合法\n");
            return 0;
        }
    }

    Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    newnode->data = e;                            // 在新节点的数据域存入数据e
    newnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点
    p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点
    return 1;
}

完整的演示代码：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%d ", p->data); // 输出节点的数据域
        p = p->next;            // 移动到下一个节点
    }
    printf("\n"); // 换行
}

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
    Node *p = List;         // 从头节点开始遍历
    while (p->next != NULL) // 遍历到链表末尾
    {
        p = p->next; // 移动到下一个节点
    }
    return p; // 返回尾节点
}

/**
 * @Description:单链表 - 尾插法插入数据
 * @param {Node} *tail   尾节点
 * @param {ElemType} e   插入的数据
 * @return {*}           返回新的尾节点
 */
Node *InsertTail(Node *tail, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    tail->next = p;                         // 尾节点的指针域指向新节点
    p->next = NULL;                         // 新节点的指针域为空
    return p;                               // 返回新的尾节点
}

/**
 * @Description:单链表 - 在指定位置插入数据
 * @param {Node} *L     单链表的头节点
 * @param {int} pos     位置
 * @param {ElemType} e  插入的数据
 * @return {*}
 */
int InsertPosNode(Node *L, int pos, ElemType e)
{
    // 用来保存插入位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到插入位置的前驱节点
    while (i < pos - 1) // 遍历到插入位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("插入位置不合法\n");
            return 0;
        }
    }

    Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    newnode->data = e;                            // 在新节点的数据域存入数据e
    newnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点
    p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点
    return 1;
}

int main()
{
    Node *list = InitList(); // 初始化一个单链表
    printf("头插法插入数据1 2 3\n");
    InsertHead(list, 1); // 头插法插入数据1
    InsertHead(list, 2); // 头插法插入数据2
    InsertHead(list, 3); // 头插法插入数据3

    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表
    printf("\n");       // 换行

    printf("\n尾插法插入数据4 5 6\n");
    Node *tail = GetTail(list); // 获取尾节点地址
    tail = InsertTail(tail, 4); // 尾插法插入数据4
    tail = InsertTail(tail, 5); // 尾插法插入数据5
    tail = InsertTail(tail, 6); // 尾插法插入数据6
    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表

    printf("\n在指定位置3插入数据7\n");
    InsertPosNode(list, 3, 7); // 在指定位置3插入数据7
    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表
    return 0;
}

输出结果

头插法插入数据1 2 3
遍历-链表中的元素为：3 2 1


尾插法插入数据4 5 6
遍历-链表中的元素为：3 2 1 4 5 6

在指定位置3插入数据7
遍历-链表中的元素为：3 2 7 1 4 5 6

请按任意键继续. . .

在指定位置3插入数据7，插入数据成功！

遍历链表

传入头节点的下一个节点，然后再while循环里遍历，直到指向NULL为止，输出链表的数据域内容即可

/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%d ", p->data); // 输出节点的数据域
        p = p->next;            // 移动到下一个节点
    }
    printf("\n"); // 换行
}

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%d ", p->data); // 输出节点的数据域
        p = p->next;            // 移动到下一个节点
    }
    printf("\n"); // 换行
}

int main()
{
    Node *list = InitList(); // 初始化一个单链表

    InsertHead(list, 1); // 头插法插入数据1
    InsertHead(list, 2); // 头插法插入数据2
    InsertHead(list, 3); // 头插法插入数据3

    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表

    return 0;
}

输出：

遍历-链表中的元素为：3 2 1

请按任意键继续. . .

按照头插法，依次插入 1 2 3，遍历链表输出 3 2 1，这是正确的！

删除节点

找到被删除节点的前驱节点p
用指针q记录被删除的节点
通过改变p的后继节点实现删除
释放删除节点的空间

删除操作：

/**
 * @Description:单链表 - 删除指定位置的节点
 * @param {Node} *L 单链表的头节点
 * @param {int} pos 位置
 * @return {*}       返回1表示成功
 */
int DeletePosNode(Node *L, int pos)
{
    // 用来保存删除位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到删除节点的前驱节点
    while (i < pos - 1) // 遍历到删除位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("删除位置不合法\n");
            return 0;
        }
    }
    if (p->next == NULL) // 判断删除位置是否合法
    {
        printf("删除位置不合法\n");
        return 0;
    }
    Node *q = p->next; // 保存要删除的节点的地址
    p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点
    free(q);           // 释放删除节点的内存

    return 1; // 返回1表示成功
}

完整的删除节点代码：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%d ", p->data); // 输出节点的数据域
        p = p->next;            // 移动到下一个节点
    }
    printf("\n"); // 换行
}

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
    Node *p = List;         // 从头节点开始遍历
    while (p->next != NULL) // 遍历到链表末尾
    {
        p = p->next; // 移动到下一个节点
    }
    return p; // 返回尾节点
}

/**
 * @Description:单链表 - 尾插法插入数据
 * @param {Node} *tail   尾节点
 * @param {ElemType} e   插入的数据
 * @return {*}           返回新的尾节点
 */
Node *InsertTail(Node *tail, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    tail->next = p;                         // 尾节点的指针域指向新节点
    p->next = NULL;                         // 新节点的指针域为空
    return p;                               // 返回新的尾节点
}

/**
 * @Description:单链表 - 在指定位置插入数据
 * @param {Node} *L     单链表的头节点
 * @param {int} pos     位置
 * @param {ElemType} e  插入的数据
 * @return {*}
 */
int InsertPosNode(Node *L, int pos, ElemType e)
{
    // 用来保存插入位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到插入位置的前驱节点
    while (i < pos - 1) // 遍历到插入位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("插入位置不合法\n");
            return 0;
        }
    }

    Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    newnode->data = e;                            // 在新节点的数据域存入数据e
    newnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点
    p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点
    return 1;
}

/**
 * @Description:单链表 - 删除指定位置的节点
 * @param {Node} *L 单链表的头节点
 * @param {int} pos 位置
 * @return {*}       返回1表示成功
 */
int DeletePosNode(Node *L, int pos)
{
    // 用来保存删除位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到删除节点的前驱节点
    while (i < pos - 1) // 遍历到删除位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("删除位置不合法\n");
            return 0;
        }
    }
    if (p->next == NULL) // 判断删除位置是否合法
    {
        printf("删除位置不合法\n");
        return 0;
    }
    Node *q = p->next; // 保存要删除的节点的地址
    p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点
    free(q);           // 释放删除节点的内存

    return 1; // 返回1表示成功
}

int main()
{
    Node *list = InitList(); // 初始化一个单链表
    printf("头插法插入数据1 2 3\n");
    InsertHead(list, 1); // 头插法插入数据1
    InsertHead(list, 2); // 头插法插入数据2
    InsertHead(list, 3); // 头插法插入数据3

    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表
    printf("\n");       // 换行

    printf("\n尾插法插入数据4 5 6\n");
    Node *tail = GetTail(list); // 获取尾节点地址
    tail = InsertTail(tail, 4); // 尾插法插入数据4
    tail = InsertTail(tail, 5); // 尾插法插入数据5
    tail = InsertTail(tail, 6); // 尾插法插入数据6
    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表

    printf("\n在指定位置3插入数据7\n");
    InsertPosNode(list, 3, 7); // 在指定位置3插入数据7
    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表

    printf("\n删除指定位置3的节点\n");
    DeletePosNode(list, 3); // 删除指定位置3的节点
    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表
    return 0;
}

输出结果：

头插法插入数据1 2 3
遍历-链表中的元素为：3 2 1


尾插法插入数据4 5 6
遍历-链表中的元素为：3 2 1 4 5 6

在指定位置3插入数据7
遍历-链表中的元素为：3 2 7 1 4 5 6

删除指定位置3的节点
遍历-链表中的元素为：3 2 1 4 5 6

请按任意键继续. . .

获取链表长度

int GetListLength(Node *L)
{
    int length = 0;
    Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不算在内

    while (p != NULL)
    {
        p = p->next;
        length++;
    }
    return length;
}

从头节点的下一个节点开始遍历,头节点不算在内

释放链表

保存头节点，把剩下的每一个节点的内存都释放掉

指针p指向头节点后的第一个节点
判断指针p是否指向NULL
如果p不为NULL，用指针q记录指针p的后继结点
释放指针p指向的节点
指针p和指针q指向同一个节点，循环上面的操作

释放链表代码

void FreeList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放
    Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在
    while (p != NULL)
    {
        q = p->next; // 保存下一个节点的地址
        free(p);     // 释放当前节点的内存
        p = q;       // 移动到下一个节点
    }
    L->next = NULL; // 头节点的指针域为空
}

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType; // 定义元素类型

typedef struct node // 定义节点类型
{
    ElemType data;
    struct node *next;
} Node;

/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
    head->data = 0;                            // 头节点的数据域为0
    head->next = NULL;                         // 头节点的指针域为空
    return head;                               // 返回头节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    p->next = L->next;                      // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
    L->next = p;                            // 头节点的指针域指向新节点
    return 1;                               // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历
    while (p != NULL)  // 遍历到链表末尾
    {
        printf("%d ", p->data); // 输出节点的数据域
        p = p->next;            // 移动到下一个节点
    }
    printf("\n"); // 换行
}

/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
    Node *p = List;         // 从头节点开始遍历
    while (p->next != NULL) // 遍历到链表末尾
    {
        p = p->next; // 移动到下一个节点
    }
    return p; // 返回尾节点
}

/**
 * @Description:单链表 - 尾插法插入数据
 * @param {Node} *tail   尾节点
 * @param {ElemType} e   插入的数据
 * @return {*}           返回新的尾节点
 */
Node *InsertTail(Node *tail, ElemType e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    p->data = e;                            // 在新节点的数据域存入数据e
    tail->next = p;                         // 尾节点的指针域指向新节点
    p->next = NULL;                         // 新节点的指针域为空
    return p;                               // 返回新的尾节点
}

/**
 * @Description:单链表 - 在指定位置插入数据
 * @param {Node} *L     单链表的头节点
 * @param {int} pos     位置
 * @param {ElemType} e  插入的数据
 * @return {*}
 */
int InsertPosNode(Node *L, int pos, ElemType e)
{
    // 用来保存插入位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到插入位置的前驱节点
    while (i < pos - 1) // 遍历到插入位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("插入位置不合法\n");
            return 0;
        }
    }

    Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
    newnode->data = e;                            // 在新节点的数据域存入数据e
    newnode->next = p->next;                      // 新节点的指针域指向插入位置的前驱节点的下一个节点
    p->next = newnode;                            // 插入位置的前驱节点的指针域指向新节点
    return 1;
}

/**
 * @Description:单链表 - 删除指定位置的节点
 * @param {Node} *L 单链表的头节点
 * @param {int} pos 位置
 * @return {*}       返回1表示成功
 */
int DeletePosNode(Node *L, int pos)
{
    // 用来保存删除位置的前驱节点
    Node *p = L; // 从头节点开始遍历
    int i = 0;
    // 遍历链表-找到删除节点的前驱节点
    while (i < pos - 1) // 遍历到删除位置的前驱节点
    {
        p = p->next; // 移动到下一个节点
        i++;
        if (p == NULL) // 判断是否到达链表末尾
        {
            printf("删除位置不合法\n");
            return 0;
        }
    }
    if (p->next == NULL) // 判断删除位置是否合法
    {
        printf("删除位置不合法\n");
        return 0;
    }
    Node *q = p->next; // 保存要删除的节点的地址
    p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点
    free(q);           // 释放删除节点的内存

    return 1; // 返回1表示成功
}

int GetListLength(Node *L)
{
    int length = 0;
    Node *p = L; // 从头节点开始遍历,头节点算在内

    while (p != NULL)
    {
        p = p->next;
        length++;
    }
    return length;
}

void FreeList(Node *L)
{
    Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放
    Node *q = NULL;    // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在
    while (p != NULL)
    {
        q = p->next; // 保存下一个节点的地址
        free(p);     // 释放当前节点的内存
        p = q;       // 移动到下一个节点
    }
    L->next = NULL; // 头节点的指针域为空
}

int main()
{
    Node *list = InitList(); // 初始化一个单链表
    printf("头插法插入数据1 2 3\n");
    InsertHead(list, 1); // 头插法插入数据1
    InsertHead(list, 2); // 头插法插入数据2
    InsertHead(list, 3); // 头插法插入数据3

    printf("尾插法插入数据4 5 6\n");
    Node *tail = GetTail(list); // 获取尾节点地址
    tail = InsertTail(tail, 4); // 尾插法插入数据4
    tail = InsertTail(tail, 5); // 尾插法插入数据5
    tail = InsertTail(tail, 6); // 尾插法插入数据6

    printf("在指定位置3插入数据7\n");
    InsertPosNode(list, 3, 7); // 在指定位置3插入数据7

    printf("删除指定位置3的节点\n");
    DeletePosNode(list, 3); // 删除指定位置3的节点
    printf("遍历-链表中的元素为：");
    TraverseList(list); // 遍历单链表

    printf("链表长度为%d\n", GetListLength(list));

    printf("释放链表\n");
    FreeList(list); // 释放链表的内存
    printf("链表长度为%d\n", GetListLength(list));

    return 0;
}

输出

头插法插入数据1 2 3
尾插法插入数据4 5 6
在指定位置3插入数据7
删除指定位置3的节点
遍历-链表中的元素为：3 2 1 4 5 6
链表长度为7
释放链表
链表长度为1

请按任意键继续. . .

查看全文

http://www.kler.cn/a/511213.html

Cloud Foundry，K8S，Mesos Marathon弹性扩缩容特性对比

【深度学习】Huber Loss详解

uni-app vue3 常用页面组合式api方式

java权限修饰符

第22篇基于ARM A9处理器用汇编语言实现中断＜四＞

从零开始：Gitee 仓库创建与 Git 配置指南

macOS Sequoia 15.3 beta3（24D5055b）发布，附黑、白苹果镜像下载地址

Spring Boot 集成MyBatis-Plus

【报错解决】Sql server 2022连接数据库时显示证书链是由不受信任的颁发机构颁发的

【SSH端口转发：实现安全的远程端口映射】

C/C++内存管理（超详解）

鸿蒙MVVM开发模式

使用Flask和Pydantic实现参数验证

【25考研】也很难！清华大学计算机考研复试难度分析！

Linux软件包管理器yum

全面解析计算机网络：从局域网基础到以太网交换机！！！

Cursor的composer和chat的区别

leetcode——接雨水（java）

API接口技术推动电商数据处理的自动化

2025.1.18——七、[GYCTF2020]Ezsqli 1

k8s 四种Service类型(ClusterIP、NodePort、LoadBalancer、ExternalName)详解

大数据技术Kafka详解 ⑤ | Kafka中的CAP机制

【深度学习】VGG16模型训练（CIFAR-10数据集）

Flask简介与安装以及实现一个糕点店的简单流程

如何使用 useMemo 和 memo 优化 React 应用性能？

01设计模式（D3_设计模式类型 - D3_行为型模式）

线性表-单链表

顺序表

链表存储结构

单链表

初始化

插入数据

头插法

尾插法

在指定位置插入数据

遍历链表

删除节点

获取链表长度

释放链表

相关文章：