数据结构课程设计一元多项式加法减法乘法运算的实现样本

1.一元多项式加法、减法、乘法运算实现1.1设计内容及规定1)设计内容（1）使用顺序存储构造实现多项式加、减、乘运算。例如：,求和成果：（2）使用链式存储构造实现多项式加、减、乘运算，，求和成果：2）设计规定（1）用C语言编程实现上述实验内容中构造定义和算法。（2）要有main()函数，并且在main()函数中使用检测数据调用上述算法。（3）用switch语句设计如下选取式菜单。***************数据构造综合性实验***********************一、多项式加法、减法、乘法运算*****************1.多项式创立*****************2.多项式相加*****************3.多项式相减*****************4.多项式相乘*****************5.清空多项式*****************0.退出系统*****************请选取（0—5）************************************************************请选取（0-5）:1.2数据构造设计依照下面给出存储构造定义：#defineMAXSIZE20//定义线性表最大容量//定义多项式项数据类型typedefstruct{ floatcoef；//系数 intexpn；//指数}term,elemType;typedefstruct{ termterms[MAXSIZE]；//线性表中数组元素 intlast；//指向线性表中最后一种元素位置}SeqList;typedefSeqListpolynomial;1.3基本操作函数阐明polynomial*Init_Polynomial();//初始化空多项式intPloynStatus(polynomial*p)//判断多项式状态intLocation_Element(polynomial*p,termx)在多项式p中查找与x项指数相似项与否存在intInsert_ElementByOrder(polynomial*p,termx)//在多项式p中插入一种指数项xintCreatePolyn(polynomial*P,intm)//输入m项系数和指数，建立表达一元多项式有序表pcharcompare(termterm1,termterm2)//比较指数项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相乘，生成一种新多项式voidprintPloyn(polynomial*p)//输出在顺序存储构造多项式p1.4程序源代码#include<stdlib.h>#include<stdio.h>#include<iostream.h>#defineNULL0#defineMAXSIZE20typedefstruct{ floatcoef; intexpn;}term,elemType;typedefstruct{ termterms[MAXSIZE]; intlast;}SeqList;typedefSeqListpolynomial;voidprintPloyn(polynomial*p);intPloynStatus(polynomial*p){ if(p==NULL) { return-1; } elseif(p->last==-1) { return0; } else { return1; }}polynomial*Init_Polynomial(){ polynomial*P; P=newpolynomial; if(P!=NULL) { P->last=-1; returnP; } else { returnNULL; }}voidReset_Polynomial(polynomial*p){ if(PloynStatus(p)==1) { p->last=-1; }}intLocation_Element(polynomial*p,termx){ inti=0; if(PloynStatus(p)==-1) return0; while(i<=p->last&&p->terms[i].expn!=x.expn) { i++; } if(i>p->last) { return0; } else { return1; }}intInsert_ElementByOrder(polynomial*p,termx){ intj; if(PloynStatus(p)==-1) return0; if(p->last==MAXSIZE-1) { cout<<"Thepolymisfull!"<<endl; return0; } j=p->last;while(p->terms[j].expn<x.expn&&j>=0){ p->terms[j+1]=p->terms[j]; j--;}p->terms[j+1]=x; p->last++; return1;}intCreatePolyn(polynomial*P,intm){ floatcoef; intexpn; termx; if(PloynStatus(P)==-1) return0; if(m>MAXSIZE) { printf("顺序表溢出\n"); return0; } else { printf("请依次输入%d对系数和指数...\n",m); for(inti=0;i<m;i++) { scanf("%f%d",&coef,&expn); x.coef=coef; x.expn=expn; if(!Location_Element(P,x)) { Insert_ElementByOrder(P,x); } } } return1;}charcompare(termterm1,termterm2){ if(term1.expn>term2.expn) { return'>'; } elseif(term1.expn<term2.expn) { return'<'; } else { return'='; }}polynomial*addPloyn(polynomial*p1,polynomial*p2){ inti,j,k; i=0; j=0; k=0; if((PloynStatus(p1)==-1)||(PloynStatus(p2)==-1)) { returnNULL; } polynomial*p3=Init_Polynomial(); while(i<=p1->last&&j<=p2->last) { switch(compare(p1->terms[i],p2->terms[j])) { case'>': p3->terms[k++]=p1->terms[i++]; p3->last++; break; case'<': p3->terms[k++]=p2->terms[j++]; p3->last++; break; case'=': if(p1->terms[i].coef+p2->terms[j].coef!=0) { p3->terms[k].coef=p1->terms[i].coef+p2->terms[j].coef; p3->terms[k].expn=p1->terms[i].expn; k++; p3->last++; } i++; j++; } } while(i<=p1->last) { p3->terms[k++]=p1->terms[i++]; p3->last++; } returnp3;}polynomial*subStractPloyn(polynomial*p1,polynomial*p2){ inti; i=0; if((PloynStatus(p1)!=1)||(PloynStatus(p2)!=1)) { returnNULL; } polynomial*p3=Init_Polynomial(); p3->last=p2->last; for(i=0;i<=p2->last;i++) { p3->terms[i].coef=-p2->terms[i].coef; p3->terms[i].expn=p2->terms[i].expn; } p3=addPloyn(p1,p3); returnp3;}polynomial*mulitPloyn(polynomial*p1,polynomial*p2){ inti; intj; intk; i=0; if((PloynStatus(p1)!=1)||(PloynStatus(p2)!=1)) { returnNULL; } polynomial*p3=Init_Polynomial(); polynomial**p=newpolynomial*[p2->last+1]; for(i=0;i<=p2->last;i++) { for(k=0;k<=p2->last;k++) { p[k]=Init_Polynomial(); p[k]->last=p1->last; for(j=0;j<=p1->last;j++) { p[k]->terms[j].coef=p1->terms[j].coef*p2->terms[k].coef; p[k]->terms[j].expn=p1->terms[j].expn+p2->terms[k].expn; } p3=addPloyn(p3,p[k]); } } returnp3;}voidprintPloyn(polynomial*p){ inti; for(i=0;i<=p->last;i++) { if(p->terms[i].coef>0&&i>0) cout<<"+"<<p->terms[i].coef; else cout<<p->terms[i].coef; cout<<"x^"<<p->terms[i].expn; } cout<<endl;}voidmenu(){ cout<<"\t\t*******数据构造综合性实验*********"<<endl; cout<<"\t\t***一、多项式加、减、乘法运算***"<<endl; cout<<"\t\t*******1.多项式创立*********"<<endl; cout<<"\t\t*******2.多项式相加*********"<<endl; cout<<"\t\t*******3.多项式相减*********"<<endl; cout<<"\t\t*******4.多项式相乘*********"<<endl; cout<<"\t\t*******5.清空多项式*********"<<endl; cout<<"\t\t*******0.退出系统*********"<<endl; cout<<"\t\t******请选取(0-5)********"<<endl; cout<<"\t\t***********************************"<<endl;}voidmain(){ intsel; polynomial*p1=NULL; polynomial*p2=NULL; polynomial*p3=NULL; while(1) { menu(); cout<<"\t\t*请选取(0-5):"; cin>>sel; switch(sel) { case1: p1=Init_Polynomial(); p2=Init_Polynomial(); intm; 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; case2: printf("p1+p2="); if((p3=subStractPloyn(p1,p2))!=NULL) printPloyn(p3); break; case3: printf("\np1-p2="); if((p3=subStractPloyn(p1,p2))!=NULL) printPloyn(p3); break; case4: printf("\np1*p2="); if((p3=mulitPloyn(p1,p2))!=NULL) printPloyn(p3); case5: Reset_Polynomial(p1); Reset_Polynomial(p2); Reset_Polynomial(p3); break; case0: return; } } return;}1.5程序执行成果2.迷宫问题实现2.1设计内容及规定1）设计内容以一种m*n长方阵表达迷宫，0和1分别表达迷宫中通路和障碍。设计一种程序，对任意设定迷宫，求出一条从入口到出口道路，或得出没有通路结论。2)设计规定（1）用C语言编程实现上述实验内容中构造定义和算法；（2）要有main()函数，并且在main()函数中使用检测数据调用上述算法；2.2数据构造设计依照以上问题给出存储构造定义：typedefstruct//定义坐标{ intx; inty;}item;//定义坐标和方向typedefstruct{ intx; inty; intd;}dataType;//定义顺序栈类型定义typedefstruct{ dataTypedata[MAXLEN]; inttop;}SeqStack;itemmove[8]；//8邻域试探方向数组intmaze[M+2][N+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基本操作函数阐明voidprint_Path(SeqStack*s);//输出迷宫路线SeqStack*InitSeqStack()//该函数初始化一种空栈，并返回指向该栈存储单元首地址intPush(SeqStack*s,dataTypex)//将元素x入栈s,若入栈成功返回成果1；否则返回0intStackEmpty(SeqStack*s)//该函数判断栈与否为空，若栈空返回成果1；否则返回0intPop(SeqStack*s,dataType*x)//将栈顶元素出栈，放入x所指向存储单元中，若出栈返回成果1；否则返回0voidinit_move(itemmove[8])//初始化8邻域方向intfind_Path(intmaze[M+2][N+2],itemmove[8])//在迷宫maze二维数组中按move8邻域方向探测迷宫路线，存在返回1，否则返回0voidprint_Path(SeqStack*s)//输出栈s中所有迷宫途径2.4程序源代码#include<stdio.h>#include<stdlib.h>#defineM6#defineN8#defineMAXLEN100typedefstruct{ intx; inty;}item;typedefstruct{ intx; inty; intd;}dataType;typedefstruct{ dataTypedata[MAXLEN]; inttop;}SeqStack;itemmove[8];intmaze[M+2][N+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},};voidprint_Path(SeqStack*s);SeqStack*InitSeqStack(){ SeqStack*s; s=newSeqStack; s->top=-1; returns;}intPush(SeqStack*s,dataTypex){ if(s->top==MAXLEN-1) return0; else { s->top++; s->data[s->top]=x; return1; }}intStackEmpty(SeqStack*s){ if(s->top==-1) return1; else return0;}intPop(SeqStack*s,dataType*x){ if(StackEmpty(s)) return0; else { *x=s->data[s->top]; s->top--; return1; }}voidinit_move(itemmove[8]){ move[0].x=0; move[0].y=1; move[1].x=1; move[1].y=1; move[2].x=1; move[2].y=0; move[3].x=1; move[3].y=-1; move[4].x=0; move[4].y=-1; move[5].x=-1; move[5].y=-1; move[6].x=-1; move[6].y=0; move[7].x=-1; move[7].y=1;}voidprintS(dataTypetemp){ intstatici=0; printf("第%d次入栈元素为:",++i); printf("(%d,%d)%d\n",temp.x,temp.y,temp.d);}intfind_Path(intmaze[M+2][N+2],itemmove[8]){ SeqStack*s=InitSeqStack(); dataTypetemp; intx,y,d,i,j; temp.x=1; temp.y=1; temp.d=-1; Push(s,temp); while(!StackEmpty(s)) { Pop(s,&temp); x=temp.x; y=temp.y; d=temp.d+1; while(d<8) { i=x+move[d].x; j=y+move[d].y; if(maze[i][j]==0) { temp