欢迎来到天天文库
浏览记录
ID:36324676
大小:857.50 KB
页数:51页
时间:2019-05-09
《c高等数据结构与算法分析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、Chapter4ListsandArraysRevisited1.SkipLists2.Multilists3.MatrixRepresentations4.MemoryManagementAprobabilisticdatastructurethatcanbeusedimplementthedictionaryADT.TheSkipListiscomparableincomplexitytotheBST,yetoftenoutperformstheBSTsincetheSkipList‘seff
2、iciencyisnottiedtothevaluesofthedatasetbeingstored.Whichareliststhatmaycontainsublists.Representationsforimplementingsparsematrices,largematricswheremostoftheelementshavezerovalues.Whichareessentiallyawayofallocatingvariable-lengthsectionsfromalargearr
3、ay.1.SkipListsSkipListsaredesignedtoovercomeabasiclimitationofarray-basedandlinkedlists:Eithersearchorupdateoperationsrequirelineartime.顺序表和链表的基本问题:每一次检索或更新需要的时间都是线性的TheprimaryproblemwiththeBSTisthatitmayeasilybecomeunbalanced.BST的主要问题:容易变得不平衡The2-3tre
4、eisguaranteedtoremainbalancedregardlessoftheorderinwhichdatavaluesareinserted,butitisrathercomplicatedtoimplement.2-3树保证不管数据值以什么顺序插入,都能保持平衡,但难以实现TheAVLtreeandthesplaytree,whicharealsoguaranteedtoprovidegoodperformance,butatthecostofaddedcomplexityascom
5、paredtotheBST.AVL树和伸展树都能保证提供好的性能(O(logn))(检索、插入、删除时间为O(logn)),但与BST树相比,也增加了额外的复杂性1.SkipLists跳跃表——n个元素的有序表,采用折半查找所需时间复杂度为O(logn)——而对一个有序链表进行查找所需的时间复杂度为O(n)对于有序链表时间复杂度如何由O(n)O(logn)?SkipLists1.SkipLists在实现的难度和性能两方面进行了很好的折中TheSkipListisnotguaranteedtoprov
6、idegoodperformance,butitwillprovidegoodperformancewithextremelyhighprobability.跳跃表不能保证提供好的性能,但提供好性能的概率极高Assuchitrepresentsagoodcompromisebetweendifficultyofimplementationandperformance.在实现难度和性能两方面进行了很好的权衡。有序链表2024304060758095^head跳跃表:2024304060758095^^
7、通过对有序表链表的全部或部分结点增加额外的指针,来提高搜索性能在查询时,通过这些指针来跳过链表中若干个结点,因此没必要从左到右搜索连表中的所有结点最坏情况下比较次数为8次最坏情况下比较次数为4次1.SkipLists01220243040608095∧∧∧75查找:key=30在二级链中找,由于30<40搜索左半部分中间元素在一级链中找,由于30>24故需在0级链中查找key=77与40比较77>40,在一级链中与75比较通常0级链包括n个元素,1级链包括n/2个元素,2级链包括n/4个元素。当且仅
8、当一个元素在0-i级链上,但不在i+1级链上时,我们称该元素定为i级链元素。如:40,95是2级链上唯一的元素,24,75是1级链元素,20,30,60,80是0级元素。插入,删除:插入key=77找到插入的位置为新元素分配一个级,分配过程由随机数产生器完成若新元素为i级链元素,则断开0~i级链指针,插入。级的分配:intrandomlevel(void){//级按指数分布for(intlevel=0;Random(2)==0;level++);returnlevel
此文档下载收益归作者所有