004-循环单链表

moc

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

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

void CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
{
        int ret = 0, i = 0;
        TCircleList* tlist = (TCircleList*)list;
        if (tlist == NULL || node == NULL || pos < 0)
        {
                return -1;
        }

        CircleListNode* current = (CircleListNode*)tlist;
        for (i = 0; (i < pos) && (current->next != NULL); i++)
        {
                current = current->next;
        }

        node->next = current->next;  // 1
        current->next = node;  // 2

        // 若第一次插入
        if (tlist->length == 0)
        {
                tlist->slider = node;
        }
        tlist->length++;

        // 若头插法 current仍然指向头部
        //（原因：跳0步，没有跳走仍留在头指针，导致尾部指针指向第二个结点）        
        if (current == (CircleListNode*)tlist)
        {
                CircleListNode* last = CircleList_Get(tlist, tlist->length - 1);
                last->next = current->next;
        }
}

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

循环链表解决方案：

typedef struct _Value
{
        CircleListNode circleNode;
        int v;
}Value;

int main()
{
        int i = 0;
        CircleList* list = CircleList_Create();
        Value v1, v2, v3, v4, v5, v6, v7, v8;
        v1.v = 1;  v2.v = 2;  v3.v = 3;  v4.v = 4;
        v5.v = 5;  v6.v = 6;  v7.v = 7;  v8.v = 8;

        CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
        CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
        CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
        CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
        CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));
        CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));
        CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));
        CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));

        for (i = 0; i < CircleList_Length(list); i++)
        {
                // 获取游标所指的元素，然后游标下移
                Value* pv = (Value*)CircleList_Next(list);
                printf("%d\n", pv->v);
        }
        printf("\n");

        // 重置游标
        CircleList_Reset(list);

        while (CircleList_Length(list) > 0)
        {
                Value* pv = NULL;
                for (i = 0; i < 2; i++)
                {
                        CircleList_Next(list);
                }
                pv = (Value*)CircleList_Current(list);
                printf("%d\n", pv->v);
                CircleList_DeleteNode(list, (CircleListNode*)pv);
        }

        CircleList_Destory(list);

        system("pause");
        return 0;
}

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

2018-9-24 11:10 上传

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