数据结构实验指导一.doc

实验一线性表实验目的线性表是最简单、最常用的基本数据结构在实际问题中有着广泛的应用。通过本章的实验巩固对线性表逻辑结构的理解掌握线性表的存储结构及基本操作的实现为应用线性表解决实际问题奠定良好的基础并进一步培养以线性表作为数据结构解决实际问题的应用能力。（1）掌握线性表的顺序存储结构；（2）验证顺序表及其基本操作的实现；（3）掌握数据结构及算法的程序实现的基本方法。（4）掌握线性表的链接存储结构；（5）验证单链表及其基本操作的实现；（6）进一步掌握数据结构及算法的程序实现的基本方法。二、实验示例学习——顺序表操作实验要求：（1）建立含有若干个元素的顺序表；（2）对已建立的顺序表实现插入、删除、查找等基本操作。实现提示：首先定义顺序表的数据类型——顺序表类SeqList包括题目要求的插入、删除、查找等基本操作为便于查看操作结果设计一个输出函数依次输出顺序表的元素。constintMaxSize=10;template<classT>//定义模板类SeqListclassSeqList{public:SeqList(){length=0;}//无参构造函数SeqList(Ta[]intn);//有参构造函数voidInsert(intiTx);//在线性表中第i个位置插入值为x的元素TDelete(inti);//删除线性表的第i个元素intLocate(Tx);//按值查找求线性表中值为x的元素序号voidPrintList();//遍历线性表按序号依次输出各元素private:Tdata[MaxSize];//存放数据元素的数组intlength;//线性表的长度};其次建立含有n个数据元素的顺序表即设计构造函数。算法如下：template<classT>SeqList::SeqList(Ta[]intn){if(n>MaxSize)throw"参数非法";for(i=0;i<n;i++)data[i]=a[i];length=n;}最后对建立的顺序表设计插入、删除、查找等基本操作的算法。（1）插入算法template<classT>voidSeqList::Insert(intiTx){if(length>=MaxSize)throw"上溢";if(i<1||i>length+1)throw"位置";for(j=length;j>=i;j--)data[j]=data[j-1];//注意第j个元素存在数组下标为j-1处data[i-1]=x;length++;}（2）删除算法template<classT>TSeqList::Delete(inti){if(length==0)throw"下溢";if(i<1||i>length)throw"位置";x=data[i-1];for(j=i;j<length;j++)data[j-1]=data[j];//注意此处j已经是元素所在的数组下标length--;returnx;}（3）查找算法template<classT>intSeqList::Locate(Tx){for(i=0;i<length;i++)if(data[i]==x)returni+1;//下标为i的元素等于x返回其序号i+1return0;//退出循环说明查找失败}实验程序：//以下为头文件文件名为SeqList.h#ifndefSeqList_H#defineSeqList_HconstintMaxSize=100;//100只是示例性的数据可以根据实际问题具体定义template<classT>//定义模板类SeqListclassSeqList{public:SeqList(){length=0;}//无参构造函数创建一个空表SeqList(Ta[]intn);//有参构造函数voidInsert(intiTx);//在线性表中第i个位置插入值为x的元素TDelete(inti);//删除线性表的第i个元素intLocate(Tx);//按值查找求线性表中值为x的元素序号