实验数组的表示及其应用Word文档格式.docx
- 文档编号:6890519
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:23
- 大小:73.65KB
实验数组的表示及其应用Word文档格式.docx
《实验数组的表示及其应用Word文档格式.docx》由会员分享,可在线阅读,更多相关《实验数组的表示及其应用Word文档格式.docx(23页珍藏版)》请在冰点文库上搜索。
2.实验方案设计完整,数据结构、算法选择合理
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
实验实现(25%)
1.代码编写规范、风格统一、注释清楚易读
2.程序运行正常,测试结果正确
15
3.界面友好、易于操作、有较强的容错性
实验报告撰写(10%)
1.内容详实无缺漏,文字流畅、图表清楚
2.实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考
个人工作量(30%)
1.个人完成工作量
2.个人技术水平
10
3.团队合作精神
实验运作(10%)
1.有一定用户群
2.应用前景分析
综合得分:
(满分100分)
指导教师:
年月日
20131120272姓名:
邓飞武本人承担角色:
结果检验,实验构思,调试代码
20131120247姓名:
温岩松本人承担角色:
错误总结,结果验证,调试代码
20131120258姓名:
程哲本人承担角色:
调试代码,错误总结,实验分析
(下面的内容由学生填写,格式统一为,字体:
楷体,行距:
固定行距18,字号:
小四,个人报告按下面每一项的百分比打分。
难度A满分70分,难度B满分90分)
一、【实验构思(Conceive)】
(10%)
(本部分应包括:
描述实验实现的基本思路,包括所用到的离散数学、工程数学、程序设计、算法等相关知识)
程序设计:
利用数组来实现迷宫的设计
数学知识:
运用到了相关的矩阵知识,以及二维数组的知识
二、【实验设计(Design)】
(20%)
抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系)
数据部分包括Point(迷宫中点位置的存储结构),而操作包括CreatMaze(获取迷宫),FindMaze(寻找迷宫maze中从(,)到(m,n)的路径),PrintPath(输出迷宫的路径)
具体为:
1.Point
classPoint//迷宫中点位置的存储结构
{
public:
intx;
//x代表当前位置的行坐标
inty;
//y代表当前位置的列坐标
intdir;
//0:
无效,1:
下,2:
右,3:
上,4:
左
};
2.CreatMaze
定义二维指针存取迷宫
输入迷宫的长和宽
输入迷宫的内容,0代表可通,1代表不通
返回存贮迷宫的二维指针maze
3.FindMaze
将入口位置入栈
获取栈顶元素
如果有新位置入栈,则把上一个探索的位置存入栈p
探索当前位置的相邻位置
判断新位置是否可达
4.PrintPath
定义一个栈,按从入口到出口存取路径
取栈p的顶点元素,即第一个位置
第一个位置入栈t
栈p非空,则反复转移
获取下一个位置
把新位置入栈
输出路径,包括行坐标,列坐标,下一个位置方向
三、【实现描述(Implement)】
(30%)
抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系,关键的程序流程图等,给出关键算法的时间复杂度分析。
)
1.抽象数据类型具体实现的函数原型说明:
2.子程序算法简介
int**CreatMaze(int&
m,int&
n);
//获取迷宫
boolFindMaze(int**maze,intm,intn);
//寻找迷宫maze中从(,)到(m,n)的路径
voidPrintPath(Stackp);
//输出迷宫的路径
四、【测试结果(Testing)】
对实验的测试结果,应具体列出每次测试所输入的数据以及输出的数据,并对测试结果进行分析总结)
1.程序功能选择界面:
2.选择后:
3.进行数据输入后的结果:
4.再次输入数据:
四、【实验总结】
自己在实验中完成的任务,注意组内的任意一位同学都必须独立完成至少一项接口的实现;
对所完成实验的经验总结、心得)
蔡智霖:
迷宫求解的算法并没有一开始想的那么难,但也需要一步一步小心的把它完成,才能避免在小细节上出错,同时这次的实验堆我们在矩阵上的了解有一定考察。
在本次试验中,也运用到了栈来进行迷宫的存储。
总之,在本次试验中,我们学到了很多,多今后在矩阵的运用有了一个全新的了解。
邓飞武:
在做实验前,一定要将课本上的知识吃透,因为这是做实验的基础,否则,在老师讲解时就会听不懂,这将使你在做实验时的难度加大,浪费做实验的宝贵时间.
温岩松:
通过这次实验,使我学到了不少实用的知识,更重要的是,做实验的过程,思考问题的方法,这与做其他的实验是通用的,真正使我们受益匪浅.
程哲:
在这次实验中,我学到很多东西,加强了我的动手能力,并且培养了我的独立思考能力。
特别是在做实验报告时,因为在做数据处理时出现很多问题,如果不解决的话,将会很难的继续下去。
五、【项目运作描述(Operate)】
项目的成本效益分析,应用效果等的分析。
本程序可以实现基本的迷宫求解功能,可以根据使用者所输入的迷宫来判断是否有同路,以及同路路径。
因为本程序并不具备可视化的运行界面,因此本程序并不具备较高的成本价值,但同时也因为本程序制作成本并不高,因此其效益相对来说尚可。
六、【代码】
完整的代码及充分的注释。
注意纸质的实验报告无需包括此部分。
格式统一为,字体:
Georgia,行距:
固定行距12,字号:
小五)
#include"
StdAfx.h"
#include<
iostream>
usingnamespacestd;
classLinkNode//链表结点的存储结构
classStack;
Pointdata;
LinkNode*next;
classStack
private:
LinkNode*top;
//指向第一个结点的栈顶指针
Stack();
//构造函数,置空栈
~Stack();
//析构函数
voidPush(Pointe);
//把元素data压入栈中
PointPop();
//使栈顶元素出栈
PointGetPop();
//取出栈顶元素
voidClear();
//把栈清空
boolempty();
//判断栈是否为空,如果为空则返回,否则返回
Stack:
:
Stack()//构造函数,置空栈
top=NULL;
}
~Stack()//析构函数
voidStack:
Push(Pointe)//把元素x压入栈中
LinkNode*P=newLinkNode;
//P=newLinkNode;
P->
data=e;
next=top;
top=P;
PointStack:
Pop()//使栈顶元素出栈
PointTemp;
LinkNode*P;
P=top;
top=top->
next;
Temp=P->
data;
deleteP;
returnTemp;
GetPop()//取出栈顶元素的值
returntop->
Clear()//把栈清空
boolStack:
empty()//判断栈是否为空,如果为空则返回,否则返回
if(top==NULL)return1;
elsereturn0;
//函数说明
voidmain()
intback=1;
while(back)
{
intm=0,n=0;
//定义迷宫的长和宽
int**maze;
//定义二维指针存取迷宫
intflag;
cout<
<
"
*************欢迎使用迷宫求解系统***************"
;
\n菜单:
\n\t1.输入迷宫并探索路径\n\t"
2.退出\n*************************************************\n"
endl;
请选择:
cin>
>
flag;
for(;
flag=0)
{
if(flag==1)
{
maze=CreatMaze(m,n);
//调用CreatMaze(int&
n)函数,得到迷宫
if(FindMaze(maze,m,n))//调用FindMaze(int**maze,intm,intn)函数获取路径;
cout<
结论:
迷宫路径探索成功!
\n"
elsecout<
迷宫路径不存在!
\n\n"
continue;
}
if(flag==2)back=0;
break;
if(flag<
1||flag>
3)
cout<
Error!
!
}
}
}
n)//创建迷宫,返回存取迷宫的二维指针
int**maze;
//inti=0,j=0;
cout<
请输入迷宫的长和宽:
inta,b;
cin>
a>
b;
//输入迷宫的长和宽
请输入迷宫内容(0为通路,1为堵塞):
m=a;
n=b;
//m,n分别代表迷宫的行数和列数
maze=newint*[m+2];
//申请长度等于行数加的二级指针
for(inti=0;
i<
m+2;
i++)//申请每个二维指针的空间
maze[i]=newint[n+2];
for(inti=1;
=m;
i++)//输入迷宫的内容,0代表可通,1代表不通
for(intj=1;
j<
=n;
j++)
cin>
maze[i][j];
for(inti=0;
i++)//将迷宫的外围全部置,这样输入的时候是从(1,1)开始
maze[i][0]=maze[i][n+1]=1;
n+2;
i++)
maze[0][i]=maze[m+1][i]=1;
您输入的迷宫如下:
\n\t"
for(inti=1;
i<
=m;
for(intj=1;
j<
=n;
if(maze[i][j]==0)
□"
if(maze[i][j]==1)
■"
if(j==n)
{
\t"
}
returnmaze;
//返回存贮迷宫的二维指针maze
boolFindMaze(int**maze,intm,intn)//寻找迷宫maze中从(,)到(m,n)的路径
//到则返回true,否则返回false
Stackp,q;
//定义栈p存储路径,q存探索迷宫的过程
PointTemp1,Temp2;
intx,y,z;
Temp1.x=1;
Temp1.y=1;
q.Push(Temp1);
//将入口位置入栈
p.Push(Temp1);
maze[1][1]=-1;
//标志入口位置已到达过
while(!
q.empty())//栈q非空,则反复探索
intorient[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
//定义当前位置移动的个方向
Temp2=q.GetPop();
//获取栈顶元素
if(!
(p.GetPop().x==q.GetPop().x&
&
p.GetPop().y==q.GetPop().y))
p.Push(Temp2);
//如果有新位置入栈,则把上一个探索的位置存入栈p
for(z=0;
z<
4;
z++)//探索当前位置的个相邻位置
{
x=Temp2.x+orient[z][0];
//计算出新位置x位置值
y=Temp2.y+orient[z][1];
//计算出新位置y位置值
if(maze[x][y]==0)//判断新位置是否可达
Temp1.x=x;
Temp1.y=y;
maze[x][y]=-1;
//标志新位置已到达过
q.Push(Temp1);
//新位置入栈
if((x==(m))&
(y==(n)))//成功到达出口
Temp1.x=m;
Temp1.y=n;
Temp1.dir=0;
p.Push(Temp1);
//把最后一个位置入栈
PrintPath(p);
//输出路径
return1;
//表示成功找到路径
if(p.GetPop().x==q.GetPop().x&
p.GetPop().y==q.GetPop().y)
//如果没有新位置入栈,则返回到上一个位置
p.Pop();
q.Pop();
return0;
//表示查找失败,即迷宫无路经
voidPrintPath(Stackp)//输出路径
\n通路判断:
该迷宫有通路,路径如下:
\t行坐标,列坐标,数字方向,实际方向)\n"
Stackt;
//定义一个栈,按从入口到出口存取路径
LinkNode*temp;
temp=newLinkNode;
//申请空间
temp->
data=p.Pop();
//取栈p的顶点元素,即第一个位置
t.Push(temp->
data);
//第一个位置入栈t
deletetemp;
//释放空间
p.empty())//栈p非空,则反复转移
temp=newLinkNode;
temp->
//获取下一个位置
//得到行走方向
a=t.GetPop().x-temp->
data.x;
//行坐标方向
b=t.GetPop().y-temp->
data.y;
//列坐标方向
if(a==1)temp->
data.dir=1;
//方向向下,用表示
elseif(b==1)temp->
data.dir=2;
//方向向右,用表示
elseif(a==-1)temp->
data.dir=3;
//方向向上,用表示
elseif(b==-1)temp->
data.dir=4;
//方向向左,用表示
t.Push(temp->
//把新位置入栈
deletetemp;
//输出路径,包括行坐标,列坐标,下一个位置方向
t.empty())//栈非空,继续输出
data=t.Pop();
'
('
data.x<
'
data.y<
data.dir<
"
//输出行坐标,列坐标
switch(data.dir)//输出相应的方向
case1:
cout<
↓)\n"
case2:
→)\n"
case3:
↑)\n"
case4:
←)\n"
case0:
)\n"
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 数组 表示 及其 应用