企业网站设计布局,个人小程序开发流程,广州市天河区,网站建设报价模版前言#xff1a;前面我们学习了动态顺序表并且模拟了它的实现#xff0c;今天我们来进一步学习#xff0c;来学习单链表#xff01;一起加油各位#xff0c;后面的路只会越来越难走需要我们一步一个脚印#xff01; #x1f496; 博主CSDN主页:卫卫卫的个人主页 #x…前言前面我们学习了动态顺序表并且模拟了它的实现今天我们来进一步学习来学习单链表一起加油各位后面的路只会越来越难走需要我们一步一个脚印 博主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;
} 结语今天的内容就到这里吧谢谢各位的观看如果有讲的不好的地方也请各位多多指出作者每一条评论都会读的谢谢各位。 祝各位接下来好运连连
