约瑟夫(Josephu)环C++课程设计数据结构

1、-作者xxxx-日期xxxx约瑟夫(Josephu)环C+课程设计数据结构【精品文档】目录1 前言1背景和意义1设计的原理、方法和主要内容12 正文1设计的目的和意义1目标与总体方案2设计方法和内容2链表的实现2设计程序3设计创新和关键技术8设计创新8关键技术8结论83 致谢9参考文献9附录A 源程序的清单9 前言数据是计算机化的信息,它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术应用等,都是对数据进行加工处理的过程。因此,要设计出一个结构好效率高的程序,必须研究数据的特性及数据间的相互关系及其对应的存储表示,并利用这些特

2、性结合相关编程技术，运用合适、熟练的方法，才能设计出符合要求、可操作性强、有利用价值的应用程序。1.2设计的原理、方法和主要内容本实验设计主要涉及到了队列的相关概念、原理、算法和操作等方面内容。本实验设计主要实现队列的3个基本功能：建立新的Josephu链表、插入一个元素、删除一个元素。应用到的原理是先进先出算法。主要内容是使用C语言和C+语言相结合编写程序，能够顺利通过键盘来操作该程序，完整实现上述要求。约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1，2，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的那个人出列，他的下一个人又从1开始数，报数到m的人出列

3、直到所有人都出列为止。从上述分析可见，在C+中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。在程序中有还参照了课外书籍上的一些函数及程序段完成了Josephu链表最主要功能之一的Josephu环功能。在main函数中加入了才学会的Switch，case语句使程序的输出看上去能比较有可视感。正文课程设计目的是为学生提供了一个

4、既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。通过实践让学生理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。课程设计的意思是培养学生运用所学课程的知识分析解决实际问题的能力；培养学生调查研究、查阅技术文献、资料、手册以及编写技术文献的能力；通过课程设计，要求学生在指导教师的指导下，独立完成设计课题的全部内容，包括：（1）通过调查研究和上机实习，收集和调查有关技术资料。（2）掌握课程设计的基本步骤和方法。（3）根据课题的要求进行上机实验调试。本实验设计的目标是运用循环链表来解决Jo

5、sephu环问题，其中运用了许多链表中的基本操作使改程序能不只解决一个Josephu的简单链表，其中的Josephu函数则是用于，运用C+程序（或C语言）编写程序，实现队列的建立、插入和删除基本功能，在程序设计成功的基础上，进一步深化理解队列的作用和实现原理，并独自撰写设计论文。本实验设计总体方案如图2-1所示：图2-1设计总体方案图要求本设计严格按照方案进行，力求省时省力，提高设计效率，节约资源。2.3.1Josphu链表的实现Josphu链表链式表示和实现约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1，2，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的

6、那个人出列，他的下一个人又从1开始数，报数到m的人出列直到所有人都出列为止。给出出列的顺序 图2-2链队列示意图 循环链表队列的顺序表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了C语言中描述方便起见，在此我们约定，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”从上述分析可见，在C+中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最

7、大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。2.3.2设计程序编写本实验设计程序采用C语言和C+想结合的方法，在允许中文环境下运行。本设计程序如下：（1）.构造Josephu链表： 由于是应用了类的结构，在main()函数又有选择语句，直接构造回产生错误所以我在构造最初的Josephu链表时运用了两个函数JosephuLink()函数和putin()函数。JosephuLink()函数能构造一个空链表而putin()函数则往其中放入初始值。template <class T>JosephuLink<T>:JosephuLink() /利用头插法定义构造

8、函数 head=new Node<T>template <class T>void JosephuLink<T>:putin()int i;cin>>n;if(n<1)cout<<"输入参数错误!"<<endl;head->data=1;tail=head;for(i=2;i<=n;i+)p=new Node<T>p->data=i;tail->next=p;tail=p;cout<<"构建的Josephu链表为:"<<

9、;endl;tail->next=head;p=head; for(i=1;i<=n;i+)cout<<p->data<<" " p=p->next;cout<<endl;如图2-3所示：图2-3 程序图（2）.插入操作 插入操作较为简单只是对以前链表的该操作做了一些简单的修改就能运用于该程序，插入操作用的是Insert()函数。template <class T>bool JosephuLink<T>:Insert() /插入 int loc;T x;cout<<"输

10、入要插入位子:"cin>>loc; cout<<"请输入要插入的数:"cin>>x; if(loc<1) /判断位置是否合法cout<<"输入参数错误，插入失败!"<<endl;return false;Node<T>*p=head->next;for(int i=1;i<loc-1;i+)p=p->next;Node<T>*m=new Node<T>m->data=x;if(loc-1!=0)m->next=p-

11、>next;p->next=m;elsem->next=head->next;head->next=m;cout<<"新的数列为:"n+;return true;（3）.删除操作同插入操作一样删除操作也是利用的以前对链表的操作加以简单改编而成，在本程序中删除操作为Delete函数。template <class T>bool JosephuLink<T>:Delete() /删除int loc;T x;cout<<"请输入要删除的位子:"cin>>loc; if(l

12、oc<1|head=NULL) /判断位置是否合法return false; Node<T>*p=head;if(loc=1)head=head->next;elseNode<T>*q=head; for(int i=0;i<loc-1;i+)q=q->next;p=q->next;q->next=p->next;x=p->data;delete p;n-;return true;（4）.Josephu操作Josephu操作为本程序的重点，在本程序中我是利用了一个Josephu函数来解决该问题的，该函数是通过不断的循环、淘

13、汰、再循环、再淘汰直到将Josephu链表中的所有元素被删除。函数如下：template <class T>int JosephuLink<T>: Josephu()int m, k;int i;cout<<"请输入执行中的每隔几位数淘汰一个元素:"<<endl;cin>>m;cout<<"请输入从第几个数开始执行:"<<endl;cin>>k;p=head;for(i=1;i<k;i+)p=p->next;cout<<"执行

14、过程如下:n"<<endl;while(p!=p->next)for(i=1;i<m;i+)q=p;p=p->next;q->next=p->next;cout<<"本轮删除元素为:"<<p->data<<endl;delete p;p=q->next; n-; f=p;cout<<"剩下的链表为 :"for(i=1;i<=n;i+)cout<<f->data<<" " f=f->n

15、ext;cout<<endl;if(p=p->next)cout<<"最终剩余的元素为:"<<p->data;delete p;head=NULL;return 0;template <class T>void JosephuLink<T>:putin()int i;cin>>n;if(n<1)cout<<"输入参数错误!"<<endl;head->data=1;tail=head;for(i=2;i<=n;i+)p=new No

16、de<T>p->data=i;tail->next=p;tail=p;cout<<"构建的Josephu链表为:"<<endl;tail->next=head;p=head; for(i=1;i<=n;i+)cout<<p->data<<" " p=p->next;cout<<endl;（5）.显示当前链表操作template <class T>void JosephuLink<T>:show() /遍历操作 Node<

17、;T> *q;q=head;cout<<q->data;q=head->next;while(q!=head)cout<<" "<<q->data;q=q->next;cout<<endl;（6）.退出操作 退出操作只运用了一个简单的返回函数quit（）。 显示当前链表操作直接运用了链表的一些特性，实行了简单的 遍历操作。template <class T>int JosephuLink<T>:quit()exit (0); 程序中主要运用了C+的类函数，C语言中的循环、判

18、断和输入输出函数等方法，进行认真仔细的编写，可以通过Win-tc和Visual C+等语言编译软件的运行，其中使用Win-tc必须在中文环境中方可运行。在Visual C+中运行的情况如图2-4所示：图2-4设计创新算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新的排序等。在本设计程序中，第一次把算法中的建立、插入、删除等操作融合在一起，在一个程序中实现各自的功能，从而提高整体的运行效率。关键技术在本设计程序中，我们首先定义全体实数为需要建立新的队列的有限集，这样就扩大了新队列建立所需元素的取值范围，减少

19、了错误的发生。在本设计程序中，我们定义队列为线性的链表形式，这样就更容易操作，方便元素的插入或删除。其中还借助了指针的作用，使得我们查找某个元素，尤其是方便了删除或有序插入的操作。使本程序能更加广泛的运用。通过本次课程设计的锻炼，使我对计算方法又有了许多新的深刻认识，更深的理解了数据结构的难点，主要有以下新的体会：一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。一个软件系统框架应建立在数据之上，而不是建立在操作

20、之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。本实验设计就是建立在“定义、表示、实现”的基础上完成的。同时，做好课程设计更能体现出同学的学习态度，对于新知识的渴望与追求，能够反映出同学对自己负责任的决心，这点让我感受颇深。致谢由于本人相关专业知识有限，在初始接触阶段遇到了许多的困难，在此特别感谢陈杰老师的帮助，他不是直接告诉我们该怎么做，而是以启发的形式鼓励我们思考，充分的调动了我们的积极性，更重要的是使我们对不懂的知识点有了深刻的了解。但在指导老师陈杰老师的大力指导下，在各位同学们的大力帮助与支持下，同时通过本人大量查阅书籍资料，浏览相关网页论坛之后，才顺利编写完毕，在此

21、十分感谢大家！虽然是讲解，。参考文献1 陈松乔，刘丽华，陈可算法与数据结构（C与c+描述）第二版. 北京；清华大学出版社，2002年；131-1352 严蔚敏，吴伟民.c语言题集（C语言版）.第1版.北京；清华大学出版社，2005年；96-105.3 李春葆，章启俊.C+程序设计.第1版.北京；清华大学出版社，2007年；56-31.+面对对象程序.第1版.北京；清华大学出版社，2006年；15-32.5 刘振东，刘燕君.c+程序设计.第一版.北京；机械工业出版社，2004年；17-37.6 许卓群C+程序设计第一版. 北京；高等教育出版社，1989年；14-18.7 严蔚敏，吴伟民C语言集（

22、C语言版）第一版. 北京；清华大学出版社，1999；3-10.8 王晓东。数据结构（c+语言版） 第一版。北京：科学出版社。2008年：36-47.9 蔡自经，施伯乐C语言教程第二版. 上海；复旦大学出版社，1984年，11-14.附录A 源程序的清单#inclue <iostream>#include <string>using namespace std;template <class T>class JosephuLink;template <class T>class Node /结点类friend class JosephuLink&l

23、t;T> /友元类T data; Node<T> *next; ;template <class T>class JosephuLink /链表类public:JosephuLink(); /构造函数void putin(); /输入函数int Josephu(); /Josephu函数bool Insert(); /插入bool Delete(); /删除void show(); /遍历int quit(); /退出private:Node<T> *head; /头指针Node<T> *tail; /尾指针Node<T> *p

24、;Node<T> *f;Node<T> *q;int n;template <class T>JosephuLink<T>:JosephuLink() /利用头插法定义构造函数 head=new Node<T>template <class T>int JosephuLink<T>: Josephu()int m, k;int i;cout<<"请输入执行中的每隔几位数淘汰一个元素:"<<endl;cin>>m;cout<<"请输入从

25、第几个数开始执行:"<<endl;cin>>k;p=head;for(i=1;i<k;i+)p=p->next;cout<<"执行过程如下:n"<<endl;while(p!=p->next)for(i=1;i<m;i+)q=p;p=p->next;q->next=p->next;cout<<"本轮删除元素为:"<<p->data<<endl;delete p;p=q->next; n-; f=p;cout&

26、lt;<"剩下的链表为 :"for(i=1;i<=n;i+)cout<<f->data<<" " f=f->next;cout<<endl;if(p=p->next)cout<<"最终剩余的元素为:"<<p->data;delete p;head=NULL;return 0;template <class T>void JosephuLink<T>:putin()int i;cin>>n;if(n<

27、1)cout<<"输入参数错误!"<<endl;head->data=1;tail=head;for(i=2;i<=n;i+)p=new Node<T>p->data=i;tail->next=p;tail=p;cout<<"构建的Josephu链表为:"<<endl;tail->next=head;p=head; for(i=1;i<=n;i+)cout<<p->data<<" " p=p->next;

28、cout<<endl;template <class T>bool JosephuLink<T>:Insert() /插入 int loc;T x;cout<<"输入要插入位子:"cin>>loc; cout<<"请输入要插入的数:"cin>>x; if(loc<1) /判断位置是否合法cout<<"输入参数错误，插入失败!"<<endl;return false;Node<T>*p=head->next

29、;for(int i=1;i<loc-1;i+)p=p->next;Node<T>*m=new Node<T>m->data=x;if(loc-1!=0)m->next=p->next;p->next=m;elsem->next=head->next;head->next=m;n+;return true;template <class T>bool JosephuLink<T>:Delete() /删除int loc;T x;cout<<"请输入要删除的位子:"

30、;cin>>loc; if(loc<1|head=NULL) /判断位置是否合法return false; Node<T>*p=head;if(loc=1)head=head->next;elseNode<T>*q=head; for(int i=0;i<loc-1;i+)q=q->next;p=q->next;q->next=p->next;x=p->data;delete p;n-;return true;template <class T>void JosephuLink<T>:show() /遍历操作 Node<T> *q;q=head;cout<<q->data;q=head->next;while(q!=head)cout<<" "<<q->data;q=q->next;cout<<endl;template <class T>int JosephuLink<T>:quit()exit (0); int main() cout<<"*n" <<&qu