实验数组的表示及其应用.docx
《实验数组的表示及其应用.docx》由会员分享，可在线阅读，更多相关《实验数组的表示及其应用.docx（23页珍藏版）》请在冰点文库上搜索。
实验数组的表示及其应用
（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）
实验难度：
A□B□C■
序号
学号
姓名
成绩
1
2
3
4
指导教师
（签名）
学 期：
2014秋季学期
任课教师:
张德海王常吉
实验题目:
数组的表示及其应用
小组长:
联系电话:
电子邮件:
完成提交时间：
2014年11月17日
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：
20131120267姓名：
蔡智霖本人承担角色：
代码设计，算法分析，运行监测，填写报告
评分项目
评分指标
分值
得分
实验构思（10%）
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计（15%）
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整，数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现（25%）
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常，测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写（10%）
1.内容详实无缺漏，文字流畅、图表清楚
5
2.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考
5
个人工作量（30%）
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作（10%）
1.有一定用户群
5
2.应用前景分析
5
综合得分：
（满分100分）
指导教师：
年月日
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：
20131120272姓名：
邓飞武本人承担角色：
结果检验，实验构思，调试代码
评分项目
评分指标
分值
得分
实验构思（10%）
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计（15%）
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整，数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现（25%）
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常，测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写（10%）
1.内容详实无缺漏，文字流畅、图表清楚
5
2.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考
5
个人工作量（30%）
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作（10%）
1.有一定用户群
5
2.应用前景分析
5
综合得分：
（满分100分）
指导教师：
年月日
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：
20131120247姓名：
温岩松本人承担角色：
错误总结，结果验证，调试代码
评分项目
评分指标
分值
得分
实验构思（10%）
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计（15%）
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整，数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现（25%）
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常，测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写（10%）
1.内容详实无缺漏，文字流畅、图表清楚
5
2.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考
5
个人工作量（30%）
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作（10%）
1.有一定用户群
5
2.应用前景分析
5
综合得分：
（满分100分）
指导教师：
年月日
云南大学软件学院2010学年秋季学期
《数据结构实验》成绩考核表
学号：
20131120258姓名：
程哲本人承担角色：
调试代码，错误总结，实验分析
评分项目
评分指标
分值
得分
实验构思（10%）
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计（15%）
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整，数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现（25%）
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常，测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写（10%）
1.内容详实无缺漏，文字流畅、图表清楚
5
2.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考
5
个人工作量（30%）
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作（10%）
1.有一定用户群
5
2.应用前景分析
5
综合得分：
（满分100分）
指导教师：
年月日
（下面的内容由学生填写，格式统一为，字体:
楷体,行距:
固定行距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.抽象数据类型具体实现的函数原型说明：
classPoint//迷宫中点位置的存储结构
{
public:
intx;//x代表当前位置的行坐标
inty;//y代表当前位置的列坐标
intdir;//0:
无效,1:
下,2:
右,3:
上,4:
左
};
2.子程序算法简介
int**CreatMaze（int&m,int&n）;//获取迷宫
boolFindMaze（int**maze,intm,intn）;//寻找迷宫maze中从（，）到（m,n）的路径
voidPrintPath（Stackp）;//输出迷宫的路径
四、【测试结果（Testing）】（10%）
（本部分应包括：
对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）
1.程序功能选择界面：
2.选择后：
3.进行数据输入后的结果：
4.再次输入数据：
四、【实验总结】（10%）
（本部分应包括：
自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）
蔡智霖：
迷宫求解的算法并没有一开始想的那么难，但也需要一步一步小心的把它完成，才能避免在小细节上出错，同时这次的实验堆我们在矩阵上的了解有一定考察。
在本次试验中，也运用到了栈来进行迷宫的存储。
总之，在本次试验中，我们学到了很多，多今后在矩阵的运用有了一个全新的了解。
邓飞武：
在做实验前,一定要将课本上的知识吃透,因为这是做实验的基础,否则,在老师讲解时就会听不懂,这将使你在做实验时的难度加大,浪费做实验的宝贵时间.
温岩松：
通过这次实验,使我学到了不少实用的知识,更重要的是,做实验的过程,思考问题的方法,这与做其他的实验是通用的,真正使我们受益匪浅.
程哲：
在这次实验中，我学到很多东西，加强了我的动手能力，并且培养了我的独立思考能力。
特别是在做实验报告时，因为在做数据处理时出现很多问题，如果不解决的话，将会很难的继续下去。
五、【项目运作描述（Operate）】（10%）
（本部分应包括：
项目的成本效益分析，应用效果等的分析。
）
本程序可以实现基本的迷宫求解功能，可以根据使用者所输入的迷宫来判断是否有同路，以及同路路径。
因为本程序并不具备可视化的运行界面，因此本程序并不具备较高的成本价值，但同时也因为本程序制作成本并不高，因此其效益相对来说尚可。
六、【代码】（10%）
（本部分应包括：
完整的代码及充分的注释。
注意纸质的实验报告无需包括此部分。
格式统一为，字体:
Georgia,行距:
固定行距12，字号:
小五）
#include"StdAfx.h"
#include
usingnamespacestd;
classPoint//迷宫中点位置的存储结构
{
public:
intx;//x代表当前位置的行坐标
inty;//y代表当前位置的列坐标
intdir;//0:
无效,1:
下,2:
右,3:
上,4:
左
};
classLinkNode//链表结点的存储结构
{
classStack;
public:
Pointdata;
LinkNode*next;
};
classStack
{
private:
LinkNode*top;//指向第一个结点的栈顶指针
public:
Stack（）;//构造函数，置空栈
~Stack（）;//析构函数
voidPush（Pointe）;//把元素data压入栈中
PointPop（）;//使栈顶元素出栈
PointGetPop（）;//取出栈顶元素
voidClear（）;//把栈清空
boolempty（）;//判断栈是否为空，如果为空则返回，否则返回
};
Stack:
:
Stack（）//构造函数，置空栈
{
top=NULL;
}
Stack:
:
~Stack（）//析构函数
{
}
voidStack:
:
Push（Pointe）//把元素x压入栈中
{
LinkNode*P=newLinkNode;
//P=newLinkNode;
P->data=e;
P->next=top;
top=P;
}
PointStack:
:
Pop（）//使栈顶元素出栈
{
PointTemp;
LinkNode*P;
P=top;
top=top->next;
Temp=P->data;
deleteP;
returnTemp;
}
PointStack:
:
GetPop（）//取出栈顶元素的值
{
returntop->data;
}
voidStack:
:
Clear（）//把栈清空
{
top=NULL;
}
boolStack:
:
empty（）//判断栈是否为空，如果为空则返回，否则返回
{
if（top==NULL）return1;
elsereturn0;
}
//函数说明
int**CreatMaze（int&m,int&n）;//获取迷宫
boolFindMaze（int**maze,intm,intn）;//寻找迷宫maze中从（，）到（m,n）的路径
voidPrintPath（Stackp）;//输出迷宫的路径
voidmain（）
{
intback=1;
while（back）
{
intm=0,n=0;//定义迷宫的长和宽
int**maze;//定义二维指针存取迷宫
intflag;
cout<<"*************欢迎使用迷宫求解系统***************";
cout<<"\n菜单：
\n\t1.输入迷宫并探索路径\n\t";
cout<<"2.退出\n*************************************************\n"<cout<<"请选择:
"<cin>>flag;
for（;;flag=0）
{
if（flag==1）
{
maze=CreatMaze（m,n）;//调用CreatMaze（int&m,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";
continue;
}
}
}
}
int**CreatMaze（int&m,int&n）//创建迷宫,返回存取迷宫的二维指针
{
int**maze;//定义二维指针存取迷宫
//inti=0,j=0;
cout<<"请输入迷宫的长和宽:
";
inta,b;cin>>a>>b;//输入迷宫的长和宽
cout<<"请输入迷宫内容（0为通路，1为堵塞）:
\n";
m=a;
n=b;//m,n分别代表迷宫的行数和列数
maze=newint*[m+2];//申请长度等于行数加的二级指针
for（inti=0;i{
maze[i]=newint[n+2];
}
for（inti=1;i<=m;i++）//输入迷宫的内容，0代表可通，1代表不通
for（intj=1;j<=n;j++）
cin>>maze[i][j];
for（inti=0;imaze[i][0]=maze[i][n+1]=1;
for（inti=0;imaze[0][i]=maze[m+1][i]=1;
cout<<"您输入的迷宫如下:
\n\t";
for（inti=1;i<=m;i++）
for（intj=1;j<=n;j++）
{
if（maze[i][j]==0）
cout<<"□";
if（maze[i][j]==1）
cout<<"■";
if（j==n）
{
cout<cout<<"\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）//输出路径
{
cout<<"\n通路判断:
";
cout<<"该迷宫有通路，路径如下:
\n";
cout<<"\t行坐标,列坐标,数字方向,实际方向）\n";
Stackt;//定义一个栈，按从入口到出口存取路径
inta,b;
Pointdata;
LinkNode*temp;
temp=newLinkNode;//申请空间
temp->data=p.Pop（）;//取栈p的顶点元素，即第一个位置
t.Push（temp->data）;//第一个位置入栈t
deletetemp;//释放空间
while（!
p.empty（））//栈p非空，则反复转移
{
temp=newLinkNode;
temp->data=p.Pop（）;//获取下一个位置
//得到行走方向
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->data）;//把新位置入栈
deletetemp;
}
//输出路径，包括行坐标，列坐标，下一个位置方向
while（!
t.empty（））//栈非空，继续输出
{
data=t.Pop（）;
cout<<"\t"<<'（'<switch（data.dir）//输出相应的方向
{
case1:
cout<<"↓）\n";break;
case2:
cout<<"→）\n";break;
case3:
cout<<"↑）\n";break;
case4:
cout<<"←）\n";break;
case0:
cout<<"）\n";break;
}
}
}
升级会员 