东华大学数据结构课程设计报告书 (2)

任务一 迷宫问题求解任务一 迷宫问题求解 问题描述 问题描述 迷宫问题是取自心理学的一个古典实验 实验中 把一只老鼠从一个没有顶 的大盒子的门放入 在盒中设置了许多墙 对行进的方向形成了多处阻挡 盒子 仅仅有一个出口 在出口处放置了一块奶酪 吸引老鼠在迷宫中寻找道路以到达 出口 重复对老鼠进行上述实验 看老鼠能在多久找到出口 测试数据 0 表示可以行走的区域 1 表示不可行走的区域 n 6 m 5 X 6 Y 5 入口 1 0 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 0 出口 功能要求 功能要求 1 输入数据 输入 m n m n 为整数 n m 表示迷宫的长和宽 输入 X Y 为整数 表示出口的坐标 输入 n 行 m 列的迷宫 0 表示可以行走的区域 1 表示不可行走的区域 2 输出形式 中文提示老鼠是否能找到出口 若能 输出需要几步能到出口 并 能够输出老鼠所走的路线 需求分析 需求分析 本演示程序中 由用户定义迷宫的大小 内容 出口的位置然后程序会自动输出 所需结果 概要思路与设计 概要思路与设计 采用的算法是深度优先搜索 所使用的数据结构是栈 搜索算法是利用计算机的高性 能来有目的的穷举一个问题解空间的部分或所有的可能情况 从而求出问题的解的一种方 法 具体思路是从入口出发 接着判断该位置的上下左右是否能走 哪一个位置能走就走 哪个位置 若在该位置遭遇无法走的情况就退后上一步往其他方向走 利用栈先进后出的 结构特性即可实现该算法 如果将所有能走的方案的走完还不能到达出口则表示无解 反 之 若走到出口则停止搜索输出解 const int maxn 5001 定义迷宫的最大尺寸 const int fx 4 1 0 1 0 模拟走迷宫时横坐标改变 const int fy 4 0 1 0 1 模拟走迷宫时纵坐标改变 int map maxn maxn 用于储存迷宫 int ansx maxn ansy maxn 用于储存路线 int v maxn maxn 搜索时所用判断数组 防止重复走某一位置 详细设计 详细设计 include include include include using namespace std const int maxn 5001 const int fx 4 1 0 1 0 const int fy 4 0 1 0 1 int map maxn maxn ansx maxn ansy maxn int v maxn maxn int i j n m X Y bool flag 0 void dfs int x int y int step int xx yy if x X cout 所需步数是 step endl cout 所走的路径是 for i 0 i ansx i ansy i printf d d X Y flag 1 exit for i 0 i 3 i xx x fx i yy y fy i if xxn yym map xx yy 1 continue step ansx step xx ansy step yy map x y 1 dfs xx yy step step ansx step 0 ansy step 0 map x y 0 int main memset map 0 sizeof map memset ansx 0 sizeof ansx memset ansy 0 sizeof ansy cout 请输入迷宫的大小 n m scanf d d cout 请输入出口的位置 X Y scanf d d cout 请输入该迷宫 endl for i 1 i n i for j 1 j m j scanf d ansx 0 ansy 0 1 dfs 1 1 0 if flag cout 老鼠不能到达出口 endl return 0 调试分析 调试分析 一开始调试程序时发现会陷入死循环 检查后发现是在搜索时没有考虑重复访问一个 位置的情况 于是采用增加一个和迷宫一样大小的数组用来记录某位置是否被走过 这样 就可以防止重复访问 接着通过调试 程序成功运行 用户手册 用户手册 1 演示程序的运行环境为 Windows 8 系统 在 Dev C 5 4 2 中运行 执行文件为 maze exe 2 进入演示程序后即显示 DOS 形式的界面 3 输入相应数据 程序会自动运行 并显示相应结果 测试结果 测试结果 任务二 哈希表查找的设计任务二 哈希表查找的设计 问题描述 问题描述 设哈希表长为 20 用除留余数法构造一个哈希函数 以开放定址法中的线 性探测再散列法作为解决冲突的方法 编程实现哈希表查找 插入和建立算法 测试数据 关键字 组为 19 01 23 14 55 20 84 27 68 11 10 77 哈 希 函 数 为 H key key 13 功能要求 功能要求 1 用除留余数法构造一个哈希函数 2 实现哈希表建立 查找和插入 需求分析 需求分析 本演示程序中 由用户输入总数不多于 20 的数字 程序会自动将数字插入哈希表 中 并可进行再次的插入与查找操作 概要设计 概要设计 static const int MOD 13 除留余数法所使用的除数 static const int M 20 定义哈希表的大小 int H map M 存储 hash 表 int a 20 用于存储读入的数 详细设计 详细设计 include include include using namespace std static const int MOD 13 static const int M 20 int H map M int a 20 int hash int x int k return x k MOD int check int x int pos int i 0 while i M pos hash x i if H map pos 0 return 1 if H map pos x return 0 i return 1 void insert int x int temp pos temp check x if temp H map pos x cout x 插入成功 endl else if temp cout 重复的关键字 endl else cout 哈希表已满 endl void find int x int pos int temp check x if temp cout 该关键字在哈希表中的位置是 pos endl else cout 该关键字不在哈希表中 endl int main int i n k memset H map 0 sizeof H map cout 请输入总个数 n n n cout 请输入这 n 个数 for i 0 i a i for i 0 i 12 i insert a i cout i while i 3 switch i case 1 n cout a n insert a n break case 2