数据结构是介于数学计算机硬件和计算机软件三者之间的一门核心课程
在计算机科学中数据结构不仅是一般程序设计的基础而且是设计和实现编译程序操作系统数据库系统及其它系统程序和大型应用程序的重要基础
学习数据结构既为进一步学习其他软件课程提供必要的准备知识又有助于提高软件设计和程序编制水平
着名的瑞士计算机科学家沃思(NWirth)教授曾提出算法+数据结构=程序这里的数据结构是指数据的逻辑结构和存储结构而算法则是对数据运算的描述由此可见程序设计的实质是对实际问题选择一种好的数据结构加之设计一个好的算法而好的算法在很大程序上取决于描述实际问题的数据结构请看下面的几个例子
【例】八皇后问题
八皇后问题源于几百年前内容是这样的在标准国际象棋棋盘上放上八个皇后使其互相不能够攻击这个问题是高斯最先提出的每一行每一列或一斜线上只能有一个皇后否则就违反了规则若不考虑旋转对称因素共有种解法
在棋盘上的八皇后所处的位子它们恰恰不能够彼此之间相互进攻 而且只要在棋盘上再多放一个皇后就会打破这种局面您可以按棋盘上方的按钮查看下一种解法
【例】最短路径
举例来说一些城市之间有道路相连道路的长度已知现在要求有这么一个系统来满足旅客提成的一些问题如一旅客要从A城到B城去旅行 他希望选择一条总路程最短或是途中中转次数最少的路径
您可以在指定的输入框中输入起点城市和终点城市的代号再按一下最短路径的按钮地图上就会用红线标出该两城市间的最短路径
【例】人机对弈问题
计算机能够和人进行对弈是因为有人将对弈的策略存入计算机而对弈是在一定规则下随机进行的不仅要看棋盘当时的格局还要能够预测将来将可能发生的趋势这是一个相当复杂的问题不仅需要数据结构的知识还深入涉及到人工智能的领域我们在这里举一个实现简单例子只是想说明数据结构的广泛用途
本例子称为井字棋规则是这样的两人对弈棋盘是 x 的方格当一方的三个棋子占同一行同一列或同一对角线时便获胜一般来说先手方有较大的主动权因此我们在这里让同学们先下子看看计算机是怎么应付的
请您和计算机比一比看谁的反应快请用鼠标点击对应的方格您所下的棋子用●表示计算机所下的棋子用○ 表示
请别太大意了!计算机可不是那么容易对付的
【例】Hanoi塔(河内塔)问题
假设有三个分别命名为AB和C的塔座在塔座B上插有n个直径大小各不相同依小到大编号为…n的圆盘现要求将B轴上的n个圆盘移至塔座A上并仍按同样顺序叠排圆盘移动时必须遵循下列规则
) 每次只能移动一个圆盘
) 圆盘可以插在AB和C中的任一塔座上
) 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上