数据结构程序设计作业——《一元多项式的四则运算》.docVIP

数据结构实验报告 题　　目　　一元多项式四则运算 　　　 学生姓名　　王某某　　　　　　 专业班级　　测控120X班　　　 学 号　　U2012XXXXX　　　　 1 问题描述 利用已学过的数据结构来构造二个存储多项式的结构，接着把输入，加，减，乘，除运算分成四个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。最后，编写main主函数以实现对多项式输入输出以及加、减、乘、除。 2 相关函数介绍说明 （1）程序定义的数据结构类型为线性表的链式存储结构类型变量： typedef struct linknode （2）程序定义的其它函数： linnode *Sort(linnode *S); //多项式按指数从大到小排序 linnode *CreateList(); //创建多项式 Void ShowList(linnode *head) ; //显示多项式 linnode *Copy(linnode *copy); //拷贝多项式（因为做减法运算时会破坏原来输入的多项式） linnode *SearchList(linnode *head,int x); //查找函数 Linnode *Mulr(linnode *s,linnode *p) //用一个节点去乘与一个多项式（辅助除法运算） Linnode *AddSame(linnode *head); //和并多项式的同类项 linnode *Add(linnode *head1,linnode *head2); // 加法 linnode *Mul(linnode *head1,linnode *head2); // 乘法 linnode *Sub(linnode *head1,linnode *head2); // 减法 Void Div(linnode *head1,linnode *head2) //除法 int main( ) //主函数 3 程序设计 3.1 多项式存储的实现 多项式是由若干项构成的一个数学式子，其每一项包含系数与指数。然而我们可以把每一项看成是一个节点，再由这些节点连接成多项式。根据所学数据结构，采用线性表的链式存储来存储多项式的每一个项的系数与指数。其结构为： typedef struct linknode //链表节点的结构体 { float coe; //系数 int index; //指数 struct linknode *next; }linnode; 3.2 加减乘除算法 在多项式运算的程序设计中，每一部分都会调用一些其它函数来辅助完成运算（例如：对输入的多项式进行排序，查找，合并等），在这里主要说明加减乘除运算的程序设计，其它函数的程序设计和具体调用关系请查看程序清单。 3.2.1加法运算的实现 加法计算还是比较容易的， 对于加法运算我们并不用考虑多项式是否为空的情况，为空时连接后合并同类项处理后仍然返回空的多项式。 3.2.2减法运算的实现 多项式的减法与加法类似，先将传递进来的两个多项式进行判断是否为空，若被减数为空时，减数按逐项系数取反操作。不为空时，被减数的每一项的指数去查找减数中与之对应的项，找到后并同类项相减，把值赋给被减数与之对应的同类项，再在减数中删除查找到的那个项（节点）。彻底查找后，将减数剩余的节点取反后再连接到被减数的末尾，在进行合并同类项操作并返回头指针。 是 否 找到 未找到 3.2.3乘法运算的实现 多项式的乘法运算，首先是判断多项式都不为空，为空时直接输出结过为0。否则将其中一个多项式的每一项去乘于另外个多项式的每一项，将乘得每一项的结果连接成一个完整的多项式，然后在对其进行合并同类项操作。最后返回结果头指针。 否 是 3.2.4除法运算的实现 首先将相除的两个多项式降序排列，两个多项式为非空时。判断被除数的最高次幂大于或等于除数的最高次幂，然后用被除数的第一项去除于除数的第一项所得商的第一项，在用所得商的这一项去乘除数的所有项所得的多项式与被减数作差，在用所得差作为被减数。循环上述步骤，当被减数最高次幂小于减数最高次幂是终止循环，输出相应的结果。 否 是 否 是 在程序设计时应注意: 由于在输入多项式的时候就调用了Sort（）函数进行降序排序，因此在除法