1、数据结构课程设计试验报告 数据结构课程设计实验报告题 目 约瑟夫问题和八皇后问题求解 学 院 数学与信息工程学院 专 业 计算机科学与技术 班 级 计科081 学 号 200853225142 学生姓名 陈哲 同组成员 魏艳舞 杨青 施晓洁 吴亚君 徐珍艳 张素姿指导教师 刘小晶 编写日期 2009年6月28日 一、问题描述 1、约瑟夫问题描述 编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1
2、报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 2、八皇后问题描述在一个的棋盘里放置个皇后，要求每个皇后两两之间不相冲（在每一横列竖列斜列只有一个皇后）。3、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。二、问题分析本人负责的是为用户设计菜单界面，使用户可以根据菜单进行选择其中的某个问题进行处理。对于一个菜单界面，首先要求界面简单明了，使得用户可以轻松通过界面知道如何获取自己想要的操作。其次，我们不能保证用户每次的选择都是有效的，即用户的选择是在
3、我们提供的服务范围之内，所以要设计容错操作，即当用户的选择超出我们提供的范围时，提示用户重新选择。最后，要保证用户选择相应的操作后，程序能正确的按照用户的选择运行下去，完成用户的要求。三、数据结构描述 Int choice; 记录用户的选择，然后选择相应的操作。 typedef struct LNode int num; int code; struct LNode *next; node,*linklist; 单链表解决约瑟夫问题时储存结点信息char a99; 八皇后问题中记录棋盘信息四、算法设计1、程序层次模块图 程序总层次模块图2、算法设计void jiemian() printf(
4、the problem of people our of circlrn); printf( *n); printf( * 1.solve by lianbiao; *n); printf( * 2.solve by shunxubiao; *n); printf( * 3.help; *n); printf( * 4.ruturn to menu; *n); printf( *n); void help() printf( the problem of people our of circlrn); printf(*n); printf(* you can choise 1,2,3 or 4
5、 to get the function you want.if you choise 1, *n); printf(* you will solve the problem by lianbiao.in this way,when a people out of *n); printf(* the circle,the node which contain his message will be deleted.if you *n); printf(* choise 2,you will solve the problem by shunxubiao.in this way,when a *
6、n); printf(* people out of the circle,his code will change into 0,but his message *n); printf(* will be remained.if you choise 4,end the game. *n); printf(*n);void welcome() printf( welcome to our systemn); printf( *n); printf( * 1.Joseph Central issues *n); printf( * 2.Queen 8 *n); printf( * 3.exit
7、 *n); printf( *n); int main() int choice; welcome(); printf( please make your choice:); scanf(%d,&choice); while(choice!=3) switch(choice) case 1:system(cls);Joseph();getch();break; case 2:system(cls);Queen();getch();getch();break; default:printf( please chooose the right choice!);getch();getch();br
8、eak; system(cls); welcome(); printf( please make your choice:); scanf(%d,&choice); 五、详细程序清单#include#includetypedef struct LNode int num; int code; struct LNode *next; node,*linklist; /数据结构声明char a99;int total;linklist creatstart(linklist L,int number) /建立单向循环链表 int m,i; linklist s,p; s=L; for(i=1;in
9、um=i; printf(please input the code of number %d:,i); scanf(%d,&p-code); p-next=NULL; s-next=p; s=p; s-next=L-next; return s;void chulie(linklist L,int number) /链表中的出列 int turn,i,j; linklist p,s; printf(please input the start code:); scanf(%d,&turn); p=L; printf(the turn out of the circle is:); for(i
10、=1;i=number-1;i+) for(j=1;jnext; printf(%d ,p-next-num); turn=p-next-code; s=p-next; p-next=s-next; free(s); printf(%d ,p-next-num); printf(n);void lianbiao() /用单向循环链表解决约瑟夫问题 int number; linklist L; L=(linklist)malloc(sizeof(node); if(!L) exit(0); printf(please input the number of people:); scanf(%d
11、,&number); L=creatstart(L,number); chulie(L,number);void jiemian() /约瑟夫问题的界面 printf( the problem of people our of circlrn); printf( *n); printf( * 1.solve by lianbiao; *n); printf( * 2.solve by shunxubiao; *n); printf( * 3.help; *n); printf( * 4.ruturn to menu; *n); printf( *n); void shunxubiao() /用
12、顺序表解决约瑟夫问题 int a500=0,i,code,number,shu; printf(please input the number of people:); scanf(%d,&number); shu=number; for(i=1;i0) while(code0) if(i+1number) i=0; if(ai+1!=0) code-; i+; printf(%d ,i); code=ai; ai=0; shu-; printf(n);void help() /帮助文档 printf( the problem of people our of circlrn); printf
13、(*n); printf(* you can choise 1,2,3 or 4 to get the function you want.if you choise 1, *n); printf(* you will solve the problem by lianbiao.in this way,when a people out of *n); printf(* the circle,the node which contain his message will be deleted.if you *n); printf(* choise 2,you will solve the pr
14、oblem by shunxubiao.in this way,when a *n); printf(* people out of the circle,his code will change into 0,but his message *n); printf(* will be remained.if you choise 4,end the game. *n); printf(*n);void Joseph() /约瑟夫问题 int choice; jiemian(); printf( please make your choice:); scanf(%d,&choice); whi
15、le(choice!=4) switch(choice) case 1:lianbiao();getch();getch();break; case 2:shunxubiao();getch();getch();break; case 3:system(cls);help();getch();getch();break; default:printf( please chooose the right choice!);getch();getch();break; system(cls); jiemian(); printf( please make your choice:); scanf(
16、%d,&choice); void init() /八皇后问题棋盘初始化 int i,j; for(i=1;i=8;i+) for(j=1;j=8;j+) aij=*;void shuchu() /输出可行解 int i,j; for(i=1;i=8;i+) for(j=1;j=8;j+) printf(%c ,aij); printf(n); printf(n);void digui(int hang) /递归解决八皇后问题 int lie; for(lie=1;lie=8;lie+) if(panduan(hang,lie) ahanglie=; if(hang!=8) digui(han
17、g+1); else shuchu(); total+; ahanglie=*; int panduan(int hang,int lie) /判断能否放置皇后 int i,j; for(i=1;ihang;i+) if(ailie=) return 0; for(i=1;i0)&(j-10) if(ai-1j-1=) return 0; i-; j-; i=hang; j=lie; while(i-10)&(j+1=8) if(ai-1j+1=) return 0; i-; j+; return 1;void Queen() /八皇后问题 digui(1); printf(the total
18、 possibility is:%dn,total);void welcome() /主程序界面 printf( welcome to our systemn); printf( *n); printf( * 1.Joseph Central issues *n); printf( * 2.Queen 8 *n); printf( * 3.exit *n); printf( *n); int main() /主函数 int choice; welcome(); printf( please make your choice:); scanf(%d,&choice); while(choice!
19、=3) switch(choice) case 1:system(cls);Joseph();getch();break; case 2:system(cls);Queen();getch();getch();break; default:printf( please chooose the right choice!);getch();getch();break; system(cls); welcome(); printf( please make your choice:); scanf(%d,&choice); 六、程序运行结果七、使用说明用户进入主界面后根据菜单内容选择1、2、3分别可进行约瑟夫问题、八皇后问题、退出系统操作。进入约瑟夫问题后按照菜单选择1、2、3、4分别可进行链表求解、顺序表求解、查看帮助文档、回到主菜单操作。进入八皇后问题系统即可输出所有的可能解，并计算解的数目。八、心得体会 良好的界面不仅能反映出程序的主题结构，让用户了解系统的答大体功能，同时可以极大地方便用户随系统的了解与使用，增加用户与系统的交互性。
