实验3线性表的链式存储.docVIP

实验报告三 线性表的链式存储 班级： 姓名： 学号： 专业： 实验目的： 掌握单链表的基本操作的实现方法。 掌握循环单链表的基本操作实现。 掌握两有序链表的归并操作算法。 实验内容：（请采用模板类及模板函数实现） 1、线性表链式存储结构及基本操作算法实现 [实现提示] （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。 所加载的库函数或常量定义： （1）单链表存储结构类的定义： （2）初始化带头结点空单链表构造函数实现 输入：无 前置条件：无 动作：初始化一个带头结点的空链表 输出：无 后置条件：头指针指向头结点。 （３）利用数组初始化带头结点的单链表构造函数实现 输入：已存储数据的数组及数组中元素的个数 前置条件：无 动作：利用头插或尾插法创建带头结点的单链表 输出：无 后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。 （４）在带头结点单链表的第i个位置前插入元素e算法 输入：插入位置i，待插入元素e 前置条件：i的值要合法 动作：在带头结点的单链表中第i个位置之前插入元素e 输出：无 后置条件：单链表中增加了一个结点 （５）在带头结点单链表中删除第i个元素算法 输入：删除第i个结点，待存放删除结点值变量e 前置条件：单链表不空，i的值要合法 动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。 输出：无 后置条件：单链表中减少了一个结点 （６）遍历单链表元素算法 输入：无 前置条件：单链表不空 动作：遍历输出单链表中的各元素。 输出：无 后置条件：无 （７）求单链表表长算法。 输入：无 前置条件：无 动作：求单链表中元素个数。 输出：返回元素个数 后置条件：无 （８）判单链表表空算法 输入：无 前置条件：无 动作：判表是否为空。 输出：为空时返回１，不为空时返回0 后置条件：无 （９）获得单链表中第i个结点的值算法 输入：无 前置条件：i不空，i合法 动??：找到第i个结点。 输出：返回第i个结点的元素值。 后置条件：无 (10)删除链表中所有结点算法（这里不是析构函数，但功能相同） 输入：无 前置条件：单链表存在 动作：清除单链表中所有的结点。 输出：无 后置条件：头指针指向空 (11)上机实现以上基本操作，写出main()程序： 参考p72 粘贴测试数据及运行结果： 2、参考单链表操作定义与实现，自行完成单循环链表的类的定义与相操作操作算法。 （１）利用数组初始化带头结点的单循环链表构造函数实现 输入：已存储数据的数组及数组中元素的个数 前置条件：无 动作：利用头插或尾插法创建带头结点的单循环链表 输出：无 后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。 （２）在带头结点单循环链表的第i个位置前插入元素e算法 输入：插入位置i，待插入元素e 前置条件：i的值要合法 动作：在带头结点的单循环链表中第i个位置之前插入元素e 输出：无 后置条件：单循环链表中增加了一个结点 （３）在带头结点单循环链表中删除第i个元素算法 输入：删除第i个结点，待存放删除结点值变量e 前置条件：单循环链表不空，i的值要合法 动作：在带头结点的单循环链表中删除第i个结点，并返回该结点的值（由e传出）。 输出：无 后置条件：单循环链表中减少了一个结点 （４）遍历单循环链表元素算法 输入：无 前置条件：单循环链表不空 动作：遍历输出单循环链表中的各元素。 输出：无 后置条件：无 (５)上机实现以上基本操作，写出main()程序： 粘贴测试数据及运行结果： ３、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc，该线性表仍有序（未考虑相同时删除一重复值）的算法。 模板函数： main() { } 粘贴测试数据及运行结果： 选做题： １、按一元多项式ADT的定义，实现相关操作算法： ADT PNode is Data 系数(coef) 指数(exp) 指针域(next):指向下一个结点 Operation 暂无 end ADT PNode ADT Polynomial is Data PNode类型的头指针。 Operation　 　 Polynomail 初始化值：无 　 动作：申请头结点，由头指针指向该头结点，并输入m项的系数和指数，建立一元多项式。 　 DestroyPolyn 输入：无 前置条件： 多项式已存在 动作：消毁多项式。 输出：无 后置条件：头指针指向空 　 Pol