数据结构一元多项式课程设计报告.docVIP

PAGE PAGE 11 《数据结构课程设计》 报告 学 号： JV144033 姓 名： 朱凌 年 级： 2014级 专 业： 软件工程 指导老师： 施东东 黄晓梅 完成日期： 2016 年 9 月 安徽大学江淮学院 理工部 一元多项式计算 一、实验内容 （一元多项式的计算问题）要求能够按照指数降序排列建立并输出一元多项式；能够完成两个一元多项式的相加、相减，并将结果输入 二、需求分析 本程序关键点是如何将输入的两个多项式相加、相减操作。 = 1 \* GB3 ①如何将输入的一元多项式按指数的降序排列 = 2 \* GB3 ②如何确定要输入的多项式的项数； = 3 \* GB3 ③如何将输入的两个一元多项式显示出来。 = 4 \* GB3 ④如何将输入的两个一元多项式进行相加操作。 = 5 \* GB3 ⑤如何将输入的两个一元多项式进行相减操作。 本程序是通过链表实现一元多项式的相加减操作。 三、概要设计、详细设计 （1）多项式的输入  先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它； （2） 两个多项式的加法  “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下： 假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况： ①指针A所指结点的指数值指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去； ②指针A所指结点的指数值指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去； ③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加， 若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。 图2 相加得到的和多项式????上述多项式的相加过程归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的基本操作来完成。（3）两个多项式的减法  两个多项式的减法实现，依然调用的是多项式加法的函数，只是在调用前，把多项式二的系数全部变为相反数c.coef=-c.coef;，然后多项式一和多项式二相加，这样就实现了多项式的相减。流程图如上。 （4）两个多项式相加就是两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多形式”中的一项，所有指数不同的项均直接移位至“和多项式”中，流程图如图4： 1、算法思想： （1） 输入并建立多项式——InitList() （2） 输入多项式，输出形式为整数序列，这个输入功能在主函数实现（3） 多项式a和b相加，建立多项式a+b，输出相加的多项式——AddPolyn(A，B)（4） 多项式a和b相减，建立多项式a-b，相减的功能调用的依然是相加的子函数 2、算法描述： A:建立多项式链表 多项式单链表可以用尾插法建表来生成。 LNode *InitList()//创建链表 { LNode *L; L=(LNode*)malloc(sizeof(LNode)); L-next=NULL; return(L); } void ChaLNode(LNode *L,ElemType x)//插入链表函数 { LNode *s,*p; s=(LNode*)malloc(sizeof(LNode)); s-data=x; p=L; while(p-next) p=p-next; s-next=NULL; p-next=s; } B: 按照指数降序排列 void Invert(LNode *L)//逆序输出链表 {LNode *p,*q,*r; p=L-next; q=p-next; while(q!=NULL) {r=q-next; q-next=p; p=q; q=r; } L-next-next=NULL; L-next=p; } C：比较 if (a-expn b-expn)｛ pre=p; p=p-ne