1、鍵入文檔標題鍵入文檔副標題 年黃薇Microsoft選取日期第一章一名詞解釋數據：是對客觀事物的客觀表示，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數據元素：構成數據的基本單位。數據項：數據不可分割的最小單位。數據對象：性質相同的數據元素的集合。數據結構：帶結構的數據元素的集合。相互之間存在一種或多種特定關系的數據元素的集合。二數據結構的三個方面：數據的邏輯結構數據的存儲結構數據的運算（操作）三抽象數據類型的定義是指一個數學模型以及定義在此數學模型上的一組操作。抽象數據類型可用（D，S，P）三元組表示。其中：D 是數據對象； S 是 D 上的關系集； P 是對 D

2、的基本操作集。四算法的概念特性原則概念：解決某一特定問題的具體步驟的描述，是指令的有限序列。五大特性：有窮性，確定性，可行性，有零個或多個輸入，有一個或多個輸出。四大原則：正確性，可讀性，健壯性，高效率和低存儲量需求。五算法的時間復雜度 對足夠大的n，有以下順序 常見數量級第二章1、順序線性表與鏈式線性表的區別對線性表的操作主要有查找，插入和刪除三大類?；跁r間上的比較查找時，數組是可以隨機存取的，因此查找時間復雜度為O(1)，對于鏈表，每次查找都必須從鏈表的首結點開始，時間復雜度為O(n)，因此查找速率上，數組是優于線性表的。插入和刪除時，數組必須首先采用順序查找的方式定位相應的數據元素，接

3、下來還需要移動大量的數據元素，而鏈表在插入和刪除時，僅需要先定位數據元素，然后通過簡單的指針修改即可完成。這方面鏈表是優于數組的?；诳臻g上的比較數組的存儲空間是預先靜態分配的，雖然在實現過程中可以動態拓展，但是如果線性表的長度變化范圍較大，空間在使用過程中會存在大量的閑置空間。鏈表的內存主要被分配為兩部分，一部分存儲數據元素，另一部分則存儲指針域，因此在線性表數據元素結構簡單，且長度變化不大時，可以考慮使用數組。2、鏈表的操作（插入、刪除）1 線性表操作ListInsert(&L, i, e)在單鏈表中的實現：O(ListLength(L)有序對<ai-1, ai>改變為

4、<ai-1, e>和<e, ai>因此，在單鏈表中第i 個結點之前進行插入的基本操作為:找到線性表中第i-1個結點，然后修改其指向后繼的指針。2 線性表的操作ListDelete (&L, i, &e)在鏈表中的實現:O(ListLength(L)有序對<ai-1, ai>和<ai, ai+1>改變為<ai-1, ai+1>在單鏈表中刪除第i 個結點的基本操作為:找到線性表中第i-1個結點p，修改其指向后繼的指針。3、鏈式結構實現一元多項式一般情況下的一元稀疏多項式可寫成Pn(x) = p1xe1 + p2xe2 +

5、+ pmxem其中：pi 是指數為ei的項的非零系數，且 0 e1< e2 <<em = n可用下列線性表表示：（p1, e1）, (p2, e2), , (pm,em) ）例如:P999(x) = 7x3 - 2x12 - 8x999可用線性表( (7, 3), (-2, 12), (-8, 999) )表示第四章1、棧和隊列的特點通常稱，棧和隊列是限定只能在表的“端點”進行插入和刪除操作的線性表棧：插入和刪除操作均在“棧頂”進行隊列：插入和刪除操作分別在“隊頭”和“隊尾”進行2、棧的典型應用例一、數制轉換例二、括號匹配的檢驗算法的設計思想：1）凡出現左括弧，則進棧；2）凡

6、出現右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余，出錯否則和棧頂元素比較，若相匹配，則“左括弧出棧”，否則表明括號不匹配。3）表達式檢驗結束時，若棧空，則表明表達式中匹配正確，否則表明“左括弧”有余，出錯。例三、行編輯程序問題思路：棧作為輸入緩沖區，每當從終端了接受一個字符之后先做如下判別：1：若是退格符#，從棧頂刪去一個元素，即出棧Pop；2：若是退行符，輸入緩沖區中的內容回退一行字符。3：若不是#或，即為有效字符，將該字符入棧，即Push；例四、迷宮求解求迷宮路徑算法的基本思想是：若當前位置“可通”，則納入路徑，繼續前進; 若當前位置“不可通”，則后退，換方向繼續探索; 若四周“

7、均無通路”，則將當前位置從路徑中刪除出去。設定當前位置的初值為入口位置； do若當前位置可通，則將當前位置插入棧頂；若該位置是出口位置，則算法結束；否則切換當前位置的東鄰方塊為新的當前位置；否則 while (棧不空）；若棧不空且棧頂位置尚有其他方向未被探索，則設定新的當前位置為: 沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置；/ 從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至?？?；若?？?，則表明迷宮沒有通路。3、棧和遞歸當在一個函數的運行期間調用另一個函數時，在運行該被調用函數之前，需先完成三項任務：將所

8、有參數、返回地址等信息傳遞給被調用函數保存；為被調用函數的局部變量分配存儲區；將控制轉移到被調用函數的入口。從被調用函數返回調用函數之前，應該完成下列三項任務：保存被調函數的計算結果；釋放被調函數的數據區；依照被調函數保存的返回地址，將控制轉移到調用函數。多個函數嵌套調用的規則是：后調用先返回！此時的內存管理實行“棧式管理”第五章1、數組及廣義表的概念數組特性：1. 可以將二維數組看成是一個定長的線性表，其中每一個數據元素也是一個定長的線性表。2. N維數組也可以看成是一個定長的線性表3. 當數組維數n=1，則數組退化為一個定長的線性表。廣義表是線性表的擴展（表中有表的線性表），也稱為列表（l

9、ists）。例如：X=(a, (b, c, (d)現實世界中的許多數據的結構可以用廣義表來定義，例如數組。廣義表是遞歸定義的線性結構，廣義表一般記作LS = ( a1, a2, ×××, an )，n是它的長度。2、矩陣的壓縮存儲特殊矩陣的壓縮存儲方法:一、對稱矩陣為每對對稱元素分配一個存儲空間二、對角矩陣只存儲其對角線上的元素。稀疏矩陣的壓縮存儲方法:一、 三元組順序表三元組順序表又稱有序的雙下標法。它的特點是：非零元在表中按行序有序存儲，每個非零元存儲的是行號、列號和元素值三項數據。二、 行邏輯聯接的順序表三元組順序表便于進行按行序處理的矩陣運算。然而，若需快

10、速存取某一行中的非零元，則需從頭開始進行查找。修改前述的稀疏矩陣的結構定義，增加一個數據項rpos-各行第一個非零元的位置三、十字鏈表利用行邏輯鏈接的順序表表示稀疏矩陣，便于查找同一行中的非零元，但是不便于查找同一列中的非零元。十字鏈表：每一個非零元均有指向分別指向同一行和同一列中下一個非零元的指針，形成行、列兩個鏈表 - 十字鏈表。3、廣義表層次劃分廣義表是一個多層次的線性結構1廣義表是遞歸定義的線性結構， LS = ( a1, a2, ×××, an )其中：ai或為原子或為廣義表例如: A = ( ) - 空表 F = (d, (e) D = (a,(b,c

11、), F) C = (A, D, F) B = (a, B) = (a, (a, (a, ××× , ) ) )2 任何一個非空廣義表 LS = ( a1, a2, , an)均可分解為：表頭 Head(LS) = a1 和表尾 Tail(LS) = ( a2, , an) 兩部分。例如: D = ( E, F ) = (a, (b, c)，F )Head(D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) =

12、 ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )第六章1、樹及二叉樹的概念樹：非線性數據結構，是n個結點的有限集。數據對象D：D是具有相同特性的數據元素的集合。數據關系R：若D為空集，則稱為空樹；否則: (1) 在D中存在唯一的稱為根的數據元素root； (2) 當n>1時，其余結點可分為m (m>0)個互不相交的有限集T1, T2, , Tm，其中每一個子集本身又是一棵符合本定義的樹，稱為根root的子樹。二叉樹：或為空樹，或是由一個根結點加上兩棵分別稱為左子樹

13、和右子樹的、互不交的二叉樹組成。2、二叉樹的重要特性性質 1 ：在二叉樹的第 i 層上至多有2i-1 個結點。 (i1)性質 2 ：深度為 k 的二叉樹上至多含 2 k-1 個結點（k1）。性質 3 ：對任何一棵二叉樹，若它含有n0 個葉子結點、n2 個度為 2 的結點，則必存在關系式：n0 = n2+1。性質 4 ：具有 n 個結點的完全二叉樹的深度為ë log2nû +1 。性質5 ：若對含n 個結點的完全二叉樹從上到下且從左至右進行1至n的編號，則對于完全二叉樹中任意一個編號為i的結點：(1) 若i=1，則該結點是二叉樹的根，無雙親，否則，編號為ëi/2&#

14、251;的結點為其雙親結點；(2) 若2i>n，則該結點無左孩子，否則，編號為2i 的結點為其左孩子結點；(3) 若2i+1>n，則該結點無右孩子結點，否則，編號為2i+1 的結點為其右孩子結點。3、二叉樹的遍歷方式二、遍歷算法對“二叉樹”而言，可以有四種搜索路徑：先（根）序遍歷-波蘭式中（根）序遍歷-中綴表示后（根）序遍歷-逆波蘭式層序遍歷先序遍歷：A B C D E F中序遍歷：B C A D F E后序遍歷：C B F E D A層序遍歷：A B D C E F4、按給定的表達式建相應二叉樹習題一：已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCH

15、KIJD，畫出此二叉樹。5、森林和二叉樹的對應及轉換設森林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m);二叉樹 B =( LBT, Node(root), RBT );由森林轉換成二叉樹的轉換規則為:若F = ，則B = ；否則，由ROOT( T1 )對應得到Node(root)；由(t11, t12, , t1m )對應得到LBT；由(T2, T3, Tn)對應得到RBT。由二叉樹轉換為森林的轉換規則為：若B = ，則F = ；否則，由Node(root)對應得到ROOT( T1)；由LBT對應得到( t11, t12, ，t1m)；由

16、RBT對應得到(T2, T3, , Tn)。由此，樹的各種操作均可對應二叉樹的操作來完成。應當注意的是，和樹對應的二叉樹，其左、右子樹的概念已改變為：左是孩子，右是兄弟。6、構造哈夫曼樹及編碼1 最優二叉樹（哈夫曼樹）樹中結點的路徑長度定義為：從根結點到該結點的路徑上經過的分支數目。樹的路徑長度定義為：樹中每個結點的路徑長度之和。樹的帶權路徑長度定義為：樹中所有葉子結點的帶權路徑長度之和 WPL(T) = Swklk(對所有葉子結點)。帶權路徑長度最小的二叉樹稱為最優二叉樹，簡稱為最優樹或哈夫曼樹。2 如何構造最優樹赫夫曼算法(兩兩合并方法) ：(1)根據給定的n 個權值w1, w2, , w

17、n，構造n 棵獨立的二叉樹的集合F = T1, T2, , Tn，其中每棵二叉樹中均只含一個帶權值為wi的根結點，其左、右子樹為空樹；(2)在F 中選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；(3)從F中刪去這兩棵樹，同時加入剛生成的新樹；(4)重復(2)和(3)兩步，直至F 中只含一棵樹為止。(5)對樹中的分支進行編碼標注：如果某分支指向左子樹，則其編碼為0，否則為1；(6)產生所有葉子結點的編碼：每個葉子結點的編碼為：從根結點到該葉子結點的路徑上所有分支的編碼的串聯（二進制編碼）。第七章1、圖的概

18、念圖的結構定義:圖是由一個頂點集V 和一個弧集VR構成的數據結構。 Graph = (V , VR )其中，VR<v,w> | v,wV 且P(v,w)<v,w>表示從v 到w 的一條弧，并稱v 為弧尾，w 為弧頭。謂詞 P(v,w) 定義了弧<v,w>的意義或信息。由于“弧”是有方向的，因此稱由頂點集和弧集構成的圖為有向圖。2、圖的存儲及遍歷一、圖的數組(鄰接矩陣)存儲表示有向圖的鄰接矩陣一般為非對稱矩陣無向圖的鄰接矩陣一定是對稱矩陣二、圖的（逆）鄰接表存儲表示三、 有向圖的十字鏈表存儲表示四、無向圖的鄰接多重表存儲表示typedefstructEbox

19、/VisitIf mark; / 訪問標記，用于遍歷intivex, jvex; /該邊依附的兩個頂點的位置structEBox*ilink, *jlink; /指向下一條依附于ivex/ jvex的邊InfoType*info; / 該邊信息指針EBox;3、圖的最小生成樹算法，兩種算法的比較該問題等價于： 構造網的一棵最小（代價）生成樹，即：在 e 條帶權的邊中選取 n-1 條邊（不構成回路），使“權值之和”為最小。算法一：（普里姆算法） 算法二：（克魯斯卡爾算法） 普里姆（Prim）算法的基本思想: 取圖G=(V, E)中任意一個頂點 v 作為生成樹的根（U=v)，之后往生成樹上添加新的

20、頂點 w。在添加的頂點 w （wÎV-U）和已經在生成樹上的頂點v （vÎU） 之間必定存在一條邊，并且該邊的權值在所有連通頂點 v 和 w 之間的邊中取值最小。之后繼續往生成樹上添加頂點，直至生成樹上含有 n-1 個頂點為止?？唆斔箍枺↘ruskal）算法的基本思想：考慮問題的出發點: 為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小，但不能出現回路。具體做法:首先構造一個只含 n 個頂點的森林，然后依權值從小到大從連通網中選擇不使森林中產生回路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通網的最小生成樹。4、圖中兩點最短路徑（源點到任意頂點）迪杰斯特拉算法： 設置輔助數組Dist，其中每個分量Distk 表示當前所求得的從源點