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

《数据结构一元多项式课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构课程设计》报告学号：JV144033姓名：朱凌年级：2014级专业：软件T程指导老师：施东东黄晓梅完成日期：2016年9M安徽大学江淮学院理工部一元多项式计算一、实验内容(一元多项式的计算问题)要求能够按照指数降序排列建立并输出一元多项式；能够完成两个一元多项式的相加、相减，并将结果输入二、需求分析本程序关键点是如何将输入的两个多项式相加、相减操作。①如何将输入的一元多项式按指数的降序排列②如何确定要输入的多项式的项数；③如何将输入的两个一元多项式显示出來。④如何将输入的两个一元多项式进行相加操作。⑤如何将输入的两个一元多项式进行相减操作。木程序是通过链表实现-元多项式的相加减操

2、作。三、概要设计、详细设计(1)多项式的输入先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；(2)两个多项式的加法“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表小摘取。其运算规则如下：假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：①指针A所指结点的指数值〈指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去；②指针A所指结点的指数值〉指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去；③指针A所指

3、结点的指数值二指针B所指结点的指数值，则将两个结点中的系数相加,若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2屮的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。图2相加得到的和多项式上述多项式的和加过程归并两个有序表的过程极其类似，不同Z处仅在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的基本操作來完成。(1)两个多项式的减法两个多项式的减法实现，依然调用的是多项式加法的函数，只是在调用前，把多项式二的系数全部变为相反

4、数c.cocf=-c.cocf；,然后多项式一和多项式二相加，这样就实现了多项式的相减。流程图如上。(2)两个多项式相加就是两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多形式”中的一项，所有指数不同的项均直接移位至“和多项式”中，流程图如图4：1、算法思想：(1)输入并建立多项式——InitList()(2)输入多项式，输出形式为整数序列，这个输入功能在主函数实现(3)多项式a和b相加，建立多项式a+b,输出相加的多项式——AddPolyn(A,B)(4)多项式。和b相减，建立多项式d-b,相减的功能调用的依然是相加的子函数2、算法描述:A:建立多项式链表多项式单链表可以用尾

5、插法建表来生成。LNode*InitList()//创建链表{LNode*L;L=(LNode*)malloc(sizeof(LNode));L->next=NULL;return(L);}voidChaLNode(LNode*L,ElemTypex)//插入链表函数{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:按照指数降序排列voidInvert(LNode*L)//逆序输出链表{LNode*p，*q，*r;p=L->n

6、cxt;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->expnexpn){pre=p;p二p->next;}〃如果多项式a的指数小于多项式b的指数，则指针P后移if(a->expn>b->expn){pre~>next=q;prc=prc->ncxt;q=q->next;}//如果多项式a的指数小于多项式b的指数，q后移这个模块主要是比较两个多项式的指数大小D、两个一元多项式的相加while(p&&q)//判断q,P是不是为空，如果不为空则继续

7、往下进行{a=p->data.expn;b=q->data.expn;if(anext;//p后移}if(a==b){sum=p->data.coef+q->data.coef;//当a,b相等，即指数相同，则系数相加if(sum!=0)//判断sum是为0,如果不为0则保留该节点{p->data・coef二sum;B=q;pre二p;p二p—>next;q二q->next；free(B);