数据结构_约瑟夫环
题目:编制一个约瑟夫环的程序
一、 需求分析
1. 本程序中,以循环链表储存个人号码和密码。人数上限为105, 。
2. 程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入相应数据,结果在之后显示。
3. 程序执行的命令包括:
1)构造循环链表 2)计算约瑟夫环 3)打印结果
4. 测试数据
人数:7 报数上限:20
个人密码:3,1,7,2,4,8,4
首个密码:6
输出顺序:6,1,4,7,2,3, 5
二、 概要设计
1. 链表的抽象数据类型定义:
ADT link{
数据对象:D={ai|ai∈CharSet.i=1,2,3„,n>=0}
数据关系:R1={|ai-1,ai∈D,ai-1
Data* creat_link(Data**head,int m,int limit)
操作结果:构建一个大小为m ,包含用户输入的信息的链表,
返回头指针前一个节点的指针。
void do_huan(Data*p1,int m)
初始条件:循环链表P1存在。
操作结果:计算约瑟夫环,把出环的顺序存入arr 数组中。 Data* del(Data*p)
初始条件:循环链表P 存在。
操作结果:删除节点P 的下一节点。
}
2. 本程序包含三个模块:
1)主程序部分:
2)构建循环链表
3)计算约瑟夫环
4)打印出环顺序
三、 详细设计
typedef struct data
{
int num; int code; struct data * next;
}Data; //元素类型
int arr[105]={0}; //储存出环顺序
int now=0; 记入目前出环个数
//构建循环链表
Data* creat_link(Data**head,int m,int limit)
{
Data*p1,*p2;
int n,i;
printf("code:");
for(i=0;i
{
p1=(Data*)malloc(sizeof(Data)); if(0==i) { } else { } p2->next=p1; p2=p1; *head=p1; p2=p1;
} scanf("%d",&n); while(n>limit||ncode=n; printf("wrong"); scanf("%d",&n);
p1->next=*head;
return p1;
}
//计算约瑟夫环
void do_huan(Data*p1,int m)
{
int n,i,j;
printf("first code:");
scanf("%d",&n);
for(i=0;i
{
for(j=0;j
}
}
n=p1->next->code; p1=del(p1);
//删除下个节点
Data * del(Data*p)
{
Data * temp;
temp=p->next;
p->next=temp->next;
arr[now]=temp->num;
now++;
free(temp);
return p;
}
//主程序
int main()
{
Data *head,*p1;
int i,j,n,m,limit; // m:number of poeple n:code
printf("number of poeple limit");
scanf("%d %d",&m,&limit);
p1=creat_link(&head,m,limit);
do_huan(p1,m);
for(i=0;i
printf("%d ",arr[i]);
printf("\n");
return 0;
}
四、 调试分析
1, 删除节点时,是找到它的前一个节点,再进行删除操作。故传入节点指针给计算约瑟夫环的指针因为首节点的前一个节点指针,即记入最后一个人的最后一个的节点指针。在最初编程时欠缺考虑,造成错误。
2, 程序编译不过的原因大多是函数声明与定义的参数类型不匹配,时不细心造成的。
感想与体会
1) 巩固和加深了对数据结构的理解,提高综合运用链表的能力。
2) 上课要好好听课,认真理解老师所讲的内容,平时多编程,
锻炼自己的编程能力,和应用知识的能力。
3) 写程序时要细心,切记心浮气躁,要考虑全面。
算法的时空分析:
时间大部分是在移动指针,寻找下个出环的人,移动位数为密码少一位。在最坏情况下,移动位数是最大密码值少一位,(最大密码值为m n 为人数),故总移动的位数为(m-1)n. 则耗时o (n*m)
五、 用户手册
1. 执行文件为链表_约瑟夫环.exe
2. 运行程序后 按程序要求输入 人数 报数的最大上限
人数从1开始的密码
3. 按回车键即可得到测试结果。
4. 本程序的输入输出只进行一次,即只做一个案例的处理,如果用户要输入第二个案例,则需要退出并再运行本程序。
六、 测试结果
输入people of number linmit 7 20
Code 3 1 7 2 4 8 4
Fisrt code 6
输出结果:6 1 4 7 2 3 5