C语言数据结构——用链表处理约瑟夫问题-创新互联

题目链接如下：
tOpenJudge - 1748:约瑟夫问题

创新互联长期为1000多家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为黄骅企业提供专业的成都网站设计、做网站，黄骅网站改版等技术服务。拥有十多年丰富建站经验和众多成功案例,为您定制开发。

---

问题描述：

约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。

输入输出要求：

输入：需能同时输入多组数据，以0 0结尾标志着结束。

样例输入：6 2  12 4  8 3  0 0

样例输出：5 1 7

解决思路：

1.由于猴子围成了一个圈，故此处使用循环链表的数据结构，将每只猴子看作是一个结点，用序号表示。

//建立结点数据结构 
typedef struct node
{
	int data;
	struct node *next;
}Node,*Link;

for(i=0;idata = i+1;
	tail->next = p;
	p->next = head->next;
	tail = p;
}

2.当猴子报数为m时，将该猴子所表示的结点删除，并将下一个结点（猴子）标号为1，看作是下一趟报数的起点。

if(i==m)
{
	q->next = p->next;
	free(p);
	p = q->next;
	i = 1;//第二趟报数 
}

3.如果不是m号猴子，不改变结点，指针指向下一结点。

代码实现：

#include#include#include//建立结点数据结构 
typedef struct node
{
	int data;
	struct node *next;
}Node,*Link;

int main()
{
	int n,m,count,i;
	//定义头结点head 
	Link head,tail,p,q;
	head = (Link)malloc(sizeof(Node));
	head->next = NULL;
	
	while(1)
	{
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)//结束条件 
		{
			free(head);
			break;
		}
		else
		{
			tail = head;
			for(i=0;idata = i+1;
				tail->next = p;
				p->next = head->next;
				tail = p;
			}
			p = head->next;//p指向第一个结点 
			q = tail;//q指向最后一个结点

            i = 1;
			while(p!=q)//出列 
			{
				if(i==m)
				{
					q->next = p->next;
					free(p);
					p = q->next;
					i = 1;//第二趟报数 
				}
				else//q指针在p指针之前，如果两个指针重合，说明只剩下一个结点 
				{
				    q = p;
					p = p->next;
					i++;	
				} 
			}
			printf("%d\n",p->data);
			free(p); 	 
		}
	}
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文标题：C语言数据结构——用链表处理约瑟夫问题-创新互联
文章转载：http://mswzjz.cn/article/cecedg.html