教学设计 课程基本信息 课题 6.1实时查询系统中数据的组织 教学目标 1.了解大数据处理过程中常见的数据组织与处理方式 2. 能结合已知的数据结构知识，选用合理的数据结构去解决问题 3. 能用迭代的思想去看待数据结构的设计、数据的组织与存储 4. 能激发进一步学习数据的组织与存储、数据结构与算法设计的兴趣 教学内容 教学重点： 能用迭代的思想去看待数据结构的设计、数据的组织与存储 教学难点： 能用迭代的思想去看待数据结构的设计、数据的组织与存储 教学过程 一、情境导入 1、师：生活中人们为了方便，很多时候会选择在网络平台进行购物，新学期要开始了，小陈同学想在网购平台购买一只书包，我们一起来看看他是如何选择心仪的书包的？ ▲在观看过程中，请同学们思考：小陈同学在该平台查询信息的方式和特点？ （播放视频） 2、请几位同学来说一说在视频中看到的信息查询的方式和特点。 二、实时查询系统中的数据业务特点 师生共同小结： 像这样实现实时查询的系统中，我们可以发现其数据业务呈现以下特殊性： （1）能实现上千个请求的实时响应 （2）支持后续商品信息的更改 三、实时查询系统中的数据结构和算法设计 1、数组 可以比较直接的表示商品之间按照某种属性呈现的有序线性关系。当数据从数据库读取到数组后，我们可以按照各个属性进行排序后，把他们分类存储。 ▲请同学们小组讨论并完成学生任务单中的“学习任务一”(1)(2)(3)。 （1）有数组如下，若要插入数字7，使数组仍然有序，该如何操作？ 索引0123456789元素13456891215 （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) （3）思考：如果数据量较多时，我们可以采用什么方法来查找位置？ _____ 师生共同分析回顾在数组中查找与插入的操作，引出为提高查找效率，可使用二分查找，简单回顾二分查找的过程，比较顺序查找与二分查找的效率。 2、链表 ▲请同学们小组讨论并完成学生任务单中的“学习任务二”(1)(2)(3)。 （1）有链表如下，若要插入数字26，使链表仍然有序，该如何操作？ （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]) （3）思考：请同学们讨论交流，分析数组与链表各自的优势和劣势。 优势劣势数组链表 师生共同分析回顾在链表中查找与插入的操作，结合程序代码直观的感知具体的算法实现。师生共同分析数组与链表各自的优势与劣势。 优势劣势数组利用二分查找 时间复杂度：O(log2n) 查找速度比较快插入位置之后的所有元素都必须往后移位，时间复杂度较大：O(n)链表插入新元素效率高，时间复杂度仅为O(1)查找时必须从头节点开始依次遍历，时间复杂度为O(n) 四、基于链表的数据结构和算法优化 1、由于链表的处理，只是在查找时效率较低，而插入操作却完全能满足要求，所以可以在链表的基础上继续加以改进，以解决顺序查找导致的低效问题。我们可以按以下思路来考虑： （1）减少查找插入位置过程中的比较次数 （2）借鉴二分查找算法的思想 2、这里我们引入一个新的数据结构--跳跃表。 原链表如下，若要在原链表中查找18，我们需要比较6次，现在，我们通过抛硬币的方式来提取一组关键节点放到上层作为一级索引，此时，我们只需要 ... ... 
