数据结构（二）单链表

一、链表

（一）概念

逻辑结构：线性
存储结构：链式存储，在内存中不连续

分为有头链表和无头链表
同时又细分为单向、循环、双向链表

（二）有头单向链表示意图

以下数据及地址只是为了方便理解设置
在这里插入图片描述

（三）操作

1. 节点的结构体定义：

① 定义：

typedef struct node
{
    int data; //保存数据
    struct node* next;  //记录下一节点的地址，注意此时指针类型不能定义为nd_t*
}nd_t;

② 注意点：

  1. 定义结构体成员时，指针的类型此时不能使用nd_t定义。

2. 创建链表

（1） 函数声明

create_list(nd_t **phead,int num);

该函数需要在内存中申请一块nd_t类型大小的空间，并将其地址返回给main函数中用户定义的指针中；
num是用来初始化这块空间中数据域的值。

（2）注意点：
  1. 必须传入二级指针
  2. phead不能为空，即不能传一个NULL作为形参，后面需要对phead取值
  3. 需要检查是否申请内存成功
（3）示意图

在这里插入图片描述

（4）代码实现
//创建节点
create_list(nd_t **phead,int num){
    if(NULL==phead){
        printf("传入指针为NULL");
    }
    //*phead可以为空，即main函数中的phead可以是一个空指针
    //但是phead不能为空，即不能传一个NULL作为形参
    *phead=(nd_t *)malloc(sizeof(nd_t));
    if(NULL==*phead){
        printf("申请空间失败！\n");
        return -1;
    }
    //初始化
    (*phead)->data=num;
    (*phead)->next=NULL;
    return 0;
}

3. 清空

（1） 函数声明

int clean_list(nd_t *phead);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现
int clean_list(nd_t *phead){
    if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    if(NULL==phead->next){
        printf("表为空\n");
        return -1;
    }
    nd_t *ptemp=NULL;
    //使用头删清空
    while(NULL!=phead->next)
    {
        ptemp=phead->next;
        phead->next=ptemp->next;
        free(ptemp);
    }
    ptemp=NULL;
    return 0;
}

4. 销毁

（1） 函数声明

int destory_list(nd_t **phead)；

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现
int destory_list(nd_t **phead){
    if(NULL==phead || NULL==*phead){
        printf("传入指针为NULL");
        return -1;
    }
    clean_list(*phead);
    free(*phead);//free参数不能是一个空指针
    *phead=NULL;
    return 0;
}

5. 插入（头插、尾插、任意位置插）

（1）头插
① 函数声明

int insert_list_by_head(nd_t *phead,int num);

② 注意点：
  1. 传入一级指针即可
  2. 需要判断传入的列表指针是否是空指针
③ 示意图

在这里插入图片描述

③ 代码实现
int insert_list_by_head(nd_t *phead,int num){
    if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }

    //创建新节点
    nd_t *ptemp = NULL;
    if(create_node(&ptemp,num)<0)
    {
        printf("内存分配失败\n");
        return -1;
    }
    ptemp->next=phead->next;
    phead->next=ptemp;

    return 0;
}
（2）尾插
① 函数声明

int insert_list_by_tail(nd_t *phead,int num);

② 注意点：
③ 代码实现
int insert_list_by_tail(nd_t *phead,int num){
    if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到尾节点
    while(NULL!=ptemp->next){
        ptemp=ptemp->next;
    }
    //创建新节点
    nd_t *pnew = NULL;
    if(create_node(&pnew,num)<0)
    {
        printf("内存分配失败\n");
        return -1;
    }
    ptemp->next=pnew;
    return 0;
}
（3）任意位置插入
① 函数声明

int insert_list_by_pos(nd_t *phead,int pos,int num);

② 注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
③ 代码实现
int insert_list_by_pos(nd_t *phead,int pos,int num){
    if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    if(0>pos){
        printf("位置不合理\n");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到要插入的位置的前一个节点
    for(int i=0;i<pos;i++){
        //当ptemp->next为0时，说明不能继续向下遍历了
        if(NULL==ptemp->next){
            printf("位置不合理\n");
            return -1;
        }
        ptemp=ptemp->next;
    }
    
    //创建新节点
    nd_t *pnew = NULL;
    if(create_node(&pnew,num)<0)
    {
        printf("内存分配失败\n");
        return -1;
    }
    pnew->next=ptemp->next;
    ptemp->next=pnew;

    return 0;
}

6. 删除（头删、尾删、任意位置删）

（1）头删
① 函数声明

int insert_list_by_tail(nd_t *phead,int num);

② 注意点：
③ 代码实现
int delete_list_by_head(nd_t *phead){
     if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    if(NULL==phead->next){
        printf("表为空\n");
        return -1;
    }
    nd_t *ptemp=phead->next;
    phead->next=ptemp->next;
    free(ptemp);
    ptemp=NULL;
    return 0;
}
（2）尾删
① 函数声明

int insert_list_by_tail(nd_t *phead,int num);

② 注意点：
③ 代码实现
int delete_list_by_tail(nd_t *phead){
     if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    if(NULL==phead->next){
        printf("表为空\n");
        return -1;
    }
    //找到尾节点的前一个节点
    nd_t *ptemp=phead;
    while(NULL!=ptemp->next->next){
        ptemp=ptemp->next;
    }
    free(ptemp->next);
    ptemp->next=NULL;

    return 0;
}
（3）任意位置删除
① 函数声明

int delete_list_by_pos(nd_t *phead,int pos);

② 注意点：
③ 代码实现
int delete_list_by_pos(nd_t *phead,int pos){
    if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    if(0>pos){
        printf("位置不合理\n");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到要删除的位置的前一个节点
    for(int i=0;i<pos;i++){
        //当ptemp->next为0时，说明此时ptemp位于链表的最后一个节点，但是此时ptemp后的节点是空，不能进行删除操作
        //所以如果ptemp->next->next为空时，就不能继续往后移动了
        if(NULL==ptemp->next->next){
            printf("位置不合理\n");
            return -1;
        }
        ptemp=ptemp->next;
    }
    nd_t *pdel=ptemp->next;
    ptemp->next=pdel->next;
    free(pdel);
    pdel=NULL;
    return 0;
}

7. 修改

（1） 函数声明

int modify_list_by_pos(nd_t *phead,int pos,int num);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现
int modify_list_by_pos(nd_t *phead,int pos,int num){
    if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    if(0>pos){
        printf("位置不合理\n");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到要修改的位置的节点
    for(int i=0;i<=pos;i++){
        //当ptemp->next为0时，说明此时ptemp位于链表的最后一个节点，不能继续后移了
        if(NULL==ptemp->next){
            printf("位置不合理\n");
            return -1;
        }
        ptemp=ptemp->next;
    }
    ptemp->data=num;
    return 0;
}

8. 查询

（1） 函数声明

int search_list_by_pos(nd_t *phead,int pos,int *num);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现
int search_list_by_pos(nd_t *phead,int pos,int *num){
    if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    if(0>pos){
        printf("位置不合理\n");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到要查找的位置的节点
    for(int i=0;i<=pos;i++){
        //当ptemp->next为0时，说明此时ptemp位于链表的最后一个节点，不能继续后移了
        if(NULL==ptemp->next){
            printf("位置不合理\n");
            return -1;
        }
        ptemp=ptemp->next;
    }
    *num=ptemp->data;
    return 0;
}

9. 链表合并

（1） 函数声明

int merge_list(nd_t *phead1,nd_t **phead2);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现
int merge_list(nd_t *phead1,nd_t **phead2){
    if(NULL==phead1||NULL==phead2||NULL==*phead2){
        printf("传参为空\n");
        return -1;
    }
    //先找到表1的尾部
    nd_t *ptemp=phead1;
    while(NULL!=ptemp->next)
    {
        ptemp=ptemp->next;
    }
    ptemp->next=(*phead2)->next;
    free(*phead2);
    *phead2=NULL;
    return 0;
}

10. 链表排序

（1） 函数声明

int create_node(node_t **list,int *num);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现

11. 链表翻转

（1） 函数声明

int create_node(node_t **list,int *num);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现

12. 链表剔重

（1） 函数声明

int create_node(node_t **list,int *num);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现

13. 打印链表

（1） 函数声明

int print_list(nd_t *phead);

（2）注意点：
  1. 注意对于边界点的判定
（3）代码实现
//打印
int print_list(nd_t *phead){
    if(NULL==phead){
        printf("传入指针为NULL");
        return -1;
    }
    nd_t *ptemp=phead->next;
    while(NULL!=ptemp){
        printf("%d ",ptemp->data);
        ptemp=ptemp->next;
    }
    putchar(10);
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/634469.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Linux】文件系统和软硬链接

【Linux】文件系统和软硬链接

目录 一、认识文件系统 二、认识磁盘 三、磁盘文件系统 3.1 磁盘存储的抽象逻辑结构 3.2 磁盘文件系统图 3.3 创建和删除文件 3.4 如何理解目录&#xff1f; 3.5 如何查找一个文件 3.6 查找文件的一般流程 3.7 如何确定文件所在的分区 3.8 总结 四、软硬链接 4.1 …
阅读更多...
30、QUiLoader 在程序运行时读取UI 文件中的信息

30、QUiLoader 在程序运行时读取UI 文件中的信息

QUiLoader 类可让独立应用程序在运行时使用UI 文件中存储的信息&#xff0c;进而可以分离UI设计工作。 一、使用Qt 设计师-Qt Designer创建ui文件 打开Qt Designer&#xff0c;选择“创建” 往中央区域拖住几个控件&#xff0c;进行布局&#xff0c;更改三个控件的objectName…
阅读更多...
参考文献交叉引用两个文献，逗号隔开

参考文献交叉引用两个文献，逗号隔开

1.引用两个参考文献&#xff0c;定位到word正文中需要引用的位置&#xff0c;然后插入-交叉引用&#xff0c;引好文献 2.选中两个参考文献&#xff0c;切换域代码&#xff0c;然后进行修改&#xff1a; 改为 上面的两张图片中的点是空格的含义&#xff0c;word中按ctrlshift8就…
阅读更多...
Qt | QGridLayout 类(网格布局)

Qt | QGridLayout 类(网格布局)

01、上节回顾 Qt | QBoxLayout 及其子类(盒式布局)02、QGridLayout 简介 1、网格布局原理(见下图)： 基本原理是把窗口划分为若干个单元格，每个子部件被放置于一个或多个单元格之中，各 单元格的大小可由拉伸因子和一行或列中单元格的数量来确定，若子部件的大小(由 sizeH…
阅读更多...
css - sass or scss ？

css - sass or scss ？

总的来说&#xff0c;Sass 和 SCSS 提供的功能是一样的&#xff0c;选择哪种语法主要取决于你的个人或团队的偏好。
阅读更多...
OFDM 802.11a的FPGA实现（二十一）发射主控模块MCU（含代码）

OFDM 802.11a的FPGA实现（二十一）发射主控模块MCU（含代码）

目录 1.前言 2.主控逻辑 3.Matlab 4.verilog 5.ModelSim 6.ModelSim仿真结构与Matlab自动化对比 完整工程链接&#xff08;含verilog和Matlab代码&#xff09;&#xff1a; https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzkxNjM0NDk2Nw&actiongetalbum&album…
阅读更多...
PHP报错 Notice: Undefined index: action in

PHP报错 Notice: Undefined index: action in

upload靶场PHP报错 Notice: Undefined index: action in 修改 php.ini 中的 error配置下错误显示方式&#xff1a;将error_reporting E_ALL 修改为 error_reporting E_ALL & ~E_NOTICE 修改后重启下APCHE服务即可。
阅读更多...
Mysql超详细安装配置教程(保姆级图文)

Mysql超详细安装配置教程(保姆级图文)

MySQL是一种流行的开源关系型数据库管理系统&#xff0c;它广泛用于网站和服务的数据存储和管理。MySQL以其高性能、可靠性和易用性而闻名&#xff0c;是许多Web应用程序的首选数据库解决方案之一。 一、下载安装包 &#xff08;1&#xff09;从网盘下载安装文件 点击此处直…
阅读更多...
UE5中搭建一个简单的海岛

UE5中搭建一个简单的海岛

本文将用UE的WaterSystem与地形搭建一个简单的海岛&#xff0c;通过WaterSystem的参数设置&#xff0c;可以更好的自定义海岸线等效果。 1.基础风貌 1.1.首先新建一个Basic基础场景&#xff0c;切换到地形编辑模式刷出一块高地&#xff0c;用于沙滩。 1.2.引入UE官方插件Wat…
阅读更多...
【EXCEL_VBA_实战】两组数据比对是否一致（字符串数组）

【EXCEL_VBA_实战】两组数据比对是否一致（字符串数组）

工作背景&#xff1a;比对两组数据是否一致&#xff08;位置非一一对应&#xff09; 思路构建&#xff1a;两组数据转换为两组字符串数组&#xff0c;比对所包含元素是否相同 问题点&#xff1a;A数组的第一个元素不一定与B数组的第一个元素对应&#xff0c;此时无法通过公式…
阅读更多...
C++开源库glog使用封装--自定义日志输出格式，设置日志保留时间

C++开源库glog使用封装--自定义日志输出格式，设置日志保留时间

glog下载和编译 glog开源地址 https://github.com/google/glog glog静态库编译 cd /home/wangz/3rdParty/hldglog/glogmkdir out mkdir build && cd buildcmake .. -DCMAKE_INSTALL_PREFIX../out -DCMAKE_BUILD_TYPERelease -DBUILD_SHARED_LIBSOFF本文选择的glo…
阅读更多...
HashMap中添加元素

HashMap中添加元素

一、HashMap底层使用了3种结构 hash数组(定位)、链表(存储元素)、红黑树(存储元素,提高查询效率) 二、添加流程描述&#xff1a; 添加元素时&#xff0c;先为元素计算出一个hash值&#xff0c;再用hash值%数组长度得到元素位置&#xff0c;将元素(k:v)封装到Node对象中&…
阅读更多...
sql server【 特定分隔符隔开的字符串转表】和【 列转逗号隔开的字符串】

sql server【 特定分隔符隔开的字符串转表】和【 列转逗号隔开的字符串】

文章目录 引言I 特定分隔符隔开的字符串转表II Sql Server 列转逗号隔开的字符串2.1 多列转行,逗号分隔(字段拼接/字段分割)2.1 案例引言 Sql Server 列转逗号隔开的字符串 和 逆转,常用于数据导出和数据查询。 I 特定分隔符隔开的字符串转表 CREATE FUNCTION [dbo].[GetIDLi…
阅读更多...
python科研数据可视化之折线图

python科研数据可视化之折线图

例如 &#xff1a; 下面的配色表画出的图很好看。选择喜欢的颜色&#xff0c;找到代码中颜色部分进行修改即可。 代码部分已经有详细的注释&#xff0c;就不一一解释了。另外&#xff0c;如果想要坐标轴从设定的值开始就把下面代码中的范围xlim&#xff0c;ylim进行注释。 imp…
阅读更多...
MySQL的备份及恢复

MySQL的备份及恢复

目录 5、MySQL的备份及恢复 5.1 MySQL日志管理 5.1.1 MySQL日志类型 5.1.2 错误日志 5.1.3 通用查询日志 5.1.4 慢查询日志 5.1.5 二进制日志 开启日志 二进制日志管理>又叫日志滚动 二进制日志还原数据 删除二进制日志文件&#xff1a; 5.1.6实例&#xff1a; 使用mysqlbi…
阅读更多...
windows远程桌面无法连接，轻松解决 Windows远程桌面无法连接问题的故障排查

windows远程桌面无法连接，轻松解决 Windows远程桌面无法连接问题的故障排查

Windows远程桌面是一个强大且实用的工具&#xff0c;它允许用户远程访问和操作另一台计算机。然而&#xff0c;有时您可能会遇到无法连接的问题&#xff0c;这无疑会严重影响工作效率和体验。但别担心&#xff0c;本文将为您揭示解决这一问题的关键策略&#xff0c;让您轻松恢复…
阅读更多...
2024042701-disjoint-set

2024042701-disjoint-set

并查集 Disjoint-Set 一、前言 并查集的历史 1964年&#xff0c; Bernard A. Galler 和 Michael J. Fischer 首次描述了不相交的并查集&#xff0c;1975 年&#xff0c;Robert Tarjan 是第一个证明O(ma(n))&#xff08;逆阿克曼函数&#xff09;算法时间复杂度的上限&#x…
阅读更多...
简易CAD程序：Qt多文档程序的一种实现

简易CAD程序：Qt多文档程序的一种实现

注&#xff1a;文中所列代码质量不高&#xff0c;但不影响演示我的思路 实现思路说明 实现DemoApplication 相当于MFC中CWinAppEx的派生类&#xff0c;暂时没加什么功能。 DemoApplication.h #pragma once#include <QtWidgets/QApplication>//相当于MFC中CWinAppEx的派生…
阅读更多...
c语言：strcmp

c语言：strcmp

strcmp函数是用于比较两个字符串的库函数&#xff0c;其功能是根据ASCII值逐一对两个字符串进行比较。 语法&#xff1a;strcmp(str1, str2) 返回值&#xff1a; 如果str1等于str2&#xff0c;则返回0。 如果str1小于str2&#xff0c;则返回负数&#xff08;具体值取决于C…
阅读更多...
【数据分析面试】51. 读取大型csv文件

【数据分析面试】51. 读取大型csv文件

题目 假设你是一家科技公司的数据分析师。近期由于管理层变动&#xff0c;新的总经理上任&#xff0c;他想要了解公司过往的交易情况数据&#xff0c;并且这个任务由数据分析团队负责完成。历史交易数据下载导出完成后&#xff0c;团队发现Csv文件大小超过了5个G&#xff0c;使…
阅读更多...
最新文章

Copyright @ 2022~2023