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

目录一、需求分析 (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 -++作为输出的。

#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);scanf("%f %d",&p->coef,&p->expn);Insert(p,head); //调用Insert函数插入结点}return head;}void DestroyPolyn(Polyn p){//销毁多项式pPolyn 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){ //若多项式为空，输出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1){//系数非1或-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;//a多项式已空，但b多项式非空else return 1;//b多项式已空，但a多项式非空}Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头指针 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);//当相加系数为0时，释放该结点}return headc;}Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多项式a-b，返回其头指针Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p){ //将pb的系数取反p->coef*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) //恢复pb的系数p->coef*=-1;return pd;}int ValuePolyn(Polyn head,int x){//输入x值，计算并返回多项式的值Polyn p;int i;int sum=0,t;for(p=head->next;p;p=p->next){t=1;for(i=p->expn;i!=0;){if(i<0){t/=x;i++;}//指数小于0，进行除法else{t*=x;i--;}//指数大于0，进行乘法}sum+=p->coef*t;}return sum;}Polyn Derivative(Polyn head){//求解并建立导函数多项式，并返回其头指针Polyn q=head->next,p1,p2,hd;hd=p1=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hd->next=NULL;while(q){if(q->expn!=0){ //该项不是常数项时p2=(Polyn)malloc(sizeof(struct Polynomial));p2->coef=q->coef*q->expn;p2->expn=q->expn-1;p2->next=p1->next;//连接结点p1->next=p2;p1=p2;}q=q->next;}return hd;}Polyn MultiplyPolyn(Polyn pa,Polyn pb){//求解并建立多项式a*b，返回其头指针Polyn hf,pf;Polyn qa=pa->next;Polyn qb=pb->next;hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点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);//调用Insert函数以合并指数相同的项}}return hf;}void main(){int m,n,a,x;char flag;Polyn pa=0,pb=0,pc;printf(" 欢迎使用多项式操作程序\n\n");printf("请输入a的项数:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多项式aprintf("请输入b的项数:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多项式b//输出菜单printf("*******************************************************\n");printf(" * 多项式操作程序*\n");printf(" * *\n");printf(" * A:输出多项式 B:输出多项式 b*\n");printf(" * *\n");printf(" * C:输出a的导数 D:输出b的导数*\n");printf(" * *\n");printf(" * E:代入x的值计算a F:代入x的值计算b*\n");printf(" * *\n");printf(" * G:输出a+b H:输出a-b*\n");printf(" * *\n");printf(" * I:输出a*b J:退出程序*\n");printf(" * *\n");printf("*******************************************************\n");while(a){printf("\n请选择操作：");scanf(" %c",&flag);//空格符号一定要注意switch(flag){case'A':case'a':{printf("\n 多项式a=");PrintPolyn(pa);break;}case'B':case'b':{printf("\n 多项式b=");PrintPolyn(pb);break;}case'C':case'c':{pc=Derivative(pa);printf("\n 多项式a的导函数为：a'=");PrintPolyn(pc);break;}case'D':case'd':{pc=Derivative(pb);printf("\n 多项式b的导函数为：b'=");PrintPolyn(pc);break;}case'E':case'e':{printf("输入x的值：x=");scanf("%d",&x);printf("\n x=%d时，a=%d\n",x,ValuePolyn(pa,x));break;}case'F':case'f':{printf("输入x的值：x=");scanf("%d",&x);printf("\n x=%d时，b=%d\n",x,ValuePolyn(pb,x));break;}case'G':case'g':{pc=AddPolyn(pa,pb);printf("\n a+b=");PrintPolyn(pc);break;}case'H':case'h':{pc=SubtractPolyn(pa,pb);printf("\n a-b=");PrintPolyn(pc);break;}case'I':case'i':{pc=MultiplyPolyn(pa,pb);printf("\n a*b=");PrintPolyn(pc);break;}case'J':case'j':{printf("\n 感谢使用此程序！\n");DestroyPolyn(pa);DestroyPolyn(pb);a=0;break;}default:printf("\n 您的选择错误，请重新选择!\n");}}}。

数据结构课程设计——一元多项式计算一、课程设计题目及要求二、设计思路和方法三、程序流程图四、程序代码及注释五、测试结果及分析六、结论七、参考文献本次课程设计的题目为“一元多项式计算”，要求设计一个程序，能够实现一元多项式的加、减、乘、求导和求值等操作。

在设计思路和方法上，我们采用了链表的数据结构来存储多项式，同时设计了相应的函数来实现各种操作。

程序的流程图如下所示：插入流程图）程序的代码及注释如下所示：插入代码及注释）在测试结果及分析方面，我们对程序进行了多组测试，并对其进行了详细的分析和比较。

结果表明，我们的程序能够正确地实现各种操作，并且具有较高的效率和稳定性。

综上所述，本次课程设计的目标已经得到了圆满地实现，我们对于所取得的成果感到非常满意。

同时，我们也希望能够通过这次课程设计，加深对于数据结构及其应用的理解和掌握，为今后的研究和工作打下坚实的基础。

设计目标：本课程设计旨在结合理论与实际应用，提高学生组织数据及编写大型程序的能力。

通过掌握数据组织、算法设计和算法性能分析的方法，培养学生良好的程序设计能力。

具体实现是利用单链表表示一元多项式，实现多项式的输入、建立、输出、相加、相减和相乘。

总体设计：2.1 数据结构描述与定义：一元多项式定义系数和指数结构如下：coef，expn和next。

定义多项式的结构为线性链表的存储结构，每个结点包含三个元素：系数coef，指数expn和指向下一个结点的指针*next。

多个单项式通过指针连接起来，形成一个多项式。

2.2 模块设计：从实现多项式运算过程的角度来分析，至少需要以下子功能模块：多项式创建、销毁、输出、相加、相减和相乘。

定义并调用的函数有：Insert、CreatePolyn、DestroyPolyn、PrintPolyn、AddPolyn、SubtractPolyn、XXX和main函数。

注：该文章中没有明显的格式错误和需要删除的段落，因此没有进行小幅度改写。

目录1问题描述 (1)2需求分析 (1)3概要设计 (1)3.1[程序设计思路] (1)3.2[存储结构设计] (1)3.3[主要算法设计] (2)3.3.1链表的操作 (2)3.3.2本程序的结构 (3)3.4[测试用例设计] (6)4详细设计 (6)4.1链表存储结构定义和创建 (6)4.2相乘算法 (7)4.3实现乘法的核心算法函数 (7)4.4main和其他的函数核心代码 (9)5调试分析 (11)6程序说明 (11)7经验和体会 (11)7.1经验 (11)7.2体会 (11)8程序结果 (12)8.1程序清单 (12)8.2结果 (16)稀疏一元多项式的相乘1问题描述：设计一个实现稀疏多项式乘法的程序2需求分析：编程实现两个一元多项式相乘，要求：2.1输入并建立多项式；2.2输出多项式，输出形式为整数序列：n,c1,e1,c2,e2``````,cn.,en,其中n 是多项式的系数，ci 和ei 分别是第i 项的系数和指数，序列按指数降序排列。

2.3多项式a 和b 相乘，建立结果多项式a*b;2.4测试。

3概要设计3.1程序设计思路建立链式结构存储多项式，在多项式a 和b 相乘多过程实际是根据对链表a 和b 进行操作所得的结果建立新的链表的过程，将a 中的每一项和b 中的结点相乘，所得的结果产生新的结点，再根据降序排列的判断条件或将其插入新链表，或直接将其系数加到和其指数相等的结点的系数上去，在相加后和为零的情况下删除结点，最后就建立起了一条存贮a 和b 相乘的结果的链表，再输出即可。

3.2存储结构采用链式存储结构，结点分三部分，分别存放系数，指数和指针。

Eg.多项式a 的项数为3，按照降序排列的各项的系数和指数分别为（3，2）（2，1），（1，0）多项式b 的项数为2，按照降序排列的各项的系数和指数分别为(2, 7), (1,0)3．3主要算法设计3．3．1链表的操作typedef struct pnode //存储结构定义{float coef；//结点的一个区域存放系数int exp;//结点的一个区域存放指数struct pnode *link;//存放指针}pnode,*node;pnode *head;//构造函数pnode *Creat(int k,char c)//输入并建立多项式，其项数为kvoid output(pnode *head)//输出多项式pnode * multiply (pnode *heada,pnode *headb)//实现以链表存储的a和b的相乘，并建立新的链表存储起结果3．3．2本程序的结构3.3.2.1主程序模块：void main(){定义指针，字符，整型变量；向屏幕输出输入提示；接受输入的字符；调用Creat(int k,char c)建立多项式a并将返回的多项式的头指针赋值给heada输出建立好的多项式；向屏幕输出输入提示；接受输入的字符；调用Creat(int k,char c)建立多项式b并将返回的多项式的头指针赋值给headb；输出建立好的多项式；调用multiply (pnode *heada,pnode *headb)函数实现两个多项式的相乘并建立新的链表并将头指针赋值给headc调用output(pnode *head)输出结果多项式；}3.3.2.2乘法实现模块——实现多项式的相乘；3.3.2.3乘法实现的核心算法：pnode *pa,*pb;pnode *pcNew;pnode *pc;pnode *pcRemark;//标记指针，记录每次操作的位置pnode *pcDel;int exp;pa=heada->link;pb=headb->link;pc=(pnode *)malloc(sizeof(pnode));//生成c的头结点pc->link=NULL;//定义指针，多项式的系数，并生成结点存放多项式相乘后的信息，将pa,pa分别指向链表a,b的首元结点while(pa)//当pa不为空的情况下执行操作,对a的某一结点去和b的所有结点进行操作{pcRemark=pc;//当a的某一结点和b中的所有结点都乘完之后,将pcRemark重新//回到头结点以便新结点插入的查找while(pb)// 当pb不为空的情况下执行操作{生成结点pcNew存放相乘后的信息while(pcRemark->link && exp<pcRemark->link->exp)//当的下一个结点的指数仍比pcNew的大的时候将pcRemark后移，一直到下一结点比乘后的指数小或者相等的时候跳出循环if(pcRemark->link && exp==pcRemark->link->exp)//当pcRemark的下一个结点的指数和pcNew相等的情况{if(coef+pcRemark->link->coef==0.0)/{如果它们系数相加为零，就释放链表中的那个结点}else{否则话将pcRemark->link的指数修改为它们相加之和}}else//否则在pcRemark为尾结点的情况下{将pcNew直接链到其后}pb=pb->link;//将的结点后移}pb=headb->link;//当a的一项和b中的每一项都乘完之后，将pb 重新回到头结点}return(pc);}3.3.2.4创建链表函数模块——生成链表存储多项式。

实验报告题目：一元稀疏多项式班级： xxx 姓名：xxx 学号：xxxxxxx 日期：2010.5.15一．需求分析1. 本演示实验中，用一个链表表示一元稀疏多项式的各自的系数和指数，其中系数用浮点型存储，且系数不为0，指数以整形存储。

每一个多项式的输入以“空格符”为标志依次输入系数与指数最终程序会将指数相同的各项相加，并自动滤去系数为0的项，输出的多项式按降序排列。

2. 演示程序会以对话方式供用户选择各项功能，程序上显示实现各项功能的编号，用户输入对应地编号即进入相应的模式，在不同模式即可完成不同功能。

3. 程序执行的功能包括：（1）输出多项式的项数、系数与指数；（2）建立两个多项式并相加；（3）建立两个多项式并相减；（4）求一个多项式的导数；（5）建立两个多项式并相乘；（6）求一个多项式在x 处的值；二．概要设计为实现上述功能，应以有序链表表示多项式。

为此需要两个抽象数据类型表示链表和多项式。

1．有序链表的抽象数据类型定义为：ADT LinkedPoly{数据对象：D={(xi,yi)|xi为浮点型，yi为整形，i=1,2……,n n>=0}数据关系：R={}基本操作：Status Init(&L)操作结果：构造链表。

void Insert(&L, a, b)初始条件：链表L存在。

操作结果：当a非0时将插入新的结点。

void descend (&L)初始条件：链表L存在。

操作结果：将链表进行排序并将指数相同的系数进行合并。

void ascend(&L)初始条件：链表L存在。

操作结果：将链表进行排序并将指数相同的系数进行合并。

int length(L)初始条件：链表L存在。

操作结果：返回链表的长度。

void load(&p, &a, &b)初始条件：p指向的结点存在。

操作结果：把结点的指数和系数赋值给a和b。

}ADT LinkedPoly2．多项式数据类型的定义为：ADT formula{数据对象：D={(xi,yi)|xi为浮点型，yi为整形，i=1,2……,n n>=0}数据关系：R={(<yi-1,yi>|yi-1>yi, i=1,2……,n n>=0}基本操作：void plus(&L, a, b )初始条件：多项式L,a,b存在。

一元稀疏多项式数据结构一元稀疏多项式是数学领域中常见的一种数据结构，用于表示只含有一个未知数的多项式，并且该多项式中只有少数项系数不为零。

在计算机科学中，我们通常需要对多项式进行存储、计算和操作，因此设计一种高效的数据结构来表示一元稀疏多项式是非常重要的。

在一元稀疏多项式数据结构中，我们需要考虑如何表示多项式中的每一项以及它们的系数和指数。

一种常见的表示方式是使用链表，其中每个节点表示一个多项式的项。

每个节点包含两个部分：系数和指数。

系数表示该项的系数大小，指数表示该项的指数大小。

为了实现高效的存储和操作，我们可以对多项式进行排序，按照指数的大小进行升序排列。

这样可以使得高次项在链表的末尾，低次项在链表的开头，方便后续的计算和操作。

在创建一元稀疏多项式数据结构时，我们需要考虑如何添加和删除多项式的项。

对于添加项的操作，我们可以按照指数的大小找到对应的位置，并插入新的节点。

对于删除项的操作，我们可以按照指数的大小找到对应的位置，并删除该节点。

这样可以保证链表的有序性。

在进行多项式的计算和操作时，我们需要考虑如何实现多项式的加法、减法和乘法。

对于加法和减法，我们可以按照指数的大小进行对应项的相加或相减。

对于乘法，我们可以使用多项式的乘法规则，将每一项相乘后按照指数的大小进行合并。

这样可以得到最终的结果。

除了基本的计算和操作，一元稀疏多项式数据结构还可以支持求导、积分和求解方程等高级操作。

对于求导操作，我们可以将每一项的系数乘以指数，并将指数减一。

对于积分操作，我们可以将每一项的系数除以指数加一，并将指数加一。

对于求解方程操作，我们可以使用牛顿法等数值方法来逼近多项式的根。

在实际应用中，一元稀疏多项式数据结构可以用于解决各种数学和工程问题。

例如，在计算机图形学中，多项式可以表示曲线和曲面，通过对多项式的计算和操作，可以实现图形的绘制和变换。

在信号处理中，多项式可以表示信号的频谱和滤波器，通过对多项式的计算和操作，可以实现信号的分析和处理。

数据结构课程设计第一篇：数据结构课程设计一、课程题目：一元稀疏多项式计算器二、需求分析1、一元稀疏多项式简单计算器的功能是：1.1 输入并建立多项式；1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；1.3多项式a和b相加，建立多项式a+b；1.4 多项式a和b相减，建立多项式a-b。

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

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

3、程序执行的命令包括：1）输入多项式a；2）输入多项式b;3）求a+b;4)求a-b；5）求a*b；6）求a的导数；7）求b的导数；8）退出程序。

4、测试数据：1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^-3-x);3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);4、(x+x^3)+(-x-x^3)=0;5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);6、(x+x^2+x^3)+0=x+x^2+x^3.7、互换上述测试数据中的前后两个多项式三、概要设计为了实现上述功能需用带表头结点的单链表存储多项式。

为此需要两个抽象的数据类型：线性表和多项式。

1.一元稀疏多项式计算器(不选)[问题描述]设计一个一元稀疏多项式简单计算器。

[基本要求]输入并建立多项式；输出多项式，输出形式为整数序列：n, c1, e1, c2, e2,……, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序；多项式a和b相加，建立多项式a+b;多项式a和b相减，建立多项式a-b;[测试数据](2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3)(1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1)(x+x3)+(-x-x3)=0(x+x2+x3)+0=(x3+x2+x)[实现提示]用带头结点的单链表存储多项式，多项式的项数存放在头结点中。

2.背包问题的求解（一人）[问题描述]假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。

例如：当T=10，各件物品的体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2）[实现提示]可利用回溯法的设计思想来解决背包问题。

首先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。

但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。

由于回溯求解的规则是“后进先出”因此自然要用到栈。