【正文】 點(diǎn)的后繼被稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。v 我們把進(jìn)行插入的一端稱作隊尾(rear)，進(jìn)行刪除的一端稱作隊首(front)。當(dāng)頭結(jié)點(diǎn)的指針域?yàn)椤翱铡睍r，單鏈表為空鏈表熟悉單鏈表中結(jié)點(diǎn)的定位、插入、刪除、查詢的算法思想和操作程序了解線性表的順序與鏈?zhǔn)酱鎯Ω髯缘膬?yōu)點(diǎn)、不足與它們適用場合。循環(huán)鏈表。線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點(diǎn)：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的，即前驅(qū)元素一定存儲在后繼元素的前面。存儲指算法執(zhí)行過程中所需的最大存儲空間。 v 樹結(jié)構(gòu)是圖結(jié)構(gòu)的特例，線性結(jié)構(gòu)是樹結(jié)構(gòu)的特例。v 集合結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={ }v 線性結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，B,C，C,D，D,E，E,F，F(xiàn),G}v 樹結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，A,C，A,D，C,E，C,F，D,G}v 圖結(jié)構(gòu)中的元素集合K和二元關(guān)系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，A,C，A,G，D,G，D,F，C,E，C,F，G,F}了解數(shù)據(jù)的幾種存儲結(jié)構(gòu)（物理結(jié)構(gòu)）及它們各自的性質(zhì)和特點(diǎn)。把算法中包含簡單操作次數(shù)的多少叫做該算法的時間復(fù)雜度，或者叫做時間復(fù)雜性，用它來衡量一個算法的運(yùn)行時間性能或稱計算性能v 平均復(fù)雜度(The Average Case)：．v 最壞情況復(fù)雜度 (The Worst Case)：估算最壞情況下時間復(fù)雜度的一個上界．這也是通常所指的復(fù)雜度．v 最好復(fù)雜度 (The Best Case):在最理想輸入情況下的時間復(fù)雜度。其中指針用于指向該結(jié)點(diǎn)的前一個或后一個結(jié)點(diǎn)，從而可以表示數(shù)據(jù)元素之間的邏輯關(guān)系。 了解單鏈表的結(jié)點(diǎn)的類型定義在程序中，L為單鏈表的頭指針，它指向表中第一個結(jié)點(diǎn)。在順序表中進(jìn)行插入和刪除數(shù)據(jù)元素時，平均要移動近一半的元素，尤其是當(dāng)每個數(shù)據(jù)元素包含的信息量較大時，移動元素所花費(fèi)的時間就相當(dāng)可觀。了解隊列特別是循環(huán)隊列情況下，隊列頭指針和尾指針的設(shè)置了解隊列出現(xiàn)“假溢出”現(xiàn)象的原因及解決辦法：循環(huán)隊列的實(shí)現(xiàn)（循環(huán)頭指針和尾指針的計算、循環(huán)（和普通）隊列長度的計算以及循環(huán)隊列為空和滿的判斷方法）第五章 樹和二叉樹了解樹的定義和樹的基本術(shù)語：樹和結(jié)點(diǎn)的度、分支結(jié)點(diǎn)和葉子結(jié)點(diǎn)、父母結(jié)點(diǎn)和孩子結(jié)點(diǎn)、結(jié)點(diǎn)的層數(shù)和樹的深度、有序樹和無序樹等在樹形表示法中，結(jié)點(diǎn)之間的關(guān)系是通過連線表示的，雖然每條連線上都不帶有箭頭(即方向)，但它并不是無向的，而是有向的，其方向隱含為從上向下或從左向右，即連線的上方或左邊結(jié)點(diǎn)是下方或右邊結(jié)點(diǎn)的前驅(qū)，下方或右邊結(jié)點(diǎn)是上方或左邊結(jié)點(diǎn)的后繼。v 堂兄弟結(jié)點(diǎn)(cousins)：其雙親在同一層但不同的結(jié)點(diǎn)互為堂兄弟。樹的總分支數(shù)為：v 性質(zhì)2： 度為k的樹中第i層上至多有ki1個結(jié)點(diǎn)（i≥1）。 分析：在結(jié)點(diǎn)數(shù)相同的 k叉樹中，每一層結(jié)點(diǎn)都滿，或除最后一層外其余層都滿的樹，其深度為最小。v 二叉樹(binary tree)是指樹的度為2的有序樹。 n1 :單分支結(jié)點(diǎn)數(shù), n2 :雙分支結(jié)點(diǎn)數(shù)) (2) 設(shè)B為二叉樹中總的分支數(shù)目，由于二叉樹中除了根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)都有一個分支進(jìn)入,而這些分支只能是由度數(shù)為1或2的結(jié)點(diǎn)所發(fā)出，所以： B = n1 + 2n2 于是得： n = n1 + 2n2 + 1(3) 由(1)和(2)得： n0 + n1 + n2 = n1 + 2n2 + 1 所以 n0 = n2 + 1 證畢性質(zhì)4：對完全二叉樹中編號為i的結(jié)點(diǎn)(1≤i≤n,n≥1，n為結(jié)點(diǎn)數(shù))有： (1) 若i≤235。 (4) 除樹根結(jié)點(diǎn)外，若一個結(jié)點(diǎn)的編號為i，則它的雙親結(jié)點(diǎn)的編號為235。+1。完全二叉樹： 除最后一層外，其余層均滿；最后層或?yàn)闈M，或缺少右邊若干連續(xù)結(jié)點(diǎn)。 { 先訪問右子樹根節(jié)點(diǎn)；再遍歷右子樹根節(jié)點(diǎn)的左子樹，再遍歷右子樹根節(jié)點(diǎn)的右子樹；……直至遍歷完所有右子樹的節(jié)點(diǎn)}(2) 中序遍歷： 若二叉樹為空，則空操作；否則 ① 中序遍歷左子樹。v 若二叉搜索樹是一棵理想平衡樹或接近理想平衡樹，則進(jìn)行查找的時間復(fù)雜度為O(log2n)，v 若為一棵單支樹(這是最極端和最差的情況)，則其時間復(fù)雜度為O(n)，v 一般情況而言，其時間復(fù)雜度可大致可看做為O(log2n)。能采用給定的數(shù)據(jù)序列來生成一個堆（大根堆或小根堆）了解樹的帶權(quán)路徑，以及哈夫曼樹（最優(yōu)二叉樹）的概念和性質(zhì)(1) 路徑和路徑長度若在一棵樹中存在著一個結(jié)點(diǎn)序列k1,k2,…,kj，使得ki是ki+1的雙親(1≤ij)，則稱此結(jié)點(diǎn)序列是從k1到kj的路徑。它是n個帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹。 1, 對于無向圖，(vi,vj)或(vj, vi)206。v 在無向圖中, 統(tǒng)計第 i 行 (列)中 1 的個數(shù)可得頂點(diǎn)i 的度。v 邊結(jié)點(diǎn)通常包含三個域：一是鄰接點(diǎn)域(adjvex)，用以存儲頂點(diǎn)vi的一個鄰接頂點(diǎn)vj的序號j；二是權(quán)域(weight)，用以存儲邊(vi, vj)或 vi, vj 上的權(quán)；三是鏈域(next)，用以鏈接vi鄰接表中的下一個邊結(jié)點(diǎn)。