实验3线性表的链式存储

《实验3线性表的链式存储》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验报告三线性表的链式存储班级：姓名：学号：专业：一、实验目的：（1）掌握单链表的基本操作的实现方法。（2）掌握循环单链表的基本操作实现。（3）掌握两有序链表的归并操作算法。二、实验内容：（请釆用模板类及模板函数实现）1、线性表链式存储结构及基本操作算法实现［实现提示］（同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义：（1）单链表存储结构类的定义：（2）初始化带头结点空单链表构造函数实现输入：无前置条件：

2、无动作：初始化一个带头结点的空链表输出：无后置条件：头指针指向头结点。（3）利用数组初始化带头结点的单链表构造函数实现输入：己存储数据的数组及数组中元素的个数前置条件：无动作：利用头插或尾插法创建带头结点的单链表输出：无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。（4）在带头结点单链表的第i个位置前插入元素e算法输入：插入位置i,待插入元素e前置条件：i的值要合法动作：在带头结点的单链表中第i个位置之前插入元素e输出：无后置条件：单链表中増加了一个结点（5）在带头结点单链表中删除第i个元素算法输入：删除第

3、i个结点，待存放删除结点值变量e前置条件：单链表不空，i的值要合法动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无后置条件：单链表中减少了一个结点（6）遍历单链表元素算法输入：无前置条件：单链表不空动作：遍历输出单链表中的各元素。输出：无后置条件：无（7）求单链表表长算法。输入：无前置条件：无动作：求单链表中元素个数。输出：返回元素个数后置条件：无（8）判单链表表空算法输入：无前置条件：无动作：判表是否为空。输出：为空时返回1,不为空时返回0后置条件：无（9）获得单链表中第i个结点的值算法输入：无

4、前置条件：i不空，i合法动作：找到第i个结点。输出：返回第i个结点的元素值。后置条件：无（10）删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无前置条件：单链表存在动作：清除单链表中所有的结点。输出：无后置条件：头指针指向空(11)上机实现以上基本操作，写出mainO程序:参考p72粘贴测试数据及运行结果：2、参考单链表操作定义与实现，自行完成单循环链表的类的定义与相操作操作算法。(1)利用数组初始化带头结点的单循环链表构造函数实现输入：己存储数据的数组及数组中元素的个数前置条件：无动作：利用头插或尾插法创建带头结

5、点的单循环链表输出：无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。(2)在带头结点单循环链表的第i个位置前插入元素e算法输入：插入位置i,待插入元素e前置条件：i的值要合法动作：在带头结点的单循环链表中第i个位置之前插入元素e输出：无后置条件：单循环链表中增加了一个结点(3)在带头结点单循环链表中删除第i个元素算法输入：删除第i个结点，待存放删除结点值变量e前置条件：单循环链表不空，i的值要合法动作：在带头结点的单循环链表中删除第i个结点，并返回该结点的值(由e传出)。输出：无后置条件：

6、单循环链表中减少了一个结点(4)遍历单循环链表元素算法输入：无前置条件：单循环链表不空动作：遍历输出单循环链表中的各元素。输出：无后置条件：无(5)上机实现以上基本操作，写出mainO程序:粘贴测试数据及运行结果:3、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc,该线性表仍有序(未考虑相同时删除一重复值)的算法。模板函数：main(){}粘贴测试数据及运行结果：选做题：1、按一元多项式ADT的定义，实现相关操作算法：ADTPNodeisData系数(coe

7、f)指数(exp)指针域(next):指向下一个结点Operation暂无endADTPNodeADTPolynomialisDataPNode类型的头指针。OperationPolynomail初始化值：无_动作：申请头结点，由头指针指向该头结点，并输入m项的系数和指数，建立一元多项式。DestroyPolyn输入：无前置条件：多项式己存在动作：消毁多项式。输出：无后置条件：头指针指向空PolyDisplay输入：无前置条件：多项式己存在，不为空动作：输出多项式各项系数与指数输出：无后置条件：无AddPoly输入：另一个待加的

8、多项式前置条件：一元多项式pa和pb己存在。动作及后置条件：完成多项式相加运算，（采用pa=pa+pb形式，并销毁一元多项式pb）输出：无endADTPolynomial2、实现一元多项式的减法，操作描述如下：SubPoly输入：待减的多项式pb前置条件：一元多