目录
一些无关紧要的废话:
翻出笔记,回忆当初学链表的日子,啊!真是痛苦的回忆。自以为C语言学得很扎实,结构体,指针。当时我就决心把指针和结构体的博客写好了,翻书翻网课,复习一下笔记。现在,终于还是更新链表,直面当初的恐惧。
学到后面,发现链表在整个数据结构只是个大头兵罢了。就像一开始学顺序表,觉得还行,发现链表已经比较难啃了,后面,呃,自己体会吧。
链表篇:单链表,双向链表,静态链表,循环链表。
由于分时间段写的,后面跟不上最初写的思路,见谅。
单链表,这里不带头节点,只有头指针。
单链表篇-------我认为单链表帮我深入理解指针和结构体;
指针部分:
1.传值和传址调用
2.涉及到二级指针
结构体部分:
结构体自引用;结构体指针;
我们要"批判"顺序表,不否认顺序表有它自己的优势,但我们要把使用过程的毛病指出来。
1.顺序表需要动态扩容
一般情况都会造成空间浪费,因为刚好装满太不现实。动态顺序表和静态顺序表或多或少都会浪费。
2.按需申请释放空间
realloc函数在增容中如果在原有空间后没有足够大,就会另辟蹊径,释放旧空间,重新申请新空间拷贝数据,造成运行效率低下。
3.实现指定位置的插入和删除整体挪动数据
时间复杂度O(n),效率低。
以上"批判"都是鉴于顺序表连续存储的”缺点”。
那我们思考一下如何解决这些问题。
Q1:既然有空间浪费问题,那我们难道不能存一个数据开一个数据的空间吗?
Q2:既然realloc有释放就空间,重新开辟新空间拷贝数据的效率问题,那开一个数据的空间,不用就直接释放,不就可以解决了吗?
Q3:因为连续存储导致实现指定位置的插入和删除要整体挪动数据,那让每个数据独立的空间,要插入删除,只需要改变它们之间的先后顺序不就可以了吗?
OK,大致想法有了,下面是整形数据 0,1,2,3,4.
每个数据都有独立的空间,有新数据了也单独给它开一块刚好大的空间。那么问题来了,我知道0后面的数是1,但我怎么用程序语言描述呢?0和1不是在内存连续存储的,程序可不知到0后面是1。有了!指针就是地址,通过指针变量存储下一个数据的地址不就行了吗。
哦哦哦,原来每块小的空间要存储这一块的数据和指向下一块的指针。有了下一块的指针就可以访问下一块空间的数据了。
注意:这里的箭头不是真实存在的,只是逻辑上想象出来的。
那么每一小块是什么数据类型呢?
显然就是结构体类型了呗。
- struct S {
- int data;//存放整型数据
- struct S* next;//下一块和这一块都是相同的结构体类型,这里是下一块的指针。
- };
这不就是结构体的自引用吗,不了解可以看看我写的结构体的博客。
这里只能存储int类型的数据吗?
当然不是了。因此我们得到了一般的情况。
- typedef int SLTDataType;//可以是内置类型,数组,结构体类型,这里可以替换。
-
- typedef struct STLNode {
- SLTDataType data;
- struct STLNode* next;
- }STLNode;
最后,每次叫一块一块的空间感觉没有逼格,单独起个名字吧,就叫做结点(节点)。
原来如此,每个节点一部分存储数据(数据域)。另一部存储下一个节点的指针(指针域)。这里的最后一个结点的指向就是空指针了(NULL),最后一个结点叫做尾结点。
注意:结点和节点是同一个东西。就和同一事物的不同称呼一样。
🆗下面就引出了链表的概念。
由一的引入,可以说链表是由一个个结点组成的有序集合。
首先,链表是一种线性表。线性表有逻辑结构和物理结构的特点,那么链表呢?
链表:
逻辑结构:连续(线性),满足线性表的定义。
物理结构:不连续(非线性)。
那么我们就可以借此画图分析了,即逻辑图和物理图。
以下就是逻辑图:
由于链表逻辑上是线性的,我们就可以如此看链表。
由于每个结点都存储了下一个结点的地址,哪怕尾结点也存储了NULL。
但是第一个结点的位置(这里不称为头节点,这里不提头节点相关的内容)不知道,需要一个结构体指针变量来记住(存储)这个值,这个结构体指针就称为头指针。
现在你明白了一个链表(单链表)的结构:
头指针,各个结点,尾结点指向NULL。
链表(单链表)的结构:
头指针,各个结点(各节点),尾结点指向NULL。
按照这种结构在main函数实现一个简单的链表
- #include
- #include
//malloc函数 - typedef int SLTDataType;
-
- typedef struct STLNode {
- SLTDataType data;
- struct STLNode* next;
- }STLNode;
-
- int main()
- {
- //头指针
- STLNode* phead = NULL;
-
- //第一个结点
- STLNode* s1 = (STLNode*)malloc(sizeof(STLNode));
- //头指针指向第一个节点
- phead = s1;
-
- //第二个结点
- STLNode* s2 = (STLNode*)malloc(sizeof(STLNode));
-
- //第三个结点
- STLNode* s3 = (STLNode*)malloc(sizeof(STLNode));
-
-
- //第四个结点(尾结点)
- STLNode* s4 = (STLNode*)malloc(sizeof(STLNode));
-
- //连接前后两个结点,并给相应结点数据域赋值。
- s1->data = 1;
- s1->next = s2;
-
- s2->data = 2;
- s2->next = s3;
-
- s3->data = 3;
- s3->next = s4;
-
- s4->data = 4;
- s4->next = NULL;
-
- //打印部分先简单看看,稍后具体实现相关函数会解释
- STLNode* cur = phead;
- while (cur)
- {
- printf("%d->",cur->data);
- cur = cur->next;
- }
- printf("NULL\n");
- return 0;
- }
运行结果如下:
如果一个链表没有任何结点,那么称其为空链表。
那么对于空链表,可以定义为节点指针指向空,或者说头指针指向空;
即 STLNode* plist = NULL;
思考一下,打印函数实现的具体步骤是什么?
1.需要一个结点结构体指针变量,遍历整个链表,要用循环逻辑
2.每次到一个结点,打印数据部分,并挪动指针到下一个节点。
- void STLPrint(STLNode* phead)
- {
- STLNode* cur = phead;//常见写法,引入循环变量来操作。
- //先打印前一个结点的数据域,在通过结点指针变量的赋值,来访问下一个结点。
- while (cur)
- {
- printf("%d->", cur->data);
- cur = cur->next;
- }
- //尾结点的指针部分指向空,打印好观察。
- printf("NULL\n");
- }
看看总的效果,代码如下:
- #include
- #include
- #include
-
-
- typedef int SLTDataType;
-
- typedef struct STLNode {
- SLTDataType data;
- struct STLNode* next;
- }STLNode;
-
-
- void STLPrint(STLNode* phead);
- int main()
- {
- //头指针
- STLNode* phead = (STLNode*)malloc(sizeof(STLNode));
-
- //第一个结点
- STLNode* s1 = phead;
-
- //第二个结点
- STLNode* s2 = (STLNode*)malloc(sizeof(STLNode));
-
- //第三个结点
- STLNode* s3 = (STLNode*)malloc(sizeof(STLNode));
-
-
- //第四个结点(尾结点)
- STLNode* s4 = (STLNode*)malloc(sizeof(STLNode));
-
- //连接前后两个结点,并给相应结点数据域赋值。
- s1->data = 1;
- s1->next = s2;
-
- s2->data = 2;
- s2->next = s3;
-
- s3->data = 3;
- s3->next = s4;
-
- s4->data = 4;
- s4->next = NULL;
-
- STLPrint(phead);
-
- return 0;
- }
-
-
- void STLPrint(STLNode* phead)
- {
- STLNode* cur = phead;
- while (cur)
- {
- printf("%d->", cur->data);
- cur = cur->next;
- }
- printf("NULL\n");
- }
附带运行结果。
比如创建一个数据为0,指针部分为空的节点,如何想呢?
这种写法是否准确?
- void BuyNode(SLTDataType x)
- {
- STLNode newnode;
- newnode.data = x;
- newnode.next = NULL;
- }
很明显这是错误的,因为函数内部声明的变量为局部变量,栈区上申请空间,生命周期是变量声明到出函数。
因此,显然不能在栈区上申请。我们用动态内存开辟函数在堆区申请空间。
动态开辟要用节点(结构体)指针。于是就有了第二种想法:
- void BuyNode(SLTDataType x)
- {
- STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
- if (NULL == newnode)//判断动态空间是否开辟成功。
- {
- perror("malloc fail");
- exit(1);//异常退出
- }
- newnode->data = x;//修改数据域
- newnode->next = NULL;//指针域为空。
- }
这种情况节点申请成功了,节点会一直存在直至程序结束(如果不主动释放)。但又出现一个问题:这个函数没有其连接功能,它只是单独创建一个节点,我们压根不知道它怎么联系整个链表。创建成功后,出函数我们能找到这个节点吗?答案是不能。这个节点指针是局部变量,存储了指向节点的地址。出函数后也销毁了,再也找不到这个节点了。
所以第二种方法已经相对成功了,只需要进行如下修改:
- STLNode* BuyNode(SLTDataType x)
- {
- STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
- if (NULL == newnode)//判断动态空间是否开辟成功。
- {
- perror("malloc fail");
- exit(1);//异常退出
- }
- newnode->data = x;//修改数据域
- newnode->next = NULL;//指针域为空。
- return newnode;
- }
🆗,总结以下这个函数的功能,这个函数需要接受相应的数据,来作为数据域的部分。在堆区为节点开辟空间,并返回指向该节点的地址。
从功能上它只是单独创建了一个节点,并没有其连接作用,但其返回了地址,使得我们在后面进行尾插和头插操作时,能找到这个节点和起连接作用。
如何实现头插的功能?
这个头插函数传什么参数,返回类型是什么,思考一下。
首先,我们考虑把头指针传过去,其次由于要创建节点(调用BuyNode这个函数),也要传入相应的数据部分;最后考虑实现节点之间的连接。
雏形有了
- void STLPushFront(STLNode* phead, SLTDataType x)
- {
- STLNode* newnode = BuyNode(x);//创建一个节点
- //如何连接呢?
- }
如何连接呢,画图分析一下
先让这个新节点的指针域指向原来的第一个节点,然后让头指针指向新节点。
- void STLPushFront(STLNode* phead, SLTDataType x)
- {
- STLNode* newnode = BuyNode(x);//创建一个节点
- //如何连接呢?
- newnode->next = phead;
- phead = newnode;
- }
这个实际上也有问题。
调试分析一下下面代码,并观察运行结果。
- #include
- #include
- #include
-
-
- typedef int SLTDataType;
-
- typedef struct STLNode {
- SLTDataType data;
- struct STLNode* next;
- }STLNode;
-
- void STLPushFront(STLNode* phead, SLTDataType x);
- STLNode* BuyNode(SLTDataType x);
- void STLPrint(STLNode* phead);
-
- int main()
- {
- //头指针
- STLNode* phead = (STLNode*)malloc(sizeof(STLNode));
-
- //第一个结点
- STLNode* s1 = phead;
-
- //第二个结点
- STLNode* s2 = (STLNode*)malloc(sizeof(STLNode));
-
- //第三个结点
- STLNode* s3 = (STLNode*)malloc(sizeof(STLNode));
-
-
- //第四个结点(尾结点)
- STLNode* s4 = (STLNode*)malloc(sizeof(STLNode));
-
- //连接前后两个结点,并给相应结点数据域赋值。
- s1->data = 1;
- s1->next = s2;
-
- s2->data = 2;
- s2->next = s3;
-
- s3->data = 3;
- s3->next = s4;
-
- s4->data = 4;
- s4->next = NULL;
-
- //先打印,头插后再打印一遍。
- STLPrint(phead);
- STLPushFront(phead, 0);
- STLPrint(phead);
-
- return 0;
- }
-
-
- STLNode* BuyNode(SLTDataType x)
- {
- STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
- if (newnode==NULL)//判断动态空间是否开辟成功。
- {
- perror("malloc fail");
- exit(1);//异常退出
- }
- newnode->data = x;//修改数据域
- newnode->next = NULL;//指针域为空。
- return newnode;
- }
-
- void STLPushFront(STLNode* phead, SLTDataType x)
- {
- STLNode* newnode = BuyNode(x);//创建一个节点
- //如何连接呢?
- newnode->next = phead;
- phead = newnode;
- }
-
- void STLPrint(STLNode* phead)
- {
- assert(phead);
- STLNode* cur = phead;
- while (cur)
- {
- printf("%d->", cur->data);
- cur = cur->next;
- }
- printf("NULL\n");
- }
运行结果说明了,头指针始终指向数据为1的节点,并没有如期望的那样修改。
为什么呢?
进了头插函数,phead由调试可以知道,“头指针”修改了,但出函数头指针怎么指回去了呢。
哦哦哦,学了函数你知道形参是实参的一份临时拷贝,是把值得数据复制了一份,这里本质是两个phead,对头插函数内部修改指向,并不能影响原来得phead的指向。本质这里是传值调用。
那么如何解决呢?
过去,学习的误区,认为传址调用就是传递地址,不理解本质上操作了什么。
- #include
- void swap1(int* x, int* y)
- {
- int tmp = *x;
- *x = *y;
- *y = tmp;
- }
-
-
- void swap2(int** x, int** y)
- {
- int* tmp = *x;
- *x = *y;
- *y = tmp;
- }
-
-
- int main()
- {
- int a = 10;
- int b = 20;
- printf("交换前:a = %d , b = %d\n", a, b);
- swap1(&a, &b);//传a和b的地址。
- printf("交换后:a = %d , b = %d\n", a, b);
-
- int* p1 = &a;
- int* p2 = &b;
-
- printf("交换前:p1 = %p ,p2 = %p\n", p1, p2);
- swap2(&p1, &p2);//传p1和p2的地址。
- printf("交换后:p1 = %p , p2 = %p\n", p1, p2);
-
- }
传址调用本质是通过向函数传递指针,在通过指针解引用的方式来间接操作内部的值。
这里要修改p1和p2,但是它们的类型是int* ,意味着要在swap2中交换它们的值,就要传递它们的地址。它们本身就是指针,这里要传指针的指针,也就是二级指针,通过二级指针解引用在swap2函数内交换。
要修改节点就用结构体(节点)指针,要修改结构体指针(头指针)就要用二级指针。
上面修改头指针失败了,本质就是进行了值拷贝,而没有传址调用。
- void STLPushFront(STLNode** pphead, SLTDataType x)
- {
- assert(pphead);//由于是头指针的指针,需要判断是否为空
- STLNode* newnode = BuyNode(x);//创建一个节点
-
- newnode->next = *pphead;
- *pphead = newnode;
- }
将这个函数替换原来的STLPushFront函数,再传头指针的地址,打印结果如下:
那么最后结束了吗?
并没有,我们还没考虑特殊情况。如果链表本身就是空表呢?检验一下头插代码是否对空表也适用。
这里的*pphead就为NULL了;
带进去分析一下,也是成立的。这里不再赘述,不理解,请自己画图分析。头插函数的最终代码就是这个了。
- void STLPushFront(STLNode** pphead, SLTDataType x)
- {
- assert(pphead);//由于是头指针的指针,需要判断是否为空
- STLNode* newnode = BuyNode(x);//创建一个节点
-
- newnode->next = *pphead;
- *pphead = newnode;
- }
这里要创建数据为5的节点并连接上尾部,思考一下如何实现?
先创建一个节点BuyNode(5);
这里感觉用不着修改头指针, 可以传头指针的值吧。
由于我们传递的是头指针,但要实现尾部连接,我们下一步就是找尾部。(用循环实现)
最后,考虑怎么连接的问题。
找到尾结点,这里循环终止条件是pcur->next==NULL;此时说明pcur到最后了。
- void STLPushBack(STLNode* phead,SLTDataType x)
- {
- STLNode* newnode = BuyNode(x);
- STLNode* pcur = phead;
- while (pcur->next != NULL)
- {
- pcur = pcur->next;
- }
- //如何连接呢?
- }
直接让尾结点的下一个指针部分指向新节点就行了。请自行测试代码是否符合逻辑。
- void STLPushBack(STLNode* phead,SLTDataType x)
- {
- STLNode* newnode = BuyNode(x);
- STLNode* pcur = phead;
- while (pcur->next != NULL)
- {
- pcur = pcur->next;
- }
- pcur->next = newnode;
- }
最后考虑空链表的情况。
显然这种情况非空链表的逻辑就不符合了,用分支结构吧。
这里只要修改一下头指针的指向就行了,让头指针指向新节点就可以了。
嗯?要修改头指针,看来尾插还是要传址调用啊。
于是就得到了尾插的最终代码。
- void STLPushBack(STLNode** pphead,SLTDataType x)
- {
- assert(pphead);//判断二级指针是否为空,即头指针的有效性
- STLNode* newnode = BuyNode(x);//创建节点
- STLNode* pcur = *pphead;//引入循环变量,找尾节点
-
- if (NULL==*pphead)//判断空表
- {
- *pphead = newnode;
- return;
- }
- else//非空表执行尾插逻辑
- {
- while (pcur->next != NULL)
- {
- pcur = pcur->next;
- }
- pcur->next = newnode;
- }
- }
删除数据为1的节点。
思路很简单,由于要修改头指针的指向,就要在头删函数内部采用二级指针。
引入临时变量存储头指针的值;
改变头指针的指向;
释放原先的第一个节点;
- void STLPopFront(STLNode** pphead)
- {
- assert(pphead);//判断二级指针是否为空,即头指针的有效性
- assert(*pphead);//判断是否为空表,空表不能执行删除操作。
-
-
- STLNode* tmp = *pphead;//临时变量存储头指针的值
- *pphead = (*pphead)->next;//头指针改变执行,指向第二个节点
- free(tmp);//释放原来头指针指向的节点
-
- }
请自行测试代码!
这里还是用二级指针作参数,具体原因不在废话了。
还是这幅图,不过我们这次删除数据为4的节点。
思考一下
首先,对于空表不能执行删除操作。
其次,对于上述情形,我们还是要找尾结点,然后释放尾结点。但是有个问题倒数第二个节点的指针域应该指向空,如果不置空,就要非法访问了(因为它还记得尾结点的地址,但尾结点已经释放了不归我们管了)。
很简单,用双指针不就行了吗。
- void STLPopBack(STLNode** pphead)
- {
- assert(pphead && *pphead);//二级指针不为空且不为空表
-
- STLNode* prev = *pphead;//找倒数第二个节点
- STLNode* ptail = *pphead;//找尾节点
- while (ptail->next)
- {
- prev = ptail;
- ptail = ptail->next;
- }
- free(ptail);//释放尾结点
- prev->next = NULL;//倒数第二个节点置空
- }
那么代码实现完了吗?看一下结果。
最后不应该打印NULL;看来双指针实现的代码还是有问题,前面打印都正常,唯独只剩下一个节点的时候出问题了。
这里其实就很简单了,直接释放头指针指向的节点,再让头指针指向空就OK了,这里的逻辑和双指针是两种情况,用if else语句实现。
最终代码实现:
- void STLPushBack(STLNode** pphead,SLTDataType x)
- {
- assert(pphead);//判断二级指针是否为空,即头指针的有效性
- STLNode* newnode = BuyNode(x);//创建节点
- STLNode* pcur = *pphead;//引入循环变量,找尾节点
-
- if (NULL==*pphead)//判断空表
- {
- *pphead = newnode;
- return;
- }
- else//非空表执行尾插逻辑
- {
- while (pcur->next != NULL)
- {
- pcur = pcur->next;
- }
- pcur->next = newnode;
- }
- }
请自行阅读下面代码,从上而下看过来,已经很容易了。
这里只是遍历查找原链表不用修改头指针,传值调用即可。看完自行实现该代码,会使用这个函数。
- STLNode* STLFind(STLNode* phead, SLTDataType x)
- {
- assert(phead);//空表不能查找
- STLNode* pcur = phead;
- while (pcur)//遍历链表查找
- {
- if (x == pcur->data)
- {
- return pcur;//找到返回指向该节点的指针
- }
- else
- pcur = pcur->next;
- }
- return NULL;//找不到返回空指针。
- }
测试结果
给定指定节点的地址pos,要求在其之前插入数据为x节点
比如在数据为3的节点之前插入数据为5的节点。
这里我们操作的是2,3和新节点newnode,3节点的地址已经知道了,新节点也知道。二节点的不知道,需要pcur来找到二节点的位置。
- void STLInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
- {
- assert(pphead && *pphead);//二级指针不为空且不能为空表
- assert(pos);//节点地址的有效性
-
- STLNode* newnode = BuyNode(x);//创建新节点
- STLNode* pcur = *pphead;//临时变量找pos的前一个结点。
- while (pcur->next != pos)
- {
- if (pcur == NULL)//给定节点不存在
- {
- perror("Not Found!");
- return;
- }
- pcur = pcur->next;
- }
- //自行画逻辑图分析,很简单
- newnode->next = pos;
- pcur->next = newnode;
-
-
- }
按照惯例,考虑特殊情况,当pos是第一个节点时,意味着这是头插。那么上面代码适用头插的情况吗?
不适用,从代码上由于循环条件是pcur->next != pos,但此时pcur==pos;这个会一直循环下去直到进入if分支结束函数。
最终代码:
- void STLInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
- {
- assert(pphead && *pphead);//二级指针不为空且不能为空表
- assert(pos);//节点地址的有效性
-
- STLNode* newnode = BuyNode(x);//创建新节点
- STLNode* pcur = *pphead;//临时变量找pos的前一个结点。
- if (pcur == pos)//分类讨论
- {
- STLPushFront(pphead,x);//直接调用先前的头插函数,暴力解决
- }
- else
- {
- while (pcur->next != pos)
- {
- if (pcur == NULL)//给定节点不存在
- {
- perror("Not Found!");
- return;
- }
- pcur = pcur->next;
- }
- //自行画逻辑图分析,很简单
- newnode->next = pos;
- pcur->next = newnode;
- }
- }
测试一下
还是这幅图,这里在节点三的位置插入数据为5的节点
这里不要什么pcur了,因为在指定节点后面插入,位置已经知道了。
- void STLInsertAfter(STLNode** pphead, STLNode* pos, SLTDataType x)
- {
- assert(pphead && *pphead);//二级指针不为空且不能为空表
- assert(pos);//节点地址的有效性
-
- STLNode* newnode = BuyNode(x);//创建新节点
-
- //下面两句代码不能交换,要考虑顺序问题。
- newnode->next = pos->next;
- pos->next = newnode;
- }
如果是尾插的情况呢?
即pos->next=NULL;代入发现也成立,所以这个就是最终代码了。
不再解释,自行分析。
- void STLErase(STLNode** pphead, STLNode* pos)
- {
- assert(pphead && *pphead);
- assert(pos);
- STLNode* prev = *pphead;
- while (prev->next != pos)
- {
- if (NULL == prev)
- {
- perror("Not Found!");
- return;
- }
- prev = prev->next;
- }
- prev->next = pos->next;
- free(pos);
- }
- void STLEraseAfter(STLNode* pos)
- {
- assert(pos && pos->next);//指定节点存在且有下一个节点
- STLNode* del = pos->next;
- pos->next = del->next;
- free(del);
- del = NULL;
- }
- void STLDestroy(STLNode** pphead)
- {
- assert(pphead);//二级指针不为空
- if (NULL == *pphead)
- {
- return;//已经是空表了,不需要销毁。
- }
- STLNode* prev = *pphead;
- STLNode* ptail = *pphead;
- while (ptail->next)
- {
- prev = ptail;//prev跟上ptail
- ptail = ptail->next;//ptail往后挪一位
- free(prev);//释放当前节点。
- }
- prev = ptail = NULL;
- *pphead = NULL;//头指针指向空,链表为空表了。
- }
- #define _CRT_SECURE_NO_WARNINGS 1
-
- #include
- #include
- #include
- #include
-
-
- typedef int SLTDataType;
-
- typedef struct STLNode {
- SLTDataType data;
- struct STLNode* next;
- }STLNode;
-
- //函数声明
- void STLEraseAfter(STLNode* pos);
- void STLErase(STLNode** pphead,STLNode* pos);
- void STLDestroy(STLNode** pphead);
- void STLInsertAfter(STLNode** pphead, STLNode* pos, SLTDataType x);
- void STLInsert(STLNode** pphead, STLNode* pos, SLTDataType x);
- void STLPushFront(STLNode** phead, SLTDataType x);
- void STLPushBack(STLNode** phead, SLTDataType x);
- void STLPopFront(STLNode** pphead);
- void STLPopBack(STLNode** pphead);
- STLNode* BuyNode(SLTDataType x);
- STLNode* STLFind(STLNode* phead, SLTDataType x);
- void STLPrint(STLNode* phead);
-
- int main()
- {
- //头指针
- STLNode* phead = (STLNode*)malloc(sizeof(STLNode));
-
- //第一个结点
- STLNode* s1 = phead;
-
- //第二个结点
- STLNode* s2 = (STLNode*)malloc(sizeof(STLNode));
-
- //第三个结点
- STLNode* s3 = (STLNode*)malloc(sizeof(STLNode));
-
-
- //第四个结点(尾结点)
- STLNode* s4 = (STLNode*)malloc(sizeof(STLNode));
-
- //连接前后两个结点,并给相应结点数据域赋值。
- s1->data = 1;
- s1->next = s2;
-
- s2->data = 2;
- s2->next = s3;
-
- s3->data = 3;
- s3->next = s4;
-
- s4->data = 4;
- s4->next = NULL;
-
- STLPushBack(&phead, 5);
- STLPrint(phead);
- STLPushFront(&phead, 0);
- STLPrint(phead);
- STLNode* ret = STLFind(phead, 3);
- STLInsert(&phead, ret, 10086);
- STLPrint(phead);
- STLInsertAfter(&phead, ret, 114514);
- STLPrint(phead);
- STLEraseAfter(ret);
- STLPrint(phead);
- STLErase(&phead, ret);
- STLPrint(phead);
- printf("销毁链表\n");
- STLDestroy(&phead);
- STLPrint(phead);
-
- return 0;
- }
-
-
- STLNode* BuyNode(SLTDataType x)
- {
- STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
- if (newnode==NULL)//判断动态空间是否开辟成功。
- {
- perror("malloc fail");
- exit(1);//异常退出
- }
- newnode->data = x;//修改数据域
- newnode->next = NULL;//指针域为空。
- return newnode;
- }
-
- void STLDestroy(STLNode** pphead)
- {
- assert(pphead);//二级指针不为空
- if (NULL == *pphead)
- {
- return;//已经是空表了,不需要销毁。
- }
- STLNode* prev = *pphead;
- STLNode* ptail = *pphead;
- while (ptail->next)
- {
- prev = ptail;//prev跟上ptail
- ptail = ptail->next;//ptail往后挪一位
- free(prev);//释放当前节点。
- }
- prev = ptail = NULL;
- *pphead = NULL;//头指针指向空,链表为空表了。
- }
- void STLEraseAfter(STLNode* pos)
- {
- assert(pos && pos->next);//指定节点存在且有下一个节点
- STLNode* del = pos->next;
- pos->next = del->next;
- free(del);
- del = NULL;
- }
-
- void STLErase(STLNode** pphead, STLNode* pos)
- {
- assert(pphead && *pphead);
- assert(pos);
- STLNode* prev = *pphead;
- while (prev->next != pos)
- {
- if (NULL == prev)
- {
- perror("Not Found!");
- return;
- }
- prev = prev->next;
- }
- prev->next = pos->next;
- free(pos);
- }
- void STLInsertAfter(STLNode** pphead, STLNode* pos, SLTDataType x)
- {
- assert(pphead && *pphead);//二级指针不为空且不能为空表
- assert(pos);//节点地址的有效性
-
- STLNode* newnode = BuyNode(x);//创建新节点
-
- //下面两句代码不能交换,要考虑顺序问题。
- newnode->next = pos->next;
- pos->next = newnode;
- }
- void STLInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
- {
- assert(pphead && *pphead);//二级指针不为空且不能为空表
- assert(pos);//节点地址的有效性
-
- STLNode* newnode = BuyNode(x);//创建新节点
- STLNode* pcur = *pphead;//临时变量找pos的前一个结点。
- if (pcur == pos)//分类讨论
- {
- STLPushFront(pphead,x);//直接调用先前的头插函数,暴力解决
- }
- else
- {
- while (pcur->next != pos)
- {
- if (pcur == NULL)//给定节点不存在
- {
- perror("Not Found!");
- return;
- }
- pcur = pcur->next;
- }
- //自行画逻辑图分析,很简单
- newnode->next = pos;
- pcur->next = newnode;
- }
- }
-
- void STLPopBack(STLNode** pphead)
- {
- assert(pphead && *pphead);//二级指针不为空且不为空表
-
- if ((*pphead)->next == NULL)
- {
- free(*pphead);
- *pphead = NULL;
- }
- else
- {
- STLNode* prev = *pphead;//找倒数第二个节点
- STLNode* ptail = *pphead;//找尾节点
- while (ptail->next)
- {
- prev = ptail;
- ptail = ptail->next;
- }
- free(ptail);//释放尾结点
- prev->next = NULL;//倒数第二个节点置空
- }
- }
- void STLPopFront(STLNode** pphead)
- {
- assert(pphead);//判断二级指针是否为空,即头指针的有效性
- assert(*pphead);//判断是否为空表,空表不能执行删除操作。
-
-
- STLNode* tmp = *pphead;//临时变量存储头指针的值
- *pphead = (*pphead)->next;//头指针改变执行,指向第二个节点
- free(tmp);//释放原来头指针指向的节点
-
- }
- STLNode* STLFind(STLNode* phead, SLTDataType x)
- {
- assert(phead);//空表不能查找
- STLNode* pcur = phead;
- while (pcur)//遍历链表查找
- {
- if (x == pcur->data)
- {
- return pcur;//找到返回指向该节点的指针
- }
- else
- pcur = pcur->next;
- }
- return NULL;//找不到返回空指针。
- }
- void STLPushBack(STLNode** pphead,SLTDataType x)
- {
- assert(pphead);//判断二级指针是否为空,即头指针的有效性
- STLNode* newnode = BuyNode(x);//创建节点
- STLNode* pcur = *pphead;//引入循环变量,找尾节点
-
- if (NULL==*pphead)//判断空表
- {
- *pphead = newnode;
- return;
- }
- else//非空表执行尾插逻辑
- {
- while (pcur->next != NULL)
- {
- pcur = pcur->next;
- }
- pcur->next = newnode;
- }
- }
-
- void STLPushFront(STLNode** pphead, SLTDataType x)
- {
- assert(pphead);//由于是头指针的指针,需要判断是否为空
- STLNode* newnode = BuyNode(x);//创建一个节点
-
- newnode->next = *pphead;
- *pphead = newnode;
- }
-
- void STLPrint(STLNode* phead)
- {
- STLNode* cur = phead;
- while (cur)
- {
- printf("%d->", cur->data);
- cur = cur->next;
- }
- printf("NULL\n");
- }
数据结构篇其二---链表---单链表结束!
链表系列:单链表,双向链表,循环链表。
静态链表如果有必要也会更一篇,因为C语言有指针可以实现链表,静态链表目前我看来意义不大。
总算写完了8个小时,手废了,可利用的时间太少了。我觉得自己独立写完此篇是很爽的,但我现在太累了。后面还有更难的数据结构要更(链表篇还没更完),总之加油吧。
今天,哦不昨天忘记提交代码了,没有小绿点了。痛!