合肥学院
计算机科学与技术系
课程设计报告
2009～2010学年第2学期
课
程 数据结构与算法
二元多项式加减运算问题
课程设计名称 学学专指
业导
班教生
姓
名 号 级 师
陈康荫 0804012007 08计科系计本(2)班
王昆仑
2010年5月
题目：二元多项式加减运算问题
设计程序以实现降幂建立、输出、加、减任意两个二元多项式。要求：（1）所设计的
数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。
1、问题分析和任务定义
此程序需要完成以下的要求：按照指数降序排列建立多项式并且输出；能够完成两个多项式的相加、相减运算，并将结果输出。在这个程序中，我采用链表的数据结构来实现二元多项式的建立和表示。然后进行降序的排列，完成二元多项式的两个基本运算：加法和减法。最后同样按照降序，对得到的结果多项式进行排列，测试用例设置为二组，分别为：第一组为系数不同而x和y的指数各自相同；第二组为系数和指数各不相同。 举一个例子如下： 第一组数据：第二组数据：
6xy2xy23?5x?x24y33?8x77y23?7x52y47
7y4?5xy2?4xy
降幂排序后的结果： 第一组数据：第二组数据：
8xy73?5xy33?7xy27?6x?x2y343
5xy72?4x75y34?2x72y27y
4327233两组多项式相加结果：两组多项式相减结果：
8xy?5xy?4xy?5xy?9xy?xy?6xy5
8xy7?5x7y?4x5y4?5x4y3?5x2y7?x2y3?6xy3
现在，我要通过程序来实现以上的过程将其在计算机上完成运算最终成功得到这样的结果。
2、数据结构的选择和概要设计
为了解决这个问题，我选择的数据结构为链表，原因是：链表中的结点可以动态生成的，用链表结构可以灵活地添加或删除结点。另外，用链表结构来存储这样的数据可以大大地减少空间复杂度，因此本题在设计算法时使用的就是链表地结构，存放多项式的链表结点结构如下图如示： 系数 coef X的指数 xexp Y的指数 yexp 指针 next 图1.存放多项式的链表结点结构 struct LinkList{
int coef; //系数 int xexp; //x指数 int yexp; //y指数 LinkList *next; //指针 }; //定义结点 这是链表的最基本的构成单元——结点。
在输入多项式时，考虑到输入多项式的形式，本程序是分别输入各个多项式中每一个项的系数，x指数,y指数，然后在输出时再把多项式的各个关键字组合在一起。 建立链表的时候，通过定义MAX的值就可以一次性地告诉计算机，本次运行程序需要开辟空间的大小。同时可以改变相应的MAX大小，来改变其空间的大小。由于是2个多项式相加相减的运算，所以设定MAX1和MAX2分别来定义。然而，二元多项式的加减在运算中难免会遇到两种极端情况，即：没有一个是同类项或者全是同类项。如果遇到“没有一个是同类项”的情况，那么，运算后的这个链表的长度就是原来的2个多项式之和，所以直接将运算后得到的链表长度开辟的空间定义为MAX1+MAX2，已免出现溢出错误。在这一点上，链表的
插入结点的操作简单的优势就体现出来了，然而对于减法的情况，同理，合并同类项的工作对于多项式来说也就是结点的删除工作。
本程序的几个重要的问题按顺序是： 1、建立链表
2、多项式的输入形式、显示以及显示的形式 3、如何按降序排序 4、多项式加法函数 5、多项式减法函数 6、选择菜单。
以上这六个问题需要最终分别用几个函数来分别实现。另外加上一个主函数。这几个函数分别为：
void CreateList(LinkList *&L,int a[],int b[],int c[], int n) //创建链表 void sort(LinkList *&L) //降序排序
void ListAdd(LinkList *&L1,LinkList *&L2,LinkList *&L3) //两个多项式相加 void ListSubtract(LinkList *&L1,LinkList *&L2,LinkList *&L3) void DisplayList(LinkList *&L) //显示多项式 int menu_select()//菜单
这些函数连同主函数在一起构成整个程序，其中，主函数依次调用建表函数、排序函数、显示函数、菜单函数，菜单函数提示用户选择来调用加法函数和减法函数，加法函数和减法函数中都分别依次调用建表函数、排序函数和显示函数，另外菜单函数还自己调用自己，即递归的调用。
3、详细设计和编码
本程序的有6个模块，分别为1、建表 2、排序 3、加法 4、减法 5、显示 6、选择。 各模块的详细分析设计如下：
1、建表
多项式的存储的数据结构采用的是链表的方式： 系数 cofe X的指数 xexp Y的指数 yexp 指针 next 存放多项式的链表结点结构 对于输入的2个多项式，都采用链表的存储方式，运算后的多项式也一样地采用这种方式来存储。在建立链表结构时，根据题目的情况，我选择了头插法来建立链表，算法为：首先建立一个只含有头结点的空单链表，然后读入数据，生成新结点，并将新结点总是插入到头结点之后，直到读满之前设置的链表的长度。系数，x指数，y指数分别用a[],x[],y[]三个数组的形式进行读入。
头插法建单链表的算法时间复杂度为O(n)。
创建链表函数为：
void CreateList(LinkList *&L,int a[],int x[],int y[], int n)//定义三个数组用于存储系数、x指数、y指数
{LinkList *s; int i;
L=(LinkList *)malloc(sizeof(LinkList));//开辟空间存放链表 L->next=NULL; for(i=0;i
L->next=s; } }
2、排序
降序排序函数的主要算法思想：先检查p 结点是不是最后一个结点，如果不是，就向后继续查找，直到找到最后一个结点，把这个结点中的指数和前一个结点中的指数进行比较，如果这个指数比前一个结点的指数大，说明这两个结点按升序排列，需要改变位置，于是执行指针的变换操作，使得两个结点改成降序排列，以此达到排序的目的。
以下是排序函数： //降序排序
void sort(LinkList *&L) {
LinkList *p=L->next,*q,*r; if(p!=NULL) {
r=p->next; p->next=NULL; p=r;
while(p!=NULL) {
r=p->next; q=L;
while(q->next!=NULL&&((q->next->xexp>p->xexp)||(q->next->xexp==p->xexp&&q->next->yexp>p->yexp)))
q=q->next; p->next=q->next; q->next=p; p=r; } }
3、加法
两个多项式相加的算法是：两个多项式中，具有相同指数项的，也就是同类项的对应系数相加，若相加和不为零，则合并成加和多项式中的一项，所有指数不相同的项均直接移动至加和多项式中的后面，至于排列，则依据排序函数进行降序排序。
对于两个多项式链表A和B，实现多项式相加时，加和多项式中的结点无需另外生成，可以看成是将多项式B加到多项式A中，最后的加和多项式即是新的多项式A，设p、q分别指向多项式A、B的首元素结点，则比较结点*p、*q的指数项，可以进行以下操作来完成多项式的加法运算：
① 若p->exp
② 若p->exp>q->exp，则*q结点应是加和多项式的一项，将*q结点插入到多项式链表A的*p结点之前，并令指针q在多项式链表B上后移。
③ 若p->exp=q->exp，则将两个结点的系数相加，若和不为零，则修改*p结点的系数域，释放指针q所指向的结点空间；若和为零，则指针p、q分别在各自的链表上后移，同时释放原先两个指针所指向的结点空间。
④ 重复上述步骤，若q=NULL，则链表A即为加和多项式链表；若p=NULL，则将链表B中指针q所指向的余下的链表全部插入到链表A的表尾，形成加和多项式链表A.
⑤ 由于这个题目是二元多项式，要考虑x和y两个元，故而以上四个步骤在实际写程序的时候是按照xexp和yexp两个变量而不是只有一个exp，写成exp是为了说明的时候看得清楚一点。加法算法的时间复杂度取决于链表A和B的项数，若A有n项,B有m项，那
么上述算法的时间复杂度为O(n+m).
以下是两个多项式相加函数： //两个多项式相加
void ListAdd(LinkList *&L1,LinkList *&L2,LinkList *&L3) {
int coef[MAX1+MAX2],xexp[MAX1+MAX2],yexp[MAX1+MAX2],i=0; //MAX1+MAX2的原因是防止两个多项式中没有任何一个相同
LinkList *p=L1->next,*q=L2->next; while(p!=NULL&&q!=NULL) {
if(p->xexp
else if(p->xexp>q->xexp) { coef[i]=q->coef; xexp[i]=q->xexp; yexp[i]=q->yexp; i++; q=q->next; } else if(p->xexp==q->xexp&&p->yexp
p=p->next; q=q->next; }