C++课程设计实验报告 .doc

目录前言11.1背景和意义11.2设计的原理、方法和主要内容1正文22.1设计的目的和意义22.2目标与总体方案22.3设计方法和内容22.3.1 线性链表的定义22.3.2 Josphu链表的实现32.3.3设计程序42.4设计创新和关键技术82.5结论9致谢9参考文献9附录A 源程序的清单11 前言1.1背景和意义数据结构它支持面向对象的程序设计方法，特别适用于中型和大型的软件开发项目，从开发时间、费用到软件的重用性、可扩充性、可维护性和可靠性等方面，数据结构均具有很大的优越性。数据结构可以实现很多东西。在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。要设计出一个结构好效率高的程序,必须研究数据的特性及数据间的相互关系及其对应的存储表示,并利用这些特性结合相关编程技术，运用合适、熟练的方法，才能设计出符合要求、可操作性强、有利用价值的应用程序。1.2设计的原理、方法和主要内容本实验设计主要实现队列的3个基本功能：建立新的Josephu链表、插入一个元素、删除一个元素。应用到的原理是先进先出算法。主要内容是使用C语言和C+语言相结合编写程序，能够顺利通过键盘来操作该程序，完整实现上述要求。线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。两部分信息组成数据元素的存储映像。它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题.在程序中运用了在本学期中新学到模版等东西，主要还是运用了类相关内容，程序中的JosphuLink()、Insert()、Delete()、show()等基本操作函数都是参照本学期所学过的链表的相关内容加以运用。约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1，2，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的那个人出列，他的下一个人又从1开始数，报数到m的人出列直到所有人都出列为止。从上述分析可见，在数据结构中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。在程序中有还参照了课外书籍上的一些函数及程序段完成了Josephu链表最主要功能之一的Josephu环功能。在main函数中加入了才学会的Switch，case语句使程序的输出看上去能比较有可视感。正文2.1设计的目的和意义课程设计目的是为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。通过实践让学生理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。课程设计的意思是培养学生运用所学课程的知识分析解决实际问题的能力；培养学生调查研究、查阅技术文献、资料、手册以及编写技术文献的能力；通过课程设计，要求学生在指导教师的指导下，独立完成设计课题的全部内容，包括：（1）通过调查研究和上机实习，收集和调查有关技术资料。（2）掌握课程设计的基本步骤和方法。（3）根据课题的要求进行上机实验调试。2.2目标与总体方案本实验设计的目标是运用循环链表来解决Josephu环问题，其中运用了许多链表中的基本操作使改程序能不只解决一个Josephu的简单链表，其中的Josephu函数则是用于，运用C+程序（或C语言）编写程序，实现队列的建立、插入和删除基本功能，在程序设计成功的基础上，进一步深化理解队列的作用和实现原理，并独自撰写设计论文。本实验设计总体方案如图2. 1所示：图2.1设计总体方案图要求本设计严格按照方案进行，力求省时省力，提高设计效率，节约资源。2.3设计方法和内容2.3.1 线性链表的定义线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。两部分信息组成数据元素的存储映像。线性表顺序存储结构的特点:它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题.在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。 循环链表是限定插入和删除操作在表的两端进行的线性表。这两端分别称为端点1和端点2也可像栈一样，可以用一个铁道转轨网络来比喻双端队列。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。 图2.2循环链表示意图2.3.2 Josphu链表的实现Josphu链表链式表示和实现约瑟夫（Josephu）问题：已知N个人围坐在一张圆桌周围（不妨以1，2，N对每一个人依次编号），现在先从序号为K的人开始报数，数到m的那个人出列，他的下一个人又从1开始数，报数到m的人出列直到所有人都出列为止。给出出列的顺序 图2.3链队列示意图 循环链表队列的顺序表示和实现和顺序栈相似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了C语言中描述方便起见，在此我们约定，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，如图2.所示从上述分析可见，在C+中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。2.3.3设计程序编写本实验设计程序采用C语言和C+想结合的方法，在允许中文环境下运行。本设计程序如下：（1）.构造Josephu链表： 由于是应用了类的结构，在main()函数又有选择语句，直接构造回产生错误所以我在构造最初的Josephu链表时运用了两个函数JosephuLink()函数和putin()函数。JosephuLink()函数能构造一个空链表而putin()函数则往其中放入初始值。template <class T>JosephuLink<T>:JosephuLink() /利用头插法定义构造函数 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链表为:"<<endl;tail->next=head;p=head; for(i=1;i<=n;i+)cout<<p->data<<" " p=p->next;cout<<endl;图2.4 构建（2）.插入操作插入操作较为简单只是对以前链表的该操作做了一些简单的修改就能运用于该程序，插入操作用的是Insert()函数。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;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;cout<<"新的数列为:"n+;return true;（3）.删除操作同插入操作一样删除操作也是利用的以前对链表的操作加以简单改编而成，在本程序中删除操作为Delete函数。template <class T>bool JosephuLink<T>:Delete() /删除int loc;T x;cout<<"请输入要删除的位子:"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;（4）.Josephu操作Josephu操作为本程序的重点，在本程序中我是利用了一个Josephu函数来解决该问题的，该函数是通过不断的循环、淘汰、再循环、再淘汰直到将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<<"执行过程如下: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->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<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;cout<<endl;图 图2.5 Josephu选择（5）.显示当前链表操作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;（6）.退出操作退出操作只运用了一个简单的返回函数quit（）。显示当前链表操作直接运用了链表的一些特性，实行了简单的 遍历操作。template <class T>int JosephuLink<T>:quit()exit (0); 程序中主要运用了C+的类函数，C语言中的循环、判断和输入输出函数等方法，进行认真仔细的编写，可以通过Win-tc和Visual C+等语言编译软件的运行，其中使用Win-tc必须在中文环境中方可运行。在Visual C+中运行的情况如图2.6所示：图2.6 运行界面2.4设计创新和关键技术C+是最有意义的方面是支持面向对象的特性。C+中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。本程序设计是利用C+来实现数据结构的特性的。所以在程序的编写过程中下列操作必不可缺：1. 结构的生成；2. 结构的销毁；3. 在结构中查找满足规定条件的数据元素；4. 在结构中插入新的数据元素；5. 删除结构中已经存在的数据元素；6. 遍历。在本设计程序中，充分体现了上述的操作，虽然只是运用局部操作，但是仍然起到了关键作用。使用C语言和C+相结合的方式，使得程序运行更灵活，处理更方便，在表现方式方面得到了创新。2.5结论通过本次课程设计的锻炼，使我对C+程序设计又有了许多新的深刻认识，更深的理解了运用C+来体现数据结构的难点。一个软件系统框架应建立在数据之上，而不是建立在操作之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。本实验设计就是建立在“定义、表示、实现”的基础上完成的。同时，做好课程设计更能体现出同学的学习态度，对于新知识的渴望与追求，能够反映出同学对自己负责任的决心，这点让我感受颇深。致谢为期14天的课程设计中，朱老师给与我们很大帮助。在同学遇到疑问时，化老师能够耐心地讲解。虽然是讲解，他不是直接告诉我们该怎么做，而是以启发的形式鼓励我们思考，充分的调动了我们的积极性，更重要的是使我们对不懂的知识点有了深刻的了解。由于本人相关专业知识有限，在初始接触阶段遇到了许多的困难，致使程序编写无法顺利进行。在指导老师朱赖红老师的大力指导下，在各位同学们的大力帮助与支持下，同时通过本人大量查阅书籍资料，浏览相关网页论坛之后，才顺利编写完毕，在此十分感谢大家！参考文献1 王晓东。数据结构（c+语言版） 第一版。北京：科学出版社。2008年：36-47.2 严蔚敏，吴伟民.数据结构题集（C语言版）.第1版.北京；清华大学出版社，2005年；96-105.3 李春葆，章启俊.C+程序设计.第1版.北京；清华大学出版社，2007年；56-31.4 谭浩强.C+面对对象程序.第1版.北京；清华大学出版社，2006年；15-32.5 刘振东，刘燕君.c+程序设计.第一版.北京；机械工业出版社，2004年；17-37.6 许卓群数据结构第一版. 北京；高等教育出版社，1989年；14-18.7 严蔚敏，吴伟民数据结构题集（C语言版）第一版. 北京；清华大学出版社，1999；3-10.8 陈松乔，刘丽华，陈可算法与数据结构（C与c+描述）第二版. 北京；清华大学出版社，2002年；131-135.9 蔡自经，施伯乐数据结构教程第二版. 上海；复旦大学出版社，1984年，11-14.10严华峰.visual C+课程设计及案例精选.中国水利水电出版社.2004:69-74.11钱能.C+程序设计教程.北京：清华大学出版社.1999:201-202.12Decoder.C/C+程序设计.北京：中国铁道出版社.2002:99-104.13顾仁.高级C+语言程序设计技巧与实例.北京：机械工业出版社.1995:153-164.14谭浩强.C程序设计(第三版).北京：清华大学出版社.2005:77-184.15陈松乔，刘丽华，陈可算法与数据结构（C与c+描述）第二版. 北京；清华大学出版社，2002年；131-135.附录A 源程序的清单#include <iostream>#include <string>using namespace std;template <class T>class JosephuLink;template <class T>class Node /结点类friend class JosephuLink<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;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<<"请输入从第几个数开始执行:"<<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<<"剩下的链表为 :"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<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;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;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<<"请输入要删除的位子:"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" <<" 计算机科学与技术13-1 李鸿潇n" <<" 倾力 打造n" <<" 利用链表链表实现Josephu环"<<endl; cout<<"*nn"<<endl; JosephuLink<int> JL;int cord; do cout<<"-"<<endl;cout<<"*主菜单*"<<endl;cout<<" | 1.建立Josephu链表 |"<<endl; cout<<" | 2.Josephu链表中插入元素 |"<<endl; cout<<" | 3.Josephu链表中删除元素 |"<<endl; cout<<" | 4.执行Josephu选择 |"<<endl; cout<<" | 5.显示当前链表 |"<<endl;cout<<" | 6.退出程序 |"<<endl; cout<<"*"<<endl;cout<<" nn"<<endl;cout<<"请输入你所需的操作:"<<endl;cin>>cord;switch(cord)case 1:cout<<"请输入你所需建立链表的元素个数:"<<endl;JL.putin();break;case 2:JL.Insert();break; case 3:JL.Delete();break;case 4:JL.Josephu();break;case 5:cout<<"当前链表为"<<endl;JL.show();break;case 6:JL.quit();cout<<"nnn"<<endl;while(cord<=6); return 0;