数据结构与算法Word文件下载.docx
《数据结构与算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构与算法Word文件下载.docx（25页珍藏版）》请在冰点文库上搜索。
数组实现
13351072_郑泽丰_11_2\
链表实现
红黑树
ColoredNodesDefinition
•Binarysearchtree.
•Eachnodeiscoloredredorblack.
•Rootandallexternalnodesareblack.
•Noroot-to-external-nodepathhastwoconsecutiverednodes.
•Allroot-to-external-nodepathshavethesamenumberofblacknodes
词典查找树
1.1.4插值查找
1.1.5外部查找
B-树
1.2排序
第8章.pdf
1.2.1插入排序
2413553.html
算法描述
假定n是数组的长度，
首先假设第一个元素被放置在正确的位置上，这样仅需从1-n-1范围内对剩余元素进行排序。
对于每次遍历，从0-i-1范围内的元素已经被排好序，
每次遍历的任务是：
通过扫描前面已排序的子列表，将位置i处的元素定位到从0到i的子列表之内的正确的位置上。
将arr[i]复制为一个名为target的临时元素。
向下扫描列表，比较这个目标值target与arr[i-1]、arr[i-2]的大小，依次类推。
这个比较过程在小于或等于目标值的第一个元素（arr[j]）处停止，或者在列表开始处停止（j=0）。
在arr[i]小于前面任何已排序元素时，后一个条件（j=0）为真，
因此，这个元素会占用新排序子列表的第一个位置。
在扫描期间，大于目标值target的每个元素都会向右滑动一个位置（arr[j]=arr[j-1]）。
一旦确定了正确位置j，
目标值target（即原始的arr[i]）就会被复制到这个位置。
与选择排序不同的是，插入排序将数据向右滑动，并且不会执行交换。
效率分析
稳定
空间复杂度O
（1）
时间复杂度O（n2）
最差情况：
反序，需要移动n*（n-1）/2个元素
最好情况：
正序，不需要移动元素
数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O（n）；
插入排序最坏情况运行时间和平均情况运行时间都为O（n2）。
通常，插入排序呈现出二次排序算法中的最佳性能。
对于具有较少元素（如n<
=15）的列表来说，二次算法十分有效。
在列表已被排序时，插入排序是线性算法O（n）。
在列表“近似排序”时，插入排序仍然是线性算法。
在列表的许多元素已位于正确的位置上时，就会出现“近似排序”的条件。
通过使用O（nlog2n）效率的算法（如快速排序）对数组进行部分排序，
然后再进行选择排序，某些高级的排序算法就是这样实现的。
数组版
template<
classRecord>
voidSortable_list<
Record>
:
insertion_sort（）
{
intfirst_unsorted;
intposition;
Recordcurrent;
for（first_unsorted=1;
frst_unsorted<
count;
first_unsorted++）
if（entry[first_unsorted]<
entry[first_unsorted-1]）
position=first_unsorted;
current=entry[first_unsorted];
do{
entry[position]=entry[position-1];
position--;
}
while（position>
0&
&
entry[position-1]>
current）;
entry[position]=current;
链式版
只需要把未排序的鱼啊元素与原链断开，然后插入到应有的位置即可
1.2.2选择排序
一、介绍
Incomputerscience,selectionsortisasortingalgorithm,specificallyanin-placecomparisonsort.IthasO（n2）timecomplexity,makingitinefficientonlargelists,andgenerallyperformsworsethanthesimilarinsertionsort.Selectionsortisnotedforitssimplicity,andithasperformanceadvantagesovermorecomplicatedalgorithmsincertainsituations,particularlywhereauxiliarymemoryislimited.
Thealgorithmdividestheinputlistintotwoparts:
thesublistofitemsalreadysorted,whichisbuiltupfromlefttorightatthefront（left）ofthelist,andthesublistofitemsremainingtobesortedthatoccupytherestofthelist.Initially,thesortedsublistisemptyandtheunsortedsublististheentireinputlist.Thealgorithmproceedsbyfindingthesmallest（orlargest,dependingonsortingorder）elementintheunsortedsublist,exchangingitwiththeleftmostunsortedelement（puttingitinsortedorder）,andmovingthesublistboundariesoneelementtotheright.
三、分析
Ø
Selectionsortdoeshavetheadvantageofpredictability:
Itsworst-casetimewilldifferlittlefromitsbest.
Thefunctionswapiscalledn-1times,andeachcalldoes3assignmentsofentries,foratotalcountof3（n-1）.
Thereare（n-1）+（n-2）+…+1=（1/2）n（n-1）comparisonsofkeys,whichweapproximateto（
1/2）n^2+O（n）.
平均来说，插入排序所进行的比较哦啊次数大约仅是选择排序的一半，如果表内的元素较小，移动起来不慢的话，则插入排序会比选择排序快。
selection_sort（）
for（intposition=count-1;
position>
0;
position--）
intmax=max_key（0,position）;
swap（max,position）;
Thefunctionmax_key（）istofindthemaximumvalueinthepartthattheparametersgave.
1.2.3希尔排序
Shellsort.
结合插入排序和选择排序的优点，采用缩小增量的方法。
先把所有元素每隔n个进行分组并排序，然后再每个m个进行分组排序，直到每隔1个为止。
最后进行的是普通的插入排序。
shell_sort（）
intincrement,start;
increment=count;
increment=increment/3+1;
for（start=0;
start<
increment;
start++）
sort_interval（start,increment）;
while（increment>
1）;
函数sort_interval（start,increment）表示起始地址为start，增量为increment的插入排序。
1.2.4分而治之排序
voidSortable_list:
sort（）
ifthlisthaslengthgreaterthan1
partitionthelistintolowlist,highlist;
lowlist.sort（）;
highlist.sort（）;
combine（lowlist,highlist）;
快速排序
每次选择一个支点（pivot），将整个序列按照大于或者等于支点和小于支点的规则分为两个部分。
依次递归至所分成的部分的元素数目为1为止。
以下是顺序实现的快速排序伪代码
iflow_position<
high_position
seperatethelistintotwopartionwiththepivotbetweenlow_positionandhigh_position.
recursivelydotheaboveoperation.
endif.
归并排序
Conceptually,amergesortworksasfollows:
Dividetheunsortedlistintonsublists,eachcontaining1element（alistof1elementisconsideredsorted）.
Repeatedlymergesubliststoproducenewsortedsublistsuntilthereisonly1sublistremaining.Thiswillbethesortedlist.
归并排序的主要操作有：
1.将序列分成两部分；
2.将两个部分进行排序整合；
3.递归以上操作直至分成两个部分之后只剩一个元素。
顺序实现的归并排序算法在空间上会消耗较多。
1.2.5堆排序
首先，对序列进行堆初始化，因为堆排序仅适用于顺序表。
然后，向堆中添加元素时，先添加到堆的最末尾。
然后一路回溯至堆根部。
回溯过程中，判断是否满足堆的条件。
堆排序的时间复杂度为O（nlogn）.
1.2.6树排序
1.2.7拓扑排序
7714519
1.前置条件
G是一个无有向环的有向图。
则G的拓扑次序是G中所有顶点的一个顺序排列
2.偏序和全序
3.常用的算法有Kahn算法和DFS算法
两者区别
Kahn算法不需要检测图为DAG，如果图为DAG，那么在出度为0的集合为空之后，图中还存在没有被移除的边，这就说明了图中存在环路。
而基于DFS的算法需要首先确定图为DAG，当然也能够做出适当调整，让环路的检测和拓扑排序同时进行，毕竟环路检测也能够在DFS的基础上进行。
二者的复杂度均为O（V+E）。
广度优先算法
一、无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋（即入度为零）的顶点，其抽象算法可描述为：
NonPreFirstTopSort（G）{//优先输出无前趋的顶点while（G中有入度为0的顶点）do{从G中选择一个入度为0的顶点v且输出之；
从G中删去v及其所有出边；
}if（输出的顶点数目<
|V（G）|）//若此条件不成立，则表示所有顶点均已输出
，排序成功。
Error（"
G中存在有向环，排序失败！
"
）；
深度优先算法
一、pseudocode
thatwillcontainthesortednodes
S←Setofallnodeswithnooutgoingedges
foreachnodeninSdo
visit（n）
functionvisit（noden）
ifnhasnotbeenvisitedyetthen
marknasvisited
foreachnodemwithanedgefrommtondo
visit（m）
addntoL
二、codeinC++
（见文档链接）
三、继的顶点优先拓扑排序方法1、思想方法该方法的每一步均是输出当前无后继（即出度为0）的顶点。
对于一个有向图，按此方法输出的序列是逆拓扑次序。
因此设置一个栈（或向量）T来保存输出的顶点序列，即可得到拓扑序列。
若T是栈，则每当输出顶点时，只需做入栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。
若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。
2、抽象算法描述算法的抽象描述为：
NonSuccFirstTopSort（G）{//优先输出无后继的顶点while（G中有出度为0的顶点）do{从G中选一出度为0的顶点v且输出v；
从G中删去v及v的所有人边}if（输出的顶点数目<
|V（G）|）Error（"
G中存在有向环，排序失败!
Kahn算法
一、eudocode
L←Emptylistthatwillcontainthesortedelements
S←Setofallnodeswithnoincomingedges
whileSisnon-emptydo
removeanodenfromS
addntotailofL
foreachnodemwithanedgeefromntomdo
removeedgeefromthegraph
ifmhasnootherincomingedgesthen
insertmintoS
ifgraphhasedgesthen
returnerror（graphhasatleastonecycle）
else
returnL（atopologicallysortedorder）
二、注意
1.需要记录的有：
顶点的连接关系、入度为0的顶点集合、存放排好序的顶点
2.需要的方法：
判断顶点入度是否为0、移走一条边、统计排好序的顶点
1.3表格信息检索
1.3.1基数排序
1.3.2哈希排序
13351072_郑泽丰_10__1
worst-casetimeforsearch,insert,anddeleteisO（size）;
ExpectedtimeisO
（1）.
IdealHashing
•Usesa1Darray（ortable）table[0:
b-1].
–Eachpositionofthisarrayisabucket.
–Abucketcannormallyholdonlyonerecord.
•Usesahashfunctionfthatconvertseachkeykintoanindexintherange[0,b-1].
–f（k）isthehomebucketforkeyk.
•Everyrecord（key,element）isstoredinitshomebuckettable[f[key]].
•Acollisionoccurswhenthehomebucketforanewrecordisoccupiedbyarecordwithadifferentkey.
•Anoverflowoccurswhenthereisnospaceinthehomebucketforthenewpair.
•Whenabucketcanholdonlyonerecord,collisionsandoverflowsoccurtogether.
•Needmethodstohandlecollisions（andoverflows）.
HashTableIssues
•Size（numberofbuckets）ofhashtable.
•Choiceofhashfunction.
•collisionshandlingmethod.
Twoprincipalcriteria:
Itshouldbeeasyandquicktocompute.
–Convertkeyintoanintegerincasethekeyisnotaninteger.
•DonebythemethodhashCode（）.
Itshouldachieveanevendistributionofthekeysthatactuallyoccuracrosstherangeofindices.
–f（k）isanintegerintherange[0,b-1],wherebisthenumberofbucketsinthetable.
choosingahashfunction
1.Truncation
●Thefirst,second,andfifthdigitsfromtherightmightmakethehashfunction,sothat21296876mapsto976.
2.Folding
●21296876mapsto212+968+76=1256.
3.ModularArithmetic
●Thebestchoiceformodulusisoften,butnotalways,aprimenumber.
CollisionResolutionwithOpenAddress
Clustering
LinearProbing
IncrementFunctions
QuadraticProbing
Key-DependentIncrements
RandomProbing
1.4图的遍历
1.4.1广度优先搜索
1.Discription:
VisitstartvertexandputintoaFIFOqueue.
Repeatedlyremoveavertexfromthequeue,visititsunvisitedadjacentvertices,putnewlyvisitedverticesintothequeue.
2.Property
Allverticesreanchablefromthestartvertex（includingthestartvertex）arevisited.
1.4.2深度优先搜索
1.pseudocode:
depthFirstSearch（v）
Lablevertexvasreached.
for（eachunreachedvertexuadjacenctfromv）
depthFirstSearch（u）;
2.prpgerties
samecomplexityasBFS;
1.5贪心算法
1.5.1最短路径
uid-27164517-id-3287891.html
Dijkstra算法
uid-20384806-id-1954190.html
1.单源最短路径
2.有向图或者无向图
3.所有边权非负
Letthenodeatwhichwearestartingbecalledtheinitialnode.LetthedistanceofnodeYbethedistancefromtheinitialnodetoY.Dijkstra'
salgorithmwillassignsomeinitialdistancevaluesandwilltrytoimprovethemstepbystep.
1.Assigntoeverynodeatentativedistancevalue:
setittozeroforourinitialnodeandtoinfi
升级会员 