选择合适数据结构解决应用问题(概论)

发布网友 发布时间：2022-12-26 14:37

我来回答

共1个回答

热心网友 时间：2023-10-15 23:56

选择合适数据结构解决应用问题

． 计算机处理问题的分类（ ）数值计算问题　　在计算机发展初期 人们使用计算机主要是处理数值计算问题 【例 ． 】线性方程的求解　　该类问题涉及的运算对象是简单的整型 实型或布尔型数据 程序设计者的主要精力集中于程序设计的技巧 无须重视数据结构

（ ）非数值性问题　　随着计算机应用领域的扩大和软 硬件的发展 非数值性问题 越来越显得重要 据统计 当今处理非数值性问题占用了 %以上的机器时间 这类问题涉及到的数据结构更为复杂 数据元素之间的相互关系一般无法用数学方程式加以描述 因此 解决此类问题的关键已不再是分析数学和计算方法 而是要设计出合适的数据结构 才能有效地解决问题

．非数值问题求解　　著名的瑞士计算机科学家沃思（N Wirth）教授曾提出 　　算法+数据结构=程序　　数据结构 是指数据的逻辑结构和存储结构　　算法 是对数据运算的描述　　程序设计的实质是对实际问题选择一种好的数据结构 加之设计一个好的算法 而好的算法在很大程度上取决于描述实际问题的数据结构

【例 】电话号码查询问题 　　编一个查询某个城市或单位的私人电话号码的程序 要求对任意给出的一个姓名 若该人有电话号码 则迅速找到其电话号码 否则指出该人没有电话号码 　　要解此问题首先构造一张电话号码登记表 表中每个结点存放两个数据项 姓名和电话号码 　　要写出好的查找算法 取决于这张表的结构及存储方式 最简单的方式是将表中结点顺序地存储在计算机中 查找时从头开始依次查对姓名 直到找出正确的姓名或是找遍整个表均没有找到为止 这种查找算法对于一个不大的单位或许是可行的 但对一个有成千上万私人电话的城市就不实用了 若这张表是按姓氏排列的 则可另造一张姓氏索引表 采用如下图所示的存储结构 那么查找过程是先在索引表中查对姓氏 然后根据索引表中的地址到电话号码登记表中核查姓名 这样查找登记表时就无需查找其它姓氏的名字了 因此 在这种新的结构上产生的查找算法就更为有效

       【例 】田径赛的时间安排问题 　　假设某校的田径选拔赛共设六个项目的比赛 即跳高 跳远 标* 铅球 米和 米短跑 规定每个选手至多参加三个项目的比赛 现有五名选手报名比赛 选手所选择的项目如参赛选手比赛项目表所示 现在要求设计一个竞赛日程安排表 使得在尽可以短的时间内安排完比赛 （ ）为了能较好地解决这个问题 首先应该选择一个合适的数据结构来表示它 表示该问题的数据结构模型图如右下图（图中顶点代表竞赛项目 在所有的两个不能同时进行比赛的项目之间连上一条边） 显然同一个选手选择的几个项目是不能在同一时间内比赛的 因此该选手选择的项目中应该两两有边相连 （ ）竞赛项目的时间安排问题可以抽象为对无向图进行 着色 操作 即用尽可能少的颜色去给图中每个顶点着色 使得任意两个有边连接的相邻顶点着上不同的颜色 每一种颜色表示一个比赛时间 著上同一种颜色的顶点是可以安排在同一时间内竞赛的项目 由此可得 只要安排 个不同的时间竞赛即可 时间 内可以比赛跳高（A）和标*（C） 时间 内可以比赛跳远（B）和铅球（D） 时间 和时间 内分别比赛 米（E）和 米（F） 　　解决问题的一个关键步骤是 选取合适的数据结构表示该问题 然后才能写出有效的算法