安徽工程大学实验报告样本

《安徽工程大学实验报告样本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安徽工程大学数据结构实验报告班级专业10X姓名XXXXXX（学号）同组者/成绩日期实验课的日期指导教师汪军实验名称线性表及其应用一、实验目的熟练掌握线性表的顺序、链式存储结构的定义；以及在顺序、链式存储结构下基本操作的实现。熟练掌握线性表的动态分配存储空间的方法，以及指针的使用和应用。二、需求分析1、分别定义数据元素为整型的线性结构的顺序存储方式和链式存储方式的类。2、在每种存储结构下类实现下面的方法：（1）构造函数；（2）析构函数；（3）在线性表插入一个元素；（4）在线性表中删除一个元素；（5）求线性

2、表的长度；（6）按序号取线性表的元素值；（7）按元素值检索查找线性表；（8）按序号检索查找线性表；（9）正序遍历线性表。（10）逆序遍历线性表。3、利用线性表实现两个有序线性表的合并操作三、系统设计（一）线性表的逻辑结构线性表List是n个具有相同数据类型的数据元素的集合。通常描述为：List=（e1，e2，…，ei-1，ei，ei+1，…，en）（n≥0）表中相邻元素之间存在着线性关系，第一个元素e1为首元素，无直接前驱；最后一个元素en为尾元素，无直接后继，其余元素都有前驱和后继元素。List表中的

3、数据元素类型相同，元素之间存在前驱与后继关系。（二）线性表的顺序存储结构线性表的顺序存储是用内存中的一段地址连续的存储空间顺序存放线性表的每一个元素。它用存放内存中的地址物理上的相邻关系表示线性表中数据元素之间的先后关系，概括为顺序存储、随机存取。1、顺序表类定义#defineDefaultListSize256typedefintDataType;classCSeqList{private:intListSize;intListLength;DataType*data;public:CSeqList(

4、intsize=DefaultListSize);~CSeqList();boolInsert(int,constDataType&);//在线性表插入一个元素；boolDelete(int,DataType&);//在线性表中删除一个元素；voidClear();//清空表boolEmpty()const;//表是否为空intLength()const;//求线性表的长度；intLocation(constDataType&)const;//按元素值检索查找线性表；voidPositiveTravel

5、()const;//正序遍历线性表voidReverseTravel()const;//正序遍历线性表};2、顺序表类中主要方法的实现1）插入算法流程图：顺序表的插入操作：在表的第i个位置上插入一个值为x的新元素，(1)检查待插入的表是否存在，若不存在退出；(2)判断顺序表是否满(即表长length是否大于等于MAXSIZE)？若满，退出；否则执行(3)；(3)检查插入位置的合法性(i满足1<=i<=length+1)。若不满足，退出；否则执行(4)；(4)将第i元素到第length元素顺序向下移动一位

6、，为新元素的插入腾出位置；(5)将x置入第i位置；(6)修改表长；算法实现：boolCSeqList::Insert(inti,DataTypeconst&Item){/*顺序表插入，入口参数：顺序表指针，插入位置，插入元素，返回标志，1表示成功，0表示插入位置不合法，-1表示溢出，-2表示表不存在*/if(ListLength>=ListSize)returnfalse;if(i<1

7、

8、i>ListLength+1)//检查插入位置的合法性returnfalse;for(intj=ListLength

9、-1;j>=i-1;j--)data[j+1]=data[j];//移动元素data[i-1]=Item;//新元素插入ListLength++;returntrue;}…...…...…...（三）线性表的链式存储结构线性表的链式存储是线性表的每一个元素离散地存储在内存中，逻辑上相邻的元素之间的物理位置是通过指针的指向来实现。概括为随机存储、顺序存取。1、链表表类定义typedefstructLNode{DataTypedata;LNode*next;}LNode,*LinkList;////////

10、//////////////////////////////////classCLinkList{private:LinkListHead;public:CLinkList();~CLinkList();LinkListLocationNo(int)const;//按序号检索查找线性表；boolInsert(int,constDataType&);//在线性表插入一个元素；boolDelete(int,DataType&);//在线性表中删