数据结构课程设计报告(约瑟夫问题)
- 格式：docx
- 大小：109.86 KB
- 文档页数：6
问题描述
约瑟夫问题：编号为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("输入有错误");//初始报数必须是正数
}
p1=head;//把头指针地址赋给p1
for(i=1;i<=n;i++)
{
printf("请输入%d号同学的key：",i);
scanf("%d",&j);//输入学生所带密码
p1->next =(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();
}
运行结果
初始画面
输入一组数据，得到运行结果。
非法数据的判断
