数据结构课程设计——一元稀疏多项式

目录一、需求分析 (4)1、程序的功能 (4)2、输入输出的要求 (4)二、概要设计 (4)三、详细设计 (4)1、数据类型 (4)2、模块的类C码算法 (5)3、函数调用关系 (12)四、调试分析以及设计体会 (14)1、调试分析 (14)2、调试分析中遇到的问题及解决方法 (16)3、心得体会 (17)五、使用说明 (18)六、附录 (19)1、参考书目 (19)2、源程序代码（带注释） (19)七、计算机科学与技术课程设计评分表 (28)1)需求分析A.程序的功能。

a.输入并建立多项式；b.输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci,ei，分别是第i项的系数和指数，序列按指数降序排列；c.多项式a和b相加，建立多项式a+b；d.多项式a和b相减，建立多项式a-b；e.计算多项式在x处的值；B.输入输出的要求。

每输入一个系数和指数确定一个一元多项式2)概要设计a.程序模块组成以及每个模块的功能。

主程序中通过调用void create(polynmial &L) 创建存储在单链表中的多项式，调用void display(polynmial L);输出显示多项式，调用void sort(polynomial &L);和void reverse(polynomial &L)对多项式进行排序，使其按降序排列，调用void add(polynomial La, polynomial Lb, polynomial&Lc)和void subtract(polynomial La, polynomial Lb, polynomial &Ld)对两个多项式进行加减操作b．数据结构和数据库结构多项式的系数为浮点型，多项式的指数为整型；用带表头结点的单链表存储多项式，多项式的项数存放在头结点中；多项式之间进行加减运算。

XX学院课程设计说明书题目一元多项式计算问题系(部) 计算机科学与技术系专业(班级) 计算机科学与技术专业姓名学号指导教师起止日期课程设计任务书课程名称：数据结构与算法设计题目：一元多项式计算问题已知技术参数和设计要求：问题描述：设计一个稀疏多项式简单计算器基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出；测试数据：(1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2(2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7(3) A+B A=x3+x1B=-x3-x1(4) A+B A=0 B=x7+x5+x3+x1(5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x选作内容：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积设计工作量：40课时工作计划：指导教师签名：日期：教研室主任签名：日期：系主任签名：日期：长沙学院课程设计鉴定表摘要本文是关于一个一元稀疏多项式计算器的问题。

一元稀疏多项式计算内容包括输入并建立多项式,多项式相加，多项式求值，多项式求乘积以及输出多项式。

本程序运用面向对象程序设计方法，使用C++语言，利用Microsoft Visual C++ 6.0开发工具，还有数据结构课中学到的链式存储结构，存储一元稀疏多项式，从而实现程序的基本功能。

在程序中定义了各种类型的运算的模块，通过主程序的调用来完成它们之间的配合，进而使得一元稀疏多项式计算器的顺利运行。

关键词：数据结构；一元稀疏多项式；链表；C++语言目录1 设计内容与要求 (1)2.设计说明 (1)2.1 问题描述与功能设计 (1)2.2 数据结构与算法 (1)2.3 函数定义 (3)2.4 界面设计 (4)2.5 编码 (5)2.6 测试 (10)3 总结 (14)参考文献 (15)附录A 源代码 (16)⒈设计内容与要求设计内容：设计一个稀疏多项式简单计算器，能够进行简单的基本运算。

数据结构实验报告——一元稀疏多项式计算器安子烨PB12203079实验目的实现一元多项式的简单运算功能，掌握线性表的知识，提高编程能力。

功能清单1.一元多项式创建2.显示一元多项式3.复制一元多项式4.多项式加法5.多项式减法6.修改一元多项式7.删除一元多项式8.销毁记录实验设计该多项式计算器以菜单驱动的形式实现上述各运算功能。

最多可支持十条记录，分别用指针数组引导存储于十个不同的位置。

以下为程序的部分源代码。

#include<stdio.h>#include<math.h>#include<stdlib.h>typedef struct LinkList{double coef;int expn;LinkList *next;}LNode;void CreatPolyn(LinkList **h)//创建多项式{LinkList *q=NULL, *w=NULL, *p=NULL;double m=0; int n=0;(*h)=(LinkList *)malloc(sizeof(LinkList));(*h)->coef=0; (*h)->expn=0; (*h)->next=NULL;printf("请输入X的系数和指数,当系数为零时结束创建\n");scanf("%lf%d",&m,&n);while(m!=0){q=(LinkList *)malloc(sizeof(LinkList));q->coef=m; q->expn=n; q->next=NULL;if((*h)->next==NULL){if(q->expn==(*h)->expn) (*h)->coef+=q->coef;else if((*h)->expn>q->expn) {q->next=(*h); *h=q; } else (*h)->next=q;}else{for(w=(*h);w->next!=NULL;w=w->next){if(q->expn==w->expn){w->coef+=q->coef;break;}else if((w->expn>q->expn)&&(w==*h)){q->next=(*h);(*h)=q;break;}else if((w->expn<q->expn)&&(w->next->expn>q->expn)){q->next=w->next;w->next=q;break;}}if(w->next==NULL){if(w->expn==q->expn) w->coef+=q->coef;else if(w->expn<q->expn) w->next=q;}}printf("请输入X的系数和指数,当系数为零时结束创建\n");scanf("%lf%d",&m,&n);}}void PrintPolyn(LinkList *p, int i)//打印多项式{printf("第%d个多项式是:",i);while(p!=NULL){if((p->coef)>0) printf("+%lf*X^%d",p->coef,p->expn);else if((p->coef)<0) printf("%lf*X^%d",p->coef,p->expn); p=p->next;}printf("\n");}void CopyPolyn(LinkList **M, LinkList **N)//多项式复制{LinkList *p=NULL, *q=NULL, *w=NULL;(*N)=(LinkList *)malloc(sizeof(LinkList));(*N)->coef=(*M)->coef; (*N)->expn=(*M)->expn; (*N)->next=NULL;for(w=(*N),p=(*M)->next;p!=NULL;p=p->next){q=(LinkList *)malloc(sizeof(LinkList));q->coef=p->coef; q->expn=p->expn; q->next=p->next;w->next=q; w=w->next;}}void AddPolyn(LinkList *M, LinkList *N, LinkList **X)//多项式加法{LinkList *p=NULL, *q=NULL, *w=NULL, *z=NULL;(*X)=(LinkList *)malloc(sizeof(LinkList));(*X)->coef=0; (*X)->expn=0; (*X)->next=NULL;for(p=M,q=N,w=(*X);(p!=NULL)&&(q!=NULL);){z=(LinkList *)malloc(sizeof(LinkList));if(p->expn<q->expn){z->coef=p->coef; z->expn=p->expn; z->next=NULL;p=p->next; w->next=z; w=w->next;}else if(p->expn>q->expn){z->coef=q->coef; z->expn=q->expn; z->next=NULL;q=q->next; w->next=z; w=w->next;}else if(p->expn==q->expn){z->coef=p->coef+q->coef; z->expn=p->expn; z->next=NULL;p=p->next; q=q->next; w->next=z; w=w->next;}}if(p==NULL){for(;q!=NULL;){z=(LinkList *)malloc(sizeof(LinkList));z->coef=q->coef; z->expn=q->expn; z->next=NULL;q=q->next; w->next=z; w=w->next;}}else if(q==NULL){for(;p!=NULL;){z=(LinkList *)malloc(sizeof(LinkList));z->coef=p->coef; z->expn=p->expn; z->next=NULL;p=p->next; w->next=z; w=w->next;}}for(w=(*X);w!=NULL;w=w->next){printf("%lf %d\n",w->coef,w->expn);}}void SubtractPolyn(LinkList *M, LinkList *N, LinkList **X)//多项式减法{LinkList *p=NULL, *q=NULL, *w=NULL, *z=NULL;(*X)=(LinkList *)malloc(sizeof(LinkList));(*X)->coef=0; (*X)->expn=0; (*X)->next=NULL;for(p=M,q=N,w=(*X);(p!=NULL)&&(q!=NULL);){z=(LinkList *)malloc(sizeof(LinkList));if(p->expn<q->expn){z->coef=p->coef; z->expn=p->expn; z->next=NULL;p=p->next; w->next=z; w=w->next;}else if(p->expn>q->expn){z->coef=-q->coef; z->expn=q->expn; z->next=NULL;q=q->next; w->next=z; w=w->next;}else if(p->expn==q->expn){z->coef=p->coef-q->coef; z->expn=p->expn; z->next=NULL;p=p->next; q=q->next; w->next=z; w=w->next;}}if(p==NULL){for(;q!=NULL;){z=(LinkList *)malloc(sizeof(LinkList));z->coef=-q->coef; z->expn=q->expn; z->next=NULL;q=q->next; w->next=z; w=w->next;}}else if(q==NULL){for(;p!=NULL;){z=(LinkList *)malloc(sizeof(LinkList));z->coef=p->coef; z->expn=p->expn; z->next=NULL;p=p->next; w->next=z; w=w->next;}}/*for(w=(*X);w!=NULL;w=w->next){printf("%lf %d\n",w->coef,w->expn);}*/}void ValuePolyn(LinkList *h, double x)//多项式求值{double sum=0, a=0;while(h!=NULL){a=pow(x,h->expn);sum=sum+(h->coef)*a;h=h->next;}printf("所求多项式的值为%lf\n",sum);}void DeletePolyn(LinkList **h){LinkList *p=(*h)->next; (*h)=NULL;while(p!=NULL){free(*h);(*h)=p;p=p->next;}}void RevisePolyn(LinkList **h, int i){int n=0;int choose=0;double m=0;LinkList *q=NULL, *w=NULL;PrintPolyn((*h),i);printf("请输入你想执行的操作代号（添加：1；修改：2；删除：3）\n");scanf("%d",&choose);switch(choose){case 1:{printf("输入你想要添加项的系数和次数\n");scanf("%lf%d",&m,&n);q=(LinkList *)malloc(sizeof(LinkList));q->coef=m; q->expn=n; q->next=NULL;for(w=(*h);w->next!=NULL;w=w->next){if((w->expn>q->expn)&&(w==*h)){q->next=(*h);(*h)=q;break;}else if((w->expn<q->expn)&&(w->next->expn>q->expn)) {q->next=w->next;w->next=q;break;}}if(w->expn<n) w->next=q;break;}case 2:{printf("输入你想要修改项的系数和次数\n");scanf("%lf%d",&m,&n);for(w=(*h);w!=NULL;w=w->next){if(w->expn==n) w->coef=m;}printf("未找到该项。

第一章问题分析与任务定义1 .题目：设计一个一元稀疏多项式的简单计算器。

输入并用带表头结点的单链表存储多项式；以整数序列：n，c1，e1，c2，e2……cn，en的形式输出多项式，其中n是多项式的项数，ci，ei分别为第i项的系数和指数，序列按指数降序排列；实现多项式a、b的相加和相减操作，输出相加、相减后的多项式。

2.问题分析：符号多项式的操作，已经成为标处理的典型应用例子，多项式可由n+1个系数唯一确定，因此在计算机里可以用一个线性表来表示，每一项的指数隐含在其系数序号里，只要在结点的data域里多加一项即可，显然我们可以对该存储采取顺序存储，使得多项式相加的算法定义十分简洁，然而通常的应用里多项式的次数可能很高而且很大，使得顺序存储结构的最大长度很难确定。

这种对内存空间的浪费是应当避免的，因此若只对多项式进行求值等不改变多项式系数和指数的运算则采用类似于顺序表的顺序存储结构即可，否则采用链式存储表示比较好。

1.如何实现这种线性链表表示的多项式的加法呢?根据一元多项式的加减法运算法则：对于两个一元多项式中的所有指数相同的项，对应系数相加减，若其和不为零，则构成和或差多项式中的一项，对于两个一元多项式中的所有指数不同的向分别复抄到和火差多项式里去。

在此，按照数据类型Polynomial中的基本操作的定义，和或差多项式中的结点无需另生成，而应该从两个多项式的链表中摘取，其运算规则如下：假设指针qa和qb分别指向多项式A和B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列三种情况（1）指针qa所指结点的指数值<指针qb所指结点的指数值，则应摘取qa所致结点插入到和差多项式链表中去（2）指针qa所致结点的指数值>指针qb所指结点的指数值，则应摘取指针qb所指结点插入到和差多项式里链表中去（3）指针qa所指结点的指数值=指针qb所指结点的指数值，则将两个结点中的系数相加减，若和差数不为零，则修改qa所指结点的系数值，同时释放qb所直接点；繁殖，从多项式Adequate链表中删除相应结点，并释放指针qa和qb所致结点。

软件学院课程设计报告书课程名称数据结构设计题目一元稀疏多项式计算器专业班级软件工程11级1班学号 1120010107姓名指导教师2013 年 1月目录1设计时间 42设计目的 43设计任务 44设计内容 44.1需求分析 44.1.1.程序所能达到的功能 44.1.2.输入的形式和输入值的范围 44.1.3.输出的形式 44.1.4.测试数据 54.2总体设计 54.2.1.本程序中用到的所有抽象数据类型的定义 54.2.2.主程序的流程 74.2.3.各程序模块之间的层次（调用）关系 74.3详细设计 74.3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法 74.3.2.对主程序和其它主要函数伪码算法 114.3.3.函数的调用关系图 124.4测试与分析 124.4.1测试 124.4.2分析 134.5 附录 135 总结与展望 19参考文献 20 成绩评定 204.1.3.输出的形式本程序要输出的是分别把创建的第一个多项式和第二个多项式按指数升序排序，并且把计算加减后的运算结果按指数升序排列输出。

4.1.4.测试数据(1)正确：图1程序输出(2)错误：图2程序输出4.2总体设计4.2.1.本程序中用到的所有抽象数据类型的定义ADT List{初始条件：多项式L已存在。

操作结果：显示多项式。

AddPoly( L_1,L_2,L_add )初始条件：多项式L_1,L_2,L_add已存在。

操作结果：生成L_1,L_2之和的多项式L_add DiffPoly( L ,L_diff)初始条件：多项式L ,L_diff已存在。

操作结果：生成L的导数多项式L_add。

AlterPoly( L )初始条件：多项式L已存在。

操作结果：将L多项式取相反数。

}ADT Poly4.2.2.主程序的流程图3主程序流程4.2.3.各程序模块之间的层次（调用）关系图4模块层次调用关系4.3详细设计4.3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法Typedef Polynomial //定义结构体类型{float coef; //多项式系数int expn; //多项式指数struct Polynomial *next; //多项式的下一个指针域}*Polyn,Polynomial;void Insert( &p,&h) //定义插入函数{if(p.coef==0) //若p的系数是则释放pfree(p);else{q1=h;q2=h->next;while(q2&&q2.expn<p.expn) //找到链表中第一个指数大于p的指数的项{q1=q2;q2=q2.next;}PrintPolyn(pc);pc=SubtractPolyn(pa,pb);printf("\n输出多项式之差a-b="); PrintPolyn(pc);printf("\n 感谢使用此程序！\n"); DestroyPolyn(pa);DestroyPolyn(pb);4.3.3.函数的调用关系图图5函数调用关系4.4测试与分析4.4.1测试输入：a=2X+3X^2; b=2X^3+7X^4输出：a+b=2X+3X^2+ 2X^3+7X^4a-b=2X+3X^2-2X^3-7X^4图6程序输出。

数据结构课程设计系别电子信息系专业计算机科学与技术班级学号4090113姓名王健指导教师党群成绩2011年7 月14 日目录一、课程题目 (1)二、需求分析 (1)三、测试数据 (2)四、概要设计 (2)五、调用关系图 (3)六、程序代码 (3)七、心得体会及总结 (12)数据结构课程设计一、课程题目一元稀疏多项式计算器二、需求分析1、一元稀疏多项式简单计算器的功能是：1.1 输入并建立多项式；1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；1.3 求多项式a、b的导函数；1.4 计算多项式在x处的值；1.5多项式a和b相加，建立多项式a+b；1.6 多项式a和b相减，建立多项式a-b。

2、设计思路:2.1 定义线性表的动态分配顺序存储结构；2.2 建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。

每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。

多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思路分析要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。

为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：① 若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

数据结构实习报告班级 XXXXXX学生姓名 XXXXXX学号 *******XXXX指导教师 XXXXXX日期 2012年11月10日报告简介：整篇实习报告主要分为三部分：实习一，实习二以及实习困惑。

其中每个实习报告涉及6个部分：需求分析，设计，调试分析，用户手册，测试结果，源程序清单。

具体报告内容如下：实习一：一元稀疏多项式运算器的设计1、需求分析【问题描述】设计一个一元稀疏多项式简单计算器。

【基本要求】（1）输入并建立两个多项式；（2）多项式a与b相加，建立和多项式c；（3）多项式a与b相减，建立和多项式d；（4）输出多项式a,b,c,d。

输出格式：比如多项式a为：A(x)=c1xe1+ c2xe2+…+ cmxem，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜em。

2、设计（1）设计思想存储结构：以带头结点的单链表存储多项式。

算法主要思想：●首先定义单链表中每个结点的结构体类型，设计能够生成多项式链表的函数，这个函数的功能是可以根据给定的多项式来创建存储它的单链表。

●然后需要设计两个多项式相加的函数与两个多项式相减的函数。

●要检验多项式的运算结果以及初始的多项式链表正确与否，需要将其打印输出，故还需要设计打印输出函数。

●主函数的设计：依次调用多项式链表生成的函数、多项式相加减的函数，最后将结果打印输出。

（2）概要设计整个算法需要设计五个函数，分别是：多项式链表生成的函数、两个多项式相加的函数、两个多项式相减的函数、打印输出的函数以及主函数。

在设计各个函数之前，要定义单链表结点的结构体类型。

每个结点应该包括指数code、系数exp和指向下一个结点的指针next。

多项式链表生成的函数：函数的返回值应该为定义的结构体类型，不需要设置参数。

函数内部，需要有多项式指数和系数的输入，直至输入的系数为零时结束，将每一对输入的指数和系数保存到新结点中，并将结点插入到链表中。

一个一元稀疏多项式简单计算器课程设计报告课程课课课告学院,课程名,称课课班课,学生姓名, ,学号目课1 一元稀疏多课式课算器1.1 述概课了课课任意多课式的加法～法～因此课课课课表的课～有一系～指～下减构体它个数数一指课个个元素3使用课言,课言C课课课境,VC++ 6.01.2 课课容内、课课描述1课课一一元稀疏多课式课课课算器。

个基本要求,一元稀疏多课式课课课算器的基本功能是,;,课入建立多课式～并1;,课出多课式～课出形式课整序列,数～其中是多课式2n,c1,e1,c2,e2,…cn,en,n的课～数分课是第课的系和指～序按指降序排序～数数数数c1,e1,i;,多课式和相加～建立多课式3aba+b;;,多课式和相～建立多课式减4aba-b;;,课算多课式在课的课～5x;,课算器的界面;课做,。

仿真6、需求分析2;,课入的形式和课入课的范课,1课入是课课课入的～课入的容课多课式的系和指～课任意的整～指课大于从内数数数数数等于的整数0;,课出的形式2从屏并减幕课出～课示用课课入的多课式～课示多课式加以后的多课式的课。

;,程序所能到的功能达3,课入建立多课式～并a,课出多课式～课出形式课整序列,数其中是多课式的课数～bn,c1,e1,c2,e2,……,cn,en,n和分课是第课的系和指～序列按指降序排列～数数数cieii,多课式和相加～建立多课式～caba+b,多课式和相～建立多课式减～daba-b,多课式的课出形式课课表式～数学达e,系课课数的非零课的课出形式中略去系数～而的课出形式课。

f11-1x-x1.3 要课课概、存课课构1typedef struct Polynomial { float coef; int expn; struct Polynomial *next;}*Polyn,Polynomial;课课用以存放第构体课的系和指和下一指课～以课课课基课。

数数个i、函数2Polyn CreatePolyn(Polyn head,int m)课函用于建立一课指课课数个～课课数的一元多课式headm课函用于课毁多课式数void DestroyPolyn(Polyn p)课函用于课出多课式数void PrintPolyn(Polyn P) aPolyn AddPolyn(Polyn pa,Polyn pb)课函用于求解建立多课式数并～返回其课指课a+bPolyn SubtractPolyn(Polyn pa,Polyn pb)课函用于求解建立多课式数并～返回其课指课a-bfloat ValuePolyn(Polyn head,int x)课函用于课入数课～课算返回多课式的课并x课函用于比课数和的指数int compare(Polyn a,Polyn b) ab、流程课3一元稀疏多课式课算器课入建立多课式并课出多课式课算多课式在x课的课课算a+b课算a-b课束1.4 课课分析1、课课分析2、行课果运1.5 源程序代课#include<stdio.h>#include<stdlib.h>typedef struct Polynomial { float coef; int expn; struct Polynomial *next;}*Polyn,Polynomial;void Insert(Polyn p,Polyn h) { if(p->coef==0) free(p); else { Polynq1,q2; q1=h; q2=h->next; while(q2&&p->expn<q2->expn) { q1=q2; q2=q2->next; }if(q2&&p->expn==q2->expn) { q2->coef+=p->coef; free(p);if(!q2->coef){q1->next=q2->next;free(q2);}}else{p->next=q2;q1->next=p; } } } Polyn CreatePolyn(Polyn head,int m) { int i; Polyn p;p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL;for(i=0;i<m;i++) { p=(Polyn)malloc(sizeof(struct Polynomial));课课入第课的系指数与数用空格隔课printf("%d ,:",i+1);scanf("%f %d",&p->coef,&p->expn); Insert(p,head); } return head; } void DestroyPolyn(Polyn p) {Polyn q1,q2; q1=p->next; q2=q1->next;while(q1->next) { free(q1); q1=q2; q2=q2->next; } }void PrintPolyn(Polyn P) {Polyn q=P->next; int flag=1;if(!q) { putchar('0'); printf("\n"); return; } while(q) { if(q->coef>0&&flag!=1) putchar('+'); if(q->coef!=1&&q->coef!=-1){ printf("%g",q->coef);if(q->expn==1) putchar('X'); else if(q->expn) printf("X^%d",q->expn); }else { if(q->coef==1) { if(!q->expn) putchar('1');else if(q->expn==1) putchar('X'); else printf("X^%d",q->expn); }if(q->coef==-1) { if(!q->expn) printf("-1"); else if(q->expn==1)printf("-X");else printf("-X^%d",q->expn); } } q=q->next; flag++; } printf("\n");} int compare(Polyn a,Polyn b) { if(a&&b) {if(!b||a->expn>b->expn) return 1; else if(!a||a->expn<b->expn)return -1; else return 0; } else if(!a&&b) return -1; else return1; }Polyn AddPolyn(Polyn pa,Polyn pb) {Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc;hc=(Polyn)malloc(sizeof(struct Polynomial)); hc->next=NULL; headc=hc;while(qa||qb) { qc=(Polyn)malloc(sizeof(struct Polynomial));switch(compare(qa,qb)) {case 1: { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn;qa=qa->next; qb=qb->next; break; }case-1:{qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;}}if(qc->coef!=0){ qc->next=hc->next; hc->next=qc; hc=qc; }else free(qc); }return headc; }Polyn SubtractPolyn(Polyn pa,Polyn pb) {Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p){ p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) p->coef*=-1; return pd;}float ValuePolyn(Polyn head,int x) {Polyn p; int i,t; floatsum=0;for(p=head->next;p;p=p->next){t=1;for(i=p->expn;i!=0;){if(i<0){t/=x;i++;} else{t*=x;i--;} } sum+=p->coef*t; }return sum; }Polyn MultiplyPolyn(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial)); hf->next=NULL;for(;qa;qa=qa->next) {for(qb=pb->next;qb;qb=qb->next) {pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef;pf->expn=qa->expn+qb->expn; Insert(pf,hf); } } return hf; }void main(){ int m,n,a,x,f,k=1; Polyn pa=0,pb=0,pc; while(k!=0){ 课课入的课数printf("a :"); scanf("%d",&m); pa=CreatePolyn(pa,m);课课入的课数printf("b :"); scanf("%d",&n); pb=CreatePolyn(pb,n);课出多课式课出多课式printf(" * 1:a 2:b \n");代入的课课算代入的课课算printf(" * 3:xa 4:xb\n");课出课出printf(" * 5:a+b 6:a-b\n");课出退出printf(" * 7:a*b 0:\n");课课课操作,while(a) { printf("\n "); scanf(" %d",&f); switch(f) { 多课式case 1: { printf("\na="); PrintPolyn(pa); break; }多课式case 2: { printf("\nb="); PrintPolyn(pb); break; }课入的课,case 3: { printf("xx="); scanf("%d",&x);课 printf("\n x=%da=%.3f\n",x,ValuePolyn(pa,x)); break; }课入的课,case 4: {printf("xx="); scanf("%d",&x);课 printf("\n x=%d b=%.3f\n",x,ValuePolyn(pb,x)); break; } case5:{ pc=AddPolyn(pa,pb); printf("\n a+b="); PrintPolyn(pc); break; } case 6:{ pc=SubtractPolyn(pa,pb);printf("\n a-b="); PrintPolyn(pc); break; }case 7:{ pc=MultiplyPolyn(pa,pb);printf("\na*b=");PrintPolyn(pc); break; }case 0:{ DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; }您的课课课课～课重新课default: printf("\n !\n"); } } } }2 哈夫曼课/课课器2.1 述概本课程课课用于建立哈夫曼课～课其课行课课、课课以及打印。

#include<stdio.h>#include<malloc.h>#include<stdlib.h>//定义多项式的项typedef struct Polynomial{float coef。

int expn。

struct Polynomial *next。

}*Polyn,Polynomial。

void Insert(Polyn p,Polyn h>{if(p->coef==0> free(p>。

//系数为0的话释放结点else{Polyn q1,q2。

q1=h。

q2=h->next。

while(q2&&p->expn<q2->expn>{//查找插入位置q1=q2。

q2=q2->next。

}if(q2&&p->expn==q2->expn>{//将指数相同相合并q2->coef+=p->coef。

free(p>。

if(!q2->coef>{//系数为0的话释放结点q1->next=q2->next。

free(q2>。

}}else{//指数为新时将结点插入p->next=q2。

q1->next=p。

}}}Polyn CreatePolyn(Polyn head,int m>{//建立一个头指针为head、项数为m的一元多项式Polyn p。

p=head=(Polyn>malloc(sizeof(struct Polynomial>>。

head->next=NULL。

for(i=0。

i<m。

i++>{p=(Polyn>malloc(sizeof(struct Polynomial>>。

//建立新结点以接收数据 printf("请输入第%d项的系数与指数:",i+1>。

实验一 一元稀疏多项式的表示及加法运算一、 需求分析1. 程序的功能:● 多项式以指数递增的顺序输入。

● 设计的数据结构应有利于表示任意一元稀释多项式。

● 输出原始多项式及运算结果。

● 附加功能：乱序输入计算表达式结果 2. 输入输出要求： ● 多项式以指数递增的方式输入 ●输出原始多项式及其结果3. 测试数据(1)1785937x x x +++ , 879228x x x -+ (2)0 , 879228x x x -+(3)87109228x x x -+ , -1附加功能测试数据：(4) 53658672x x x x +--,268x x --二、 概要设计●所用数据结构定义：struct Term{ //多项式结点的定义 float coef; //系数 int exp; //指数 Term * link;Term(float c,int e,Term * next=NULL){coef=c;exp=e;link=next;} Term *InsertAfter(float c,int e); Term & operator -=(Term & t){if ==exp) coef-=;return *this ;} Term & operator +=(Term & t){if ==exp) coef+=;return *this ;}friend ostream & operator <<(ostream &,const Term&);};class Polynomal{ //多项式的类定义public:Polynomal(){ //构造函数，建立空链表first=new Term(0,-1);first->link=first; //必须链成环}~Polynomal(){makeEmpty();}Polynomal(Polynomal & R); //复制构造函数Polynomal & operator=(const Polynomal & R); //重载复制赋值操作符void insert(float c,int e,Polynomal& R);//对于二项式进行插入排序 Polynomal sort();//对于多项式进行排序Term * getHead() const{return first;}void makeEmpty();private:Term * first;friend ostream & operator<<(ostream &,const Polynomal&);friend istream & operator>>(istream &,Polynomal&);friend Polynomal operator+(Polynomal&,Polynomal&);};主程序的流程及各模块之间的层次关系：1)主程序流程2)模块之间层次关系三、详细设计1、插入一个结点Term* Term::InsertAfter(float c,int e){//在当前由this指针指示的项(即调用此函数的对象)后面插入一个新项link=new Term(c,e,link); //创建一个新结点，自动链接return link; //插入到this结点后面2、重载各运算符（1）Polynomal & Polynomal::operator =(const Polynomal & R){makeEmpty(); //先清空first=new Term(0,-1);Term *destptr=first,*srcptr=>link;while(srcptr!={destptr->InsertAfter(srcptr->coef,srcptr->exp);srcptr=srcptr->link;destptr=destptr->link;}destptr->link=first; //必须链成环return *this;}#伪代码清空；动态创建节点first；创建节点指针*destptr指向first，创建节点指针*srcptr指向>link；WHILE（R链未遍历结束）将R链表中的结点一次插入到first之后；ENDWHILE将*destptr连成环；结束（2）istream& operator>>(istream& in,Polynomal& x){Term *rear=;int e;float c; //定义尾指针rearwhile(1){cout<<"输入：系数,指数（以、-1结束）:"<<endl;in>>c>>e;if(c==0&&e==-1)break; //用e小于控制输入结束rear=rear->InsertAfter(c,e); //链接到rear所指结点后}return in;}（3）ostream & operator<<(ostream& out,const Polynomal & x){ //输出到附加头结点的多项式链表xTerm *current=>link;cout<<"The polynomal is:"<<endl;bool h=true;while(current!={if(h==false&&current->coef>out<<"+";h=false;if(current->coef==0){out<<"0";current=current->link;}else{out<<*current; //调用term类的重载操作"<<"current=current->link;}}out<<endl;return out;}#伪代码创建指针*current指向当前节点>link；设置标志位hWHILE<遍历多项式>IF<标志位h为假，当前指向节点指数为0>打印符号+；改变标志位；ELSE打印该节点；指向下一个节点；ENDIFENDWHILE（4）Polynomal operator+(Polynomal& A,Polynomal& B){Term *pa,*pb,*pc,*p,*last;float temp;Polynomal C;pc=;pa=>link;pb=>link;while(pa!= &&pb!={ //两两比较if(pa->exp==pb->exp){ //对应项指数相等temp=pa->coef+pb->coef; //系数相加if(fabs(temp)!=0)pc=pc->InsertAfter(temp,pa->exp);pa=pa->link ;pb=pb->link;}else if(pa->exp<pb->exp){pc=pc->InsertAfter(pa->coef,pa->exp); //pa指数小pa=pa->link;}else{pc=pc->InsertAfter (pb->coef,pb->exp);pb=pb->link;} //pb指数小，加入ah 链}if(pa!={p=pa;last=;}else{p=pb;last=;}while(p!=last){pc=pc->InsertAfter (p->coef,p->exp );p=p->link;}return C;}#伪代码*Pa=二项式a的当前节点;*pb=二项式b的当前节点;新建二项式c；WHILE<遍历二项式>IF<pa,pb的指数相等>IF<指数之和不为0>系数相加后将插入节点到c尾部；ENDIF比较a,b的下一个节点ELSEIF<pa的指数小于pb的>将pa的当前节点复制到c尾部；Pa后移；ELSE将Pb的当前节点复制到c尾部；Pb后移；ENDIFENDWHILEIF<pa,pb中某一多项式未遍历结束>将未遍历空的那一个所在的二项式剩余部分复制到c尾部；ENDIF返回合成多项式3、排序算法（1）Polynomal Polynomal::sort(){Polynomal R;Term *p=first;p=p->link;while(p!=first){insert(p->coef,p->exp,R);p=p->link;}return R;}（2）void Polynomal::insert(float c, int e, Polynomal &R){Term *q=,*p=>link, *r;if(p== {q->link=new Term(c,e);//c为空q->link->link=;}else { while (p!={if (p->exp==e)//指数相等 { p->coef+=c;if (p->coef!=0)break ; if (p->coef==0) { q->link=p->link; r=p; p=p->link; delete r; break ;}}else if (p->exp>e)//e 小于当前结点的指数 { q->link=new Term(c,e); q=q->link; q->link=p; break ; } else { p=p->link; q=q->link;}} if (p== //e 大于R 中每一项的指数，插在表尾 { q->link=new Term(c,e); q->link->link=p; }}}四、 调试分析1、调试中的问题（1）在测试数据一时，出现带有常数项的多项式，常数项被构造为一次项，例如多项式1785937x x x +++被输出为1785937x x x x +++解决办法：在重载运算符+中，当pa 的指数小时，将程序由{pc=pc->InsertAfter (pa->coef,pb->exp);pb=pb->link;}改为{pc=pc->InsertAfter (pb->coef,pb->exp);pb=pb->link;}即可；（2）在调试问题二的过程中，出现的0被程序自动忽略，不能打印使得输出结果为879228x x x -++解决办法：在重载输出运算符的程序模块中添加： if(current->coef==0){ out<<"0";current=current->link; }即可保证程序的输出正常，但是是以8792280x x x -++作为输出的。