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

【数据结构】单链表的使用

article 2025/2/28 15:30:35

单链表的使用

    • 1、基本概念
    • 2、链表的分类
    • 3、链表的基本操作
      • a、单链表节点设计
      • b、单链表初始化
      • c、单链表增删节点
        • **节点头插：**
        • **节点尾插：**
        • **新节点插入指定节点后：**
        • 节点删除：
      • d、单链表修改节点
      • e、单链表遍历，并打印数据
    • 4、链表优缺点
    • 5、完整示例代码

1、基本概念

  • 顺序表：顺序存储的线性表。
  • 链式表：链式存储的线性表，简称链表。
    既然顺序存储中的数据因为挤在一起而导致需要成片移动，那很容易想到的解决方案是将数据离散地存储在不同内存块中，然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表，就是所谓的链表。

顺序表和链表在内存在的基本样态如下图所示：

  • 顺序表：

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

2、链表的分类

\quad 根据链表中各个节点之间使用指针的个数，以及首尾节点是否相连，可以将链表细分为如下种类：
1.单向链表
2.单向循环链表
3.双向循环链表
\quad 这些不同链表的操作都是差不多的，只是指针数目的异同。以最简单的单向链表为例，其基本示意图如下所示：
在这里插入图片描述上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。
另外注意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节点。head 通常被称为头指针。

3、链表的基本操作

  1. 节点设计
  2. 初始化空链表
  3. 增删节点
  4. 链表遍历(改查)
  5. 销毁链表

下面着重针对这几项常见操作，讲解单向链表的处理。

a、单链表节点设计

单向链表的节点非常简单，节点中除了要保存用户数据之外（这里以整型数据为例），只需要增加一个指向本类节点的指针即可，如下所示：

typedef struct single_list{
	// 数据域--》真实的数据
    int data;    				// 以整型数据为例
    // 指针域
    struct single_list *next; 	// //用来指向下一个元素在内存中的首地址
}single_list_t;

b、单链表初始化

\quad 首先，空链表有两种常见的形式。一种是带头结点的，一种是不带头结点的。所谓的头结点是不存放有效数据的节点，仅仅用来方便操作，如下：
在这里插入图片描述
而不带头结点的空链表如下所示：
在这里插入图片描述
\quad 由于头结点是不存放有效数据的，因此如果空链表中带有头结点，那么头指针 head 将永远不变，这会给以后的链表操作带来些许便捷。
下面以带头结点的链表为例，展示单向链表的初始化的示例代码：

single_list_t *single_list_init()
{
    single_list_t *head_node = malloc(sizeof(single_list_t));
    if (head_node != NULL)
    {
        head_node->next = NULL;
    }

    return head_node;
}

c、单链表增删节点

\quad 相对于顺序表需要整片移动数据，链表增删节点只需要修改几个相关指针的指向，动作非常快速。
\quad 与顺序表类似，可以对一条链表中的任意节点进行增删操作，示例代码：

节点头插：
int insert_list_head(int newdata, single_list_t *list)
{
    // 申请一个节点 -堆空间
    single_list_t *new_node = malloc(sizeof(single_list_t));
    // 初始化数据域
    new_node->data = newdata;
    new_node->next = NULL;

    // 插入节点
    new_node->next = list->next;
    list->next = new_node;

    return 0;
}
节点尾插：
int insert_list(int newdata, single_list_t *list)
{
    // 申请一个节点 -堆空间
    single_list_t *new_node = malloc(sizeof(single_list_t));
    // 初始化数据域
    new_node->data = newdata;
    new_node->next = NULL;
    
    // 定义指针p去找到链表的尾部
    single_list_t *p = list;
    while (p->next != NULL)
    {
        p = p->next;
    }
    // 此时p已经到最后一个节点的位置
    p->next = new_node;

    return 0;
}
新节点插入指定节点后：
int insert_list_mid(int olddata, int newdata, single_list_t *list)
{
    // 找到要插入的节点
    single_list_t *p = list;
    while (p->next != NULL)
    {
        p = p->next;
        if (p->data == olddata) // 待插入的节点在链表中间
        {
            break;
        }
    }
    // 申请一个新的节点 
    single_list_t *new_node = malloc(sizeof(single_list_t));
    // 初始化数据域
    new_node->data = newdata;
    new_node->next = NULL;
    // p指向最后一个节点
    if (p->next == NULL)
    {
    	// 最后一个节点是要插入的节点
        if (p->data == olddata)
        {
            new_node->next = p->next; // 先让新增加的节点指向找到节点的下一个节点
            p->next = new_node;   // 再将该节点指向新增加的节点
        }
        else
        {
            printf("要插入的数据不存在\n");
            return -1;
        }
    }
    else // 遍历到中间找到需要插入的节点
    {
        new_node->next = p->next; // 先让新增加的节点指向找到节点的下一个节点
        p->next = new_node;   // 再将该节点指向新增加的节点
        
    }
    return 0;
}
节点删除：
int list_delnode(int deldata, single_list_t *list)
{
    single_list_t *q = list;
    single_list_t *p = list->next;
    while (p->next != NULL)
    {
        // 找到要删除的节点并进行删除
        if (p->data == deldata)
        {
            q->next = p->next;  // 将q指向的节点指向被删除节点的下一个节点
            p->next = NULL;     // p节点的next指针指向NULL
            free(p);    // 释放p后此时p是野指针
            p = q->next;// 将p指向被删除节点的下一个节点
        }
        else
        {
            p = p->next;
            q = q->next;
        }  
    }
    // 遍历到最后一个节点
    if (p->next == NULL)
    {
        // 若最后一个节点是要删除的节点，则删除
        if (p->data == deldata)
        {
            q->next = p->next;
            p->next = NULL;
            free(p);
        }
        else
        {
            printf("最后一个节点不是要删除的节点\n");
            return 0;
        }
    }
}

d、单链表修改节点

int list_update_node(int old_data, int new_data, single_list_t *list)
{
    single_list_t *p = list;
    while (p->next != NULL)
    {
        p = p->next;  // p指向下一个节点
        if (p->data == old_data)
        {
            p->data = new_data;
        }
    }
    return 0;
}

e、单链表遍历，并打印数据

int list_show(single_list_t *list)
{
    single_list_t *p = list;

    while (p->next != NULL)
    {
        p = p->next;
        printf("当前p指向的节点数据:%d\n", p->data);
    }
}

4、链表优缺点

\quad 链式存储中，所有节点的存储位置是随机的，他们之间的逻辑关系用指针来确定，跟物理存储位置无关，因此从上述示例代码可以很清楚看到，增删数据都非常迅速，不需要移动任何数据。另外，又由于位置与逻辑关系无关，因此也无法直接访问某一个指定的节点，只能从头到尾按遍历的方式一个个找到想要的节点。简单讲，链式存储的优缺点跟顺序存储几乎是相对的。
总结其特点如下：

  • 优点
    a.插入、删除时只需要调整几个指针，无需移动任何数据
    b.当数据节点数量较多时，无需一整片较大的连续内存空间，可以灵活利用离散的内存
    c.当数据节点数量变化剧烈时，内存的释放和分配灵活，速度快
  • 缺点
    a.在节点中，需要多余的指针来记录节点之间的关联
    b.所有数据都是随机存储的，不支持立即访问任意一个随机数据。

5、完整示例代码

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

// 1.封装一个结构体来表示单链表
typedef struct single_list{
    int data;
    struct single_list *next;
}single_list_t;

// 2.初始化单链表-->定义结构体变量 创建头节点
single_list_t *single_list_init()
{
    single_list_t *head_node = malloc(sizeof(single_list_t));
    if (head_node != NULL)
    {
        head_node->next = NULL;
    }
    
    return head_node;
}

// 头插
int insert_list_head(int newdata, single_list_t *list)
{
    // 申请一个节点 -堆空间
    single_list_t *new_node = malloc(sizeof(single_list_t));
    // 初始化数据域
    new_node->data = newdata;
    new_node->next = NULL;

    // 插入节点
    new_node->next = list->next;
    list->next = new_node;

    return 0;
}
/*@brief:3.插入数据-->尾插(在最后一个有效成员的后面插入数据)
 *@param(in):  newdata :待插入的数据  
                list:待插入的链表
 *@param(out):  
 *@retval:    
*/
int insert_list(int newdata, single_list_t *list)
{
    // 申请一个节点 -堆空间
    single_list_t *new_node = malloc(sizeof(single_list_t));
    // 初始化数据域
    new_node->data = newdata;
    new_node->next = NULL;
    
    // 定义指针p去找到链表的尾部
    single_list_t *p = list;
    while (p->next != NULL)
    {
        p = p->next;
    }
    // 此时p已经到最后一个节点的位置
    p->next = new_node;

    return 0;
}

// 中间插入
int insert_list_mid(int olddata, int newdata, single_list_t *list)
{
    // 找到要插入的节点
    single_list_t *p = list;
    while (p->next != NULL)
    {
        p = p->next;
        if (p->data == olddata)
        {
            break;
        }
    }
    // 申请一个节点 -堆空间
    single_list_t *new_node = malloc(sizeof(single_list_t));
    // 初始化数据域
    new_node->data = newdata;
    new_node->next = NULL;
    // p指向最后一个节点
    if (p->next == NULL)
    {
        if (p->data == olddata)
        {
            new_node->next = p->next; // 先让新增加的节点指向找到节点的下一个节点
            p->next = new_node;   // 再将该节点指向新增加的节点
        }
        else
        {
            printf("要插入的数据不存在\n");
            return -1;
        }
    }
    else // 遍历到中间找到需要插入的节点
    {
        new_node->next = p->next; // 先让新增加的节点指向找到节点的下一个节点
        p->next = new_node;   // 再将该节点指向新增加的节点
        
    }
    return 0;
}
// 删除节点
int list_delnode(int deldata, single_list_t *list)
{
    single_list_t *q = list;
    single_list_t *p = list->next;
    while (p->next != NULL)
    {
        // 找到要删除的节点并进行删除
        if (p->data == deldata)
        {
            q->next = p->next;  // 将q指向的节点指向被删除节点的下一个节点
            p->next = NULL;     // p节点的next指针指向NULL
            free(p);    // 释放p后此时p是野指针
            p = q->next;// 将p指向被删除节点的下一个节点
        }
        else
        {
            p = p->next;
            q = q->next;
        }  
    }
    // 遍历到最后一个节点
    if (p->next == NULL)
    {
        // 若最后一个节点是要删除的节点，则删除
        if (p->data == deldata)
        {
            q->next = p->next;
            p->next = NULL;
            free(p);
        }
        else
        {
            printf("最后一个节点不是要删除的节点\n");
            return 0;
        }
    }
}
// 修改节点
int list_update_node(int old_data, int new_data, single_list_t *list)
{
    single_list_t *p = list;
    while (p->next != NULL)
    {
        p = p->next;  // p往后移动
        if (p->data == old_data)
        {
            p->data = new_data;
        }
    }
    return 0;
}

// 4.遍历链表,打印节点数据
int list_show(single_list_t *list)
{
    single_list_t *p = list;

    while (p->next != NULL)
    {
        p = p->next;
        printf("当前p指向的节点数据:%d\n", p->data);
    }
}

int main(int argc, char const *argv[])
{
    // 初始化单链表
    single_list_t *my_list = single_list_init();
    // 往链表插入数据
    insert_list(15, my_list);
    insert_list(18, my_list);
    insert_list(15, my_list);
    insert_list(25, my_list);
    insert_list(666, my_list);
    insert_list(123, my_list);
    insert_list(11111111, my_list);
    insert_list_mid(666, 777, my_list);
    insert_list_mid(1, 222, my_list);
    insert_list_head(15, my_list);

    printf("============插入的节点============\n");
    list_show(my_list);
    printf("============插入的节点============\n");
    // 删除节点
    list_delnode(25,my_list);
    printf("============删除后的节点============\n");
    list_show(my_list); // 打印数据
    printf("============删除后的节点============\n");
    // 修改数据
    list_update_node(123, 234, my_list);
    printf("============修改后的节点============\n");
    list_show(my_list); // 打印数据
    printf("============修改后的节点============\n");

    return 0;
}
/*
执行结果：
要插入的数据不存在
============插入的节点============
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:25
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:123
当前p指向的节点数据:11111111
============插入的节点============
最后一个节点不是要删除的节点
============删除后的节点============
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:123
当前p指向的节点数据:11111111
============删除后的节点============
============修改后的节点============
当前p指向的节点数据:15
当前p指向的节点数据:15
当前p指向的节点数据:18
当前p指向的节点数据:15
当前p指向的节点数据:666
当前p指向的节点数据:777
当前p指向的节点数据:234
当前p指向的节点数据:11111111
============修改后的节点============
*/

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

相关文章：

  • 【CSS in Depth 2 精译_096】16.4：CSS 中的三维变换 + 16.5：本章小结
  • 解决VSCODE输出python中文乱码问题
  • 【网络云计算】2024第52周-每日【2024/12/26】小测-理论实操-备份MySQL数据库并发送邮件-解析
  • 【从0带做】基于Springboot3+Vue3的高校食堂点餐系统
  • C# 编程系列：网络通信之TCP通信（第一篇：介绍TCP协议在C#中的基本概念和工作原理）
  • wordpres当前分类调用父分类的名称和链接
  • Vue3响应式:Proxy设计原理解析
  • 在 Linux 中如何使用粘滞位 (t-bit)共享文件
  • 基于websocket实现本地web语音聊天
  • 每日一题 347. 前 K 个高频元素
  • 数据库原理及应用（MySQL版-李月军）-习题参考答案
  • 【RabbitMQ】超详细Windows系统下RabbitMQ的安装配置
  • 如何使用fetch函数获取多个数据并同时使用（在嵌套的fetch函数之间传递数据）
  • 如何为运行在 PICO 4 Ultra 设备上的项目设置外部文件读写权限？
  • pdf有密码，如何实现pdf转换word？
  • 易基因： BS+ChIP-seq揭示DNA甲基化调控非编码RNA(VIM-AS1)抑制肿瘤侵袭性｜Exp Mol Med
  • 在K8S中，nodePort的externalTrafficPolicy字段有什么作用？
  • Vue.js组件开发-如何实现vueFLow流程
  • pyqt6 OpenCV相关练习
  • 【信息系统项目管理师】高分论文：论信息系统项目的资源管理（移动警务通系统）