数据结构-实验一-一元多项式相加

数据结构实验报告实验名称：实验一—线性表实现一个多项式学生姓名：黄锦雨班级：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即可，将每项得到的结果插入到结果多项式的链表中。

一元多项式相加问题实验报告一元多项式相加问题一、问题描述通过键盘输入两个形如P 0 +P 1 X 1 +P 2 X 2 +…+P n X 的多项式，经过程序运后在屏幕上输出它们的相加和。

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

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

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

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

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

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

⑶初始化完成后将最后一个结点的指针域置为空，并返回该新建链表的首地址。

if(q!=NULL)q-next=NULL;return a; ⑷动态分配空间新建结点存储系数和指数的代码如下：p=new node;p-coef=x;p-exp=y;if(a==NULL) a=p;else q-next=p;q=p; 2、多项式显示功能函数由于系数有正有负，故采取如下处理：对于正数，输出时在前面加“+”，头指针除外；对于负数，直接将系数输出即可，即：p=a;while(p){if(p==a)coutp-coef"*x^"p-else if(p-coef0)coutp-coef"*x^"p-else if(p-coef0)cout"+"p-coef"*x^"p-p=p-next;} 输出的多项式的形式形如：P 1 X^1+P 2 X^2+…+P n X^n 3、多项式相加的功能函数函数为：node *plus_fun(node *a,node *b) 此函数根据在 1 中初始化的两个多项式进行相加运算，并存放在以c 为头指针的一个新链表中。

实验一：完成多项式的相加运算（验证性、4学时）一、实验目的完成多项式的相加、相乘运算。

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

利用单链表实现。

三、算法描述及实验步骤1描述1、创建两个单链表A、B，分别调用CreatePolyn（）；2、输出多项式，分别调用PrintPolyn（）；3、多项式相加运算AddPolyn（）。

2算法流程图4 65inputA-B inputA-B inputA-B end3代码(注释)#include<stdio.h>#include<malloc.h>#include<math.h>typedef struct Polynomial{float coef;//系数变量int exp;//指数变量struct Polynomial *next;//定义next指针}*Polyn,Polynomial; //Polyn为结点指针类型void Insert(Polyn p,Polyn h) //插入新的结点p{if(p->coef==0) free(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;}}}//Insertint f(float x)//判断输入是否为整形{float a;a=x-(long int)x;if(a==0&&x==fabs(x))return 1;elsereturn 0;}Polyn 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("please input NO.%d coef and exp:",i+1);scanf("%f %d",&p->coef,&p->exp);while(!f(p->coef)&&!f(p->exp)){printf("输入有错，请重新输入: ");scanf("%f %d",&p->coef,&p->exp);}Insert(p,head); //调用Insert函数插入结点}return head;}//CreatePolynvoid DestroyPolyn(Polyn p) //销毁多项式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) //若多项式为空，输出0{putchar('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->exp==1) putchar('X');else if(q->exp) printf("X^%d",q->exp);}else{if(q->coef==1){if(!q->exp) putchar('1');else if(q->exp==1) putchar('X');else printf("X^%d",q->exp);}if(q->coef==-1){if(!q->exp) printf("-1");else if(q->exp==1) printf("-X");else printf("-X^%d",q->exp);}}q=q->next;flag++;}//whileprintf("\n");}//PrintPolynint compare(Polyn a,Polyn b){if(a&&b){if(!b||a->exp>b->exp) return 1;else if(!a||a->exp<b->exp) return -1;else return 0;}else 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)) //功能选择{ case 1:{qc->coef=qa->coef;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;qc->exp=qb->exp;qb=qb->next;break;}}//switchif(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}else free(qc);//当相加系数为0时，释放该结点}//whilereturn headc;}//AddPolynPolyn 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;}//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函数以合并指数相同的项}}return hf;}//MultiplyPolynvoid DevicePolyn(Polyn pa,Polyn pb){//求解并建立多项式A/B，返回其头指针Polyn hf,pf,af,temp1,temp2,q;Polyn qa=pa->next;Polyn qb=pb->next;hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点,存储商hf->next=NULL;pf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点，存储余数pf->next=NULL;temp1=(Polyn)malloc(sizeof(struct Polynomial));temp1->next=NULL;temp2=(Polyn)malloc(sizeof(struct Polynomial));temp2->next=NULL;temp1=AddPolyn(temp1,pa);while(qa!=NULL&&qa->exp>=qb->exp){temp2->next=(Polyn)malloc(sizeof(struct Polynomial));temp2->next->coef=(qa->coef)/(qb->coef);temp2->next->exp=(qa->exp)-(qb->exp);Insert(temp2->next,hf);pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2));qa=pa->next;temp2->next=NULL;}pf=SubtractPolyn(temp1,MultiplyPolyn(hf,pb));pb=temp1;printf("the quotient is :");PrintPolyn(hf);printf("the remainder is :");PrintPolyn(pf);}//DevicePolynint main(){int m,n,flag=0;float x;Polyn pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf("please input A number:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多项式Aprintf("please input B number:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多项式B//输出菜单printf("**********************************************\n");printf("choise：\n\t1.Output A and B\n\t2.CreatePolyn A+B\n");printf("\t3.CreatePolyn A-B\n\t4.CreatePolyn A*B\n");printf("\t5.CreatePolynA/B\n\t6.Return\n**********************************************\n");for(;;flag=0){printf("choise");scanf("%d",&flag);if(flag==1){printf("多项式A：");PrintPolyn(pa);printf("多项式B：");PrintPolyn(pb);continue;}if(flag==2){pc=AddPolyn(pa,pb);printf("多项式A+B：");PrintPolyn(pc);DestroyPolyn(pc);continue;}if(flag==3){pd=SubtractPolyn(pa,pb);printf("多项式A-B：");PrintPolyn(pd);DestroyPolyn(pd);continue;}if(flag==4){pf=MultiplyPolyn(pa,pb);printf("多项式a*b：");PrintPolyn(pf);DestroyPolyn(pf);continue;}if(flag==5){DevicePolyn(pa,pb);continue;}if(flag==6) break;if(flag<1||flag>6) printf("Error\n");continue;}//forDestroyPolyn(pa);DestroyPolyn(pb);return 0;}一、调试过程一次调试二次调试二、实验结果测试数据（1）多项式A:3x^4+11x^3+21x^2多项式B:2x^5+11x^4+12x^3+7x实验结果（1）多项式A+B=2x^5+14x^4+23x^3+21x^2+7x多项式A-B=-2x^5-8^4-x^3+21x^2-7x多项式A*B=6x^9+55x^8+199x^7+363x^6+273x^5+77x^4+147x^3多项式A/B=0实验截图（1）测试数据（2）：多项式A:2x^3+5x^-3多项式B:9x^2+6x^-2+11x^-3实验结果（2）：多项式A+B=2x^3+9x^2+6x^-2+16x^-3多项式A-B=2x^3-9x^2-6x^(-2)=16x^(-3)多项式A*B=18x^5+12x+22+45x^(-1)+30x^(-5)+55x^(-6)多项式A/B=0.222222x实验截图（2）：测试数据（3）多项式A:-x^7+3x^5多项式B:x^7-4x6%+7x^3实验结果（3）多项式A+B=-x^5+7x^3多项式A-B=-2x^7+7x^5-7x^3多项式A*B=-x^14+7x^12-19x^10+21x^8多项式A/B=-1实验截图（3）：三、总结1.在熟悉VC6.0环境的同时，对单链表的存储格式有了深刻的理解；2.复习C++语法的同时，对刚学的线性表进行综合性理解和表达，与之前所学融合。

一元多项式相加问题一．问题描述设计算法实现一元多项式的简单运算。

二．数据结构设计分析任意一元多项式的描述方法可知，一个一元多项式的每一个子项都由“系数---指数”两部分组成，所以可以将它抽象成一个由“系数----指数对”构成的线性表。

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

具体数据类型定义为：typedef struct node{float cofe; //系数域int exp; //指数域struct node* next; //指针域指向下一个子项}*polynode,poly;Polynode head_a,head_b,head_c;这三个指针分别作为链表A，B和C的头指针。

三．功能设计1.输入并建立多项式的功能模块此模块要求按照“系数---指数对”的输入格式输入各个子项，输入一个子项，通过遍历链表比较指数的大小，将新结点插在合适的位置，使多项式的指数按递增的顺序存储。

当遇到输入结束标志是停止输入，而转去执行程序下面的部分。

具体函数构造为：polynode creat_polynode(){polynode A ,p,q,s; //建立这种类型的头指针，尾指针，遍历指针和动态指针float a;int b;A=new poly;A->next=NULL;q=A;p=A;cin>>a;cin>>b;while(a!=0||b!=0){s=new poly;s->cofe=a;s->exp=b;while(q->next){if(q->next->exp<b)q=q->next; //遍历链表，若指数大于原链表指数，指针后移一个else{s->next=q->next;q->next=s;break; //若不是，将结点插入指针后面}}if(q->next==NULL){s->next=p->next;p->next=s;p=s; //q遍历到链表尾仍未插入，将结点插入最后，改变尾指针使其指向新结点}q=A; //让q返回头指针处，以便下一次遍历链表cin>>a;cin>>b;}if(p!=NULL)p->next=NULL;return A;}2.多项式相加的功能模块此模块根据在1中建立的两个多项式进行相加运算，并存放在以C为头指针的一个新链表中。

中南大学《数据结构与算法》课程实验实验报告题目实验一线性表的操作学生姓名谭淇蔚学生学号 3901130721 专业班级软件工程1307班完成日期2014年3月31日星期一实验一线性表的操作（一元多项式相加）1. 需求分析我们使用计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。

而数据存储结构有两种：顺序存储结构和链式存储结构。

线性表是最常用且最简单的一种数据结构。

所以我们做的是实验一-----------线性表的操作。

实验的目的是掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算以及熟练运用掌握的线性表的操作，实现一元n次多项式的加法运算。

学习实现一元n次多项式的加法是符号多项式的操作，是表处理的典型用例，需要注意的是：顺序存储结构指的是用数组方法，使用数组方法实现时，在插入和删除的方面，数组不如链表灵活，方法复杂，删除其中一个需要将其后的数组元素改变位置，使其数组保持原有的顺序结构，在查找方面较链表简单，只需要知道其下标就可以知道。

链接存储结构指的是用链表方法,值得注意的是，删除和插入较为灵活，不需要变动大多数元素，但是查找过程相对于数组这种顺序存储结构来说较为复杂，耗时巨大。

我们要学习的是通过对两种方法基本操作的掌握来做到实现一元n次多项式的相加减。

我们程序的任务是：能进行简单的线性表操作（插入、删除、查找）以及线性表合并等运算。

能通过这些基本操作实现一元多项式相加。

明确规定：输入的形式：按照提示（比如：“请您输入第一个结构体数组的项数（不超过50项）：”、“请您输入第二个结构体数组的项数（不超过50项）：”、“请输入第n项的系数”、“请输入第n项的指数”等等），先输入多项式的项数，之后顺次输入每一项的系数与指数。

输入值的范围：项数没有要求，但不能过于巨大；系数取为float型数据，指数取为int 型数据，输出的形式：按照提示（比如：“您输入的第一个多项式为：”、“您输入的第二个多项式为：”等等），会输出原输入的多项式和经过排序和合并之后的降幂型多项式。

[计算机]一元多项式相加完整实验报告一元多项式的相加一实验内容根据所学的数据结构中线性结构(线性表)的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加二需求分析1掌握线性结构的逻辑特性和物理特性。

2建立一元多项式。

3将一元多项式输入，并存储在内存中，并按照指数降序排列输出多项式。

4能够完成两个多项式的加减运算，并输出结果。

三概要设计1 本程序所用到的抽象数据类型:typedef OrderedLinkList polynomial;// 用带表头结点的有序链表表示多项式结点的数据元素类型定义为:typedef struct { // 项的表示oat flcoef; // 系数int expn; // 指数 term, ElemType;Void AddPolyn(polynomail&Pa,polynomail&Pb)Position GetHead()Position NextPos(LinkList L,Link p)Elem GetCurElem(Link p)int cmp(term a term b)Status SetCurElem(Link&p, ElemType e)Status DelFirst(Link h, Link &q)Status ListEmpty(LinkList L)Status Append(LinkList&L, Link S)FreeNode()2 存储结构一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。

它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。

序数coef 指数exp 指针域next创建一元多项式链表，对运算中可能出现的各种情况进行分析，实现一元多项式的相加相减操作。

3 模块划分a) 主程序;2)初始化单链表;3)建立单链表; 4)相加多项式 4 主程序流程图开始申请结点空间输入多项式各项的系数X，指数Y输出已输出的多项式否是否输入正确合并同类项结束四详细设计根据一元多项式相加的运算规则:对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。

实验一一元多项式的表示与相加实验目的：1.复习并熟练掌握数据结构所使用的程序设计语言——C语言；2.学会单步跟踪、调试自己的程序；3.加深对线性表特别是链表知识的理解和掌握，并能够运用相关知识来解决相关的具体问题，如一元多项式相加等；程序流程：1.定义一元多项式链表结构体类型；2.输入多项式项数以分配存储空间；3.输入多项式每项的系数和指数，将其插入当前多项式链表。

同时判断是否有与当前节点指数相同的项，若存在，则将两项系数相加合并。

此外，若存在系数为0的项，将其存储空间释放；4.进行多项数加法时，新建一个存储结果的链表，分别将两多项式各项依次插入结果多项式即完成多项式相加运算；5.进行多项数加法时，将减项多项式各项系数化为相反数后进行加法操作，即完成多项式相减运算；6.对x赋值后，将x值代入多项式进行运算得到多项式的值；7.输出多项式。

注意：进行完一次运算以后，应该及时销毁无用多项式以释放空间以便再次应用。

算法及注释：1）定义一元多项式链表结构体类型typedef struct Lnode{float cof; //定义系数int exp; //定义指数struct Lnode *next; //定义指针变量指向下一个节点}Lnode ,*Linklist; //定义新的变量类型2）建立多项式存储线性链表头结点void makehead(Linklist &head){head=(Linklist)malloc(sizeof(Lnode)); //建立新的节点head->exp=-1;head->next=NULL; //指针赋空head->cof=1;}3）将输入的多项式信息存储于节点中void makelnode(Lnode *&p){p=(Lnode*)malloc(sizeof(Lnode)); //建立新的节点printf("Input the cof and exp\n");scanf("%fx%d",&p->cof,&p->exp); //输入多项式底数指数信息p->next=NULL; //指针赋空}4）清除系数为零的多项式节点void clear(Linklist la){Lnode *p,*q; //定义两个指向结构体的指针p=la;q=p->next;while (q){if (fabs(q->cof)<=0.000001) { //判断系数为零p->next=q->next; //指针指向相隔的下一个节点free(q); //销毁系数为零的节点q=p->next; //指针后移一位}else {p=p->next; //p q分别后移一位q=q->next;}}}5）找到多项式中与当前节点同指数项位置int locate(Linklist l,Lnode *&p,Lnode*e){p=l;//标记表头if (!l->next)return(0);while(p&&e->exp!=p->exp){//当p存在且指数不相等时指针后移p=p->next;}if(p)return(p);//当p存在时，返回p地址else {//没找到时寻找出插入位置p=l;while (p->next&&e->exp<=p->next->exp)p=p->next;if (!p->next){p=p;return(0);}return(0);}}6）将多项式节点插入已有多项式链表中，同时完成系数运算void caseinsert(Linklist &l,Lnode *e){Lnode *p;if (locate(l,p,e)){//指数相同项系数相加p->cof += e->cof;free(e);}else{//插入新的项e->next=p->next;p->next=e;}}7）创建新的多项式链表void creat(Linklist &head,int m){Lnode *p;int i;makehead(head);//建立头结点for (i=1;i<=m;i++){p=(Linklist)malloc(sizeof(Linklist));//建立新的多项式单个节点空间makelnode(p);//建立赋值caseinsert(head,p);//将多项式节点插入已有多项式链表中，同时完成系数运算}clear(head);}8）输入多项式项数并创建节点进行存储void input(Linklist &l){int m;printf("Input the Poly numbers\n");scanf("%d",&m);creat(l,m);//建立一个l指向的头指针有m项的多项式链表}9）输出多项式void print(Linklist l){Lnode *p;p=l->next;printf("Poly：%6fx^%d",p->cof,p->exp);p=p->next;while (p){if(p->cof>0) printf("+");//系数正负号if (fabs(p->cof)<=0.000001); break;//不输出系数为零的项printf("%6fx^%d",p->cof,p->exp);p=p->next;//指针后移}printf("\n");}10）进行多项式加法运算void add(Linklist la,Linklist lb,Linklist &lc){ Lnode *p,*q,*q1,*p1;p=la->next;q=lb->next;makehead(lc);//建立一个新的表头while(p){p1=p->next;caseinsert(lc,p);//将多项式节点p插入已有多项式链表lc中，同时完成系数运算p=p1;//指针后移}while(q){q1=q->next;caseinsert(lc,q);//将多项式节点q插入已有多项式链表lc中，同时完成系数运算q=q1;}}11）将减项多项式转化为系数为相反数的多项式便于转化为加法运算void reverse(Linklist &l){Linklist p;p=l->next;while(p){p->cof*=-1;//系数自乘-1p=p->next;}}12）进行多项式减法运算void sub(Linklist la,Linklist lb,Linklist &lc){reverse(lb);add(la,lb,lc);clear(lc);//清除头结点}13）对x赋值进行多项式赋值运算float value(Linklist l,float x){float sum=0,t;int i;Linklist p=l->next;while(p){t=1;for (i=p->exp;i>0;i--)t*=x;sum=sum+t*p->cof;p=p->next;}return(sum);}14）销毁已有多项式，清除已有多项式占用的存储空间void destroy(Linklist la){Lnode *p,*q;p=la;while(p){q=p;p=p->next;free(q);}}15）创建主程序即菜单界面void main(){Linklist l[10];int c,n,m,i;float a;printf("Choose the number to operate：\n");printf(" 1：Creat a Poly\n");printf(" 2：Poly Addition\n");printf(" 3：Poly Substraction\n");printf(" 4：Evaluation\n");printf(" 5：Destroy a Poly\n");printf(" 6：Print a Poly\n");printf(" 0：Exit\n");printf("\nDestroy the Polys after used.\n");printf("\n*use ',' to separate\n");scanf("%d",&c);while (c){switch (c){case 1: printf("Input the Poly number 1~9\n");scanf("%d",&n);input(l[n]);break;case 2: printf(" Input the Poly number to add,and the Poly number stored in\n");scanf("%d,%d,%d",&n,&m,&i);add(l[n],l[m],l[i]);break;case 3: printf(" Input the Poly number to subtract,and the Poly number stored in\n");scanf("%d,%d,%d",&n,&m,&i);sub(l[n],l[m],l[i]);break;case 4: printf("Input the number to operate and the value of x:\n");scanf("%d,%f",&n,&a);printf("%f\n",value(l[n],a));break;case 5: printf("Input the Poly number:\n");scanf("%d",&n);destroy(l[n]);break;case 6: printf(" Input the Poly number:\n");scanf("%d",&n);print(l[n]);case 0: n=0;break;default:printf("ERROR!");}printf("Choose the number to operate:\n");scanf("%d",&c);}printf("OK!\n");程序运行截图：实验总结：这次实验室数据结构第一次上机实验，由于与C语言课程的学习相隔已经一个学期，对C语言有些生疏和遗忘，在编程过程中出现很多错误。

实验报告课程名称：数据结构实验名称：一元多项式的相加班级： 1333 学生姓名：蔡景旺学号： 37一、需求分析1.用户可以根据自己的需求分别输入两个一元多项式（输入必须按指数递增顺序），并且能够实现输入的一元多项式的显示。

2.能够完成两个一元多项式的相加功能并显示结果。

3.程序执行的命令包括：（1）构造链表A （2）构造链表B （3）两个链表的相加（4）求链表的长度（5）打印（显示）已有的链表二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：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}基本操作:CreatPolyn(&p,m)操作结果：输入m项的系数和指数，建立一个一元多项式P。

DestroyPolyn(&p)初始条件：一元多项式P已存在。

操作结果：销毁一元多项式P。

PrintPolyn(P)初始条件：一元多项式P已存在。

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

PolynLength(P)初始条件：一元多项式P已存在。

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

AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。

操作结果：完成一元多项式相加运算，即：Pa=Pa+Pb,销毁一元多项式Pb.}ADT Polynomailtypedef struct{ // 项的表示，多项式为linklist的数据元素float coef; //系数int evpn; //指数}term,ElemType; //两个类型名：term用于本ADT,ElemType为Linklist的数据对象名Typedef Linklist polynomial; //用带表头结点的有序链表表示多项式；Int cmp(term a,term b)；void CreatPolyn (polynomial &P,int m){//输入m项的系数和指数，建立表示一元多项式的有序链表PInitList (P); h = GetHead (P);e.coef = 0.0;e.expn = -1;SetCurElem (h,e); //设置头结点的数据元素for （i = 1;i<=m;++i）{//依次输入m项非零项scanf(e.coef,e.expn);if (! LocateElem(P,e,q,(*cmp)){ //当链表不存在指数项if(MakeNode (s,e)) InsFirst(q,s);//生成结点并插入链表}}}//CreatPolynvoid AddPolyn(polynomial &Pa, polynomial &Pb){//多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”ha=Gethead(Pa); hb=Gethead(Pb);//ha和hb分别指向Pa和Pb的头结点qa=NextPos(Pa,ha); qb=NextPos(Pb,hb);// /ha和hb分别指向Pa和Pb的当前结点while(qa&&qb){//qa和qb均非空a=GetCurElem(qa); b=GetCurElem(qb);switch(*cmp(a,b)){case -1: //多项式PA中当前结点的指数值小ha=qa;qa= NextPos(Pa,ha);break;case 0://l两者的指数相等sum=a.cofe+b.cofe;if(sum!=0.0){//修改多项式PA中当前结点的系数值SetCurELem(qa,sum);ha=qa;}else {//删除当前结点Delfirst(ha,qa);FreeNode(qa);}Delfirst(ha,qa);FreeNode(qa); qb=NextPos(Pb,hb); qa=NextPos(Pa,ha);break;Case1://多项式PB中当前结点的指数值小DelFirst(hb,qb); InsFirst(ha,qb);qb=NextPos(Pb,hb); qa=NextPos(Pa,ha);break;}//swtich}//whileIf(!ListEmpty(Pb)) Append(Pa,qb);FreeNode(hb)://释放Pb头结点}//AddPolyn2. 数据结构分析：逻辑结构为线性表，采用链式存储结构。

问题描述：设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;//完成运算符和其他项的输//出,然后类似于上面，对第二个多项式进行相应的操作。

数据结构课题设计报告设计题目：一元多项式的加、乘法的实现姓名：班级：学号：指导老师：目录一、实验题目 (4)二、设计内容 (4)三、设计实现 (4)四、概要设计 (5)1，按要求输入一元多项式的系数 (5)2，计算一元多项式的加法 (5)3，输出计算结果 (5)4，按要求输入一元多项式的系数 (5)5，计算一元多项式的乘法 (5)6，输出计算结果 (5)7，退出 (5)五、程序流程图 (6)1，加法运算 (6)2，乘法运算 (7)六、源程序 (8)七、程序运行界面图 (20)1，加法运行输入项数 (20)2，输入每一项的系数及指数 (20)3，算出加法运算结果及乘法运行输入项数 (21)4，入乘法运算每一项的系数及指数 (21)5，算出乘法运算的结果 (22)八、心得体会................................................. - 23 -课程设计评分表 (24)一、实验题目一元多项式加法、乘法运算的实现二、设计内容该程序的功能是实现一个一元多项式运算。

能够完成两个多项式的相加、相乘的运算并且输出正确的答案。

三、设计实现一元多项式加法，乘法运算的实现1.根据输入创建一元多项式，采用顺序和链表存储结构实现顺序存储结构：在计算机内部可以采用不同方式存储一个线性表，其中最简单的方式就是用一组地址连续的存储单元来依次存储线性表中的数据元素。

对一元多项式存储结构的选择，输入多项式采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；一元多项式可以用顺序和链表两种存储结构表示，顺序结构的最大长度很难确定。

单链表的结构体可以用来存储多项式的系数，指数，便于实现任意多项式的运算。

2．创建的的第个一元多项式用于实现加法的运算，第二个一元多项式用于实现乘法的运算。

3.运算完毕后，退出运行程序四、概要设计1，按要求输入一元多项式的系数2，计算一元多项式的加法3，输出计算结果4，按要求输入一元多项式的系数5，计算一元多项式的乘法6，输出计算结果7，退出五、程序流程图 1，加法运算2，乘法运算六、源程序#include <stdio.h>#include <stdlib.h>#include <string.h>#define NULL 0typedef struct Node{ //定义结构体类型float coef; //系数int expn; //指数struct Node *next; //结构体指针}Node,*Linklist;struct polynode{int c;int e;struct polynode *next;};struct polynode * creat(void){int c,e;struct polynode *head=NULL;struct polynode *p1,*p2,*l,*r;while(scanf("%d,%d%*c",&c,&e),c||e){p2=(struct polynode *)malloc(sizeof(struct polynode)); p2->c=c;p2->e=e;p2->next=NULL;if(head==NULL){head=p2;continue;}for(l=r=head;l!=NULL&&(l->e)<e;l=l->next) r=l;if(l==head&&l->e>e) head=p2;else r->next=p2;p2->next=l;}return head;}void output(struct polynode* head){struct polynode *p1;p1=head;if(p1==NULL){printf("\n multinomial is zero\n");return;}printf("\n");while(p1!=NULL){printf(p1!=head&&(p1->c)>0? "+%d":"%d",p1->c);printf(p1->e? "x^%d":"",p1->e);p1=p1->next;}printf("\n");}struct polynode * add(struct polynode *head1,struct polynode *head2) {struct polynode *p1,*p2,*r,*l,*h;h=r=p1=head1;p2=head2;if(head1==NULL){h=head2;return h;}while (p1!=NULL&&p2!=NULL) {if(p1->e==p2->e){p1->c+=p2->c;p2=p2->next;r=p1;p1=p1->next;continue;}if(p1->e<p2->e){r=p1;p1=p1->next;continue;}if(p1->e>p2->e){l=p2;p2=p2->next;if(p1==h) h=l;else r->next=l;l->next=p1;r=l;continue;}}if (p1==NULL) r->next=p2;return h;}struct polynode * mul(struct polynode *head1,struct polynode *head2) {struct polynode *p,*p1,*p2,*r,*t,*head;head=NULL;if(head1==NULL||head2==NULL) return head;for(p2=head2;p2!=NULL;p2=p2->next){for(p1=head1;p1!=NULL;p1=p1->next){p=(struct polynode *)malloc(sizeof(struct polynode));p->c=p1->c*p2->c;p->e=p1->e+p2->e;p->next=NULL;if(p1==head1) t=p;else r->next=p;r=p;}head=add(head,t);}// output(head);return head;}Linklist creatpolyn(Linklist L,int n){ //构造新的一元多项式int i;Linklist head,p;head=(Linklist)malloc(sizeof(Node)); //创建头结点head->next=NULL;L=head;for(i=n;i>0;i--){p=(Linklist)malloc(sizeof(Node));printf("请输入一元多项式的第%d项的系数和指数：",i);scanf("%f%d",&(*p).coef,&(*p).expn); //输入系数和指数p->next=L->next;L->next=p;}return(head); //返回头结点}//creatpolynint cmp(int a,int b){ //比较a,b的大小if(a>b)return(1);elseif(a==b)return(0);elsereturn(-1);}void print(Linklist L){ //显示一元多项式Linklist p;p=L->next;while(p->next!=NULL){printf("%f*x^%d+",(*p).coef,(*p).expn); //输出多项式的项p=p->next;}printf("%f*x^%d\n",(*p).coef,(*p).expn); //输出多项式最后一项}//PrintLinklist Addpolyn(Linklist pa,Linklist pb){ //多项式相加int a,b;float sum;Linklist ha,hb,qa,qb,p1,p2;ha=pa; //ha,hb分别指向pa和pb中当前结点hb=pb;qa=ha->next; //qa和qb分别指向pa和pb中当前结点qb=hb->next;while(qa!=NULL&&qb!=NULL){ //qa和qb均非空a=(*qa).expn;b=(*qb).expn;switch(cmp(a,b)){ //比较指数case -1:{ //a<bha->next=qa;ha=ha->next;qa=qa->next; break;}case 0:{ //a=b sum=(*qa).coef+(*qb).coef;if(sum!=0.0){(*qa).coef=sum;ha->next=qa;ha=ha->next;}else{p1=qa;free(p1);}p2=qb;qa=qa->next;qb=qb->next;free(p2);break;}case 1:{ //a>b ha->next=qb;ha=ha->next;qb=qb->next;break;}}//switch}//whilewhile(qa!=NULL){ //如果qb不为空ha->next=qa;ha=ha->next;qa=qa->next;}while(qb!=NULL){ //如果qb不为空ha->next=qb;ha=ha->next;qb=qb->next;}return(pa);}//Addpolynvoid main(){int m,n,i;char t;Linklist pa,pb;pa=(Linklist)malloc(sizeof(Node));pb=(Linklist)malloc(sizeof(Node));printf("请输入一元多项式pa的项数:\n"); //构造一元多项式pascanf("%d",&m);pa=creatpolyn(pa,m);printf("请输入一元多项式pb的项数:\n"); //构造一元多项式pbscanf("%d",&n);pb=creatpolyn(pb,n);printf("多项式pa为:"); //输出paprint(pa);printf("多项式pb为:"); //输出pbprint(pb);printf("多项式pa与pb的和为:"); //输出多项式pa和pb的和print(Addpolyn(pa,pb));struct polynode *head1=NULL,*head2=NULL,*head=NULL;logn: printf("请输入需要相乘的多项式个数,至少2个: ");scanf("%d%c",&n);printf("\n 输入一个多项式的方式为:系数,指数; 例如: 3,4;5,6;7,8;as0,0;结束\n");printf("\n 请输入第1个多项式的系数和指数: ");head1=creat();printf("\n 第1个多项式的为: ");output(head1);for(i=1;i<n;i++){printf("\n 请输入第%d个多项式的系数和指数 : ",i+1);head2=creat();printf("\n 第%d个多项式为: ",i+1);output(head2);if(i==1)head=mul(head1,head2);else head=mul(head,head2);}printf("\n 多项式相乘结果为 : ");output(head);printf("\n 是否继续(y/n)? ");scanf("%*c%c",&t);if(t=='y') goto logn;}七、程序运行界面图1，加法运行输入项数2，输入每一项的系数及指数3，算出加法运算结果及乘法运行输入项数4，入乘法运算每一项的系数及指数5，算出乘法运算的结果八、心得体会通过这次的课程设计，是我又温习了数组、循环结构以及嵌套以及分块模块等C语言知识。

一元多项式加法一、实验目的通过实现多项式加法，对链表有更深入的了解二、实验内容问题描述：设计一个一元稀疏多项式简单的加法计算器实现要求：一元稀疏多项式简单计算器的基本功能是：（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)设计内容（1）使用顺序存储结构实现多项式加、减、乘运算。

例如：，求与结果：(2）使用链式存储结构实现多项式加、减、乘运算,，求与结果：2)设计要求（1)用C语言编程实现上述实验内容中得结构定义与算法。

（2）要有main（）函数,并且在ｍain(）函数中使用检测数据调用上述算法。

(3）用sｗitch语句设计如下选择式菜单。

＊**＊*＊*＊*＊**＊*＊数据结构综合性实验*＊＊**＊*＊＊＊*＊＊＊＊＊**＊＊*＊＊一、多项式得加法、减法、乘法运算*＊*＊***＊＊＊＊*＊＊＊＊＊ 1、多项式创建 *＊*＊*＊＊＊**＊*＊＊＊*＊2、多项式相加＊*＊＊＊****＊*＊＊＊**＊ 3、多项式相减＊**＊＊**＊*＊***＊＊＊＊４、多项式相乘＊*＊*＊＊*＊＊＊＊＊＊*＊＊* 5、清空多项式*＊＊＊＊＊**＊＊＊**＊＊＊＊０、退出系统 *＊＊＊＊*＊＊＊*＊＊＊＊＊** 请选择(０—5） *＊*＊***＊*＊＊＊＊**＊＊＊*＊＊＊*******＊＊*＊＊＊＊*＊*＊*＊*＊＊＊**＊*＊*＊*＊＊＊＊＊*请选择（０—5）:1、2数据结构设计根据下面给出得存储结构定义：#defiｎe ＭＡXSIZE 20 //定义线性表最大容量//定义多项式项数据类型ｔｙpｅdｅｆ stｒｕｃt｛ﻩfloaｔｃｏef; /／系数iｎt ｅxpn； //指数}teｒｍ，elｅmType;ｔｙｐedｅf sｔrｕｃt{ﻩterm ｔｅrｍs[MＡXSIZE]； //线性表中数组元素ｉｎt ｌast; //指向线性表中最后一个元素位置｝SeｑＬｉst;tyｐedef ＳeqLiｓt poｌynomｉal;１、3基本操作函数说明poｌynoｍial＊Init_Ｐｏlynomial()；/／初始化空得多项式int PｌｏｙｎSｔａtuｓ(polyｎomｉａl*p)//判断多项式得状态ｉnt Ｌocａtion＿Eｌeｍent（polynoｍial*p，terｍ x）在多项式p中查找与x项指数相同得项就是否存在ｉｎt Iｎserｔ_EｌemeｎｔBｙＯrder（polｙnomial*p,term ｘ)//在多项式ｐ中插入一个指数项xｉnt CｒeａtｅPolyn(polyｎomial＊Ｐ，iｎt m)//输入m项系数与指数，建立表示一元多项式得有序表pchａｒｐａre（term term1，teｒｍterm2)／/比较指数项tｅrm1与指数项ｔｅrm２poｌｙｎomｉａl＊ａdｄPｌｏyn（polｙnomiaｌ＊p1,ｐolynｏmiａl＊p2) ／/将多项式p１与多项式p２相加，生成一个新得多项式polynomial＊sｕbStｒacｔPloｙn（polｙnomiaｌ*p１，polｙnomial*ｐ２）/／多项式p1与多项式p２相减,生成一个新得多项式polynoｍiaｌ＊ｍulitPloyｎ(pｏｌｙnomｉal＊ｐ1，poｌynomiａl*ｐ2) ／／多项式p１与多项式p２相乘，生成一个新得多项式ｖoid prinｔPloｙn(polynｏmiaｌ＊p）／/输出在顺序存储结构得多项式p１、４程序源代码＃incluｄe〈stdlｉb、h>#inclｕdｅ〈stｄio、h＞#include〈iｏstreaｍ、h〉＃dｅfine NＵLL 0#ｄeｆine ＭAXSＩZＥ 20tyｐｅdef struct{ﻩfloat coef；ﻩｉnt expn；｝tｅrm，elemＴype;ｔypedef sｔrucｔ｛ﻩｔerm ｔerms[MAＸSIＺE];ﻩint lａst;｝SeｑＬiｓt；typｅdeｆ SｅqLｉst polynｏmiaｌ；ｖｏiｄｐｒiｎtPlｏｙｎ（polyｎoｍial*p)；iｎt PloyｎStatus(pｏlynｏｍiａl*p)｛if(p==ＮULL）ﻩ{retｕrn －1;｝ﻩelｓｅｉf（ｐ—>ｌaｓt=＝—1)｛ﻩｒetuｒn ０；ﻩ｝ｅｌseﻩ{ﻩrｅturｎ 1;ﻩ｝｝poｌynomial*Inｉt_Polyｎｏmial（）{ｐｏlynomiａl*Ｐ;ﻩP=new polｙnomial;ﻩif（P！=NULL）ﻩ｛P－＞last＝-1；ﻩﻩreｔurn P;ﻩ｝ﻩelse{ﻩﻩreturｎ NUＬL；ﻩ}}void Reｓet_Pｏlｙnomiaｌ（pｏｌynｏmial*ｐ){if(ＰlｏynStatｕs(p）＝=1）｛p-〉lａsｔ=－1;}｝ｉｎt Ｌocation_Elemeｎt（polｙnoｍial＊p，tｅrｍ x）{ﻩiｎt i=0；ｉf（PloyｎStａtｕs（ｐ)==—1)ﻩﻩreｔuｒn 0；ｗhilｅ(i〈＝ｐ->lasｔ＆＆ p—>tｅｒmｓ[ｉ］、expｎ!＝x、ｅxpn）｛i+＋；ﻩ}if（i〉ｐ—>last）｛ﻩﻩretuｒn 0;}elseﻩ｛retuｒｎ 1；ﻩ}｝int Insｅrｔ＿ElemenｔＢyＯrdｅr(polｙnomial＊p，term x）{ﻩint ｊ；ﻩiｆ(PｌoynＳtatｕｓ（p)==－１）return ０;ﻩif(p—＞last==MAXSIZE—１）{ﻩcoｕt＜<"Ｔhｅ polyｍ is ｆull!"〈＜ｅｎdｌ；ﻩｒeｔuｒn ０;｝ﻩj＝p—〉last;wｈｉlｅ(ｐ—＞ｔermｓ［j]、eｘpｎ<x、ｅxｐn && ｊ＞=0) {ﻩ p-〉tｅrms［j＋1］=ｐ->tｅrms[j];ﻩ j-—；｝p->tｅｒmｓ［j+1]=x；ｐ—〉ｌａst++；ﻩreturn 1；｝iｎｔ CｒeａｔePolyn(polｙnomiaｌ*Ｐ，int ｍ）｛float coeｆ;ｉnt exｐn；ｔerm x；if（PlｏyｎStatｕs（P）==－1）ﻩreturn ０；ﻩｉf(m＞MAXSIZＥ）{printf(”顺序表溢出\n"）；ﻩｒetuｒｎ0;｝elsｅ｛ﻩprｉntf（”请依次输入%ｄ对系数与指数、、、\ｎ＂，m）；ﻩfｏr(int i=０；ｉ<m；i++)ﻩﻩ{ﻩscanf(”％f％ｄ",＆ｃoef,&exｐn）;ﻩx、coｅf＝coｅf;ｘ、ｅxpn＝expｎ;ﻩﻩif（！Loｃaｔion＿Elemｅnt(P,ｘ）)｛ﻩﻩﻩIｎｓert＿ＥlｅmentBｙＯrder(Ｐ，x)；}ﻩﻩ}｝ｒeｔuｒn 1;｝chaｒ pａre（tｅｒm tｅrm１,terｍ tｅｒｍ2){iｆ（tｅrｍ１、expn〉ｔerm２、expn）｛ﻩｒeｔuｒn’＞＇；ﻩ}else iｆ(ｔerｍ1、expn〈teｒm2、expn）ﻩ｛retｕrｎ’＜';｝ﻩｅlseﻩ{ﻩreturn＇=’；ﻩ｝｝polｙｎomｉａl*aｄdPｌoｙｎ(ｐolynomｉal*ｐ1，polynomiaｌ＊p2）{ｉｎｔ i，ｊ,ｋ；ﻩi＝０;ﻩｊ=０；k=０；if(（PｌoynStａｔus(p1）==-１）｜|（PｌoyｎStatｕs(p2）==-1)) ﻩ｛ﻩﻩreturｎ NＵＬL；｝ﻩpolynｏｍiａl＊p3＝Iniｔ_Poｌｙnoｍiaｌ()；ｗhｉle（i＜=p１—>ｌast ＆＆ j＜=p2—＞last){ｓwｉtｃh(pａre(p１-＞terms[ｉ］,ｐ２->ｔerｍs［j］））ﻩﻩ{ﻩﻩcase'>’:ﻩﻩp3—〉termｓ［k++］＝p1-＞tｅｒｍs［i++］;ﻩp3—＞last+＋;ﻩﻩﻩﻩｂreak;ﻩcase'〈’:ﻩﻩﻩﻩｐ3－>terms［ｋ＋+]=p2—>ｔeｒｍs［ｊ＋+］;ﻩﻩp3－>laｓt+＋;ﻩbｒeak；ﻩcａse'='：ﻩﻩｉｆ（ｐ1－〉terｍs［i]、coｅf+p２-〉teｒｍｓ[j］、coef！＝0) ﻩﻩﻩ｛ﻩﻩp３->teｒｍｓ［ｋ］、coef=ｐ1->teｒms［i]、cｏef＋p２—〉ｔerm ｓ［ｊ]、cｏef；ﻩﻩp3－>teｒms[k]、expｎ＝p1-＞ｔerms［i]、ｅxpn;ﻩﻩﻩｋ＋+；ﻩp3—＞lａsｔ+＋;ﻩ｝ﻩﻩﻩi＋+；ﻩﻩﻩj++;｝ﻩ｝ﻩwhile(i〈=p１—〉last）{ﻩﻩp3－>tｅｒms［k+＋］=p1－〉ｔermｓ［ｉ++]；ﻩｐ3－〉lasｔ++;｝retｕrn p3;｝ｐolyｎｏmiａl＊sｕbＳtrａctPlｏｙｎ（polynoｍiａl＊p1，ｐoｌynomial*p2）{ﻩint i;i=０;ﻩiｆ（(PloynＳtaｔuｓ（p１）!=1)｜｜(PloynStatｕs（p2)!＝1))ﻩ{ﻩreｔurn ＮULL;}polynｏmial＊ｐ３＝Iｎit＿Polynoｍiaｌ（）;ﻩp3－〉ｌast=ｐ2—>last;fｏr(i=0；i〈=p2—>ｌａｓｔ;i++){ﻩﻩp3—>terms［i]、coef=—ｐ2－＞termｓ［i]、coeｆ;ﻩﻩp３—＞terｍs[i］、expn=ｐ2-〉terｍs［ｉ］、expn；｝ﻩp3=addＰloｙｎ（p1，p３);retｕrn ｐ3;｝ｐolynoｍial＊ｍulitPｌoｙｎ（ｐolynｏｍial＊p１，poｌynｏmｉal*p２) {ﻩint i;inｔ j;int k；ﻩi＝0;if((PloynＳtａtus(p1）!=1)｜|(PｌoynStaｔｕs(p２)!=1）)ﻩ｛ﻩretuｒn NULL;ﻩ｝polynoｍｉal*p3=Iｎiｔ_Polｙnomiaｌ(）；polyｎomiaｌ*＊p=new polyｎoｍiａｌ＊［p2－〉lasｔ+1］;ﻩfor(i=0;i〈=p2－＞ｌａsｔ；i＋+){ﻩfor(k＝0；k＜=p2-〉last;k++）{ﻩﻩp[k］=Ｉnit_Polｙnｏmiaｌ（)；ﻩﻩp[k］－＞ｌast＝ｐ１—>lａst；ﻩﻩfｏr（ｊ=0；j〈=ｐ１-＞ｌasｔ；ｊ++）ﻩ｛p［k］—>teｒms［j］、coeｆ=p１－>tｅrms［j]、coef＊ｐ２—>terｍs［k]、coef；ﻩp[k］-〉ｔｅｒｍs[j］、eｘpn=p1—>terms［j]、ｅｘｐn＋p2-〉terms[k］、expn;ﻩ}p３=addPloyn(p3，ｐ[ｋ]）；ﻩ｝ﻩ}ﻩｒeturn p3；｝void priｎtPloｙn(ｐolｙnｏmiａl＊p){ｉnt ｉ；fｏr（i=0;i〈＝p－>lａｓt；i++）ﻩ｛ﻩｉf(ｐ-＞terms[i]、ｃoeｆ〉0 ＆＆i＞０）ﻩcｏut＜<"+"＜<ｐ—＞terｍs[i]、coef;elsｅﻩﻩﻩcout＜〈ｐ—>ｔerms［i］、coef；ﻩcｏｕｔ＜＜＂x^"〈<p—＞tｅrms［i]、expn;ﻩ}ﻩcoｕt〈＜eｎdｌ；｝voｉｄ mｅnu（）｛ﻩｃoｕt〈〈”\t\t＊**＊*＊*数据结构综合性实验＊*＊＊＊＊＊＊*＂＜〈ｅndl；ｃout<<”\ｔ＼t*＊*一、多项式得加、减、乘法运算**＊”<<enｄｌ；ﻩcoｕt〈＜＂\t\t＊*＊*＊＊＊１、多项式创建 ****＊＊＊＊*”<〈eｎdl；ﻩcoｕt<〈＂\t\ｔ*＊＊＊*＊* 2、多项式相加 *＊**＊＊*＊＊”<＜e ｎdｌ;ｃouｔ<〈”\t＼t＊＊*＊＊＊* 3、多项式相减**＊*＊**＊*＂<<endl;cｏｕt＜<”\t\t*＊***＊* 4、多项式相乘＊＊*＊＊*＊*＊”<〈en ｄｌ;cout＜<"\t\t**＊**＊* 5、清空多项式 ***＊＊＊*＊*"〈〈endl；ｃout<〈"\t\t**＊＊**＊ 0、退出系统 *＊*＊＊＊＊＊*＂＜<endl；couｔ＜＜”\t\t＊**＊*＊请选择(０—5）*＊******"〈<e ｎdｌ;cout＜〈"\t\t*＊＊＊＊**＊*＊＊＊**＊＊**＊**＊＊*＊******＊＊＊*"〈＜endl；｝void ｍain（）｛ｉnt sｅl；ﻩpｏlynomiａl*p１=NULL；pｏｌynomial＊p2=NULL；ﻩpolｙｎｏｍiａl＊p3=NULL；ｗｈilｅ(１）｛ﻩﻩｍenｕ（);ﻩcout〈<”\t＼t*请选择(0-5)：”；ｃiｎ〉＞seｌ；sｗｉｔｃh（ｓel)ﻩ｛caｓe 1：ﻩﻩｐ1=Ｉｎit＿Poｌynomｉａl();ﻩﻩp2=Iｎit_Ｐolynomｉal（）；iｎｔ m;pｒiｎtf（"请输入第一个多项式得项数:\n"）；ﻩscanf（＂％d”,＆m）;ﻩﻩCreatePoｌyｎ（p1,m)；priｎｔf(＂第一个多项式得表达式为p1=”);ﻩﻩpｒｉｎtＰｌoyn（ｐ1）;ｐrintｆ（＂请输入第二个多项式得项数:\n＂)；ﻩﻩscaｎf（＂%ｄ＂,&m）;ﻩＣrｅatePoｌｙn(p2，m）;priｎtf（＂第二个多项式得表达式为p２="）；pｒinｔPloyn(ｐ2);ﻩﻩｂreak;ﻩｃaｓe ２：ﻩﻩpｒｉｎｔｆ(”p1+p2=＂)；if(（p3＝suｂStractＰｌoｙn（p1,p2)）！=NULL) ﻩﻩﻩｐrｉntPloyn(p3)；ﻩﻩbreak；ｃase 3:ﻩprintf（”\ｎp1—ｐ２＝”）;ﻩﻩif(（p3=ｓｕbStraｃtＰloyn（p1，p２）)!＝NULL)ﻩﻩprinｔPloyn（ｐ3）;ﻩﻩbreak；ﻩﻩcａｓｅ 4：ﻩprｉｎtf("＼ｎp1＊ｐ2=")；ﻩif((p3＝muliｔPlｏyn(p１，p2)）!＝NULL) ﻩﻩｐrｉntPｌoyn（ｐ3）;ﻩｃase ５：Rｅsｅｔ＿Pｏlynｏｍial（ｐ1）；Reseｔ_Polｙnｏmiａl（p2)；Resｅｔ_Ｐoｌｙnomial（p3）；ﻩﻩﻩｂreａk；ﻩcａse 0:return；ﻩﻩ｝ﻩ｝ﻩｒetuｒn;}1、5程序执行结果2、迷宫问题实现２、1设计内容及要求1)设计内容以一个m＊ｎ得长方阵表示迷宫,０与１分别表示迷宫中得通路与障碍。

数据结构课程设计设计题目：利用线性表链式存储实现一元多项式相加减目录第一章、课题描述1第二章、课题设计目的1第三章、课题设计意义1第四章、设计思路1第五章、需求分析2第六章、概要设计26.1、存储结构：26.2、基本算法：26.2.1、输入输出26.2.2、构造数据类型36.2.3、多项式的加法46.2.4、多项式的减法4第七章、程序结果及截图4第八章、算法的时间复杂度及改进5 第九章、总结及心得体会5第十章、附录6第十一章、参考文献13第一章、课题描述能够完成两个或多个多项式的输出，并且实现两个多项式的相加和相减，并且输出结果。

第二章、课题设计目的了解数据结构与算法的设计方法，独立分析和设计一元多项式加减的程序编码，通过程序编写掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能，提高综合运用所学的理论知识和方法独立分析和解决问题的能力，通过这次实践将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理，掌握线性表的链式存储如何实现一元多项式的加减，通过不断探索程序的算法，不断优化程序，使得学生的知识掌握更加牢固，实践能力加强，也激发了学生对于数据结构这门课的兴趣，为以后这门课的深入研究做了准备，这次实践使同学更加深入了解了数据结构内在的逻辑关系。

第三章、课题设计意义通过完成此次课题，可以了解各种数据结构内在的逻辑关系，讨论它在计算机中的存储表示，以及在其上进行各种运算时的算法实现，并对算法的效率和优化进行简单的分析和讨论，不仅加强了学生对于线性表链式存储的理解，也提高了学生的思维能力，促进学生的综合应用能力和专业素质的提高，解决了现实生活中复杂繁琐的计算过程，不仅提高了效率，也增加了正确率，学生对于线性表和指针等知识的理解更加深入深刻，也灵活运用了理论知识解决了实际问题，活学活用，加强了学生的实践能力，同时完成作业还需要与同学的讨论，增强了学生的团队合作能力。

第四章、设计思路这个程序的关键是多项式的创建和排列，以及相加时相同指数的系数相加。

《数据结构》实验报告1、实验名称:实现一元多项式的加法2、实验日期: 2011-3-73、基本要求：1）编程实现一元多项式的加法；2）设计一个测试主函数。

4、实验目的：通过实验使学生掌握链表的最基本和最主要的操作：插入和删除操作。

5、测试数据：随意输入两个一元多项式的系数和指数：第一个：系数：4 8 6 7；指数：2 3 4 5第二个：系数：5 9 3 8；指数：1 3 5 6两式相加后输出结果。

6、算法思想或算法步骤:1）用尾插入法创建单链表（PLoy *create_Ploy_LinkList(void)）2）输出单链表中所有结点的值，得到一元多项式（void output_Ploy_LinkList(PLoy *L, char ch)）3）进行多项式的相加，采用链式存储表示加法，根据结点类型定义，若指数不同，则进行链表的合并；若指数相同，则进行系数相加；若和为0，则去掉结点；若和不为0，则修改结点的系数域。

（PLoy *add_ploy(PLoy *La, PLoy *Lb)）7、模块划分：1）头文件stdiob.h。

头文件stdiob.h中包括：结点结构体定义、一元多项式的系数和指数的输入、一元多项式的输出以及两式相加输出结果的操作等；2）实现文件yydxsxj.cpp。

包含主函数int main()，其功能是测试所设计的一元多项式加法的正确性。

8、数据结构：链表中的结点的结构体定义如下：typedef struct Node{float coef; /*系数部分*/int expn; /*指数部分*/struct Node *next ;} PloyNode;9、源程序：源程序存放在两个文件中，即头文件stdiob.h和实现文件yydxsxj.cpp。

//头文件stdiob.htypedef struct Node{float coef; /*系数部分*/int expn; /*指数部分*/struct Node *next ;} PloyNode;PloyNode *create_Ploy_LinkList(void){/* 尾插入法创建单链表,链表的头结点head作为返回值 */ float coef ; int expn ;PloyNode *head, *p, *q;head=p=(PloyNode *)malloc(sizeof(PloyNode));p->next=NULL; /* 创建单链表的表头结点head */while (1){printf("\n请输入一元多项式的系数(0表示结束): ") ;scanf("%f",&coef);if (coef==0) break ;else{printf("\n请输入一元多项式的指数: ") ;scanf("%d",&expn);q=(PloyNode *)malloc(sizeof(PloyNode));q->coef=coef ; /* 指数部分赋值 */q->expn=expn ; /* 系数部分赋值 */q->next=p->next; p->next=q; p=q ;/* 钩链，新创建的结点总是作为最后一个结点 */ }}return(head);}void output_Ploy_LinkList(PloyNode *L, char ch)/* 输出以L为头结点的单链表中所有结点的值 */ {PloyNode *p;p=L->next; /* 使p指向第一个结点 */if (p==NULL) printf("\n此多项式为空!!\n\n") ;else{printf("f(x)= \n",ch) ;while (p!=NULL){if (p->coef>0)printf("%+g",p->coef) ;else printf("%g",p->coef) ;if (p->expn!=0){printf("X^") ;printf("%d",p->expn);}p=p->next;}} /* 移动指针p */printf("\n\n") ;}PloyNode *add_Ploy(PloyNode *La, PloyNode *Lb){PloyNode *Lc , *pc , *pa , *pb ,*ptr ; float x ;Lc=pc=La ; pa=La->next ; pb=Lb->next ;if(pa==NULL&&pb==NULL)printf("两个式子之和也为空项");while (pa!=NULL&&pb!=NULL){if (pa->expn< pb->expn){pc->next=pa ; pc=pa ; pa=pa->next ; } else{if (pa->expn>pb->expn){ pc->next=pb ; pc=pb ; pb=pb->next ; }else{x=pa->coef+pb->coef ;if (x==0){ ptr=pa ; pa=pa->next ;ptr=pb ; pb=pb->next ;}else{ pc->next=pa ; pa->coef=x ;pc=pa ; pa=pa->next ;ptr=pb ; pb=pb->next ;}}}}if (pa==NULL) pc->next=pb ;else pc->next=pa ;return (Lc) ;}//实现文件yydxsxj.cpp#include<iostream>#include<malloc.h>#include"stdiob.h"using namespace std;int main(){PloyNode * pa,* pb;char pc,pd;cout<<"请输入第一个多项式(按指数递增顺序输入):"<<endl; pa=create_Ploy_LinkList();output_Ploy_LinkList(pa,pc);cout<<"请输入第二个多项式(按指数递增顺序输入):"<<endl; pb=create_Ploy_LinkList();output_Ploy_LinkList(pb,pd);cout<<"多项式相加结果是:"<<endl;add_Ploy(pa,pb);output_Ploy_LinkList(pa,pc);return 0;}10、测试情况：1）程序运行输出为：第一个多项式为：f(x)=+4x^2+8x^3+6x^4+7x^5第二个多项式为：f(x)=+5x^1+9x^3+3x^5+8x^6两式相加之和为：f(x)=+5x^1+4x^2+17x^3+6x^410x^5+8x^6 2）测试结果分析：程序运行结果和预测的完全相同，说明所设计的一元多项式的加法是正确的。

《算法与数据结构》实验报告姓名：***班级：计科01学号：**********实验题目：链表的应用实验内容：一元多项式求和把任意给定的两个一元多项式P(x),Q(x)输入计算机，计算它们的和并输出计算结果。

设计分析：一元多项式可以用单链表表示，结点结构图示如下：Array一元多项式链表的结点结构一元多项式算法伪代码如下：源程序代码：#include"StdAfx.h"#include<stdlib.h>typedef struct LNode{int x,z;struct LNode *next;}LinkList;void OutLinkList(LinkList *L);void PutLinkList(LinkList *&L,int n);LinkList *AddLinkList(LinkList *a,LinkList *b);void OutXLinkList(LinkList *L);void OutZLinkList(LinkList *L);void main(){int n,m;LinkList *a,*b,*c;printf("\t\t\t本À?程¨¬序¨°可¨¦以°?完ª¨º成¨¦两¢?个?一°?元a多¨¤项?式º?的Ì?加¨®法¤¡§运?算?。

¡ê\n");printf("请?输º?入¨?一°?元a多¨¤项?式º?a的Ì?项?数ºym：êo");scanf("%d",&m);printf("请?按ã¡ä照?从䨮低̨ª次ä?到Ì?高?次ä?的Ì?顺3序¨°依°¨¤此ä?输º?入¨?一°?元a多¨¤项?式º?a的Ì?系¦Ì数ºy和¨ª指?数ºy：êo\n");PutLinkList(a,m);printf("a=");OutLinkList(a);printf("请?输º?入¨?一°?元a多¨¤项?式º?b的Ì?项?数ºyn：êo");scanf("%d",&n);printf("请?按ã¡ä照?从䨮低̨ª次ä?到Ì?高?次ä?的Ì?顺3序¨°依°¨¤此ä?输º?入¨?一°?元a多¨¤项?式º?b的Ì?系¦Ì数ºy和¨ª指?数ºy：êo\n");PutLinkList(b,n);printf("b=");OutLinkList(b);c=AddLinkList(a,b);printf("两¢?个?多¨¤项?式º?的Ì?和¨ª为a：êo\na+b=");OutLinkList(c);}void PutLinkList(LinkList *&L,int n){LinkList *s,*r;L=(LinkList *)malloc(sizeof(LinkList));r=L;for(int i=0;i<n;i++){s=(LinkList *)malloc(sizeof(LinkList));printf("请?输º?入¨?第̨²%d项?的Ì?系¦Ì数ºy：êo",i+1);scanf("%d",&s->x);printf("请?输º?入¨?第̨²%d项?的Ì?指?数ºy：êo",i+1);scanf("%d",&s->z);r->next=s;r=s;}r->next=NULL;}void OutLinkList(LinkList *L) {char FuHao;LinkList *p=L->next;FuHao=p->x>0? '+':'-';if(FuHao=='-'){printf("%c",FuHao);if(p->x==-1)printf("1");}OutXLinkList(p);OutZLinkList(p);p=p->next;while(p!=NULL){FuHao=p->x>0? '+':'-';printf("%c",FuHao);OutXLinkList(p);OutZLinkList(p);p=p->next;}printf("\n");}void OutXLinkList(LinkList *L) {int xi=L->x>0? L->x:-L->x;if(L->x==1||L->x==-1);elseprintf("%d",xi);}void OutZLinkList(LinkList *L) {if(L->z==0);else if(L->z==1||L->z==-1){if(L->z<0){if(L->x==1||L->x==-1)printf("1");printf("/");}printf("X");}else{if(L->z<0)printf("/");int zhi=L->z>0? L->z:-L->z;printf("X^%d",zhi);}}LinkList *AddLinkList(LinkList *a,LinkList *b){a=a->next;b=b->next;LinkList *c,*d,*s;c=(LinkList *)malloc(sizeof(LinkList));d=c;while(a!=NULL&&b!=NULL){if(a->z<b->z){s=(LinkList *)malloc(sizeof(LinkList));s->x=b->x;s->z=b->z;d->next=s;d=s;b=b->next;}else if(a->z>b->z){s=(LinkList *)malloc(sizeof(LinkList));s->x=a->x;s->z=a->z;d->next=s;d=s;a=a->next;}else{s=(LinkList *)malloc(sizeof(LinkList));s->x=a->x+b->x;s->z=a->z;if(s->x==0);else{d->next=s;d=s;}a=a->next;b=b->next;}}if(a!=NULL)d->next=a;else if(b!=NULL)d->next=b;elsed->next=NULL;return c;}测试用例：当a=3x^8-x^5+2x^3+7x^2+5x,b=5x^5+3x^4-7x^2-3x^(-3)时，运行结果如下：试验总结：通过本次试验，学会了链表的应用，加深了对链表的理解，知道了链表是把线性表中的元素按照链式储存方式到计算机中的一片连续的储存空间中。