【数据结构】单链表之--无头单向非循环链表

2023-11-11 14:36
文章标签 链表 数据结构 循环 单链 单向 无头 表之

本文主要是介绍【数据结构】单链表之--无头单向非循环链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：前面我们学习了动态顺序表并且模拟了它的实现，今天我们来进一步学习，来学习单链表！一起加油各位，后面的路只会越来越难走需要我们一步一个脚印！

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:数据结构 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力！
在这里插入图片描述

单链表

今天我们要实现的全部功能就如下所示，功能很多我们一步一步来，一起来手撕链表吧！加油！

typedef int SLNDataType;typedef struct SList
{int val;struct SList* next;
}SLNode;//单链表的打印
void SLTPrint(SLNode* phead);//单链表的尾插
void SLTPushBack(SLNode** pphead, SLNDataType x);//单链表的头插
void SLTPushFront(SLNode** pphead, SLNDataType x);//单链表的尾删
void SLTPopback(SLNode** pphead);//单链表的头删
void SLTPopFront(SLNode** pphead);//单链表的元素查找
SLNode* SLFind(SLNode* phead, SLNDataType x);//单链表的插入-在pos的前面插入
SLNode* SLInsert(SLNode** pphead,SLNode* pos, SLNDataType x);//需要自己思考一级还是二级//单链表的删除
void SLTErase(SLNode** pphead, SLNode* pos);//单链表的销毁
void SLTDestroy(SLNode** pphead);//单链表的删除-pos之后的元素
void SLTEraseAfter(SLNode* pos,SLNDataType x);//单链表插入-pos之后插入
void SLTInsertAfter(SLNode* pos,SLNDataType x);

动态申请一个结点

代码思路，首先我们要开辟一个结构体，来开始我们今天的单链表

typedef struct SList
{int val;struct SList* next;
}SLNode;

当然了，我们肯定得写一个接口，来申请动态开辟的一个结点(这个我们在前面写顺序表的时候就写过了，就不过多介绍这个了)，可以看下图帮助自己理解在这里插入图片描述

SLNode* CreateNewNode(SLNDataType x)//开辟一个新的节点
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL)//判断是否有空间{perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}

单链表的打印

代码思路：单链表中我们可以知道它是如下图这种形式，每一个结构体中存着下个节点的地址，我们可以通过判断结构体指针是否为空指针来依次打印
在这里插入图片描述

void SLTPrint(SLNode* phead)
{SLNode* cur = phead;//通过头节点依次访问while (cur != NULL){printf("%d->", cur->val);cur = cur->next;}printf("NULL\n");
}

单链表的尾插

在写代码之前，我们需要重新复习一下，对形参的修改不会改变实参,形参是实参的一个临时拷贝（请牢牢记住，后面有很大的作用），这在后面帮助我们理解单链表有很大的帮助。
我们先来看一串代码

void swap(int* a, int* b)
{int tmp = 0;tmp = *a;*a = *b;*b = tmp;
}int main()
{int a = 3;int b = 5;swap(&a, &b);printf("a = %d,b = %d", a, b);return 0;
}

我们要想改变
在这里插入图片描述

void swap(int** a, int** b)
{int tmp = 0;tmp = **a;**a = **b;**b = tmp;
}int main()
{int arr1[] = { 1 };int arr2[] = { 2 };int* a = arr1;int* b = arr2;swap(&a, &b); printf("*a = %d, *b = %d",*a, *b);return 0;
}

在这里插入图片描述
由这些可以知道，我们要想修改一级指针里面的值，我们要用二级指针接收。接下来我们就开始上我们的第一盘凉菜了！
代码思路：首先我们肯定要考虑两种情况，即一种是链表是空的什么都没有，另一种即链表中有值，需要我们尾增新的值，我们可以借助下图来帮助我们分析！我们通过循环找到该链表的尾结点，然后让尾部结点中的next，假如链表中没有值是空链表，我们直接指向新的结点即可。
在这里插入图片描述

void SLTPushBack(SLNode** pphead, SLNDataType x)//尾插节点
{assert(pphead);//判断传过来的链表是否存在SLNode* newnode = CreateNewNode(x);//开辟节点if (*pphead == NULL)//判断传来的是否是空指针，如果为空就直接开辟新的节点{*pphead = newnode;}else{SLNode* tail = *pphead;while (tail->next != NULL)//只有尾结点的next才是空{tail = tail->next;//找到尾节点}tail->next = newnode;//将为节点的值指向新节点}
}

这里大家肯定会有很多疑问，为什么是 **phead ,我们来看下图
在这里插入图片描述

函数测试与结果运行图：

void Test1()
{SLNode* plist = NULL;SLTPushBack(&plist, 1);//尾插SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);
}int main()
{Test1();return 0;
}

在这里插入图片描述

单链表的头插

代码思路：单链表的头插我们依然得借助图像来帮助我们分析如下图，我们让*phead指向newnode开辟的结点，在让newnode->next指向原本的头结点即可完成头插，当然我们依然得用二级指针接收，因为我们要修改的一级指针。
在这里插入图片描述
代码实现：

void SLTPushFront(SLNode** pphead, SLNDataType x)//单链表的头插
{assert(pphead);SLNode* newnode = CreateNewNode(x);//开辟一个新的节点newnode->next = *pphead;//将头节点地址存放在next中*pphead = newnode;  //在让头节点指向Newnode，此时newnode就称为了头节点
}

函数测试与效果图：

void Test2()
{SLNode* plist = NULL;SLTPushFront(&plist, 2);//头插SLTPushFront(&plist, 2);SLTPushFront(&plist, 9);SLTPrint(plist);
}int main()
{//Test1();Test2();return 0;
}

在这里插入图片描述

单链表的尾删

思路分析：在单链表的尾部删除中，我们需要考虑两种情况一种为单节点，一种为多节点，即一种删除完后链表中的值为空，另一种即删除最后一个后仍然还有结点。当然了，我们依然得先画图分析，如下图。我们看图一，可以知道，我们直接找到 *phead这个结点将他free掉即可，然后将 *phead置为空指针，即可完成单结点的删除。我们看图二，我们得找到一个尾结点将它释放，将尾部结点的前一个结点中的next即保留最后一个结点中的地址，让它置为空指针即删除完毕，由此我们可以通过一个快慢指针，一个指针往后走，一个保留前一个结点的地址，因此我们可以找到最后一个结点并保留前一个结点的地址。
在这里插入图片描述

在这里插入图片描述

代码思路：

void SLTPopback(SLNode** pphead)//单链表的尾删
{//一个节点//多个节点assert(pphead);assert(*pphead);if ((*pphead)->next == NULL)//单节点{free(*pphead);//释放pphead所在的空间*pphead = NULL;//将pphead置为空指针}else//多节点{SLNode* tail = *pphead;//铜鼓快慢指针来找到节点SLNode* prev = NULL;while (tail->next != NULL)//找到尾节点{//倒数第一步(尾节点的前一个节点时)prev = tail;//此时prev就是记录后一个节点的地址tail = tail->next;//此时找到了NULL}free(tail);//释放掉记录尾结点的地址prev->next = NULL;//将此时赋值为NULL即删除成功}
}

函数测试与运行结果：

void Test3()
{SLNode* plist = NULL;printf("打印删除之前的\n");SLTPushFront(&plist, 2);//头增SLTPushFront(&plist, 2);SLTPushFront(&plist, 9);SLTPrint(plist);printf("打印删除之后的\n");SLTPopback(&plist);//尾删SLTPopback(&plist);SLTPrint(plist);
}int main()
{//Test1();//Test2();Test3();return 0;
}

在这里插入图片描述

单链表的头删

思路分析:实现头删，我们就是把头部中的空间free掉,在将 *phead指向原本的第二个节点即可，因此我们需要用一个结构体指针指向第二个节点将其保留下来传给原本的头指针。可以通过下图帮助自己分析，如下图。
在这里插入图片描述
代码思路实现：

void SLTPopFront(SLNode** pphead)//头删
{//空assert(pphead);//多个节点SLNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;	
}

测试函数与运行结果：

void Test4()
{SLNode* plist = NULL;printf("打印删除之前的\n");SLTPushFront(&plist, 2);//尾增SLTPushFront(&plist, 2);SLTPushFront(&plist, 9);SLTPrint(plist);printf("打印删除之后的\n");SLTPopFront(&plist);//头删SLTPopFront(&plist);SLTPrint(plist);
}
int main()
{//Test1();//Test2();//Test3();Test4();return 0;
}

在这里插入图片描述

单链表的数值查找

思路分析：我们可以通过指针去一次遍历链表中的数据，找到对应值即找到了，返回此时指针的地址，遍历到最后一个NULL也没有找到时，即返回空指针，如下图在这里插入图片描述
代码实现:

SLNode* SLFind(SLNode* phead, SLNDataType x)//查找
{assert(phead);SLNode* tail = phead;while (tail){if(tail->val == x){return tail;//返回此时指针的值}tail = tail->next;}return NULL;
}

函数测试与效果图：

void Test5()
{SLNode* plist = NULL;printf("打印删除之前的\n");SLTPushFront(&plist, 2);//尾增SLTPushFront(&plist, 2);SLTPushFront(&plist, 9);SLTPrint(plist);printf("查找结果:\n");printf("%p\n",SLFind(plist, 2));//查找数printf("%p\n", SLFind(plist, 99));
}
int main()
{//Test1();//Test2();//Test3();//Test4();Test5();return 0;
}

在这里插入图片描述

单链表的插入- 在pos的前面插入

思路分析：如果是多节点要想实现在pos的前面插入，首先我们要找到pos的前面一个节点让它指向我们新开辟的节点newnode然后再让newnode->next指向我们原本pos的所在的节点就完成了头插，如下图1所示。如果是单节点的时候，就是相当于头插，我们只需要判断是否是单节点，如果是就直接调用头插函数即可。
在这里插入图片描述
代码实现：

SLNode* SLInsert(SLNode** pphead, SLNode* pos, SLNDataType x)//单链表插入
{assert(pphead);assert(pos);assert(*pphead);//单节点if (*pphead == pos){//头插SLTPushFront(pphead, x);}else{//多节点SLNode* tail = *pphead;SLNode* newnode = CreateNewNode(x);while (tail->next != pos){tail = tail->next;}tail->next = newnode;newnode->next = pos;}
}

函数测试与效果图：

void Test6()
{SLNode* plist = NULL;printf("原本的值\n");SLTPushFront(&plist, 2);//尾增SLTPushFront(&plist, 2);SLTPushFront(&plist, 9);SLTPrint(plist);printf("插入之后的结果\n");SLNode* address = SLFind(plist, 2);//查找数SLInsert(&plist, address, 10);SLTPrint(plist);
}
int main()
{//Test1();//Test2();//Test3();//Test4();//Test5();Test6();return 0;
}

在这里插入图片描述

单链表数值的删除-删除Pos前的值

思路分析：当然了单链表的删除我们依然得采用俩种情况，一种情况为单节点，一种情况为多节点，我们先来分析多节点，如果是多节点的情况，我们应当找到pos的节点将它释放掉，并且我们应当将pos的前一个节点将他记录下来，并让它指向pos之后的一个节点，此时我们即可完成数值的删除。如下图所示，如果是单节点的情况，我们可以直接当成头删，直接调用头删函数即可。
在这里插入图片描述

代码实例：

void SLTErase(SLNode** pphead, SLNode* pos)//数值的删除
{assert(pphead);//判断传来的结构体是否存在assert(*pphead);//判断是否为空指针assert(pos);//判断空地址if (*pphead == pos){SLTPopFront(pphead);//头删}else{SLNode* tail = *pphead;while (tail->next != pos){tail = tail->next;}tail->next = pos->next;free(pos);pos = NULL;}
}

函数测试与效果图：

void Test7()
{SLNode* plist = NULL;printf("原本的值\n");SLTPushFront(&plist, 2);//尾增SLTPushFront(&plist, 3);SLTPushFront(&plist, 2);SLTPushFront(&plist, 9);SLTPrint(plist);printf("删除之后的结果\n");SLNode* address = SLFind(plist, 2);//查找数SLTErase(&plist, address);SLTPrint(plist);
}
int main()
{//Test1();//Test2();//Test3();//Test4();//Test5();//Test6();Test7();return 0;
}

在这里插入图片描述

单链表的销毁

思路分析：要想销毁单链表中的所有值，我们只需要把单链表中的每个节点给它释放，并最后让头节点指向空指针即可，因此我们需要借助两个指针，一个指针指向tail的下一个节点，当释放掉tail后让tail可以指向下一个节点再依次释放，这样就可以达到链表的销毁的作用，如下图所示。
在这里插入图片描述
代码实例：

void SLTDestroy(SLNode** pphead)//单链表的销毁
{assert(*pphead);//判断传来的是否已经是空指针SLNode* tail = *pphead;SLNode* pre = NULL;while (tail != NULL)//找到尾节点{pre = tail->next;free(tail);//依次释放tail = pre;}*pphead = NULL;
}

函数测试与效果图:

void Test8()
{SLNode* plist = NULL;printf("原本的值\n");SLTPushFront(&plist, 2);//尾增SLTPushFront(&plist, 3);SLTPushFront(&plist, 2);SLTPushFront(&plist, 9);SLTPrint(plist);printf("删除之后的结果\n");SLTDestroy(&plist);SLTPrint(plist);
}int main()
{//Test1();//Test2();//Test3();//Test4();//Test5();//Test6();Test8();return 0;
}

在这里插入图片描述

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。

🫵🫵🫵 祝各位接下来好运连连 💞

这篇关于【数据结构】单链表之--无头单向非循环链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/390743。

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2