莱芜网站建设费用,佛山最好的网站建设公司,如何用源码建站,网站设计类毕业设计链表1.为什么存在链表2.链表的概念3.单链表的实现4.测试1.为什么存在链表
我们在学习顺序表的时候#xff0c;了解到顺序表有一定的缺陷#xff1a;#xff08;1#xff09;在中间插入数据和删除数据需要挪动数据#xff0c;时间复杂度是O#xff08;N#xff09;…
链表1.为什么存在链表2.链表的概念3.单链表的实现4.测试1.为什么存在链表
我们在学习顺序表的时候了解到顺序表有一定的缺陷1在中间插入数据和删除数据需要挪动数据时间复杂度是ON效率低下。2realloc会异地扩容需要申请新空间拷贝数据释放旧空间。有不小的消耗。3 realloc扩容后难免有一定的空间浪费数据删除后的空间或者扩容后不用的空间。而链表就能弥补顺序表的缺点。 2.链表的概念
链表是一种物理存储结构上非连续地址非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表就是在逻辑结构上就是一条链链接着一个个节点每个节点就是一个结构体包含数据和指向下一个节点的地址。 节点的定义
typedef int SLTDataType;//方便后面更改数据的类型//比如你存储的数据不是整形而是浮点型就可以在这里修改
typedef struct SListNode//链表的节点
{SLTDataType data;//数据struct SListNode* next;//指向下一个节点的指针
}SLTNode;//重命名有意义的、简短的名字3.单链表的实现
打印链表假设现在有一个现成的链表上图
void SLTPrint(SLTNode* plist)//plist是头节点
{while (plist!NULL){printf(%d-, plist-data);plist plist-next;}printf(NULL\n);
}结果 1-2-3-4-NULL 疑惑 1plist plist-next;是什么意思能不能写成plist; a.plist是头节点指向第一个节点节点的成员next是指针指向第二个节点将next存储的地址赋值给plistplist就指向第二个节点。以此类推直到plist指向最后一个节点的空指针。b.不能。plist跳到物理地址上的下一个结构体。而链表的各节点在物理地址上是不连续的。
2循环体的判断条件能否改成whlie(plist-next!NULL) 不能因为最后一个元素没有打印。
单链表尾插 1首先在找到最后一个节点然后接上要插入的新节点。 2其次要考虑特殊情况如果单链表是空链表该如何解决
void SLTPushBack(SLTNode** pplist, SLTDateType x)//pplist是指向头节点的指针x是新节点的数据
{assert(pplist);//pplist接收plist的地址一定不是NULL就更要断言防止函数传参传个NULL过来//首先获得一个新节点SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL)//检查是否申请空间失败{perror(malloc);return;}newnode-data x;//记得把数据放入新节点newnode-next NULL;//记得将next置为NULL//考虑是空链表if (*pplist NULL){*pplist newnode;//直接让头指针接上新的节点就行return;}//不是空链表else{//首先找到链表的尾巴SLTNode* tail *pplist;while (tail-next ! NULL)//当tail指向最后一个节点时停止循环因为最后一个节点的next是NULL{tail tail-next;}//然后接上新节点tail-next newnode;}
}画图分析
疑惑 1在函数开头对pplist进行断言有没有必要对*pplist断言 没有这个链表是空的我们就是要对其进行尾插才不为空断言了就不能对空链表进行尾插。 2为什么函数传参要传头节点的地址 我们都知道形参是实参的临时拷贝形参的改变不影响实参。如果要改变实参就是传实参的地址。在单链表不为空时直接传头节点可以实现尾插但在单链表为空时则不能实现如图。
单链表头插 同样需要考虑两种情况单链表为空或者单 链表不为空。
// 单链表的头插
void SLTPushFront(SLTNode** pplist, SLTDateType x)
{assert(pplist);//获得一个新的节点直接将这个功能封装成一个函数SLTNode* newnode GetNewNode(x);//先考虑普通再考虑特殊SLTNode* tmp *pplist;//加入一个临时变量保存旧的头节点*pplist newnode;newnode-next tmp;//最终我们发现链表为空也适用不用考虑特殊情况
}//获得新节点
SLTNode* GetNewNode(SLTDateType* x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc);return;}newnode-data x;newnode-next NULL;
}单链表尾删
void SLTPopBack(SLTNode** pplist)
{assert(pplist);//空链表就没必要删除//找到尾巴SLTNode* tail *pplist;SLTNode* tailFront tail;同时需要记录尾巴前一个节点while (tail-next)//当tail指向最后一个节点时tailFront指向上一个节点{tailFront tail;}free(tail);tail NULL;tailFront-next NULL;
}是不是这样做就完成了并没有当只有一个节点时就会这个函数就不能实现尾删。
//正确做法
void SLTPopBack(SLTNode** pplist)
{//空链表就没必要删除assert(*pplist);//找到尾巴SLTNode* tail *pplist;SLTNode* tailFront tail;同时需要记录尾巴前一个节点//只有一个节点if (tail-next NULL){*pplist NULL;free(tail);tail NULL;return;}while (tail-next)//当tail指向最后一个节点时tailFront指向上一个节点{tailFront tail;tail tail-next;}free(tail);tail NULL;tailFront-next NULL;
}单链表头删
void SLTPopFront(SLTNode** pplist)
{//防止为空assert(*pplist);SLTNode* first *pplist;//记录要删除的头节点*pplist first-next;//适用于所有特殊情况包括只有一个节点。free(first);first NULL;
}单链表查找
SLTNode* SLTFind(SLTNode* plist, SLTDateType x)
{SLTNode* tmp plist;while (tmp){if (tmp-data x){return tmp;}tmp tmp-next;}return tmp;
}单链表在pos之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);//首先获得一个新节点SLTNode* newnode GetNewNode(x);newnode-next pos-next;pos-next newnode;
}疑惑 为什么不在pos位置之前插入 当pos刚好是第一个节点时插入新的节点后由于函数并没有传头节点过来所以头节点将无法指向新的节点。其实也可以在pos这个位置插入只要将pos这个位子的数据和插入节点的数据交换一下然后插入节点继续在pos之后插入这样数据就像在pos之前的节点插入一样。
单链表删除pos位置之后的值
void SListEraseAfter(SLTNode* pos)
{assert(pos);//要考虑pos指向最后一个节点的情况if (pos-next NULL){return;}SLTNode* tmp pos-next;pos-next pos-next-next;free(tmp);tmp NULL;
}疑惑 为什么不删除pos位置 当pos是第一个节点时被释放后由于函数没有传头节点头节点将指向野指针同时无法指向新的链表
单链表的销毁
void SLTDestroy(SLTNode* plist)
{assert(plist);SLTNode* tmp plist-next ;//用来遍历链表while (tmp){free(plist);plist tmp;tmp tmp-next;}free(plist);plist NULL;
}分析 当只有一个节点时tmp NULL不进入循环直接将头节点释放当有多个节点tmp进入循环在tmp NULL时plist指向最后一个节点并没有在while中释放所以出了循环之后还要释放一次。 4.测试
