数据结构之 约瑟夫环

很久以前就想把上个学期上过的数据结构的实验的代码拿上来,可是还是因为种种原因放弃了。

其实网上有很多,可是大部分都是有错误的,不能运行,我就修改了一下。原文地址我都不记得了,大家Google吧。

现在终于重开博客,所以把这些代码分享一下吧。

一、需求分析

1. 以单项循环链表存储结构模拟约瑟夫环问题。即编号为123…nn个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。按出列顺序印出各人编号。
2. 演示程序以用户与计算机的对话方式执行,用户输入相应的数据,输出结果显示在其后。

3.程序所能达到的功能是,输入mn以及每个人的密码,就能输出正确的出列顺序。
4. 测试数据:m初始值20n=77个人密码依次为:317248,4。正确出列顺序为6147235

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio .h>
#include <stdlib .h>
 
typedef struct LNode{
	int data;  // 密码
	int order; // 序号
	struct LNode *next;
}LNode;
 
void main()
{
	struct LNode *head;//head为头指针
	struct LNode *p1,*p2;
 
	int i,j,m,n;
 
	printf("输入人数:\n");//输入人数
	scanf("%d",&n);
 
	//为了简化代码,建表的时候使用一个空的Node作为表头,建好以后删除。
	p1=(struct LNode*)malloc(sizeof(LNode));
	head = p1;
	for(i=1;i< =n;i++)
	{
		p1->next =(struct LNode*)malloc(sizeof(LNode));
		printf("输入第 %d 个人的密码:\n",i);//输入密码
		scanf("%d",&p1->next->data);
		p1->next->order = i;
		p1 = p1->next;
	}
 
	p1->next = head->next; // 首尾相连,此时p1指向链表的尾
 
	//删除空表头
	p2 = head->next;  //此时p2指向链表的头
	delete head;
 
	printf("输入上限:\n");
	scanf("%d",&m);//输入上限
 
	printf("出列顺序:");
	while(p2->next != p2){//当人数大于1个的时候
		for(j=1;j < m;j++)//运行至第m个,因为p2指向的是第1个,所以只要跑m-1次,就指向了第m个
		{
			p1 = p2;
			p2 = p2->next;
		}
		printf(" %d",p2->order); //第m个人出列
 
		m = p2 ->data;
 
		p1 -> next = p2 ->next;//删除第m个结点
		delete p2;
		p2 = p1 ->next;
	}
	printf(" %d\n",p2->order); //输出队列的最后一个人
 
	delete p2; // 清空队列的最后一个
 
}
</stdlib></stdio>

如果需要实验报告,请留下邮箱。当然也要看我心情啦。

>> 若为原创,转载请注明: 转载自Laycher's Blog

>> 本文链接地址: 数据结构之 约瑟夫环

>> 订阅本站: http://feed.feedsky.com/laycher



无觅相关文章插件,快速提升流量

发表评论

电子邮件地址不会被公开。 必填项已用*标注