[关闭]
@coder-pig 2019-05-31T14:24:47.000000Z 字数 3823 阅读 1838

小猪的数据结构辅助教程——2.7 线性表中的双向循环链表

数据结构


本节学习路线图与学习要点

学习要点

1.了解引入双向循环链表的原因
2.熟悉双向循环链表的特点以及存储结构
3.掌握双向循环链表的一些基本操作的实现逻辑
4.掌握逆序输出双向循环链表元素逻辑


1.双向循环链表的引入


2.双向循环链表的存储结构

双向循环链表的特点

上面也说了,空间换时间,比起循环链表只是多了一个指向前驱的指针
特点的话:
判断空表:L ->next = L -> prior = L;

存储结构

  1. typedef struct LNode
  2. {
  3. ElemType data; //数据域
  4. struct LNode *prior; //前驱指针
  5. struct LNode *next; //后继指针
  6. }LNode;
  7. typedef struct LNode *LinkList;

双向循环链表的结构图


3.相关基本操作的代码实现

1)构建空表

  1. Status InitList(LinkList L)
  2. {
  3. L = (LinkList)malloc(sizeof(LNode));
  4. if(!L)exit(ERROR);
  5. else L ->next = L ->prior = L;
  6. return OK;
  7. }

逻辑解析

很简单,就是头结点自己指自己而已~


2)将表置空

  1. void ClearList(LinkList L)
  2. {
  3. LinkList p = L ->next; //指向第一个结点
  4. while(p != L)
  5. {
  6. p = p ->next; //指向下一个结点
  7. free(p->prior); //释放该结点的前驱结点
  8. }
  9. L ->next = L ->prior = L; //自己指自己
  10. }

3)判断是否为空表

  1. Status ListEmpty(LinkList L)
  2. {
  3. return L->next == L && L ->prior == L?TRUE:FALSE;
  4. }

4)销毁表

  1. void DestoryList(LinkList L)
  2. {
  3. ClearList(L);
  4. free(L);
  5. L = NULL;
  6. }

5)获得表长度

  1. int ListLength(LinkList L)
  2. {
  3. int i = 0;
  4. LinkList p = L ->next;
  5. while(p != L)
  6. {
  7. i++;
  8. p = p ->next;
  9. }
  10. return i;
  11. }

6)获得表中第i个元素的值

  1. Status GetElem(LinkList L,int i,ElemType *e)
  2. {
  3. int j = 1;
  4. LinkList p = L ->next; //指向第一个结点
  5. while(p != L && j < i) //指针后移
  6. {
  7. j++;
  8. p = p ->next;
  9. }
  10. if(p == L || j > i)return ERROR; //找不到该元素
  11. e = p ->data;
  12. return OK;
  13. }

7)查找表中是否存在满足条件的元素

  1. int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
  2. {
  3. int i = 0;
  4. LinkList p = L ->next ->next; //指向第一个结点
  5. while(p != L ->next)
  6. {
  7. i++;
  8. if(compare(p->data,e))return i;
  9. p = p ->next;
  10. }
  11. return 0; //找不到,返回0
  12. }

8)获得某个节点的直接前驱

  1. Status BeforeElem(LinkList L,ElemType choose,ElemType *before)
  2. {
  3. LinkList p = L ->next ->next; //指向第二个结点
  4. while(p != L) //未指向头结点
  5. {
  6. if(p ->data == choose)
  7. {
  8. before = p ->prior ->data;
  9. return OK;
  10. }
  11. p = p ->next;
  12. }
  13. return ERROR;
  14. }

9)获得某个节点的直接后继

  1. Status NextElem(LinkList L,ElemType choose,ElemType *behind)
  2. {
  3. LinkList p = L ->next ->next; //指向第二个结点
  4. while(p != L)
  5. {
  6. if(p ->prior ->data == choose)
  7. {
  8. behind = p ->data;
  9. return OK;
  10. }
  11. p = p ->next;
  12. }
  13. return ERROR;
  14. }

10)返回第i个元素的地址

  1. LinkList GetElemAdd(LinkList L,int i)
  2. {
  3. int j;
  4. LinkList p = L;
  5. if(i < 0 || i > ListLength(L))return NULL; //判断i值位置是否合法
  6. for(j = 1;j < = i;j++)
  7. {
  8. p = p ->next;
  9. }
  10. return p;
  11. }

11)往第i个位置插入元素

  1. Status ListInsert(LinkList L,int i,ElemType e)
  2. {
  3. LinkList p,q;
  4. //判断i值是否合法
  5. if(i < 1 || i > ListLength(L) + 1)return ERROR;
  6. p = GetElemAdd(L,i - 1);
  7. //NULL的话说明,第i个结点的前驱不存在,
  8. //这里假设头节点为第一个结点的前驱
  9. if(!p)return ERROR;
  10. q = (LinkList)malloc(sizeof(LNode));
  11. if(!q)return ERROR;
  12. q ->data = e; //给新结点赋值
  13. q ->prior = p; //新结点的前驱为第i - 1个结点
  14. q ->next = p ->next; //新结点的后记为第i个结点
  15. p ->next ->prior = q; //第i个结点前驱指向新结点
  16. p ->next = q; //第i-1个结点的后继指向新结点
  17. return OK;
  18. }

实现逻辑图

12)删除第i个位置的元素

  1. Status ListDelete(LinkList L,int i,ElemType *e)
  2. {
  3. LinkList p;
  4. if(i < 1)return ERROR; //判断删除位置是否合法
  5. p = GetElemAdd(L,i);
  6. if(!p)return ERROR; //为NULL说明第i个元素不存在
  7. e = p ->data;
  8. p ->prior ->next = p ->next; //i-1个结点的后继指向滴i+1个结点
  9. p ->next ->prior = p ->prior; //第i+1个结点的前驱指向第i - 1个结点
  10. free(p); //释放第i个结点
  11. return OK;
  12. }

实现逻辑图

嘿嘿,是不是觉得少了个遍历表中元素的基本操作呢,别急,我们下面写个例子,
按正序遍历链表,以及逆序来遍历表中的所有元素~


4.简单例子:正序和逆序遍历表中元素

运行截图

代码实现

  1. #include <stdio.h>
  2. #include<stdlib.h>
  3. #define OK 1
  4. #define ERROR 0
  5. #define TRUE 1
  6. #define FALSE 0
  7. typedef int ElemType;
  8. typedef int Status;
  9. typedef struct LNode
  10. {
  11. ElemType data; //数据域
  12. struct LNode *prior; //前驱指针
  13. struct LNode *next; //后继指针
  14. }LNode;
  15. typedef struct LNode *LinkList;
  16. //定义一个创建N个结点的方法
  17. LinkList ListCreate(int N)
  18. {
  19. LinkList p,q,head;
  20. int i,data;
  21. q = head;
  22. head = (LinkList)malloc(sizeof(LNode));
  23. head ->prior = head;
  24. head ->next = head;
  25. p = head;
  26. for(i = 0;i < N;i++)
  27. {
  28. printf("请输入第%d个结点的值:",i + 1);
  29. scanf("%d",&data);
  30. q = (LinkList)malloc(sizeof(LNode));
  31. q ->data = data;
  32. p ->next = q;
  33. q ->prior = p;
  34. q ->next = head;
  35. head ->prior = q;
  36. p = q;
  37. }
  38. return head;
  39. }
  40. //定义一个打印结点数据的方法
  41. void PrintNode(ElemType e)
  42. {
  43. printf("%d\t",e);
  44. }
  45. //定义一个正序输出链表的方法
  46. void ListTraverse(LinkList L)
  47. {
  48. LinkList p = L->next; //指向首元结点
  49. while(p!=L)
  50. {
  51. PrintNode(p->data);
  52. p = p ->next;
  53. }
  54. printf("\n");
  55. }
  56. //定义一个逆序输出链表的方法
  57. void ListTraverseBack(LinkList L)
  58. {
  59. LinkList p = L ->prior; //指向最后一个结点
  60. while(p!=L)
  61. {
  62. PrintNode(p->data);
  63. p = p ->prior;
  64. }
  65. printf("\n");
  66. }
  67. int main()
  68. {
  69. LinkList p;
  70. int N = 0;
  71. printf("请输入双向链表的结点个数:");
  72. scanf("%d", &N);
  73. p = ListCreate(N);
  74. printf("正序打印链表中的结点:\n");
  75. ListTraverse(p);
  76. printf("逆序打印链表中的结点:\n");
  77. ListTraverseBack(p);
  78. return 0;
  79. }

很简单,就不BB了~


5.本节示例代码下载:

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/list5.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/list6.c

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注