数据结构是计算机软件和计算机应用专业的核心课程之一在众多的计算机系统软件和应用软件中都要用到各种数据结构因此仅掌握几种计算机语言是难以应付众多复杂的课题的要想有效地使用计算机还必须学习数据结构的有关知识
选择合适数据结构解决应用问题
计算机处理问题的分类
()数值计算问题
在计算机发展初期人们使用计算机主要是处理数值计算问题
【例】线性方程的求解
该类问题涉及的运算对象是简单的整型实型或布尔型数据程序设计者的主要精力集中于程序设计的技巧无须重视数据结构
()非数值性问题
随着计算机应用领域的扩大和软硬件的发展非数值性问题越来越显得重要据统计当今处理非数值性问题占用了%以上的机器时间这类问题涉及到的数据结构更为复杂数据元素之间的相互关系一般无法用数学方程式加以描述因此解决此类问题的关键已不再是分析数学和计算方法而是要设计出合适的数据结构才能有效地解决问题
非数值问题求解
着名的瑞士计算机科学家沃思(NWirth)教授曾提出
算法+数据结构=程序
数据结构是指数据的逻辑结构和存储结构
算法是对数据运算的描述
程序设计的实质是对实际问题选择一种好的数据结构加之设计一个好的算法而好的算法在很大程度上取决于描述实际问题的数据结构
【例】电话号码查询问题
编一个查询某个城市或单位的私人电话号码的程序要求对任意给出的一个姓名若该人有电话号码则迅速找到其电话号码;否则指出该人没有电话号码
要解此问题首先构造一张电话号码登记表表中每个结点存放两个数据项 姓名和电话号码
要写出好的查找算法取决于这张表的结构及存储方式最简单的方式是将表中结点顺序地存储在计算机中查找时从头开始依次查对姓名直到找出正确的姓名或是找遍整个表均没有找到为止这种查找算法对于一个不大的单位或许是可行的但对一个有成千上万私人电话的城市就不实用了若这张表是按姓氏排列的则可另造一张姓氏索引表采用如下图所示的存储结构那么查找过程是先在索引表中查对姓氏然后根据索引表中的地址到电话号码登记表中核查姓名这样查找登记表时就无需查找其它姓氏的名字了因此在这种新的结构上产生的查找算法就更为有效
【例】田径赛的时间安排问题
假设某校的田径选拔赛共设六个项目的比赛即跳高跳远标枪铅球米和米短跑规定每个选手至多参加三个项目的比赛现有五名选手报名比赛选手所选择的项目如参赛选手比赛项目表所示现在要求设计一个竞赛日程安排表使得在尽可以短的时间内安排完比赛
()为了能较好地解决这个问题首先应该选择一个合适的数据结构来表示它表示该问题的数据结构模型图如右下图(图中顶点代表竞赛项目在所有的两个不能同时进行比赛的项目之间连上一条边)显然同一个选手选择的几个项目是不能在同一时间内比赛的因此该选手选择的项目中应该两两有边相连
()竞赛项目的时间安排问题可以抽象为对无向图进行着色操作即用尽可能少的颜色去给图中每个顶点着色使得任意两个有边连接的相邻顶点着上不同的颜色每一种颜色表示一个比赛时间着上同一种颜色的顶点是可以安排在同一时间内竞赛的项目由此可得只要安排个不同的时间竞赛即可时间内可以比赛跳高(A)和标枪(C)时间内可以比赛跳远(B)和铅球(D)时间和时间内分别比赛米(E)和米(F)
解决问题的一个关键步骤是选取合适的数据结构表示该问题然后才能写出有效的算法
