史上最强数据结构----双向循环链表的实现(带哨兵位)

x33g5p2x  于2022-03-28 转载在 其他  
字(3.4k)|赞(0)|评价(0)|浏览(526)

1、双向链表的基本结构

图示:

2、双向链表的基本结构实现

代码:

  1. typedef int LTDataType;
  2. typedef struct ListNode
  3. {
  4. LTDataType data;//存储的数据
  5. struct ListNode* next;//存储下一个节点的地址
  6. struct ListNode* prev;//存储上一个节点的地址
  7. }ListNode;

3、双向链表的初始化

图示:

代码:

第一种:传二级指针的

  1. void ListInit(ListNode** phead);//初始化函数的声明
  2. void ListInit(ListNode** phead)//为什么要传二级指针,因为改变的是结构体的指针,所以要传结构体的指针
  3. {
  4. assert(phead);
  5. *phead = BuyListNode(-1);//此处是开辟一个哨兵位的节点,存储的是无效数据,-1也是随便给的
  6. (*phead)->next = (*phead);
  7. (*phead)->prev = (*phead);
  8. //这两行代码主要是使哨兵位的next指针和prev指针自己指向自己,形成双向循环结构
  9. }
  10. //下面是main函数中调用初始化函数的地方,为了方便理解二级指针
  11. int main()
  12. {
  13. ListNode*phead = NULL;//初始化之后,phead就会指向哨兵位,即NULL发生了改变,即改变的是结构体的指针,所以要传二级指针
  14. ListNode(&phead);
  15. return 0;
  16. }

第二种:不传二级指针的

  1. ListNode* ListInit(ListNode* phead);//初始化函数的声明
  2. ListNode* ListInit()//此处为什么不传二级指针,因为在函数中会将开辟的哨兵位的地址作为返回值返回
  3. {
  4. ListNode*phead = NULL;
  5. phead = BuyListNode(-1);//此处是开辟一个哨兵位的节点,存储的是无效数据,-1也是随便给的
  6. phead->next = phead;
  7. phead->prev = phead;
  8. //这两行代码主要是使哨兵位的next指针和prev指针自己指向自己,形成双向循环结构
  9. }
  10. int main()
  11. {
  12. ListNode*phead = ListInit();
  13. return 0;
  14. }

4、双向链表的尾插

图示:

代码:

  1. void ListPushBack(ListNode* phead, LTDataType x)
  2. {
  3. assert(phead);//哨兵位不可为空
  4. ListNode* newnode = BuyListNode(x);
  5. ListNode* tail = phead->prev;
  6. tail->next = newnode;//(1)
  7. newnode->prev = tail;//(2)
  8. newnode->next = phead;//(3)
  9. phead->prev = newnode;//(4)
  10. }

5、双向链表的尾删

图示:

代码:

  1. void ListPopBack(ListNode* phead)
  2. {
  3. assert(phead);
  4. assert(phead->next == phead);//链表为空
  5. ListNode* tail = phead->prev;
  6. ListNode* tailPrev = tail->prev;
  7. free(tail);
  8. tail = NULL;
  9. tailPrev->next = phead;//(1)
  10. phead->prev = tailPrev;//(2)
  11. }

6、双向链表的头插

图示:

代码:

  1. void ListPushFront(ListNode* phead,LTDataType x)
  2. {
  3. assert(phead);
  4. ListNode* next = phead->next;
  5. ListNode* newnode = BuyListNode(x);
  6. phead->next = newnode;//(1)
  7. newnode->prev = phead;//(2)
  8. next->prev = newnode;//(3)
  9. newnode->next = next;//(4)
  10. }

7、双向链表的头删

图示:

代码:

  1. void ListPopFront(ListNode* phead)
  2. {
  3. assert(phead);
  4. assert(phead->next != phead);
  5. ListNode* nextNext = phead->next->next;
  6. free(phead->next);
  7. phead->next = nextNext;//(1)
  8. nextNext->prev = phead;//(2)
  9. }

8、双向链表的打印

代码:

  1. void ListPrint(ListNode* phead)
  2. {
  3. assert(phead);
  4. ListNode* cur = phead->next;
  5. while (cur != phead)//当cur = phead的时候说明已经遍历完一遍了
  6. {
  7. printf("%d->", cur->data);
  8. cur = cur->next;
  9. }
  10. printf("NULL\n");
  11. }

9、双向链表元素的查找

代码:

  1. ListNode*ListFind(ListNode* phead, LTDataType x)
  2. {
  3. assert(phead);
  4. ListNode* cur = phead->next;
  5. while (cur!=phead)
  6. {
  7. if (cur->data == x)
  8. {
  9. return cur;
  10. }
  11. cur = cur->next;
  12. }
  13. return NULL;
  14. }

注意:为什么要在最开始将cur置为phead->next?

1. 因为phead作为哨兵位中存储的不是有效数据,所以不能从这个开始查找。
2. 同时phead作为查找的终止条件,不能从这个元素开始,如果从这个元素开始遍历查找的话在一开始查找就停止了。

10、双向链表特定元素的删除

图示:

代码:

  1. void ListErase(ListNode* pos)
  2. {
  3. assert(pos);
  4. ListNode* next = pos->next;
  5. ListNode* prev = pos->prev;
  6. free(pos);
  7. pos = NULL;//此处可以置空也可以不置空,因为pos只是函数中的局部变量
  8. prev->next = next;//(1)
  9. next->prev = prev;//(2)
  10. }

驼峰法命名规则:

  1. 函数名和类型名所有单词首字母大写
  2. 变量:第一个单词小写,后续单词首字母大写

11、双向链表特定元素的前插

图示:

代码:

  1. void ListInsertBefore(ListNode* phead, ListNode* pos, LTDataType x)
  2. {
  3. assert(pos);
  4. ListNode* newnode = BuyListNode(x);
  5. ListNode* prev = pos->prev;
  6. prev->next = newnode;//(1)
  7. newnode->prev = prev;//(2)
  8. pos->prev = newnode;//(3)
  9. newnode->next = pos;//(4)
  10. }

12、双向链表的销毁

图示:

代码:

第一种:传二级指针的,此时会将哨兵位的空间进行释放。

  1. void ListDestory(ListNode** phead)
  2. {
  3. assert(phead);
  4. ListNode* cur = (*phead)->next;
  5. while (cur!=(*phead))//结束条件就是不等于头节点
  6. {
  7. ListNode* next = cur->next;//存储当前释放节点的下一个节点的地址
  8. free(cur);//释放当前节点
  9. cur = next;//将节点向后推移
  10. }
  11. free(*phead);//释放哨兵位节点
  12. *phead = NULL;//防止内存泄漏
  13. }

第二种:不传二级指针的,此时不将哨兵位的空间进行释放。

  1. void ListDestory(ListNode* phead)
  2. {
  3. assert(phead);
  4. ListNode* cur = phead->next;
  5. while (cur != phead)
  6. {
  7. ListNode* next = cur->next;
  8. free(cur);
  9. cur = cur->next;
  10. }
  11. cur = NULL;
  12. }

相关文章