數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)整理資料

1、數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)整理資料數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)整理0、?？蓟A(chǔ)必知必會(huì)A. 排序:排序有幾種,各種排序的比較,哪些排序是穩(wěn)定的,快排的算法;B. 查找:哈希查找、二叉樹(shù)查找、折半查找的對(duì)比,哈希映射和哈希表的區(qū)別?C. 鏈表和數(shù)組的區(qū)別,在什么情況下用鏈表什么情況下用數(shù)組?D. 棧和隊(duì)列的區(qū)別?E. 多態(tài),舉例說(shuō)明;overload和override的區(qū)別?F. 字符串有關(guān)的函數(shù),比如讓你寫(xiě)一個(gè)拷貝字符串的函數(shù)啊,或者字符串反轉(zhuǎn)啊什么的。strcpy和memcpy?G. 繼承、多繼承?H. 面向?qū)ο笥惺裁春锰?I. 說(shuō)說(shuō)static的與眾不同之處,如果一個(gè)變量被聲明為static,它會(huì)被分配在哪

2、里?在什么時(shí)候分配空間等?J. 什么是虛函數(shù)、純虛函數(shù)、虛的析構(gòu)函數(shù),用途?K. 內(nèi)存泄漏及解決方法?網(wǎng)絡(luò)部分:OSI模型7層結(jié)構(gòu),TCP/IP模型結(jié)構(gòu)?B. TCP/UDP區(qū)別?C. TCP建立連接的步驟?D. 香農(nóng)定理?1、二叉樹(shù)三種遍歷的非遞歸算法（背誦版）本貼給出二叉樹(shù)先序、中序、后序三種遍歷的非遞歸算法,此三個(gè)算法可視為標(biāo)準(zhǔn)算法,直接用于考研答題。1. 先序遍歷非遞歸算法#definesize100typedefstructBitreeElemsize;inttop;SqStack;voidPreOrderUnrecBitreetSqStacks;StackInits;pt;whil

3、ep!null|!StackEmptyswhilep!null/遍歷左子樹(shù)visitep-data;pushs,p;pp-lchild;/endwhileif!StackEmptys/通過(guò)下一次循環(huán)中的內(nèi)嵌while實(shí)現(xiàn)右子樹(shù)遍歷ppops;pp-rchild;/endif/endwhile/PreOrderUnrec2. 中序遍歷非遞歸算法#definesize100typedefstructBitreeElemsize;inttop;SqStack;voidInOrderUnrecBitreetSqStacks;StackInits;pt;whilep!null|!StackEmptysw

4、hilep!null/遍歷左子樹(shù)pushs,p;pp-lchild;/endwhileif!StackEmptysppops;visitep-data;/訪(fǎng)問(wèn)根結(jié)點(diǎn)pp-rchild;/通過(guò)下一次循環(huán)實(shí)現(xiàn)右子樹(shù)遍歷/endif/endwhile/InOrderUnrec3. 后序遍歷非遞歸算法#definesize100typedefenumL,Rtagtype;typedefstructBitreeptr;tagtypetag;stacknode;typedefstructstacknodeElemsize;inttop;SqStack;/后序遍歷voidPostOrderUnrecBitr

5、eetpp-lchild; whileSqStacks;stacknodex;StackInits;pt;dowhilep!null/遍歷左子樹(shù)x.ptrp;x.tagL;/標(biāo)記為左子樹(shù)pushs,x;!StackEmptys&&s.Elems.top.tagRxpops;px.ptr;visitep-data;/tag為R,表示右子樹(shù)訪(fǎng)問(wèn)完畢,故訪(fǎng)問(wèn)根結(jié)點(diǎn)if!StackEmptyss.Elems.top.tagR;/遍歷右子樹(shù)ps.Elems.top.ptr-rchild;while!StackEmptys;/PostOrderUnrec4. 層次遍歷算法/二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)

6、structBinaryTreeintvalue;/不寫(xiě)模板了,暫時(shí)用整形代替節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型BinaryTree*left;BinaryTree*right;BinaryTree*root;/已知二叉樹(shù)的根節(jié)點(diǎn)/層次遍歷voidLevelconstBinaryTree*rootQueue*bufnewQueue;/定義一個(gè)空隊(duì)列,假設(shè)此隊(duì)列的節(jié)點(diǎn)數(shù)據(jù)類(lèi)型也是整形的BinaryTreet;/一個(gè)臨時(shí)變量buf.push_backroot;/令根節(jié)點(diǎn)入隊(duì)whilebuf.emptyfalse/當(dāng)隊(duì)列不為空pbuf.front;/取出隊(duì)列的第一個(gè)元素coutp-value''ifp-

7、leftNULL/若左子樹(shù)不空,則令其入隊(duì)q.pushp-left;ifp-right!NULL/若右子樹(shù)不空,則令其入隊(duì)q.pushp-right;buf.pop;/遍歷過(guò)的節(jié)點(diǎn)出隊(duì)coutendl;2、線(xiàn)性表(1) 性表的鏈?zhǔn)酱鎯?chǔ)方式及以下幾種常用鏈表的特點(diǎn)和運(yùn)算:單鏈表、循環(huán)鏈表,雙向鏈表,雙向循環(huán)鏈表。(2) 單鏈表的歸并算法、循環(huán)鏈表的歸并算法、雙向鏈表及雙向循環(huán)鏈表的插入和刪除算法等都是較為常見(jiàn)的考查方式。(3) 單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針以及索引存儲(chǔ)結(jié)構(gòu)的各自好處。3、棧與隊(duì)列你可以問(wèn)一下自己是不是已經(jīng)知道了以下幾點(diǎn):1棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的

8、概念,包括:順序棧,鏈棧,共享?xiàng)?循環(huán)隊(duì)列,鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)(請(qǐng)注意包括:存和取兩部分)的特點(diǎn)。2遞歸算法。棧與遞歸的關(guān)系,以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法:n!階乘問(wèn)題,fib數(shù)列問(wèn)題,hanoi問(wèn)題,背包問(wèn)題,二叉樹(shù)的遞歸和非遞歸遍歷問(wèn)題,圖的深度遍歷與棧的關(guān)系等。其中,涉及到樹(shù)與圖的問(wèn)題,多半會(huì)在樹(shù)與圖的相關(guān)章節(jié)中進(jìn)行考查。3棧的應(yīng)用:數(shù)值表達(dá)式的求解,括號(hào)的配對(duì)等的原理,只作原理性了解,具體要求考查此為題目的算法設(shè)計(jì)題不多。4循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿(mǎn)條件,循環(huán)隊(duì)列中入隊(duì)與出隊(duì)(循環(huán)隊(duì)列在插入時(shí)也要判斷其是否已滿(mǎn),刪除時(shí)要判斷其是否已空)算法?！狙h(huán)隊(duì)列的隊(duì)空隊(duì)滿(mǎn)條件為了方便

9、起見(jiàn),約定:初始化建空隊(duì)時(shí),令frontrear0,當(dāng)隊(duì)空時(shí):frontrear,當(dāng)隊(duì)滿(mǎn)時(shí):frontrear亦成立,因此只憑等式frontrear無(wú)法判斷隊(duì)空還是隊(duì)滿(mǎn)。有兩種方法處理上述問(wèn)題:(1)另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿(mǎn)。(2)少用一個(gè)元素空間,約定以“隊(duì)列頭指針front在隊(duì)尾指針rear的下一個(gè)位置上”作為隊(duì)列“滿(mǎn)”狀態(tài)的標(biāo)志。隊(duì)空時(shí):frontrear,隊(duì)滿(mǎn)時(shí):rear+1%sizefront】如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌,棧與隊(duì)列一章可以不看書(shū)了。注意,我說(shuō)的是可以不看書(shū),并不是可以不作題哦。/循環(huán)隊(duì)列的主要操作:1創(chuàng)建循環(huán)隊(duì)列2初始化循環(huán)隊(duì)列3判斷循環(huán)隊(duì)列是否為空4判

10、斷循環(huán)隊(duì)列是否為滿(mǎn)5入隊(duì)、出隊(duì)/空出頭尾之間的一個(gè)元素不用#include#include#defineSIZE100typedefstructintelemSIZE;intfront,rear;Quque;/定義隊(duì)頭intinitQueQuque*q/初始化*q-front0;*q-rear0;intisFullQuque*qifq-frontq-rear+1%SIZE/判滿(mǎn)空出一個(gè)元素不用劉勉剛return1;elsereturn0;intinsertQueQuque*q,intelemifisFull*qreturn-1;*q-elem*q-rearelem;*q-rear*q-rear

11、+1%SIZE;/插入return0;intisEmptyQuque*qifq-frontq-rear/判 空 return 1; else return 0;intdeleteQueQuque*q,int*pelemifisEmpty*qreturn0;*pelem*q-elem*q-front;*q-front*q-front+1%SIZE;return0;4、串串一章需要攻破的主要堡壘有:1. 串的基本概念,串與線(xiàn)性表的關(guān)系（串是其元素均為字符型數(shù)據(jù)的特殊線(xiàn)性表）,空串與空格串的區(qū)別,串相等的條件;2. 串的基本操作,以及這些基本函數(shù)的使用,包括:取子串,串連接,串替換,求串長(zhǎng)等等。運(yùn)用

12、串的基本操作去完成特定的算法是很多學(xué)校在基本操作上的考查重點(diǎn)。3.順序串與鏈串及塊鏈串的區(qū)別和聯(lián)系,實(shí)現(xiàn)方式。4 .KMP算法思想。KMP中next數(shù)組以及nextval數(shù)組的求法。明確傳統(tǒng)模式匹配算法的不足,明確next數(shù)組需要改進(jìn)?？赡苓M(jìn)行的考查方式是:求next和nextval數(shù)組值,根據(jù)求得的next或nextval數(shù)組值給出運(yùn)用KMP算法進(jìn)行匹配的匹配過(guò)程。5 、多維數(shù)組和廣義表矩陣包括:對(duì)稱(chēng)矩陣,三角矩陣,具有某種特點(diǎn)的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲(chǔ)方式:三元組,帶輔助行向量的二元組,十字鏈表存儲(chǔ)。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。6 、樹(shù)與二叉樹(shù)樹(shù)一

13、章的知識(shí)點(diǎn)包括:二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu),二叉樹(shù)遍歷的三種算法（遞歸與非遞歸）,在三種基本遍歷算法的基礎(chǔ)上實(shí)現(xiàn)二叉樹(shù)的其它算法,線(xiàn)索二叉樹(shù)的概念和線(xiàn)索化算法以及線(xiàn)索化后的查找算法,最優(yōu)二叉樹(shù)的概念、構(gòu)成和應(yīng)用,樹(shù)的概念和存儲(chǔ)形式,樹(shù)與森林的遍歷算法及其與二叉樹(shù)遍歷算法的聯(lián)系,樹(shù)與森林和二叉樹(shù)的轉(zhuǎn)換。1二叉樹(shù)的概念、性質(zhì)和存儲(chǔ)結(jié)構(gòu)考查方法可有:直接考查二叉樹(shù)的定義,讓你說(shuō)明二叉樹(shù)與普通雙分支樹(shù)左右子樹(shù)無(wú)序的區(qū)別;考查滿(mǎn)二叉樹(shù)和完全二叉樹(shù)的性質(zhì),普通二叉樹(shù)的五個(gè)性質(zhì):A. 第i層的最多結(jié)點(diǎn)數(shù),B. 深度為k的二叉樹(shù)的最多結(jié)點(diǎn)數(shù),C.n0n2+1的性質(zhì),D.n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度,E.順序存

14、儲(chǔ)二叉樹(shù)時(shí)孩子結(jié)點(diǎn)與父結(jié)點(diǎn)之間的換算關(guān)系（root從1開(kāi)始,則左為:2*i,右為:2*i+1)二叉樹(shù)的順序存儲(chǔ)和二叉鏈表存儲(chǔ)的各自?xún)?yōu)缺點(diǎn)及適用場(chǎng)合,二叉樹(shù)的三叉鏈表表示方法。2二叉樹(shù)的三種遍歷算法這一知識(shí)點(diǎn)掌握的好壞,將直接關(guān)系到樹(shù)一章的算法能否理解,進(jìn)而關(guān)系到樹(shù)一章的算法設(shè)計(jì)題能否順利完成。二叉樹(shù)的遍歷算法有三種:先序,中序和后序。其劃分的依據(jù)是視其每個(gè)算法中對(duì)根結(jié)點(diǎn)數(shù)據(jù)的訪(fǎng)問(wèn)順序而定。不僅要熟練掌握三種遍歷的遞歸算法,理解其執(zhí)行的實(shí)際步驟,并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。由于二叉樹(shù)一章的很多算法,可以直接根據(jù)三種遞歸算法改造而來(lái)（比如:求葉子個(gè)數(shù)）,所以,掌握了三種遍歷的非遞歸算法后

15、,對(duì)付諸如:“利用非遞歸算法求二叉樹(shù)葉子個(gè)數(shù)”這樣的題目就下筆如有神了。3可在三種遍歷算法的基礎(chǔ)上改造完成的其它二叉樹(shù)算法:求葉子個(gè)數(shù),求二叉樹(shù)結(jié)點(diǎn)總數(shù),求度為1或度為2的結(jié)點(diǎn)總數(shù),復(fù)制二叉樹(shù),建立二叉樹(shù),交換左右子樹(shù),查找值為n的某個(gè)指定結(jié)點(diǎn),刪除值為n的某個(gè)指定結(jié)點(diǎn),諸如此類(lèi)等等等等。如果你可以熟練掌握二叉樹(shù)的遞歸和非遞歸遍歷算法,那么解決以上問(wèn)題就是小菜一碟了。4線(xiàn)索二叉樹(shù):線(xiàn)索二叉樹(shù)的引出,是為避免如二叉樹(shù)遍歷時(shí)的遞歸求解。眾所周知,遞歸雖然形式上比較好理解,但是消耗了大量的內(nèi)存資源,如果遞歸層次一多,勢(shì)必帶來(lái)資源耗盡的危險(xiǎn),為了避免此類(lèi)情況,線(xiàn)索二叉樹(shù)便堂而皇之地出現(xiàn)了。對(duì)于線(xiàn)索二叉

16、樹(shù),應(yīng)該掌握:線(xiàn)索化的實(shí)質(zhì),三種線(xiàn)索化的算法,線(xiàn)索化后二叉樹(shù)的遍歷算法,基本線(xiàn)索二叉樹(shù)的其它算法問(wèn)題（如:查找某一類(lèi)線(xiàn)索二叉樹(shù)中指定結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)就是一類(lèi)?？碱}）。5最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）:最優(yōu)二叉樹(shù)是為了解決特定問(wèn)題引出的特殊二叉樹(shù)結(jié)構(gòu),它的前提是給二叉樹(shù)的每條邊賦予了權(quán)值,這樣形成的二叉樹(shù)按權(quán)相加之和是最小的。最優(yōu)二叉樹(shù)一節(jié),直接考查算法源碼的很少,一般是給你一組數(shù)據(jù),要求你建立基于這組數(shù)據(jù)的最優(yōu)二叉樹(shù),并求出其最小權(quán)值之和,此類(lèi)題目不難,屬送分題。6樹(shù)與森林:二叉樹(shù)是一種特殊的樹(shù),這種特殊不僅僅在于其分支最多為2以及其它特征,一個(gè)最重要的特殊之處是在于:二叉樹(shù)是有序的!即:二叉樹(shù)的

17、左右孩子是不可交換的,如果交換了就成了另外一棵二叉樹(shù)。樹(shù)與森林的遍歷,不像二叉樹(shù)那樣豐富,他們只有兩種遍歷算法:先根與后根（對(duì)于森林而言稱(chēng)作:先序與后序遍歷）。此二者的先根與后根遍歷與二叉樹(shù)中的遍歷算法是有對(duì)應(yīng)關(guān)系的:先根遍歷對(duì)應(yīng)二叉樹(shù)的先序遍歷,而后根遍歷對(duì)應(yīng)二叉樹(shù)的中序遍歷。二叉樹(shù)、樹(shù)與森林之所以能有以上的對(duì)應(yīng)關(guān)系,全拜二叉鏈表所賜。二叉樹(shù)使用二叉鏈表分別存放他的左右孩子,樹(shù)利用二叉鏈表存儲(chǔ)孩子及兄弟（稱(chēng)孩子兄弟鏈表）,而森林也是利用二叉鏈表存儲(chǔ)孩子及兄弟。7、圖1.圖的基本概念:圖的定義和特點(diǎn),無(wú)向圖,有向圖,入度,出度,完全圖,生成子圖,路徑長(zhǎng)度,回路,（強(qiáng)）連通圖,（強(qiáng)）連通分量等概

18、念。2.圖的幾種存儲(chǔ)形式:鄰接矩陣,（逆）鄰接表,十字鏈表及鄰接多重表。在考查時(shí),有的學(xué)校是給出一種存儲(chǔ)形式,要求考生用算法或手寫(xiě)出與給定的結(jié)構(gòu)相對(duì)應(yīng)的該圖的另一種存儲(chǔ)形式。3.考查圖的兩種遍歷算法:深度遍歷和廣度遍歷深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法,這兩個(gè)算法對(duì)圖一章的重要性等同于“先序、中序、后序遍歷”對(duì)于二叉樹(shù)一章的重要性。在考查時(shí),圖一章的算法設(shè)計(jì)題常常是基于這兩種基本的遍歷算法而設(shè)計(jì)的,比如:“求最長(zhǎng)的最短路徑問(wèn)題”和“判斷兩頂點(diǎn)間是否存在長(zhǎng)為K的簡(jiǎn)單路徑問(wèn)題”,就分別用到了廣度遍歷和深度遍歷算法。4.生成樹(shù)、最小生成樹(shù)的概念以及最小生成樹(shù)的構(gòu)造:PRIM算法和KRUSKA

19、L算法?？疾闀r(shí)，一般不要求寫(xiě)出算法源碼，而是要求根據(jù)這兩種最小生成樹(shù)的算法思想寫(xiě)出其構(gòu)造過(guò)程及最終生成的最小生成樹(shù)。5.拓?fù)渑判騿?wèn)題:拓?fù)渑判蛴袃煞N方法,一是無(wú)前趨的頂點(diǎn)優(yōu)先算法,二是無(wú)后繼的頂點(diǎn)優(yōu)先算法。換句話(huà)說(shuō),一種是“從前向后”的排序,一種是“從后向前”排。當(dāng)然,后一種排序出來(lái)的結(jié)果是“逆拓?fù)溆行颉钡摹?.關(guān)鍵路徑問(wèn)題:這個(gè)問(wèn)題是圖一章的難點(diǎn)問(wèn)題。理解關(guān)鍵路徑的關(guān)鍵有三個(gè)方面:一是何謂關(guān)鍵路徑;二是最早時(shí)間是什么意思、如何求;三是最晚時(shí)間是什么意思、如何求。簡(jiǎn)單地說(shuō),最早時(shí)間是通過(guò)“從前向后”的方法求的,而最晚時(shí)間是通過(guò)“從后向前”的方法求解的,并且,要想求最晚時(shí)間必須是在所有的最早時(shí)間

20、都已經(jīng)求出來(lái)之后才能進(jìn)行。在實(shí)際設(shè)計(jì)關(guān)鍵路徑的算法時(shí),還應(yīng)該注意以下這一點(diǎn):采用鄰接表的存儲(chǔ)結(jié)構(gòu),求最早時(shí)間和最晚時(shí)間要采用不同的處理方法,即:在算法初始時(shí),應(yīng)該首先將所有頂點(diǎn)的最早時(shí)間全部置為0。關(guān)鍵路徑問(wèn)題是工程進(jìn)度控制的重要方法,具有很強(qiáng)的實(shí)用性。7.最短路徑問(wèn)題:與關(guān)鍵路徑問(wèn)題并稱(chēng)為圖一章的兩只攔路虎。概念理解是比較容易的,關(guān)鍵是算法的理解。最短路徑問(wèn)題分為兩種:一是求從某一點(diǎn)出發(fā)到其余各點(diǎn)的最短路徑(單源最短路徑);二是求圖中每一對(duì)頂點(diǎn)之間的最短路徑。這個(gè)問(wèn)題也具有非常實(shí)用的背景特色,一個(gè)典型的應(yīng)該就是旅游景點(diǎn)及旅游路線(xiàn)的選擇問(wèn)題。解決第一個(gè)問(wèn)題用DIJSKTRA算法,解決第二個(gè)問(wèn)題

21、用FLOYD算法,注意區(qū)分。8 、查找(search)先弄清楚以下幾個(gè)概念:關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字的含義;靜態(tài)查找與動(dòng)態(tài)查找的含義及區(qū)別;平均查找長(zhǎng)度ASL的概念及在各種查找算法中的計(jì)算方法和計(jì)算結(jié)果,特別是一些典型結(jié)構(gòu)的ASL值,應(yīng)該記住。一般將search分為三類(lèi):在順序表上的查找;在樹(shù)表上的查找;在哈希表上的查找。(1)線(xiàn)性表上的查找:主要分為三種線(xiàn)性結(jié)構(gòu):順序表?傳統(tǒng)查找方法:逐個(gè)比較;有序順序表?二分查找法(注意適用條件以及其遞歸實(shí)現(xiàn)方法);索引順序表?對(duì)索引結(jié)構(gòu),采用索引查找算法。注意這三種表下的ASL值以及三種算法的實(shí)現(xiàn)。(2)樹(shù)表上的查找:樹(shù)表主要分為以下幾種:二叉排序樹(shù)(

22、即二叉查找樹(shù)),平衡二叉查找樹(shù)(AVL樹(shù)),B樹(shù),鍵樹(shù)。其中,尤以前兩種結(jié)構(gòu)為重,也有部分名校偏愛(ài)考B樹(shù)的。由于二叉排序樹(shù)與平衡二叉樹(shù)是一種特殊的二叉樹(shù)。二叉排序樹(shù),簡(jiǎn)言之,就是“左小右大”,它的中序遍歷結(jié)果是一個(gè)遞增的有序序列。平衡二叉排序樹(shù)是二叉排序樹(shù)的優(yōu)化,其本質(zhì)也是一種二叉排序樹(shù),只不過(guò),平衡排序二叉樹(shù)對(duì)左右子樹(shù)的深度有了限定:深度之差的絕對(duì)值不得大于1。對(duì)于二叉排序樹(shù),“判斷某棵二叉樹(shù)是否二叉排序樹(shù)”這一算法經(jīng)常被考到,可用遞歸,也可以用非遞歸。平衡二叉樹(shù)的建立也是一個(gè)?？键c(diǎn),但該知識(shí)點(diǎn)歸根結(jié)底還是關(guān)注的平衡二叉樹(shù)的四種調(diào)整算法,調(diào)整的一個(gè)參照是:調(diào)整前后的中序遍歷結(jié)果相同。B樹(shù)是二

23、叉排序樹(shù)的進(jìn)一步改進(jìn),也可以把B樹(shù)理解為三叉、四叉.排序樹(shù)。除B樹(shù)的查找算法外,應(yīng)該特別注意一下B樹(shù)的插入和刪除算法,因?yàn)檫@兩種算法涉及到B樹(shù)結(jié)點(diǎn)的分裂和合并,是一個(gè)難點(diǎn)。鍵樹(shù)(keywordtree),又稱(chēng)數(shù)字搜索樹(shù)(digitalsearchtree)或字符樹(shù)。trie樹(shù)也可說(shuō)等同于鍵樹(shù)或?qū)儆阪I樹(shù)的一種。鍵樹(shù)特別適用于查找英文單詞的場(chǎng)合。一般不要求能完整描述算法源碼,多是根據(jù)算法思想建立鍵樹(shù)及描述其大致查找過(guò)程。(3)基于哈希表的查找算法：哈希譯自“hash”一詞,意為“散列”或“雜湊”。哈希表查找的基本思想是:根據(jù)當(dāng)前待查找數(shù)據(jù)的特征,以記錄關(guān)鍵字為自變量,設(shè)計(jì)一個(gè)function,該函

24、數(shù)對(duì)關(guān)鍵字進(jìn)行轉(zhuǎn)換后,其解釋結(jié)果為待查的地址?；诠１淼目疾辄c(diǎn)有:哈希函數(shù)的設(shè)計(jì),沖突解決方法的選擇及沖突處理過(guò)程的描述。9 、內(nèi)部排序考查你對(duì)書(shū)本上的各種排序算法及其思想以及其優(yōu)缺點(diǎn)和性能指標(biāo)(時(shí)間復(fù)雜度)能否了如指掌。排序方法分類(lèi)有:插入、選擇、交換、歸并、計(jì)數(shù)等五種排序方法。(1)插入排序中又可分為:直接插入、折半插入、2路插入(?)、希爾排序。這幾種插入排序算法的最根本的不同點(diǎn),說(shuō)到底就是根據(jù)什么規(guī)則尋找新元素的插入點(diǎn)。直接插入是依次尋找,折半插入是折半尋找,希爾排序,是通過(guò)控制每次參與排序的數(shù)的總范圍“由小到大”的增量來(lái)實(shí)現(xiàn)排序效率提高的目的。(2)交換排序,又稱(chēng)冒泡排序,在交換排

25、序的基礎(chǔ)上改進(jìn)又可以得到快速排序?？焖倥判虻乃枷?一語(yǔ)以敝之:用中間數(shù)將待排數(shù)據(jù)組一分為二。（3）選擇排序可以分為:簡(jiǎn)單選擇、樹(shù)選擇、堆排序。選擇排序相對(duì)于前面幾種排序算法來(lái)說(shuō),難度大一點(diǎn)。這三種方法的不同點(diǎn)是,根據(jù)什么規(guī)則選取最小的數(shù)。簡(jiǎn)單選擇,是通過(guò)簡(jiǎn)單的數(shù)組遍歷方案確定最小數(shù);樹(shù)選擇,是通過(guò)“錦標(biāo)賽”類(lèi)似的思想,讓兩數(shù)相比,不斷淘汰較大（?。┱?最終選出最?。ù螅?shù);而堆排序,是利用堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì),通過(guò)堆元素的刪除、調(diào)整等一系列操作將最小數(shù)選出放在堆頂。堆排序中的堆建立、堆調(diào)整是重要考點(diǎn)。（4）歸并排序,是通過(guò)“歸并”這種操作完成排序的目的,既然是歸并就必須是兩者以上的數(shù)據(jù)集合才可

26、能實(shí)現(xiàn)歸并。所以,在歸并排序中,關(guān)注最多的就是2路歸并。算法思想比較簡(jiǎn)單,有一點(diǎn),要銘記在心:歸并排序是穩(wěn)定排序。（5）基數(shù)排序,是一種很特別的排序方法,也正是由于它的特殊,所以,基數(shù)排序就比較適合于一些特別的場(chǎng)合,比如撲克牌排序問(wèn)題等?；鶖?shù)排序,又分為兩種:多關(guān)鍵字的排序（撲克牌排序）,鏈?zhǔn)脚判颍ㄕ麛?shù)排序）?；鶖?shù)排序的核心思想也是利用“基數(shù)空間”這個(gè)概念將問(wèn)題規(guī)模規(guī)范、變小,并且,在排序的過(guò)程中,只要按照基排的思想,是不用進(jìn)行關(guān)鍵字比較的,這樣得出的最終序列就是一個(gè)有序序列。本章各種排序算法的思想以及偽代碼實(shí)現(xiàn),及其時(shí)間復(fù)雜度都是必須掌握的。/穩(wěn)定性分析/排序算法的穩(wěn)定性,通俗地講就是能保證

27、排序前2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同。穩(wěn)定性的好處:若排序算法如果是穩(wěn)定的,那么從一個(gè)鍵上排序,然后再?gòu)牧硪粋€(gè)鍵上排序,第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用。基數(shù)排序就是這樣,先按低位排序,逐次按高位排序,低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的。另外,如果排序算法穩(wěn)定,對(duì)基于比較的排序算法而言,元素交換的次數(shù)可能會(huì)少一些個(gè)人感覺(jué),沒(méi)有證實(shí)。分析一下常見(jiàn)的排序算法的穩(wěn)定性,每個(gè)都給出簡(jiǎn)單的理由。1冒泡排序冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較,交換也發(fā)生在這兩個(gè)元素之間。所以,如果兩個(gè)元素相等,我想你是不會(huì)再無(wú)

28、聊地把他們倆交換一下的;如果兩個(gè)相等的元素沒(méi)有相鄰,那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái),這時(shí)候也不會(huì)交換,所以相同元素的前后順序并沒(méi)有改變,所以冒泡排序是一種穩(wěn)定排序算法。2選擇排序選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的,比如給第一個(gè)位置選擇最小的,在剩余元素里面給第二個(gè)元素選擇第二小的,依次類(lèi)推,直到第n-1個(gè)元素,第n個(gè)元素不用選擇了,因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了。那么,在一趟選擇,如果當(dāng)前元素比一個(gè)元素小,而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面,那么交換后穩(wěn)定性就被破壞了。比較拗口,舉個(gè)例子,序列58529,我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換,那么原序列中2個(gè)5的相

29、對(duì)前后順序就被破壞了,所以選擇排序不是一個(gè)穩(wěn)定的排序算法。3插入排序插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上,一次插入一個(gè)元素。當(dāng)然,剛開(kāi)始這個(gè)有序的小序列只有1個(gè)元素,就是第一個(gè)元素。比較是從有序序列的末尾開(kāi)始,也就是想要插入的元素和已經(jīng)有序的最大者開(kāi)始比起,如果比它大則直接插入在其后面,否則一直往前找直到找到它該插入的位置。如果碰見(jiàn)一個(gè)和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后順序沒(méi)有改變,從原無(wú)序序列出去的順序就是排好序后的順序,所以插入排序是穩(wěn)定的。4快速排序快速排序有兩個(gè)方向,左邊的i下標(biāo)一直往右走,當(dāng)aiacenter_index,其中ce

30、nter_index是中樞元素的數(shù)組下標(biāo),一般取為數(shù)組第0個(gè)元素。而右邊的j下標(biāo)一直往左走,當(dāng)ajacenter_index。如果i和j都走不動(dòng)了,ij,交換ai和aj,重復(fù)上面的過(guò)程,直到ij。交換aj和acenter_index,完成一趟快速排序。在中樞元素和aj交換的時(shí)候,很有可能把前面的元素的穩(wěn)定性打亂,比如序列為53343891011,現(xiàn)在中樞元素5和3第5個(gè)元素,下標(biāo)從1開(kāi)始計(jì)交換就會(huì)把元素3的穩(wěn)定性打亂,所以快速排序是一個(gè)不穩(wěn)定的排序算法,不穩(wěn)定發(fā)生在中樞元素和aj交換的時(shí)刻。5歸并排序歸并排序是把序列遞歸地分成短序列,遞歸出口是短序列只有1個(gè)元素認(rèn)為直接有序或者2個(gè)序列1次比較

31、和交換,然后把各個(gè)有序的段序列合并成一個(gè)有序的長(zhǎng)序列,不斷合并直到原序列全部排好序。可以發(fā)現(xiàn),在1個(gè)或2個(gè)元素時(shí),1個(gè)元素不會(huì)交換,2個(gè)元素如果大小相等也沒(méi)有人故意交換,這不會(huì)破壞穩(wěn)定性。那么,在短的有序序列合并的過(guò)程中,穩(wěn)定是是否受到破壞?沒(méi)有,合并過(guò)程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí),我們把處在前面的序列的元素保存在結(jié)果序列的前面,這樣就保證了穩(wěn)定性。所以,歸并排序也是穩(wěn)定的排序算法。6基數(shù)排序基數(shù)排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次類(lèi)推,直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的,先按低優(yōu)先級(jí)排序,再按高優(yōu)先級(jí)排序,最后的次序就是高優(yōu)先級(jí)高的在前,高優(yōu)先級(jí)

32、相同的低優(yōu)先級(jí)高的在前?；鶖?shù)排序基于分別排序,分別收集,所以其是穩(wěn)定的排序算法。7希爾排序shell希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序,當(dāng)剛開(kāi)始元素很無(wú)序的時(shí)候,步長(zhǎng)最大,所以插入排序的元素個(gè)數(shù)很少,速度很快;當(dāng)元素基本有序了,步長(zhǎng)很小,插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時(shí)間復(fù)雜度會(huì)比on2好一些。由于多次插入排序,我們知道一次插入排序是穩(wěn)定的,不會(huì)改變相同元素的相對(duì)順序,但在不同的插入排序過(guò)程中,相同的元素可能在各自的插入排序中移動(dòng),最后其穩(wěn)定性就會(huì)被打亂,所shell排序是不穩(wěn)定的。8堆排序我們知道堆的結(jié)構(gòu)是節(jié)點(diǎn)i的孩子為2*i和2*i+1節(jié)點(diǎn),大頂堆要求父節(jié)點(diǎn)大于等于

33、其2個(gè)子節(jié)點(diǎn),小頂堆要求父節(jié)點(diǎn)小于等于其2個(gè)子節(jié)點(diǎn)。在一個(gè)長(zhǎng)為n的序列,堆排序的過(guò)程是從第n/2開(kāi)始和其子節(jié)點(diǎn)共3個(gè)值選擇最大大頂堆或者最小小頂堆這3個(gè)元素之間的選擇當(dāng)然不會(huì)破壞穩(wěn)定性。但當(dāng)為n/2-1,n/2-2,.1這些個(gè)父節(jié)點(diǎn)選擇元素時(shí),就會(huì)破壞穩(wěn)定性。有可能第n/2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過(guò)去了,而第n/2-1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒(méi)有交換,那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了。所以,堆排序不是穩(wěn)定的排序算法。/冒泡排序插入排序二路插入排序希爾排序快速排序選擇排序歸并排序堆排序算法的C/C+實(shí)現(xiàn)/#includeusingnamespacestd;/交換兩個(gè)數(shù)的值vo

34、idswapint&a,int&binttmp;tmpa;ab;btmp;/屏幕輸出數(shù)組voiddisplayintarray,intlencout"theresultis:"endl;forinti0;ilen;i+coutarrayi""coutendl;/*冒泡排序算法思想:將被排序的記錄數(shù)組R1.n垂直排列,每個(gè)記錄Ri看作是重量為Ri.key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則,從下往上掃描數(shù)組R:凡掃描到違反本原則的輕氣泡,就使其向上"飄浮"。如此反復(fù)進(jìn)行,直到最后任何兩個(gè)氣泡都是輕者在上,重者在下為止

35、。時(shí)間復(fù)雜度onA2空間復(fù)雜度o1比較次數(shù)nn+1/2*/voidbubble_sortintarray,intlenfor int i len-1 ;i0;i-forint j 0;ji;j+ifarrayjarrayj+1swaparrayj,arrayj+1;/*直接插入排序算法思想:把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無(wú)序表,開(kāi)始時(shí)有序表中只包含一個(gè)元素,無(wú)序表中包含有n-1個(gè)元素,排序過(guò)程中每次從無(wú)序表中取出第一個(gè)元素,將它插入到有序表中的適當(dāng)位置,使之成為新的有序表,重復(fù)n-1次可完成排序過(guò)程。時(shí)間復(fù)雜度onA2空間復(fù)雜度o1比較次數(shù)nn+1/2*/voidinsert_sor

36、tintarray,intleninttmp,i,j;fori1;ilen;i+ifarrayiarrayi-1tmparrayi;arrayiarrayi-1;/插入到相應(yīng)位置forji-2;j0;j-/往后移ifarrayjtmparrayj+1arrayj;elsearrayj+1tmp;break;ifj-1arrayj+1tmp;/*2- 路插入排序算法思想:增加一個(gè)輔助空間d,把r1賦值給d1,并將d1看成是排好序后處于中間位置的記錄。然后從r2開(kāi)始依次插入到d1之前或之后的有序序列中。時(shí)間復(fù)雜度onA2空間復(fù)雜度o1比較次數(shù)nn+1/2*/voidbi_insert_sortin

37、tarray,intlenint*arr_dint*mallocsizeofint*len;arr_d0array0;inthead0,tail0;forinti1;ilen;i+ifarrayiarr_d0intj;forjtail;j0;j-ifarrayiarr_djarr_dj+1arr_dj;elsebreak;arr_dj+1arrayi;tail+1;elseifhead0arr_dlen-1arrayi;headlen-1;elseintj;forjhead;jlen-1;j+ifarrayiarr_djarr_dj-1arr_dj;elsebreak;arr_dj-1arra

38、yi;head-1;forinti0;ilen;i+intposi+head;ifposlenpos-len;arrayiarr_dpos;freearr_d;/*希爾排序算法思想:先將整個(gè)待排序記錄分割成若干子序列分別進(jìn)行直接插入排序,待整個(gè)序列中的記錄基本有序時(shí),再對(duì)全體記錄進(jìn)行一次直接插入排序時(shí)間復(fù)雜度onA2空間復(fù)雜度o1比較次數(shù)*/voidshell_insertintarray,intd,intleninttmp,j;forintid;ilen;i+ifarrayiarrayi-dtmparrayi;ji-d;doarrayj+darrayj;jj-d;whilej0&&a

39、mp;tmparrayj;arrayj+dtmp;voidshell_sortintarray,intlenintinclen;doincinc/2;shell_insertarray,inc,len;whileinc1;/*快速排序算法思想:將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些子問(wèn)題,然后將這些子問(wèn)題的解組合成為原問(wèn)題的解。時(shí)間復(fù)雜度onlogn空間復(fù)雜度ologn比較次數(shù)*/voidquick_sortintarray,intlow,inthighiflowhighintpivotlocpartitionarray,low,high;quick_sortar

40、ray,low,pivotloc-1;quick_sortarray,pivotloc+1,high;intpartitionintarray,intlow,inthighintpivotkeyarraylow;whilelowhighwhilelowhigh&&arrayhighpivotkey-high;swaparraylow,arrayhigh;whilelowhigh&&arraylowpivotkey+low;swaparraylow,arrayhigh;arraylowpivotkey;returnlow;/*直接選擇排序算法思想:每一趟在n-i+

41、1個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄時(shí)間復(fù)雜度onA2空間復(fù)雜度o1比較次數(shù)nn+1/2*/intSelectMinKeyintarray,intiPos,intlenintret0;forintiiPos;ilen;i+ifarrayretarrayireti;returnret;voidselect_sortintarray,intlenforinti0;ilen;i+intjSelectMinKeyarray,i,len;ifi!jswaparrayi,arrayj;/*歸并排序算法思想:設(shè)兩個(gè)有序的子文件相當(dāng)于輸入堆放在同一向量中相鄰的位置上:Rlow.m,Rm+1

42、.high,先將它們合并到一個(gè)局部的暫存向量R1相當(dāng)于輸出堆中,待合并完成后將R1復(fù)制回Rlow.high中。時(shí)間復(fù)雜度onlogn空間復(fù)雜度on比較次數(shù)*/voidmergeintarray,inti,intm,intnintj,k;intiStarti,iEndn;intarrayDest256;forjm+1,ki;im&&jn;+kifarrayiarrayjarrayDestkarrayi+;elsearrayDestkarrayj+;ifimfor;kn;k+,i+arrayDestkarrayi;ifjnfor;kn;k+,j+arrayDestkarrayj;f

43、orjiStart;jiEnd;j+arrayjarrayDestj;voidmerge_sortintarray,ints,inttintm;ifstms+t/2;merge_sortarray,s,m;merge_sortarray,m+1,t;mergearray,s,m,t;/*堆排序算法思想:堆排序(HeapSort)是指利用堆(heaps)這種數(shù)據(jù)結(jié)構(gòu)來(lái)構(gòu)造的一種排序算法。堆是一個(gè)近似完全二叉樹(shù)結(jié)構(gòu),并同時(shí)滿(mǎn)足堆屬性:即子節(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。時(shí)間復(fù)雜度onlogn空間復(fù)雜度o1比較次數(shù):較多*/voidheap_adjustintarray,inti,i

44、ntlenintrcarrayi;forintj2*i;jlen;j*2ifjlen&&arrayjarrayj+1j+;ifrcarrayjbreak;arrayiarrayj;ij;arrayirc;voidheap_sortintarray,intleninti;forilen-1/2;i0;i-heap_adjustarray,i,len;forilen-1;i0;i-swaparray0,arrayi;/彈出最大值,重新對(duì)i-1個(gè)元素建堆heap_adjustarray,0,i-1;intmainintarray45,56,76,234,1,34,23,2,3,55,88,100;intlensizeofarray/si