Categories: 算法相关

线性表之“循环单链表”

结构:

在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可。

循环单链表的优点在于通过任意一个节点可以遍历整个表的所有节点,而单链表只能遍历该节点之后的节点,在他之前的节点是不能遍历的。

举例:

约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

约瑟夫环问题我们就可以通过循环单链表的方式求出答案。代码如下:

下载地址:https://github.com/gongjiehong/ListNode/archive/master.zip

[code lang=”C”]// MARK: 循环单链表

LinkList create_circle_list(int length);

/**
* @author 龚杰洪, 16-08-05 14:08:21
*
* 约瑟夫环: 已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
*
* @param head 链表的头指针
* @param k 开始报数的编号
* @param m 每次报数的数字 m > 1
*
* @return 最后那个没有被out的
*
* @since 1.0
*/
DataType josephus(LinkList head, int k, int m);
[/code]

[code lang=”C”]// MARK: 循环单链表
LinkList create_circle_list(int length)
{
ListNode *p = NULL, *head = NULL, *q = NULL;
for (int index = 1; index <= length; index ++)
{
if (index == 1)
{
// 初始化头指针并赋值
head = (LinkList)malloc(sizeof(ListNode));
head->data = index;
head->next = NULL;
// 赋值为头指针
p = head;
}
else
{
// 出事化后续的节点并赋值
q = (LinkList)malloc(sizeof(ListNode));
q->data = index;
q->next = NULL;
// next指向后续的节点
p->next = q;
// 指针更换为下一节点的指针
p = q;
}
}
// 尾节点的指针指向头指针
if (p->next == NULL)
{
p->next = head;
}
return head;
}

DataType josephus(LinkList head, int k, int m)
{
ListNode *p = head, *q = NULL;
int i;

// 找到开始报数的那个人
while (p->data != k) {
p = p->next;
}

// 如果不是空表的时候执行循环,剩下的那个为幸存者
while (p->next != p)
{
for (i = 0; i < m – 1; i++)
{
// q为临时缓存
q = p;
// 往下一个报数
p = p->next;
}
// p = p->next的替换
q->next = p->next;

printf("%3d out.\n", p->data);
free(p);
// 释放以后将后一个指针前移
p = q->next;
}
return p->data;
}
[/code]

[code lang=”C”]
int n, k, m;
printf("请输入链表的长度:\n");
scanf("%d",&n);

ListNode *p = create_circle_list(n);

printf("请输入开始报数的标号:\n");
scanf("%d",&k);

printf("请输入出列的数:\n");
scanf("%d",&m);

printf("最后没被out的那个: %d \n", josephus(p, k, m));

[/code]

龚杰洪

Share
Published by
龚杰洪

Recent Posts

GOLANG面试八股文-并发控制

背景 协程A执行过程中需要创建…

1 年 ago

MYSQL面试八股文-常见面试问题和答案整理二

索引B+树的理解和坑 MYSQ…

1 年 ago

MYSQL面试八股文-InnoDB的MVCC实现机制

背景 什么是MVCC? MVC…

1 年 ago

MYSQL面试八股文-索引类型和使用相关总结

什么是索引? 索引是一种用于加…

1 年 ago

MYSQL面试八股文-索引优化之全文索引(解决文本搜索问题)

背景:为什么要有全文索引 在当…

1 年 ago