004-循环单链表
本帖最后由 moc 于 2018-9-24 11:10 编辑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;
}
完整代码：
页:
[1]