《数据结构》 课程设计报告
1
目录
《数据结构》 ...................................................................................................................................1 课程设计报告 ...................................................................................................................................1 目录 ..................................................................................................................................................2 课题一：表达式求值 .......................................................................................................................3 一：算数表达式后缀版 ...........................................................................................................3
1、问题描述： .................................................................................................................3
2、设计思路： .................................................................................................................3
3、程序代码： .................................................................................................................3
4、运行与测试 .................................................................................................................6
5、设计心得： .................................................................................................................6 二：算术表达式中缀版 ...........................................................................................................7
1、问题描述： .................................................................................................................7
2、设计思路： .................................................................................................................7
3、代码： .........................................................................................................................7
4、调试及测试 ...............................................................................................................13
5、设计心得： ...............................................................................................................13 课题四：迷宫求解 .........................................................................................................................14 一：问题描述： .............................................................................................................14 二：设计思路： .............................................................................................................14 三：功能函数设计 .........................................................................................................14 四：代码 .........................................................................................................................14 五：测试及调试 .............................................................................................................21 六：设计心得 .................................................................................................................23
2 课题一：表达式求值
一：算数表达式后缀版
1、问题描述：一个算术表达式是由操作数、运算符和界线符组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界线符有左右括号和表达式起始、结束符“#”，如：“1285-*+42/-#”。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
2、设计思路：在C++环境下，用字符数组A，保存算数式，一“#”表示结束。用栈对数字和运算符号进行操作。当扫描A不是‘#’时，判断数组成员是数字还是字符，若数字，则将数字的ASCII码入栈，若不是，则弹出两个数字，并根据字符进行相应的运算，并将结果入栈保存，以便下一次的运算操作。
3、程序代码：
#include using namespace std; cla stack { private: int *base; int *top; public: int size; int empty_stack(); int push_stack(int e); int pop_stack(int &e);
3 int get_stack(int &e); stack(int Size=100) {
base=new int[Size];
top=base;
size=Size; }; ~stack() {
delete[] base;
base=NULL;
top=NULL; }; }; int stack::empty_stack() { return ((top==base)); } int stack::push_stack(int e) { if(top-base
*top=e;
top++;
return 1; } else
return 0; } int stack::pop_stack(int &e) { if(top>base) {
top--;
e=*top;
return 1; } else
return 0; } int stack::get_stack(int &e) { if(top>base) {
4
e=*(top-1);
return 1; } else
return 0; } int match(char A[]) { stack s; int i=0,x,y,z; while(A[i]!=\'#\') {
while(A[i]>\'0\'&&A[i]
{
s.push_stack(A[i]-\'0\');//存储 数字0~9 char-char
i++;
}
if(A[i]\'9\')
{
s.pop_stack(x);
s.pop_stack(y);
switch(A[i])
{
case \'+\':s.push_stack(x+y);break;//switch,case \'ch\'的用法
case \'-\':s.push_stack(x-y);break;
case \'*\':s.push_stack(x*y);break;
case \'/\':s.push_stack(x/y);break;
}
}
i++; } s.pop_stack(z); printf(\"%d\\n\",z); return z; } int main() { char A[100]; int m; scanf(\"%s\",A); m=match(A); printf(\"%d\\n\",m); return 0; }
5
4、运行与测试
5、设计心得：考察栈的应用，在c++环境下栈的构建与操作，在输入数组A时（用于存放数组），注意当数组元素是数字时，将A[i]-’0’，（ASCII码）作为栈相应函数的参数。后缀表达式还是相应比较简单的。
6 二：算术表达式中缀版
1、问题描述：一个算术表达式是由操作数、运算符和界线符组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界线符有左右括号和表达式起始、结束符“#”，如：“1285-*+42/-#”。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
2、设计思路：在C++环境下，在后缀表达式的基础上，增加将中缀转换为后缀存储的算法。自左向右扫描表达式，当扫描到的是操作数时直接输出，扫描到运算符时不能马上输出，因为后面可能还有更高的运算；若运算符栈栈顶字符比这个字符低，则入栈，继续向后处理；若高，则从运算符栈出栈一个运算符输出，继续处理当前字符；若相等，则为括号，从栈中出栈，继续向后处理，直到遇到字符’#‘，求值结束。例如：“1+2*（8-5）-4/2#”。
3、代码：
#include using namespace std; #include cla stack { private: int *base; int *top; public: int size; int empty_stack();
7 int push_stack(char e); int pop_stack(char &e); int get_stack(char &e); stack(int Size=100) {
base=new int[Size];
top=base;
size=Size; }; ~stack() {
delete[] base;
base=NULL;
top=NULL; }; }; int stack::empty_stack() { return ((top==base)); } int stack::push_stack(char e) { if(top-base
*top=e;
top++;
return 1; } else
return 0; } int stack::pop_stack(char &e) { if(top>base) {
top--;
e=*top;
return 1; } else
return 0; } int stack::get_stack(char &e) {
8 if(top>base) {
e=*(top-1);
return 1; } else
return 0; } cla temp { private: int *base; int *top; public: int size; int empty_temp(); int push_temp(int e); int pop_temp(int &e); int get_temp(int &e); temp(int Size=100) {
base=new int[Size];
top=base;
size=Size; }; ~temp() {
delete[] base;
base=NULL;
top=NULL;
}; }; int temp::empty_temp() { return ((top==base)); } int temp::push_temp(int e) { if(top-base
*top=e;
top++;
return 1; }
9 else
return 0; } int temp::pop_temp(int &e) { if(top>base) {
top--;
e=*top;
return 1; } else
return 0; } int temp::get_temp(int &e) { if(top>base) {
e=*(top-1);
return 1; } else
return 0; } char fhcg(char a,char b)//#不能传进a { int i,j; char h; char CH[7]={\'+\',\'-\',\'*\',\'/\',\'(\',\')\',\'#\'}; char R[7][7]={{\'>\',\'>\',\'\',\'>\'},
{\'>\',\'>\',\'\',\'>\'},
{\'>\',\'>\',\'>\',\'>\',\'\',\'>\'},
{\'>\',\'>\',\'>\',\'>\',\'\',\'>\'},
{\'
{\'>\',\'>\',\'>\',\'>\',\'/\',\'>\',\'>\'},
{\'
if(CH[i]==a)
break; } for(j=0;j
if(CH[j]==b)
break; } h=R[i][j]; return (h); } int matchcg(char A[],char B[])// { stack s; char h,x,y; int i,j; i=0;j=0; s.push_stack(\'#\');//#没传入 // s.get_stack(y); //cout
while(!s.empty_stack())//最后的-4/2有问题，/没进入B[j] {
if(A[i]>\'0\'&&A[i]
{
B[j]=A[i];
j++;
i++;
}
else//(A[i]\'9\')
{
s.get_stack(y);
// s.pop_stack(x);//
h=fhcg(y,A[i]);//
switch(h)
{
case \'>\':
{
s.pop_stack(x);
B[j++]=x;//x没有下移，还是‘-’只有这一步把数据压入B，j++
break;///////////
}
case \'
case \'=\':s.pop_stack(x);i++;break;
default:
return 0;
}
} }
11 B[j]=\'#\';//B[]由j控制进程
B[++j]=\'\\0\'; // printf(\"%s\\n\",B); return 1; } int matchfn(char A[]) { temp s; int i=0; int n,x,y,z; n=strlen(A); //printf(\"n=%d\\n\",n); // printf(\"%s\\n\",A); while(A[i]!=\'\\#\')//!!!!!!!!! {
if(A[i]>\'0\'&&A[i]
{
s.push_temp(A[i]-\'0\');//存储 数字0~9 char-char
i++;
}
else//(A[i]\'9\')
{
s.pop_temp(x);
s.pop_temp(y);
switch(A[i])
{
case \'+\':s.push_temp(y+x);break;//switch,case \'ch\'的用法
case \'-\':s.push_temp(y-x);break;
case \'*\':s.push_temp(x*y);break;
case \'/\':s.push_temp(y/x);break;
}
i++;
}
} s.pop_temp(z); return z; } int main() { //char A[100]={\"1+2*(8-5)-4/2#\"}; char A[100]; printf(\"A[]=以#结束:\"); scanf(\"%s\",A);
} char B[100]; int m,n,i=0; m=matchcg(A,B); m=matchfn(B); printf(\"%s\",A); printf(\"=%d\\n\",m); return 0;
4、调试及测试
5、设计心得：
中缀算法是在后缀的基础上，增加了处理，是的中缀在栈的存储中为后缀，然后只用后缀的算法运算。最容易忽略的是字符数组处理是的’\\0‘问题，所以加上了B[j]=\'#\';B[++j]=\'\\0\';在int matchcg(char A[],char B[])函数后。
13 课题四：迷宫求解
一：问题描述：设二维数组maze[m][n]为’0‘，表示此路可通,为’1‘表示此路不通.入口是maze[1][1]出口为maze[m][n]且maze[1][1]=0, maze[m][n]=0.编写寻找从入口到出口的一条路径的程序。必须沿4个方向搜索.二：设计思路：回溯法，从入口出发，按某一方向探索，若能走通并未走过（maze[i][j]==0），即该处可以到达，并标记为已走过（maze[i][j]=-1），并入栈保存前一步到达的位置，否则探索下一个方向（d++）；若所有的方向均没有通路，则按原路返回前一步到达的位置，换下一个方向继续探索，直到找到一条同路。
三：功能函数设计
typedef struct _Befor//前一点的坐标方向 typedef struct//链栈
void play(Befor temp)//temp void play(Befor temp)//temp用于实现在DOS下的界面显示
typedef struct MOVE和typedef struct _Path//用于计算四个方向的位移量
int Export(int (*maze)[10],int x0,int y0,int m,int n,PStack s)//用于探索迷宫寻找出路
四：代码
//用c表示栈
//改进，加入动态演示（子弹打飞机）
//最重大的错误，ij的位置反了，i是行，对应的是y坐标；j是列，对应的是x坐标。 #include #include #include #include #include #include #include #include #include const int True = 1; const int False = 0; #define MAX 15//限定了栈的容量
14 //system(\"cls\"); #define Up
0x48 #define Down 0x50 #define Left 0x4b #define Right 0x4d #define Esc
0x1b void gotoxy(int x, int y) //光标移到（x,y）friend函数（COORD,HANDLE）屏幕宽80、高25 {
COORD point; // 创建光标位置坐标。COORD类（x,y）
HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);// 控制台屏幕缓冲区的把手。HANDLE类
point.X = x; point.Y = y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),point); //设置控制台光标位置 }
void clear(int left,int top,int width,int higth)//!!!!! {
//函数消除轨迹
gotoxy(left,top); for(int i=0;i
for(int j=0;j
{
gotoxy(left+i,top+j);
cout
} } void sound(DWORD freq) //按freq HZ频率发声 （50ms） { Beep(freq,50); } void delay(DWORD dur)//延时dur毫秒 {
Sleep(dur); } //////正文
typedef struct _Befor { int x,y,d; }Befor;//前一点的坐标方向 typedef struct//链栈 { int top; Befor Node[100];//结构体每一个都是Befor型 }Stack,*PStack; //初始化栈
15 PStack Inite_Stack() { PStack s; s=(PStack)malloc(sizeof(Stack)); if(s) {
s->top=-1; } return s; } int empty_Stack(PStack s) { return(s->top==-1);//s.top==0即为空 } int push_Stack(PStack s,Befor temp) { if(s->top==MAX-1)//限定了栈的容量
return 0; else {
s->top++;
s->Node[s->top]=temp;
return 1; } } int pop_Stack(PStack s,Befor &temp) { if(empty_Stack(s))
return 0; else {
temp=s->Node[s->top];
s->top--;
return 1; } } int get_Stack(PStack s,Befor &temp) { if(empty_Stack(s)) return 0; else {
temp=s->Node[s->top];
return 1;
16 } } void play(Befor temp)//temp { delay(500); clear(20+temp.y+temp.y*3,5+temp.x+temp.x*3,1,1); gotoxy(20+temp.y+temp.y*3,5+temp.x+temp.x*3); printf(\"$\"); } ////////////////////////////////////////栈完成
//迷宫点的设计，保存的坐标，保存前一点的坐标（方向），此点的四个方向坐标 //加入难度，也就是迷宫复杂化，1出现在中间区域。 /*typedef struct _Befor { int x,y,d; }Befor;//前一点的坐标方向*/ typedef struct MOVE { int dx,dy; }move; typedef struct _Path {
move x,y; }Path; int Export(int (*maze)[10],int x0,int y0,int m,int n,PStack s)//二维数组做实参形参 {//(x0,y0)起始点,(m,n)将要到达的点
Befor temp; int i,j,x,y,d; struct MOVE move[4]; move[0].dx=-1;//位置错误。向上i-1;向左j+1;向下i+1;向左j-1;!!!!!!!!!!!!!! move[0].dy=0; move[1].dx=0; move[1].dy=1; move[2].dx=1; move[2].dy=0; move[3].dx=0; move[3].dy=-1; //栈初始化temp(x,y,d),入栈
temp.x=x0; temp.y=y0; temp.d=-1; push_Stack(s,temp); while(!empty_Stack(s)) {
pop_Stack(s,temp);//出栈，存储为之前的点 x=temp.x; y=temp.y; d=temp.d+1; while(d
i=x+move[d].dx;//一直是1 j=y+move[d].dy;//当前点坐标y值不对，一直增长
if(maze[i][j]==0)//当前的可走 改变了，maze[i][j]没变
{
temp.x=x;
temp.y=y;
temp.d=d;
push_Stack(s,temp);//入栈保存
//加入动态（temp）
play(temp);//
x=i;
y=j;
maze[x][y]=-1;//记录当前点已走过
if(x==m&&j==n)//已走出则输出路径
{
temp.x=x;
temp.y=y;
temp.d=d;
push_Stack(s,temp);//入栈保存最后一个点，出口点/////////////////////
//加入动态（temp）
play(temp);/////////////
gotoxy(0,2);
while(!empty_Stack(s))
{
pop_Stack(s,temp);/////////////////////////
printf(\"(%d,%d,%d)\\t\",temp.x,temp.y,temp.d);//没有改变!!!!! 正确
}
for(i=x0;i
for(j=y0;j
{
if(maze[i][j]==-1)
maze[i][j]=0;
}
return 1;//已成功
}
else
d=0;
}
else
d++;
} } //空栈后，恢复迷宫
for(i=x0;i
for(j=y0;j
{
if(maze[i][j]==-1)
maze[i][j]=0;
}
return 0;//失败 } //迷宫的初始化maze[m+2][n+2] int main() { int maze[10][10]; int m,n,i=0,j=0; char c_0; int nx,ny; PStack s=Inite_Stack(); printf(\"迷宫的规格：\"); scanf(\"%d%d\",&m,&n); gotoxy(20,5);//通过键盘控制迷宫中间区域
for(i=0;i
for(j=0;j
{
maze[i][j]=1;
gotoxy(20+i+3*i,5+j+3*j);
printf(\"1\");
} for(i=1;i
for(j=1;j
{
maze[i][j]=0;
gotoxy(20+i+3*i,5+j+3*j);
printf(\"0\");
} gotoxy(3,0); printf(\"请修改迷宫，增加难度。\\n\"); printf(\"输入0为此位置可行，输入1为此位置不可行。请不要修改外部。\\n\");
} printf(\"向上;向左;向右；向下\\n\"); nx=20;ny=5; gotoxy(20,5); c_0=getch(); while(c_0!=\'q\')//增加改错了，改为0的选项 { switch(c_0) { case Esc:break; case Up:ny--;
gotoxy(nx,ny);
break; case Left:nx--;
gotoxy(nx,ny);
break; case Down:ny++;
gotoxy(nx,ny);
break; case Right:nx++;
gotoxy(nx,ny);
break; case \'1\':j=(nx-20)/4;
i=(ny-5)/4;
maze[i][j]=1;//
delay(100);
clear(nx,ny,1,1);
gotoxy(nx,ny);
printf(\"%d\",maze[i][j]);//
break; case \'0\':j=(nx-20)/4;
i=(ny-5)/4;
maze[i][j]=0;//
delay(100);
clear(nx,ny,1,1);
gotoxy(nx,ny);
printf(\"%d\",maze[i][j]);//
break;
} c_0=getch(); } Export(maze,1,1,m,n,s); return 0; 20 五：测试及调试
1、初始化迷宫及操作提示
2、增加难度修改迷宫
21
3、运行结果 22
六：设计心得
1、最麻烦的是几个结构体之间的关联，比如“typedef struct//链栈中{Befor Node[100];}//结构体每一个都是Befor型”；“typedef struct _Path// {move x,y;}”move类型的变量x，y。
2、还有四个位移的变化（move[d].dx,move[d].dy）他的变化是与i,j的位置的变化相关的。
3、迷宫的探索中，一但按某一方向探索，若能走通并未走过（maze[i][j]==0），即该处可以到达，并标记为已走过（maze[i][j]=-1），并入栈保存前一步到达的位置，这是值得注意的，因为可能返回，要保存前面的位置。
4、界面的设计以及增加迷宫复杂性时，更改迷宫位置是的处理，也是要注意的。
23
