《数据结构课程设计报告(约瑟夫问题).docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告(约瑟夫问题).docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计报告(约瑟夫问题) 问题描述 约瑟夫问题：编号为1-n的n个人围坐圆桌旁,从任一指定编号为k的人开始报数,报数为m的人离开圆桌,下一个人接着从n开始报数, 报数为m的人又离开圆桌,依此重复,直至所有人离开圆桌.编一程序,输出离开圆桌的人的编号序列. 设计思想 首先采单循环链表建立整个约瑟夫环，手动输入总人数（既链表的长度）、每个人的所持下一轮报数出对值和初始报数值。node-num为人的编号，node-为此人所持的下一轮报数值。建立单循环链表后，通过初始报数值找到出列的人，输出node-num的值，然后将该结点中的data值作为下一轮的报数值。重复以上过程直至所有的人都出列，则
2、程序结束。 主要算法 do k=1; while(k!=m)/当k=m时，结束第一轮报数 p1=p1-next; k+; /报数中将指针指向下一位 p2=p1-next; p1-next=p2-next;/把报数为m的人的结点从链表中删除 printf(编号为%d的人出列，他的key%d作为新的m值/n,p2-num,p2-data);/ m=p2-data;/报数为m的人的密码作为下一轮新的m值 free(p2);/释放报m的人的结点 while(p1-next!=p1);/当p1-指向自己时，报数结束 k为计数器，指针每移动一次，k的值加一，当k=m时，此时p1指向人出列，p2指向该结点的
3、上一结点，让上一结点的next指向该结点的下一结点，然后删除该结点。P1指向该结点下一结点，令k=1，再开始下一轮报数。等到所有人出列后，循环结束。 for(i=1;inext =(listnode*)malloc(sizeof(listnode);/建立一个空间 p1=p1-next ; p1-data=j; p1-num=i;/对结点的num和data成员赋值 p1-next=head-next; 定义指针p1,然后建立一个新结点并将p1-next指向他，再将地址赋给p1，最后将head-next赋给 p1-next,构成了循环单链表，然后让所有人键入链表并给num和data成员赋值。 调
4、试过程 一、输入过程中由于输入法的原因出现很多输入符号无法被编译器识别，导致出现很多 错误。 二、当一轮报数结束时，让该结点的人出列后，忘记释放改结点，导致程序无法继续执 行，重新加入free函数后，释放清空的结点，使程序能正确执行 三、要注意c语言中的输入输出的格式 四、约瑟夫问题并不是十分的复杂，调试过程并不是十分的繁琐 测试过程 测试数据一总人数4 初始报数值2 四个人分别得key为2 2 2 2 出列顺序为2 4 3 1 测试数据二总人数9 初始报数值6 九个人的key分别为3 4 5 3 4 5 3 4 5 出列顺序为6 2 7 1 5 4 3 8 9 经验和体会 数据结构的这次课程
5、设计是十分有意义的，让我巩固了这学期对数据结构这么学科的学习，自己在解决问题的同时，学会了怎样去思考和怎样去摸索，享受了编程过程中的快乐和成功后的喜悦。此次解决的是约瑟夫问题，并不是十分的复杂，但需要有足够的细心和全方面的考虑，通过设计数据的保存和数据的出列检验了对链表的掌握程度，如果对基础知识掌握不好，是无法成功写出程序的。 在编写和调试过程中要有足够的耐心，有特殊到全面，保证程序的各项性能完好，也许你会迷茫，你会不知道错误在哪里，但只要不放弃，最终总能完成程序的编写，并尝到最终的喜悦。 全部源代码 #includestdafx.h #includestdio.h #includestdli
6、b.h #includestring.h typedef struct node int data; int num; struct node *next; listnode; typedef listnode *linklist; void main() int n,m,i,j,k; linklist head=(listnode*)malloc(sizeof(listnode);/开辟一个空间，将其起始地址赋给头指针head listnode *p1,*p2; printf(*请输入总人数：); scanf(%d,&n);/输入总人数 printf(请输入初始报数值：); scanf(%d
7、,&m);/输入初始报数值 if (mnext =(listnode*)malloc(sizeof(listnode);/建立一个空间并将他的地址赋给 p1-next p1=p1-next ; p1-data=j; p1-num=i;/对节点num和data成员赋值 p1-next=head-next;/构成单循环链表 do k=1; while(k!=m)/当k=m时结束一轮报数 p1=p1-next; k+; /报数中将指针p1指向下一位? p2=p1-next; p1-next=p2-next;/把报m的人的节点从链表中删除 printf(编号为%d 的人出列，他的key 作为新的m值n,p2-num,p2-data);/报数为m的人出列 m=p2-data;/报数为m的人的密码作为新的m值 free(p2);/释放报m的人的结点 while(p1-next!=p1);/当p1-next指向自己的地址时，报数结束 printf(编号为 %d 的人出列，所有人出列完毕n,p1-num);/所有人出列完毕 free(p1);/释放最后一个结点 free(head);/释放头结点 char c; c=getchar(); 运行结果 初始画面 输入一组数据，得到运行结果。 非法数据的判断