《最新数据结构(c++版)实验参考书》由会员分享，可在线阅读，更多相关《最新数据结构(c++版)实验参考书（45页珍藏版）》请在金锄头文库上搜索。
1、前 言数据结构是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写实验指导书。一、实验目的更
2、好的理解算法的思想、培养编程能力。二、实验要求1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。3、实验结束后总结实验内容、书写实验报告。4、遵守实验室规章制度、不缺席、按时上、下机。5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣 10 分。6、实验报告有一次不合格，扣 5 分，两次以上不合格者，平时成绩以零分记。三、实验环境 Qt 或 VC+6.0四、说明1、本实验的所有算法中元素类型可以根据实际需要选择。2、实验题目中带者为较高要求，学生可自选；
3、其余部分为基本内容，应尽量完成（至少完成 70%，否则实验不合格） 。3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。五、实验报告的书写要求1明确实验的目的及要求；2记录实验的输入数据和输出结果；3说明实验中出现的问题和解决过程；4写出实验的体会和实验过程中没能解决的问题；六、参考书目数据结构 （C+语言描述） 王红梅等 清华大学出版社DATA STRUCTURE WITH C+ William Ford,William Topp清华大学出版社（影印版）实验一 线性表的操作实验类型：验证性 实验要求：必修实
4、验学时： 2 学时一、实验目的一、实验目的：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。二、实验要求二、实验要求：1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：三、实验内容：1设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素 1，2，3，10，然后删除数据元素 6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过 50 个。
5、2设计一个带头结点的单链表类，要求：(1)生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间） 。(2)设计一个测试主函数，实际运行验证所设计单链表类的正确性。3设计一个不带头结点的单链表类，要求：(1)不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为 k 的元素、取数据元素。(提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他位置插入和删除其他位置结点时的不同情况。)(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。4设计一个带头结点的循环单链表类，实现约瑟夫环问题；问题描述：设
6、编号为 1,2,，n(n0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值 m 从第一个人开始顺时针方向自 1 起顺序报数。报到 m 时停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人起重新自 1 起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。测试数据：n=7,7 个人的密码依次为 3,1,7,2,4,8,4初始报数上限值 m=20*5设计一个带头结点的循环双向链表类，要求：(1)带头结点循环双向链表类的成员函数包括：取数据元素个数、插入、删除、取数据元素。(2)设计一个测试
7、主函数，实际运行验证所设计循环双向链表类的正确性。 *6设计一个单链表实现一元多项式求和问题。要求：（1）设计存储结构表示一元多项式；（2）设计算法实现一元多项式相加。 四、程序样例四、程序样例顺序表类定义：将该类保存在文件 SeqList.h 中。const int MaxSize=100; /100 只是示例性的数据，可根据实际问题具体定义 template /定义模板类 SeqList class SeqList public:SeqList( ) length=0; /无参构造函数SeqList(T a , int n); /有参构造函数SeqList( ) /析构函数为空int Le
8、ngth( ) return length; /求线性表的长度T Get(int i); /按位查找，取线性表的第 i 个元素int Locate(T x ); /按值查找，求线性表中值为 x 的元素序号void Insert(int i, T x); /在线性表中第 i 个位置插入值为 x 的元素T Delete(int i); /删除线性表的第 i 个元素void PrintList( ); /遍历线性表，按序号依次输出各元素 private:T dataMaxSize; /存放数据元素的数组int length; /线性表的长度 ;template SeqList: SeqList(T
9、a , int n) if (nMaxSize) throw “参数非法“;for (i=0; i T SeqList:Get(int i) if (ilength) throw “查找位置非法“;else return datai-1; template int SeqList:Locate(T x) for (i=0; i void SeqList:Insert(int i, T x) if (length=MaxSize) throw “上溢“;if (ilength+1) throw “位置“; for (j=length; j=i; j-)dataj=dataj-1; /注意第 j
10、个元素存在数组下标为 j-1 处datai-1=x; length+; template T SeqList:Delete(int i) if (length=0) throw “下溢“;if (ilength) throw “位置“;x=datai-1;for (j=i; j struct Node T data;Node *next; /此处也可以省略 template class LinkList public: LinkList( )first=new Node; first-next=NULL; /建立只有头结点的空链表LinkList(T a , int n); /建立有 n 个元
11、素的单链表 LinkList( ); /析构函数 int Length( ); /求单链表的长度 T Get(int i); /取单链表中第 i 个结点的元素值 int Locate(T x); /求单链表中值为 x 的元素序号 void Insert(int i, T x); /在单链表中第 i 个位置插入元素值为 x 的结点 T Delete(int i); /在单链表中删除第 i 个结点 void PrintList( ); /遍历单链表，按序号依次输出各元素 private: Node *first; /单链表的头指针 ;template LinkList: LinkList( ) p
12、=first; /工作指针 p 初始化while (p) /释放单链表的每一个结点的存储空间q=p; /暂存被释放结点p=p-next; /工作指针 p 指向被释放结点的下一个结点，使单链表不断开delete q; template T LinkList:Get(int i) p=first-next; j=1; /或 p=first; j=0;while (p /工作指针 p 后移j+;if (!p) throw “位置“;else return p-data;template void LinkList:Insert(int i, T x)p=first ; j=0; /工作指针 p 初始
13、化 while (p /工作指针 p 后移 j+; if (!p) throw “位置“; else s=new Node; s-data=x; /向内存申请一个结点 s，其数据域为 xs-next=p-next; /将结点 s 插入到结点 p 之后 p-next=s;template T LinkList:Delete(int i) p=first ; j=0; /工作指针 p 初始化while (p j+;if (!p | | !p-next) throw “位置“; /结点 p 不存在或结点 p 的后继结点不存在else q=p-next; x=q-data; /暂存被删结点p-next
14、=q-next; /摘链delete q; return x; template LinkList: LinkList(T a , int n)first=new Node;first-next=NULL; /初始化一个空链表for (i=0; i; s-data=ai; /为每个数组元素建立一个结点s-next=first-next; /插入到头结点之后first-next=s;template LinkList: LinkList(T a , int n)first=new Node; /生成头结点r=first; /尾指针初始化for (i=0; i; s-data=ai; /为每个数组
15、元素建立一个结点r-next=s; r=s; /插入到终端结点之后r-next=NULL; /单链表建立完毕，将终端结点的指针域置空1#include #includevoid main( ) int r =1,2,3,4,5,6,7,8,9,10;SeqList a(r,50);cout#includevoid divid( LinkList h=new Node( );p=L.first-next; q=L.first;while (p) if(p-data%2!=0) q=p; p=p-next;else q=p; p=p-next; q-next=h.first-next; h.first-next=q;p=L.firs
