实验三.docx
《实验三.docx》由会员分享，可在线阅读，更多相关《实验三.docx（13页珍藏版）》请在冰点文库上搜索。
实验三
实验三栈和队列
软件工程122
学号1213042037
鹿瑶
题目：
1表达式括号匹配对判断问题
2迷宫问题
3显示杨辉三角形
问题描述：
1表达式括号匹配对判断问题（栈）
2迷宫问题（栈）
3显示杨辉三角形
杨辉三角形，又称贾宪三角形，帕斯卡三角形，是二项式系数在三角形中的一种几何排列。
前提：
端点的数为1.
1、每个数等于它上方两数之和。
2、每行数字左右对称，由1开始逐渐变大。
3、第n行的数字有n项。
4、第n行数字和为
。
5、第n行的第m个数和第n-m+1个数相等，即C（n-1,m-1）=C（n-1,n-m）（组合数性质
之一）
6、每个数字等于上一行的左右两个数字之和。
可用此性质写出整个杨辉三角。
即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。
即
7、第n行的m个数可表示为C（n-1,m-1）（n-1下标，m-1上标），即为从n-1个不同
元素中取m-1个元素的组合数。
（见右图）
组合数计算方法：
C（n,m）=n!
/[m!
（n-m）!
]
8、（a+b）^n的展开式中的各项系数依次对应杨辉三角的第（n+1）行中的每一项。
[1]
9、将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第4n+1个斐波那契数；将第2n行第2个数（n>1），跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。
10、将各行数字相排列，可得11的N-1次方：
1=11^0;11=11^1;121=11^2……;
数据结构设计：
1.利用一个栈st进行判定，将“（”、“【”或“{”进栈，当遇到“）”、“】”或“}”时，检查当前栈顶元素是否是相对应的“（”、“【”或“{”，若是则退栈，否则返回表示不配对。
当整个算术表达式检查完毕时栈为空，表示括号正确配对；否则不配对。
运行与测试：
1表达式括号匹配对判断问题
2迷宫问题
2.显示杨辉三角形
总结与心得：
明白栈和队列的定义与功能，分析问题所需要何种结构，最终解决问题。
源程序：
1.表达式括号匹配对判断问题
#include
usingnamespacestd;
#defineMaxSize100//MaxSize为算术表达式中最大字符个数
voidcorrect（charexp[],int&tag）//tag为引用型参量
{
charst[MaxSize];
inttop=-1,i=0;
tag=1;
while（exp[i]!
='\0\'&&tag）
）{
if（exp[i]=='（'||exp[i]=='['||exp[i]=='{'）
{
top++;//遇到‘（’，‘【’或‘{’，则将其进栈
st[top]=exp[i];
}
if（exp[i]=='）'）//遇到‘）’，若栈顶是‘（’，则继续处理，否则以不配对返回
if（st[top]=='（'）
top--;
else
tag=0;
if（exp[i]==']'）//遇到‘】’，若栈顶是‘【’，则继续处理，否则以不配对返回
if（st[top]='['）
top--;
else
tag=0;
if（exp[i]=='}'）//遇到‘}’，若栈顶是‘{’，则继续处理，否则以不配对返回
if（st[top]='{'）
top--;
else
tag=0;
i++;
}
if（top!
=-1）//若栈不空，则不配对
tag=0;
}
intmain（void）
{
charexp[]="{5+[3-（4*7）]}";
intt;
correct（exp,t）;
if（t）
cout<else
cout<return0;
}
2.迷宫问题
栈代码：
/************************************************************************/
/*自定义栈*/
/*通过自定义的简单栈以满足迷宫求解*/
/*功能：
push（）将元素加入栈中*/
/*pop（）退栈；topValue（）获得栈顶元素*/
/*clear（）清除栈length（）获得栈中元素个数*/
/************************************************************************/
#include
#include
usingnamespacestd;
templateclassPathStack:
publicstack
{
private:
intsize;
inttop;
Elem*listArray;
public:
PathStack（intsz=DefaultListSize）{
size=sz;
top=0;
listArray=newElem[sz];
}
~PathStack（）{delete[]listArray;}
voidclear（）{top=0;}
/****向栈中加入元素****/
boolpush（constElem&item）;
/***********退栈**********/
Elempop（）;
/********获得栈顶元素*******/
ElemtopValue（）const;
intlength（）const{returntop;}
};
template
boolPathStack:
:
push（constElem&item）{
if（top==size）returnfalse;
listArray[top++]=item;
returntrue;
}
template
ElemPathStack:
:
pop（）{
Elemit;
if（top==0）returnit;
it=listArray[--top];
returnit;
}
template
ElemPathStack:
:
topValue（）const{
Elemit;
if（top==0）returnit;
it=listArray[top-1];
returnit;
}
CPP代码：
//迷宫求解的方法类
//功能：
通过findPath（）方法实现对路径的查找
//通过printPath（）方法将路径打印出来
#include"PathStack.h"
#include
usingnamespacestd;
classMazeSolveMethod
{
private:
staticintmaze[10][10];//存放迷宫数据
PathStackpathStack;//定义栈
public:
MazeSolveMethod（）:
pathStack（100）{
}
~MazeSolveMethod（）{}
voidfindPath（intstartX,intstartY）;
voidprintPath（）const;
};
intMazeSolveMethod:
:
maze[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,0,0,0,1},
{1,0,0,0,1,0,1,0,0,1},
{1,0,1,0,0,0,1,1,0,1},
{1,0,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,1,1,1,0,0,0,1,1},
{1,1,1,1,1,1,1,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
voidMazeSolveMethod:
:
findPath（intstartX,intstartY）{
intx=startX;
inty=startY;
pathStack.push（x）;
pathStack.push（y）;
maze[x][y]=2;
cout<<"进入方法！
"<while（true）{
if（maze[x-1][y]==0）{
pathStack.push（--x）;
pathStack.push（y）;
maze[x][y]=2;
}elseif（maze[x][y-1]==0）{
pathStack.push（x）;
pathStack.push（--y）;
maze[x][y]=2;
}elseif（maze[x][y+1]==0）{
pathStack.push（x）;
pathStack.push（++y）;
maze[x][y]=2;
}elseif（maze[x+1][y]==0）{
pathStack.push（++x）;
pathStack.push（y）;
maze[x][y]=2;
}
if（maze[x-1][y]!
=0&&maze[x][y+1]!
=0&&maze[x+1][y]!
=0&&maze[x][y-1]!
=0）{
if（x>=8&&y>=8）{
break;
}else{
maze[x][y]=3;
y=pathStack.pop（）;
x=pathStack.pop（）;
}
y=pathStack.topValue（）;
inttemp=pathStack.pop（）;
x=pathStack.topValue（）;
pathStack.push（temp）;
}
}
}
voidMazeSolveMethod:
:
printPath（）const{
cout<<"printPath"<for（inti=0;i<10;i++）{
for（intj=0;j<10;j++）{
if（maze[i][j]==2）
cout<<'*'<<"";
elseif（maze[i][j]==3）
cout<<0<<"";
else
cout<<1<<"";
}
cout<}
}
主函数代码：
/************************************************************************/
/*迷宫求解----栈方法实现*/
//功能：
通过对栈实现迷宫算法求解
//Author：
Andrew
//Date：
2012-10-20
/************************************************************************/
#include"MazeSolveMethod.h"
#include
usingstd:
:
cout;
usingstd:
:
endl;
intmain（）{
MazeSolveMethodsolve;
solve.findPath（1,1）;
solve.printPath（）;
system（"pause"）;
return0;
}
3.显示杨辉三角形
#include
#include
usingnamespacestd;
ints=0,t=0,rst,j;
dequeque;
voidmain（）
{
que.push_back
（1）;
for（inti=1;i<10;i++）
{
cout<que.push_back（0）;
for（j=0;j{
rst=que.front（）;
que.pop_front（）;
t=rst;
if（rst>0）
cout<que.push_back（s+t）;
s=t;
}
}
}
升级会员 