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

1、问题描述 约瑟夫问题：编号为1-n的n个人围坐圆桌旁,从任一指定编号为k的人开始报数,报数为m的人离开圆桌,下一个人接着从n开始报数, 报数为m的人又离开圆桌,依此重复,直至所有人离开圆桌.编一程序,输出离开圆桌的人的编号序列.设计思想首先采单循环链表建立整个约瑟夫环，手动输入总人数（既链表的长度）、每个人的所持下一轮报数出对值和初始报数值。node->num为人的编号，node->为此人所持的下一轮报数值。建立单循环链表后，通过初始报数值找到出列的人，输出node->num的值，然后将该结点中的data值作为下一轮的报数值。重复以上过程直至所有的人都出列，则程序结束。主要算

2、法dok=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的

3、值加一，当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;/对结点的n

4、um和data成员赋值p1->next=head->next;定义指针p1,然后建立一个新结点并将p1->next指向他，再将地址赋给p1，最后将head->next赋给p1->next,构成了循环单链表，然后让所有人键入链表并给num和data成员赋值。调试过程一、 输入过程中由于输入法的原因出现很多输入符号无法被编译器识别，导致出现很多错误。二、 当一轮报数结束时，让该结点的人出列后，忘记释放改结点，导致程序无法继续执行，重新加入free函数后，释放清空的结点，使程序能正确执行三、 要注意c语言中的输入输出的格式四、 约瑟夫问题并不是十分的复杂，调试过程并不是

5、十分的繁琐测试过程测试数据一 总人数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经验和体会数据结构的这次课程设计是十分有意义的，让我巩固了这学期对数据结构这么学科的学习，自己在解决问题的同时，学会了怎样去思考和怎样去摸索，享受了编程过程中的快乐和成功后的喜悦。此次解决的是约瑟夫问题，并不是十分的复杂，但需要有足够的细心和全方面的考虑，通过设计数据的保存和数据的出列检验了对链表的掌握程度，如果对基础知识掌握不好，是无法成功写出

6、程序的。在编写和调试过程中要有足够的耐心，有特殊到全面，保证程序的各项性能完好，也许你会迷茫，你会不知道错误在哪里，但只要不放弃，最终总能完成程序的编写，并尝到最终的喜悦。全部源代码#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;

7、void main()int n,m,i,j,k;linklist head=(listnode*)malloc(sizeof(listnode);/开辟一个空间，将其起始地址赋给头指针headlistnode *p1,*p2;printf("*请输入总人数：");scanf("%d",&n);/输入总人数printf("请输入初始报数值：");scanf("%d",&m);/输入初始报数值if (m<=0)printf("输入有错误");/初始报数必须是正数p1=head

8、;/把头指针地址赋给p1for(i=1;i<=n;i+)printf("请输入%d号同学的key：",i);scanf("%d",&j);/输入学生所带密码p1->next =(listnode*)malloc(sizeof(listnode);/建立一个空间并将他的地址赋给p1->nextp1=p1->next ;p1->data=j;p1->num=i;/对节点num和data成员赋值p1->next=head->next;/构成单循环链表dok=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("