数据结构 约瑟夫环问题

实验日期：2014.5.14

1.问题描述

设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 2.数据结构设计

首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：

struct Node {

int data; Node *next; };

其次，建立一个不带头结点的循环链表并由头指针first指示。 最后，设计约瑟夫环问题的算法。 3.算法设计

基本要求：人数为n的循环圈，密码m，实现约瑟夫环。 本程序包含3个模块 1）主程序模块 void main() {int m,n;

NODE *first;

printf(\"please input the student number:\"); scanf(\"%d\ //输入人数 printf(\"\\n\");

printf(\"please input the mima:\"); scanf(\"%d\ //输入持有密码

first=init(n); //调用init函数，建立循环链表

yue(first,n,m); //调用yue函数，实现约瑟夫环问题输出出圈次序 }

2）构造链表并输入每个人信息模块 NODE* init(int n) {int i;

NODE *first,*p,*q;

first=(NODE*)malloc(sizeof(NODE)); //建立头结点 first->data=1; //头结点赋值

p=first;

for(i=2;i<=n;i++) //循环建立余下结点并赋值 {q=(NODE*)malloc(sizeof(NODE)); q->data=i; p->next=q; p=p->next;}

p->next=first; //链表首尾相连，建立循环链表

return first; //向主函数返回创建完成的循环链表首节点的地址 }

3）处理出列函数的模块

void yue(NODE*head,int n,int m) {NODE *r,*s,*t; int j; r=head; s=head; while(r)

{for(j=1;jr=r->next;}

printf(\"the student with the number %d is out \ //输出出列序号 printf(\"\\n\");

s->next=r->next; //将出列的结点删除 t=r;

r=r->next; free(t);} }

4.运行、测试与分析

运行程序，从键盘按照提示输入人数15，按回车键，继续输入密码4，按回车键，就会输出程序结果如上。

按照程序，得到n=15,，m=4，调用init函数得到循环链表头指针地址，继续调用yue函数输出结果，正确的输出顺序为：4、8、12、1、6、11、2、9、15、10、5、3、7、14、13.对比可知，程序运行正确。

本程序中，要求m,n均为正整数，若输入其他数据则会导致程序运行错误，无法输出结果。 5.实验收获及思考

1）收获：数据结构是一门比较抽象的学科，但也是一门最基础的课程，在现实生活中也应用的非常广泛。通过设计该实验让我更深刻的掌握了有关链表的知识，同时也认识到了平时学习中的盲点。今后一定会多编程，多思考。在以后还需要不断的完善学习，希望能把数据结构这门课程学习的更加深入、更加透彻。 2）思考：a 若采用顺序结构,则应使first指针始终指向头节点，for循环时，当指针指向最后一个节点后，应使它转至头节点。每删除一个元素后，后面的元素前移，并将删除元素赋值给e，并将其输出。若删除头节点，应将first指针后移。 b 若每个人的密码不同，数据类型可定义两个数据域，一个data域，存放人的编号，一个mima域，存放个人的密码，for循环时，每个人的密码与i相比，若相等，则输出该节点的data域中的编号。

附录

#include #include typedef struct node {int data;

struct node* next;

}NODE;//数据类型定义 NODE* init(int n) {int i;

NODE *first,*p,*q;

first=(NODE*)malloc(sizeof(NODE)); //建立头结点 first->data=1; //头结点赋值 p=first;

for(i=2;i<=n;i++) //循环建立余下结点并赋值 {q=(NODE*)malloc(sizeof(NODE)); q->data=i; p->next=q; p=p->next;}

p->next=first; //链表首尾相连，建立循环链表

return first; //向主函数返回创建完成的循环链表首节点的地址 }//创建链表

void yue(NODE*head,int n,int m) {NODE *r,*s,*t; int j; r=head;

s=head; while(r)

{for(j=1;jr=r->next;}

printf(\"the student with the number %d is out \ //输出出列序号 printf(\"\\n\");

s->next=r->next; //将出列的结点删除 t=r;

r=r->next; free(t);}

}//约瑟夫函数操作 void main() {int m,n;

NODE *first;

printf(\"please input the student number:\"); scanf(\"%d\ //输入人数 printf(\"\\n\");

printf(\"please input the mima:\"); scanf(\"%d\ //输入持有密码

first=init(n); //调用init函数，建立循环链表

yue(first,n,m); //调用yue函数，实现约瑟夫环问题输出出圈次序 }//主函数