前言
带头双向循环链表，是链表中最为复杂的一种结构，我们主要实现的功能为，头插尾插，头删尾删，初始化、打印、指定pos位置插入结点或者删除结点、寻找结点、摧毁链表等函数。
一、带头双向循环链表是什么？
如图所示：
二、实现带头双向循环链表
1.结构体和要实现函数
结构体如下：
1. typedef struct DSLDataType; 2. //定义双向链表的结构体 3. 4. //双向链表每一个节点都有一个前驱节点和后继节点，可以根据节点获得其前后的节点 5. typedef struct DSListNode { 6. struct DSListNode* prev;//前驱节点 7. struct DSListNode* next;//后继节点 8. int value;//数据域 9. }DSLNode;//重定义
相比单向链表，多一个指针域prev，指向前面的结点地址
实现功能的函数：
1. //初始化 2. DSLNode*ListInit(); 3. //打印链表 4. void ListPrint(DSLNode* ps); 5. //尾部插入 6. void ListPushBack(DSLNode* ps, int data); 7. //头部插入 8. void ListPushFront(DSLNode* ps, int data); 9. //尾部删除 10. void ListPopBack(DSLNode* ps); 11. //头部删除 12. void ListPopFront(DSLNode* ps); 13. //判空 14. bool ListEmpty(DSLNode* ps); 15. //返回链表节点个数 16. int Listsize(DSLNode* ps); 17. //寻找指定元素，返回对应的节点 18. DSLNode* ListFind(DSLNode* ps, int data); 19. //在pos之前插入节点 20. void ListInsert(DSLNode* pos, int data); 21. //删除pos位置结点 22. void ListEarse(DSLNode* pos); 23. //摧毁链表 24. void ListDestory(DSLNode* ps);
2.初始化和打印链表
1. //对于函数的实现 2. //初始化 3. DSLNode* ListInit() { 4. //初始化创建链表 5. //创建新节点 6. DSLNode* num = (DSLNode*)malloc(sizeof(DSLNode)); 7. //判断是否创建成功 8. if (num == NULL) { 9. perror("malloc fail\n"); 10. exit(-1); 11. } 12. num->prev = num; 13. num->next = num;//作为头节点，前驱和后驱结点都指向自己 14. return num; 15. } 16. 17. //打印链表 18. void ListPrint(DSLNode* ps) { 19. assert(ps);//断言 20. DSLNode* cur = ps->next; 21. printf("phead->"); 22. while (cur != ps) {//双向链表，回到ps，就表示转了一圈 23. printf("%d->", cur->value); 24. cur = cur->next; 25. } 26. printf("NULL\n"); 27. }
3.头插和尾插
尾插如图所示：
代码如下：
1. 2. DSLNode* CreatNode(int data) {//创建新节点 3. DSLNode* cur = (DSLNode*)malloc(sizeof(DSLNode)); 4. if (cur == NULL) { 5. perror("malloc fail\n"); 6. exit(-1); 7. } 8. cur->next = cur->prev = NULL; 9. cur->value = data; 10. } 11. //尾部插入 12. void ListPushBack(DSLNode* ps, int data) { 13. assert(ps);//断言 14. DSLNode* newnode = CreatNode(data); 15. DSLNode* tail = ps->prev;//把头节点之前的那个地址给tail 16. tail->next = newnode;//将ps之前的那个数值，实际上是这个双向链表的最后一个元素的位置，的next指针指向新节点 17. newnode->prev = tail;//新节点前后为 tail和ps 18. newnode->next = ps; 19. ps->prev = newnode;//tail的两个指针域都指向完成，就只剩下ps的前驱指针 20. 21. }
头插如图所示：
代码如下：
1. 2. //头部插入 3. void ListPushFront(DSLNode* ps, int data) { 4. assert(ps); 5. //头部插入就是将ps之后的一个地址给临时变量tail 6. DSLNode* tail = ps->next; 7. DSLNode* newnode = CreatNode(data);//创建新节点 8. ps->next->prev = newnode; 9. newnode->next = ps->next; 10. newnode->prev = ps; 11. ps->next = newnode; 12. }
4.头删和尾删
尾部删除如图所示：
代码如下：
1. //判空 2. bool ListEmpty(DSLNode* ps) { 3. assert(ps);//断言 4. return ps->next == ps;//如果是只有一个ps头节点，则表示为空，返回true，否则返回false 5. 6. } 7. //尾部删除 8. void ListPopBack(DSLNode* ps) { 9. 10. assert(ps);//断言 11. assert(!ListEmpty(ps));//先判断是否为空 12. DSLNode* cur = ps->prev; 13. //将cur的next值为NULL 14. ps->prev = ps->prev->prev; 15. ps->prev->next = ps; 16. //这是直接略过尾部最后一个元素 17. //跳过ps之前的一个节点，先让其左右节点相连，然后释放这个地址 18. free(cur); 19. cur = NULL; 20. }
头部删除如图所示：
代码如下：
1. //头部删除 2. void ListPopFront(DSLNode* ps) { 3. assert(ps); 4. assert(!ListEmpty(ps)); 5. DSLNode* cur = ps->next; 6. //头删 是将头节点之后的第一个节点删除释放空间 7. ps->next = ps->next->next; 8. ps->next->prev = ps; 9. free(cur); 10. cur = NULL; 11. }
5.查找和返回结点个数
查找：返回一个结点，根据data数值域，来返回第一个遇到的结点cur，若没有返回NULL
1. //返回链表节点个数 2. int Listsize(DSLNode* ps) { 3. assert(ps); 4. int count = 0; 5. DSLNode* cur = ps->next; 6. while (cur != ps) { 7. count++; 8. cur = cur->next; 9. } 10. return count; 11. } 12. //查找 13. DSLNode* ListFind(DSLNode* ps, int data) { 14. assert(ps); 15. DSLNode* cur = ps->next; 16. while (cur != ps) { 17. if (cur->value == data) { 18. return cur; 19. } 20. } 21. return NULL;//NULL表示不存在 22. }
6.在pos位置之前插入结点
如图所示：
代码如下：
1. //插入节点 2. void ListInsert(DSLNode* pos, int data) { 3. 4. assert(pos); 5. //pos三种可能 6. //1.空链表 7. //2.只有一个节点 8. DSLNode* cur = pos->prev; 9. //双向链表可以直接找到pos之前的位置，单向链表只能进行循环 10. DSLNode* newnode = CreatNode(data); 11. pos->prev = newnode;//把新节点newnode的位置给pos的prev 12. newnode->prev = cur;//cur表示的是创建new节点之前的时候pos之前的结点 13. cur->next = newnode; 14. newnode->next = pos; 15. //另一种不使用cur的方法 16. //newnode->next = pos; 17. //pos->prev->next = newnode; 18. //newnode->prev = pos->prev; 19. //pos->prev = newnode; 20. }
