沈阳网站建设seo优化,高端网站建设 飞沐,前程无忧招聘网下载app官网,wordpress 加入字体库作者#xff1a;几冬雪来 时间#xff1a;2023年3月3日 内容#xff1a;数据结构链表讲解 目录
前言#xff1a;
链表的概念#xff1a;
1.为什么要有链表#xff1a;
2.链表的运行原理#xff1a;
3.链表的形态多少#xff1a;
4.单链表的代码书写#xff1… 作者几冬雪来 时间2023年3月3日 内容数据结构链表讲解 目录
前言
链表的概念
1.为什么要有链表
2.链表的运行原理
3.链表的形态多少
4.单链表的代码书写
1.创建文件
2.创建结构体
3.链表的打印
4.链表执行
5.尾插
6.头插
7.尾删
8.头删
9.代码 结尾 前言 在上一篇博客中我们结束了对顺序表的讲解在讲解顺序表的过程中一个新的概念——线性表被提起通过了解得知顺序表和链表都属于线性表的一种而在之前我们讲解了顺序表的内容那么今天就要讲解数据结构另一大重要的内容——链表。 链表的概念 链表是一种物理存储结构上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 1.为什么要有链表
在之前有说过顺序表和链表都属于线性表中的一种。那么为什么在学习完顺序表后还要再去学习链表呢那肯定是因为链表相较于顺序表有它的优势所在那么顺序表对比起链表有哪些劣势的地方存在我们一一说明一下。 以上两条就是顺序表的缺点这里有人可能不太了解空间浪费是什么意思 举个例子来说明正常情况下每当我们空间不够的时候都会进行扩容操作而每次扩容我们不可能只增加一小块空间通常扩容后的空间大小是我们原大小的一或者两倍。这里假设我们开辟了150个数据的空间但是实际上我们要存的值只有101个这里我们的空间就会浪费。这都是因为顺序表开辟的空间是连续的的特性。
2.链表的运行原理
而链表则是一个数据存储在一个内存块它不要求我们的内容连续每个内存块都用指针进行相关的链接。而这些内存块在链表里面则被称为——结点。 这里如果想通过第一个数据找到第二个的值该怎么办这里则将这里的第一个数据的后面存放下一个数据的地址类似我们的锁链一样。
3.链表的形态多少
和顺序表的插入还有细分为头插和尾插两种方式一样我们的链表也足足有8种之多的形态。不过在数据结构的学习中8种形态并不会全部讲解我们会在这8种形式中挑2种十分常用且有代表性的形式来讲解那么今天所讲解的就是我们其中的单链表。
4.单链表的代码书写
既然已经对链表的概念有所了解那么接下来我们就一点一点的写单链表的代码并对其进行分析。
1.创建文件
从上文可以得知顺序表和链表都被归于线性表中因此写顺序表代码的前置条件在写链表的时候也要使用。 这里依旧创建一个.h文件和两个.c文件。
2.创建结构体
顺序表和链表本质是相似的因此和顺序表一样凡是有多个数据我们都应该将数据存储到我们的结构体当中去那么在写链表的时候结构体里面要存放什么数据 首先是像写顺序表代码一样将int类型重命名。接下来书写链表结构体内的内容一开始先定义一个数据但是接下来定义的这个指针就有人看不懂了。这里在结构体中为什么突然多出来这个东西
根据上文所讲我们在第一个数据的后面存放下一个数据的地址。而我们每一个结点就是一个结构体因此在这里我们存下一个结点的地址也就是存放一个结构体类型的指针。
有人这里就要说了结构体里面再次调用结构体这种方法在C语言中不是不行的吗这种方式确实不行但是在这个结构体中我们其实是存放了一个地址而并非结构体只是刚好我们这个指针的类型是结构体类型罢了。所以这里并不会报错然后在最后将结构体进行重命名就行了。
3.链表的打印
在写链表代码的过程中理解它也是我们应该做的一件事情那么既然要理解单凭口头讲解肯定是不够彻底的因此我们需要先将其代码写出来。
链表的打印可以说是链表讲解中最简单的一个部分与顺序表的打印内容不同链表的打印不需要多个数据什么的。 在打印的时候在这里只需要一个指针指向我们的第一个结点。 在这里我们就遇到了链表的第一个问题在打印链表的时候一开始需要对其进行断言吗其实在写链表代码我们是不需要对其断言的。这里有人就可能要问了不是说顺序表和链表都属于线性表。那么在顺序表中最基本的对指针进行断言的操作为什么在链表中却不用了 首先如果在一开始没有断言这样可能导致顺序表或者链表为空。那么如果链表或者顺序表为空的话我们能否去打印它们呢
如果顺序表为空的话其实还是可以将其打印出来只不过里面没有数据。
接下来是空的链表空链表也是可以打印出来的一般我们链表都以空为结束。如果一开始进行断言的话程序直接被终止掉了这样是不合适的。
还有就是这两个结构其实是不一样的链表的指针是指向第一个存有数据的节点而我们的顺序表的指针指向的是结构体。哪怕顺序表中应该数据都没有但是它的结构还是存在的顺序表里有无数据是由size来决定的但是如果这个结构体的指针都为空size的大小就毫无意义了。
4.链表执行
接下来继续写我们的代码。 大家能看得懂这段代码想表达的意思吗我们来一步一步讲解一下。
一开始我们建立一个指针然后把phead赋值给cur这样子我们的cur也会指向第一个节点的位置和顺序表的结束方法不同链表是以空也就是NULL结束的所以循环条件就应该是不为空。
接下来打印数据的话就像顺序表的那样进行指向在打印完了一个值之后我们就要找下一个值的位置那应该怎么走这里就用cur指向next就可以指向下一个值的地址。 就像这里cur一开始指向值的地址值next以后指向结构体的下一个成员这个成员存放着2的地址。所以cur经过next之后指向了2的地址打印出来也就是2的值。到了最后cur指向4后下一个值为空我们循环结束。 当然这里的条件也可以进行修改。
5.尾插
在写完了什么较简单的代码后接下来就要向更深入的知识点前进了。
记得在我们书写顺序表的代码中第一个执行的程序就是尾插数据那么在书写链表的时候第一个程序还是尾部插入。 这里还是一样一开始先创建一个结点但是在这里又和顺序表的结构不一样。因为链表的空间并不连续因此并不用和顺序表一样进行扩容链表的空间是随时都有的。然后检查我们有没有创建结点接下来将要插入的结点进行初始化。
剩下的就是将这个新结点和上一个结点进行对接严格来说就是找上一个结点的尾。 不为空链表的尾插 尾插的本质原尾节点中要存储新尾结点的地址 但是在链接的过程中是有一个坑的很多人都被坑到过那是什么样的代码我们将其写出来看看。 这么看来代码是没有问题的一开始将phead赋值给同类型的tail这样tail也指向第一个结点的地址而后tail不为0我们让tail指向结构体的第二个元素后赋值给tail最后将指针变量newnode赋值给tail看似没有问题但是这里忽略了一个重要的因素。
这里我们的tail和newnode变量都是局部变量出了作用域要被销毁。 因此这样链表并没有被链接起来链表连接需要我们上一个结点存下一个结点的地址。那代码要怎么修改 这里我们就把newnode的值也就是我们想添加的值的地址给了tail的next链表链接其实改的是这个结构体。在上一个代码中我们只是将一个指针赋值给另一个指针而在这个代码中则是用next存放下一个结点的地址二者是有差别的。
这里我们的尾插代码看似差不多完成了但是其实这里还有问题的存在。如果这个链表为空程序会发生什么这里分两种情况。 第一种情况如果链表为空的话这里直接将结点链接到它的后面。这样就可以打印我们的值了真的是这样吗这里输入几个然后打印出来看看会发生什么 运行结果输出为空很明显结果并不符合预期是代码哪里写错了吗我们将数据调试出来看看出了什么问题。 这里从窗口可以看见一开始的plist为空而后调用函数将指针plist进行传参用phead来进行接收代码往下走因为我们要插入一个值所以要创建一个结点而结点是有它的地址的后面进行判断因为一开始是空链表所以phead为空符合条件接下来再把newnode赋值给phead。看起来一切都合情合理但是这个坑需要仔细寻找。 通过调试看出在最后一步将newnode赋值给phead的代码执行了phead的地址进行了修改但是这里的plist依旧为空没有被修改。这就是这段代码的第二个坑。
为什么plist没有被改变 这里就是C语言中一个最简单的结论形参是实参的一份临时拷贝形参的改变不影响实参。 类似这个代码我们对ptr的改变并不会影响到px这里不是指针的问题类似以前改写一个值我们传的是整形类型后用整形指针接收地址这样形参的改变就可以影响实参。这被称为传址调用如果是用整形同类型来接收的话就会变为传值调用。
而这个代码我们要改变的值的类型是一个指针类型传参后依旧用一个一级指针接收属于同类型因此在这里ptr的改变也不会影响到px那如果要影响到实参代码要如何修改 像这样进行修改即可要求传一级指针的话应该传一级指针的地址而后用一个二级指针来接收这个地址传递的是一级指针接收的是二级指针pptr的改变才能影响到px。 因此也得出一个结论 改变的int*使用int*的地址int**的指针来接收。 可能还是有人不懂程序是怎么运行的我们可以画个图来理解一下。 这就是两种情况第一种因为是同类型传参所以p并没有指向那块空间的地址。第二种我们传一级指针用二级指针来接收相当于px里面存放了要打印值的地址。 因此第一次方法我们p中并没有被赋值Func函数结束后空间销毁p的值依旧为空。 第二种方法里p中存放着想打印的值的地址即使空间被销毁px中依旧存在着这个值。 那么代码要进行修改。 这就是代码改后的样子改进后运行起来试试看。 代码可以正常运行并输出我们想要的结果这就证明我们的这个尾插的代码成功了。但是有眼尖的同学就提出他的问题。在前面刚刚说过这里要用二级指针来改变值但是在最后赋值的时候我们用了一级指针这不就相冲突了吗 首先要明白这里要改变的是什么其实除了第一次赋值要使用到plish在下面我们写代码的过程中已经不需要再用到了。这里改变的对象并不是指针而是结构体因此这里我们并不使用二级指针来改变。
接下来再问一个问题在.h文件中SLPrint需不需要用二级指针来接收答案是不需要。因为这里我们并没有改变指针而是打印数据使用一级指针够用。
那么这里我们头插的代码和需要了解的坑都讲解完毕了。
6.头插
jiang讲解完了尾插接下来就要讲解同源的头插。首先就是一个问题头插的代码书写需不需要和尾插一样使用二级指针这里是需要的。
这里写头插的代码也分为两种情况。我们来看看是分为哪两种情况 一种情况就是链表一开始里面就有数据另一种情况就是指针为空的情况。 开始还是先写代码和尾插一样都是要先创立一个结点而创建结点的方法在尾插的时候就已经书写过了。那么为了避免后面经常要书写创建结点的代码我们可以将其进行封装提取一个公共的函数。 既然提取了一个公共函数那么尾插一开始创建结点的代码就能用函数来代替。同样的写头插的时候也可以引用这个函数。
接下来就来实现头插那么头插数据是怎么样插入的呢我们先将代码书写出来。 这就是我们头插的代码一开始先创建一个结点并赋值给newnode而后这个创建的结点进行赋值因为*pphead指向plis的地址也就是未修改前第一个结点的地址我们将它赋值给newnode的next最后因为第一个结点被改变了因此这里需要将第一个结点改为newnode。 这个就是我们尾插的运行原理。 并且代码可以正常的运行并输出指定的结果那么到这里我们链表的两种插入方法头插和尾插就讲解完毕了。
7.尾删 讲解忘了两种插入方法后下来就是两种删除方法这里我们先讲解两种方法中的——尾删。
首先尾删需不需要二级指针呢这个先放置一下先书写代码。要进行尾删操作首先就是要找到我们的尾。而在尾插的代码中曾经写过找尾的方法这里我们就可以直接引用。 在写尾删的时候很多人会写这种形式的代码看起来是没有问题的。先进行找尾找到了就将其释放掉。但是这样写了之后好多人的程序跑不过去这又是为什么我们试一试用现在这个代码来删除数据试试看。 这块可以看出来如果我们用上面的代码去删除数据的话程序会直接出错。那么为什么会报错呢
在上面这个代码中我们找到了尾结点并将其释放掉。但是这么做导致了倒数第二个结点中的next指向了一个野指针这里置为空也对其没有影响因为这里我们只是对tail置空tail是我们的局部变量并不能对next产生影响。那代码需要怎么样修改。 这就是我们代码修改之后的样子。这里我们新创建了一个指针并初始化为空进入循环后我们先将tail赋值给prev然后tail指向下一个结点到最后我们找到了尾后依旧将其释放置空但是这里prev是指向倒数第二个结点在这里将它的next置空就不会指向野指针了。 这里就成功的进行了尾删操作同时我们这个尾删的代码也有另一种写法。 运用这种方法我们也可以实现想要的尾插操作但是代码到这里就结束了吗并没有这里的代码依旧存在着问题。那么是哪里出问题了 这里我们不断的进行尾删操作一开始并没有问题但是当链表中只存在一个结点的时候问题就出现了。我们上面两种写法都会出错。
首先是我们的第二种方法的问题所在 这个代码在判断阶段出了问题因为链表只剩下一个结点所以我们的tail-next就已经是空了而后再在原来的基础上进行next是会出错的。
那第一种方法的错误又在哪里呢 第一种方法的错误就出现在最后prev-next这里在上面我们可以得知prev一开始被我们置为空当只剩下一个结点的时候循环不会进行我们的prev依旧为空最后还要将prev-next置为空这就是第一种方法的问题所在。
当然这只是链表只剩下一个结点的情况如果链表没有结点的话这两种方法出现的问题会更加的多比如第一种方法中循环不会执行。
那么为了避免这种情况的发生我们该怎么样对代码进行修改 这里就需要对其判断如果第一个结点的next为空的话我们就直接将其释放后置空。
还有一种情况那就是一开始链表就为空这种情况又要怎么去处理它呢 在开始的时候就要对代码进行判断如果链表一开始为空的话这里就直接return结束又或者是将其进行断言。
8.头删
接下来就是我们的头删头插相较于尾插就比较简单了为什么
按照惯例我们还是先将头删的代码写出来。 首先检查链表是不是空链表无论是头删还是尾删链表内有数据才可以让我们删除因此这一步是必不可少的。
但是和尾删的代码不一样头删的操作并不用对只有一个结点的情况进行另外的代码书写。
那么指针头插操作是怎么样运行的 这就是头删的原理将我们链表中的头结点删除而后链表的指针指向原理第二个结点的地址这样就是我们的头删操作。
接下来就是书写我们的代码了。 而后我们将代码运行起来看看结果是什么 从这张图片来看我们的头删的操作可以运行起来并且没有报错。
9.代码 SList.h文件 #include SLish.hvoid SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL)//while(cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;return newnode;
}void SLTPushBack(SLTNode** pphead,SLTDataType x)
{/*SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);return;}newnode-data x;newnode-next NULL;*/SLTNode* newnode BuySLTNode(x);if (*pphead NULL){*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySLTNode(x);newnode-next *pphead;*pphead newnode;
}void SLTPopBack(SLTNode** pphead)
{/*assert(*pphead);*/if (*pphead NULL){return;}if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* prev NULL;SLTNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}//while(tail-next-next!NULL)//{// tail tail-next;//}//free(tail-next);//tail-next NULL;free(tail);tail NULL;prev-next NULL;}
}void SLTPopFront(SLTNode** pphead)
{/*assert(*pphead);*/if (*pphead NULL){return;}SLTNode* first *pphead;*pphead first-next;free(first);first NULL;
}test.c文件 #include SLish.h//void TestSList1()
//{
// SLTNode* plist NULL;
// SLTPushBack(plist, 1);
// SLTPushBack(plist, 2);
// SLTPushBack(plist, 3);
// SLTPushBack(plist, 4);
//
// SLTPrint(plist);
//}//void TestSList2()
//{
// SLTNode* plist NULL;
// SLTPushFront(plist, 1);
// SLTPushFront(plist, 2);
// SLTPushFront(plist, 3);
// SLTPushFront(plist, 4);
// SLTPrint(plist);
//
// SLTPopBack(plist);
// SLTPrint(plist);
//
// SLTPopBack(plist);
// SLTPrint(plist);
//
// SLTPopBack(plist);
// SLTPrint(plist);
//}void TestSList3()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);
}int main()
{/*TestSList1();*//*TestSList2();*/TestSList3();return 0;
} SList.h文件 #pragma once#include stdio.h
#include stdlib.h
#include assert.htypedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead,SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead); 结尾 到这里我们链表的头插头删尾插尾删等程序代码就已经写完了但是和顺序表一样链表也有在中间插入或者删除的操作这些操作我们放在下一篇博客中去讲解这篇博客相较与以往的博客内容有质的提升所以我们要先搞懂头删这些程序的原理不要操之过急。因为内容质量的提升我在有些地方自己理解了但是没有办法完全表达出来这一个点还请各位读者见谅。最后希望这篇博客能帮到学习链表的同学。
