约瑟夫环数据结构上机实验报告

PAGEPAGE3数据结构实验报告题目：约瑟夫环班级：1403041姓名：王超学号成日期：2015.10.31需求分析任务：约瑟夫(Joseph)问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试用链式存储结构存储数据，设计一个程序求出出列顺序。功能要求：利用单向循环链表存储结构模拟约瑟夫环，按照出列的顺序印出各人的编号。测试数据：m的上限为20，初值为20；(1)对于n=7，7个人的密码依次为：3,1,7,2,4,8,4进行测试。(2)对于从键盘输入的n和n个人的密码进行测试。概要设计定义一个循环链表voidincertList(LinkList*list,LinkListq,inte1,inte2)2、定义处理成员的信息的函数voidexJoseph(LinkList*jsp,intm)

3、定义判断输入约瑟夫环voidCreatJoseph(LinkList*jsp,intn)详细设计1）创建循环链表voidincertList(LinkList*list,LinkListq,inte1,inte2){LinkListp;p=(LinkList)malloc(sizeof(LNode));p->number=e1;p->psw=e2;if(!*list){*list=p;p->next=NULL;}else{p->next=q->next;q->next=p;}}2）输入约瑟夫环的数据voidCreatJoseph(LinkList*jsp,intn){LinkListq=NULL,list=NULL;inti,e;printf("请输入密码\n");for(i=0;i<n;i++){scanf("%d",&e);incertList(&list,q,i+1,e);if(i==0)q=list;elseq=q->next;}q->next=list;*jsp=list;}3）处理输出结果voidexJoseph(LinkList*jsp,intm){LinkListp,q;inti;q=p=*jsp;while(q->next!=p)q=q->next;printf("顺序是\n");while(p->next!=p){for(i=0;i<m-1;i++){q=p;p=p->next;}q->next=p->next;printf("%d",p->number);m=p->psw;free(p);p=q->next;}printf("%d\n",p->number);}调试分析在设计过程中，有些函数调用的规范以及算法设计方面多次存在缺陷，多次修改之后，学到了链表循环中数据的处理结构，利用函数方面还需要多调用。五、测试结果附录（源代码）#include<stdio.h>#include<stdlib.h>#include<conio.h>/*链表节点定义*/typedefstructnode{intnumber;/*编号*/intpsw;/*个人密码*/structnode*next;}LNode,*LinkList;voidincertList(LinkList*list,LinkListq,inte1,inte2){LinkListp;p=(LinkList)malloc(sizeof(LNode));p->number=e1;p->psw=e2;if(!*list){*list=p;p->next=NULL;}else{p->next=q->next;q->next=p;}}voidCreatJoseph(LinkList*jsp,intn){LinkListq=NULL,list=NULL;inti,e;printf("请输入密码\n");for(i=0;i<n;i++){scanf("%d",&e);incertList(&list,q,i+1,e);if(i==0)q=list;elseq=q->next;}q->next=list;*jsp=list;}voidexJoseph(LinkList*jsp,intm){LinkListp,q;inti;q=p=*jsp;while(q->next!=p)q=q->next;printf("顺序是\n");while(p->next!=p){for(i=0;i<m-1;i++){q=p;p=p->next;}q->next=p->next;printf("%d",p->number);m=p->psw;free(p);p=q->next;}printf("%d\n",p->number);}intmain(){LinkListjsp;intn,m;