青岛网站改版,设计师赚钱的网站,东莞公司网站价格,google关键词推广目录 带头双向循环链表带头双向循环链表的实现带头双向循环链表的功能实现创造新节点LTNode* CreateLTNode(LTDataType x)代码 初始化链表LTNode*LTInit(LTNode* phead)代码 打印链表void LTPrint(LTNode* phead)代码 链表尾插void LTPushBack(LTNode* phead, LTDataType x)代码… 目录 带头双向循环链表带头双向循环链表的实现带头双向循环链表的功能实现创造新节点LTNode* CreateLTNode(LTDataType x)代码 初始化链表LTNode*LTInit(LTNode* phead)代码 打印链表void LTPrint(LTNode* phead)代码 链表尾插void LTPushBack(LTNode* phead, LTDataType x)代码 链表头插 void LTPushFront(LTNode* phead, LTDataType x)代码 链表尾删 void LTPopBack(LTNode* phead)链表头删void LTPopFront(LTNode* phead)代码 链表查找void LTFind(LTNode* phead)代码 在链表任意位置前插入void LTInsert(LTNode* pos, LTDataType x)代码 在链表任意位置前删除void LTErase(LTNode* pos, LTNode* phead, LTDataType x)代码 链表销毁void LTDestory(LTNode* phead)代码 顺序表和链表的区别和联系链表双向优势顺序表问题 感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接 个人主页 C语言 ️️️
C语言例题 python 数据结构C语言 以下我写的一些文章,如果在阅读这篇文章过程中有疑惑的可以看一下 动态内存管理(下malloc free等函数的用法 动态内存管理(下)free空间等一些问题 自定义类型结构体(下)计算结构体内存大小的方法 自定义类型结构体(中)计算结构体内存大小的方法 自定义类型结构体(上)结构体的用法 C语言深入理解指针非常详细一指针的用法 C语言深入理解指针非常详细二指针的用法以及野指针问题和assert用法 C语言深入理解指针非常详细三二级指针 单链表详解 顺序表详解
带头双向循环链表
带头双向循环链表的结构是链表中最复杂的.一般用于单独存储数据
带头双向循环链表的结构如图 这个链表中的head为哨兵位,哨兵位只存储他前一个节点(尾节点)和后一个节点(头节点)的地址,不存储有效的数据,当链表没有节点的时候,哨兵位也必须存在,这种情况就是哨兵位的箭头都指向他自己
我们有了这个哨兵位节点后就可以轻松的实现尾插,不用像之前的单向链表一样,要遍历一遍找到尾节点后再实现尾插
带头双向循环链表的实现
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType val;
}LTNode;next为指向后一个节点的指针,prev为指向前一个节点的指针,data为存储的有效数据
带头双向循环链表的功能实现
创造新节点LTNode* CreateLTNode(LTDataType x)
代码
LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;newnode-prev NULL;return newnode;
}初始化链表LTNodeLTInit(LTNode phead)
初始化链表是让链表只有一个哨兵位让哨兵位的next和prev都指向他自己因为CreateLNode必须要传入一个值所以我们固定传一个-1进去
代码
LTNode*LTInit(LTNode* phead)
{LTNode* newnode CreateLTNode(-1);phead-next phead;phead-prev phead;return phead;
}打印链表void LTPrint(LTNode* phead)
打印链表需要注意的一点就是我们应该怎么去判断结束因为这个链表是循环链表他不像单向不循环链表一样当指针指向空时就结束停止打印
所以我们需要用到循环的这个特点当我们循环完一遍后就可以停止打印
具体过程就是我们定义一个cur指针指向phead-next(phead是哨兵位,没有有效数据,所以直接跳过),判断结束的条件是while(cur!phead)(循环完一遍后回到哨兵位),每次循环让curcur-next
代码
void LTPrint(LTNode* phead)
{assert(phead);printf(哨兵位-);LTNode* cur phead-next;while (cur ! phead){printf(%d-, cur-val);cur cur-next;}
}链表尾插void LTPushBack(LTNode* phead, LTDataType x) 我们需要用tail指针指向尾节点,让尾节点的next指向newnode,并且让newnode的prev指向tail 然后就是让新的尾节点和head连接起来,我们就让newnode的next指向head,head的prev指向newnode,就实现了尾插 我们还需要注意,这个链表有没有空链表的情况,换句话来说就是实现这个函数时有没有必要assert(phead)
当链表为空时,就代表着这个链表没有任何节点(包括哨兵位),哨兵位是不可以为空的,即使链表没有有效数据,哨兵位也必须存在,所以我们需要保证传进来的phead是不可以为空
代码
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode CreateLTNode(x);tail-next newnode;newnode-next phead;newnode-prev tail;phead-prev newnode;
}链表头插 void LTPushFront(LTNode* phead, LTDataType x)
代码
方法一
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode CreateLTNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;
}方法二
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode CreateLTNode(x);LTNode* first phead-next;phead-next newnode;newnode-prev phead;newnode-next first;first-prev newnode;
}链表尾删 void LTPopBack(LTNode* phead)
尾插需要用一个指针tailprev保存尾节点的前一个地址,删除尾节点后让tailprev-next指向phead,再让phead-prev指向tailprev
我们需要注意当链表中只有一个哨兵位时,我们是不可以删除的,所以我们需要断言提醒
void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail phead-prev;LTNode* tailprev tail-prev;free(tail);tailprev-next phead;phead-prev tailprev;
}链表头删void LTPopFront(LTNode* phead)
链表的头删有三个指针,pheadhead,firstphead-next,secondfirst-next,删除链表时我们需要先让phead-next指向second.然后让second-prev指向phead,最后释放掉first,让first的prev和next都指向空, 这种方法也适用于链表中只有一个节点的情况 因为second为first-next,first-next是指向哨兵位,所以second也就指向哨兵位了 当链表只有一个哨兵位时,first和second都是phead,如果我们将first对空间释放掉的话,那就意味着phead的空间也会被释放,这样就会出现野指针,为了防止这样的情况出现,我们需要加一个断言assert(phead-!phead)
代码
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next!phead);LTNode* first phead-next;LTNode* second first-next;phead-next second;second-prev phead;free(first);first NULL;
}链表查找void LTFind(LTNode* phead)
代码
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-val){return cur;}cur cur-next;}return NULL;
}在链表任意位置前插入void LTInsert(LTNode* pos, LTDataType x)
要在双链表pos位置前插入,比较简单的一种做法就是设一个指针posprev,让posprevpos-prev,之后的过程就如下图 注意pos可以等于phead,因为是双向循环链表,所以当posphead时,我们可以理解成尾插
代码
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev pos-prev;LTNode* newnode CreateLTNode(x);posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;
}在链表任意位置前删除void LTErase(LTNode* pos, LTNode* phead, LTDataType x)
删除的时候我们需要判断pos位置释放为哨兵位,其他的都和前面的差不多
代码
void LTErase(LTNode* pos, LTNode* phead, LTDataType x)
{assert(pos);assert(pos ! phead);LTNode* posNext pos-next;LTNode* posPrev pos-prev;posPrev-next posNext;posNext-prev posPrev;free(pos);pos NULL;
}
链表销毁void LTDestory(LTNode* phead)
链表的销毁其实传入的参数应该为LTNode**phead,包括前面的链表删除,因为如果只是一级指针,那么这种情况就和我之前写的单链表(链表的尾插void SLPushBack(SLNode** pphead, SLNDataType x))这部分相似,但是用LTNode* phead当参数也是可以的只不过需要用完函数后在函数外面将指针变成空
代码
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);phead NULL;
}顺序表和链表的区别和联系
链表双向优势
1任意位置插入删除时间复杂度O1 2按需申请释放合理利用空间 缺点 1下标随机访问不方便时间复杂度为ON像数组一样下标访问是不方便的
顺序表问题
1头部或者中间插入效率低要挪动空间时间复杂度为ON 2空间不够需要扩容且扩容有一定的消耗可能存在一定的空间浪费 3只适合尾插尾删 优点 1支持下标随机访问时间复杂度O1
