南昌航空大学实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
课程名称:数据结构实验名称:实验二线性表的链式存储结构
班级:学生姓名:冯华华学号:11046213 指导教师评定: XXX 签名: XXX
一、问题描述
1单链表的实现与操作。
2
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
一个程序求出约瑟夫环的出列顺序。约瑟夫问题的一种描述是:编号为1,2,…,
n的n个人按顺时针方向围坐一圈,每个人持有一个密码(正整数)。一开始任选一个正整
数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。
报m的人出列,将他的密码作为新的m 值,从他在顺时针方向上的下一个人开始重新从1
报数,如此下去,直到所有人全部出列为止。例如,n=7,7个人的密码依次为:
3,1,7,2,4,8,4,m的初值取6,则正确的出列顺序应为6,1,4,7,2,3,5。要求使用单向循环
链表模拟此出列过程。
二、程序分析
约瑟夫环的大小是变化的,因此相应的结点也是变化的,使用链式存储结构可以动态的
生成其中的结点,出列操作也非常简单。用单向循环链表模拟其出列顺序比较合适。
用结构指针描述每个人:
struct Joseph
{int num;/*环中某个人的序号*/
int secret;/环中某个人的密码*/
struct Joseph *next;/指向其下一个的指针*/};
1)初始化约瑟夫环:
调用
函
关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函
数struct Joseph *creat()生成初始约瑟夫环。在该函数中使用head 指向
表头。输入序号为0时结束,指针p1指向的最后结束序号为0的结点没有加入到
链表中,p2 指向最后一个序号为非0 的结点(最后一个结点)。
2)报数出列:
调用函数voil sort(struct Joseph * head,int m),使用条件p1->next!=p1判断
单向链表非空,使用两个指针变量p1和p2,语句p2=p1;p1=p1->next;移动指针,
计算结点数(报数);结点p1出列时直接使用语句:p2->next=p1->next,取出该
结点中的密码作为新的循环终值。
三、调试过程及实验结果
最后程序运行结果如下所示:
输入数据:数据格式为序号,密码
输入0,0为结束
1,3↙<回车>
2,1↙<回车>
3,7↙<回车>
4,2↙<回车>
5,4↙<回车>
6,8↙<回车>
7,4↙<回车>
0,0↙<回车>
输入m值
6↙<回车>
出列的序号是
6→1→4→7→2→3→5
四、附录
源程序文件清单:
该程序的源代码如下:
#define NULL 0
#define LENGTH sizeof(struct Joseph)
#include
#include
struct Joseph
{
int num;
int secret;
struct Joseph *next;
};/*定义结点num为序号,secret为密码*/
/*创建初始链表函数*/
struct Joseph *creat()
{
struct Joseph *head;
struct Joseph *p1,*p2;
int n=0;
p1=p2=(struct Joseph *)malloc(LENGTH);
scanf("%d,%d",&p1->num,&p1->secret);
head=NULL;
while(p1->num!=0)
{
n=n+1;
if(n==1)
{
head=p1;
}
else p2->next=p1;
p2=p1;
p1=(struct Joseph *)malloc(LENGTH);
scanf("%d,%d",&p1->num,&p1->secret);
p2->next=head;
return(head);
}
}
/*报数出列*/
void sort(struct Joseph * head,int m)
{
struct Joseph *p1,*p2;
int i;
if(head==NULL)
printf("\n链表为空!\n");
p1=head;
while(p1->next!=p1)
{
for(i=1;inext;
}
p2->next=p1->next;
m=p1->secret;
printf("%d ",p1->num);
p1=p2->next;
if(p1->next==p1)
{
printf("%d ",p1->num);
}
}
}
int main()
{
struct Joseph *head;
int m;
printf("\n输入数据:数据格式为序号,密码\n输入0,0为结束\n");
head=creat();
printf("输入 m值\n");
scanf("%d",&m);
if(m<1)printf("error! 请输入一个合法的 m值!");
printf("出列的序号是:\n");
sort(head,m);
}
浙公网安备 33021202002483