《数据结构》协同作业试验项目文档—— 第二组.doc

上海交通大学网络教育 数据结构协同作业实验 线性表 1 顺序表操作验证 2 1.1 实验目的 2 1.2 实验内容 2 2 一元多项式相加实验 2 3 开发环境 2 4 算法设计介绍 3 4.1 设计思路 3 4.2 详细设计 6 5 界面流程展示 7 6 检查及测试报告 9 6.1 检查报告 9 6.2 测试报告 9 7 附程序源代码 10 7.1 一元多项式验证： 10 7.2 顺序表操作验证： 17  顺序表操作验证 实验目的 掌握线性表的顺序存储结构； 验证顺序表及其基本操作的实现； 掌握数据结构及算法的程序实现的基本方法。 实验内容 建立含有若干个元素的顺序表； 对已建立的顺序表实现插入、删除、查找等基本操作。 一元多项式相加已知 A( x )= a0 + a1x + a2x2 + …… + anxn 和B(x) = 0 + b1x + b2x2 +…… + amxm ，并在 A( x ) 和 B( x ) 中指数相差很多，求 A( x ) = A( x ) + B(x) 。软件平台Windows XP 软件环境：Microsoft Visual C++ 6.0 最低硬件配置：内存64MB、硬盘3.2G 算法设计介绍 设计思路 分析: 1．存储结构分析 根据一元多项式的特点，要表示一个多项式，只要存储第i项以及ai的值，并且如果ai为0的话，该项就不用存储了，从而减少一个存储空间。在线性表中可以通过顺序和链式存储，并用Ti表示一个数据项Ti=（ai,i）。下面以图示表示两种存储结构(假设a2=0)。 图1 顺序存储表 图2 单链表存储 以上两个图可知，在存储空间分配量上两种结构是一致的，但如果两多项式相加的话需要频繁的做插入操作，顺序表的结构特性决定了插入操作的时间复杂度为O(n/2)，链式表的时间复杂度为O(1)，并且如果存储的是一个排好序的多项式的话，不需要双向查找，因此选择单链表存储。 2．相加算法分析 首先，由于两个多项式A(x)和B(x)的指数相差非常多，因此一定要把输入的多项式按照指数i排好序，防止过高的查找时间复杂度；其次，两个AB多项式同时从head开始查找，AB指数i相同的计算相加ai值存入A表，并且回收不需要的B空间，指数不同的，B指数小的节点插到A指数大的前面。以此往后推移。其时间复杂度为O(n)。 举例： A(x)=2+3x+1x3 B(x)=1+3x+2x2+2x4+12x7+32x8+42x11+2x12 整个相加过程如下： 见注释1 图3 初始化后的A(x) pA=headA 图4 初始化后的B(x) pB=HeadB-next 第一步： 图5 A(x) pA-next系数＋pB系数 图6 B(x) pA-next指数0与pB指数0相等 free pB所指节点 第二步与第一步做法一致 第三步 将pB的节点插入pA后 第四步pA-next指数小于pB指数,pA=pA-next， pB不动 第五步pA没有后继节点，直接把pB的所有节点接到pA后即可  详细设计 数据结构 typedef struct term { float coef; //系数 int expn; //指数 struct term *next //指向下一节点 } term 输入输出 输入：两个多项式A,B 输出：A+B 样式： 输入一元多项式的项数 2 请依次输入非零2个非零项，请注意输入格式 2 2 3 3 3X^3+2X^2 1~4 （+ - * 退出）4个选项 再输入一元多项式的项数 3 请依次输入非零3个非零项，请注意输入格式 2 2 3 3 4 4 3X^3+2X^2 + 4X^4+3X^3+2X^2 = 4X^4+6X^3+4X^2 函数原型 主函数：void main() 输入函数: InputPolynomial(LinkList p) 多项式相加函数: term* APolyn(term *Pa, term *Pb) 多项式相减函数: term* BPolyn(term *Pa, term *Pb) 多项式相乘函数: term* CPolyn(term *Pa, term *Pb) 输出函数: void PrintfPoly(term *P)  界面流程展示 第一步：先输入第一个“一元多项式的项数” 第二步，根据一元多项式的项数，输入非零项。注意输入格式，系数和指数之间要有空格。第三步，选择要进行的运算方式编码 第四步，再输入第二个“一元多项式的项数”，方式如第二步一致，最后回车进行运算  检查及测试报告 检查报告 检查名称 检查任务 完成情况 是 否 安装 程序运