实习一线性表及其应用题目：一元稀疏多项式的加法运算

1、实习一线性表及其应用(题目：一元稀疏多项式的加法运算)一、需求分析1 .输入并建立两个多项式；2 .多项式a与b相加，建立和多项式c；3 .输出多项式abco输出格式：比如多项式a为：A(x)=c1xe1+c2xe2+cmxem其中，ci和ei分别为第i项的系数和指数，且各项按指数的开幕排列，即0<e1e2<-<em0多项式bc类似输出。4测试数据(1) (1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(2) (x+x100)+(x100+x200)=(x+2x100+x200)(3) (2x+5x8-3x11)+(7-5x8+11x9)=(7+2

2、x+11x9-3x11)实习一线性表及其应用题目：一元稀疏多项式的加法运算实习时间：2012/9/20.10.12一、需求分析1 .输入并建立两个多项式；2 .多项式a与b相加，建立和多项式c；3 .输出多项式abc0输出格式：比如多项式a为：A(x)=c1xe1+c2xe2+cmxem其中，ci和ei分别为第i项的系数和指数，且各项按指数的开幕排列，即0<e1e2<-<em0多项式bc类似输出。4测试数据(1) (1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(2) (x+x100)+(x100+x200)=(x+2x100+x200)(3) (

3、2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)二、设计1.设计思想(1)存储结构用带头结点的单链表存储多项式。三个多项式链表中都只存储非零系数项。若多项式a与b中指数相等的两项相加后，系数为零，则在和多项式c中不存储该指数项。(2)主要算法基本思想按照链表的基本操作，初始化三个链表，在两个链表中按指数由小到大分别插入a和b的多项式(系数和指数)，将多项式a的链表复制给多项式c的链表,再调用求和函数(b的链表和c的链表相加)，将求和的结果插入到c的链表中(作为多项式c)最后输出多项式a,b,c三个多项式。11插入函数：设计按多项式指数的从小到大插入。从第一个

4、元素开始判断，直到遇到比插入元素更大的指数或链表尾为止，再进行插入操作。2求和函数：先将多项式a的链表复制给多项式c的链表，在b的链表不为空的前提下，将b中的各项的指数与c中各项的指数比较大小。(1)若相等，就将该项的系数相加，和不为零就将c中该项的系数替换为其和(何若为零则删除该节点)。(2)若b中的指数大，就在c链表该节点之前插入b项的此节点。(3)若b中的指数小，就一直查找到c链表尾。再将多余的b链表一起复制给c链表。【3】输出函数(系数为0的项已被删除)：多项式第一项若为正数，无需符号，其余项带符号输出(定义一个开关变量)(1) 系数为a,指数b为0的项输出(a)。(2) 系数a为1,

5、指数b为1的项输出(x)。(3) 系数a为1,指数b不为1的项输出(xAb)。(4) 系数a为-1，指数b为1的项输出(-x)0(5) 系数a为-1,指数b不为1的项输出(-xAb)o(6) 系数a不为1或-1，指数b不为0或1的项输出(axAb)。2 .设计表示(1)函数调用关系图mainListinitiatefListinsertfListAddfListGet(2)函数接口规格说明voidListinitiate(SLNode*head)/*初始化以head为头指针的单链表*/intListinsert(SLNode*headDaTatypexishuDaTatypezhishu)在单

6、链表中按指数的由小到大顺序插入多项式的指数和系数*/intListAdd(SLNode*head1SLNode*head2SLNode*head3)/以head1为头指针的单链表与以head2为头指针的单链表相加等于以head3为头指针的单链表*/intListGet(SLNode*head)/*输出以head为头指针的单链表*/3 .实现注释(即各项功能的实现程度)(1)根据输入的n值建立多项式a,b的单链表；根据提示输入每项的系数和指数。(2)可不按指数大小顺序任意输入多项式的每项(整数项)。(3)按数学格式输出ab两多项式，然后再输出相加后的和c的多项式。4 .详细设计11插入函数：in

7、tListInsert(SLNode*headDaTatypexishuDaTatypezhishu)插入(SLNode*p*q;p=head;while(p->next!=NULL)(if(p->next->zhishu)>zhishu)break;/比较指数大/、p=p->next;链表中节点指数大，则比较链表下一个q=(SLNode*)malloc(sizeof(SLNode);/链表中节点指数小,在该节点前插入q->xishu=xishu;q->zhishu=zhishu;q->next=NULL;q->next=p->nex

8、t;p->next=q;return1;【2】求和函数：intListAdd(SLNode*head1SLNode*head2SLNode*head3)(SLNode*p*q*s*r;intn=0;p=head1;q=head2;s=head3;while(p->next!=NULL)先将a存入c中(r=(SLNode*)malloczeof(SLNode);r->zhishu=p->next->zhishu;r->xishu=p->next->xishu;r->next=NULL;s->next=r;p=p->next;s=s

9、->next;)s=head3;while(s->next!=NULL&&q->next!=NULL)(while(s->next!=NULL&&s->next->zhishu<q->next->zhishu)披寻s=s->next;if(s->next!=NULL)n=1;if(n)if(s->next->zhishu=q->next->zhishu)if(s->next->xishu+q->next->xishu!=0)s->next-&g

10、t;xishu=s->next->xishu+q->next->xishu;s=s->next;elses->next=s->next->next;elser=(SLNode*)malloc(sizeof(SLNode);r->zhishu=q->next->zhishu;r->xishu=q->next->xishu;r->next=s->next;s->next=r;s=s->next;/插入q=q->next;n=0;if(q->next!=NULL&&

11、s->next=NULL)s->next=q->next;剩余项的接到C链表的尾部return1;【3】输出函数(系数为0的项已被删除)：intListGet(SLNode*head)/输出SLNode*p;p=head->next;intkaiguan=1;if(p=NULL)printf("0n");while(p!=NULL)(if(kaiguan=1)(if(p->zhishu=0)判断头结点为空的输出判断头结点非空/多项式第一项的输出当指数为时，只输出系数xishuelseif(p->xishu=1)系数为1时输出XAzhish

12、ui或xprintf("%d"p->xishu);if(p->zhishu=1)printf("x");elseprintf("xA%d"p->zhishu);)elseif(p->xishu=-1)/系数为-1时输出-XAzhishui或-xif(p->zhishu=1)printf("-x");elseprintf("-xA%d"p->zhishu);)elseif(p->xishu>0)/系数大于0时if(p->zhishu=1)pri

13、ntf("%dx"p->xishu);elseprintf("%dxA%d"p->xishup->zhishu);)elseif(p->xishu<0)系数为负数时，原样输出if(p->zhishu=1)printf("%dx"p->xishu);elseprintf("%dxA%d"p->xishup->zhishu);)kaiguan=0;)else/多项式的其余项都前带符号输出if(p->zhishu=0)if(p->xishu!=0)prin

14、tf("+%d"p->xishu);)elseif(p->xishu=1)if(p->zhishu=1)printf("+x");elseprintf("+xA%d"p->zhishu);)elseif(p->xishu=-1)if(p->zhishu=1)printf("-x");elseprintf("-xA%d"p->zhishu);)elseif(p->xishu>0)系数大于0时，系数前面带“+”if(p->zhishu=1)

15、printf("+%dx"p->xishu);elseprintf("+%dxA%d"p->xishup->zhishu);)elseif(p->xishu<0)系数为负时，原样输出if(p->zhishu=1)printf("%dx"p->xishu);elseprintf("%dxA%d"p->xishup->zhishu);)p=p->next;)printf("n");return1;)三、调试分析1 .调试过程中遇到的主要问题

16、是如何解决的；调试过程中存在少许C语言的基础语法错误，经独立仔细观察和调试修改正确,最大的难题是将各多项式按数学格式输出，经过很多次的调试，还是存在错误，向同学请教，仍不能解决，最后重新修改算法，最终达到输出要求。部分错误：2 .时间和空间复杂度的分析；1插入函数：时间O(nA2)空间O(n)2求和函数：时间O(m+n)空间O(m+n)【3】输出函数(系数为0的项已被删除)：时间O(n)空间0(1)3 .改进设想；(1)求和函数：将多项式a的链表复制给多项式c的链表，再调用求和函数(b的链表和c的链表相加)，将求和的结果插入到c的链表中(作为多项式c)o修改思路：将多项式a的各项先与多项b的各项比较，运算后再插入多项式c的链表，(由于ab多项式已按指数由小到大排序)修改后时间复杂度降低。(2)输出函数：设计按数学格式输出时，算法多样。4 .经验和体会等。深刻体会到多动手的重要性，只有多动手编程，才能熟练灵活的掌握C语言基础知识，才能更好的理解掌握数据结构