(
课件网) 6.1实时查询系统中数据的组织 一、情境导入 网购平台购物，如何查询和选择商品？ 思考：小陈同学在该平台查询信息的方式和特点？ （1）能实现上千个请求的实时响应 网站应能做到“即点即现”，即当某用户选择一种查询方式后，系统能马上呈现结果，而且同一时刻可能有上千名用户提出了查询请求。 二、实时查询系统中的数据业务特点 （2）支持后续商品信息的更改 当用户选择了某种查询后，可能马上又有另一名用户提出其他方式的查询请求，而此时恰好网站中更改了某个商品的属性，也或者是删除、增加了商品，那么这个修改信息应该体现在最新的查询结果中。 三、实时查询系统中的数据结构和算法设计 数组 链表 三、实时查询系统中的数据结构和算法设计 1、数组 原数据（商品名称，人气，销量，信用，价格） 数据1 （按人气排序） 数据2 （按销量排序） 数据3 （按信用排序） 数据4 （按价格排序） 分类存储 三、实时查询系统中的数据结构和算法设计 1、数组 索引 0 1 2 3 4 5 6 7 8 9 元素 1 3 4 5 6 （1）有数组如下，若要插入数字7，使数组仍然有序，该如何操作？ 8 9 12 15 7 ▲请同学们小组讨论并完成学生任务单中的“学习任务一”(1)(2)(3)。 三、实时查询系统中的数据结构和算法设计 1、数组 （2）程序实现： a=[1,3,4,5,6,8,9,12,15,0] #0表示该位置未存储元素 num=int(input("输入需要插入的数据：")) for i in range(len(a)): if a[i]>num: for j in range(len(a)-1,i-1,-1): _____①_____ ____②_____ break else: a [-1]=num print(a) a[j]=a [j-1] a [i]=num 三、实时查询系统中的数据结构和算法设计 1、数组 （3）思考：如果数据量较多时，我们可以采用什么方法来查找位置？ 二分查找 时间复杂度：O(log2n) 索引 0 1 2 3 4 5 6 7 8 元素 1 3 4 5 6 8 9 12 15 i j m m m i j j 三、实时查询系统中的数据结构和算法设计 2、链表 12 15 22 29 46 35 （1）有链表如下，若要插入数字26，使链表仍然有序，该如何操作？ head 26 ▲请同学们小组讨论并完成学生任务单中的“学习任务二”(1)(2)(3)。 三、实时查询系统中的数据结构和算法设计 2、链表 （2）程序实现： a=[[12,1],[15,2],[22,3],[29,4],[35,5],[46,-1]] num=int(input("输入需要插入的数据：")) head=0 p=head if num
a[p][0]and p!=-1: q=p p=a[p][1] a.append([num,p]) _____②_____ p=head while a[p][1]!=-1: print(a[p][0],end='->') _____③_____ print(a[p][0]) head=len(a)-1 a[q][1]=len(a)-1 p=a[p][1] 三、实时查询系统中的数据结构和算法设计 2、链表 （3）思考：请同学们讨论交流，分析数组与链表各自的优势和劣势。 优势 劣势 数组 链表 利用二分查找 时间复杂度：O(log2n) 查找速度比较快 插入位置之后的所有元素都必须往后移位，时间复杂度较大：O(n) 插入新元素效率高，时间复杂度仅为O(1) 查找时必须从头节点开始依次遍历，时间复杂度为O(n) 四、基于链表的数据结构和算法优化 思路： （1）减少查找插入位置过程中的比较次数 （2）借鉴二分查找算法的思想 二分查找算法之所以效率较高，首先是因为数据是有序的，其次是利用有序性进行跨区间、跳跃性的比较，从而避免低效的逐个依次比较。 跳跃表 四、基于链表的数据结构和算法优化 跳跃表 1 3 4 10 13 18 20 原链表 抛硬币 关键节点 一级索引 1 4 13 20 四、基于链表的数据结构和算法优化 跳跃表 1 3 4 10 13 18 20 原链表 抛硬币 关键节点 一级索引 1 4 13 20 二级索引 1 13 时间复杂度为： O(log2n) 四、基于链表的数据结构和算法优化 跳跃表--增设关键节 ... ... 
