《安徽工程大学实验报告样本》由会员分享，可在线阅读，更多相关《安徽工程大学实验报告样本（6页珍藏版）》请在金锄头文库上搜索。
1、安 徽 工 程 大 学数数 据据 结结 构构 实实 验验 报报 告告班级 专业专业 10X 姓名 XXXXXX（学号）（学号） 同组者 / 成绩 日期 实验课的日期实验课的日期 指导教师 汪军汪军 实验名称实验名称 线性表及其应用一、实验目的一、实验目的熟练掌握线性表的顺序、链式存储结构的定义；以及在顺序、链式存储结构下基本操作的实现。熟练掌握线性表的动态分配存储空间的方法，以及指针的使用和应用。 二、需求分析二、需求分析1、分别定义数据元素为整型的线性结构的顺序存储方式和链式存储方式的类。2、在每种存储结构下类实现下面的方法：（1）构造函数；（2）析构函数；（3）在线性表插入一个元素；（4）
2、在线性表中删除一个元素；（5）求线性表的长度；（6）按序号取线性表的元素值； （7）按元素值检索查找线性表；（8）按序号检索查找线性表；（9）正序遍历线性表。（10）逆序遍历线性表。3、利用线性表实现两个有序线性表的合并操作三、系统设计三、系统设计（一）线性表的逻辑结构线性表 List 是 n 个具有相同数据类型的数据元素的集合。通常描述为：List =（e1，e2，ei-1，ei，ei+1，en） （n0）表中相邻元素之间存在着线性关系，第一个元素 e1 为首元素，无直接前驱；最后一个元素 en 为尾元素，无直接后继，其余元素都有前驱和后继元素。List 表中的数据元素类型相同，元素之间存在
3、前驱与后继关系。（二）线性表的顺序存储结构线性表的顺序存储是用内存中的一段地址连续的存储空间顺序存放线性表的每一个元素。它用存放内存中的地址物理上的相邻关系表示线性表中数据元素之间的先后关系，概括为顺序存储、随机存取。1、顺序表类定义#define DefaultListSize 256typedef int DataType;class CSeqListprivate:int ListSize;int ListLength;DataType* data;public:CSeqList( int size= DefaultListSize );CSeqList();bool Insert( i
4、nt,const DataType /在线性表插入一个元素；bool Delete( int,DataType /在线性表中删除一个元素；void Clear() ; /清空表bool Empty() const; /表是否为空int Length() const; /求线性表的长度；int Location(const DataType /按元素值检索查找线性表；void PositiveTravel() const; /正序遍历线性表void ReverseTravel() const; /正序遍历线性表; 2、顺序表类中主要方法的实现1）插入算法流程图：顺序表的插入操作：在表的第 i 个
5、位置上插入一个值为 x 的新元素，(1)检查待插入的表是否存在，若不存在退出；(2)判断顺序表是否满(即表长 length 是否大于等于 MAXSIZE)？若满，退出；否则执行(3)；(3)检查插入位置的合法性( i 满足 1=ListSize )return false;if (i ListLength+1) /检查插入位置的合法性return false;for(int j= ListLength-1; j=i-1; j-)dataj+1= dataj; /移动元素datai-1=Item; /新元素插入ListLength+;return true;.（三）线性表的链式存储结构线性表的链
6、式存储是线性表的每一个元素离散地存储在内存中，逻辑上相邻的元素之间的物理位置是通过指针的指向来实现。概括为随机存储、顺序存取。1、链表表类定义typedef struct LNodeDataType data;LNode *next;LNode,* LinkList;/class CLinkListprivate:LinkList Head;public:CLinkList();CLinkList();LinkList LocationNo(int ) const; /按序号检索查找线性表；bool Insert( int,const DataType /在线性表插入一个元素；bool Del
7、ete( int,DataType /在线性表中删除一个元素；void Clear() ; /清空表bool Empty() const; /表是否为空int Length() const; /求线性表的长度；LinkList Location(const DataType /按元素值检索查找线性表；void PositiveTravel() const; /正序遍历线性表void Reverse() ; /逆序void ReverseTravel() const; /逆序序遍历线性表;2、链表类中主要方法的实现1）按序号查找链表的按序号查找：找到表中第 i 个结点地址，算法流程图：从单链表的
8、第一个结点起，判断当前结点是否是第 i 个，若是，则返回该结点的指针，否则继续下一个结点的查找，直到表结束为止。若没有第个结点则返回空。(1)初始化从第一个结点开始，从 0 计数；(2) 判断当前结点是否是第 i 个，若是，则返回该结点的指针，否则继续下一个结点的查找，直到表结束，或者插入位置小于 0；(3)判断是否找到；(4)找到返回找到结点的地址，否则返回 NULL； 算法实现：LinkList CLinkList:LocationNo(int i ) constLinkList p;int j;p=Head;j=0;while (p j+;if ( j!=i | !p) return (NULL);elsereturn p; .四、调试与测试四、调试与测试1、主要是逻辑错误的调试过程记录（说明出错现象和分析原因以及解决的办法，错误直接用红色的笔在详细设计上改正）2、测试过程的设计和使用的测试数据及测试结果（1）插入算法 Insert_SeqList 的测试： 采用下面的数据，将算法的特殊情况都考虑在内进行全面测试算法 i1 插入元素 0 i表长 插入元素 -4 i表长 插入元素 5 i1 插入元素 12i表长与 1 之间的数 插入元素 124测试结果：经过测试，Insert_SeqList 在上述情况下均是正确，通过测试五、实验小结五、实验小结
