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

目录 前言 1 1.1背景和意义 1 1.2设计的原理、方法和主要内容 1 正文 2 2.1设计的目的和意义 2 2.2目标与总体方案 2 2.3设计方法和内容 2 2.3.1 线性链表的定义 2 2.3.2 Josphu链表的实现 3 2.3.3设计程序 4 2.4设计创新和关键技术 8 2.5结论 9 致谢 9 参考文献 9 附录A 源程序的清单 11 前言 1.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 JosephuLinkT::JosephuLink() //利用头插法定义构造函数 { head=new NodeT; } template class T void JosephuLinkT::putin() { int i; cinn; if(n1) cout输入参数错误!endl; head-data=1; tail=head; for(i=2;i=n;i++) { p=new NodeT; p-data=i; tail-next=p; tail=p; } cout构建的Josephu链表为:endl; tail-next=head; p=head; for(i=1;i=n;i++) { coutp-data ; p=p-next;