两个多项式相加试验报告-read.docVIP

两个多项式相加实验报告 班级 ：计科021 姓名：罗晶晶 学号：0207110183 日期：2005/5/10 主要实验内容：根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 运行环境 ：visual C++ 需求分析 掌握线性结构的逻辑特性和物理特性 掌握线性结构的各种相关算法 掌握将算法转换成程序的方法和步骤 掌握采用线性结构解决实际问题。 概要设计 抽象数据类型一元多项式的定义如下： ADT Polynomial { 数据对象：D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 } 数据关系：R1＝{ ai-1 ,ai |ai-1 ,ai∈D, i=2,...,n， 且ai-1中的指数值＜ai中的指数值} 基本操作： CreatPolyn ( P, m ) 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。 DestroyPolyn ( P ) 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。 PrintPolyn ( P ) 初始条件：一元多项式 P 已存在。 操作结果：打印输出一元多项式 P。 PolynLength( P ) 初始条件：一元多项式 P 已存在。 操作结果：返回一元多项式 P 中的项数。 AddPolyn ( Pa, Pb ) 初始条件：一元多项式 Pa 和 Pb 已存在。 操作结果：完成多项式相加运算，即： Pa = Pa＋Pb，并销毁一元多项式 Pb。 SubtractPolyn ( Pa, Pb ) … … } ADT Polynomial 2、一元多项式的实现： typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 term, ElemType; 详细设计 线性表的应用--多项式相加问题 多项式的相加操作是线性表处理的典型例子。在数学上，一个多项式可写成下列形式： P（x）=anxn+an-1x n-1+ … +a1x+a0 (其中ai为xi的非零系数) 在多项式相加时，至少有两个或两个以上的多项式同时并存，而且在实现运算的过程中所产生的中间多项式和结果多项式的项数和次数都是难以预料的。因此计算机实现时，可采用单链表来表示。多项式中的每一项为单链表中的一个结点，每个结点包含三个域：系数域、指数域和指针域，其形式如下： 现在设有两个多项式： A(x)=12+3x2+5x3+8x4 B(x)=5+6x5 它们的链表结构见图2-5-1。 图2-5-1 多项式的单链表结构 下面是一个完整的C程序，包含三个算法：PolyAdd、Creat_Linkst和Print_Linkst。 核心算法PolyAdd是把分别由pa和pb所指的两个多项式相加，结果为pa所指的多项式。相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描(见图2-5-1)，比较qa和qb所指结点指数域的值，可能出现下列三种情况之一： （1）qa-exp大于qb-exp,则qa继续向后扫描。 （2）qa-exp等于qb-exp,则将其系数相加。若相加结果不为零，将结果放入qa-coef中，并删除qb所指结点，否则同时删除qa和qb所指结点。然后qa、qb继续向后扫描。 （3）qa-exp小于qb-exp,则将qb所指结点插入qa所指结点之前，然后qa、qb继续向后扫描。 扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果链表上。所得pa指向的链表即为两个多项式之和。 算法 Creat_Linkst是建立表示多项式的单链表。建立链表的过程是一个动态生成的过程，即从“空表”的初始状态起，依次输入数据元素，每输入一个就生成一个新结点并插入到表尾。为了方便新结点的插入，算法中设置一个指针pre使其始终指向当前链表的表尾结点，初始指向pa(见图2-5-1)。 测试数据及结果： 源程序（带注释） #include s