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

1、实习一 线性表及其应用 (题目：一元稀疏多项式的加法运算 )一、需求分析1. 输入并建立两个多项式；2. 多项式 a 与 b 相加，建立和多项式 c ；3. 输出多项式abc。输出格式：比如多项式 a为：A(X)=C1xe1 +c2xe2+ CmXem其中，Ci和ei分别为第i项的系数和指数，且各项按指数的升幕排列，即0eKe2vvem。多项式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

2、)=(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项的系数和指数，且各项按指数的升幕排列，即0eKe2vvem。多项式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三个多项式。【1】插入

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

5、项带符号输出(定义一个开关变量)(1) 系数为a,指数b为O的项输出(a)。( 2)系数 a 为 1，指数 b 为 1 的项输出( x)。(3) 系数a为1,指数b不为1的项输出(xb)( 4)系数 a 为-1,指数 b 为 1 的项输出( -x)。(5) 系数a为-1,指数b不为1的项输出(-xb)。(6) 系数a不为1或-1,指数b不为O或1的项输出(axb)2. 设计表示( 1)函数调用关系图mainListInitiate ListInsert ListAdd ListGet( 2)函数接口规格说明VOid LiStlnitiate(SLNode *head)/*初始化以 head为头

6、指针的单链表 */int ListInsert(SLNode *headDaTatype xishuDaTatype zhishu) /在* 单链 表中按指数的由小到大顺序插入多项式的指数和系数 */int LiStAdd(SLNode*head1SLNode*head2SLNode*head3)/以 head1 为 头指针的单链表与以head2为头指针的单链表相加等于以head3为头指针的单链 表*/lnt LiStGet(SLNode*head) /* 输出以 head 为头指针的单链表 */3. 实现注释 (即各项功能的实现程度)( 1)根据输入的 n 值建立多项式 a, b 的单链表；

7、根据提示输入每项的系数 和指数。(2) 可不按指数大小顺序任意输入多项式的每项(整数项)。(3) 按数学格式输出ab两多项式，然后再输出相加后的和C的多项式4. 详细设计【1】插入函数：int LiStl nsert(SLNode *headDaTatype XiShuDaTatyPe ZhiShU)插入SLNode *p*q;p=head;while(p-neXt!=NULL)if(p-neXt-ZhiShu)ZhiShu)break;/ 比较指数大小p=p-neXt;/ 链表中节点指数大，则比较链表下一个q=(SLNode*)malloc(SiZeof(SLNode);/ 链表中节点指数小

8、，则在该节点前插入q-XiShu=XiShu;q-ZhiShu=ZhiShu;q-neXt=NULL;q-neXt=p-neXt;p-neXt=q;return 1;【2】求和函数：int LiStAdd(SLNode*head1SLNode*head2SLNode*head3)SLNode *p*q*S*r;int n=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-ne

9、Xt=NULL;S-neXt=r;p=p-neXt;s=s-next;s=head3; while(s-next!=NULL &q-next!=NULL )WhiIe(s- next!=NULL & s-n ext-zhishun ext-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;eIse s-next=s-next-ne

10、xt;eIse r=(SLNode*)maIIoc(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链表的尾部return 1;【3】输出函数(系数为 0 的项已被删除)：int ListGet(SLNode *head)/输出SLNode *p; p=head-next;/ 判断头结点为空的输出/ 判断头结点非空/

11、多项式第一项的输出/ 当指数为时，只输出系数 xishuint kaiguan=1; if(p=NULL)printf(0n);while(p!=NULL) if(kaiguan=1)if(p-zhishu=0)printf(%dp-xishu);else if(p-xishu=1)/ 系数为 1 时输出 Xzhishui 或 xif(p-zhishu=1)printf(x);else printf(x%dp-zhishu);else if(p-xishu=-1) / 系数为-1 时输出-Xzhishui或-Xif(p-zhishu=1)printf(-x);else printf(-x%dp

12、-zhishu);else if(p-xishu0)/ 系数大于 0 时if(p-zhishu=1)printf(%dxp-xishu);else printf(%dx%dp-xishup-zhishu);else if(p-xishuzhishu=1)printf(%dxp-xishu);else printf(%dx%dp-xishup-zhishu); kaiguan=0;else/多项式的其余项都前带符号输出if(p-zhishu=0)if(p-xishu!=0) printf(+%dp-xishu);else if(p-xishu=1)if(p-zhishu=1)printf(+x)

13、;else printf(+x%dp-zhishu);else if(p-xishu=-1)if(p-zhishu=1)printf(-x);else printf(-x%dp-zhishu);else if(p-xishu0) / 系数大于 0 时，系数前面带 “ +” if(p-zhishu=1)printf(+%dxp-xishu);else printf(+%dx%dp-xishup-zhishu);else if(p-xishuzhishu=1)printf(%dxp-xishu);else printf(%dx%dp-xishup-zhishu);p=p-next;printf(n

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