数据结构【线性表篇】(二）

数据结构【线性表篇】(二）

文章目录

  • 数据结构【线性表篇】(二）
  • 前言
    • 为什么突然想学算法了？
    • 为什么选择码蹄集作为刷题软件？
  • 目录
  • 一、单链表
    • (一)、单链表的定义
    • (二)、单链表的建立
    • (三)、单链表的插入删除
    • (四)、单链表的查找
  • 二、主函数代码
  • 三、结语

前言

在这里插入图片描述

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下竞争压力逐渐增大，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个寒假巩固速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

在这里插入图片描述

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
.
在这里插入图片描述

目录

一、单链表

(一)、单链表的定义

参考代码

//单链表的定义
typedef struct LNode{                   //定义单链表结点类型
    int data;                           //每个节点存放一个数据元素
    struct LNode*next;                  //指针指向下一个节点
}LNode,*LinkList;
//增加一个新的结点:在内存中申请一个结点所需空间，并用指针p指向这个结点
LNode* p=(LNode*)malloc(sizeof(LNode));
//要表示一个单链表时，只需要声明一个头指针L,指向单链表的第一个结点
LinkList L; //声明一个指向单链表第一个结点的指针=LNode *L，但前者可读性更强

(二)、单链表的建立

//单链表的建立
//尾插法建立单链表
LinkList List_TailInsert(LinkList &L){      //正向建立单链表
    int x;                                  //设ElemType为整型
    L = (LinkList)malloc(sizeof(LNode));    //建立头结点，初始化空表
    LNode *s,*r=L;                          //r为表尾指针
    scanf("%d",&x);                  //输入9999表示结束
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));   //在r结点之后插入元素x
        s->data=x;
        r->next=s;
        r=s;                                //r指向新的表尾结构。永远保持r指向最后一个结点
        scanf("%d",&x);
    }
    r->next=NULL;                           //表尾指针置空
    return L;
}

//头插法建立单链表——重要应用：链表的逆置
LinkList List_HeadInsert(LinkList &L){      //逆向建立单链表
    LNode *s; int x;
    L=(LinkList)malloc(sizeof(LNode));      //创建头结点
    L->next=NULL;                           //初始为空链表
    scanf("%d",&x);                  //输入9999表示结束
    while(x != 9999){
        s=(LNode*)malloc(sizeof(LNode));    //创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s;                          //将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}

//创建不带头结点的单链表
//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;                               //空表，暂时还没有任何结点(防止脏数据)
    return true;
}

bool Empty(LinkList L){                     //判断单链表是否为空
    return (L==NULL);
}

/初始化一个单链表(带头结点)
bool InitListWithNode(LinkList &L){
    L = (LNode *) malloc(sizeof(LNode));    //分配一个头结点
    if(L==NULL)                             //内存不足，分配失败
        return false;
    L->next = NULL;                         //头结点之后暂时还没有节点
    return true;
}

//判断单链表是否为空(带头结点)
bool EmptyWithNode(LinkList L){
    if(L->next==NULL)
        return true;
    else
        return false;
}

//------------------------------------------------
//带头结点，写代码更方便
//不带头结点，写代码更麻烦
// （1）对第一个数据节点和后续数据结点的处理需要用不同的代码逻辑
// （2）对空表和非空表的处理需要用不同的代码逻辑

(三)、单链表的插入删除

//插入
//按位序插入(带头结点)
//在第i个位置插入元素e(带头结点)
bool ListInsertWithNode(LinkList &L,int i,int e){
    if(i<1)
        return false;
    LNode *p;                               //指针p指向当前扫描到的结点
    int j=0;                                //当前p指向的是第几个结点
    p=L;                              //L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i-1){                //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)                             //i值不合法
        return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;                            //将结点s连到p之后
    return true;                            //插入成功
} //平均时间复杂度O(n)

//按位序插入(不带头结点)
//插入、删除第1个元素时，需要改变头指针L
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)
        return false;
    if(i==1){ //插入第1个结点的操作与其他结点操作不同
        LNode *s = (LNode *) malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;                              //头指针指向新结点
        return true;
    }
    LNode *p;                               //指针p指向当前扫描的结点
    int j=1;                                //当前p指向的是第几个结点
    p=L;                                    //p指向第1个结点(注意：不是头结点)
    while(p!=NULL && j<i-1){                //循环找到第i-1个结点
        p=p->next;
        j++;
    }                                       //自此往下,=return InsertNextNode(p,e);
    if(p==NULL)                             //i值不合法
        return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;                            //插入成功
}

//指定结点的后插操作
//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p,int e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    if(s==NULL)                             //内存分配失败
        return false;
    s->data = e;                            //用结点s保存数据元素e
    s->next = p->next;
    p->next = s;                            //将结点s连到p之后
    return true;
} //时间复杂度O(1)

//指定结点的前插操作
//前插操作（法一）：在p结点之前插入元素e
bool InsertPriorNode(LNode *p,int e){
    if(p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL)                             //内存分配失败
        return false;
    s->next=p->next;
    p->next=s;                              //新结点s连到p之后
    s->data=p->data;                        //将p中元素复制到s中
    p->data=e;                              //p中元素覆盖为e
    return true;
}

//前插操作（法二）：在p结点之前插入元素e
bool InsertPriorNode(LNode *p,LNode *s){
    if(p==NULL || s==NULL)
        return false;
    s->next=p->next;
    p->next=s;                              //新结点s连到p之后
    int temp = p->data;                     //交换数据域部分
    p->data=s->data;
    s->data=temp;
    return true;
}

//删除操作
//删除表L中第i个位置的元素，并用e返回删除元素的值

//按位序删除(带头结点)
bool ListDeleteWithNode(LinkList &L,int i,int e){
    if(i<1)
        return false;
    LNode *p;                               //指针p指向当前扫描到的结点
    int j=0;                                //当前p指向的是第几个结点
    p=L;                                    //L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i-1){                //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)                             //i值不合法
        return false;
    if(p->next==NULL)                       //第i-1个结点之后已无其他结点
        return false;
    LNode *q=p->next;                       //令q指向被删除结点
    e = q->data;                            //用e返回元素的值
    p->next=q->next;                        //将*q结点从链中“断开”
    free(q);                                //释放结点的存储空间
    return true;
}

//删除指定结点p
bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    LNode *q=p->next;                       //令q指向*p的后继结点
    p->data=p->next->data;                  //和后继结点交换数据域
    p->next=q->next;                        //将*q结点从链中“断开”
    free(q);                                //释放后继结点的存储空间
    return true;
}
//单链表的局限性：
// （1）无法逆向检索，有时候不太方便
// （2）如果p是最后一个结点，只能从表头开始依次寻找p的前驱，时间复杂度O(n)

(四)、单链表的查找

//查找
//按位查找，返回第i个元素(带头结点)
LNode *GetElemWithNode(LinkList L,int i){
    if(i<0)
        return NULL;
    LNode *p;                               //指针p指向当前扫描到的结点
    int j=0;                                //当前p指向的是第几个结点
    p=L;                                    //L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i){                  //循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
} //平均时间复杂度O(n)

//王道书版本：
LNode *GetElemWithNodeCS(LinkList L,int i){
    int j=1;
    LNode *p=L->next;
    if(i==0)
        return L;
    if(i<1)
        return NULL;
    while(p!=NULL && j<i){                  //循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
} //平均时间复杂度O(n)


//按值查找，找到数据域==e的结点
LNode * LocateElem(LinkList L,int e){
    LNode *p = L->next;
    int i=0;
    //从第1个结点开始查找数据域为e的结点
    while(p!=NULL && p->data !=e){
        p=p->next;
        i++;
    }
    return p;                               //找到后返回该结点指针，否则返回NULL
} //平均时间复杂度O(n)

int LocateElemI(LinkList L,int e){
    LNode *p = L->next;
    int i=1;
    //从第1个结点开始查找数据域为e的结点
    while(p!=NULL && p->data !=e){
        p=p->next;
        i++;
    }
    if(p==NULL) return 0;
    else return i;                          //找到后返回该元素位置,如果没找到，则返回0
} //平均时间复杂度O(n)

二、主函数代码

//求表的长度
int Length(LinkList L){
    int len=0;                              //统计表长
    LNode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

//------------------------------------------------------------
void printListWithNode(LinkList L){         //带头结点
    LNode *p=L;
    p=p->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}

void printList(LinkList L){                  //不带头结点
    LNode *p=L;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}

int main(){
    LinkList L;                              //声明一个指向单链表的指针
    InitListWithNode(L);                  //初始化一个空表(带头结点)
    //InitList(L);                          //初始化一个空表(不带头结点)

    //插入
    ListInsertWithNode(L,1,3);      //带头结点
    ListInsertWithNode(L,2,4);
    ListInsertWithNode(L,3,5);
    printListWithNode(L);
//
//    if(ListInsert(L,1,3))                  //不带头结点
//        printList(L);

    //删除
    ListDeleteWithNode(L,2,5);
    printf("删除后的序列为：\n");
    printListWithNode(L);

    //查找
    LNode *p;
    p=GetElemWithNode(L,2);                         //按位查找
    printf("第2个元素值为：%d\n",p->data);
    int i = LocateElemI(L,4);                //按值查找
    if(i==0) printf("不存在该元素\n");
    else printf("元素4所在位置为：%d\n",i);

    //求单链表长度
    int len = Length(L);
    printf("该单链表的长度为：%d\n",len);

    return 0;
}

三、结语

感谢大家一直以来的不断支持与鼓励，码题集题库中的进阶塔350题正在逐步更新，之后会逐步跟进星耀，王者的题，尽请期待！！！
同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

愿你的结局，配得上你一路的颠沛流离。
在这里插入图片描述

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

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

相关文章

springBoot2.3-基本介绍及入门案例

springBoot2.3-基本介绍及入门案例

本次学习雷丰阳springBoot(2.3版本)。建议先修ssm 一、SpringBoot基本介绍 springBoot是当今最为流行的java开发框架。 1、springBoot的底层是spring&#xff0c; 因此继承了spring的粘合其他框架的能力。 2、本质上还是其他框架包括spring在工作 , springBoot起到一个整合其他…
阅读更多...
LeetCode刷题--- 黄金矿工

LeetCode刷题--- 黄金矿工

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 ​​​​​​http://t.csdnimg.cn/6AbpV 数据结构与算法 ​​​​http://t.csdnimg.cn/hKh2l 前言&#xff1a;这个专栏主要讲述…
阅读更多...
基于SSM的学生信息管理系统

基于SSM的学生信息管理系统

基于SSM的学生信息管理系统资源-CSDN文库 项目介绍 学生管理系统是我从自己学校的综合信息平台得到灵感&#xff0c;于是使用学习过的Spring、SpringMVC、Mybatis框架LayUI完成了这么一套系统。 项目整体难度不大&#xff0c;部署简单&#xff0c;界面友好&#xff0c;代码结…
阅读更多...
免费API-JSONPlaceholder使用手册

免费API-JSONPlaceholder使用手册

官方使用指南快速索引>>点这里 快速导览&#xff1a; 什么是JSONPlaceholder?有啥用?如何使用JSONPlaceholder? 关于“增”关于“改”关于“查”关于“删”关于“分页查”关于“根据ID查多个” 尝试自己搭一个&#xff1f;扩展的可能&#xff1f; 什么是JSONPlaceho…
阅读更多...
机器学习（一） -- 概述

机器学习（一） -- 概述

系列文章目录 机器学习&#xff08;一&#xff09; -- 概述 机器学习&#xff08;二&#xff09; -- 数据预处理 未完待续…… 目录 系列文章目录 前言 一、机器学习定义&#xff08;是什么&#xff09; 二、机器学习的应用&#xff08;能做什么&#xff09; 三、***机器…
阅读更多...
ArkUI动画概述

ArkUI动画概述

目录 1、按照页面分类 2、按照功能分类 3、显示动画 4、属性动画 动画的原理是在一个时间段内&#xff0c;多次改变UI外观&#xff0c;由于人眼会产生视觉暂留&#xff0c;所以最终看到的就是一个“连续”的动画。UI的一次改变称为一个动画帧&#xff0c;对应一次屏幕刷新&a…
阅读更多...
图像分割实战-系列教程2：Unet系列算法（Unet、Unet++、Unet+++、网络架构、损失计算方法）

图像分割实战-系列教程2：Unet系列算法（Unet、Unet++、Unet+++、网络架构、损失计算方法）

图像分割实战-系列教程 总目录 语义分割与实例分割概述 Unet系列算法 1、Unet网络 1.1 概述 整体结构&#xff1a;概述就是编码解码过程简单但是很实用&#xff0c;应用广起初是做医学方向&#xff0c;现在也是 虽然用的不是很多&#xff0c;在16年特别火&#xff0c;在医学…
阅读更多...
GRNdb：解码不同人类和小鼠条件下的基因调控网络

GRNdb：解码不同人类和小鼠条件下的基因调控网络

GRNdb&#xff1a;解码不同人类和小鼠条件下的基因调控网络 摘要introduction数据收集和处理Single-cell and bulk RNA-seq data collection and processing 单细胞和bulk RNA-seq 数据收集和处理Cell cluster identification for scRNA-seq datasets &#xff08;scRNA-seq 数…
阅读更多...
在 Linux 中使用 cat 命令

在 Linux 中使用 cat 命令

cat 命令用于打印文本文件的文件内容。至少&#xff0c;大多数 Linux 用户都是这么做的&#xff0c;而且没有什么问题。 cat 实际上代表 “连接(concatenate)”&#xff0c;创建它是为了 合并文本文件。但只要有一个参数&#xff0c;它就会打印文件内容。因此&#xff0c;它是用…
阅读更多...
vscode中默认shell选择

vscode中默认shell选择

terminal.integrated.defaultProfile.linux在vs的Preference的Settings里面搜索terminal.integrated.defaultProfile.linux&#xff0c;默认的应该是null&#xff0c;将其修改为bash即可。 linux———/bin/sh、 /bin/bash、 /bin/dash的区别
阅读更多...
[设计模式 Go实现] 创建型～抽象工厂模式

[设计模式 Go实现] 创建型～抽象工厂模式

抽象工厂模式用于生成产品族的工厂&#xff0c;所生成的对象是有关联的。 如果抽象工厂退化成生成的对象无关联则成为工厂函数模式。 比如本例子中使用RDB和XML存储订单信息&#xff0c;抽象工厂分别能生成相关的主订单信息和订单详情信息。 如果业务逻辑中需要替换使用的时候…
阅读更多...
基于JWT的用户token验证

基于JWT的用户token验证

1. 基于session的用户验证 2. 基于token的用户身份验证 3. jwt jwt代码实现方式 1. 导包 <dependency><groupId>com.auth0</groupId><artifactId>java-jwt</artifactId><version>3.18.2</version> </dependency> 2. 在登录…
阅读更多...
golang锁源码【只有关键逻辑】

golang锁源码【只有关键逻辑】

条件锁 type Cond struct {L Lockernotify notifyList } type notifyList struct {wait uint32 //表示当前 Wait 的最大 ticket 值notify uint32 //表示目前已唤醒的 goroutine 的 ticket 的最大值lock uintptr // key field of the mutexhead unsafe.Pointer //链表头…
阅读更多...
Redis经典五大类型源码及底层实现（一）

Redis经典五大类型源码及底层实现（一）

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱吃芝士的土豆倪&#xff0c;24届校招生Java选手&#xff0c;很高兴认识大家&#x1f4d5;系列专栏&#xff1a;Spring源码、JUC源码、Kafka原理、分布式技术原理、数据库技术&#x1f525;如果感觉博主的文章还不错的…
阅读更多...
Excel模板填充：从minio上获取模板使用easyExcel填充

Excel模板填充：从minio上获取模板使用easyExcel填充

最近工作中有个excel导出的功能&#xff0c;要求导出的模板和客户提供的模板一致&#xff0c;而客户提供的模板有着复杂的表头和独特列表风格&#xff0c;像以往使用poi去画是非常耗时间的&#xff0c;比如需要考虑字体大小&#xff0c;单元格合并&#xff0c;单元格的格式等问…
阅读更多...
Cisco模拟器-企业网络部署

Cisco模拟器-企业网络部署

某企业园区网有&#xff1a;2个分厂&#xff08;分别是&#xff1a;零件分厂、总装分厂&#xff09;1个总厂网络中心 1个总厂会议室&#xff1b; &#xff08;1&#xff09;每个分厂有自己的路由器&#xff0c;均各有&#xff1a;1个楼宇分厂网络中心 每个楼宇均包含&#x…
阅读更多...
Apache Doris (五十五）： Doris Join类型 - Colocation Join

Apache Doris (五十五）： Doris Join类型 - Colocation Join

🏡 个人主页：IT贫道_大数据OLAP体系技术栈,Apache Doris,Clickhouse 技术-CSDN博客 🚩 私聊博主：加入大数据技术讨论群聊，获取更多大数据资料。 🔔 博主个人B栈地址：豹哥教你大数据的个人空间-豹哥教你大数据个人主页-哔哩哔哩视频 目录 1. Colocation Join原理
阅读更多...
Gitee触发Jenkins403讨逆猴子-解决方案

Gitee触发Jenkins403讨逆猴子-解决方案

Jenkins报&#xff1a;403 No valid crumb was included in the request 具体解决方案如下&#xff1a; 执行如下脚本内容&#xff1a; hudson.security.csrf.GlobalCrumbIssuerConfiguration.DISABLE_CSRF_PROTECTION true成功后&#xff1a; Gitee再次测试&#xff1a…
阅读更多...
51单片机项目（24）——基于51单片机的温控风扇protues仿真

51单片机项目（24）——基于51单片机的温控风扇protues仿真

1.功能设计 使用传感器测量温度&#xff0c;并将温度显示在LCD1602上。如果温度超过阈值&#xff0c;那么就打开风扇&#xff0c;否则风扇不打开。&#xff08;仿真的时候&#xff0c;用直流电机模拟风扇&#xff09;。 仿真截图如下&#xff1a; 此时温度是27度&#xff0c;我…
阅读更多...
C++初阶——基础知识（函数重载与引用）

C++初阶——基础知识（函数重载与引用）

目录 1.命名冲突 2.命名空间 3.缺省参数 4.函数重载 1.函数重载的特点包括&#xff1a; 2.函数重载的好处包括&#xff1a; 3.引用 引用的特点包括 引用的主要用途包括 引用和指针 引用 指针 类域 命名空间域 局部域 全局域 第一个关键字 命名冲突 同一个项目之间冲…
阅读更多...
最新文章

Copyright @ 2022~2023