数据与算法基础(数据结构)实验指导书

《数据与算法基础(数据结构)实验指导书》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、C据与算法基础(1)(数据结构)实验指导书重庆邮电大学软件工程学院2016-2017学年第一学期实验目的与要求—、实验目的数据结构是软件工程学科中一门非常重要的专业基础课程。当用汁算机来解决实际问题时，就要涉及到数据的存储表示及数据的处理，而数据存储表示及数据处理正是数据结构课程的主要研宄对象，通过这两方而内容的学习，为后续课程，特别是为软件方而的课程打丁厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构在软件工程学科及相关学科专业的课程体系屮具有极其重要的作川。本课程的任务是：通过实践

2、，学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会；能够快速确定数据的逻辑结构、并根据数据处理的类型和频度选择最佳的存储结构和算法组合。二、实验要求1.准备好上机所需要的C++程序，以提高上机效率。对程序中自己有疑问的地方应作记号,以便在上机时给予注意或获取教师指导。不得抄袭他人程序。2.上机输入并调试/运行所编写程序。3.上机结朿后，提交实验报告，实验报告应包括但不限于以下内容：⑴题0;(2)实验目的；(3)主要数裾结构

3、描述；(4)算法的基本思想描述；(5)算法时间复杂度分析；(6)运行的结果截图；(7)实验体会和收获；(8)程序清单。实验一顺序表的存储与操作一、实验目的1.理解线性表的逻辑结构；2.理解顺序表的存储结构特点，掌握顺序表的存储分配要点；3.掌握顺序表的基本操作及实现，并能正确分析其时间复杂度。二、实验内容1.定义顺序表的存储结构；2.顺序表的基本操作(1)初始化顺序表(无参和有参)；(2)求顺序表长度；(3)按位置查找；(4)按值查找；(5)在位置i插入一个数据元素；(6)删除位置i的数据元素；

4、(7)遍历顺序表；(8)销毁顺序表。三、算法思想和时间复杂度当我们耍在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。1.顺序表的存储结构和操作接口SeqList.h声明类SeqList，文件名为SeqList.h#ifndefSeqList_H#defineSeqList_HconstintMaxSize=100;//100

5、只是示例性的数据，可以根据实际问题具体定义template//定义模板类SeqListclassSeqListpublic:SeqList();//无参构造函数SeqList(Ta[],intn);//有参构造函数〜SeqList();//析构函数为空intLength();//求线性表的长度TGet(inti);//按位査找，取线性表的第i个元素intLocate(Tx);//按值查找，求线性表中值为X的元素序号voidInsert(inti,Tx);//在线性表中第i个位罝插

6、入值为X的元素TDelete(inti);//删除线性表的第i个元素voidPrintList();//遍历线性表，按序号依次输出各元素private:Tdata[MaxSize];//存放数据元素的数组intlength;//线性表的长度＞；#endif2.顺序表操作的实现//SeqList.cpp#includenSeqList.h"/功能：构建一个顺序表*输出：无*后置条件：构建一个顺序表*/templateSeqList::SeqList()*前賈条件：顺序表不存在

7、*输入：无}/**前置条件：顺序表不存在*输入：顺序表信息的数组形式aU，顺序表长度n*功能：将数组4］中元素建为长度为n的顺序表*输出：无*后罝条件：构建一个顺序表*/templateSeqList::SeqList(Tafl,intn)*前置条件：无*输入：无*功能：无*输出：无*后罝条件：无*/templateSeqList::〜SeqList()*前置条件：顺序表存在*输A：插入元素X，插入位置i*功能：将元素X插入到顺序表中位置i处*输出：无

8、*后置条件：顺序表插入新元素*/templatevoidSeqList::Insert(inti,Tx)/前置条件：顺序表存在*输入：查询元素位置i*功能：查找位置为i的元素并输出值*前置条件：顺序表存在*输入：要删除元素位罝i*功能：删除顺序表屮位置为i的元素*输出：无*后置条件：顺序表删除元素*/templateTSeqList::Delete(inti)}/**前置条件：顺序表存在*输入：无*功能：输出顺序表长度*输山：顺序表长度*后置条件：顺序