数据结构课程设计报告（约瑟夫问题）.docx

问题描述 约瑟夫问题：编号为1-n的n个人围坐圆桌旁,从任一指定编号为k的人开始报数,报数为m的人离开圆桌,下一个人接着从n开始报数, 报数为m的人又离开圆桌,依此重复,直至所有人离开圆桌.编一程序,输出离开圆桌的人的编号序列. 设计思想 首先采单循环链表建立整个约瑟夫环，手动输入总人数（既链表的长度）、每个人的所持下一轮报数出对值和初始报数值。node-num为人的编号，node-为此人所持的下一轮报数值。建立单循环链表后，通过初始报数值找到出列的人，输出node-num的值，然后将该结点中的data值作为下一轮的报数值。重复以上过程直至所有的人都出列，则程序结束。 主要算法 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指向该结点的上一结点，让上一结点的next指向该结点的下一结点，然后删除该结点。P1指向该结点下一结点，令k=1，再开始下一轮报数。等到所有人出列后，循环结束。 for(i=1;i=n;i++) { printf(请输入%d号同学的key,i); scanf(%d,j);//输入学生所带有的密码 p1-next =(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成员赋值。 调试过程 输入过程中由于输入法的原因出现很多输入符号无法被编译器识别，导致出现很多错误。 当一轮报数结束时，让该结点的人出列后，忘记释放改结点，导致程序无法继续执行，重新加入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 经验和体会 数据结构的这次课程设计是十分有意义的，让我巩固了这学期对数据结构这么学科的学习，自己在解决问题的同时，学会了怎样去思考和怎样去摸索，享受了编程过程中的快乐和成功后的喜悦。此次解决的是约瑟夫问题，并不是十分的复杂，但需要有足够的细心和全方面的考虑，通过设计数据的保存和数据的出列检验了对链表的掌握程度，如果对基础知识掌握不好，是无法成功写出程序的。 在编写和调试过程中要有足够的耐心，有特殊到全面，保证程序的各项性能完好，也许你会迷茫，你会不知道错误在哪里，但只要不放弃，最终总能完成程序的编写，并尝到最终的喜悦。 全部源代码 #include stdafx.h #include stdio.h #include stdlib.h #include string.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,m);//输入初始报数值 if (m=0) { printf