数据结构课程设计报告一元多项式加法减法乘法运算的实现.doc
-1.一元多项式加法、减法、乘法运算的实现1.1设计容及要求1)设计容1使用顺序存储构造实现多项式加、减、乘运算。例如：,求和结果：2使用链式存储构造实现多项式加、减、乘运算，求和结果：2设计要求1用C语言编程实现上述实验容中的构造定义和算法。2要有main()函数，并且在main()函数中使用检测数据调用上述算法。3用switch语句设计如下选择式菜单。 *数据构造综合性实验* *一、多项式的加法、减法、乘法运算* * 1.多项式创立 * * 2.多项式相加 * * 3.多项式相减 * 4.多项式相乘 * 5.清空多项式 * 0.退出系统 * 请选择05 *请选择0-5:1.2数据构造设计根据下面给出的存储构造定义：#define MA*SIZE 20 /定义线性表最大容量 /定义多项式项数据类型typedef structfloat coef; /系数int e*pn; /指数 term,elemType;typedef structterm termsMA*SIZE; /线性表中数组元素int last; /指向线性表中最后一个元素位置 SeqList;typedef SeqList polynomial;1.3根本操作函数说明polynomial*Init_Polynomial();/初始化空的多项式int PloynStatus(polynomial*p)/判断多项式的状态int Location_Element(polynomial*p,term *)在多项式p中查找与*项指数一样的项是否存在int Insert_ElementByOrder(polynomial*p,term *)/在多项式p中插入一个指数项*int CreatePolyn(polynomial*P,int m)/输入m项系数和指数，建立表示一元多项式的有序表pchar pare(term term1,term term2)/比拟指数项term1和指数项term2polynomial*addPloyn(polynomial*p1,polynomial*p2)/将多项式p1和多项式p2相加，生成一个新的多项式polynomial*subStractPloyn(polynomial*p1,polynomial*p2)/多项式p1和多项式p2相减，生成一个新的多项式polynomial*mulitPloyn(polynomial*p1,polynomial*p2)/多项式p1和多项式p2相乘，生成一个新的多项式void printPloyn(polynomial*p)/输出在顺序存储构造的多项式p1.4程序源代码#include<stdlib.h>#include<stdio.h>#include<iostream.h>#define NULL 0#define MA*SIZE 20typedef structfloat coef;int e*pn;term,elemType;typedef structterm termsMA*SIZE;int last;SeqList;typedef SeqList polynomial;void printPloyn(polynomial*p);int PloynStatus(polynomial*p)if(p=NULL)return -1;else if(p->last=-1)return 0;elsereturn 1;polynomial*Init_Polynomial()polynomial*P;P=new polynomial;if(P!=NULL)P->last=-1;return P;elsereturn NULL;void Reset_Polynomial(polynomial*p)if(PloynStatus(p)=1)p->last=-1;int Location_Element(polynomial*p,term *)int i=0;if(PloynStatus(p)=-1)return 0;while(i<=p->last && p->termsi.e*pn!=*.e*pn)i+;if(i>p->last)return 0;elsereturn 1;int Insert_ElementByOrder(polynomial*p,term *)int j;if(PloynStatus(p)=-1)return 0;if(p->last=MA*SIZE-1)cout<<"The polym is full!"<<endl;return 0;j=p->last;while(p->termsj.e*pn<*.e*pn && j>=0) p->termsj+1=p->termsj; j-; p->termsj+1=*;p->last+;return 1;int CreatePolyn(polynomial*P,int m)float coef;int e*pn;term *;if(PloynStatus(P)=-1)return 0;if(m>MA*SIZE)printf("顺序表溢出n");return 0;elseprintf("请依次输入%d对系数和指数.n",m);for(int i=0;i<m;i+)scanf("%f%d",&coef,&e*pn);*.coef=coef;*.e*pn=e*pn;if(!Location_Element(P,*)Insert_ElementByOrder(P,*);return 1;char pare(term term1,term term2)if(term1.e*pn>term2.e*pn)return'>'else if(term1.e*pn<term2.e*pn)return'<'elsereturn'='polynomial*addPloyn(polynomial*p1,polynomial*p2)int i,j,k;i=0;j=0;k=0;if(PloynStatus(p1)=-1)|(PloynStatus(p2)=-1)return NULL;polynomial*p3=Init_Polynomial();while(i<=p1->last && j<=p2->last)switch(pare(p1->termsi,p2->termsj)case'>':p3->termsk+=p1->termsi+;p3->last+;break;case'<':p3->termsk+=p2->termsj+;p3->last+;break;case'=':if(p1->termsi.coef+p2->termsj.coef!=0)p3->termsk.coef=p1->termsi.coef+p2->termsj.coef;p3->termsk.e*pn=p1->termsi.e*pn;k+;p3->last+;i+;j+;while(i<=p1->last)p3->termsk+=p1->termsi+;p3->last+;return p3;polynomial*subStractPloyn(polynomial*p1,polynomial*p2)int i;i=0;if(PloynStatus(p1)!=1)|(PloynStatus(p2)!=1)return NULL;polynomial*p3=Init_Polynomial();p3->last=p2->last;for(i=0;i<=p2->last;i+)p3->termsi.coef=-p2->termsi.coef;p3->termsi.e*pn=p2->termsi.e*pn;p3=addPloyn(p1,p3);return p3;polynomial*mulitPloyn(polynomial*p1,polynomial*p2)int i;int j;int k;i=0;if(PloynStatus(p1)!=1)|(PloynStatus(p2)!=1)return NULL;polynomial*p3=Init_Polynomial();polynomial*p=new polynomial*p2->last+1;for(i=0;i<=p2->last;i+)for(k=0;k<=p2->last;k+)pk=Init_Polynomial();pk->last=p1->last;for(j=0;j<=p1->last;j+)pk->termsj.coef=p1->termsj.coef*p2->termsk.coef;pk->termsj.e*pn=p1->termsj.e*pn+p2->termsk.e*pn;p3=addPloyn(p3,pk);return p3;void printPloyn(polynomial*p)int i;for(i=0;i<=p->last;i+)if(p->termsi.coef>0 && i>0)cout<<"+"<<p->termsi.coef;elsecout<<p->termsi.coef;cout<<"*"<<p->termsi.e*pn;cout<<endl;void menu()cout<<"tt*数据构造综合性实验*"<<endl;cout<<"tt*一、多项式的加、减、乘法运算*"<<endl;cout<<"tt* 1.多项式创立 *"<<endl;cout<<"tt* 2.多项式相加 *"<<endl;cout<<"tt* 3.多项式相减 *"<<endl;cout<<"tt* 4.多项式相乘 *"<<endl;cout<<"tt* 5.清空多项式 *"<<endl;cout<<"tt* 0.退出系统 *"<<endl;cout<<"tt* 请选择(0-5) *"<<endl;cout<<"tt*"<<endl;void main()int sel;polynomial*p1=NULL;polynomial*p2=NULL;polynomial*p3=NULL;while(1)menu();cout<<"tt*请选择(0-5):"cin>>sel;switch(sel)case 1:p1=Init_Polynomial();p2=Init_Polynomial();int m;printf("请输入第一个多项式的项数:n");scanf("%d",&m);CreatePolyn(p1,m);printf("第一个多项式的表达式为p1=");printPloyn(p1);printf("请输入第二个多项式的项数:n");scanf("%d",&m);CreatePolyn(p2,m);printf("第二个多项式的表达式为p2=");printPloyn(p2);break;case 2:printf("p1+p2=");if(p3=subStractPloyn(p1,p2)!=NULL)printPloyn(p3);break;case 3:printf("np1-p2=");if(p3=subStractPloyn(p1,p2)!=NULL)printPloyn(p3);break;case 4:printf("np1*p2=");if(p3=mulitPloyn(p1,p2)!=NULL)printPloyn(p3);case 5:Reset_Polynomial(p1);Reset_Polynomial(p2);Reset_Polynomial(p3);break;case 0:return;return;1.5程序执行结果2.迷宫问题实现2.1设计容及要求1设计容以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的道路，或得出没有通路的结论。2)设计要求1用C语言编程实现上述实验容中的构造定义和算法；2要有main()函数，并且在main()函数中使用检测数据调用上述算法；2.2数据构造设计根据以上问题给出存储构造定义：typedef struct /定义坐标int *;int y;item; /定义坐标和方向typedef structint *;int y;int d;dataType; /定义顺序栈的类型定义typedef structdataType dataMA*LEN;int top;SeqStack;item move8; /8邻域试探方向数组int mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,; /定义迷宫数组，0表示有路径，1表示不存在路径2.3根本操作函数说明void print_Path(SeqStack*s);/输出迷宫路线SeqStack*InitSeqStack()/该函数初始化一个空栈，并返回指向该栈的存储单元首地址int Push(SeqStack*s,dataType *)/将元素*入栈s,假设入栈成功返回结果1；否则返回0int StackEmpty(SeqStack*s)/该函数判断栈是否为空，假设栈空返回结果1；否则返回0int Pop(SeqStack*s,dataType*)/将栈顶元素出栈，放入*所指向的存储单元中，假设出栈返回结果1；否则返回0void init_move(item move8)/初始化8邻域方向int find_Path(int mazeM+2N+2,item move8)/在迷宫maze二维数组中按move的8邻域方向探测迷宫路线，存在返回1，否则返回0void print_Path(SeqStack*s)/输出栈s中所有迷宫路径2.4程序源代码#include<stdio.h>#include<stdlib.h>#define M 6#define N 8#define MA*LEN 100typedef structint *;int y;item;typedef structint *;int y;int d;dataType;typedef structdataType dataMA*LEN;int top;SeqStack;item move8;int mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,;void print_Path(SeqStack*s);SeqStack*InitSeqStack()SeqStack*s;s=new SeqStack;s->top=-1;return s;int Push(SeqStack*s,dataType *)if(s->top=MA*LEN-1)return 0;elses->top+;s->datas->top=*;return 1;int StackEmpty(SeqStack*s)if(s->top=-1)return 1;elsereturn 0;int Pop(SeqStack*s,dataType*)if(StackEmpty(s)return 0;else*=s->datas->top;s->top-;return 1;void init_move(item move8)move0.*=0;move0.y=1;move1.*=1;move1.y=1;move2.*=1;move2.y=0;move3.*=1;move3.y=-1;move4.*=0;move4.y=-1;move5.*=-1;move5.y=-1;move6.*=-1;move6.y=0;move7.*=-1;move7.y=1;void printS(dataType temp)int static i=0;printf("第%d次入栈元素为:",+i);printf("(%d,%d)%dn",temp.*,temp.y,temp.d);int find_Path(int mazeM+2N+2,item move8)SeqStack*s=InitSeqStack();dataType temp;int *,y,d,i,j;temp.*=1;temp.y=1;temp.d=-1;Push(s,temp); while(!StackEmpty(s)Pop(s,&temp);*=temp.*;y=temp.y;d=temp.d+1;while(d<8)i=*+moved.*;j=y+moved.y;if(mazeij=0)temp.*=*;temp.y=y;temp.d=d;Push(s,temp);printS(temp);*=i;y=j;maze*y=-1;if(*=M && y=N)print_Path(s);return 1;elsed=0;elsed+;return 0;void print_Path(SeqStack*s)printf("迷宫路径为:n");for(int i=0;i<s->top;i+)printf("(%d,%d)%d->",s->datai.*,s->datai.y,s->datai.d);printf("(%d,%d)%dn",s->datai.*,s->datai.y,s->datai.d);void main()init_move(move);if(!find_Path(maze,move) printf("迷宫路径不存在");2.5程序执行结果总 结通过这本次课程设计，加深了我对"数据构造"这门课程知识的理解，使我更熟练掌握实践技巧。我通过这一周的时间在选题，编译调试，查阅相关文献资料，认真思考，敢于实践操作，攻克了一个个错误，完成了此次课程设计。在“一元多项式的加、减、乘法运算实现中主要使用了线性表的根本操作，使我更进一步理解线性表的顺序存储和链式存储构造，熟练线性表的插入、删除等根本功能；“迷宫问题的实现又是栈的典型实际应用，在编译调试此程序更突出了栈的特性。通过实际应用的程序编译来稳固自己数据构造的相关知识，更能加深记忆。这次课程设计，对我的程序设计和调试能力有很大的提升。这次课程设计使我深刻认识到自己专业知识的匮乏，程序设计的能力的缺乏。通过这次的课程设计也提高了我的独立思考、敢于实践操作能力，弥补了我的局部专业知识的缺乏之处。我的程序设计思想和代码的编写和调试能力在此次课设期间有所提高。这样一种更贴切实际的课程设计，更能提高我的学习效率，让我真正理解这门课程的知识要点。最后，非常感雷教师在平时以及在本次课设中给予我们的耐心的教诲与帮助。参考文献【1】数据构造C语言版 主编：严蔚敏 吴伟民【2】C程序设计 主编：谭浩强【3】数据构造C语言版例题详解与课程设计指导 主编：锋 袁志祥【4】二级C语言程序设计 主编：文辉. z.
