數據結構知識點全面總結—精華版(編輯修改稿)

　

【文章內容簡介】 ，但其實數組中還有空位置，這就叫“假溢出”。解決假溢出的途徑———采用循環隊列。，若約定隊首指針指向隊首元素的前一個位置。那么，從循環隊列中刪除一個元素時，其操作是先 移動隊首位置 ，后 取出元素。、棧、隊的異同點：相同點：邏輯結構相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表（只是對插入、刪除運算加以限制）。不同點：① 運算規則不同：線性表為隨機存取；而棧是只允許在一端進行插入和刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。② 用途不同，線性表比較通用；堆棧用于函數調用、遞歸和簡化設計等；隊列用于離散事件模擬、OS作業調度和簡化設計等。第四章 串內容提要：◆ 串是數據元素為字符的線性表，串的定義及操作。串即字符串，是由零個或多個字符組成的有限序列，是數據元素為單個字符的特殊線性表。串比較：int strcmp(char *s1,char *s2)。 求串長：int strlen(char *s)。 串連接：char strcat(char *to,char *from) 子串T定位：char strchr(char *s,char *c)。 ◆ 串的存儲結構，因串是數據元素為字符的線性表，所以存在“結點大小”的問題。模式匹配算法串有三種機內表示方法：模式匹配算法：算法目的：確定主串中所含子串第一次出現的位置（定位）定位問題稱為串的模式匹配，典型函數為Index(S,T,pos)BF算法的實現—即編寫Index(S, T, pos)函數BF算法設計思想：將主串S的第pos個字符和模式T的第1個字符比較， 若相等，繼續逐個比較后續字符；若不等，從主串S的下一字符（pos+1）起，重新與T第一個字符比較。 直到主串S的一個連續子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值 0。Int Index_BP(SString S, SString T, int pos) { //返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數值為0. // 其中，T非空，1≤pos≤StrLength(S) i=pos。 j=1。 while ( i=S[0] amp。amp。 j=T[0] ) //如果i,j二指針在正常長度范圍， { if (S[i] = = T[j] ) {++i, ++j。 } //則繼續比較后續字符 else {i=ij+2。 j=1。} //若不相等，指針后退重新開始匹配 } if(jT[0]) return iT[0]。 //T子串指針j正常到尾，說明匹配成功， else return 0。 //否則屬于iS[0]情況，i先到尾就不正常} //Index_BP補充重點：？答：有區別。空串(Null String)是指長度為零的串；而空白串(Blank String),是指包含一個或多個空白字符‘ ’(空格鍵)的字符串.2. “空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串。” 第6章 樹和二叉樹內容提要：◆ 樹是復雜的非線性數據結構，樹，二叉樹的遞歸定義，基本概念，術語。樹：由一個或多個(n≥0)結點組成的有限集合T，有且僅有一個結點稱為根（root），當n1時，其余的結點分為m(m≥0)個互不相交的有限集合T1,T2，…，Tm。每個集合本身又是棵樹，被稱作這個根的子樹 。二叉樹：是n（n≥0）個結點的有限集合，由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。術語：P88◆ 二叉樹的性質，存儲結構。性質1: 在二叉樹的第i層上至多有2i1個結點（i0）。性質2: 深度為k的二叉樹至多有2k1個結點（k0）。性質3: 對于任何一棵二叉樹，若2度的結點數有n2個，則葉子數（n0）必定為n2＋1 性質4: 具有n個結點的完全二叉樹的深度必為 235。 性質5: 對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結點，其左孩子編號必為2i，其右孩子編號為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）。 二叉樹的存儲結構：一、順序存儲結構按二叉樹的結點“自上而下、從左至右”編號，用一組連續的存儲單元存儲。若是完全/滿二叉樹則可以做到唯一復原。不是完全二叉樹：一律轉為完全二叉樹！方法很簡單，將各層空缺處統統補上“虛結點”，其內容為空。缺點：①浪費空間；②插入、刪除不便 二、鏈式存儲結構用二叉鏈表即可方便表示。一般從根結點開始存儲。優點：①不浪費空間；②插入、刪除方便 ◆ 二叉樹的遍歷。指按照某種次序訪問二叉樹的所有結點，并且每個結點僅訪問一次，得到一個線性序列。遍歷規則———二叉樹由根、左子樹、右子樹構成，定義為D、 L、R若限定先左后右，則有三種實現方案： DLR LDR LRD先序遍歷 中序遍歷 后序遍歷 ◆ 樹的存儲結構，樹、森林的遍歷及和二叉樹的相互轉換。 回顧2：二叉樹怎樣還原為樹？ 要點：逆操作，把所有右孩子變為兄弟！ 討論1：森林如何轉為二叉樹？ 法一：① 各森林先各自轉為二叉樹；② 依次連到前一個二叉樹的右子樹上。 法二：森林直接變兄弟，再轉為二叉樹 討論2：二叉樹如何還原為森林？ 要點：把最右邊的子樹變為森林，其余右子樹變為兄弟樹和森林的存儲方式：樹有三種常用存儲方式：①雙親表示法 ②孩子表示法 ③孩子—兄弟表示法問：樹→二叉樹的“連線—抹線—旋轉” 如何由計算機自動實現？答：用“左孩子右兄弟”表示法來存儲即可。存儲的過程就是樹轉換為二叉樹的過程！樹、森林的遍歷：① 先根遍歷：訪問根結點；依次先根遍歷根結點的每棵子樹。② 后根遍歷：依次后根遍歷根結點的每棵子樹；訪問根結點。討論：樹若采用“先轉換，后遍歷”方式，結果是否一樣？1. 樹的先根遍歷與二叉樹的先序遍歷相同； 2. 樹的后根遍歷相當于二叉樹的中序遍歷；3. 樹沒有中序遍歷，因為子樹無左右之分。① 先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結點；先根遍歷第一棵樹的根結點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構成的森林。② 中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結點的子樹森林；訪問第一棵樹的根結點；中根遍歷除去第一棵樹之后剩余的樹構成的森林。◆ 二叉樹的應用：哈夫曼樹和哈夫曼編碼。Huffman樹：最優二叉樹（帶權路徑長度最短的樹）Huffman編碼：不等長編碼。樹的帶權路徑長度：（樹中所有葉子結點的帶權路徑長度之和）構造Huffman樹的基本思想：權值大的結點用短路徑，權值小的結點用長路徑。構造Huffman樹的步驟（即Huffman算法）：(1) 由給定的 n 個權值{ w1, w2, …, wn }構成n棵二叉樹的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉樹 Ti 中只有一個帶權為 wi 的根結點，其左右子樹均空。(2) 在F 中選取兩棵根結點權值最小的樹 做為左右子樹構造一棵新的二叉樹，且讓新二叉樹根結點的權值等于其左右子樹的根結點權值之和。(3) 在F 中刪去這兩棵樹，同時將新得到的二叉樹加入 F中。(4) 重復(2) 和(3) , 直到 F 只含一棵樹為止。這棵樹便是Huffman樹。具體操作步驟：學習重點：（本章內容是本課程的重點）◆ 二叉樹性質及證明方法，并能把這種方法推廣到K叉樹。◆ 二叉樹遍歷，遍歷是基礎，由此導出許多實用的算法，如求二叉樹的高度、各結點的層次數、度為0、2的結點數。◆ 由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構造一棵二叉樹。由前序和后序序列不能唯一確定一棵二叉樹。 ◆ 完全二叉樹的性質。◆ 樹、森林和二叉樹間的相互轉換。◆ 哈夫曼樹的定義、構造及求哈夫曼編碼。補充：？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前k1層是滿的，但最底層卻允許在右邊缺少連續若干個結點。滿二叉樹是完全二叉樹的一個特例。2. Huffman樹有什么用？最小冗余編碼、信息高效傳輸第7章 圖內容提要：◆ 圖的定義，概念、術語及基本操作。 圖：記為 G＝( V, E ) 其中：V 是G 的頂點集合，是有窮非空集； E 是G 的邊集合，是有窮集。 術語：見課件◆ 圖的存儲結構。(數組)表示法① 建立一個頂點