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

1、.1. 一元多项式加法、减法、乘法运算的实现1.1 设计内容及要求1) 设计内容（ 1）使用顺序存储结构实现多项式加、减、乘运算。例如：f ( x) 8x 65x510x432 x 2x10 , g( x)7x 510 x420 x310x 2x求和结果：()()8 612520x322210f xg xxxx（ 2）使用链式存储结构实现多项式加、减、乘运算，f ( x) 100x1005x5030x1010 ， g ( x)150x905x 5040 x2020x103x求和结果： f (x)g( x)100x100150x9040 x 2010x103x 102）设计要求（ 1）用 C 语

2、言编程实现上述实验内容中的结构定义和算法。（ 2）要有 main() 函数，并且在 main() 函数中使用检测数据调用上述算法。（ 3）用 switch 语句设计如下选择式菜单。*数据结构综合性实验 *一、多项式的加法、减法、乘法运算 *1.多项式创建*2.多项式相加*3.多项式相减*4.多项式相乘*5.清空多项式*0.退出系统*请选择（ 0 5）* 请选择（ 0-5 ） :1.2 数据结构设计根据下面给出的存储结构定义：.#define MAXSIZE 20/定义线性表最大容量/定义多项式项数据类型typedef structfloat coef;/系数int expn;/指数term,e

3、lemType;typedef structterm termsMAXSIZE;/线性表中数组元素int last;/指向线性表中最后一个元素位置SeqList;typedef SeqList polynomial;1.3 基本操作函数说明polynomial*Init_Polynomial();/ 初始化空的多项式int PloynStatus(polynomial*p)/ 判断多项式的状态int Location_Element(polynomial*p,term x)在多项式 p 中查找与 x 项指数相同的项是否存在int Insert_ElementByOrder(polynomial

4、*p,term x)/ 在多项式 p 中插入一个指数项 x int CreatePolyn(polynomial*P,int m)/ 输入 m项系数和指数，建立表示一元多项式的有序表 p char compare(term term1,term term2)/ 比较指数项 term1 和指数项 term2 polynomial*addPloyn(polynomial*p1,polynomial*p2)./ 将多项式 p1 和多项式 p2 相加，生成一个新的多项式polynomial*subStractPloyn(polynomial*p1,polynomial*p2)/ 多项式 p1 和多项式

5、 p2 相减，生成一个新的多项式polynomial*mulitPloyn(polynomial*p1,polynomial*p2)/ 多项式 p1 和多项式 p2 相乘，生成一个新的多项式void printPloyn(polynomial*p)/ 输出在顺序存储结构的多项式 p1.4 程序源代码#include#include#include#define NULL 0#define MAXSIZE 20typedef structfloat coef;int expn;term,elemType;typedef structterm termsMAXSIZE;int last;SeqLi

6、st;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(PloynSta

7、tus(p)=1)p-last=-1;int Location_Element(polynomial*p,term x)int i=0;if(PloynStatus(p)=-1)return 0;while(ilast & p-termsi.expn!=x.expn)i+;if(ip-last)return 0;elsereturn 1;.int Insert_ElementByOrder(polynomial*p,term x)int j;if(PloynStatus(p)=-1)return 0;if(p-last=MAXSIZE-1)coutThe polym is full!last;

8、while(p-termsj.expn=0)p-termsj+1=p-termsj;j-;p-termsj+1=x;p-last+;return 1;int CreatePolyn(polynomial*P,int m)float coef;int expn;term x;if(PloynStatus(P)=-1)return 0;if(mMAXSIZE)printf(顺序表溢出 n);return 0;elseprintf(请依次输入 %d对系数和指数 .n,m);for(int i=0;iterm2.expn)return;else if(term1.expnterm2.expn)retu

9、rn;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(ilast & jlast)switch(compare(p1-termsi,p2-termsj)case:p3-termsk+=p1-termsi+;p3-last+;break;casetermsk+=p2-termsj+;p3-last+

10、;break;case=:if(p1-termsi.coef+p2-termsj.coef!=0).p3-termsk.coef=p1-termsi.coef+p2-termsj.coef;p3-termsk.expn=p1-termsi.expn;k+;p3-last+;i+;j+;while(ilast)p3-termsk+=p1-termsi+;p3-last+;return p3;polynomial*subStractPloyn(polynomial*p1,polynomial*p2)int i;i=0;if(PloynStatus(p1)!=1)|(PloynStatus(p2)!

11、=1)return NULL;polynomial*p3=Init_Polynomial();p3-last=p2-last;for(i=0;ilast;i+)p3-termsi.coef=-p2-termsi.coef;p3-termsi.expn=p2-termsi.expn;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;.po

12、lynomial*p3=Init_Polynomial();polynomial*p=new polynomial*p2-last+1;for(i=0;ilast;i+)for(k=0;klast;k+)pk=Init_Polynomial();pk-last=p1-last;for(j=0;jlast;j+)pk-termsj.coef=p1-termsj.coef*p2-termsk.coef;pk-termsj.expn=p1-termsj.expn+p2-termsk.expn;p3=addPloyn(p3,pk);return p3;void printPloyn(polynomia

13、l*p)int i;for(i=0;ilast;i+)if(p-termsi.coef0 & i0)cout+termsi.coef;elsecouttermsi.coef;coutxtermsi.expn;coutendl;void menu()couttt*数据结构综合性实验 *endl;couttt*一、多项式的加、减、乘法运算 *endl;couttt*1.多项式创建*endl;couttt*2.多项式相加*endl;couttt*3.多项式相减*endl;couttt*4.多项式相乘*endl;couttt*5.清空多项式*endl;couttt*0.退出系统*endl;couttt

14、*请选择 (0-5)*endl;.couttt*endl;void main()int sel;polynomial*p1=NULL;polynomial*p2=NULL;polynomial*p3=NULL;while(1)menu();coutsel;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(请输入第二个多

15、项式的项数: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)printPlo

16、yn(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() 函数中使用检测数据调用上述

17、算法；2.2 数据结构设计根据以上问题给出存储结构定义：typedef struct/定义坐标int x;int y;item;/ 定义坐标和方向typedef structint x;int y;int d;dataType;/ 定义顺序栈的类型定义typedef structdataType dataMAXLEN;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

18、,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 x)/ 将元素 x 入栈 s, 若入栈成功返回结果 1；否则返回 0 int StackEmpty(SeqStack*s)/ 该函数

19、判断栈是否为空，若栈空返回结果 1；否则返回 0 int Pop(SeqStack*s,dataType*x)/ 将栈顶元素出栈，放入x 所指向的存储单元中，若出栈返回结果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#include#define M 6#d

20、efine N 8#define MAXLEN 100typedef structint x;int y;item;typedef structint x;int y;int d;dataType;typedef structdataType dataMAXLEN;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,

21、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 x)if(s-top=MAXLEN-1)return 0;elses-top+;s-datas-top=x;return 1;int StackEmpty(SeqStack*s)if(s-top=-1)return 1;elsereturn 0;int Pop(SeqStac

22、k*s,dataType*x)if(StackEmpty(s)return 0;else*x=s-datas-top;s-top-;return 1;void init_move(item move8)move0.x=0;move0.y=1;move1.x=1;move1.y=1;move2.x=1;move2.y=0;move3.x=1;move3.y=-1;move4.x=0;move4.y=-1;.move5.x=-1;move5.y=-1;move6.x=-1;move6.y=0;move7.x=-1;move7.y=1;void printS(dataType temp)int st

23、atic i=0;printf(第%d次入栈元素为 :,+i);printf(%d,%d)%dn,temp.x,temp.y,temp.d);int find_Path(int mazeM+2N+2,item move8)SeqStack*s=InitSeqStack();dataType temp;int x,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(d8)i=x+moved.x;j=y+moved.y;if(mazeij=0)temp.x=x;temp.y=y;temp.d=d;Push(s,temp);printS(temp);x=i;y=j;mazexy=-1;if(x=M & y=N).print_Path(s);return 1;elsed=0;elsed+;return 0;void print_Path(SeqStack*s)p