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

. .
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数据结构设计
根据下面给出的存储结构定义：
#define MAXSIZE 20 //定义线性表最大容量
//定义多项式项数据类型
typedef struct
{
float coef; //系数
int expn; //指数
}term,elemType;

typedef struct
{
term terms[MAXSIZE]; //线性表中数组元素
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*p,term x)
//在多项式p中插入一个指数项x
int CreatePolyn(polynomial*P,int m)
//输入m项系数和指数，建立表示一元多项式的有序表p
char pare(term term1,term term2)
//比较指数项term1和指数项term2
polynomial*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)
//输出在顺序存储结构的多项式p

1.4程序源代码
#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#define NULL 0
#define MAXSIZE 20

typedef struct
{
float coef;
int expn;
}term,elemType;

typedef struct
{
term terms[MAXSIZE];
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;
}
else
{
return 1;
}
}
polynomial*Init_Polynomial()
{
polynomial*P;
P=new polynomial;
if(P!=NULL)
{
P->last=-1;
return P;
}
else
{
return NULL;
}
}
void Reset_Polynomial(polynomial*p)
{
if(PloynStatus(p)==1)
{
p->last=-1;
}
}
int Location_Element(polynomial*p,term x)
{
int i=0;
if(PloynStatus(p)==-1)
return 0;
while(i<=p->last && p->terms[i].expn!=x.expn)
{
i++;
}
if(i>p->last)
{
return 0;
}
else
{
return 1;
}
}
int Insert_ElementByOrder(polynomial*p,term x)
{
int j;
if(PloynStatus(p)==-1)
return 0;
if(p->last==MAXSIZE-1)
{
cout<<"The polym is full!"<<endl;
return 0;
}
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++;
return 1;
}
int CreatePolyn(polynomial*P,int m)
{
float coef;
int expn;
term x;
if(PloynStatus(P)==-1)
return 0;
if(m>MAXSIZE)
{
printf("顺序表溢出\n");
return 0;
}
else
{
printf("请依次输入%d对系数和指数...\n",m);
for(int i=0;i<m;i++)
{
scanf("%f%d",&coef,&expn);
x.coef=coef;
x.expn=expn;
if(!Location_Element(P,x))
{
Insert_ElementByOrder(P,x);
}
}
}
return 1;
}
char pare(term term1,term term2)
{
if(term1.expn>term2.expn)
{
return'>';
}
else if(term1.expn<term2.expn)
{
return'<';
}
else
{
return'=';
}
}
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->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++;
}
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->terms[i].coef=-p2->terms[i].coef;
p3->terms[i].expn=p2->terms[i].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;
}
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++)
{
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]);
}
}
return p3;
}
void printPloyn(polynomial*p)
{
int i;
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;
}
void menu()
{
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;
}
void main()
{
int sel;
polynomial*p1=NULL;
polynomial*p2=NULL;
polynomial*p3=NULL;
while(1)
{
menu();
cout<<"\t\t*请选择(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 x;
int y;
}item;
//定义坐标和方向
typedef struct
{
int x;
int y;
int d;
}dataType;
//定义顺序栈的类型定义
typedef struct
{
dataType data[MAXLEN];
int top;
}SeqStack;
item move[8]; //8邻域试探方向数组
int maze[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基本操作函数说明
void print_Path(SeqStack*s);
//输出迷宫路线
SeqStack*InitSeqStack()
//该函数初始化一个空栈，并返回指向该栈的存储单元首地址
int Push(SeqStack*s,dataType x)
//将元素x入栈s,若入栈成功返回结果1；否则返回0
int StackEmpty(SeqStack*s)
//该函数判断栈是否为空，若栈空返回结果1；否则返回0
int Pop(SeqStack*s,dataType*x)
//将栈顶元素出栈，放入x所指向的存储单元中，若出栈返回结果1；否则返回0
void init_move(item move[8])
//初始化8邻域方向
int find_Path(int maze[M+2][N+2],item move[8])
//在迷宫maze二维数组中按move的8邻域方向探测迷宫路线，存在返回1，否则返回0
void print_Path(SeqStack*s)
//输出栈s中所有迷宫路径

2.4程序源代码
#include<stdio.h>
#include<stdlib.h>
#define M 6
#define N 8
#define MAXLEN 100
typedef struct
{
int x;
int y;
}item;
typedef struct
{
int x;
int y;
int d;
}dataType;
typedef struct
{
dataType data[MAXLEN];
int top;
}SeqStack;
item move[8];
int maze[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},
};
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;
else
{
s->top++;
s->data[s->top]=x;
return 1;
}
}
int StackEmpty(SeqStack*s)
{
if(s->top==-1)
return 1;
else
return 0;
}
int Pop(SeqStack*s,dataType*x)
{
if(StackEmpty(s))
return 0;
else
{
*x=s->data[s->top];
s->top--;
return 1;
}
}
void init_move(item move[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;
}
void printS(dataType temp)
{
int static i=0;
printf("第%d次入栈元素为:",++i);
printf("(%d,%d)%d\n",temp.x,temp.y,temp.d);
}
int find_Path(int maze[M+2][N+2],item move[8])
{
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(d<8)
{
i=x+move[d].x;
j=y+move[d].y;
if(maze[i][j]==0)
{
temp.x=x;
temp.y=y;
temp.d=d;
Push(s,temp);
printS(temp);
x=i;
y=j;
maze[x][y]=-1;
if(x==M && y==N)
{
print_Path(s);
return 1;
}
else
d=0;
}
else
d++;
}
}
return 0;
}
void print_Path(SeqStack*s)
{
printf("迷宫路径为:\n");
for(int i=0;i<s->top;i++)
{
printf("(%d,%d)%d->",s->data[i].x,s->data[i].y,s->data[i].d);
}
printf("(%d,%d)%d\n",s->data[i].x,s->data[i].y,s->data[i].d);
}
void main()
{
init_move(move);
if(!find_Path(maze,move))
printf("迷宫路径不存在");
}

2.5程序执行结果

总 结
通过这本次课程设计，加深了我对《数据结构》这门课程知识的理解，使我更熟练掌握实践技巧。我通过这一周的时间在选题，编译调试，查阅相关文献资料，认真思考，敢于实践操作，攻克了一个个错误，完成了此次课程设计。
在“一元多项式的加、减、乘法运算实现”中主要使用了线性表的基本操作，使我更进一步理解线性表的顺序存储和链式存储结构，熟练线性表的插入、删除等基本功能；“迷宫问题的实现”又是栈的典型实际应用，在编译调试此程序更突出了栈的特性。通过实际应用的程序编译来巩固自己数据结构的相关知识，更能加深记忆。
这次课程设计，对我的程序设计和调试能力有很大的提升。这次课程设计使我深刻认识到自己专业知识的匮乏，程序设计的能力的不足。通过这次的课程设计也提高了我的独立思考、敢于实践操作能力，弥补了我的部分专业知识的不足之处。我的程序设计思想和代码的编写和调试能力在此次课设期间有所提高。这样一种更贴切实际的课程设计，更能提高我的学习效率，让我真正理解这门课程的知识要点。
最后，非常感谢雷老师在平时以及在本次课设中给予我们的耐心的教导与帮助。

参考文献
【1】数据结构（C语言版） 主编：严蔚敏 X伟民
【2】C程序设计 主编：谭浩强
【3】数据结构（C语言版）例题详解与课程设计指导 主编：秦锋 袁志祥
【4】二级C语言程序设计 主编：X文辉

. .word..