《最新数据结构(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 个。2设计一个带头结点的单链表类
5、，要求： (1)生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个 全部为偶数(尽量利用已知的存储空间)。(2)设计一个测试主函数，实际运行验证所设计单链表类的正确性。 3设计一个不带头结点的单链表类，要求：(1)不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为 k 的元素、取数据元素。(提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其 他位置插入和删除其他位置结点时的不同情况。)(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。 4设计一个带头结点的循环单链表类，实现约瑟夫环问题；问题描述：设编号为1,2,，n(
6、nO)个人按顺时针方向围坐-圈，每人持有一个正整数 密码。开始时任意给出一个报数上限值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 /定义模板类 SeqListclass SeqListpublic:SeqList( ) length=0;SeqList(T a , int n);SeqList( ) int Length( ) return length; T Get(int i);/无参构造函数/有参构造函数/析构
8、函数为空/求线性表的长度按位查找，取线性表的第i个元素int Locate(T x); void Insert(int i, T x); T Delete(int i); void PrintList( );按值查找，求线性表中值为x的元素序号/在线性表中第i个位置插入值为x的元素删除线性表的第i个元素/遍历线性表，按序号依次输出各元素private:T dataMaxSize; int length;/存放数据元素的数组/线性表的长度template SeqList: SeqList(T a , int n)if (nMaxSize) throw 参数非法; for (i=0; in; i+
9、)datai=ai; length=n;template T SeqList:Get(int i)if(ilength) throw 查找位置非法; else return datai-1;template int SeqList:Locate(T x)for (i=0; ilength; i+)if (datai=x) return i+1; 下标为i的元素等于x,返回其序号i+1 return 0;/退出循环，说明查找失败template void SeqList:Insert(int i, T x)if (length=MaxSize) throw 上溢; if(ilength+1) t
10、hrow 位置; for (j=length; j=i; j-)dataj=dataj-1;注意第j个元素存在数组下标为jT处datai-1=x;length+;template T SeqList:Delete(int i)if (length=0) throw 下溢;if (ilength) throw 位置; x=datai-1;for (j=i; jlength; j+)dataj-1=dataj;注意此处j已经是元素所在的数组下标length-;return x;链表类定义：将该类保存在文件 LinkList.h 中。template struct Node T data;Nodev
11、T *next; 此处vT也可以省略template class LinkListpublic:LinkList( )first=new Node; first-next=NULL; /建立只有头结点的空链表 LinkList(T a , int n); /建立有 n 个元素的单链表LinkList( ); int Length( );T Get(int i); int Locate(T x);void Insert(int i, T x); T Delete(int i);void PrintList( );/析构函数/求单链表的长度取单链表中第i个结点的元素值求单链表中值为x的元素序号在单
12、链表中第i个位置插入元素值为x的结点 在单链表中删除第i个结点/遍历单链表，按序号依次输出各元素private:Node *first; /单链表的头指针 ;template LinkList: LinkList( )p=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 & jnext;/工作指针
13、p 后移j+;if (!p) throw 位置;else return p-data;template void LinkList:Insert(int i, T x)p=first ; j=0;工作指针p初始化while (p & jnext;/工作指针 p 后移j+; if(!p) throw 位置; else s=new NodevT; s-data=x; 向内存申请一个结点s，其数据域为xs-next=p-next;/将结点 s 插入到结点 p 之后p-next=s;template T LinkList:Delete(int i)p=first ; j=0; 工作指针p初始化whil
14、e (p & ji-1) /查找第 i-1 个结点p=p-next;j+;if (!p | | !p-next) throw 位置; /结点 p 不存在或结点 p 的后继结点不存在 else q=p-next; x=q-data; /暂存被删结点 p-next=q-next; /摘链 delete q;return x; template LinkList: LinkList(T a , int n)first=new Node;first-next=NULL; /初始化一个空链表for (i=0; in; i+)s=new Node; s-data=ai; /为每个数组元素建立一个结点 s-next=first-next;/插入
