《数据结构》
课程设计报告
课程名称：
姓名： 院系： 专业： 年级: 学号： 指导教师：
《数据结构》课程设计
课程设计题目: joseph环
计算机学院
2011年12月18日
(完整word版)约瑟夫环课程设计实验报告
目 录
1 课程设计的目的………………………………………………………………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、要求:
(完整word版)约瑟夫环课程设计实验报告
利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号.
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 ）； // 约瑟夫环 私有成员是
(完整word版)约瑟夫环课程设计实验报告
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<〈\"请输入密码:”〈 head=elem=new LinkNode; head->data=1; cout<〈\"请依次输入各个密码：\"〈〈endl; cin>〉head-〉code； (完整word版)约瑟夫环课程设计实验报告 LinkNode*q=head; q=head; for（int i=1;i〈number；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的情况下 { (完整word版)约瑟夫环课程设计实验报告 q=elem; int a=q—>code； //将选中的结点的密码记录在a中 elem=elem—〉next; cout〈 for（int i=1;i〈m；i++） elem=elem-〉next; //找到需要出列的结点 q=elem； elem=elem-〉next； //此处的elem指针指向要删除的结点的下一个结点,下次递归调用 时从这里开始向下循环报数 int a=q->code； cout< } else //在只有一个结点的情况下 cout< 最后还有一个Delete函数，在删除结点的时候要考虑几个特殊情况,头尾结点。删除第一个结点时，需要将head指针下移，尾结点的next也要指向第二个结点；删除尾结点时，要将尾结点前的结点与第一个结点相连。在设计这个函数时，我只考虑了当len大于1的情况，在只剩 (完整word版)约瑟夫环课程设计实验报告 下一个结点时，不必要删除，直接输出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) (完整word版)约瑟夫环课程设计实验报告 ｛ 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、测试结果： (完整word版)约瑟夫环课程设计实验报告 (完整word版)约瑟夫环课程设计实验报告 6 程序清单: ＃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； }; (完整word版)约瑟夫环课程设计实验报告 LinkList:：LinkList（） { head=elem=NULL; len=0; } void LinkList：:Creat(const int number） ｛ if（number==1） { head=elem=new LinkNode; head->data=1; cout〈<\"请输入密码：”<〈endl; cin〉〉head-〉code; head—>next=head; ｝ else ｛ head=elem=new LinkNode； head—>data=1; cout<<”请依次输入各个密码:”<〈endl； cin>>head->code; LinkNode*q=head； q=head； (完整word版)约瑟夫环课程设计实验报告 for(int i=1；i〈number；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; (完整word版)约瑟夫环课程设计实验报告 ｝ 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） (完整word版)约瑟夫环课程设计实验报告 { if（len〉1） { LinkNode ＊q； if(m==1) ｛ q=elem; int a=q-〉code； elem=elem-〉next； cout〈 { for(int i=1;i q=elem; elem=elem—>next; int a=q—>code； cout〈 (完整word版)约瑟夫环课程设计实验报告 } cout<〈head—>data; int main() { int num,code; cout〈<\"请输入人数: ”; cin〉〉num; LinkList L; L.Creat（num)； cout〈〈\"请输入第一个上限数: ”； cin>>code; cout〈<\"出列顺序:\"〈〈endl； L.Joseph（code）； return 0； ｝ 4、小结 一、这次课程设计的心得体会通过实践我的收获如下: 一开始接触数据结构课程设计真的挺难的，好多都不会,不是逻辑方面的问题,而是不具备动手能力，脑子里总有一团火，比如对于这个题目，一开始有很多的想法,想到了从逻辑上怎么实现他，要编写哪些程序，但是一到需要编写了就开始为难了,可以说是几乎不知道从哪里入手,参考了书本里的程序，仿照他的结构一步一步做下来，现在对于单链表的各种操作已经算是比较熟练了，让我知道光有理论知识还远远不够，需要多动手，写的多了自然就能手到擒来. (完整word版)约瑟夫环课程设计实验报告 二、根据我在实习中遇到得问题,我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中要考虑周到，严密。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的知识点,并在此基础上学会灵活运用。 5、在课余时间里多写程序,熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 因篇幅问题不能全部显示，请点此查看更多更全内容