数据结构概论之学习数据结构的意义

数据结构概论之学习数据结构的意义  

　　数据结构是介于数学 计算机硬件和计算机软件三者之间的一门核心课程 　　在计算机科学中 数据结构不仅是一般程序设计的基础 而且是设计和实现编译程序 操作系统 数据库系统及其它系统程序和大型应用程序的重要基础 　　学习 数据结构 既为进一步学习其他软件课程提供必要的准备知识 又有助于提高软件设计和程序编制水平 　　著名的瑞士计算机科学家沃思（N Wirth）教授曾提出 算法+数据结构=程序 这里的数据结构是指数据的逻辑结构和存储结构 而算法则是对数据运算的描述 由此可见 程序设计的实质是对实际问题选择一种好的数据结构 加之设计一个好的算法 而好的算法在很大程序上取决于描述实际问题的数据结构 请看下面的几个例子 【例 】八皇后问题 　　八皇后问题源于几百年前 内容是这样的 在标准国际象棋棋盘上 放上八个皇后 使其互相不能够攻击 这个问题是高斯最先提出的 每一行 每一列 或一斜线上只能有一个皇后 否则就违反了规则 若不考虑旋转对称因素 共有 种解法 　　　　在棋盘上的八皇后所处的位子 它们恰恰不能够彼此之间相互进攻 而且只要在棋盘上再多放一个皇后 就会打破这种局面 您可以按棋盘上方的按钮查看下一种解法  【例 】最短路径 　　举例来说 一些城市之间有道路相连 道路的长度已知 现在要求有这么一个系统来满足旅客提成的一些问题 如一旅客要从Ａ城到Ｂ城去旅行 他希望选择一条总路程最短或是途中中转次数最少的路径 　　　　您可以在指定的输入框中输入起点城市和终点城市的代号 再按一下 最短路径 的按钮 地图上就会用红线标出该两城市间的最短路径

【例 】人机对弈问题 　　计算机能够和人进行对弈 是因为有人将对弈的策略存入计算机 而对弈是在一定规则下随机进行的 不仅要看棋盘当时的格局 还要能够预测将来将可能发生的趋势 这是一个相当复杂的问题 不仅需要数据结构的知识 还深入涉及到人工智能的领域 我们在这里举一个实现简单例子 只是想说明数据结构的广泛用途 　　本例子称为井字棋 规则是这样的 两人对弈 棋盘是 x 的方格 当一方的三个棋子占同一行 同一列 或同一对角线时便获胜 一般来说 先手方有较大的主动权 因此我们在这里让同学们先下子 看看计算机是怎么应付的 　　　　请您和计算机比一比 看谁的反应快 请用鼠标点击对应的方格 您所下的棋子用 ● 表示 计算机所下的棋子用 ○ 表示 　　　　请别太大意了！计算机可不是那么容易对付的