很久以前就想把上个学期上过的数据结构的实验的代码拿上来,可是还是因为种种原因放弃了。
其实网上有很多,可是大部分都是有错误的,不能运行,我就修改了一下。原文地址我都不记得了,大家Google吧。
现在终于重开博客,所以把这些代码分享一下吧。
一、需求分析
1. 以单项循环链表存储结构模拟约瑟夫环问题。即编号为1、2、3…、n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。按出列顺序印出各人编号。
2. 演示程序以用户与计算机的对话方式执行,用户输入相应的数据,输出结果显示在其后。
3.程序所能达到的功能是,输入m和n以及每个人的密码,就能输出正确的出列顺序。
4. 测试数据:m初始值20,n=7,7个人密码依次为:3,1,7,2,4,8,4。正确出列顺序为6,1,4,7,2,3,5。
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
#include
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; // 清空队列的最后一个
}
|
如果需要实验报告,请留下邮箱。当然也要看我心情啦。