數(shù)據(jù)結(jié)構(gòu)與算法常用詞匯

數(shù)據(jù)結(jié)構(gòu)與算法DataStructures緒論Section1Introduction數(shù)據(jù)元素XE"數(shù)據(jù)元素"dataelement數(shù)據(jù)對(duì)象XE"數(shù)據(jù)對(duì)象"dataobject數(shù)據(jù)類型XE"數(shù)據(jù)類型"datatype抽象XE"抽象"\y"chōuxiàng"abstract*數(shù)據(jù)結(jié)構(gòu)XE"數(shù)據(jù)結(jié)構(gòu)"datastructure*邏輯結(jié)構(gòu)XE"邏輯結(jié)構(gòu)"logicalstructure*物理結(jié)構(gòu)XE"物理結(jié)構(gòu)"physicalstructure*存儲(chǔ)結(jié)構(gòu)XE"存儲(chǔ)結(jié)構(gòu)"storagestructure*順序(存儲(chǔ)結(jié)構(gòu))XE"順序(存儲(chǔ)結(jié)構(gòu))"sequential/〔storagestructure〕*鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu))XE"鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu))"linked〔storagestructure〕算法分析XE"算法分析"analysisofanalgorithm*漸進(jìn)分析XE"漸進(jìn)分析"asymptoticanalysis漸進(jìn)復(fù)雜度XE"漸進(jìn)復(fù)雜度"\y"jiànjìnfùzádù"asymptoticcomplexity問題規(guī)模XE"問題規(guī)模"\y"wèntíguīmó"problemscope根本語(yǔ)句XE"根本語(yǔ)句"\y"jīběnyǔjù"basicstatement*大O記法XE"大O記法"Big-Onotation正確性XE"正確性"correctness可讀性XE"可讀性"readability魯棒性XE"魯棒性"robustness頻度XE"頻度"frequencycount計(jì)算理論XE"計(jì)算理論"computabilitytheory計(jì)算復(fù)雜性理論XE"計(jì)算復(fù)雜性理論"computationalcomplexitytheory*抽象數(shù)據(jù)類型XE"抽象數(shù)據(jù)類型"abstractdatatype(ADT):AbstractDataType(ADT)definesthedomainandstructureofthedata,alongwithacollectionofoperationsthataccessthedata.Itcreatesauser-defineddatatypewhoseoperationsspecifyhowaclientmaymanipulatethedata.抽象數(shù)據(jù)類型定義了數(shù)據(jù)取值范圍和表現(xiàn)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的操作。ADT給出了一種用戶定義的數(shù)據(jù)類型，其運(yùn)算符指明了用戶如何操作數(shù)據(jù)。*時(shí)間復(fù)雜度XE"時(shí)間復(fù)雜度"timecomplexity:Timecomplexityanalysislooksattheinternalstructureofanalgorithmbyanalyzingitsdesign,includingthenumberofcomparisontests,thenumberofiterations,thenumberofassignmentstatementsusedbythealgorithm.

時(shí)間復(fù)雜度分析旨在檢查算法的內(nèi)部結(jié)構(gòu)，所使用的方法是分析算法的設(shè)計(jì)，包括算法中使用的比擬、賦值等各種語(yǔ)句的次數(shù)。Timecomplexityanalysisisindependentofanyparticularcomputersystem.Thecriteriameasurethecomputationalcomplexityofthealgorithmrelativeton,thenumberofdataitemsinthecollection.

時(shí)間復(fù)雜度分析是獨(dú)立于特定的計(jì)算機(jī)系統(tǒng)，它用算法處理的數(shù)據(jù)元素的個(gè)數(shù)n來衡量算法的計(jì)算復(fù)雜度。*空間復(fù)雜度XE"空間復(fù)雜度"spacecomplexity:Spacecomplexityisameasureoftherelativeamountofinternalmemoryusedbyanalgorithm.Itcandictatewhatkindofcomputeriscapableofrunningthealgorithmandtheoverallsystemefficiencyofthealgorithm.

空間復(fù)雜度用來測(cè)定算法需要的內(nèi)存空間大小，它可以用來說明算法適合在何種計(jì)算機(jī)上運(yùn)行及算法的總體系統(tǒng)性能。線性表Section2LinearLists直接前驅(qū)XE"直接前驅(qū)"immediatepredecessor直接后繼XE"直接后繼"immediatesuccessor隨機(jī)存取XE"隨機(jī)存取"\y"suíjīcúnqǔ"randomaccess順序存取XE"順序存取"\y"shùnxùcúnqǔ"sequentialaccess結(jié)點(diǎn)XE"結(jié)點(diǎn)"\y"jiédiǎn"node尾標(biāo)志XE"尾標(biāo)志"\y"wěibiāozhì"tailmark*線性鏈表XE"線性鏈表"linearlinkedlists鏈表XE"鏈表"linkedlist單鏈表XE"單鏈表"singlylinkedlists雙鏈表XE"雙鏈表"\y"shuāngliànbiǎo"doublylinkedlists頭指針XE"頭指針"headpointer尾指針XE"尾指針"\y"wěizhǐzhēn"rearpointer存儲(chǔ)密度XE"存儲(chǔ)密度"\y"cúnchǔmìdù"storagedensity*循環(huán)鏈表XE"循環(huán)鏈表"circularlinkedlists指示器XE"指示器"cursor靜態(tài)鏈表XE"靜態(tài)鏈表"implementinglinkedlistsusingarray間接尋址XE"間接尋址"\y"jiànjiēxúnzhǐ"indirectaddress*線性表XE"線性表"linearlists:Alinearlististhecollectionofobjectsthataresequentiallyaccessed.Ithasauniquefirstandlastelementandeachinterioritemhasauniquesuccessor.Alinearlistisageneraldescriptionforstructuresthatincludearrays,stacks,queues,andlinkedlists.

線性表是順序訪問的對(duì)象集合。它只有唯一一個(gè)頭元素和一個(gè)尾元素，中間各項(xiàng)都有唯一一個(gè)后繼。線性表是數(shù)組、堆棧、隊(duì)列和鏈表等結(jié)構(gòu)的統(tǒng)稱。*順序表XE"順序表"sequentiallist:Sequentiallistisakindofstoragestructureoflinearliststhatstoreselementsinasequentialorder.Thestructureholdsanarbitrarynumberofitems.Thesizeofthelistismodifiedbyaddingordeletinganitemfromthelist,andtheitemsinthelistarereferencedbytheirpositions.

順序表是線性表的一種存儲(chǔ)結(jié)構(gòu)，這種線性表的結(jié)構(gòu)存放著任意個(gè)數(shù)的元素。表的大小通過增加或刪除表中的元素來改變，表中元素通過其位置來訪問。

Inalinearlist,thefirstelementoccursattheheadorfrontofthelist,andthelastelementoccursattherearofthelist.Eachelementexceptthefirstandthelasthasauniquepredecessorandauniquesuccessor.

在線性表中，第一個(gè)元素位于表頭，最后一個(gè)元素是表尾，除第一個(gè)元素和最后一個(gè)元素外，每一個(gè)元素都有唯一的前趨和唯一的后繼。頭節(jié)點(diǎn)XE"頭節(jié)點(diǎn)"headnodeorheader:Anemptylinkedlistcontainsanode,whichhasanuninitializeddatafield.Thisnodeiscalledtheheaderandinitiallypointstoitself.Theroleoftheheaderistopointthefirst‘real’nodeinthelistandhencetheheaderisoftenreferredtoasasentinelnode.

一個(gè)空鏈表中包含一個(gè)結(jié)點(diǎn)，它有一個(gè)未經(jīng)初始化的數(shù)據(jù)域。該結(jié)點(diǎn)叫頭結(jié)點(diǎn)，初始化時(shí)它指向自己。頭結(jié)點(diǎn)的作用是指向表中第一個(gè)“真正的”結(jié)點(diǎn)，因此它常被稱為“哨位”結(jié)點(diǎn)。有序表XE"有序表"orderedlist:Anorderedlistisaspecialtypeoflistthatmaintainstheelementsinascendingorder.

有序表是一種特殊的表，其元素按升序排列。雙向鏈表XE"雙向鏈表"doublylinkedlists或bi-directionallinkedlists:Incaseswhereweneedtoaccessnodesineitherdirection,adoublylinkedlistishelpful.Anodeinadoublylinkedlistcontainstwopointersandthedatafield.

當(dāng)我們需要雙向訪問節(jié)點(diǎn)時(shí)，雙向鏈表是很有用的。雙向鏈表中的節(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)數(shù)據(jù)域。棧和隊(duì)列Section3StacksandQueues順序棧XE"順序棧"\y"shùnxùzhàn"sequentialstack鏈棧XE"鏈棧"\y"liànzhàn"linkedstack棧頂XE"棧頂"top棧底XE"棧底"bottom*后進(jìn)先出XE"后進(jìn)先出"LastInFirstOut(LIFO)上溢XE"上溢"overflow/表達(dá)式求值XE"表達(dá)式求值"expressionevaluation后綴表達(dá)式XE"后綴表達(dá)式"postfixexpression漢諾塔算法XE"漢諾塔算法"TowerofHanoialgorithm遞歸XE"遞歸"\y"dìguī"recursion隊(duì)頭(元素)XE"隊(duì)頭(元素)"front〔element〕隊(duì)尾〔元素〕XE"隊(duì)尾〔元素〕"rear(element)*先進(jìn)先出XE"先進(jìn)先出"FirstInFirstOut(FIFO)雙向隊(duì)列XE"雙向隊(duì)列"double-endedqueue*循環(huán)隊(duì)列XE"循環(huán)隊(duì)列"circularqueue鏈隊(duì)列XE"鏈隊(duì)列"\y"liànduìliè"linkedqueue共享XE"共享"share離散事件模擬XE"離散事件模擬"discreteeventsimulation*棧XE"棧"stack:Astackisalistofitemsthatareaccessibleatonlyoneendofthelist.Itemsareaddedordeletedfromthelistonlyatthetopofthestack.AstackissaidtohaveLIFO(last-in/first-out)ordering.

棧是一種只能在表的一端訪問元素的表，其元素只能從棧頂端增加或刪除。出入棧的順序?yàn)楹筮M(jìn)先出〔LIFO,last-in/first-out〕。

Astackstructurefeaturesoperationsthataddanddeleteitems.APushoperationaddsanitemtothetopofthestack.Theoperationofremovinganelementfromthestackissaidtopopthestack.

棧結(jié)構(gòu)就出增加和刪除元素的操作。壓入〔push〕操作往棧頂增加一個(gè)元素。從棧頂刪除一個(gè)元素的操作稱為彈出〔pop〕。遞歸過程XE"遞歸過程"recursiveprocedure:Analgorithmisdefinedrecursivelyifitsdefinitionconsistsof:

〔1〕Oneormorestoppingconditionswhichcanbeevaluatedforcertainparameters.

〔2〕Arecursivestepinwhichacurrentvalueinthealgorithmcanbedefinedintermsofapreviousvalue.Eventually,therecursivestepmustleadtostoppingconditions.

如果一種算法的定義組成如下，那么它就是遞歸的。

〔1〕對(duì)應(yīng)于某些參數(shù)可以求值的一個(gè)或多個(gè)終止條件。

〔2〕一個(gè)遞歸步驟，它根據(jù)先前某次值求當(dāng)前值。遞歸步驟最終必須導(dǎo)致終止條件。*隊(duì)列XE"隊(duì)列"queue:Aqueueisadatastructurethatstoreselementsinalistandpermitsdataaccessonlyatthetwoendsofthelist.Anelementisinsertedattherearofthelistandisdeletedfromthefrontofthelist.

隊(duì)列是以表形式存放元素，但只允許在表的兩端訪問元素的數(shù)據(jù)結(jié)構(gòu)，其元素只能在表尾插入(入隊(duì))，在表頭刪除〔出隊(duì)〕。

ElementsareremovedfromthequeueinthesameorderinwhichtheyarestoredandhenceaqueueprovidesFIFO(first-in/first-out)orFCFS(first-come/first-served)ordering.

隊(duì)列刪除元素的順序和元素到達(dá)隊(duì)列的順序相同，可稱為先進(jìn)先出〔FIFO,first-in/first-out〕或先到先效勞〔FCFS，first-come/first-served〕。優(yōu)先級(jí)隊(duì)列XE"優(yōu)先級(jí)隊(duì)列"priorityqueue:AqueueisadatastructurethatprovidesaFIFOorderingofelements.Thequeueremovesthe“oldest”itemfromthelist.Applicationsoftenrequireamodifiedversionofqueuestorageinwhichtheitemofhighestpriorityisremovedfromthelist.Thisstructureiscalledapriorityqueue.

一個(gè)隊(duì)列是以FIFO順序訪問元素的數(shù)據(jù)結(jié)構(gòu)，它從中刪除“最老”的元素。實(shí)際應(yīng)用中常需要另外一種隊(duì)列，它刪除優(yōu)先級(jí)最高的元素，這種結(jié)構(gòu)我們稱為優(yōu)先級(jí)隊(duì)列。串和數(shù)組Section4StringsandArrays*子串XE"子串"substring主串XE"主串"\y"zhǔchuàn"primarystring空串XE"空串"nullstring空格串XE"空格串"blankstring文本編輯XE"文本編輯"textediting模式XE"模式"\y"móshì"pattern存儲(chǔ)密度XE"存儲(chǔ)密度"storagedensity*三元組表XE"三元組表"listof3-tuples三元組順序表XE"三元組順序表"\y"sānyuánzǔshùnxùbiǎo"sequentiallistof3-tuples十字鏈表XE"十字鏈表"\y"shízìliànbiǎo"orthogonallist*特殊矩陣XE"特殊矩陣"specialmatrix*稀疏矩陣XE"稀疏矩陣"sparsematrix*串XE"串"string:Astringisaspecialformofanarraythatholdscharacterdatathatidentifynames,words,sentences,andsoforth.Ittreatsthecharactersasasingleentityandprovidesoperationstoaccesscharactersequenceswithinthestring.

串是一種特殊形式的數(shù)組，它存放著組成名字、單詞、句子等的字符數(shù)據(jù)。它將字符視為單元實(shí)體，并提供得到字符在串中位置的操作。*模式匹配XE"模式匹配"patternmatching:Acommonpatternmatchingprobleminvolvessearchingforoneormoreoccurrencesofastringinatext.

一個(gè)最普通的模式匹配問題就是在文本文件中查找串。*數(shù)組XE"數(shù)組"array:Anarrayisanexampleofadatacollection.Itdefinesastructureddatatypethatholdsahomogeneouslistofitems.Aone-dimensionalarrayisafinite,sequentiallistofelementsofthesamedatatype(homogeneousarray).Atwo-dimensionalarray,oftencalledamatrix,isastructureddatatypethatiscreatedbynestingone-dimensionalarrays.Itemsareaccessedbyrowandcolumnsindices.

數(shù)組是一個(gè)數(shù)據(jù)集的例子。它定義了一個(gè)可以存放多個(gè)相同類型元素的結(jié)構(gòu)化數(shù)據(jù)類型。一維數(shù)組是一個(gè)具有有限個(gè)相同數(shù)據(jù)類型元素的順序表〔同構(gòu)數(shù)組〕。二維數(shù)組通常成為矩陣，是一種由多個(gè)一維數(shù)組合成的結(jié)構(gòu)化數(shù)據(jù)類型。其元素通過行和列下標(biāo)存取。

Theelementtypeofanarraycanincludenotonlythebuilt-indatatypesuchasintorcharbutalsouser-definedclasstype.

數(shù)組元素的類型不但可以是原始類型如整型或字符型，也可以是用戶定義的類類型。一維數(shù)組的存儲(chǔ)XE"一維數(shù)組的存儲(chǔ)"storageofone-dimensionalarray:AC++one-dimensionalarrayAislogicallystoredasaconsecutivesequenceofitemsinmemory.Eachitemisofthesamedatatype.

C++的一維數(shù)組A邏輯上在內(nèi)存中連續(xù)存放，其每個(gè)元素的類型相同。二維數(shù)組的存儲(chǔ)XE"二維數(shù)組的存儲(chǔ)"storageoftwo-dimensionalarrays:Atwo-dimensionalarraycanbeinitializedbyassigningtheitemsarowatatime.

二維數(shù)組可以通過一次賦值一行元素來初始化。樹和二叉樹Section5TreesandBinaryTrees根XE"根"root結(jié)點(diǎn)XE"節(jié)點(diǎn)"node〔結(jié)點(diǎn)的〕度XE"〔節(jié)點(diǎn)的〕度"degree葉子結(jié)點(diǎn)XE"葉子"leafnode孩子結(jié)點(diǎn)XE"孩子"childrennode分支結(jié)點(diǎn)branchnode雙親XE"雙親"parents兄弟XE"兄弟"sibling/祖先XE"祖先"ancestors/子孫XE"子孫"descendant*深度XE"深度"depth*層、層次XE"層、層次"level有序樹XE"有序樹"orderedtree無(wú)序樹XE"無(wú)序樹"unorderedtree*森林XE"森林"forest〔表達(dá)式的〕中綴表示XE"〔表達(dá)式的〕中綴表示"infixnotation〔表達(dá)式的〕后綴表示XE"〔表達(dá)式的〕后綴表示"postfixnotation同構(gòu)XE"同構(gòu)"\y"tónggòu"isomorphic遍歷XE"遍歷"\y"biànlì"traverse雙親表示法XE"雙親表示法"\y"shuāngqīnbiǎoshìfǎ"parentexpression孩子表示法XE"孩子表示法"\y"háizibiǎoshìfǎ"childexpression雙親孩子表示法XE"雙親孩子表示法"\y"shuāngqīnháizibiǎoshìfǎ"parent-childexpression孩子兄弟表示法XE"孩子兄弟表示法"\y"háizixiōngdìbiǎoshìfǎ"children-brotherexpression*先序遍歷XE"先序遍歷"preordertraversal*后序遍歷XE"后序遍歷"postordertraversal*完全二叉樹XE"完全二叉樹"completebinarytree*滿二叉樹XE"滿二叉樹"fullbinarytree二叉鏈表XE"二叉鏈表"\y"èrchāliànbiǎo"binarylinkedlist三叉鏈表XE"三叉鏈表"\y"sānchāliànbiǎo"tridentlinkedlist判定樹XE"判定樹"decisiontree線索XE"線索"\y"xiànsuǒ"thread*線索二叉樹XE"線索二叉樹"threadedbinarytrees線索鏈表XE"線索鏈表"threadedlists等價(jià)關(guān)系XE"等價(jià)關(guān)系"equivalencerelation等價(jià)類XE"等價(jià)類"equivalenceclass*哈夫曼樹XE"哈夫曼樹"Huffmantree*最優(yōu)樹XE"最優(yōu)樹"optimaltree前綴編碼XE"前綴編碼"prefixcode哈夫曼編碼XE"哈夫曼編碼"Huffmancode*路徑XE"路徑"path路徑長(zhǎng)度XE"路徑長(zhǎng)度"\y"lùjìngchángdù"pathlength帶權(quán)路徑長(zhǎng)度XE"帶權(quán)路徑長(zhǎng)度"\y"dàiquánlùjìngchángdù"weightedpathlength〔表達(dá)式的〕前綴表示XE"〔表達(dá)式的〕前綴表示"prefixnotation*樹的遍歷XE"樹的遍歷"treetraversal樹的計(jì)數(shù)XE"樹的計(jì)數(shù)"enumerationoftree*樹XE"樹"tree:Atreeisahierarchicalstructurethatconsistsofnodesemanatingfromaroot.Atreestructureischaracterizedasasetofnodesthatoriginatesfromauniquestartingnodecalledtheroot.Eachnodeinatreeistherootofasubtree,whichisdefinedbythenodeandalldescendantsofthenode.

樹是一種由根發(fā)散的節(jié)點(diǎn)所組成的層次結(jié)構(gòu)由假設(shè)干個(gè)節(jié)點(diǎn)和葉子組成的。它的特點(diǎn)是它是由唯一的起始點(diǎn)“根〔root〕”開始的“節(jié)點(diǎn)”集合。樹中的每個(gè)節(jié)點(diǎn)都是一棵“子樹”的根，這個(gè)子樹是由節(jié)點(diǎn)和節(jié)點(diǎn)的后代定義的。*二叉樹XE"二叉樹"binarytree:Abinarytreeisarestrictedclassoftreeinwhicheachparenthasnomorethantwochildren.Abinarytreeisarecursivestructure.Eachnodeistherootofitsownsubtreeandhaschildren,whicharerootsofthetreecalledtheleftandrightsubtreesofthenode,respectively.

叉樹是一種特定的樹，在這類樹中，每個(gè)雙親的孩子數(shù)不超過兩個(gè)。二叉樹是一種遞歸結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)都是其子樹的根并有孩子，這些孩子分別是被稱為節(jié)點(diǎn)的左子樹和右子樹的根。圖和廣義表Section6GraphsandGeneralizedLists入度XE"入度"in-degree出度XE"出度"out-degree連通圖XE"連通圖"connectedgraph連通分量XE"連通分量"connectedcomponent強(qiáng)連通圖XE"強(qiáng)連通圖"stronglyconnectedgraph強(qiáng)連通分量XE"強(qiáng)連通分量"stronglyconnectedcomponent*鄰接矩陣XE"鄰接矩陣"adjacencymatrix*鄰接表XE"鄰接表"adjacencylists頂點(diǎn)XE"頂點(diǎn)"vertex邊XE"邊"edge弧XE"弧"arc弧尾XE"弧尾"tail弧頭XE"弧頭"head*無(wú)向圖XE"無(wú)向圖"undirectedgraph*有向圖XE"有向圖"directedgraph簡(jiǎn)單圖XE"簡(jiǎn)單圖"\y"jiǎndāntú"simplegraph完全圖XE"完全圖"completedgraph*鄰接多重表XE"鄰接多重表"adjacencymulti-lists*圖的遍歷XE"圖的遍歷"traversinggraph稀疏圖XE"稀疏圖"sparsegraph稠密圖XE"稠密圖"densegraph子圖subgraph*生成樹XE"生成樹"spanningtree*生成森林XE"生成森林"spanningforest*最小生成樹XE"最小生成樹"minimalspanningtree普里姆算法XE"普里姆算法"\y"pǔlǐmǔsuànfǎ"Primalgorithm克魯斯卡爾算法XE"克魯斯卡爾算法"\y"kèlǔsīkǎěrsuànfǎ"Kruskalalgorithm關(guān)節(jié)點(diǎn)XE"關(guān)節(jié)點(diǎn)"articulationpoint重連通圖XE"重連通圖"bi-connectedgraph*有向無(wú)環(huán)圖XE"有向無(wú)環(huán)圖"directedacyclicgraph*拓?fù)渑判騒E"拓?fù)渑判?topologicalsort拓?fù)湫蛄蠿E"拓?fù)溆行?topologicalorderAOV-網(wǎng)XE"AOV-網(wǎng)"ActivityOnVertexnetworkAOE-網(wǎng)XE"AOE-網(wǎng)"ActivityOnEdgenetwork*關(guān)鍵路徑XE"關(guān)鍵路徑"criticalpath始點(diǎn)XE"始點(diǎn)"\y"shǐdiǎn"beginning源點(diǎn)XE"源點(diǎn)"\y"yuándiǎn"source終點(diǎn)XE"終點(diǎn)"\y"zhōngdiǎn"End匯點(diǎn)XE"匯點(diǎn)"\y"huìdiǎn"convergency關(guān)鍵活動(dòng)XE"關(guān)鍵活動(dòng)"\y"guānjiànhuódòng"criticalactivity*最短路徑XE"最短路徑"shortestpath二部圖XE"二部圖"bipartitegraph最大匹配XE"最大匹配"maximalmatching完全匹配XE"完全匹配"completematching增廣路徑XE"增廣路徑"augmentingpath*廣義表XE"廣義表"generalizedlists頭尾表示法XE"頭尾表示法"\y"tóuwěibiǎoshìfǎ"head-tailexpression*逆鄰接表XE"逆鄰接表"inverseadjacencylists*十字鏈表XE"十字鏈表"orthogonallist*圖XE"圖"graph:Agraphisageneralizedhierarchicalstructurethatiscomposedofasetofdataitemscalledverticesandasetofedgesthatconnectpairsofvertices.Graphsfindapplicationsinjobscheduling,transportation,andsoforth.

圖是一種一般化的層次結(jié)構(gòu)。它由一組叫作“頂點(diǎn)〔vertex〕”的數(shù)據(jù)項(xiàng)和一組連接各對(duì)頂點(diǎn)的“邊〔edge〕”所組成。它在作業(yè)調(diào)度、運(yùn)輸?shù)确矫嬗兄鴳?yīng)用。*深度優(yōu)先搜索XE"深度優(yōu)先搜索"Depth-FirstSearch(DFS):ThesearchalgorithmusesalistLtomaintainarecordofvisitedverticesandastackStostoreadjacentvertices.Afterplacingtheinitialvertexonthestack,webeginaniterativeprocessthatpopsavertexfromthestackandthenvisitsthevertex.Weterminatewhenthestackisemptyandreturnthelistofvisitedvertices.

搜索算法用表L維護(hù)被訪問頂點(diǎn)的記錄，用堆棧S存儲(chǔ)鄰接頂點(diǎn)。在將初始頂點(diǎn)放入堆棧以后，開始迭代過程，從堆棧中彈出一個(gè)頂點(diǎn)并訪問它。當(dāng)堆棧為空時(shí)過程終止并返回被訪問過的頂點(diǎn)表。*寬度優(yōu)先搜索XE"寬度優(yōu)先搜索"Breadth-FirstSearch(BFS):Thebreadth-firstsearchusesaqueueasdoesthelevelorderscanofabinarytree.Thealgorithmusesthetechniquesdevelopedforthedepth-firstsearch.Verticesareplacedinaqueueinsteadofastack.Aniterativeprocessremovesverticesfromthequeueuntilitisempty.

與二叉樹的逐層掃描一樣，寬度優(yōu)先搜索使用隊(duì)列。除此之外，該算法使用與深度優(yōu)先搜索相同的技術(shù)。即頂點(diǎn)是放到隊(duì)列中而非堆棧中。迭代過程從隊(duì)列中刪除頂點(diǎn)直到隊(duì)列空為止。查找Section7Searching*靜態(tài)查找表XE"靜態(tài)查找表"staticsearchtable*動(dòng)態(tài)查找表XE"動(dòng)態(tài)查找表"dynamicsearchtable主關(guān)鍵字XE"主關(guān)鍵字"primarykey次關(guān)鍵字XE"次關(guān)鍵字"secondkey*查找XE"查找"searching*平均查找長(zhǎng)度XE"平均查找長(zhǎng)度"AverageSearchLength(ASL)斐波那契查找XE"斐波那契查找"Fibonaccisearch斐波那契序列XE"斐波那契序列"Fibonaccinumbers*索引順序查找XE"索引順序查找"indexedsequentialsearch*分塊查找XE"分塊查找"blockingsearch*二叉排序樹XE"二叉排序樹"binarysorttree平衡因子XE"平衡因子"balancefactor平衡旋轉(zhuǎn)XE"平衡旋轉(zhuǎn)"balancerotation數(shù)字查找樹XE"數(shù)字查找樹"digitalsearchtree雙鏈樹XE"雙鏈樹"doublylinkedtree*哈希表XE"哈希表"hashtable同義詞XE"同義詞"synonym*沖突XE"沖突"collision沖突的解決XE"沖突的解決"collisionresolution*開放定址XE"開放定址"openaddressing*線性探測(cè)XE"線性探測(cè)"linearprobing*二次探測(cè)XE"二次探測(cè)"quadraticprobing*偽隨機(jī)探測(cè)XE"偽隨機(jī)探測(cè)"randomprobing*鏈地址法XE"鏈地址法"chaining-addressmethod*直接定址XE"直接定址"immediatelyallocate隨機(jī)數(shù)法XE"隨機(jī)數(shù)法"randomnumbermethod折疊法XE"折疊法"foldingmethod移位疊加XE"移位疊加"shiftfolding數(shù)字分析法XE"數(shù)字分析法"digitanalysismethod間界疊加XE"間界疊加"foldingattheboundaries平方取中XE"平方取中"mid-squaremethod估值函數(shù)XE"估值函數(shù)"evaluationfunction*再哈希XE"再哈希"rehash*裝填因子XE"裝填因子"loadfactor查找表XE"查找表"searchtables:Searchtablesareaseriesofliststructuresthatallowtheclienttosearchforandretrievedata.Ineachstructure,aFindmethodtakesakeyandtraversesthelistlookingforamatchingdataitem.

查找表是一系列允許客戶程序搜索和取出數(shù)據(jù)的表結(jié)構(gòu)。每種結(jié)構(gòu)都有一個(gè)Find〔查找〕方法，它以關(guān)鍵字為參數(shù)，遍歷表以找到匹配的數(shù)據(jù)項(xiàng)。*順序查找XE"順序查找"sequentialsearch:Asequentialsearchlooksforaniteminalistusingatargetvaluecalledthekey.Thealgorithmbeginsatauser-suppliedindex,calledstart,andtraversestheremainingitemsinthelist,comparingeachitemwiththekey.Thescancontinuesuntilthekeyisfoundorthelistisexhausted.Ifthekeyisfound,thefunctionreturnstheindexofthematchedelementinthelist;otherwise,thevalue–1isreturned.

順序查找用一個(gè)稱為關(guān)鍵字Key的目標(biāo)值來查找表中的元素。該算法從用戶給出的起點(diǎn)開始，遍歷表中的后續(xù)元素，并將元素值與Key比擬，直到元素值與Key值相等或到表尾。如果找到Key值，函數(shù)返回該元素在表中的位置；否那么，返回-1。有序表XE"有序表"orderedlist:Anorderedlistisaspecialtypeoflistthatmaintainstheelementsinascendingorder.

有序表是一種特殊的表，其元素按升序排列。*折半查找XE"折半查找"binarysearch:Thesequentialsearchappliestoanylist.Ifthelistisordered,analgorithm,calledthebinarysearch,providesanimprovedsearchtechnique.

順序查找可適用于任意表。假設(shè)被查找的表有序，那么可用折半查找算法來查找，它是一種改良的查找算法。*二叉查找樹XE"二叉查找樹"binarysearchtree:Inabinarysearchtree,foreachnode,thedatavaluesintheleftsubtreearelessthanthevalueofthenodeandthedatavaluesintherightsubtreearegreaterthanorequaltothevalueofthenode.

在二叉查找樹中，對(duì)每個(gè)節(jié)點(diǎn)，其左子樹中的數(shù)據(jù)值都小于節(jié)點(diǎn)本身的值，而右子樹中的數(shù)據(jù)值都大于或等于節(jié)點(diǎn)的值。*平衡二叉樹〔AVL樹〕XE"平衡二叉樹〔AVL樹〕"balancedbinarytree或height-balancedtree:Binarysearchtreeisdesignedforrapidaccesstodata.Ideally,thetreeisreasonablybalancedandhasheightapproximatelyO(log2n).Withsomedata,however,abinarysearchtreecanbedegenerate.Inthatcase,theheightisO(n)andaccesstothedataissignificantlyslowed.WedevelopAVLtreeinwhicheverynodeisheight-balanced.BythiswemeanthatforeachnodeinanAVLtree,thedifferenceinheightofitstwosubtreeisatmost1.

二叉搜索樹是為快速訪問數(shù)據(jù)而設(shè)計(jì)的。理想情況下，樹是平衡分布的，其高度為O(log2n)。但對(duì)有些數(shù)據(jù)來說，二叉搜索樹也可能是退化的。那時(shí)樹高將是O(n)，訪問數(shù)據(jù)的速度將明顯變慢。我們要設(shè)計(jì)的是各節(jié)點(diǎn)具有平衡高度的AVL樹。也就是說，在AVL樹中任一節(jié)點(diǎn)的兩個(gè)子樹的高度差最多為1。*哈希函數(shù)XE"哈希函數(shù)"hashfunction:Inmostapplications,akeyisusedtoprovideanindirectreferencetothedata.Afunction,calledahashfunction,mapsthekeyintoarangeofintegersandthenusestheintegervaluetoaccessthedata.

在多數(shù)應(yīng)用中，關(guān)鍵字用來提供對(duì)數(shù)據(jù)的間接引用。哈希函數(shù)是將關(guān)鍵字映射到一定范圍的整數(shù)內(nèi)，然后用整數(shù)值來訪問數(shù)據(jù)。

Ahashfunctionmustmapakeytoaintegervalueintherange0ton-1.Itsdesignshouldlimitcollisionsandguaranteeefficientexecution.

哈希函數(shù)必須將關(guān)鍵字映射為0到n-1范圍內(nèi)的整數(shù)值。其設(shè)計(jì)必須考慮減少?zèng)_突并保證執(zhí)行效率。除留余數(shù)法XE"除留余數(shù)法"divisionmethod:Thedivisionmethodisthemostcommonlyusedhashingtechnique,requiringtwosteps.Firstthekeymustbetransformedintoanintegerandthenthevaluemustbetelescopedintotherange0ton-1usingtheremainderoperator.Inpractice,thedivisionmethodisusedinmosthashingapplications.

除留取余法〔divisionmethod〕是最常用的哈希技術(shù)，它分為兩個(gè)步驟。首先必須將關(guān)鍵字轉(zhuǎn)換成整數(shù)值，然后再用求余數(shù)運(yùn)算符將這一值縮到0~n-1的范圍內(nèi)。在實(shí)際的哈希應(yīng)用中，除留取余法用得最多。排序Section8Sorting正序XE"正序"\y"zhèngxù"exactorder逆序XE"逆序"\y"nìxù"inverseorder反序XE"反序"\y"fǎnxù"anti-order穩(wěn)定XE"穩(wěn)定"\y"wěndìng"stable不穩(wěn)定XE"不穩(wěn)定"\y"búwěndìng"unstable單鍵排序XE"單鍵排序"\y"dānjiànpáixù"single-keysort多鍵排序XE"多鍵排序"\y"duōjiànpáixù"multiple-keysort*內(nèi)部排序XE"內(nèi)部排序"internalsorting*外部排序XE"外部排序"externalsorting*穩(wěn)定的排序法XE"穩(wěn)定的排序法"stablesortingmethod插入查找XE"插入查找"insertionsearch*插入排序XE"插入排序"insertionsort*直接插入排序XE"直接插入排序"straightinsertionsort折半插入排序XE"折半插入排序"binaryinsertionsort2-路插入排序XE"2-路插入排序"2-wayinsertionsort表插入排序XE"表插入排序"listinsertionsort*希爾排序XE"希爾排序"Shell’smethod*縮小增量排序XE"縮小增量排序"diminishingincrementsort歸并插入排序XE"歸并插入排序"mergeinsertionsort*起泡排序XE"起泡排序"bubblesort*快速排序XE"快速排序"quicksort簡(jiǎn)單(選擇排序)XE"簡(jiǎn)單(選擇排序)"simple(selectionsort)樹形(選擇排序)XE"樹形(選擇排序)"tree(selectionsort)錦標(biāo)賽排序XE"錦標(biāo)賽排序"tournamentsort*堆XE"堆"heap*堆排序XE"堆排序"heapsorting*基數(shù)排序XE"基數(shù)排序"radixsorting*最高位優(yōu)先XE"最高位優(yōu)先"MostSignificantDigitfirst(MSD)*最低位優(yōu)先XE"最低位優(yōu)先"LeastSignificantDigitfirst(LSD)*鏈?zhǔn)交鶖?shù)排序XE"鏈?zhǔn)交鶖?shù)排序"linkedradixsorting磁帶排序XE"磁帶排序"sortingwithtapes間隙XE"間隙"gap尋查時(shí)間XE"尋查時(shí)間"seektime等待時(shí)間XE"等待時(shí)間"latencytime傳輸時(shí)間XE"傳輸時(shí)間"transmissiontime段XE"段"segment歸并段XE"歸并段"mergingsegment有序段XE"有序段"sortedsegment延遲時(shí)間XE"延遲時(shí)間"delaytime字符組間的間隙XE"字符組間的間隙"InterRecordGap(IRC)塊間的間隙XE"塊間的間隙"InterBlockGap(IBG)多路歸并XE"多路歸并"multi-waymerge敗者樹XE"敗者樹"treeofloser置換-選擇排序XE"置換-選擇排序"replacementselectionsort并行操作處理XE"并行操作處理"handlingforparalleloperation最正確歸并樹XE"最正確歸并樹"optimalmergetree平衡歸并XE"平衡歸并"balancedmerge多步歸并XE"多步歸并"polyphasemerge廣義斐波那契序列XE"廣義斐波那契序列"generalizedFibonaccinumbers*排序XE"排序"sorting:Sortingistheprocessofarrangingagroupofdataelementsintosomedesiredorderaccordingtorulesdependentuponakeyorseveralkeyscontainedineachdataelement.

排序是根據(jù)每個(gè)數(shù)據(jù)元素中所含關(guān)鍵字所確定的規(guī)那么,將一組數(shù)據(jù)元素排列成某種所需次序的過程。*選擇排序XE"選擇排序"selectionsort:Givenagroupofdataitemsinrandomorder,theselectionsortrepeatedlyselectsthesmallestitemfromthegroupandmovesittoalistthatisforminginascendingorder.

對(duì)以隨機(jī)順序排列的一組數(shù)據(jù)項(xiàng)，選擇排序?qū)⒎磸?fù)地從組中挑選出最小的數(shù)據(jù)項(xiàng)并將它移到正在形成的按升序排列的表中。文件Section9File定長(zhǎng)(文件)XE"定長(zhǎng)(文件)"fixed-sizerecords不定長(zhǎng)(文件)XE"不定長(zhǎng)(文件)"variable-sizerecords單關(guān)鍵字(文件)XE"單關(guān)鍵字(文件)"onlyonekey多關(guān)鍵字(文件)XE"多關(guān)鍵字(文件)"withmorethanonekey*順序文件XE"順序文件"sequentialfile*索引順序文件XE"索引順序文件"indexedsequentialfile*索引文件XE"索引文件"indexedfile*索引順序存取方法XE"索引順序存取方法"IndexedSequentialAccessMethod(ISAM)*虛擬存儲(chǔ)存取方法XE"虛擬存儲(chǔ)存取方法"VirtualStorageAccessMethod(VSAM)控制區(qū)間XE"控制區(qū)間"controlinterval控制區(qū)域XE"控制區(qū)域"controlrange*散列文件XE"散列文件"hashedfile桶XE"桶"bucket多重表文件XE"多重表文件"multilistfile*倒排文件XE"倒排文件"invertedfile*文件XE"文件"file:Afileistherecordcollectionofthesametype.Thestoreddataontheexternaldevicealongwiththetransferoperationsdefineadatastructure,calleda(logical)file,thathastheimportantadvantageofholdinggreateramountsofinformationthantypicallyresidesinmemory.

文件是類型相同的記錄集合。外部設(shè)備上存儲(chǔ)的數(shù)據(jù)及轉(zhuǎn)換操作定義了一個(gè)〔邏輯〕文件數(shù)據(jù)結(jié)構(gòu)。它在存放大量信息方面比傳統(tǒng)的只在內(nèi)存駐留信息方法占有很大優(yōu)勢(shì)。

Twotypesofdiskfilesaretextfilesandbinaryfiles.AtextfilecontainsASCIIcharactersandisprintablewhereasabinaryfilecontainspurebinarydata.

磁盤文件有兩種類型：文本文件和二進(jìn)制文件。文本文件中存放可打印的ASCII字符，而二進(jìn)制文件中存放純粹的二進(jìn)制數(shù)據(jù)。記錄XE"記錄"rec