嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)整理

1、1復(fù)雜性分析對各種操作的時間復(fù)雜性的分析。主要是鏈表，樹，排序等簡單一些的分析。 分析的時候，從簡單的入手，學(xué)會方法。 后續(xù)的各種豆可能讓你分析時間復(fù)雜度。線性鏈表（順序表和單鏈表）鏈表q循環(huán)鏈表雙向鏈表2線性結(jié)構(gòu)q 隊列（循環(huán)隊列）棧鏈表主要操作：找某一個元素，插入一個（在哪個位置增加），刪除一個（在哪個位置刪除） 棧：查找，插入（位置固定），刪除（位置固定）隊列：查找，插入（位置固定），刪除（位置固定）順序表（可以視為一個數(shù)組）下標(biāo)冠0A1B2C3D4E5F6G7H8 4 單鏈表:（刪除）PO循環(huán)鏈表雙向鏈表匸跖二和RT =L ;u “/弋hotid棧:隊列(插入刪除查找)循環(huán)隊列的實現(xiàn)，

2、并不是像上面的圖那樣，實現(xiàn)了一個循環(huán)的樣子。3二叉樹基本概念二叉樹是每個最多有兩個子樹的有序樹。二叉樹常被用于實現(xiàn)和。值得注意的是，二叉樹不是樹的特殊情形。二叉樹是每個結(jié)點最多有兩個子樹的有序樹。通常根的子樹被稱作“左子樹” (leftsubtree)和“右子樹” (right subtree)。二叉樹常被用作和或是。二叉樹的每個結(jié)點至多只 有二棵子樹(不存在出度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹不是樹的一種特殊情形，盡管其與樹有許多相似之處，但樹和二叉樹有兩個主要差別：1. 樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2 ；2. 樹的結(jié)點無左、右之分，而二叉

3、樹的結(jié)點有左、右之分。0Z / jfLjfX0 0 67/ /O O 0 O二叉樹是定義的，其結(jié)點有左右子樹之分，邏輯上二叉樹有五種基本形態(tài):(1)空二叉樹一一如圖(a);只有一個根結(jié)點的二叉樹如圖(b)；只有左子樹一一如圖(c)；(4)只有右子樹一一如圖(d)；一一如圖(e)注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形(|)性質(zhì)在非空二叉樹中，第 i 層的結(jié)點總數(shù)不超過(2) 深度為h的二叉樹最多有2Ah-1個結(jié)點(h=1)，最少有h個結(jié)點；(3) 對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為NO，而度數(shù)為2的結(jié)點總數(shù)為 N2，則N0=N2+1 ；(4)具有n個結(jié)點的的深度為(5)有

4、N個結(jié)點的各結(jié)點如果用順序方式存儲，則結(jié)點之間有如下關(guān)系：若I為結(jié)點編號則 如果11，則其父結(jié)點的編號為1/2 ；如果2*IN，則無左兒子；如果2*I+1N，則無右兒子。給定N個節(jié)點，能構(gòu)成h(N)種不同的二叉樹。h(N)為的第N項。h(n)=C(2*n , n)/(n+1)。(7)設(shè)有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和 J=I+2i存儲結(jié)構(gòu)順序存儲表示0123456二叉樹可以用或線性表來存儲，而且如果這是，這種方法不會浪費空間。用這種緊湊排 列，如果一個結(jié)點的索引為i,它的子結(jié)點能在索引2i+1和2i+2找到，并且它的父節(jié)點(如果有)能在索引floor(i-1)/2)

5、找到(假設(shè)根節(jié)點的索引為0)。這種方法更有利于緊湊存儲和更好的，特別是在前序遍歷中。然而，它需要連續(xù)的，這樣在存儲高度為 h的n個結(jié)點組成的一般普通樹時將會浪費很多空間。一種最極壞的情況下如果深度為h的二叉樹每個節(jié)點只有右孩子需要占用 2的h次幕減1,而實際卻只有h個結(jié)點，空間的浪費太大，這是順序 存儲結(jié)構(gòu)的一大缺點。/*二叉樹的順序存儲表示*/#define MAX TREE SIZE 100 /* 二叉樹的最大節(jié)點數(shù) */typedef struct int level,order; /*positi on;節(jié)點的層，本層序號（按滿二叉樹計算）*/二叉鏈表存儲表示/*二叉樹的二叉鏈表存儲表

6、示*/ typedef struct BiTNodeTEIemType data;左右孩子指針*/struct BiTNode *lchild,*rchild; /*BiTNode,*BiTree;遍歷算法二叉樹的遍歷三種方式，如下：（1）前序遍歷（DLR），首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右 子樹。簡記根-左-右。（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右 子樹。簡記左-根-右。（3）后序遍歷（LRD ），首先遍歷左子樹，然后遍歷右子樹，最后訪問根 結(jié)點。簡記左-右-根。例1:如上圖所示的二叉樹，若按前序遍歷，則其輸出序列為。若按中序遍歷，則其輸出序列為。若

7、按后序遍歷，則其輸出序列為。前序：根A , A的左子樹B，B的左子樹沒有，看右子樹，為D，所以A-B-D 再來看A的右子樹，根C,左子樹E，E的左子樹F，E的右子樹G，G的左子 樹為H，沒有了結(jié)束。連起來為 C-E-F-G-H,最后結(jié)果為ABDCEFGH中序：先訪問根的左子樹，B沒有左子樹，其有右子樹D，D無左子樹，下面 訪問樹的根A，連起來是BDA。再訪問根的右子樹，C的左子樹的左子樹是F，F(xiàn)的根E, E的右子樹有左子 樹是H，再從H出發(fā)找到G,到此C的左子樹結(jié)束，找到根C,無右子樹，結(jié) 束。連起來是FEHGC,中序結(jié)果連起來是BDAFEHGC后序：B無左子樹，有右子樹D，再到根B。再看右子

8、樹，最下面的左子樹 是F,其根的右子樹的左子樹是 H，再到H的根G,再到G的根E, E的根C 無右子樹了，直接到C,這時再和B找它們其有的根A，所以連起來是DBFHGECA深度優(yōu)先遍歷在深度優(yōu)先中，我們希望從根結(jié)點訪問最遠(yuǎn)的結(jié)點。和圖的不同的是，不需 記住訪問過的每一個結(jié)點，因為樹中不會有環(huán)。廣度優(yōu)先遍歷和深度優(yōu)先遍歷不同，廣度優(yōu)先遍歷會先訪問離根節(jié)點最近的節(jié)點GO藕XHe】左全二叉掲1. 滿二叉樹：一棵深度為 k,且有個節(jié)點稱之為滿二叉樹2. 完全二叉樹：深度為k,有n個節(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個節(jié)點都與深度為k的滿二叉樹中，序號為 1至n的節(jié)點對應(yīng)時，稱之為完全二叉樹4樹基本概念樹（t

9、ree）是包含n （n0）個結(jié)點的有窮集，其中：（1）每個元素稱為結(jié)點（n ode）;（2）有一個特定的結(jié)點被稱為根結(jié)點或樹根（ root ）。（3） 除根結(jié)點之外的其余數(shù)據(jù)元素被分為m （m0）個互不相交的集合 T1, T2,Tm-1 ,其中每一個集合 Ti （1=i=0)棵互不相交的樹的集合稱為森林；存儲父節(jié)點表示法/* 樹節(jié)點的定義 */#define MAX_TREE_SIZE 100typedef struct TEIemType data;in t pare nt; /* 父節(jié)點位置域 */ PTNode;typedef struct PTNode no desMAX_TREE_S

10、IZE;int n; /* 節(jié)點數(shù) */ PTree;孩子鏈表表示法/*樹的孩子鏈表存儲表示*/typedef struct CTNode /孩子節(jié)點int child;struct CTNode *n ext; *ChildPtr;typedef struct ElemType data ; / 節(jié)點的數(shù)據(jù)元素ChildPtr firstchild ; / 孩子鏈表頭指針 CTBox;typedef struct CTBox no desMAX_TREE_SIZE；int n, r ； / 節(jié)點數(shù)和根節(jié)點的位置 CTree;5. 森林6. 森林、樹與二叉樹的轉(zhuǎn)換將樹轉(zhuǎn)換為二叉樹樹中每個結(jié)點最

11、多只有一個最左邊的孩子（長子）和一個右鄰的兄弟。 按照這種關(guān)系很自然地就能將樹轉(zhuǎn)換成相應(yīng)的二叉樹： 在所有兄弟結(jié)點之間加一連線； 對每個結(jié)點，除了保留與其長子的連線外，去掉該結(jié)點與其它孩子的連線。(a)(b)(c)樹轉(zhuǎn)化虛-足鞫注意:由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點的右子樹必為空。2）將一個森林轉(zhuǎn)換為二叉樹具體方法是： 將森林中的每棵樹變?yōu)槎鏄?因為轉(zhuǎn)換所得的二叉樹的根結(jié)點的右子樹均為空，故可將各二叉樹的根結(jié)點視 為兄弟從左至右連在一起，就形成了一棵二叉樹。二叉樹到樹、森林的轉(zhuǎn)換把二叉樹轉(zhuǎn)換到樹和森林自然的方式是：若結(jié)點x是雙親y的左孩子，則把x的右孩子,右孩子的右孩子，

12、都與 y用連線連起來，最后去掉所有雙親到右孩子的連線。二元組的定義圖G是一個有序二元組(V,E)，其中V稱為頂集(Vertices Set)疋稱為邊集(Edges set) , E與V不相交。它們亦可寫成 V(G)和E(G)。E的元素都是二元組，用(x,y)表示，其中x,y V。三元組的定義圖G是指一個三元組(V,E,I)，其中V稱為頂集，E稱為邊集，E與V不相交；I 稱為關(guān)聯(lián)函數(shù)，I將E中的每一個元素映射到VxV。如果e被映射到(u,v)，那么稱邊e連接頂點u,v，而u,v貝U稱作e的端點， u,v此時關(guān)于e相鄰。同時，若兩條邊i,j有一個公共頂點u，則稱i,j關(guān)于u 相鄰。有/無向圖如果給

13、圖的每條邊規(guī)定一個方向， 那么得到的圖稱為有向圖。在有向圖中，與 個節(jié)點相關(guān)聯(lián)的邊有出邊和入邊之分。相反，邊沒有方向的圖稱為無向圖。簡單圖一個圖如果1. 沒有兩條邊，它們所關(guān)聯(lián)的兩個點都相同(在 有向圖 中，沒有兩條邊的起點終點都 分別相同)；2. 每條邊所關(guān)聯(lián)的是兩個不同的頂點則稱為簡單圖( Simple graph )。簡單的有向圖和無向圖都可以使用以上的“二元組的定義” ，但形如 的 序 對 不能 屬 于 E。 而無 向 圖的 邊 集必 須 是對稱 的， 即 如果那么基本術(shù)語階(Order):圖G中頂集V的大小稱作圖G的階。子圖(Sub-Graph):當(dāng)圖G=(V,E) 其中V 包含于V

14、, E 包含于E,貝U G稱 作圖G=(V,E)的子圖。每個圖都是本身的子圖。生成子圖(Spanning Sub-Graph ):指滿足條件 V(G) = V(G)的G的子圖G 導(dǎo)出子圖(Induced Subgraph ):以圖G的頂點集V的非空子集V1為頂點集， 以兩端點均在V1中的全體邊為邊集的G的子圖，稱為V1導(dǎo)出的導(dǎo)出子圖；以圖 G的邊集E的非空子集E1為邊集，以E1中邊關(guān)聯(lián)的頂點的全體為頂點集的G的子圖，稱為 E1 導(dǎo)出的導(dǎo)出子圖。度(Degree): 個頂點的度是指與該頂點相關(guān)聯(lián)的邊的條數(shù)，頂點v的度記作d(v) 。入度（In-degree ）和出度（Out-degree ）:對

15、于有向圖來說，一個頂點的度可 細(xì)分為入度和出度。一個頂點的入度是指與其關(guān)聯(lián)的各邊之中，以其為終點的邊數(shù)；出度則是相對的概念，指以該頂點為起點的邊數(shù)。自環(huán)（Loop）:若一條邊的兩個頂點為同一頂點，則此邊稱作自環(huán)。路徑（Path）:從u到v的一條路徑是指一個序列 v0,e1,v1,e2,v2,ek,vk ，其 中ei的頂點為vi及vi - 1, k稱作路徑的長度。如果它的起止頂點相同，該路 徑是“閉”的，反之，則稱為“開”的。一條路徑稱為一簡單路徑（simple path）， 如果路徑中除起始與終止可以重合外，所有頂點兩兩不等。行跡（Trace）:如果路徑P（u,v）中的邊各不相同，則該路徑稱為

16、 u到v的一條 行跡。軌道（Track）:如果路徑P（u,v）中的頂點各不相同，則該路徑稱為 u到v的一 條軌道。閉的行跡稱作回路（Circuit ），閉的軌稱作圈（Cycle）。（另一種定義是：walk對應(yīng)上述的path， path對應(yīng)上述的track 。Trail對應(yīng) trace。）橋（Bridge ）：若去掉一條邊，便會使得整個圖不連通，該邊稱為。圖的存儲表示1.數(shù)組（鄰接矩陣）存儲表示（有向或無向）typedef structVRType adj; /頂點關(guān)系類型。對無權(quán)圏*用1（是）或趴否）表示相鄰否i對帶權(quán)圖，刊為權(quán)值 InfaType/該弧拒美信息的指針（可無）JArcCell,

17、 MatrxMAX_VERTEX_MUlMMAX_VERTEX_NUIM;.-/ 二維數(shù)組struct rGraphA f弐A03AV 中的頊Q(jìng) CO境規(guī)占枚荷肯最短2選人G此時0=弧c*側(cè)播趣SS橙ATy毆C為申鬧點，從k-C=3這熹帑趣SS徑開 站找V=D、E. Fa -c t耐c比上面眾一歩的 r 聰要短） 就時列B撫值為A TU -S=5A -C T XEA -C ETA T瞪T直催V中的頂點二加爲(wèi)觀* TQ -B=5衩偉為餐短Z選入此時鈴匚、止時疑短S&徑 斗社0*九一03,A TU 以E為中間點從去TC TE再這條杲短X狐 H FA貞一CTETD =10（比;面第二歩的AD=6要長

18、J 就時到D取值更改為A -C TD翡人C TE T菖池U中的頂點=oa覽現(xiàn)atctm權(quán)儻為杲短4ift人九a c,比 &止陽最短罐往F S3.A TC B-5 * C D=&削D為申詞點,從盤T C TD這條席短路徑 另贈找11= ATCTDTE =3( tt面簫二歩的 ATCTE b 要*; 時到E權(quán)值更改育ATCTE可ATCTJtTF W爲(wèi)觀aTCTE =t權(quán)值加蹇短SiSAif比也狀時暑短握徑A TWO * fc-C=3*C TD=3ATCTE =7以E為中何丸從A-C-I =7謹(jǐn)條理邏 理住開始找x A TC T E TF =12 C館上面算E3步的& TC T D TF羽 賽長）此

19、時劉FtSUS更改麹ATCTDTF =9 蔑規(guī)ATCTDTP勻權(quán)值力堆短6選入F此時丹S匚、氛比E、F 腸接祖銘徑AT口玄TC -B=S A C TD=& aTCTE =T 丸 TCTDF Sfl弗洛伊德算法1.定義概覽Floyd-Warshall算法（Floyd-Warshall algorithm ）是解決任意兩點間的最短路徑 的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，同時也被用于計算有 向圖的傳遞閉包。Floyd-Warshall算法的時間復(fù)雜度為0（N，空間復(fù)雜度為 0（N2）。2.算法描述1）算法思想原理：Floyd算法是一個經(jīng)典的動態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先

20、我們 的目標(biāo)是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題，我們需要為 這個目標(biāo)重新做一個詮釋（這個詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在）從任意節(jié)點i到任意節(jié)點j的最短路徑不外乎2種可能，1是直接從i至叮,2 是從i經(jīng)過若干個節(jié)點k至叮。所以，我們假設(shè)Dis(i,j)為節(jié)點u到節(jié)點v的最短 路徑的距離，對于每一個節(jié)點 k,我們檢查Dis(i,k) + Dis(k,j) right 一定不為空，右旋的時候p-left 定不為空，這是顯而易見的。如果從空樹開始建立，并時刻保持平衡，那么不平衡只會發(fā)生在插入刪除操刪除 雖然平衡二叉樹的節(jié)點刪除操作的代碼比較復(fù)雜， 代碼量也比較大， 但是其刪除

21、過程只有以下 3 種情況： 注：只要牢牢把握住以下 3 點，理解平衡二叉樹的刪 除操作不是太難 被刪的節(jié)點是葉子節(jié)點處理思路： 將該節(jié)點直接從樹中刪除， 并利用遞歸的特點和高度的變化， 反向推 算其父節(jié)點和祖先節(jié)點是否失衡。如果失衡，則判斷是那種類型的失衡（LL 、LR、RR、RL），再對失衡節(jié)點進(jìn)行旋轉(zhuǎn)處理，直到根節(jié)點或高度不再變化。 被刪的節(jié)點只有左子樹或只有右子樹 處理思路：將左子樹（右子樹）替代原有節(jié)點的位置，并利用遞歸的特點和高度 的變化，反向推算父節(jié)點和祖先節(jié)點是否失衡。 如果失衡， 則判斷是那種類型的 失衡（LL、LR、RR、RL），再對失衡節(jié)點進(jìn)行旋轉(zhuǎn)處理，直到根節(jié)點或高度 不

22、再發(fā)生變化。 被刪的節(jié)點既有左子樹又有右子樹 處理思路：找到被刪節(jié)點的左子樹的最右端的節(jié)點 rnode,將rnode的值賦給node, 再把rnode的左孩子替換rnode的位置，在把rnode釋放掉，并利用遞歸特點， 反向推斷rnode的父節(jié)點和祖父節(jié)點是否失衡。如果失衡，則判斷是哪種類型的 失衡（LL、LR、RR、RL），再對失衡的節(jié)點進(jìn)行旋轉(zhuǎn)處理，直到根節(jié)點或高 度不再發(fā)生變化。LOG寺如果q新的平衡因子bf(q)=0,意味著刪除前bf(q)=1或者bf(q)=-1,只有單子樹心此時高度減仁需改變父節(jié)點和其他某些祖先節(jié)點 的平衡因子現(xiàn)象2:如果q新的平衡因子bf(q)=l或-1,意味著刪

23、除前bf (q)=0,左右子樹高度一樣:此時高度不變，需改變父節(jié)點和其他某些祖先節(jié) 點的平衡因子錚如果q新的平衡因子bf(q)= 2或2,意味著刪除前 bf(q)二-1或1,左右子樹高度不同昏此時樹在q節(jié)點是不平衡的，需要平衡化處理B-樹和B+樹定義和分析，算法要求程度不高。哈希表定義構(gòu)造方法處理沖突的方法 查找_直接播入排常 廠插人排序黑爾排庫使用內(nèi)存內(nèi)部排序廣簡單選擇排序 r選擇排序堆排序冒泡排序快速排序排序交換排序.-.-歸并排序L基數(shù)排序內(nèi)存和外村結(jié)臺使用外部排序排序插入排序直接插入排序1. 直接插入排序的基本思想 直接插入排序（Insertion Sort）的基本思想是：每次將一個待

24、排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插 入完成為止。設(shè)數(shù)組為a0n-1。1. 初始時，a0自成1個有序區(qū)，無序區(qū)為a1.n-1。令i=12. 將ai并入當(dāng)前的有序區(qū)a0 i-1中形成a0i的有序區(qū)間。 3.i+并重復(fù)第二步直到i=n-1。排序完成。折半插入排序 算法的基本過程：1） 計算0 i-1 的中間點，用i索引處的元素與中間值進(jìn)行比較， 如果i索引處的元素大，說明要插入的這個元素應(yīng)該在中間值和剛加入i索引之間，反之，就是在剛開始的位置至帥間值的位置，這樣很簡單的完成了折半；2）在相應(yīng)的半個范圍里面找插入的位置時，不斷的用（1）步驟縮小范圍，不停

25、的折半，范圍依次縮小為1/21/41/8 .快速的確定出第i個元素要插在什么地方；3）確定位置之后，將整個序列后移，并將元素插入到相應(yīng)位置。2路插入排序表插入排序希爾排序該方法的基本思想是：先將整個待排元素序列分割成若干個子序列(由相隔某個 “增量”的元素組 成的)分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排 序，待整個序列中的元素基本有序(增量足夠小)時，再對全體元素進(jìn)行一次直 接插入排序。因為直接插 入排序在元素基本有序的情況下(接近最好情況)， 效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。以NO的一個數(shù)組49, 38? 65, 97, 26,13, 27, 49, 5

26、5, 4為例第一次 gap =10/2 = 549 38 65 97 26 13 27 49 55 41A1B2A2B3A3B4A4B5A5B1A,1B，2A,2B等為分組標(biāo)記，數(shù)字相同的表示在同一組，大寫字母表示是該組 的第幾個元素， 每 次對同一組的數(shù)據(jù)進(jìn)行直接插入排序。即分成了五組 (49, 13) (38, 27) (65, 49)(97, 55)(26,4)這樣每組排序后就變成了 (13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。第二次 gap = 5f2 = 2排序后1327495541A1B1C2A2B第 afcgap = 2/2 = 14 26 13 27 381A 1B 1C 1D 1E49386597261D1E2C2D2E49495597651F1G1Hii1J第四次gap = 1/2 = 0排序完成得到數(shù)組；4 13 26 27 3849 49 5565 97快速排序冒泡排序 冒泡排序算法的運(yùn)作如下：(從后往前)比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一