004-循环单链表

moc

1、基本概念
循环单链表的定义：将单链表中的最后一个元素的next指向第一个元素。

        注意：头指针是链表的开始，它的指针域指向头结点，数据域存放着与整个链表相关的数据，如长度等；头指针结点不参与链表循环。
拥有的操作：
        创建链表
        销毁链表
        获取链表长度
        清空链表
        获取链表的第pos个元素
        插入元素到pos位置
        删除pos位置的元素
新增功能： 游标
        在循环链表中可以定义一个“当前”指针，这个指针即通常称的“游标”，可以通过游标来遍历元素。
循环链表的新增操作：
        将游标重置，即指向链表的第一个元素；
        获取当前游标指向的数据元素；
        将游标移动至下一个元素；
        直接指定删除链表中的某个数据元素。
2、设计与实现
1. 插入元素
        ① 普通插入元素：  和单链表一样
        ② 尾插法： 和单链表一样
        ③ 头插法： 需要先求出尾结点，因为0号位置，辅助指针current跳0步，没有跳走仍留在头指针。
        ④ 判断若为第一次插入，让游标指向头结点。

1. void CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
   
2. {
   
3.         int ret = 0, i = 0;
   
4.         TCircleList* tlist = (TCircleList*)list;
   
5.         if (tlist == NULL || node == NULL || pos < 0)
   
6.         {
   
7.                 return -1;
   
8.         }
   
9. 
   
10.         CircleListNode* current = (CircleListNode*)tlist;
    
11.         for (i = 0; (i < pos) && (current->next != NULL); i++)
    
12.         {
    
13.                 current = current->next;
    
14.         }
    
15. 
    
16.         node->next = current->next;  // 1
    
17.         current->next = node;  // 2
    
18. 
    
19.         // 若第一次插入
    
20.         if (tlist->length == 0)
    
21.         {
    
22.                 tlist->slider = node;
    
23.         }
    
24.         tlist->length++;
    
25. 
    
26.         // 若头插法 current仍然指向头部
    
27.         //（原因：跳0步，没有跳走仍留在头指针，导致尾部指针指向第二个结点）       
    
28.         if (current == (CircleListNode*)tlist)
    
29.         {
    
30.                 CircleListNode* last = CircleList_Get(tlist, tlist->length - 1);
    
31.                 last->next = current->next;
    
32.         }
    
33. }

复制代码

2. 其他操作与单链表类似。
3、优缺点与典型应用
优点：
        循环单链表在单链表的基础上功能增强啦；
        完全可以替代单链表。
缺点：
        代码复杂度提高啦。
约瑟夫问题：
        n个人围成一个圆圈，首先第一个人从1开始一个人一个人顺时针报数，报到第m个人，令其出列，然后从下一个人开始顺时针报数，报到第m个人，再令其出列，....，如此下去，求出出列顺序。

循环链表解决方案：

1. typedef struct _Value
   
2. {
   
3.         CircleListNode circleNode;
   
4.         int v;
   
5. }Value;
   
6. 
   
7. int main()
   
8. {
   
9.         int i = 0;
   
10.         CircleList* list = CircleList_Create();
    
11.         Value v1, v2, v3, v4, v5, v6, v7, v8;
    
12.         v1.v = 1;  v2.v = 2;  v3.v = 3;  v4.v = 4;
    
13.         v5.v = 5;  v6.v = 6;  v7.v = 7;  v8.v = 8;
    
14. 
    
15.         CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
    
16.         CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
    
17.         CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
    
18.         CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
    
19.         CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));
    
20.         CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));
    
21.         CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));
    
22.         CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));
    
23. 
    
24.         for (i = 0; i < CircleList_Length(list); i++)
    
25.         {
    
26.                 // 获取游标所指的元素，然后游标下移
    
27.                 Value* pv = (Value*)CircleList_Next(list);
    
28.                 printf("%d\n", pv->v);
    
29.         }
    
30.         printf("\n");
    
31. 
    
32.         // 重置游标
    
33.         CircleList_Reset(list);
    
34. 
    
35.         while (CircleList_Length(list) > 0)
    
36.         {
    
37.                 Value* pv = NULL;
    
38.                 for (i = 0; i < 2; i++)
    
39.                 {
    
40.                         CircleList_Next(list);
    
41.                 }
    
42.                 pv = (Value*)CircleList_Current(list);
    
43.                 printf("%d\n", pv->v);
    
44.                 CircleList_DeleteNode(list, (CircleListNode*)pv);
    
45.         }
    
46. 
    
47.         CircleList_Destory(list);
    
48. 
    
49.         system("pause");
    
50.         return 0;
    
51. }

复制代码

完整代码： 循环单链表.zip (2.27 KB, 下载次数: 13)

2018-9-24 11:10 上传

点击文件名下载附件
循环单链表