怎样快速仿做网站,动漫与游戏制作专业有前途吗,建设局网站查询个人信息,微盟企业微信助手关于链表你应该先了解这些
下图描述了物理模型和逻辑模型#xff0c;大多数常见的其实是逻辑模型#xff0c;但这对初学者或者掌握不扎实的同学不太友好#xff0c;所以这里我重点讲解物理模型#xff0c;当了解了这些细节#xff0c;以后做题或是什么就直接画逻辑模型就…关于链表你应该先了解这些
下图描述了物理模型和逻辑模型大多数常见的其实是逻辑模型但这对初学者或者掌握不扎实的同学不太友好所以这里我重点讲解物理模型当了解了这些细节以后做题或是什么就直接画逻辑模型就好了 物理模型 在这里一个大方框表示着一个结点这个结点里存储了两种数据
一是你本身要存储的数据二是为了让这些结点具有连接作用而需要存放相应结点的地址这样当你访问了当前的结点内容想要访问下一个结点的内容这时就需要有下一个节点的地址这就是为什么要存地址的原因。
链表的类型
单链表
上面的就是单链表
双链表 与单链表的不同就是一个结点里存有两个地址可以实现双向访问弥补了单链表只能单向访问的缺点
循环链表 单链表的最后一个结点存的是NULL而循环链表的最后一个结点存放的是第一个结点的地址事实上你看这张图确实也分辨不出哪个是第一个结点所以想象成单链表最后一个结点放的头结点的地址就行
链表的存储方式
数组是一块连续的内存而链表不同每个结点都有自己的地址并没有联系这些地址是取决于操作系统的内存管理在没学习操作系统之前可以当做这些地址是随机分配的
链表的定义
这一节我所讲的知识都是基于单链表
typedef int SLTDataType;//结点中存储数据的类型
typedef struct SListNode
{SLTDataType data;//结点中要存储的数据struct SListNode* next;//结点中指向下一个结点的指针
}SLTNode;先看这张图 与开头的那张区别就在于头指针phead这是一个指针变量用来存放第一个结点的地址利用该指针就可以依次访问或操作节点中的数据 接下来初始化一个指向结点的头指针这里是头指针不是头结点
SLTNode* phead NULL;链表的操作
先了解是如何访问链表的 完整流程
为什么要用二级指针 经过了头插操作我们将new_node成功连入链表的头部pphead存的也是new_node的地址但是我们的实参phead它里面的内容竟还是之前第一个结点的内容而往后我们还是要用phead来访问操作这个链表但新插入的节点却永远访问不到那你说能不能用pphead访问不就行了记住pphead是局部变量执行完头插这个函数pphead就不存在了我们想操作这个链表一直都是利用phead当做实参传递的。想要改变实参的内容只需传址调用即可因此我们将指针变量phead的地址当做实参传递过去那么相应的形参就需要一个二级指针接收因为phead是指针我们传递的是指针的地址所以需要二级指针接收。如此通过对二级指针pphead解引用就可以直接对phead的内容进行修改到此phead就可以存new_node地址了 创建一个新节点
SLTNode* SLTCreatNode(SLTDataType x)
{
//里用malloc函数向栈区开辟一个大小为sizeof(SLTNode)个字节的空间将这个空间的首地址存放于new_p这个指针变量中SLTNode* new_p (SLTNode*)malloc(sizeof(SLTNode));malloc函数开辟空间失败会返回NULL这时就不要再进行后续操作避免解引用空指针if (new_p NULL){perror(malloc);//进行报错在屏幕上会出现错误提示exit(0);//直接让程序结束}//开辟成功就将x存入新的节点中节点中的指针next指向NULLnew_p-data x;new_p-next NULL;return new_p;
}打印链表
这里只需将头指针的内容作为实参穿过来利用形参指针phead接收就能达到效果
void SLTPrint(SLTNode* phead)//这里接收的是第一个结点的地址
{while (phead ! NULL){printf(%d-, phead-data);phead phead-next;}printf(NULL\n);
}头插法
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead ! NULL);SLTNode* p_node SLTCreatNode(x);p_node-next *pphead;*pphead p_node;
}尾插法
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//pphead里存的是phead的地址不可能为NULL所以如果传来NULL就会出问题因此需要防止误传NULL指针这里就要断言一下assert(pphead ! NULL);SLTNode* p_node SLTCreatNode(x);//试着将空链表的逻辑带入else中你会发现cur-next在访问空指针这是不行的所以要专门为链表为空这个特殊情况写一段代码if (*pphead NULL){*pphead p_node;}else{SLTNode* cur *pphead;while (cur-next ! NULL){cur cur-next;}cur-next p_node;}
}头删法
void SLTPopFront(SLTNode** pphead)
{assert(pphead ! NULL);assert(*pphead ! NULL);//如果传来的是个空链表就报错SLTNode* tmp *pphead;*pphead (*pphead)-next;free(tmp);
}尾删法
//尾删的时候分三种情况讨论没有节点一个节点多个节点
//不是说上来你就知道要分三种情况而是当你写出适应多个节点的代码后
//这时你就要考虑边界情况没有节点或者一个还是两个节点的情况
void SLTPopBack(SLTNode** pphead)
{assert(pphead ! NULL);assert(*pphead ! NULL);//头指针为空没有节点就报错if ((*pphead)-next NULL)//只有一个节点的情况{free(*pphead);*pphead NULL;}else//多个节点{SLTNode* cur *pphead;SLTNode* prev NULL;while (cur-next ! NULL){prev cur;cur cur-next;}prev-next NULL;free(cur);}
}给指定的地址插入数据
这里是要将数据插入到pos前为什么我们会知道一个结点的地址pos呢答案就是查找函数帮你找的
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead ! NULL);assert(pos ! NULL);assert(*pphead);//传过来头指针指向的是空SLTNode* p_new SLTCreatNode(x);if (*pphead pos){p_new-next *pphead;*pphead p_new;}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}p_new-next prev-next;prev-next p_new;
查找数据
返回的是查找到结点的地址
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{assert(phead ! NULL);SLTNode* cur phead;while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
}销毁链表意外的知识
在C语言和C中程序员在堆区开辟的数据需要程序员亲手释放一个一个开出的节点只能一个一个释放掉。 这里既可以用一级指针也可以用二级指针不过有个小小的区别当你用free释放一个指针的动态内存后需要及时置空那么在这里我们的头指针phead在释放完链表后也需要及时置空 但是
如果你传的实参是phead本身那当SLTDestory执行完后你需要额外的将phead手动置空如果传的是phead的地址那么在函数SLTDestory中释放完链表后就可以操作*pphead NULL,其实就等于在函数内部将函数外部的phead置空出了函数就不需要手动置空了到这里或许是有些抽象你可以想一下free函数它把指针释放后需要你手动置空实际上原因就是你传的是指针本身free函数不能在它的内部将这个指针置空所以需要你在free执行完手动置空
void SLTDestory(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){SLTNode* nxt cur-next;free(cur);cur nxt;}
}
void test()
{SLTNode* phead NULL;...SLTDestory(phead);phead NULL;//手动置空
}void SLTDestory(SLTNode** pphead)//用二级指针接收phead的地址
{SLTNode* cur *pphead;while(cur ! NULL){SLTNode* nxt cur-next;free(cur);cur nxt;}*phead NULL;//远程操作置空
}
void test()
{LSTNode* phead NULL;...SLTDestory(phead);//实参是指针变量phead的地址
}哨兵位 哨兵位也算是一个结点但哨兵位是不计入链表的长度。哨兵位里不需要存值最好不要存有的数据结构书上会将哨兵位存入链表的结点个数但这里的前提是你创建的链表是存储int型的数据如果是char呢那么根据数据在内存中的存储方式不同char型只能存储8个bit的数据范围也就是-128~127如果这个链表结点个数大于127那么这个哨兵位存的数据就会出错如果换做是浮点型那就更离谱了所以哨兵位最好不要存储数据。
初始化
LSTNode* phead (LSTNode*)malloc(sizeof(LSTNode));
//phead这个指针变量指向哨兵位传参
有了哨兵位再也不用为二级指针苦恼了 每当我们可能对链表的头结点进行插入或者删除实际是phead指向的结点的地址改变了phead的内容需要更改只能通过二级指针的方式远程操控phead 现在哨兵位出现了你想对链表的头结点进行操作想改变头结点的地址随便改我phead现在指向是哨兵位哨兵位的地址是固定不变的再也不用担心要修改链表的同时还要考虑需不需要修改phead的指向当哨兵位不改变时链表怎样的增删改都只会影响哨兵位的指向,与phead无关
这里用头删演示
void SLTPopFront(SLTNode* phead)
{assert(phead ! NULL);assert(phead-next ! NULL);//当链表为空还要删就报错SLTNode* tail phead-next;phead-next tail-next;free(tail);
}为什么都是用头删头插演示呢
那是因为这两个操作更改的是第一个结点节点发生改变那就要更新指向这个结点的指针现在的函数实参传的是哨兵位的地址phead指向的也就是哨兵位传的是哨兵位的地址那就可以对哨兵位进行更新而远在函数外的头指针一直指向的都是固定不变的哨兵位的地址。而前面我们如果更改了第一个结点那就要更新头指针想在函数里更改函数外的指针只能传指针的地址指针的地址就需要二级指针接收。当然重点讲带头单链表的原因也在于算法题里的链表大部分都是带头链表避免与哨兵位混淆。哨兵位在某些时刻也会帮忙简化一些判断甚至帮助解题后续有机会讲算法题会提到的。
