第一章 绪论
1-教学安排
略
2-数据结构基本概念，术语与主要学习内容
1-数据结构主要内容
在计算机学科中，学习程序语言之后就要学习数据结构与算法内容。
1、为什么要学习数据结构与算法？它和计算机有什么关系？
计算机除去硬件以外，还需要有软件，用来丰富计算机的功能。软件就是程序+文档构成： 程序＝算法+数据结构，算法=逻辑+控制；
【例1】 迷宫：字符界面、图形界面、迷宫游戏
这些迷宫形式不同，但是本质相同
需要解决下面的几个问题：
①输入是什么：迷宫地图、入口与出口
②输出是什么：入口到出口的路径
③输入如何转换为输出：在已知迷宫地图寻找入口到出口路径的方法（算法）
要解决的问题1：迷宫地图【数据结构选择与设计】
如何表示给定的空间和可行的路径？（迷宫表示）
如何表示入口与出口？
可以用一个m行n列的二维数组maze[m][n]来表示迷宫空间，并约定：
当数组元素maze[i][j]=0，表示通路；maze[i][j]=1，表示不通。
构建出的迷宫结构如上所示
要解决的问题2：寻路过程【算法设计】
当有多条可行路径时如何选择？
当某条路径在某一点没有可行之路时如何处理？
某点会重复经过吗（避免兜圈子）？
多条可行路：
在某一点（x，y），有8个可以探索的方向：
八个方向的坐标改变量
假设：从正东方向开始，沿顺时针方向依次进行探索，将探索方向存储在增量数组DeltaXY中：
数组变化如上
Problem：角点、边点和中间点探测的判断方法是一致的吗？
答：角点和边点都要考虑边界的问题，没有八个方向，因此要对三者的探测方法进行一致性处理，也就是迷宫地图简化，在迷宫四周都扩展一个点，增加两行两列，并全部设置为1，表示是墙不能通行。这样所有点都成为中间点，不用再判断当前点是角点、边点还是中间点，每个点的探索方向均为8个。
简化后的迷宫如上图所示
死路退回：
回退到上一个有多条路径的地方选择下一条路径探测；
需要存储每一个局有多条路径的点坐标和探索方向（x，y，d）【x代表横坐标，y代表纵坐标，d取值0~7代表方向】；
存储的多个（x，y，d）选择最新存储位置回退——栈
兜死圈子：
两种方法：
1.设置一个标志数组mark[m][n]，所有元素初始化为0；
在探索中，当所探索的点（i，j）对应的mark[i][j]=0时，才进入该点，并将mark[i][j]设置为1；当所探索的点（i，j）对应的mark[i][j]=1时，表明已经探索过，不需要再进入。
2.当到达某点（i，j）后，在迷宫地图的该点坐标上标记特殊值，例如把maze[i][j]设置为-1，以便区分没有到达过的点。
小结：
1.二维数组maze[m+2][n+2]来表示迷宫，解决迷宫地图的存储；
2.一维数组DeltaXY[8]来记载8个探索方向的坐标增量，将8个探索方向数字化为0到7，并将向下一点前进的操作统一为当前点的坐标+沿该探索方向的增量，即可得到下一点的坐标；
3.当某点无路通行时，需要从该点返回到前一点，再从前一点选择下一个方向继续进行探索，即需要知道前一点和前一点当前探索的方向。因此，我们需要保留依次到达各点的坐标和到达该点的方向；
4.需要防止重复到达某点，避免在迷宫中兜死圈子，需要记载已经到达过的点。
本节小结：
数据结构有两大用途：
一是用于存放要处理的数据，如迷宫地图；
二是用于实现算法策略，如迷宫例子中探索方向增量数组、回溯的栈、避免重复走的标志数组或特殊标记。
网友评论