中南民族大学数据结构实验报告

院系：计算机科学学院专业：计算机科学与技术年级： 2011级课程名称：数据结构学号： ******** *名：***指导教师：***2013年 6月10日设计题目一：一元稀疏多项式计算器【问题描述】一元稀疏多项式计算器【基本要求】一元稀疏多项式简单计算器的功能是：（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；（3）多项式a和b相加，建立多项式a+b；（4）多项式a和b相减，建立多项式a-b。

一、需求分析1. 定义线性表的动态分配顺序存储结构；2. 建立多项式存储结构，定义指针*next3. 利用链表实现队列的构造。

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

多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en 序列按指数降序排列。

5.设计思路分析要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为:序数coef指数expn指针域next运用尾插法建立两条单链表，以单链表LinkList p和LinkList h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题,将单链表LinkList p中的结点插入到单链表LinkList h中即可。

为了实现处理，设p、q分别指向单链表LinkList a和LinkList b的当前项，比较p、q结点的指数项，由此得到下列运算规则：若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移; 若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p 的系数; 若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

6.测试数据（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、元素类型、结点类型和指针类型：typedef struct Polynode{float coef; //系数int exp; //指数struct Polynode *next;}*Poly,Polynode; //Poly为结点指针类型2、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点:LinkList CreateLinkList(LinkList head,int m){int i;LinkList p;p=head=(LinkList)malloc(sizeof(struct LNode));head->next=NULL;for(i=0;i<m;i++){p=(LinkList)malloc(sizeof(struct LNode));printf("请输入第%d项的系数与指数:",i+1);scanf("%f %d",&p->coef,&p->expn);Insert(p,head);}return head;}3、主函数和其他函数：int main(){int m,n,flag=0;float x;Poly pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULL ·········}主函数- 建立链表->多项式相加减—>输出多项式三、详细设计：#include<stdio.h>#include<malloc.h>#include<iostream.h>typedef struct Polynode{float coef; //系数int exp; //指数struct Polynode *next;}*Poly,Polynode; //Poly为结点指针类型void Insert(Poly p,Poly head){if(p->coef==0) //系数为0时释放结点free(p);else{Poly q1,q2;q1=head;q2=head->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;}}}//InsertPoly CreateList(Poly head,int m){ //建立一个头指针为head、项数为m的一元多项式int i;Poly p;Polynode *q;p=head=(Poly)malloc(sizeof(struct Polynode));head->next=NULL;for(i=0;i<m;i++){p=(Poly)malloc(sizeof(struct Polynode));//建立新结点以接收数据cout<<"请输入第"<<i+1<<"项的系数与指数: ";cin>>p->coef>>p->exp;Insert(p,head); //调用Insert函数插入结点}q=head->next;while(q!=NULL){cout<<"系数："<<q->coef<<"\t"<<"指数: "<<q->exp<<endl;q=q->next;}return head;}//CreatePolyvoid DestroyList(Poly p){ //销毁多项式pPoly q1,q2;if(p->next!=NULL){q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指针后移q2=q2->next;}}}int OutputList(Poly P){ //输出多项式Poly q=P->next;int flag=1;//项数计数器if(!q){ //若多项式为空，输出0cout<<" 0 "<<endl;return(0);}while (q){if(q->coef>0&&flag!=1) //系数大于0且不是第一项cout<<"+";if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况{cout<<q->coef;if(q->exp==1)cout<<"X";else if(q->exp)cout<<"X^"<<q->exp;}else{if(q->coef==1){if(!q->exp)cout<<"1";else if(q->exp==1)cout<<"X";else if(q->exp)cout<<"X^"<<q->exp;}if(q->coef==-1){if(!q->exp) cout<<"-1";else if(q->exp==1) cout<<"-X";else cout<<"-X^"<<q->exp;}}q=q->next;flag++;}//whilecout<<endl;return(0);}//OutputPolyint compare(Poly a,Poly 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多项式非空}//comparePoly AddPoly(Poly pa,Poly pb){//求解并建立和多项式a+b，返回其头指针Poly qa=pa->next;Poly qb=pb->next;Poly headc,hc,qc;hc=(Poly)malloc(sizeof(struct Polynode));//建立头结点hc->next=NULL;headc=hc;while(qa||qb){qc=(Poly)malloc(sizeof(struct Polynode));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;}//AddPolyPoly SubtractPoly(Poly pa,Poly pb){//求解并建立和多项式a-b，返回其头指针Poly qa=pa->next;Poly qb=pb->next;Poly headc,hc,qc;hc=(Poly)malloc(sizeof(struct Polynode));//建立头结点hc->next=NULL;headc=hc;while(qa||qb){qc=(Poly)malloc(sizeof(struct Polynode));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;}//AddPolyPoly MultiplyPoly(Poly pa,Poly pb){//求解并建立积多项式a*b，返回其头指针Poly hf,pf;Poly qa=pa->next;Poly qb=pb->next;hf=(Poly)malloc(sizeof(struct Polynode));//建立头结点hf->next=NULL;for(qa=pa->next;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){pf=(Poly)malloc(sizeof(struct Polynode));pf->coef=qa->coef*qb->coef;pf->exp=qa->exp+qb->exp;Insert(pf,hf);//调用Insert函数以合并指数相同的项}}return hf;}//MultiplyPolyvoid DevicePoly(Poly pa,Poly pb){//求解并建立商多项式a/b，返回其头指针Poly hf,pf,temp1,temp2;Poly qa=pa->next;Poly qb=pb->next;hf=(Poly)malloc(sizeof(struct Polynode));//建立头结点,存储商hf->next=NULL;pf=(Poly)malloc(sizeof(struct Polynode));//建立头结点，存储余数pf->next=NULL;temp1=(Poly)malloc(sizeof(struct Polynode));temp1->next=NULL;temp2=(Poly)malloc(sizeof(struct Polynode));temp2->next=NULL;temp1=AddPoly(temp1,pa);while(qa!=NULL&&qa->exp>=qb->exp){temp2->next=(Poly)malloc(sizeof(struct Polynode));temp2->next->coef=(qa->coef)/(qb->coef);temp2->next->exp=(qa->exp)-(qb->exp);Insert(temp2->next,hf);pa=SubtractPoly(pa,MultiplyPoly(pb,temp2));qa=pa->next;temp2->next=NULL;}pf=SubtractPoly(temp1,MultiplyPoly(hf,pb));cout<<"商是：";OutputList(hf);cout<<"余数是：";OutputList(pf);}//DevicePolyfloat ValuePoly(Poly head,float x){//输入x值，计算并返回多项式的值Poly p;int i;float sum=0,t;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，进行乘法}sum+=p->coef*t;}return sum;}//ValuePolyPoly Derivative(Poly head){//求解并建立a的导函数多项式，并返回其头指针Poly q=head->next,p1,p2,hd;hd=p1=(Poly)malloc(sizeof(struct Polynode));//建立头结点hd->next=NULL;while(q){if(q->exp!=0){ //该项不是常数项时p2=(Poly)malloc(sizeof(struct Polynode));p2->coef=q->coef*q->exp;p2->exp=q->exp-1;p2->next=p1->next;//尾插法插入结点p1->next=p2;p1=p2;}else if(q->exp==0) //该项为常数项break;q=q->next;}return hd;}//Dervativeint main(){int m,n,flag=0;float x;Poly pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULLcout<<"请输入a的项数:" ;cin>>m;pa=CreateList(pa,m);//建立多项式acout<<"请输入b的项数:" ;cin>>n;pb=CreateList(pb,n);//建立多项式a//输出菜单cout<<"---------------------------------------------------------------------"<<endl;cout<<" 1.输出多项式a和b \n"; cout<<" 2.建立多项式a+b \n";cout<<" 3.建立多项式a-b \n"; cout<<" 4.建立多项式a*b \n"; cout<<" 5.建立多项式a/b \n"; cout<<" 6.计算多项式a在x处的值\n"; cout<<" 7.求多项式a的导函数\n"; cout<<" 8.退出程序\n"; cout<<"----------------------------------------------------------------------"<<endl;for(;;flag=0){cout<<"执行操作为:" ;cin>>flag;if(flag==1){cout<<"多项式a为：";OutputList(pa);cout<<"多项式b为：";OutputList(pb);continue;}if(flag==2){pc=AddPoly(pa,pb);cout<<"多项式a+b为：";OutputList(pc);DestroyList(pc);continue;}if(flag==3){pd=SubtractPoly(pa,pb);cout<<"多项式a-b为：";OutputList(pd);DestroyList(pd);continue;}if(flag==4){pe=MultiplyPoly(pa,pb);cout<<"多项式a*b为：";OutputList(pe);DestroyList(pe);continue;}if(flag==5){DevicePoly(pa,pb);continue;}if(flag==6){cout<<"请输入x的值：x=";cin>>x;cout<<"多项式a的值为:"<<ValuePoly(pa,x)<<endl;continue;}if(flag==7){pf=Derivative(pa);cout<<"多项式a的导函数为：";OutputList(pf);DestroyList(pf);continue;}if(flag==8)break;if(flag<1||flag>8)cout<<"输入错误请重新选择!!";continue;}DestroyList(pa);DestroyList(pb);return 0;}四、运行结果截屏：（七项测试数据经运行皆正确）以测试数据（1）(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7); 为例：五、心得体会设计题目二：马踏棋盘【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。