数据结构实验报告,一元多项式资料

数据结构实验报告实验名称：实验一—线性表实现一个多项式学生姓名：黄锦雨班级：2011211109班内序号：20学号：2011210263日期：2012年10月31日实验目的：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3+ … + a n x n要求：1．能够实现一元多项式的输入和输出2．能够进行一元多项式相加3．能够进行一元多项式相减4．能够计算一元多项式在x处的值5．能够计算一元多项式的导数（选作）6．能够进行一元多项式相乘（选作）7．编写测试main()函数测试线性表的正确性2. 程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。

如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。

两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表里。

2.1本程序完成的主要功能：1.输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。

输出即是将多项式的内容向屏幕输出。

2.多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。

将每项运算得到的结果都插入到新的链表中，形成结果多项式。

3.多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。

数据结构实验报告-一元多项式
实验目的
1.使用C语言编写一元多项式运算的程序
2.理解和掌握链表的基本概念和操作
3.熟悉链表在实际问题中的应用
实验内容
1.设计一元多项式数据结构，支持多项式的输入、输出、加、减、乘、求导等计算。

2.使用链表来实现多项式数据结构。

3.编写测试程序，测试多项式数据结构的正确性和效率。

实验步骤
1.设计一元多项式数据结构，包括多项式中的每一项所包含的系数和指数，以及链表节点结构体定义。

typedef struct node
{
float coef; // 系数
int expn; // 指数
struct node *next; // 指向下一个节点的指针
} Node, *pNode;
2.按照上述定义的结构体，实现多项式的输入函数。

3.利用链表实现多项式的加法函数。

6.编写测试程序，测试多项式数据结构的正确性和效率。

实验结果
1.输入第一个多项式为 3x^3+2x^2+3 第二个多项式为 2x^3+x^2+4x+1
2.经过程序的处理，两个多项式的加法结果为 5.00x^3+
3.00x^2+
4.00x+4.00
两个多项式的乘法结果为
6.00x^6+10.00x^5+5.00x^4+10.00x^3+14.00x^2+19.00x+3.00
第一个多项式求导结果为 9.00x^2+4.00x
1.链表可以有效地实现多项式数据结构的存储和操作，具有较好的效率和灵活性。

2.通过本次实验，能够更加深入地理解数据结构中链表的应用，有助于提高编程能力和实际问题解决能力。

数据结构实验报告实验名称：实验一题目3 一元多项式学生姓名：许虎班级：信通20班内序号：10学号：78日期：2012年11月2日1．实验要求实验目的：利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3+ … + a n x n并实现相应功能。

实验内容：使用一元多项式类存储多项式元素，通过定义并实现相关函数完成相应的功能，并通过设计的main函数测试了其正确性。

用户可自行输入正确的多项式进行相关运算，得到相应结果。

相关函数实现的功能：1.能够实现一元多项式的输入和输出2.能够进行一元多项式相加3.能够进行一元多项式相减4.能够计算一元多项式在x处的值5.能够计算一元多项式的导数6.能够进行两个一元多项式相乘2. 程序分析2.1 存储结构存储结构：单链表（带头节点）单链表示意图如下：在本程序中使用结构类型element（赋给模版类型T）数组data储存数据成员，包含coef（系数）和exp（指数）两个成员，但仍为一维数组。

在节点构造类型Node（运用了模版类）中定义了指针域next指向下一个结点，直到链表尾将next置空，front头指针为该链表类私有数据成员，如此得到多项式链表（单链表）。

2.2 关键算法分析1、关键算法：1）一元多项式类求和函数（1）初始化工作指针p_prior(指向A链表头结点),p(p->next)，q(指向B链表第一个结点)。

（2）若p和q都不为空，则循环下列操作：（3）若p->data.exp<q->data.exp，则p_prior=p;p=p->next。

（4）否则，若p->data.exp>q->data.exp，则：将q结点加入到A链表p结点之前，q指向B链表下移个结点。

（5）否则，p->data.coef=p->data.coef+q->data.coef;（6）若p->data.coef==0，删除p结点，p指向下一个结点，删除q结点，q指向下一个结点。

一元多项式计算：程序要求：1）、能够按照指数降序排列建立并输出多项式；2）、能够完成两个多项式的相加、相减，并将结果输入。

概要设计：1.功能：将要进行运算的多项式输入输出。

2.数据流入：要输入的多项式的系数与指数。

3.数据流出：合并同类项后的多项式。

4.程序流程图：多项式输入流程图如图3.2.1所示。

5.测试要点：输入的多项式是否正确，若输入错误则重新输入2、多项式的加法（1）功能：将两多项式相加。

（2）数据流入：输入函数。

（3）数据流出：多项式相加后的结果。

（4）程序流程图：多项式的加法流程图如图3.2.2所示。

（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。

3、多项式的减法（1）功能：将两多项式相减。

（2）数据流入：调用输入函数。

（3）数据流出：多项式相减后的结果。

（4）程序流程图：多项式的减法流程图如图3.2.3所示。

（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。

详细代码：#include<iostream>#include<conio.h>#include<stdlib.h>using namespace std; struct Node{float coef;//结点类型int exp;};typedef Node polynomial;struct LNode{polynomial data;//链表类型LNode *next;};typedef LNode* Link;void CreateLink(Link &L,int n);void PrintList(Link L);void PolyAdd(Link &pc,Link pa,Link pb);void PolySubstract(Link &pc,Link pa,Link pb); void CopyLink(Link &pc,Link pa);void PolyMultiply(Link &pc,Link pa,Link pb);int JudgeIfExpSame(Link pa,Link e);void DestroyLink(Link &L);int CompareIfNum(int i);void DestroyLink(Link &L){Link p;p=L->next;while(p){L->next=p->next;delete p;p=L->next;}delete L;L=NULL;}//创建含有n个链表类型结点的项，即创建一个n项多项式void CreateLink(Link &L,int n){if(L!=NULL){DestroyLink(L);}Link p,newp;L=new LNode;L->next=NULL;(L->data).exp=-1;//创建头结点p=L;for(int i=1;i<=n;i++){newp=new LNode;cout<<"请输入第"<<i<<"项的系数和指数:"<<endl;cout<<"系数:";cin>>(newp->data).coef;cout<<"指数:";cin>>(newp->data).exp;if(newp->data.exp<0){cout<<"您输入有误，指数不允许为负值!"<<endl;delete newp;i--;continue;}newp->next=NULL;p=L;if(newp->data.coef==0){cout<<"系数为零，重新输入!"<<endl;delete newp;i--;continue;}while((p->next!=NULL)&&((p->next->data).exp<(newp->data).exp)){p=p->next; //p指向指数最小的那一个}if(!JudgeIfExpSame( L, newp)){newp->next=p->next;p->next=newp;}else{cout<<"输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式"<<endl;delete newp;DestroyLink(L);CreateLink(L,n); //创建多项式没有成功，递归调用重新创建break;}}}/*判断指数是否与多项式中已存在的某项相同*/int JudgeIfExpSame(Link L,Link e){Link p;p=L->next;while(p!=NULL&&(e->data.exp!=p->data.exp))p=p->next;if(p==NULL)return 0;else return 1;}/*输出链表*/void PrintList(Link L){Link p;if(L==NULL||L->next==NULL)cout<<"该一元多项式为空！"<<endl;else{p=L->next;//项的系数大于的种情况if((p->data).coef>0){if((p->data).exp==0)cout<<(p->data).coef;else if((p->data).coef==1&&(p->data).exp==1)cout<<"x";else if((p->data).coef==1&&(p->data).exp!=1)cout<<"x^"<<(p->data).exp;else if((p->data).exp==1&&(p->data).coef!=1)cout<<(p->data).coef<<"x";else cout<<(p->data).coef<<"x^"<<(p->data).exp; }//项的系数小于的种情况if((p->data).coef<0){if((p->data).exp==0)cout<<(p->data).coef;else if(p->data.coef==-1&&p->data.exp==1)cout<<"-x";else if(p->data.coef==-1&&p->data.exp!=1)cout<<"-x^"<<p->data.exp;else if(p->data.exp==1)cout<<p->data.coef<<"x";else cout<<(p->data).coef<<"x^"<<(p->data).exp; }p=p->next;while(p!=NULL){if((p->data).coef>0){if((p->data).exp==0)cout<<"+"<<(p->data).coef;else if((p->data).exp==1&&(p->data).coef!=1)cout<<"+"<<(p->data).coef<<"x";else if((p->data).exp==1&&(p->data).coef==1)cout<<"+"<<"x";else if((p->data).coef==1&&(p->data).exp!=1)cout<<"+"<<"x^"<<(p->data).exp;else cout<<"+"<<(p->data).coef<<"x^"<<(p->data).exp; }if((p->data).coef<0){if((p->data).exp==0)cout<<(p->data).coef;else if(p->data.coef==-1&&p->data.exp==1)cout<<"-x";else if(p->data.coef==-1&&p->data.exp!=1)cout<<"-x^"<<p->data.exp;else if(p->data.exp==1)cout<<p->data.coef<<"x";else cout<<(p->data).coef<<"x^"<<(p->data).exp;}p=p->next;}}cout<<endl;}/*把一个链表的内容复制给另一个链表*/void CopyLink(Link &pc,Link pa){Link p,q,r;pc=new LNode;pc->next=NULL;r=pc;p=pa;while(p->next!=NULL){q=new LNode;q->data.coef=p->next->data.coef;q->data.exp=p->next->data.exp;r->next=q;q->next=NULL;r=q;p=p->next;}}/*将两个一元多项式相加*/void PolyAdd(Link &pc,Link pa,Link pb){Link p1,p2,p,pd;CopyLink(p1,pa);CopyLink(p2,pb);pc=new LNode;pc->next=NULL;p=pc;p1=p1->next;p2=p2->next;while(p1!=NULL&&p2!=NULL){if(p1->data.exp<p2->data.exp){p->next=p1;p=p->next;p1=p1->next;}else if(p1->data.exp>p2->data.exp){p->next=p2;p=p->next;p2=p2->next;}else{p1->data.coef=p1->data.coef+p2->data.coef;if(p1->data.coef!=0){p->next=p1;p=p->next;p1=p1->next;p2=p2->next;}else{pd=p1;p1=p1->next;p2=p2->next;delete pd;}}}if(p1!=NULL){p->next=p1;}if(p2!=NULL){p->next=p2;}}/*将两个多项式相减*/void PolySubstract(Link &pc,Link pa,Link pb) {Link p,pt;CopyLink(pt,pb);p=pt;while(p!=NULL){(p->data).coef=(-(p->data).coef);p=p->next;}PolyAdd(pc,pa,pt);DestroyLink(pt);}//清屏函数void Clear(){system("pause");system("cls");}/*将两个一元多项式相乘*/void PolyMultiply(Link &pc,Link pa,Link pb) {Link p1,p2,p,pd,newp,t;pc=new LNode;pc->next=NULL;p1=pa->next;p2=pb->next;while(p1!=NULL){pd=new LNode;pd->next=NULL;p=new LNode;p->next=NULL;t=p;while(p2){newp=new LNode;newp->next=NULL;newp->data.coef=p1->data.coef*p2->data.coef;newp->data.exp=p1->data.exp+p2->data.exp;t->next=newp;t=t->next;p2=p2->next;}PolyAdd(pd,pc,p);CopyLink(pc,pd);p1=p1->next;p2=pb->next;DestroyLink(p);DestroyLink(pd);}}//菜单函数void Menu(){cout<<""<<endl;cout<<endl;cout<<"\t=========================一元多项式的简单运算========================="<<endl;cout<<"\t\t\t\t\t\t\t\t "<<endl;cout<<"\t\t\t [1] 创建要运算的两个一元多项式\t\t "<<endl; cout<<"\t\t\t [2] 将两个一元多项式相加\t\t\t "<<endl; cout<<"\t\t\t [3] 将两个一元多项式相减\t\t\t "<<endl; cout<<"\t\t\t [4] 将两个一元多项式相乘\t\t\t "<<endl; cout<<"\t\t\t [5] 显示两个一元多项式\t\t\t "<<endl;cout<<"\t\t\t [6] 销毁所创建的二个多项式\t\t "<<endl; cout<<"\t\t\t [7] 退出\t\t\t\t\t "<<endl;cout<<"\t\t\t\t\t\t\t\t "<<endl;cout<<"\t=========================一元多项式的简单运算========================="<<endl;cout<<endl;cout<<"\t\t 请选择:";}//判断输入的整数是不是为到的数字int CompareIfNum(int i){if(i>0&&i<8)return 0;else return 1;}void main(){{system("color b");//system("pause");system("color a");//system("pause");}int n;Link L,La=NULL,Lb=NULL;//La,Lb分别为创建的两个多项式int choose;while(1){Menu(); //调用菜单函数cin>>choose;switch(choose){case 1:cout<<"请输入你要运算的第一个一元多项式的项数:"<<endl; cin>>n;if(CompareIfNum(n)==1){cout<<"您的输入有误，请重新输入……"<<endl;Clear();break;}CreateLink(La,n);cout<<"请输入你要运算的第二个一元多项式的项数:"<<endl; cin>>n;if(CompareIfNum(n)==1){cout<<"您的输入有误，请重新输入……"<<endl;Clear();break;}CreateLink(Lb,n);Clear();break;case 2:if(La==NULL||Lb==NULL){cout<<"您的多项式创建有误，请重新选择……"<<endl; Clear();break;}PolyAdd(L,La,Lb);cout<<""<<endl;cout<<"待相加的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相加后的结果为：";PrintList(L);cout<<""<<endl;Clear();DestroyLink(L);break;case 3:if(La==NULL||Lb==NULL){cout<<"您的多项式创建有误，请重新选择……"<<endl; Clear();break;}PolySubstract(L,La,Lb);cout<<"相减的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相减后的结果为：";PrintList(L);cout<<""<<endl;Clear();DestroyLink(L);break;case 4:if(La==NULL||Lb==NULL){cout<<"您的多项式创建有误，请重新选择……"<<endl; Clear();break;}PolyMultiply(L,La,Lb);cout<<"相乘的两个一元多项式为："<<endl;cout<<""<<endl;cout<<"A的多项式为：";PrintList(La);cout<<""<<endl;cout<<"B的多项式为：";PrintList(Lb);cout<<""<<endl;cout<<"相乘后的结果为：";PrintList(L);DestroyLink(L);cout<<""<<endl;Clear();break;case 5:if(La==NULL||Lb==NULL){cout<<"您的多项式创建有误，请重新选择……"<<endl; Clear();break;}cout<<"一元多项式A为："<<endl;PrintList(La);cout<<""<<endl;cout<<"一元多项式B为："<<endl;PrintList(Lb);cout<<""<<endl;Clear();break;case 6:if(La&&Lb){DestroyLink(La);DestroyLink(Lb);cout<<"多项式销毁成功！"<<endl;Clear();}else{cout<<"多项式不存在，请重新选择^^^"<<endl;Clear();}break;case 7:exit(0); //exit(0)强制终止程序，返回状态码表示正常结束default:cout<<"您的输入有误，请重新选择操作……"<<endl;Clear();break;}}}。

数据结构课程设计报告课题: 一元多项式姓名：XX学号：************专业班级：XXXX指导教师：XXXX设计时间：2015年12月30日星期三评阅意见：评定成绩：指导老师签名：年月日目录一、任务目标 (3)二、概要设计 (4)三、详细设计 (6)四、调试分析 (8)五、源程序代码 (8)六、程序运行效果图与说明 (15)七、本次实验小结 (16)八、参考文献 (16)一丶任务目标分析(1) a.能够按照指数降序排列建立并输出多项式b.能够完成两个多项式的相加，相减，并将结果输入要求：程序所能达到的功能：a.实现一元多项式的输入；b.实现一元多项式的输出；c.计算两个一元多项式的和并输出结果；d.计算两个一元多项式的差并输出结果；除任务要求外新增乘法：计算两个一元多项式的乘积并输出结果（2）输入的形式和输入值的范围：输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。

输入形式：2 3-1 23 01 20 0输入值的范围：系数为int型，指数为float型（3）输出的形式：第一行输出多项式1；第二行输出多项式2；第三行输出多项式1与多项式2相加的结果多项式；第四行输出多项式1与多项式2相减的结果多项式；第五行输出多项式1与多项式2相乘的结果多项式二、概要设计程序实现a. 功能：将要进行运算的二项式输入输出；b. 数据流入：要输入的二项式的系数与指数；c. 数据流出：合并同类项后的二项式；d. 程序流程图：二项式输入流程图；e. 测试要点：输入的二项式是否正确，若输入错误则重新输入。

流程图：三、详细设计（1）：存储结构一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。

链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。

创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。

数据结构课程设计报告一元多项式加减乘除精多项式想加减与乘与升降序学院计算机科学与技术专业信息安全学号 12070学生姓名陶宝中辅导教师姓名12月 22 日一、设计目的与内容了解数据结构的与算法的设计方法，独立分析和设计一元多项式加减与乘除的程序编码，经过程序编写掌握软件开发过程的问题分析，系统设计，程序编码，测试等基本方法和技能，提高综合运用所学理论知识和方法独立分析和解决问题的能力，经过这次实践将实验问题中的所涉及的对象在计算机中表示出来并对她们进行处理，掌握线除。

任务与分析本课题主要的目的是分别采用顺序和动态存储结构实现一元多项式的加法、减法和乘法。

并将操作结果分别按升序和降序输出程序的主要功能一元多项式创立建立一元多项式的顺序表和链式表，按程序提示输入每个项数据结束创立。

借助元素在存储器中的相对位置来表示数据元素之间的关系，顺序表中第i个位置表示一元多项式的第i项的系数为第i个位置存放的内容，指数为i-1。

创立一个一元多项式顺序表，对一元多项式的运算中会出现的各种情况进行分析，实现一元多项式的相加、相减、相乘操作。

用链表来表示只存储多项式中系数非零的项。

链表中的每一个结点存放多项式的一个term项结构和指向下一个节点的指针域，term又包括系数和指数两个域分别存放该项的系数、。

创立一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减、相乘操作。

一元多项式的加法对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到和多项式中去。

一元多项式的减法对于两个一元多项式中所有指数相同的项，对应系数相减，若其差不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，将其按减法规则复抄到差多项式中去。

一元多项式的乘法将乘法运算分解为一系列的加法运算利用两个一元多项式相加的算法实现。

一元多项式相加问题实验报告本实验的目的是进一步熟练掌握应用链表处理实际问题的能力。

一、问题描述通过键盘输入两个形如Po+P₁X¹+P₂X²+…+PX的多项式，经过程序运算后在屏幕上输出它们的相加和。

二、数据结构设计分析任意一元多项式的描述方法可知，一个一元多项式的每一个子项都由“系数-指数”两部份组成，因此可将其抽象为包含系数coef、指数 exp、指针域next 构成的链式线性表。

对多项式中系数为0的子项可以不记录它的指数值，将两个多项式分别存放在两个线性表中，然后经过相加后将所得多项式存放在一个新的线性表中，但是不用再开辟新的存储空间，只依靠结点的挪移来构成新的线性表，期间可以将某些不需要的空间回收。

基于这样的分析，可以采用不带头结点的单链表来表示一个一元多项式。

具体数据类型定义为：struct nodefloat coef;//系数域int exp; //指数域struct node *next;};三、功能函数设计1、输入并建立多项式的功能模块具体函数为node *in f un()此函数的处理较为全面，要求用户按照指数递增的顺序和一定的输入格式输入各个系数不为0的子项，输入一个子项建立一个相关结点，当遇到输入结束标志时住手输入。

关键步骤具体如下：(1)控制用户按照指数递增的顺序输入r=a;while(r!=q->next)if(y<=r->exp)cout<<"请按照指数递增顺序输入，请重新输入";cin>>x>>y;break;r=r->next;从头开始遍历，若遇到目前输入的指数不是最大时，就跳出循环，让用户重新输入。

(2)当输入的系数为零时，不为其分配存储空间存储while(x==0){cin>>x>>y;continue;}即若系数为0,再也不进行动态分配并新建结点，而是重新提取用户输入的下一个子项的系数和指数，利用continue 进入下一次循环。

问题描述：设Pn (x)和Qm(x)分别两个一元多项式。

试编写程序实现一元多项式的加法运算。

一、需求分析：1、本程序需要基于线性表的基本操作来实现一元多项式的加法，也可以用数组实现。

2、两个多项式都有键盘输入相应的系数和指数。

3、//第一个多项式为9x15+ 7x8+5x3+3x输入4 //表示第一个多项式的项数9， 15（回车） //表示9x157， 8 （回车）5， 3 （回车）3， 1 （回车）输出9x^15+ 7x^8+5x^3+3x^1//第二个多项式为 -7x8+6x3+2输入3 //表示第二个多项式的项数6， 3（回车） //表示9x15-7， 8（回车）2， 0 （回车）输出-7x^8+ 6x^3+2x^0求和结果9x^15+11x^3+3x^1+ 2x^0二、概要设计：抽象数据类型为实现上述程序的功能，应以整数存储用户的输入，以及计算的结果。

实现多项式的运算，利用数组的方式需开辟一个二维数组，利用链表的方式须创造两个链表。

算法的基本思想数组实现：定义一个结构体数组,p存储系数,q存储指数。

分别输出两次输入的多项式。

将两次输入的多项式的指数按从大到小的顺序进行排列，同时相应的系数要进行交换。

输出时如果进行判断。

如果当前该项与下一项的的系数相同，将两项系数相加后输出，并跳过下一项。

如果不相等，直接输出。

输出时需注意的问题：当系数为0时，该项不输出当系数为负数时，不要再在前面输出+。

程序的流程程序由三个模块组成：输入模块：完成两个多项式的输入。

处理模块：将多项式按其指数大小进行排列。

输出模块：输出合并后的多项式。

三、详细设计算法的具体步骤：数组方法：struct code{int p,q;}a[1000],b[1000];//结构体数组，可以用二维数组代//替for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(a[j].q>a[i].q) {temp=a[j].q;//指数排序a[j].q=a[i].q;a[i].q=temp;temp=a[j].p;//系数跟着变化a[j].p=a[i].p;a[i].p=temp;}}//对输入的指数进行排序，相应的系数跟着变化cout<<a[0].p<<"x^"<<a[0].q; //先输出第一项if(a[i].p>0)else if(a[i].p<0)cout<<a[i].p<<"x^"<<a[i].q;cout<<'+'<<a[i].p<<"x^"<<a[i].q;//完成运算符和其他项的输//出,然后类似于上面，对第二个多项式进行相应的操作。

简单介绍：本次作业力在学会链表表示线性表的插入、删除、查找等基本操作设计与实现，学习利用链表提供的接口去求解实际问题，同时熟悉链表的的存储方法。

再基于线性链表的基础设计完成多项式的相加运算程序。

一、实验目的和要求完成多项式的相加、相乘运算。

（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法二、实验内容和原理1.实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式；（2）输出多项式；（3）多项式的相加运算。

利用单链表实现。

2.实验原理使用单链表实现一元多项式的存储，并实现两个一元多项式的加法运算。

三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统（2）VC6.0四、算法描述及实验步骤1、描述：加法：输入建立一元多项式,进行简单加法运算,输出结果；通过建立单链表A和B分别存放多项式的a和b的各项系数及指数；并且利用A使得不产生新的节点而在A中存放数据运算结果；该过程通过定义指针变量p和q使它们分别指向两个多项式的第一个节点，之后依次比较它们所指向的项的指数，即一种情况指数相等时系数相加且和不为零，修改当前p所指项的系数（和），同时删除q所指项，若和为零则同时删除p和q各自所指；情况二，p当前项指数大于q当前项，将q所指插入p所指之前作为结果项之一；情况三，p当前项指数小于q当前项，p所指作为多项式和的一项，移动p指向下一项，进行比较，在移动p，q至其中以个链空，把另一个链余下节点插在p所指之后；乘法：定义指针p,q指向所操作节点，通过A链表的每一项与B链表各项相乘，指数相加，系数相乘，将值赋给新节点各自域，构成一新的链表，最后返回头结点。

可这样有一个问题，即新生成的链表，即最终结果混乱，没有对数据进行过滤，相同指数项应在执行加法运算，所以可以这样实现，通过A链表的每一项与B链表各项相乘的新生成节点单独构成一链表，并将第一个链表加入另一新链表，循环此操作将后生成的链表加之先前的链表，即可实现排序问题。

南昌航空大学实验报告课程名称：数据结构实验名称：实验二线性表的链式存储结构班级：080611 学生姓名：学号：08指导教师评定：签名:题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。

一、需求分析1.用户可以根据自己的需求分别输入两个一元多项式，并且能够实现输入的一元多项式的显示。

2.能够完成两个一元多项式的相加功能，而且还能显示相加后的逆置的一元多项式。

3.程序执行的命令包括：（1）构造链表A （2）构造链表B （3）两个链表的相加（4）求链表的长度（5）打印（显示）已有的链表（6）将已相加的链表进行逆序排列二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT Polynomial {数据对象：D={a i:|a i∈TermSet,i=1…n,n≥0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={<a i-1,a i>|a i-1,a i∈D,且a i-1中的指数值< a i中的指数值i=2,…n≥0}基本操作:initlink(& L)操作结果：构造一个空的链表L。

Creatlink(&L,n)操作结果：输入n项的系数和指数，建立一个非空的一元多项式L。

LinkLength(L)初始条件：链表L已经存在。

操作结果：返回一元多项式L中的项数。

Displaylink（L）初始条件：链表L已经存在。

操作结果：打印输出一元多项式L。

Addpolyn(A,B,&C)初始条件：一元多项式A和B已存在。

操作结果：完成多项式相加运算，即：C=A+B，并且带回C。

subtracypolyn(&La,&Lb,)初始条件：一元多项式La和Lb已存在。

操作结果：完成多项式的相减运算La=La+Lb，并且销毁多项式Lb。

一元多项式一、需求分析实现实系数一元多项式的创建，打印以及两个一元多项式的加、减、乘运算。

（1）程序所能达到的功能：a. 实现一元多项式的输入；b. 实现一元多项式的输出；c. 计算两个一元多项式的和并输出结果；d. 计算两个一元多项式的差并输出结果；e. 计算两个一元多项式的积并输出结果。

（2）输入的形式和输入值的范围：输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。

输入形式：2 3-1 23 01 20 0输入值的范围：系数为int型，指数为float型。

（3）输出的形式：要求：第一行输出多项式1；第二行输出多项式2；第三行输出多项式1与多项式2相加的结果多项式；第四行输出多项式1与多项式2相减的结果多项式；第五行输出多项式1与多项式2相乘的结果多项式注：多项式的每一项形如：2.0x^3,注意指数应保留一位小数；多项式按照升幂次序排列；系数为1的非零次项应略去系数，系数为0的项不能出现在结果中；指数为0的项应只输出系数；多项式的第一项系数符号为正时，不要输出“+”，其他项要输出“+”，“-”符号。

-3.0x^-1-6.0x-2.0x^2-9.0x^3-4.0x^4-6.0x^6二、概要设计（1）：程序实现a. 功能：将要进行运算的二项式输入输出；b. 数据流入：要输入的二项式的系数与指数；c. 数据流出：合并同类项后的二项式；d. 程序流程图：二项式输入流程图；e. 测试要点：输入的二项式是否正确，若输入错误则重新输入。

（2）：数据类型ADT Polynomial{数据对象：D={ai| ai ∈TermSet,i=1,2,…,m,m≥0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1={< ai-1,ai >| ai-1 , ai ∈D,且ai-1 中的指数值＜ai 中的指数值，i=2,…,n}基本操作：sort(Polyn & h); //对多项式进行排序print(Polyn h); //输出多项式delZeroCoef(Polyn & h); //判断系数为零的情况merge(Polyn & h); //合并指数相同的项createList(); //创建多项式addPoly(Polyn h1,Polyn h2); //多项式相加subPoly(Polyn h1,Polyn h2); //多项式相减multPoly(Polyn h1,Polyn h2); //多项式相乘} ADT Polynomial三、详细设计（1）：存储结构一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。

实验报告一元多项式实验报告：一元多项式引言：一元多项式是数学中的重要概念，它在代数学、数论、几何学等领域都有广泛的应用。

本实验旨在通过实际计算和推导，深入探讨一元多项式的特性和运算规则。

一、一元多项式的定义和表示一元多项式是指只含有一个变量的多项式。

一元多项式的一般形式为：P(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0，其中 a_n, a_{n-1}, ..., a_1, a_0 是常数系数，x 是变量。

一元多项式可以用系数和指数的形式表示，如 P(x) = 2x^3 + 3x^2 - 5x + 1。

二、一元多项式的运算规则1. 加法和减法：一元多项式的加法和减法运算与普通数的加法和减法类似，只需将相同次数的项合并即可。

例如，P(x) = 2x^3 + 3x^2 - 5x + 1 和 Q(x) = x^3 - 4x^2 + 2x + 3 的和为 R(x) = 3x^3 - x^2 - 3x + 4。

2. 乘法：一元多项式的乘法运算需要将每一项的系数相乘，并将指数相加。

例如，P(x) = 2x^3 + 3x^2 - 5x + 1 和 Q(x) = x^2 - 2x + 3 的乘积为 R(x) = 2x^5 - x^4 + 5x^3 - 11x^2 + 4x + 3。

3. 除法：一元多项式的除法运算可以通过长除法进行。

将除式的最高次项与被除式的最高次项相除，得到商的最高次项，并将商乘以除式后与被除式相减，得到新的被除式。

重复这个过程，直到被除式的次数小于除式的次数为止。

例如，将 P(x) = 2x^3 + 3x^2 - 5x + 1 除以 Q(x) = x^2 - 2x + 1，得到商 S(x) = 2x+ 5 和余数 R(x) = -3x + 6。

三、一元多项式的因式分解一元多项式的因式分解是将多项式表示为若干个不可再分解的因式的乘积。

常见的因式分解方法有提公因式法、配方法和求根法等。

一元多项式加法一、实验目的通过实现多项式加法，对链表有更深入的了解二、实验内容问题描述：设计一个一元稀疏多项式简单的加法计算器实现要求：一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项式：1785937)(x x x x A +++=；879228)(x x x x B -+=（2）输出多项式（3）多项式A 和B 相加，建立多项式C ＝A ＋B ，并输出相加的结果多项式C（4）选作：多项式A 和B 相减，建立多项式C ＝A －B ，并输出相减的结果多项式D 方法说明：（1）多项式的输入与存储用带表头结点的单链表存储多项式，链表中的每个节点分别存储多项式各项的系数和指数，即每从键盘输入多项式的一对数（系数，指数），可对应建立链表的一个结点。

每个节点的结构为：建立两个链表，其中pa 和pb 分别为它们的头指针：pb结果链表Pa(或者是Pc)Pc（2）多项式数据类型的定义struct tagNode{float coef;int exp;struct tagNode *next;typedef struct tagNode Node;typedef struct tagNode* pNode;（3）主要算法①创建两个链表，分别存放多项式1和多项式2，这两个链表中的节点是按指数降序或者升序排列的②多项式相加，下面给出多项式相加的部分实现/*下面的函数实现两个多项式的相加，要相加的链表分别由pa和pb指向（其中，pa，pb都是分配了空间的头结点）。

相加的结果直接由pa指向的链表保存，即是在pa链表中添加或删除（当系数因为相加为0的情况下）一些结点，构成结果。

相加的链表中指数按从小到大的顺序排列好的，是升序链表。

*/void add_poly(Node *pa,Node *pb){Node *p=pa->pNext;//链表1，将来的结果也放在此Node *q=pb->pNext;//链表2Node *pre=pa;Node *u;//临时用float x;while (p!=NULL && q!=NULL)//当两个链表都不为空{if (p->exp<q->exp)//比较链表1跟链表2当前节点的指数大小，链表1也是存放结果的地方{pre=p;p=p->pNext;//p指向要比较的下一个结点。

数据结构上机实习报告实验题目：实现一元多项式抽象数据类型班级：姓名：学号：指导老师：完成日期：1、需求分析1.1问题描述和规格说明已知一元n次多项式：设计程序实现一元n次多项式的抽象数据类型，模拟一元n次多项式的操作行为。

包括：数据元素：a i，存储结构，逻辑操作：1、构造一个空的多项式2、多项式插入新的一项3、多项式合并同类项4、多项式的加法P n(x)+Q n(x)=R t(x)5、多项式的乘法P n(x)*Q n(x)=R t(x)6、打印多项式7、计算多项式的值1.2功能需求1)首先构造两三个多项式供用户使用；2)用户可以进行添加多项式或是添加多项式中的项；3)或是修改其中的项，或是对多项式进行删除，或仅仅删除其中的某项；4)或是查看当前的某项多项式5) 用户赋予多项式变量x值后可以计算多项式的值6)可以计算两个或是多个多项式的和；7)可以计算两个以上多项式的乘积8)可以对多项式中的同类项进行合并2、设计(目标：有效组织与处理数据)2.1抽象数据类型:因为每个多项式有n个项，每个项包含不同的系数和指数，多项式的系数a i抽象为整数，变量x也是整数，x的次幂n也是整数，故多项式的每一项抽象为一个Nape类型的节点，包括：a i、x、n数据元素，最后整个一元n次多项式抽象为Polynomial数据类型。

详细设计如下：Nope类型设计为：class Nope{friend class Polynomial; //设置Polynomial为Nope的友元类，方便Polynomial类访问Nope的私有数据成员private:int m_factor; //项系数int m_times; //次幂public:Nope(int factor=0,int times=0);//构造函数~Nope();int GetFoctor()const; //获取项系数int GetTimes()const; //获取次幂void SetFactor(int factor); //设置项系数void SetTimes(int times); //设置次幂Nope & operator=(const Nope& item); //赋值=int operator<=(const Nope& item); //比较<=//比较次幂的大小friend ostream &operator<<(ostream& out, const Nope&item); //输出<<Nope(const Nope& item); //复制构造&};Polynoomial数据类型设计为：class Polynomial{private:int m_x; //多项式中的变量xint m_size; //多项式的项数LinListWithRear< Nope > m_list; //存储多项式的带尾指针的单向链表public:Polynomial(int size = 0,int factor= 1);//可以构造系数为factor，个数为size 的多项式，次幂依次增长~Polynomial();Polynomial(const Polynomial&poly);int GetM_size()const; //获取多项式的项数int GetM_x()const;int GetM_factor(const int& index)const; //获取第index项的系数//从第1项开始（而不是第0项）int GetM_times(const int& index)const; //获取第index项的次幂inline double GetM_Number(const int& index)const; //获取第index项的值,因为计算多项式的值时频繁调用，所以设计为内联函数int Getfactor(const int& times)const; //获取次幂为times的项的系数 //失败或没有，返回0int GetIndex(const int& times)const; //获取次幂为times 的项的下标//从1开始double GetNumber(const int& times)const; //获取次幂为times的项的值 //失败或没有返回0double GetTotalNumber()const; //获取整个多项式的值int SetM_factor(const int& index,const int& factor); //设置第index项的系数//从第1项开始（而不是第0项）int Setfactor(const int& times,const int& factor); //设置次幂为times 的项的系数//失败返回0int SetM_times(const int& index, const int& times); //设置次幂为times 的项的系数//失败返回0int SetM_x(const int & x); //给未知数m_x赋值bool DeleteIndex(const int & index); //删除第index项bool DeleteTimes(const int & times); //删除次幂为times的项bool DeleteFactor(const int& factor); //删除所有系数为factor的项inline int InsertEnd(const int& factor, const int& times); //从尾部插入新项，系数为factor，次数为times//失败返回0inline void InsertEnd(const Nope& item);Polynomial& operator=(const Polynomial&Poly); //赋值void Combine(); //合并同类项且按次幂排序void Print()const; //打印多项式void OrderPolynomial(); //按次幂排序多项式int OrderInsert(const int& factor, const int& times); //有序插入新项，系数为factor，次数为times//失败返回0Polynomial operator+(const Polynomial&polyb); //多项式的加法Polynomial operator*(const Polynomial&polyb); //多项式的乘法friend ostream &operator<<(ostream& out, const Polynomial& item);//输出<<};2.2存储结构设计：1)存储结构的确定数据结构的目的是有效组织和处理数据。

数据结构课程设计报告题目：一元多项式相加学号：姓名：指导老师：时间： 2011年10月18日星期二程序建立的过程及步骤：1首先建立一个定义多项式的结构体duoxiangshi，其中包括一个指数（int型），一个系数（float型），还有一个指向下一项的指针，具体编译代码如下：typedef struct duoxiangshi//定义一个多项式{float coef;//多项式系数int exp;//多项式指数struct duoxiangshi *next;};2在定义一个函数（1），用来指导用户输入程序运行时所需要的必须得数据，两个一元多项式的项数、系数、指数。

具体的代码如下：void creatDuoX(Polynomial &Px,int n)//定义一个多项式函数{initDuoX(Px);duoxiangshi *p,*q;p=Px;for(int i=1;i<=n;i++){q=new duoxiangshi;cout<<"第"<<i<<"项的系数：";cin>>q->coef;//输入系数cout<<"第"<<i<<"项的指数：";cin>>q->exp;//输入指数q->next=NULL;p->next=q;p=q;}}3定义一个计算合并后的多项式的项数的函数（2），此函数的主要作用是用来最后输出合并后的多项式的时候起到作用。

具体代码如下：int lengthDuoX(Polynomial &Px)//计算多项式项数的函数，返回值是这个合并后的多项式的项数{duoxiangshi *p;int count;//定义一个变量，用来计算多项式的长度p=Px->next;count=0;while(p!=NULL){p=p->next;count++;//自加最后得出总项数并返回}return count;}4定义一个输出合并后的多项式的函数（3），主要作用为主函数调用后可以输出一元多项式，具体代码如下：void outputDuoX(Polynomial &Px)//输出合并后的多项式{ duoxiangshi *p;p=Px->next;int i;for(i=0;i<lengthDuoX(Px);i++)//调用上一个计算项数的函数，逐项的输出合并后的项{cout<<p->coef<<"*X^ "<<p->exp<<" +";p=p->next;}cout<<"0"<<endl;}5, 最重要的核心部分，程序的逻辑中心，让两个多项式相加，其中要考虑的情况如下一：两个多项式A、B 都为0二：其中一个多项式A 为0，B不为0三：其中一个多项式B为0，A不为0四：A与B 都不为0而在程序中我将二与三这两种情况，通过IF语句将其嵌到四的情况中，这样可以节省代码的复杂度。

编号：江西理工大学数据结构课程设计报告班级：网络112班学号：09姓名：李秀光时间：2012年12月31日~2012年1月11日指导教师：涂燕琼井福荣2013年01月数制转换一、需求分析1、输入的形式和输入值的范围n和f的输入形式均为int型，n和f的输入范围均为1~327672、输出的形式十六进制10-15输出A-E，超过十六进制时按16以上数值按原值输出。

3、程序所能达到的功能把十进制数n转换成任意进制数f（对于输入的任意一个非负十进制整数，输出与其等值的任意进制数（如二，四，八，十六进制）。

4、测试数据n（十进制）f（进制）输出值22 2 10110354 4 112025376 8 1240032767 16 7FFF1、抽象数据类型的定义ADT Stack｛基本操作：InitStack(&S)操作结果：构造一个空栈s。

Push(&S,e)初始条件：栈s已存在。

操作结果：插入元素e为新的栈顶元素。

Pop(SqStack &S)初始操作：栈s已存在且非空。

操作结果：删除s的栈顶元素，并用e返回其值。

StackEmpty(SqStack S)初始条件：栈s已存在。

操作结果：若栈为空则返回1，否则返回0。

｝ADT Stack2、主程序的流程以及各程序模块之间的层次调用关系见（三、详细设计3、流程图）↓1、数据类型// = = = = = ADT Stack 的表示与实现= = = = = //// - - - - - 数制转换- - - - -//#define STACK_INIT_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量typedef struct {int *base;int *top;int stacksize;}SqStack;// - - - - - 基本操作的函数原型说明- - - - - //void InitStack(SqStack &S)//构造一个空栈svoid Push(SqStack &S,int e)//插入e为新的栈顶元素int Pop(SqStack &S)//删除s的栈顶元素，并用e返回其值int StackEmpty(SqStack S)//若栈为空则返回1，否则返回0void conversion(int n,int f)//对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数2、伪码算法// - - - - - 基本操作的算法描述 - - - - - //void InitStack(SqStack &S){//构造一个空栈sS.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));if(!S.base) exit(-2);S.top = S.base;S.stacksize = STACK_INIT_SIZE;}// InitStackvoid Push(SqStack &S,int e){//插入元素e为新的栈顶元素if(S.top- S.base >= S.stacksize){S.base = (int *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(int));if(!S.base) exit(-2);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;}// Pushint Pop(SqStack &S){//删除s的栈顶元素，并用e返回其值int e;if(S.top == S.base) return 0;e = *--S.top;return e;}//Popint StackEmpty(SqStack S){//若栈为空则返回1，否则返回0if(S.top == S.base) return 1;else return 0;}// StackEmpty//对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数void conversion(int n,int f){InitStack(S);while(n){Push(S,n%f);n = n/f;}while(!StackEmpty(S)){Pop(S,e)printf("%d",e);}}// conversion3、流程图(1)调试过程中遇到的问题和解决方法在调试过程中主要遇到一些符号打错或输出、输出和函数之类的名称打错或漏打，根据第一行提示的错误然后进行修改，修改之后再运行调试，如此循环，直到彻底正常运行，后面就是优化见面的问题了。

中南大学物理学院数据结构实验报告- - - -一元多项式相加及其运用专业班级：电信0903时间：2010年10月18日数据结构实验报告----一元多项式相加及其运用【问题描述】设计一个一元稀疏多项式简单计算器【基本要求】一元稀疏多项式简单计算器的功能是：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………c n,e n,其中n是多项式的项数，c i和e i分别是第i项的系数和指数，序列按指数降序排列；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。

【运用拓展】（1）计算多项式在x处的值；（2）多项式a和b相乘，建立乘积多项式ab；（3）计算器的仿真友好界面。

【设计思路分析】（1）解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表。

（2）运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（3）设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：①若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

②若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。

③若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

【测试数据】多项式a：6x+3x^5-7.1x^11多项式b: 2-5x^5+11x^9若计算a+b则有:(6x+3x^5-7.1x^11)+(2-5x^5+11x^9)=(-7.1x^11+11x^9-2x^5+6x+2)等。

【操作界面显示】1：建立多项式的操作：2：输出多项式及计算x的值3：进行运算操作：4：结束程序：【程序代码】#include<stdio.h> //调用输入输出函数#include<stdlib.h>typedef struct Polynomial //定义一个Polyn结构体{ float coef; int exp; //系数指定为浮点型，指数指定为整型struct Polynomial *next;}*Polyn,Polynomial;void Insert(Polyn p,Polyn h){ //查找位置插入新链节if(p->coef==0) free(p); //p系数为0的话释放结点else{ //否则查找插入位置Polyn q1,q2;q1=h; q2=h->next;while(q2&& p->exp < q2->exp) //指数较大则插前面{ q1=q2; q2=q2->next; }if(q2&& p->exp == q2->exp) //将指数相同相合并{ q2->coef += p->coef;free(p);if(!q2->coef) //系数为0的话释放结点{q1->next=q2->next;free(q2);}}else { p->next=q2; q1->next=p;} //指数为新时将结点插入}//第一个else} //void InsertPolyn CreatePolyn(Polyn head,int m){ //建立一个头指针为head、项数为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->exp);Insert(p,head); //调用Insert函数插入结点}return head;}void PrintPolyn(Polyn P) //输出多项式{ Polyn q=P->next;int flag=1; //项数计数器if(!q){ //若多项式为空，输出0putchar('0');printf("\n");return;} //void ifwhile(q){if(q->coef>0&& flag!=1) putchar('+'); //系数大于0且不是第一项，显示"+"连接if(q->coef!=1&&q->coef!=-1) //系数非1或-1时输出{ printf("%g",q->coef);if(q->exp==1) putchar('X'); //指数为1时，直接输出"X"else if(q->exp) printf("X^%d",q->exp); //指数不为1时，输入"X^"格式}//while if ifelse { if(q->coef==1){ if(!q->exp) putchar('1');else if(q->exp==1) putchar('X');else printf("X^%d",q->exp);}//else ifif(q->coef==-1) //系数为"-1"时，前面加上负号，其他情况与"+1"类似{ if(!q->exp) printf("-1");else if(q->exp==1) printf("-X");else printf("-X^%d",q->exp);}//else if if}//elseq=q->next; flag++;}//whileprintf("\n");}//voidint compare(Polyn a,Polyn b) //两个多项式的判断{ if(a&&b) //若两个多项式都非空{ if(!b||a->exp>b->exp) return 1; //b多项式已空或指数较小，返回1 else if(!a||a->exp<b->exp) return -1; //a多项式已空或指数较小，返回-1else return 0; //a、b两多项式的指数相等，返回0 }//ifelse if(!a&&b) return -1; //a多项式已空，但b多项式非空else return 1; //b多项式已空，但a多项式非空}//comparePolyn 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)) //判断多项式a和b { case 1: { qc->coef=qa->coef; //输入a多项式qc->exp=qa->exp; qa=qa->next; break; }case 0: { qc->coef=qa->coef+qb->coef; //指数相等时系数相加qc->exp=qa->exp; qa=qa->next; qb=qb->next; break; } case -1: { qc->coef=qb->coef; //输入b多项式qc->exp=qb->exp; qb=qb->next; break; }}//switchif(qc->coef!=0) //当相加系数不为0，加入该结点{ qc->next=hc->next; hc->next=qc; hc=qc;}else free(qc); //当相加系数为0时，释放该结点}//whilereturn 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;} //whilepd=AddPolyn(pa,h);for(p=h->next;p;p=p->next) //恢复pb的系数p->coef*=-1;return pd;}//SubtractPolynPolyn 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->exp=qa->exp+qb->exp;Insert(pf,hf); //调用Insert函数以合并指数相同的项}//for for}//forreturn hf;}//MultiplyPolynfloat V aluePolyn(Polyn head,int x){ //输入x值，计算并返回多项式的值Polyn p; int i,t; float sum=0;for(p=head->next;p;p=p->next){ t=1; for(i=p->exp;i!=0;){ if(i<0){t/=x;i++;} //指数小于0，进行除法else{t*=x;i--;} //指数大于0，进行乘法}//for forsum+=p->coef*t; //计算求和} //forreturn sum;}//V aluePolynvoid DestroyPolyn(Polyn p) //销毁多项式p{Polyn q1,q2;q1=p->next; q2=q1->next;while(q1->next) //删除q1的元素直至q1为空{ free(q1); q1=q2; q2=q2->next; }}//DestroyPolynvoid main(){ int m,n,a,x;char flag;Polyn pa=0,pb=0,pc;printf(" --------------------------------------------------\n");printf(" 欢迎使用一元多项式及其运用操作程序\n");printf(" --------------------------------------------------\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:输出多项式a B:输出多项式b *\n");printf(" * *\n");printf(" * C:同时输出多项式a和b *\n");printf(" * *\n");printf(" * D:代入x的值计算a E:代入x的值计算b *\n");printf(" * *\n");printf(" * F:代人x的值同时计算a和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="); //输出多项式aPrintPolyn(pa); //调用输出函数显示break; //跳出}case'B':case'b': { printf("\n 多项式b="); //输出多项式bPrintPolyn(pb);break;}case'C':case'c': { printf("\n 多项式a="); //输出多项式a和bPrintPolyn(pa);printf("\n 多项式b=");PrintPolyn(pb);break;}case'D':case'd': { printf("输入x的值：x="); //输入x值后计算ascanf("%d",&x);printf("\n x=%d时，a=%.3f\n",x,V aluePolyn(pa,x));break;}case'E':case'e': { printf("输入x的值：x="); //输入x值后计算bscanf("%d",&x);printf("\n x=%d时，b=%.3f\n",x,V aluePolyn(pb,x));break;}case'F':case'f': { printf("输入x的值：x="); //输入x值后计算a和bscanf("%d",&x);printf("\n x=%d时，a=%.3f\n",x,V aluePolyn(pa,x));printf("\n x=%d时，b=%.3f\n",x,V aluePolyn(pb,x));break;}case'G':case'g': { pc=AddPolyn(pa,pb); //输出a+b，用新多项式显示printf("\n a+b=");PrintPolyn(pc);break;}case'H':case'h': { pc=SubtractPolyn(pa,pb); //输出a-b，用新多项式显示printf("\n a-b=");PrintPolyn(pc);break;}case'I':case'i': { pc=MultiplyPolyn(pa,pb); //输出a*b，用新多项式显示printf("\n a*b=");PrintPolyn(pc);break;}case'J':case'j': { printf("\n 感谢使用此程序！\n"); //退出该程序DestroyPolyn(pa); //删除多项式aDestroyPolyn(pb); //删除多项式ba=0; //暂停显示界面，用户选择关闭break;}default:printf("\n 您的选择错误，请重新选择!\n");}//swich}//while}//main。

数据结构实验报告实验名称：实验一一元多项式学生姓名：叶远锋班级：2010211111班内序号：18学号：10210328日期：2011年11月9日1．实验要求实验目的●熟悉C++语言的基本编程方法，掌握继承编译环境的调试方法；●学习指针、模板类、异常处理的使用；●掌握线性表的操作实现方法；●培养使用线性表解决实际问题的能力。

实验内容利用线性表实现一个一元多项式Polynomial：f（x）=a0+a1X+a2X^2+……+anX^n具体要求如下：①能够实现一元多项式的输入和输出；②能够进行一元多项式相加；③能够进行一元多项式相减；④能够计算一元多项式在x处的值；⑤能够计算一元多项式的导数（选作）；⑥能够进行一元多项式相乘（选作）；⑦编写main（）函数测试算法的正确性。

2. 程序分析2.1 存储结构存储结构：顺序表a[0]a[1]a[2]……a[n].2 关键算法分析1、关键算法：加法、减法、求导、乘法、求值✧加法时间复杂度O（n）输出参数：返回一个新一元多项式c输入参数：两个一元多项式PolyList类对象的引用a、b[1] 从第一项开始，比较a和b 的指数，直到其中一个多项式比较到最后一项[1.1] 如果a对应项的指数小于b对应项的指数，把a的对应项复制给C的对应项，再把a的下一项和b的当前项比较[1.2] 如果a对应项的指数大于b对应项的指数，把b的对应项复制给C的对应项，再把b的下一项和a的当前项比较[1.3] 如果a的对应项指数等于b的对应项指数，则c的对应项的系数等于a的对应项系数和b的对应项系数相加，c的对应项的指数等于a或b的对应项指数，再把a的下一项和b的下一项比较[2] 如果a或b其中有一个没有比较完，就把没有比较的项都复制到c中[3] 返回c✧减法时间复杂度O（n）输出参数：返回一个新一元多项式c输入参数：两个一元多项式PolyList类对象的引用a、b[1] 将多项式b的每一项系数都乘以-1[2] 调用加法，把a+b的值赋给c[3] 返回c✧求导时间复杂度O（n）输出参数：返回一个新一元多项式a输入参数：无[1] 从第一项开始，直到最后一项，如果指数不等于零，则a的对应项系数等于现有项系数乘以现有项指数，a的对应项指数等于现有项指数减一[2] 返回a✧乘法时间复杂度O（mn）输出参数：返回一个新一元多项式 c输入参数：两个一元多项式PolyList类对象的引用a、b[1] 从a的第一项开始，直至最后一项，逐项和b相乘[2] 将每一次相乘得到的多项式相加，并把相加的结果赋给c[3] 返回c✧求值时间复杂度O（n）输出参数：返回一个float型数输入参数：输入一个float型数[1] 从第一项开始，直至最后一项，依次计算每一项的值[2] 将每次计算得到的结果相加，并把相加结果赋给value[3] 返回value3. 程序运行结果1、测试主函数流程：流程图如图所示2、测试条件1)输入项数应少于100项2)输入多项式项数是大于零的整数3)输入多项式时，要从低次项到高次项依次逐项输入，先输入系数，再输入指数4)按屏幕提示输入3、测试结论1)程序可以实现多项式的输入输出操作2)程序可以进行多项式的加减乘及求导和求值运算4. 总结1.调试时出现的问题及解决方法1)问题：main函数中，在定义term结构数组时使用整型n，m变量作为数组的长度遇到系统报错解决方法：为数组申请动态内存2)问题：main函数中，当输入多项式项数小于1时无法报错解决方法：在用户输入完毕后增加if判断语句来实现报错3)问题：用户无法循环输入多项式解决方法：在程序末尾增加按键判断语句，如果用户选择要重新输入多项式则返回程序开头重新执行，否则程序结束2.心得体会1）通过这次编程练习，我加深了对顺序表的理解与运用。