第一篇：题目：约瑟夫环问题
数据结构上机实验报告
02090401 12 雒文杰 题目：约瑟夫环问题
一．问题描述
设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设计确定他们的出列次序序列的程序。
二．基本要求
运用循环单链表解决约瑟夫环问题。
三．算法说明
本程序采用循环单链表的算法来解决约瑟夫环问题：建立一个循环单链表，按顺序查找指定结点，找到后删除，最后打印删除的编号序列。
四 ．源程序清单 #include
/* 人的序号, 密码*/ struct clist *next;
/* 指向下一个节点的指针 */ };typedef struct clist cnode;typedef cnode *clink;clink createclist(int *array,int len)
/* 建立循环链表 */ {clink head;clink before;clink new_node;int i;head=(clink)malloc(sizeof(cnode));if(!head)return NULL;head->data=array[0];head->order=1;head->next=NULL;before=head;for(i=1;i if(!new_node) return NULL; new_node->data=array[i]; new_node->order=i+1; new_node->next=NULL; before->next=new_node; before=new_node;} new_node->next=head;return head;} void main(){clink head,ptr;int find,j,i,a,list[n];printf(“Please input 'm'n”);for(i=0;i printf(“n”);} head=createclist(list,n);printf(“input first 's'n”);scanf(“%d”,&a);for(i=1;i head=head->next; ptr=head->next; head->next=ptr->next; find=ptr->data; printf(“order is %dn”,ptr->order); free(ptr); /* 让最后一个人也出列 */ } } 《数据结构》 课程设计报告 课程名称： 课程设计题目：姓名： 院系： 专业： 年级： 学号： 指导教师： 《数据结构》课程设计 joseph环 计算机学院 2011年12月18日 目 录 课程设计的目的………………………………………………………………2 2 需求分析………………………………………………………………………2 3 课程设计报告内容……………………………………………………………3 1、概要设计……………………………………………………………………3 2、详细设计……………………………………………………………………3 3、调试分析……………………………………………………………………x 4、用户手册……………………………………………………………………x 5、测试结果……………………………………………………………………6 6、程序清单……………………………………………………………………7 4 小结 …………………………………………………………………………10 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列 3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; //顺序 int code; //密码 LinkNode *next; };建立一个类LinkList ,包含的函数： LinkList(); //构造函数 void Creat(const int); //创建循环链表 int Delete(LinkNode*); //删除报到数的结点 int Joseph(int); // 约瑟夫环 私有成员是 LinkNode* head; //指向第一个结点的指针 LinkNode* elem; // 同上 int len; //长度 我定义了一个elem指针是为了约瑟夫环里运行方便，elem只在约瑟夫环这个函数里用到，其他函数没有特别大的用处。 构造函数与书上的没什么大差别，创建循环链表时，要考虑几个问题，一个是题目要求是不带头结点，所以head指针直接指向了第一个结点，我在创建链表时把第一个结点初始化data为1，表明这个结点是第一个结点。具体如下： void LinkList::Creat(const int number) //number为结点个数，也就是参与的人数 { if(number==1) //只有一个人的情况 { head=elem=new LinkNode; head->data=1; cout<<“请输入密码:”< cin>>head->code; head->next=head;} else { head=elem=new LinkNode; head->data=1; cout<<“请依次输入各个密码:”< cin>>head->code;LinkNode*q=head; q=head; for(int i=1;i //将每个结点链接上，在链接时填入密码 { LinkNode*p=new LinkNode; p->data=i+1; cin>>p->code; q->next=p; q=p;} q->next=head; //构成循环链表 } len=number;} 在构建约瑟夫环的执行函数时，我首先考虑了递归调用的函数，原本的这个程序的所有的都定为elemtype类型的，虽然编译没出错，但是在连接时发生了错误，在老师的指导下改成了具体的int型。int LinkList::Joseph(int m){ if(len>1){ LinkNode *q;if(m==1) //在初始报数为1的情况下 { q=elem;int a=q->code; //将选中的结点的密码记录在a中 elem=elem->next;cout< //用已经删除的结点的存的密码作为下一次循环的报数值 } else //一般情况下 { for(int i=1;i elem=elem->next;//找到需要出列的结点 q=elem;elem=elem->next; //此处的elem指针指向要删除的结点的下一个结点，下 次递归调用时从这里开始向下循环报数 int a=q->code; cout< //在只有一个结点的情况下 cout< 最后还有一个Delete函数，在删除结点的时候要考虑几个特殊情况，头尾结点。删除第一个结点时，需要将head指针下移，尾结点的next也要指向第二个结点；删除尾结点时，要将尾结点前的结点与第一个结点相连。在设计这个函数时，我只考虑了当len大于1的情况，在只剩下一个结点时，不必要删除，直接输出data的值即可（在约瑟夫函数中有写）。具体函数如下： int LinkList::Delete(LinkNode *a) { if(len>1)//只考虑长度大于1的情况 { if(head==a){ int out=head->data;LinkNode* q=head; while(q->next!=head){ q=q->next;} q->next=head->next;head=head->next;delete a;len--; //用len记录删除后的循环链表的长度 return out;} else { LinkNode* q=head;int out=a->data; while(q->next!=a){ q=q->next;} if(a->next=head).//删除的是尾结点时（不知道为什么我写程序里总是编译出现错误） { q->next=head; //重新链接 delete a; len--; return out;} else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果： 程序清单： #include int data; int code; LinkNode *next;}; class LinkList { public: LinkList(); void Creat(const int); //~LinkList(); int Delete(LinkNode*); int Joseph(int); private: LinkNode* head; LinkNode* elem; int len; }; LinkList::LinkList() { head=elem=NULL; len=0;} void LinkList::Creat(const int number) { if(number==1){ head=elem=new LinkNode; head->data=1; cout<<“请输入密码:”< cin>>head->code; head->next=head;} else { head=elem=new LinkNode; head->data=1; cout<<“请依次输入各个密码:”< cin>>head->code; LinkNode*q=head; q=head; for(int i=1;i { LinkNode*p=new LinkNode; p->data=i+1; cin>>p->code; q->next=p; q=p; } q->next=head;} len=number;} int LinkList::Delete(LinkNode *a) { if(len>1) { if(head==a) { int out=head->data; LinkNode* q=head; while(q->next!=head) { q=q->next; } q->next=head->next; head=head->next; delete a; len--; return out; } else { LinkNode* q=head; int out=a->data; while(q->next!=a) { q=q->next; } q->next=a->next; delete a; len--; return out; } } } int LinkList::Joseph(int m){ if(len>1){ LinkNode *q; if(m==1) { q=elem; int a=q->code; elem=elem->next; cout< Joseph(a); } else { for(int i=1;i elem=elem->next; q=elem; elem=elem->next; int a=q->code; cout< Joseph(a); } } else cout< int main(){ int num,code; cout<<“请输入人数: ”; cin>>num; LinkList L; L.Creat(num); cout<<“请输入第一个上限数: ”; cin>>code; cout<<“出列顺序:”< L.Joseph(code); return 0;} 4、小结 一、这次课程设计的心得体会通过实践我的收获如下： 一开始接触数据结构课程设计真的挺难的，好多都不会，不是逻辑方面的问题，而是不具备动手能力，脑子里总有一团火，比如对于这个题目，一开始有很多的想法，想到了从逻辑上怎么实现他，要编写哪些程序，但是一到需要编写了就开始为难了，可以说是几乎不知道从哪里入手，参考了书本里的程序，仿照他的结构一步一步做下来，现在对于单链表的各种操作已经算是比较熟练了，让我知道光有理论知识还远远不够，需要多动手，写的多了自然就能手到擒来。 二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中要考虑周到，严密。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 实习报告 题目:约瑟夫环 班级：08052712学号: 08052211姓名: 葛俊峰 一、需求分析 1.本演示程序中，编号为1，2，„，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，如此下去，直到所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即总人数，m的值，每个人所持的密码），运算结果显示在其后。 3.程序执行的命令包括： （1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。 4.测试数据： m的初始值为20；n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。 二、概要设计 为了实现上述操作，应以单向循环链表为存储结构。为此，需要1个抽象数据类型：线性表。 1.线性表的抽象数据类型为： ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,„，n,n≥0} 数据关系：R1={ 基本操作： InitList(&L) 操作结果：构造一个空的线性表L。 }ADT List 2.本程序包括三个模块: 1）主程序模块： void main（）{ 初始化； 输入数据； 函数调用； } 2）构造链表并输入每个人信息的模块-----实现线性表的抽象数据类型； 3）运行模块-----模拟约瑟夫环依次出列； 各模块之间调用关系如下： 主程序模块 ↓ 构造链表并输入每个人信息的模块 ↓ 运行模块 三、详细设计 1.结点类型和指针类型 typedef struct Node{ int num; int password; struct Node *next; }LNode,*LinkList;//结点类型,指针类型 Status MakeNode（LinkList &p，Elem Type e） { //分配由p指向的数据元素为e、后继为“空”的特点，并返回TRUE，//若分配失败，则返回FALSE P=(LinkType)malloc（sizeof（NodeType））； If（！p）return FALSE； p->data=e；p->next=null；return TRUE； } viod Free Node（Link Type &p） { //释放p所指结点 } 2.主函数和其他函数 int main() { //主函数 LinkList L = NULL; LinkList s ,r; int n,i,j,m;//初始化 printf(“请输入人数nn”); scanf(“%d”,&n); printf(“请输入mn”); scanf(“%d”,&m); printf(“请依次输入每个人的密码n”);//输入数据 CreatList(L,s,r,n);//创建链表run(L,n,m);//模拟约瑟夫环并输出 return 0; }//main void CreatList(LinkList &L,LinkList &s,LinkList &r,int n) { //创建链表 int i=1; s=(LNode*)malloc(sizeof(LNode));//分配空间 scanf(“%d”,&s->password);//输入密码 s->num = i;//序号为i if(L==NULL) L=s; else r->next=s; r=s;//为下次连接做准备 for(i=2;i<=n;i++) { s=(LNode*)malloc(sizeof(LNode));//分配空间 scanf(“%d”,&s->password); s->num = i; r->next=s;//连接到下个结点 r=s;//为下次连接做准备 } r->next = L;//闭合L = r; } // void CreatList void run(LinkList &L,int n,int m) { //模拟约瑟夫环并输出 LinkList s,r; int i,j; for(i = 0;i < n;i ++) { for(j = 1;j < m;j ++) L = L->next;//报数 s = L->next; r = s->next; printf(“%dn”,s->num);//输出序号 m = s->password; L->next = r; free(s);//删除结点 } }//run 3.函数的调用关系图反映了演示程序的层次结构: main ↓↓ CreatListrun ↓↓ Make NodeFree Node 四、调试分析 1.刚开始由于使用头结点,使得程序不符合要求。 2.在写程序时忽略了一些变量参数的标识“&”,使调试程序费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。 3.本程序模块划分比较简单且容易看懂，但头指针赋空不太合理。 4.本实习作业采用数据抽象的设计方法，将程序划分为3个层次，使得设计时思路清晰，实现调试顺利 五、用户手册 1.本程序运行环境为DOS操作系统，执行文件为约瑟夫环.exe。 2． 进入演示程序后出现提示信息： “请输入人数n” 输入后，出现提示信息： “请输入m” 输入后，出现提示信息： “请依次输入每个人的密码” 输入后，显示相应的结果。 /*功能：约瑟夫变种问题 假如有k个好人，和k个坏人，所有人站成一圈，前K个人是好人，后K个人是坏人，编写程序计算一个最小的m,使k个坏人都被处死，而不处决任何好人。 本程序基于韩顺平Java约瑟夫环程序！ */ public class Demo { public static void main(String[] args) { int m=ysminm(2);//该圈中有2个好人和2个坏人 System.out.println(“将坏人杀死的最小的m=”+m); } //找出将k个坏人杀死的最小m public static int ysminm(int k) { int temp=1; int m=1; while(true) { CycLink cyclink=new CycLink(); cyclink.setLen(2*k);//设置环为k个好人和k个坏人 cyclink.createLink(); cyclink.setK(temp); cyclink.setM(m); cyclink.show(); if(cyclink.play()) { return m; } m++; } } } class Child { int no; Child nextchild=null; public Child(int no){ //给一个编号this.no=no;} } //环形链表 class CycLink { //先定义一个指向链表第一个人的引用 Child firstChild=null;Child temp=null;int len=0;//表示共有几个人 int k=0;//表示从第几个开始数 int m=0;//表示第几个人别杀死//设置链表大小 public void setLen(int len){this.len=len;} //设置从第几个人开始数数 public void setK(int k){this.k=k;}public void setM(int m){this.m=m;}//开始play，如果找到m则返回true,否则返回false.public boolean play(){int lenTemp=len;Child temp=this.firstChild;//1.先找到开始数数的人 for(int i=1;i }temp=temp.nextchild;} //找到要杀死的前一个人 Child temp2=temp;while(temp2.nextchild!= temp){temp2=temp2.nextchild;} //3.将数到m的人杀死，推出圈 temp2.nextchild=temp.nextchild;// 如果杀死的人是好人，就表示m设置的不正确，返回false if(temp.no>=1&&temp.no<=lenTemp/2){return false;} //让temp指向下一个数数的人 System.out.println(“第”+temp.no+“ 个人出局”);temp=temp.nextchild;this.len--;} //运行到此处表明杀死的都是坏人，所以返回true.return true;//初始化环形链表 public void createLink(){for(int i=1;i<=len;i++){if(i==1){//创建第一个人Child ch=new Child(i);this.firstChild=ch;this.temp=ch;}else{//创建最后一个人if(i==len){//继续创建人Child ch=new Child(i);temp.nextchild=ch;temp=ch; }}}} } else {} //继续创建人 Child ch=new Child(i);temp.nextchild=ch;temp=ch;//打印该环形链表 public void show(){} //定义一个跑龙套的 Child temp=this.firstChild;do{System.out.println(temp.no);temp=temp.nextchild;}while(temp!= this.firstChild); #include typedef struct LNode { //数据域 int cipher; //密码 int number; //编号 struct LNode *next; //指针域 }LNode,*LinkList; void InitList(LinkList &L) //创建一个只有头结点链表 { L =(LinkList)malloc(sizeof(LNode));if(!L){ exit(1); printf(“/n/nError!/n/n”);} L->next = L;} void CreateList(int n,LinkList &L)//初始化循环单链表 { LinkList p,q;q = L;printf(“分别输入每个人的密码：”);for(int i = 1;i <= n;i++){ int k; scanf(“%d”,&k); if(k <= 0) { printf(“nn密码有误!nn”); exit(1); } p =(LinkList)malloc(sizeof(LNode)); if(!p) { exit(1); printf(“/n/nError!/n/n”); } p->cipher = k; p->number = i; L->next = p; L = p;} L->next = q->next;free(q);} void PrintList(int x,int n,LinkList L)//输出出列顺序 { LinkList p,q;p = L;for(int i = 1;i <= n;i++){ for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf(“%d ”,q->number); p->next = q->next; free(q);} } int main(){ printf(“=============约瑟夫环==============nnn”); int n,x;LinkList L;L = NULL;InitList(L); //构造空链表 printf(“输入初始密码：”);scanf(“%d”,&x); //初始密码为x printf(“n”);printf(“输入参与总人数：”);scanf(“%d”,&n); //总共的人数n printf(“n”);CreateList(n,L); //建立好一个约瑟夫环 printf(“nnn===================================nn”); printf(“出列编号为：”);PrintList(x,n,L); //输出出列顺序 printf(“nn”);return 0;}第二篇：约瑟夫环课程设计实验报告
第三篇：数据结构报告--约瑟夫环范文
第四篇：约瑟夫环变种问题——k个好人k个坏人
第五篇：数据结构课程设计——约瑟夫环报告(含代码)
点击咨询 