(
课件网) 6.1 实时查询系统中数据的组织 学习目标： 感受数据结构设计过程中的迭代思想。 了解实时查询系统中的数据业务特点。 了解数据业务中，数据进行分类、整理等组织工作的必要性。 引入 引入 操作与体验： 打开天猫购物商城，解决以下问题： 要购买一本有关信息技术的书籍，预算在30元以内？ 想要知道目前哪本信息技术书籍最畅销？ 想要知道哪个店铺的好评率最高？ 引入 实时查询系统数据业务特点： ①能实现上千个请求的实时响应。“即点即现” ②支持后续商品信息的更改。 更改信息、删除商品、增加商品应体现在最新的查询结果中 实时查询系统的两个特殊性： 实时查询系统数据业务特点： 计算机硬盘 数据库 内存 访问 保存 系统崩溃 用户流失 提高读取速度 实时查询系统数据业务特点： 用某种数据结构组织并存储数据： 能体现数据间的逻辑关系 能为后续查询提供算法支持 实时查询系统数据结构和算法设计： 1.基于数据间线性关系的数据结构设计 （1）数组 数据读取到数组后，先按各属性（销量、信用、价格等）进行排序并分类存储。 体现商品间的有序线性关系 基于数组的算法设计： 查询过程中涉及的主要操作： 数据插入 数据查找 例如：新增商品时，需要插入一个新数据并维持数组元素继续有序。 基于数组的算法设计： 查询过程中涉及的主要操作： 数据插入 数据查找 二分查找 插入位置x到n中的元素均后移一位 上千名用户提出请求时，时效性较差 实时查询系统数据结构和算法设计： 整体复杂度有所下降，但还是达不到现实的需求。 （2）链表 数据查找过程： 数据插入过程： 需从链表的一端依次遍历 问题与讨论： 除了数组和链表，是否还有其他的数据结构来组织并存储数据？ 非线性数据： 树结构 实时查询系统数据结构和算法设计： 只在查找过程低效 （2）链表 数据查找过程： 数据插入过程： 需从链表的一端依次遍历 实时查询系统数据结构和算法设计： 2.基于链表的数据结构和算法优化设计 （1）减少查找插入位置过程中的比较次数 链表结构数据主要消耗在插入位置的查找中，可减少查找过程中的数据两两比较的次数来优化数据结构。 （2）借鉴二分查找算法的思想 ①数据进行有序化处理 ②确定比较的关键节点 基于链表的数据结构和算法优化设计： 关键节点：对每个节点采用抛硬币的方法确定是否放在关键节点中 1 3 4 10 13 15 20 1 原链表 4 10 15 关键节点 基于链表的数据结构和算法优化设计： 1 3 4 10 13 15 20 1 原链表 4 10 15 关键节点 抛硬币的次数越多，其正反的概率越趋向于 6 例如：查找元素6 分别与1,3,4,10比较 分别与1, 4,10比较 基于链表的数据结构和算法优化设计： 1 3 4 10 13 15 20 1 原链表 4 10 15 关键节点 从整体效率分析：增设关键节点后，查找速度是原来的2倍 6 例如：查找元素6 分别与1,3,4,10比较 分别与1, 4,10比较 索引表 基于链表的数据结构和算法优化设计： 1 3 4 10 13 15 20 1 原链表 4 10 15 一级索引 1 建立二级索引 10 二级索引 基于链表的数据结构和算法优化设计： 1 3 4 10 13 15 20 1 原链表 4 10 15 一级索引 1 插入数据元素6 10 二级索引 原一级索引的比较次数减少一半，数据多，还可增设三、四级索引 总体来说,通过对链表改进可实现 基于链表的数据结构和算法优化设计： 数据增加时，增设关键节点 实时查询系统中，数据不断发生变化，需对关键节点进行动态调整： 数据减少时，删除关键节点 基于链表的数据结构和算法优化设计： 1 3 4 10 13 15 20 1 原链表 4 10 15 一级索引 1 ①增设关键节点。例如：增加数据元素24。 10 二级索引 24 24 “抛硬币”为负则不需要提升；为正，把节点24提升到上一层索引 基于链表的数据结构 ... ...
