《约瑟夫环课程设计实验报告》由会员分享，可在线阅读，更多相关《约瑟夫环课程设计实验报告（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告课程名称：数据结构课程设计课程设计题目：joseph环姓名：院系：计算机学院专业：年级：学号：指导教师：2011年12月18日目 录1 课程设计的目的22 需求分析23 课程设计报告内容31、概要设计32、详细设计33、调试分析x4、用户手册x5、测试结果66、程序清单74 小结 101、 课程设计的目的（1） 熟练使用C+编写程序，解决实际问题；（2） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（3） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（4） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；2、 需
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、
3、课程设计报告内容概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode int data; /顺序 int code; /密码 LinkNode *next; ;建立一个类LinkList ,包含的函数：LinkList(); /构造函数 void Creat(const int ); /创建循环链表 int Delete
4、(LinkNode* ); /删除报到数的结点 int Joseph(int ); / 约瑟夫环私有成员是LinkNode* head; /指向第一个结点的指针LinkNode* elem; / 同上 int len; /长度我定义了一个elem指针是为了约瑟夫环里运行方便，elem只在约瑟夫环这个函数里用到，其他函数没有特别大的用处。构造函数与书上的没什么大差别，创建循环链表时，要考虑几个问题，一个是题目要求是不带头结点，所以head指针直接指向了第一个结点，我在创建链表时把第一个结点初始化data为1，表明这个结点是第一个结点。具体如下：void LinkList:Creat(const
5、int number) /number为结点个数，也就是参与的人数 if(number=1) /只有一个人的情况 head=elem=new LinkNode; head-data=1; cout请输入密码:head-code; head-next=head; else head=elem=new LinkNode; head-data=1; cout请依次输入各个密码:head-code;LinkNode*q=head; q=head; for(int i=1;idata=i+1; cinp-code; q-next=p; q=p; q-next=head; /构成循环链表 len=numb
6、er; 在构建约瑟夫环的执行函数时，我首先考虑了递归调用的函数，原本的这个程序的所有的都定为elemtype类型的，虽然编译没出错，但是在连接时发生了错误，在老师的指导下改成了具体的int型。int LinkList:Joseph(int m) if(len1) LinkNode *q;if(m=1) /在初始报数为1的情况下 q=elem;int a=q-code; /将选中的结点的密码记录在a中elem=elem-next;coutDelete(q)endl; /Delete函数是为了将已经报过数的人删除Joseph(a); /用已经删除的结点的存的密码作为下一次循环的报数值else /一
7、般情况下for(int i=1;inext; /找到需要出列的结点q=elem;elem=elem-next; /此处的elem指针指向要删除的结点的下一个结点，下次递归调用时从这里开始向下循环报数 int a=q-code; coutDelete(q)endl;Joseph(a);else /在只有一个结点的情况下coutdata; 最后还有一个Delete函数，在删除结点的时候要考虑几个特殊情况，头尾结点。删除第一个结点时，需要将head指针下移，尾结点的next也要指向第二个结点；删除尾结点时，要将尾结点前的结点与第一个结点相连。在设计这个函数时，我只考虑了当len大于1的情况，在只剩下
8、一个结点时，不必要删除，直接输出data的值即可（在约瑟夫函数中有写）。具体函数如下：int LinkList:Delete(LinkNode *a) if(len1) /只考虑长度大于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-nex
9、t!=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、测试结果：6 程序清单：#include struct LinkNode int data; int code; LinkNode *next;class LinkListpublic: LinkList(); void Creat(const int ); /LinkList(
10、); 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请输入密码:head-code; head-next=head; else head=elem=new LinkNode; head-data=1; cout请依次输入各个密码:head-code; LinkNode*q=head; q=head; for(int i=1;idata=i+1; cinp-code; q-next=p; q=p; q-next=head; len=number;int LinkList:Delete(LinkNode *a) if(len1) if(head=a)
