[关闭]
@coder-pig 2019-05-31T06:04:29.000000Z 字数 2804 阅读 927

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

数据结构


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

学习要点

  • 1.了解单链表存在怎样的缺点,暴露出来的问题
  • 2.知道什么是循环单链表,掌握单链表的特点以及存储结构
  • 3.掌握循环链表的一些基本操作的实现逻辑,最好能手撕代码

1.循环单链表的引入


2.循环链表的特点以及存储结构

循环链表的特点:

上面也说了,比单链表稍微高比格一点的地方就是:
链表最后一个结点的指针域指向了头结点而已,这样形成所谓的环,就是循环单链表了,呵呵!
特点的话有:
我们之前判断单链表是否为空:head -> next 是否为NULL即可
而循环单链表只需:head -> next 是否为head(自身)即可
相关的操作和单链表还是比较相似的!

存储结构:(和单链表一样~)

  1. typedef int ElemType;
  2. typedef int Status;
  3. typedef struct LNode
  4. {
  5. ElemType data; //数据域
  6. struct LNode *next; //指针域
  7. }LNode;
  8. typedef struct LNode *LinkList;

单链表的结构图

如上图,加入我们的链表很长的话,从表头找到表尾是很费时的,所以循环链表往往是设置尾指针
而不是设置头指针!尾指针尾指针尾指针


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

1)构造空表

  1. Status InitList(LinkList L)
  2. {
  3. L = (LinkList)malloc(sizeof(LNode));
  4. if(!L)exit(ERROR);
  5. L ->next = L; //自己指自己~(头节点指针域指向头结点)
  6. return OK;
  7. }

2)将表置空

  1. void ClearList(LinkList L)
  2. {
  3. LinkList p,q;
  4. L = L ->next; //指向头结点
  5. p = L ->next; //指向第一个结点
  6. while(p!=L)
  7. {
  8. q = p ->next;
  9. free(p);
  10. p = q;
  11. }
  12. L ->next = L; //自己指自己
  13. }

3)判断是否为空表

有头节点的哦~

  1. Status ListEmpty(LinkList L)
  2. {
  3. return L!=L ->next?FALSE:TRUE;
  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 ->next; //指向第一个结点
  5. if(i <= 0||i >ListLength)return ERROR; //判断插入位置是否合法
  6. while(j < i)
  7. {
  8. j++;
  9. p = p ->next;
  10. }
  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 q,p = L ->next ->next; //指向第一个结点
  4. q = p ->next;
  5. while(q != L ->next)
  6. {
  7. if(q ->data == choose)
  8. {
  9. before = p ->data;
  10. return OK;
  11. }
  12. p = q; //继续后移
  13. q = q ->next;
  14. }
  15. return ERROR;
  16. }

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 ->data == choose)
  7. {
  8. behind = p ->next ->data;
  9. return OK;
  10. }
  11. }
  12. }

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

  1. Status ListInsert(LinkList L,int i,ElemType e)
  2. {
  3. LinkList s,p = L ->next;
  4. int j = 0;
  5. if(i <= 0 || i > ListLength(L) + 1)return ERROR; //判断插入位置是否合法
  6. //寻找插入结点的前一个结点
  7. while(j < i - 1)
  8. {
  9. j++;
  10. p = p ->next;
  11. }
  12. //生成新结点
  13. s = (LinkList)malloc(sizeof(LNode));
  14. s ->data = e; //将e赋值给新结点
  15. s ->next = p ->next; //新结点指向原来的第i个结点
  16. p ->next = s; //原i - 1个结点指向新结点
  17. //假如插入的位置是表尾,把新的表尾地址给尾指针
  18. if(p == L)
  19. {
  20. L = s;
  21. }
  22. return OK;
  23. }

步骤解析

普通的插入和单链表都是大同小异,普通结点插入的流程:

而特殊情况就是,假如插入位置是尾结点的话,那么还需要让尾指针指向这个新插入的尾结点
就是上面的:L = s;

11)删除表中第i个元素

  1. Status ListDelete(LinkList L,int i,ElemType *e)
  2. {
  3. LinkList s,p = L ->next;
  4. int j = 0;
  5. if(i <= 0||i > ListLength(L))return ERROR;//判断删除位置是否合法
  6. //寻找插入结点的前一个结点
  7. while(j < i - 1)
  8. {
  9. j++;
  10. p = p ->next;
  11. }
  12. s = p ->next;
  13. p ->next = s ->next;
  14. e = s ->data;
  15. if(s == L)
  16. L = p;
  17. free(q); //释放结点
  18. return OK;
  19. }

步骤解析

和插入一样,删除完后,还要考虑尾指针指向的位置

假如删除的是尾结点的话,那么还要让L = p;指向删除结点的前一个节点~

12)遍历循环链表里的所有元素

  1. void ListTraverser(LinkList L,void(*visit)(ElemType))
  2. {
  3. LinkList p = L ->next ->next; //指向第一个结点
  4. while(p != L ->next)
  5. {
  6. visit(p ->data);
  7. p = p ->next;
  8. }
  9. printf("\n");
  10. }

4.本节代码下载:

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

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