数据结构课程设计报告_数据结构课程设计心得

其他范文时间：2020-02-27 10:41:34 收藏本文下载本文

【www.daodoc.com - 其他范文】

数据结构课程设计报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计心得”。

《数据结构》课程设计报告

《数据结构》...................................................................................................................................1 课程设计报告...................................................................................................................................1 目录..................................................................................................................................................2 课题一：表达式求值.......................................................................................................................3 一：算数表达式后缀版...........................................................................................................31、问题描述：.................................................................................................................32、设计思路：.................................................................................................................33、程序代码：.................................................................................................................34、运行与测试.................................................................................................................65、设计心得：.................................................................................................................6 二：算术表达式中缀版...........................................................................................................71、问题描述：.................................................................................................................72、设计思路：.................................................................................................................73、代码：.........................................................................................................................74、调试及测试...............................................................................................................135、设计心得：...............................................................................................................13 课题四：迷宫求解.........................................................................................................................14 一：问题描述：.............................................................................................................14 二：设计思路：.............................................................................................................14 三：功能函数设计.........................................................................................................14 四：代码.........................................................................................................................14 五：测试及调试.............................................................................................................21 六：设计心得.................................................................................................................23 课题一：表达式求值

一：算数表达式后缀版

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);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){

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(“%dn”,z);return z;} int main(){ char A[100];int m;scanf(“%s”,A);m=match(A);printf(“%dn”,m);return 0;}

4、运行与测试

5、设计心得：考察栈的应用，在c++环境下栈的构建与操作，在输入数组A时（用于存放数组），注意当数组元素是数字时，将A[i]-’0’，（ASCII码）作为栈相应函数的参数。后缀表达式还是相应比较简单的。二：算术表达式中缀版

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();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){ 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;} 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;

}

} } B[j]='#';//B[]由j控制进程

B[++j]='';// printf(“%sn”,B);return 1;} int matchfn(char A[]){ temp s;int i=0;int n,x,y,z;n=strlen(A);//printf(“n=%dn”,n);// printf(“%sn”,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(“=%dn”,m);return 0;

4、调试及测试

5、设计心得：

中缀算法是在后缀的基础上，增加了处理，是的中缀在栈的存储中为后缀，然后只用后缀的算法运算。最容易忽略的是字符数组处理是的’‘问题，所以加上了B[j]='#';B[++j]='';在int matchcg(char A[],char B[])函数后。课题四：迷宫求解

一：问题描述：设二维数组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//限定了栈的容量//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;//初始化栈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;} } 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”);