约瑟夫环与八皇后问题-数据结构课程设计实验报告

目录一、 问题描述 1二、 问题分析 1三、 数据结构描述 1四、 算法设计 2五、 详细程序清单 4六、 程序运行结果 11七、 心得体会 12问题描述1.约瑟夫问题描述编号为1，2…n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。2.八皇后问题描述在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。3、界面设计模块问题描述设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。问题分析在整个课程设计中，我主要负责的是约瑟夫问题中链表中的出列的操作算法的设计。用循环单链表表示编号为1，2…n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始输入一个正整数作为报数的上限值turn，从第一个人开始按顺时针方向自1开始顺序报数（即从第一个结点开始指针向后移动），报到turn-1时（即指针指向turn-1个结点时）停止，他的下一位出列，将他的下一位密码作为新的turn值，从出列的人的的顺时针方向上的下一个开始重新从1报数，如此下去，直至链表中只剩一位（即一个结点）退出循环，并所有人的编号按出列顺序输出。在实现的过程中定义i表示报数的循环次数，因为每次循环都会有一个人出列且只剩一个人时结束循环，所以i<=number-1。定义j表示所报的数，在j等于turn（报数上限）-1之前随着报数的进行，把指向头结点的指针p随着j增加的方向依次后移。当j等于turn-1时，让p所指向结点的下一位出列。用指针s表示要出列的人的结点，则出列后删除结点s（即free（s））。按出列的顺序输出出列人的编号。数据结构描述typedefstructLNode{intdata;intcode;structLNode*next;}node,*linklist;//单链表解决约瑟夫问题时储存结点信息在单循环链表中进行出列的操作，方便、快捷、易理解。链表中的结点及其指针域、数值域之间的联系与各种赋值与转换使得出列操作的思路变得清晰简单。算法设计我负责的是约瑟夫问题中链表中的出列的操作算法。算法流程图开始开始输入开始的报数上限turn循环次数i为1否结束指针p指向链表头结点i是否小于等于人数-1j是否小于等于turn-1报数j从1开始是指针后移否报数+1报数上限变成p的下一个结点的密码，并删除p的下一个结点循环次数i加1输出p的下一个结点的值输出p的下一个结点的值是2.具体算法设计voidchulie(linklistL,intnumber){ intturn,i,j; linklistp,s; printf("pleaseinputthestartcode:"); scanf("%d",&turn); p=L; printf("theturnoutofthecircleis:"); for(i=1;i<=number-1;i++) { for(j=1;j<=turn-1;j++)p=p->next; printf("%d",p->next->data); turn=p->next->code; s=p->next; p->next=s->next; free(s); } printf("%d",p->next->data); printf("\n");}详细程序清单#include<stdio.h>#include<conio.h>#include<malloc.h>//八皇后问题intcount;intm,n;inta[8];intb[15];intc[15];intd[8][8];intcheck(inti,intj);voidputchess(inti);voidtakeposition(inti,intj);voidleaveposition(inti,intj);voidshow(void);voidQueenstart(void){count=0;for(m=0;m<8;m++){a[m]=0;for(n=0;n<8;n++){d[m][n]=0;}}for(m=0;m<15;m++){b[m]=0;c[m]=0;}}voidputchess(inti){intj;if(i<8){for(j=1;j<=8;j++){if(1==check(i,j)){takeposition(i,j);putchess(i+1);leaveposition(i,j);}}}elseif(8==i){for(j=1;j<=8;j++){if(1==check(i,j)){takeposition(i,j);show();leaveposition(i,j);}}}}intcheck(inti,intj){if(0==a[j-1]&&0==b[i+j-2]&&0==c[i-j+7]){return1;}else{return0;}}voidtakeposition(inti,intj){a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;d[i-1][j-1]=1;}voidleaveposition(inti,intj){a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;d[i-1][j-1]=0;}voidshow(){count++;printf("%d\n",count);for(m=0;m<8;m++){for(n=0;n<8;n++){if(0==d[m][n])printf("*");elseprintf("@");}printf("\n");}printf("\n");}//约瑟夫环问题typedefstructLNode{intdata;intcode;structLNode*next;}node,*linklist;linklistcreatstart(linklistL,intnumber){intm,i;linklists,p; s=L; for(i=1;i<=number;i++) { p=(linklist)malloc(sizeof(node)); if(!p)exit(0); p->data=i;printf("pleaseinputthecodeofnumber%d:",i);scanf("%d",&p->code);p->next=NULL; s->next=p;s=p; }s->next=L->next;returns;}voidchulie(linklistL,intnumber){ intturn,i,j; linklistp,s; printf("pleaseinputthestartcode:"); scanf("%d",&turn); p=L; printf("theturnoutofthecircleis:"); for(i=1;i<=number-1;i++) { for(j=1;j<=turn-1;j++)p=p->next; printf("%d",p->next->data); turn=p->next->code; s=p->next; p->next=s->next; free(s); } printf("%d",p->next->data); printf("\n");}voidlianbiao(){intnumber; linklistL; L=(linklist)malloc(sizeof(node)); if(!L)exit(0); printf("pleaseinputthenumberofpeople:"); scanf("%d",&number); L=creatstart(L,number); chulie(L,number);}/*主菜单*/voidmenu(){ printf("欢迎登入界面！\n");printf("****************************************************\n"); printf("*1.约瑟夫环问题*\n"); printf("*2.八皇后问题运行结果*\n"); printf("*3.退出*\n"); printf("****************************************************\n");}/*Main：主函数。*/voidmain(){ intchoice; menu(); printf("pleasemakeyourchoice:"); scanf("%d",&choice); while(choice) { switch(choice) { case1:printf("约瑟夫环问题开始！");lianbiao();getch();break; case2:printf("八皇后问题运行结果如下：");get