徐长稳2013508058一元稀疏多项式计算器

1、信息科学与技术学院数据结构课程设计报告题目名称：一元稀疏多项式计算器专业班级：13级计算机科学与技术学生姓名：徐长稳学生学号：2013508058指导教师：韩峰老师完成日期：2014-12目 录一、需求分析2（1）问题描述2（2）基本要求2二、概要设计2（1）多项式的输入与存储3（2）多项式数据链表结点的定义3（3）. 本程序包含六个模块3三、详细设计4（1） 创建链表5（2） 减法时多项式的建立6（3）输出8（4）多项式相加减8（5）主函数10四、调试分析12五、用户手册12六、测试结果13（1）输入：13（2）输出：13七、总结13一、需求分析（1）问题描述设计一个一元稀疏多项式简单计算器

2、。（2）基本要求一元稀疏多项式简单计算器的基本功能是：(1) 输入并建立多项式 ；(2) 输出多项式，输出形式为整数序列：n，cl，el，c2，e2，cn，en，其中n是多项式的项数，ci 和ei，分别是第 i 项的系数和指数，序列按指数降序排列；(3) 多项式a和b相加，建立多项式a +b；(4) 多项式a和b相减，建立多项式a -b 。【测试数据】(1)(2x+5x83.1x11) + (75x8+11x9)=(3.lx11+11x9+2x+7)(2)(6x-3x+4.4x21.2x9) (-6x-3+5.4x2x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x)(3)(1

3、 +x + x2+x3+x4+x5)+(-x3x4)=(1+x+x2+x5) (4)(x+x3)+(-xx3)=0(5)(x+x100)+(x100 +x200)=(x+2x100+x200)(6)(x+x2+x3)+0=x+x2+x3二、概要设计根据一元多项式的相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则作“和多项式”中的一项插入到“和多项式”链表中去；对于两个一元多项式中指数不同的项，则将指数值较小的项插入到“和多项式”链表中去。“和多项式”链表中的结点无需生成，而应该从两个多项式的链表中摘取。定义线性表typedef int ElemType; （

4、1）多项式的输入与存储用带表头结点的单链表存储多项式，链表中的每个节点分别存储多项式各项的系数和指数，即每从键盘输入多项式的一对数（系数，指数），可对应建立链表的一个结点。建立两个链表，并将结果保存在其中一条链表中。（2）多项式数据链表结点的定义 typedef struct LNode /表示多项式链表的节点float coef; /系数int exp; /指数struct LNode *next; LNode,*LinkList;（3）. 本程序包含六个模块1) 主程序模块void main()初始化：输入 函数调用输出2) 链表结点的建立；3) 加法多项式的建立；4) 减法多项

5、式的建立；5）程序结果的输出；6）主函数三、详细设计创建两个链表，分别存放多项式1和多项式2，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插到此项的前面，这样既可保证多项式链表的有序性。 多项式相加或相减，下面给出多项式相加的部分实现/*假设头指针Pa和Pb的单链表分别为多项式后A和B的储存结构，指针p和q分别只想A和B种当前进行比较的某个结点，则逐一比较两个结点中的指数项，有一下三种情况：（1）指针p所致结点的指数值等于指针q所指结点的指数值，则将两个结点的系数相加，若和不为零，则修改p所指的系数值，同时删除q所指结点；若和为零，则删除p和q所指结点。（2）指针p所指

6、结点的指数值小于指针q所指的结点的指数值，则应当摘取p所指结点插入到“和多项式”链表中。（3）指针p所指结点的指数值大于指针q所指的结点的指数值，则应当摘取q所指结点插入到“和多项式”链表中。最后，当有一个多项式链表为空时，则将另一个非空多项式的剩余段直接链在“和多项式”的链表后面。*/（1） 创建链表void InitList(LinkList &q)q=(LNode*)malloc(sizeof(struct LNode);q->next=NULL;/建立一个带节点的单链表1) 加法时的多项式的建立LinkList InsertList(LinkList L)LinkList

7、 p;/生成一个新结点while(L->next=NULL)p=(LNode*)malloc(sizeof(struct LNode);printf("n输入各项系数和指数（系数，指数）输入0，0为结束: ");scanf("%f,%d",&p->coef,&p->exp);p->next=L->next;/运用前插法将新结点插入到头结点后面L->next=p;Do p=(LNode*)malloc(sizeof(struct LNode);printf("n输入各项系数和指数（系数，指数）输

8、入0，0为结束: ");scanf("%f,%d",&p->coef,&p->exp);LinkList r=L,q=L->next;/定义r用于保存L的前驱，初值为头结点while (q!=NULL)/通过比较指数找到第一个大于输入项指数的项pif(p->exp<q->exp)p->next=q;r->next=p;break;else if(p->exp=q->exp)/如果两个指数相等，则归并两个有序表q->coef=p->coef+q->coef;break;El

9、seq=q->next;/通过比较指数找到第一个大于输入项指数的项pr=r->next;if(q=NULL)/将输入项p插入到q和其前驱结点r之间p->next=q;r->next=p;while(p->coef!=0|p->exp!=0);/结束语return L;（2） 减法时多项式的建立LinkList DecInsertList(LinkList L)LinkList p;while(L->next=NULL)p=(LNode*)malloc(sizeof(struct LNode);printf("n输入各项系数和指数（系数，指数）

10、输入(0，0)为结束: ");scanf("%f,%d",&p->coef,&p->exp);p->coef=-(p->coef);/将系数变成负数p->next=L->next;L->next=p;do p=(LNode*)malloc(sizeof(struct LNode);printf("n输入各项系数和指数（系数，指数）输入(0，0)为结束: ");scanf("%f,%d",&p->coef,&p->exp);p->coe

11、f=-(p->coef);/将系数变成负数LinkList r=L,q=L->next;while (q!=NULL)if(p->exp<q->exp)p->next=q;r->next=p;break;else if(p->exp=q->exp)q->coef=p->coef+q->coef;break;Else q=q->next;r=r->next;if(q=NULL) p->next=q;r->next=p;while(p->coef!=0|p->exp!=0);/结束语retu

12、rn L;（3）输出void Output(LinkList L)LinkList p;p=L->next;while(p)/知道p为空时，全部输出printf(" %fx%d",p->coef,p->exp);p=p->next;printf("n");（4）多项式相加减LinkList LinkListAdd(LinkList pa,LinkList pb)LinkList p,q,r,s,t;float x;/定义X用于系数相加p=pa->next;/定义p指向pa的第一个结点r=pa;/r指向当前和多项式的当前结点，

13、初值为pat=pb;/t指向当前和多项式的当前结点，初值为pbq=pb->next;/定义q指向pb的第一个结点while(p!=NULL&&q!=NULL)if(p->exp<q->exp)/如果pa当前指针p的指数小r=p; /r指向pp=p->next;/p指向下一个指针else if(p->exp=q->exp)/如果指数相等x=p->coef+q->coef;/用X保存两系数和if(x=0)/如果系数为0删除两结点r->next=p->next;s=p;p=p->next;/p指向下一个结点fre

14、e(s);t->next=q->next;s=q;q=q->next;/q指向下一个结点free(s); Elsep->coef=x;/修改pa当前结点p的系数为两项系数之和r->next=p;/将修改后的pa当前结点p链接在r之后r=r->next;/r指向下一个结点p=p->next;/p指向下一个结点t->next=q->next;s=q;/删除pb当前结点q=q->next;free(s);Else /如果pb当前指针q的指数小s=q->next;q->next=p;r->next=q;/将q接在r后面r=q

15、;/r指向qq=s;/q指向下一个结点t->next=q;if(q!=NULL)r->next=q;/插入非空多项式的剩余段return pa ;（5）主函数void main() printf("n"); printf(" n"); printf(" 数据结构 n"); printf(" 一元稀疏多项式的计算 n"); printf(" n"); printf(" 班级:13级2班 学号:2013508058 n"); printf(" 姓名:徐长稳

16、专业：计科 n"); printf(" n"); printf("n"); printf("n");printf("请选择：n");printf("多项式的加法输入1n");printf("多项式的减法输入2n");printf("nn");int m;scanf("%d",&m); LinkList a,b;printf("n输入第一个多项式");InitList(a);InsertList(a)

17、; printf("n输入第二个多项式");InitList(b); if(m=1) InsertList(b); else DecInsertList(b); printf("n第一个多项式为：n"); Output(a); printf("n第二个多项式为：n"); Output(b); LinkListAdd( a, b ); printf("n计算结果是n"); Output(a);5. 函数的调用关系图反映了演示程序的层次结构 : InitList(a);创建链表InsertList(a);加法多项式的建

18、立InitList(a);创建链表m=1：InsertList(b);加法多项式的建立 m主函数m=2：DecInsertList(b);减法多项式的建立Output(a|b);输出a或bLinkListAdd( a, b );多项式的加减Output(a);输出结果四、调试分析1. 由于对多项式的计算规则不是很理解，所以在设计算法时无法入手。2. 刚开始时曾忽略了一些变量参数的标识"&"，使调试程序时费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。3. 本程序的模块划分比较合理,且尽可能主函数简化，多为1调用和输入致使模块的调试比较顺利。反之，如此划分的

19、模块并非完全合理，因为在实现集合操作的编码中仍然需要判别指针是否为空。按理，两个链表的并、交和差的操作也应封装在链表的模块中，而在集合的模块中，只要进行相应的应用即可。4. 算法的时空分析l)由于链表采用带头结点的有序单链表，并进行了大量的比较与插入，所以各种操作的算法时间复杂度比较合理。InsertList(a), DecInsertList(b), LinkListAdd( a, b )和I Output以及确定链表中第一个结点和之后一个结点的位置都是O(l)， 2)基于有序链表实现的有序集的各种运算和操作的时间复杂度分析如下：构造有序集算法InitList 读入n个元素，逐个进行比较判定当前结点的指数值的大小确定插入位置后，在插入到有序集中,所以时间复杂度是O(n2)。五、用户手册1. 本程序的运行环绕为C语言下的编码程序2. 进入演示程序后即显示文本方式的用户界面; 数据结构 一元稀疏多项式的计算 班级:13级2班 学号:2013508058 姓名:徐长稳 专业：计科 请选择：多项式的加法输入1多项式的减法输入2