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

实习一线性表及其应用（题目：一元稀疏多项式的加法运算）一、需求分析1.输入并建立两个多项式；2.多项式a与b相加，建立和多项式c；3.输出多项式abc。输出格式：比如多项式a为：A(x)=c1xe1+c2xe2+…+cmxem，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜em。多项式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+2x+11x9-3x11)实习一线性表及其应用题目：一元稀疏多项式的加法运算实习时间：2012/9/20.10.12一、需求分析1.输入并建立两个多项式；2.多项式a与b相加，建立和多项式c；3.输出多项式abc。输出格式：比如多项式a为：A(x)=c1xe1+c2xe2+…+cmxem，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜em。多项式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+2x+11x9-3x11)二、设计1.设计思想（1）存储结构用带头结点的单链表存储多项式。三个多项式链表中都只存储非零系数项。若多项式a与b中指数相等的两项相加后，系数为零，则在和多项式c中不存储该指数项。（2）主要算法基本思想按照链表的基本操作，初始化三个链表，在两个链表中按指数由小到大分别插入a和b的多项式（系数和指数），将多项式a的链表复制给多项式c的链表，再调用求和函数（b的链表和c的链表相加），将求和的结果插入到c的链表中（作为多项式c）最后输出多项式a，b，c三个多项式。【1】插入函数：设计按多项式指数的从小到大插入。从第一个元素开始判断，直到遇到比插入元素更大的指数或链表尾为止，再进行插入操作。【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，指数b为1的项输出（x）。（3）系数a为1，指数b不为1的项输出（x^b）。（4）系数a为-1，指数b为1的项输出（-x）。（5）系数a为-1，指数b不为1的项输出（-x^b）。（6）系数a不为1或-1，指数b不为0或1的项输出（ax^b）。2.设计表示（1）函数调用关系图main→ListInitiate→ListInsert→ListAdd→ListGet（2）函数接口规格说明voidListInitiate(SLNode**head)/*初始化以head为头指针的单链表*/intListInsert(SLNode*headDaTatypexishuDaTatypezhishu)/*在单链表中按指数的由小到大顺序插入多项式的指数和系数*/intListAdd(SLNode*head1SLNode*head2SLNode*head3)/*以head1为头指针的单链表与以head2为头指针的单链表相加等于以head3为头指针的单链表*/IntListGet(SLNode*head)/*输出以head为头指针的单链表*/3.实现注释（即各项功能的实现程度）（1）根据输入的n值建立多项式a，b的单链表；根据提示输入每项的系数和指数。（2）可不按指数大小顺序任意输入多项式的每项（整数项）。（3）按数学格式输出ab两多项式，然后再输出相加后的和c的多项式。4.详细设计【1】插入函数：intListInsert(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-next;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*)malloc(sizeof(SLNode));r-zhishu=p-next-zhishu;r-xishu=p-next-xishu;r-next=NULL;s-next=r;p=p-next;s=s-next;}s=head3;while(s-next!=NULL&&q-next!=NULL){while(s-next!=NULL&&s-next-zhishuq-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-xishu=s-next-xishu+q-next-xishu;s=s-next;}elses-next=s-next-next;}else{r=(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&&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(0\n);//判断头结点为空的输出while(p!=NULL)//判断头结点非空{if(kaiguan==1)//多项式第一项的输出{if(p-zhishu==0)//当指数为时，只输出系数xishuprintf(%dp-xishu);elseif(p-xishu==1)//系数为1时输出X^zhishui或x{if(p-zhishu==1)printf(x);elseprintf(x^%dp-zhishu);}elseif(p-xishu==-1)//系数为-1时输出-X^zhishui或-x{if(p-zhishu==1)printf(-x);elseprintf(-x^%dp-zhishu);}elseif(p-xishu0)//系数大于0时{if(p-zhishu==1)printf(%dxp-xishu);elseprintf(%dx^%dp-xishup-zhishu);}elseif(p-xishu0)//系数为负数时，原样输出{if(p-zhishu==1)printf(%dxp-xishu);elseprintf(%dx^%dp-xishup-zhishu);}kaiguan=0;}else{//多项式的其余项都前带符号输出if(p-zhishu==0){if(p-xishu!=0)printf(+%dp-xishu);}elseif(p-xishu==1){if(p-zhishu==1)printf(+x);elseprintf(+x^%dp-zhishu);}elseif(p-xishu==-1){if(p-zhishu==1)printf(-x);elseprintf(-x^%dp-zhishu);}elseif(p-xishu0)//系数大于0时，系数前面带“+”{if(p-zhishu==1)printf(+%dxp-xishu);elseprintf(+%dx^%dp-xishup-zhishu);}elseif(p-xishu0)//系数为负时，原样输出{if(p-zhishu==1)printf(%dxp-xishu);elseprintf(%dx^%dp-xishup-zhishu);}}p=p-next;}printf(\n);return1;}三、调试分析1.调试过程中遇到的主要问题是如何解决的；调试过程中存在少许C语言的基础语法错误，经独立仔细观察和调试修改正确，最大的难题是将各多项式按数学格式输出，经过很多次的调试，还是存在错误，向同学请教，仍不能解决，最后重新修改算法，最终达到输出要求。部分错误：2.时间和空间复杂度的分析；【1】插入函数：时间O(n^2)空间O(n)【2】求和函数：时间O(m+n)空间O(m+n)【3】输出函数（系数为0的项已被删除）：时间O(n)空间O(1)3.改进设想；（1）求和函数：将多项式a的链表复制给多项式c的链表，再调用求和函数（b的链表和c的链表相加），将求和的结果插入到c的链表中（作为多项式c）。修改思路：将多项式a的各项先与多项b的各项比较，运算后再插入多项式c的链表，（由于ab多项式已按指数由小到大排序）修改后时间复杂度降低。（2）输出函数：设计按数学格式输出时，算法多样。4.经验和体会等。深刻体会到多动手的重要性，只有多动手编程，才能熟练灵活的掌握C语言基础知识，才能更好的理解掌握数据结构的精髓。从而避免基础语法错误，让代码变得更简洁高效。如此才能准确高效的解决问题。四、用户手册（即使用说明）仅需按照提示输入数字即可。五、运行结果运行环境：C-free1.(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+2x+11x9-3x11)4.(-x+2x3)+(x-2x3)=0六、源程序清单见文库文本文件“线性表及其应用-一元稀疏多项式的加法运算”