c高等数据结构与算法分析

《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