joseph环—数据结构课程设计报告.doc

《joseph环—数据结构课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、joseph环一.需求分析：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。1.输入的形式和输入值的范围  本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。2.输出的形式  从屏幕显示出列顺序。3.程序功能  提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。二、  概要设计以单向循环链表实现该结构。1.抽象数据类型的定义为：ADTLN

2、ode{  数据对象：D={ai

3、ai∈CharSet，i=1，2，…，n，n≥0}  数据关系：R1={<ai-1，ai>

4、ai∈D，I=2，…，n}三．源程序：#include#includetypedefstructNode{intkey;//每个人持有的密码intnum;//这个人的编号structNode*next;//指向下一个节点}Node,*Link;voidInitList(Link&L)//创建一个空的链表{L=(Node*)malloc(siz

5、eof(Node));if(!L)exit(1);L->key=0;L->num=0;L->next=L;}voidCreater(intn,Link&L)//初始化链表{Linkp,q;q=L;for(inti=1;i<=n;i++){p=(Node*)malloc(sizeof(Node));if(!p)exit(1);printf("thekey_%dis:",i);scanf("%d",&p->key);p->num=i;L->next=p;L=p;}L->next=q->next;free(q);}voi

6、dmain()//主函数{LinkL,p,q;intn,x;L=NULL;InitList(L);//构造出一个只有头结点的空链表printf("pleaseinputthetotlenumberofpeople:");scanf("%d",&n);//总共的人数nprintf("thestartkeyis:");scanf("%d",&x);//初始密码为xCreater(n,L);//建立好一个约瑟夫环p=L;for(inti=1;i<=n;i++){for(intj=1;jnext;q

7、=p->next;x=q->key;printf("%d",q->num);p->next=q->next;free(q);}}四、测试数据：m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4输出：6741532