实时查询系统中数据的组织-教学设计 .docx
教学设计课程基本信息课题6.1实时资询系统中数据的组织教学目标1.了解大数据处理过程中常见的数据祖织与处理方式2,能结合已知的数据结构知识，选用合理的数据结构去解决问麹3 .能用迭代的思想去看待数据结构的设计、数据的组织与存储4 .能激发进一步学习数据的组织与存储、数据结构与算法设计的兴趣教学内容教学面点；能用迭代的思想去看待数据结构的设计、数据的组织与存储教学难点：能用迭代的思想去看待数据结构的设计、数据的组织与存储教学过程一、情境导入1、师：生活中人们为了方便，很多时候会选择在网络平台进行购物，新学期要开始了，小陈同学想在惬期平价的买一只书包.我们一起来看看他是如何选择心仪的书包的？在观看过程中，请同学们思考：小陈同学在该平台食询信息的方式和特点？（播放视频）2、请几位同学来说一说在视频中看到的信息查询的方式和特点.二、实时If询系统中的数据业务特点师生共同小结：像这样实现实时查询的系统中，我们可以发现其数据业务呈现以下特殊性：<1）能实现上千个谛求的实时响应（2）支持后续商品信息的更改三、实时承!系统中的数据结构和算法设计1.数组可以比较直接的表示商M之间按照某种属性呈现的有序线性关系.当数据从数据库读取到数姐后，我们可以按照各个属性进行持序后,把他们分类存储，摩黑播(商，名0.人,Mf.仪用.传卷)H««2M«)AM4(栓人3生)(4f4)I)(爱代用拗亭)!<Aft-MM*4)说同学们小组讨论并完成学生任务单中的“学习任务一”(D(2)(3%(D有数组如下,若要插入数字7,使数组仍然有序，该如何操作？索引0123156789八：素13456891215(2)程序实现：完成以下代码填空a=l,3,4,5,6,8,9,12,15,0«0我示该位置未存储元素num=inMinput("输入需要插入的数据：")foriinrange(Ien（八）):ifa(i>num:forJinrange(Ien（八）-1,i-l,l):-breakelse:a-l=runprint（八）(3)思考：如果数据Ift较多时，我们可以采用什么方法来我找位置？师生共同分析口1顾在数组中查找与插入的操作，引出为提岛查找效率，可使用二分杳找，简单回顾：分在找的过程，比较顺序在找马二分传找的效率。2、链表的同学们小组讨论并完成学生任务单中的“学习任务二"(D(2)(3).(I)有链表如下，若要插入数字26,使能表仍然有序，该如何操作？12S152229-35-g46(2)程序实现：a=12,1,15,2,22,3,29,4,35,5,46,-1)的51打足白叩成(”输入需要插入的数据：”)head=Op=headifnu三<aheadj0:a.append(num,head)else:whilenum>apjlandp!=-l:q二Pp=apla.append(num,)p=headwhileapl!=-l:print(apj.end=1->>)print(ap0)(3)思考：请同学们讨论交流,分析数组与能表各自的优势和劣势,优势劣势数组融表师生共同分析回顾在就表中宜找与插入的操作，结合程序代码直观的那却具体的嶙法实现,师生共同分析数组与琏表各自的优势与劣势.优势劣势数组利用二分查找时间熨杂度：O(IOgm)查找速度比较快插入位置之后的所有元素都必须往后移位，时间史杂度较大：0(n)就表插入新元素效率高,时间复杂度仅为Oa)查找时必须从头节点开始依次遍历，时间复杂度为(Kn)四、基于卷良的皴据结构和算法优化1.由于链表的处理，只是在瓷找时效率较低，而插入操作却完全能满足要求，所以可以在桂表的基础上继续加以改进.以解决顺序查找导致的低效问题.我们可以按以下则路来考虑：(1)减少杳找插入位置过程中的比较次数(2)借鉴二分查找算法的思想2,这里我们引入一个新的数据结构跳跃去。原鞋表如下,若要在原桂表中查找18.我们需要比较6次.现在,我的通过他饿而的方式来提取一组关犍节点放到上层作为一徼索引，此时，我们只需要比较5次就可以找到18.如果用同样的方法,为一级索引建立二纸索引，我们只同要比较4次就可以找到18。二-M*<1麻ItAI34IOB1820由此可见关谯行点起到一个索引表的作用，能快速定位到一个较小的查找区间,然后只需将索引位置对应到额链表，就可以找到了。如果数据比较多时，还可以维续增设三、四汲索引，进一步提升查找的速度.跳球友的时间亚朵度：O(Iogm)(1)跳跃表增设关键节点例如.原林表增加了新节点24.我们仍然果川抛硬币的方式来决定是否把24提升为上一层的关堆节点，如果她硬币结果为不提升，那么24只出现在原陡衣中,如果他硬币结果为(2)跳跃表捌除关键节点例如要删除13,从：级索引开始，依次往下删除各层的13。由于：级索引在削除13以后只剜卜.一个关键。点,对于区间划分和提商杳找效率没有任何意义，所以桁剜卜的节点13、帅生共同小结：从数殂到跳衣，再到跳跃表，我们可以发现，一个切合实际的数据结构和算法不是一域而就的，而是根据问题中的数据及其关系的特点，通过迭代逐步优化得到的，五、其他数据蛆纲与处理方式单纯的采用传统的磁盘:数据库来组织、处埋海奴的数据，其固有的数据组织、存取、处理等模式已经无法适应当今很多数据业务对实时数据管理和杳询的需求，为了提升数据的处理性能人们发明了内存数据库.大部分的内存数据库主要从以下几个方面来提升数据的处理性能：(1)减少对磁盘的访问(2)对数据进行分徼存储(3)采用改进后的数据结构来组税、存储数据六、小结与拓展师生共同小结：本节课，我们了解了大数据处理过程中常见的数据组织与处理方式，以及在数据业务中，数据进行分类、整理等组织工作的必要性,还一起感受了数据结构设计过程中的迭代思想.课外拓展：除了本节课提到的几种数据结构，是否还有其他的数据结构来解决数据的如织与存储问胞呢？请同学们课后讨论交流.如果有,请简要描述该数据结构组织数据并处理的算法,并尝试分析用该数据结构斛决何明的时间复杂度。
