做电影平台网站怎么赚钱吗,素材分享网站源码,免登录直接玩的游戏,淘宝客返利网站开发前言#xff1a; 小编在近日学习了单链表的知识#xff0c;为了加强记忆#xff0c;于是诞生了这一篇文章#xff0c;单链表是数据结构比较重要的知识#xff0c;读者朋友们一定要去好好的学习#xff01;这个可以说是比顺序表更好用的线性表#xff0c;下面废话不多说 小编在近日学习了单链表的知识为了加强记忆于是诞生了这一篇文章单链表是数据结构比较重要的知识读者朋友们一定要去好好的学习这个可以说是比顺序表更好用的线性表下面废话不多说开始进入单链表的学习喽 目录 1.单链表 1.1.链表的概念与单链表 1.2.单链表的结构 1.3.单链表的性质 2.单链表功能的代码实现 2.1.单链表的打印 2.2.单链表的尾插 2.3.单链表的头插 2.4.单链表的尾删 2.5.单链表的头删 3.还有一些函数没写由于小编不想让篇幅太大所以分成了两部分 正文
1.单链表
1.1.链表的概念 链表是一种物理结构上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表也有很多的种类比如单链表双链表等等小编今天讲述的就是单链表下面小编来讲述一下单链表的结构
1.2.单链表的结构
引例 对于单链表的结构小编先给出一个引例火车我相信各位读者朋友都坐过没坐过也应该见过火车是由车头和一节一节的车厢组成如下图所示 在人们乘车少的时候火车可以减少车厢具体减少哪个车厢这是可以随机指出的并不一定就是去掉最后一个车厢我们也可以把中间的给删除在旅游旺季的时候我们同样也可以加上几节车厢来应对人多车少的情况。
1.2.1.结点的概念 单链表就类似火车车厢一样它也可以随时的减少随时的增加我们把单链表中的每一表称之为结点所以可以这么说单链表是由一个一个结点构成的单链表和顺序表最大的不同就是单链表当中的结点是一个一个动态内存申请出来的不是和顺序表一样基于数组来进行书写的下面小编将会给各位讲述一下单链表的结构
·1.2.2.单链表的结构 小编在上图给各位读者朋友了单链表的结构图细细一看我们可以看出每一个结点里面都存储着数据类型和一个地址不难发现结点里面的地址都对应着下一个结点所以单链表就是靠地址来进行连接的那么肯定有读者朋友会感到疑惑这么一看单链表的物理结构不还是连续的其实这个说法是错误的可能每一个单链表都隔着很远才进行的链接所以单链表是不连续的不和顺序表的一样我们可以看到单链表中最后一个结点指向的是NULL这里展示了单链表也是有始有终的下面我们来简单介绍一下单链表的性质
1.3.单链表的性质 单链表的性质可以分为三个 1.单链表在逻辑上是连续的线性表统一的性质在物理结构是不连续的。 2.结点一般都是从堆上申请的。 3.从堆上申请的空间是按照一定策略分配出来的每次申请的空间可能连续也可能不连续 其实性质我们用多了自然也会记住了对于编程的学习我们不是靠死记硬背下来的而是不断的去应用应用多了自然就熟悉了 我们已经讲述了单链表的概念和性质我们可不能纸上谈兵下面小编将带着大家手动的一步一步的去实现单链表 2.单链表功能的代码实现 在讲述那些单链表的增删查改之前我们现在肯定要先创建一个单链表我们已经学习了顺序表和单链表的知识单链表的结构图也在上面进行展示了那么下面我们就可以实现单链表的创建了对于数据部分我们不一定是存储整型浮点型等等所以我们可以类似顺序表用typedef关键字来对类型改名后面我们可以统一进行替换。下面是代码的实现
typedef int SLdate; //方便后面整体类型的改变//创立一个单链表
typedef struct Slist {//先设置一个类型SLdate date;struct Slist* next; //存放下一个节点的地址
}SLTNode; 此外对于单链表代码的书写小编同样是分成了三个文件与顺序表一样这三个文件分别是头文件用于单链表的创建各种函数的声明源文件函数的实现源文件代码的测试我们每写完一个函数一定一定记着先测试免得到后面在慢慢改这样显得太麻烦了下面我们开始实现一一函数的功能 2.1.单链表的打印 虽然我们还没有开始放置数据但我们一定要先学会单链表的打印这个与我们正常的打印是不同的 首先我们肯定要创建一个函数下面是代码呈现 void SLTprintf(SLTNode* phead);//此时phead代表的是头节点就是第一个节点 正如代码解释所说phead属于头结点我们想要打印每一个结点的数据肯定要先知道它的头节点之后我们可以通过它的头结点来开始对下一个节点进行遍历直到遇到NULL这样我们便可以停止打印所以不难想到这里我们用到了循环的知识通过每一次循环来打印数据之后再让下一个结点代替当前结点不过在这之前我们应该做到对于头结点不让它做出改变因为我们倘若任由头节点进行改变那么之后我们在这个函数中会再也不会找到链表的头这样就得不偿失了所以我们用一个新的结点来存放头节点让它做出对应的的改变下面是代码的呈现
void SLTprintf(SLTNode* phead)
{SLTNode* pour phead; //这么做是为了保证头节点不会发生改变while (pour){printf(%d-, pour-date);pour pour-next;}printf(NULL\n);
} //这个操作是打印单链表的数据2.2.单链表的尾插 我们在简述完打印后肯定要讲述单链表的增删查改了我们先从单链表的尾插说起对于单链表的尾插这其实和顺序表的尾插有点类似的不过在顺序表中在顺序表中我们是扩容操作而在单链表中我们实现的是插入结点操作在插入结点之前我们是肯定先要创建一个新的结点作为我们要插入的结点不过我们在实现尾插之前肯定是要先创建一个函数的这里有我们值得注意的一个点那就是我们传过去的应该是单链表指针的地址也就是传一个二级指针过去这是一个重要的点因为我们要对单链表指针进行改变对于内容的改变我们需要传址调用来实现下面是函数的创建
void SLTPushBack(SLTNode** pphead, SLdate x);首先我们需要先分装出一个函数用来作为新结点的创建这里我们需要用到malloc函数来对开辟出一个新的空间来作为新节点空间之后我们再将数据转化为我们想要的数据再让下一个结点置为空就好这个操作可以类似于顺序表的扩容操作下面是代码实现
SLTNode* SLTbuynode(SLdate x)
{SLTNode* pour (SLTNode*)malloc(sizeof(SLTNode));assert(pour);pour-date x;pour-next NULL;return pour;
} 之后我们就开始进行插入操作这里我们分为两种情况 第一种情况是头节点为空这个就很简单了我们将新节点的内容直接给予头节点就好了这对于屏幕前的你当然是小case尾插的大头就是下一个情况了 第二种情况就是头节点不为空正式进行尾插操作这个操作其实是蛮简单的我们只需要先进行循环找到尾结点让尾结点的next指针指向新结点就好了下面我们用图文进行解释这里用pcur当作尾结点 这样我们便可以实现尾插操作下面是代码实现
void SLTPushBack(SLTNode** pphead, SLdate x)
{//首先可以先建一个函数这个函数是来开辟一个新节点的后面想要插入直接调用就好了assert(pphead);SLTNode * p SLTbuynode(x);if (*pphead NULL) //首先判断{*pphead p;}else{SLTNode* pour *pphead; //保证头节点不做出改变while (pour - next){pour pour-next;}pour-next p;}
}2.3.单链表的头插
//头插
void SLTPushFront(SLTNode** pphead, SLdate x); 我们在看完尾插操作以后紧接着头插就来了同样的头插函数也需要先有一个新的结点的建立去小编在上面已经叙述了就不再多谢了同样的头插也同样分为了两种情况 第一种情况是是头结点是不存在的这时候只需要将新节点设置为头节点就好了。 第二种情况是头节点是存在的这时候需要我们将新节点的下一个结点指向为原来的头节点再将头节点更改为新节点就好了。具体情况小编用图文进行解释 不过此时不难看拿出头插函数似乎是不需要分两种情况讨论的因为两种情况都涉及了将新节点的下一个结点变为头节点所以我们将两种情况合并下来就好了下面是代码呈现
void SLTPushFront(SLTNode** pphead, SLdate x)
{assert(pphead);SLTNode* newnode SLTbuynode(x);newnode-next *pphead;*pphead newnode;
}
2.3.单链表的尾删
//尾删
void SLTPopBack(SLTNode** pphead); 简单的插入函数就先告一段落了下面我们来进行删除操作首先登场的就是尾删尾删操作与顺序表的尾删一个概念就是把单链表的尾结点置为空首先我们需要保证头节点是存在的不然单链表都是空的我们删来删去也没什么意思了这里可以用assert断言来判断下头节点是否为空之后我们就可以进行删除操作·。 首先我们要先定义两个指针一个指向头节点这个的作用是找到尾结点一个为空这个的作用我们稍后就知道之后我们采用循环让空指针在刚开始指向第一个指针再让第一个指针一直往后走我们是要找到尾结点所以我们循环结束的条件就是第一个指针的下一个结点不指向空之后第一个指针变成了尾结点第二个指针变成了尾结点之前的结点这样我们就可以让第二个指针的下一个置为空然后再让第一个指针释放掉这样我们就完成了尾删操作不过此时细心的读者朋友可能会发现如果单链表只有头节点的话这时候上面就不成立了我们这里就对空指针进行解引用了所以尾删操作我们同样也是分为两种情况 第一种是如果只有头节点的话我们直接将头节点变为空这里就完成了尾删操作。 第二种情况就是正常情况方法就是上面所讲下面是图文解释代码呈现 void SLTPopBack(SLTNode** pphead)
{assert(pphead *pphead);if ((*pphead)-next NULL){*pphead NULL;}else{SLTNode* pour *pphead;SLTNode* plist NULL;while (pour-next){plist pour;pour pour-next;}plist-next NULL;free(pour);pour NULL;}
}2.5.单链表的头删 尾删我们讲完了下面是头删环节与尾删一样我们首先要判断头节点是否为空如果为空直接报错就好了之后我们就要进行正常的头删操作了头删操作我们也要创建一个指针·这个指针表示头节点之后我们直接让现头节点变成原头节点的下一个结点然后我们再将指针释放这里我们便完成了单链表的头删操作是不是很简单呢下面小编给出图文解释和代码呈现 void SLTPopFront(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* pour *pphead;*pphead (*pphead)-next;free(pour);pour NULL;
}总结 正如小编上面所说小编不想让文章的篇幅太大于是小编就把博客分装成了两部分来进行书写单链表的操作当然不仅限于这些了下一篇将会是重点如果文章有错误恳请在评论区指出小编肯定会改正下面小编将要肝下篇文章了那我们下一篇文章见喽
