《數(shù)據(jù)結(jié)構(gòu)》復習

1、數(shù)據(jù)結(jié)構(gòu)復習第一章 緒論一、 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)線性結(jié)構(gòu)、非線性結(jié)構(gòu)順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、散列存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)數(shù)據(jù)類型、抽象數(shù)據(jù)類型。算法、語句的頻度、算法的時間復雜度、算法的漸進復雜度空間復雜度二、 數(shù)據(jù)結(jié)構(gòu)概念：數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算。數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，是通過算法來描述的。數(shù)據(jù)運算的實現(xiàn)依賴于數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)分類方法：按數(shù)據(jù)元素間的邏輯關系分類：集合、線性、樹狀、圖狀或網(wǎng)狀按元素間的邏輯關系和施加的運算分類（抽象數(shù)據(jù)類型）： 線性表、棧、隊列、串、數(shù)據(jù)、廣義表 樹、二叉樹、圖 查找

2、表 文件三、 算法的時間復雜度算法的時間復雜度T(n):算法的時間消耗算法的時間消耗：所有語句的執(zhí)行次數(shù)（頻度）之和算法的漸進時間復雜度（簡稱時間復雜度）：當n->時，T(n)的數(shù)量級。即為T(n)中階最高的那一項，是算法中頻度最大的語句頻度。空間復雜度：除數(shù)據(jù)集合所需的空間外，為實現(xiàn)運算所需的輔助空間的數(shù)量（級）。第二章 線性表一、線性表的邏輯特征數(shù)據(jù)元素在線性表中的相對位置是線性的，可以用一個連續(xù)的整數(shù)編碼來標識，即數(shù)據(jù)元素在線性表中的位置只依賴于它們自己的序號，與數(shù)據(jù)元素的具體內(nèi)容無關。 二、對線性表的基本操作1、 初始化操作2、 求線性表的長度3、 取表中第i個元素:若1iLEN

3、GTH(L)，則函數(shù)值為給定線性表中第i個元素，否則為元素NULL。4、 定位函數(shù):返回元素x的位序。5、 INSERT（L，i,b）:前插函數(shù)。在第i 個元素前插入數(shù)據(jù)元素b。6、 DELETE（L，i）:刪除第i個數(shù)據(jù)元素。7、 刪除指針p指定的結(jié)點。三、線性表的順序存儲結(jié)構(gòu)（向量結(jié)構(gòu)）用一組連續(xù)的存儲單元依次存儲線性表的元素。 特點：1、邏輯上相鄰的數(shù)據(jù)元素ai和ai+1的存儲位置也相鄰。即以數(shù)據(jù)元素在計算機內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關系。 loc(ai)=loc(a1)+(i-1)*L loc(a1)是第一個數(shù)據(jù)元素的存儲位置，通常稱為線性表的起始地址或基地址。

4、 2、只要確定了存儲線性表的起始地址，就直接確定了線性表中任一數(shù)據(jù)元素的存儲位置，并且通過該公式實現(xiàn)對線性表元素的隨機存取（訪問）。 線性表順序存儲結(jié)構(gòu)的C描述線性表順序存儲結(jié)構(gòu)的操作1、定位操作：定位平均比較次數(shù)為(i)/n=(n+1)/2，算法的時間復雜度為O(n)。 不成功，則要比較n+1。2、 INSERT(v,i,b):前插操作，在第i個數(shù)據(jù)元素之前插入一個元素b。所需移動元素次數(shù)的期望值（平均次數(shù)）為： Eis=pi(n-i+1)=(n(n+1)/2)/(n+1)=n/2 (i=1,2,n+1) 即：算法的時間復雜度為O(n).3、刪除運算：在長度為n的線性表中刪除第i個元素。刪除

5、第i個元素移動次數(shù)為n-i平均移動次數(shù)為Ede=(n-i)/n=(n-1)/2 (i=1,2,.,n)刪除運算的時間復雜度為O(n)缺點：插入刪除操作可能要移動大量元素。四、線性表的鏈式存儲結(jié)構(gòu)特點：用一組任意的存儲單元存放線性表的數(shù)據(jù)元素（存儲單元可以不連續(xù)）。 數(shù)據(jù)元素間的邏輯關系表示：存儲一個指示其直接后繼的信息。 用獨立結(jié)點來存儲數(shù)據(jù)元素的信息和指示數(shù)據(jù)元素間的邏輯關系。 實現(xiàn)的C語言描述單鏈表的特點 1、頭指針：指示線性鏈表中第一個結(jié)點。 2、最后一個結(jié)點無后繼，其指針域設為“空”（NIL），表示鏈表到此結(jié)束。 3、結(jié)點指針域：把內(nèi)存中可能不連續(xù)的數(shù)據(jù)元素順序組成一個線性表。 4、要

6、訪問任一元素，必須從頭指針出發(fā)尋找，是順序訪問結(jié)構(gòu)。5、增設一個頭結(jié)點，作為線性表的第一個結(jié)點，可以簡化插入、刪除算法。線性鏈表的運算1、在相鄰元素a和b之間插入一個值為x的數(shù)據(jù)元素的基本操作步驟：生成一個數(shù)據(jù)域值為x的結(jié)點s;使x結(jié)點的指針域指向結(jié)點b: s->next=p->next;修改a結(jié)點的指針域指向結(jié)點x:p->next=s;2、在第i個元素前插入一個元素x的步驟：生成一個數(shù)據(jù)域值為x的結(jié)點s;查找第i-1個接點p使x結(jié)點的指針域指向結(jié)點p的后繼接點: s->next=p->next;使p結(jié)點的指針域指向結(jié)點s:p->next=s; 3、刪除第i

7、個結(jié)點。 實現(xiàn)：修改前驅(qū)結(jié)點(第i-1結(jié)點)的指針域使其指向第i+1個結(jié)點。 插入和刪除運算的關鍵：尋找前驅(qū)結(jié)點。在兩種運算中，WHILE循環(huán)平均比較次數(shù)： (i)/(n+1)=(n+1)/2 （I=1,2,n+1）循環(huán)體的執(zhí)行次數(shù): (（i-1）/(n+1)=n/2 時間復雜度為(n)。 采用線性鏈表的優(yōu)點： 有效利用存儲資源，提高程序運行的可靠性。有多少數(shù)據(jù)元素，才申請多少相應的存儲空間。不使用的單元可歸還給系統(tǒng)。存儲密度 插入和刪除，不需移動元素。3、循環(huán)鏈表 使最后一個結(jié)點的指針域又指向第一個結(jié)點或頭結(jié)點。這樣的線性鏈表就叫循環(huán)鏈表。特點：從任一結(jié)點出發(fā)，可以訪問表中所有其它結(jié)點。 為

8、了使得空表和非空表的運算統(tǒng)一，設置一個表頭結(jié)點。它的值域或為空. 用指向表尾結(jié)點的指針來表示循環(huán)鏈表的優(yōu)點4、雙向循環(huán)鏈表雙向鏈表：每個結(jié)點設置兩個指針，一個指向直接前驅(qū)，一個指向直接后繼。雙向循環(huán)鏈表：在雙向鏈表中，若第一個結(jié)點（后頭結(jié)點）的前向指針指向最后一個結(jié)點，最后一個結(jié)點的后向指針指向第一個結(jié)點（或頭結(jié)點），則就是雙向循環(huán)鏈表。雙向循環(huán)鏈表結(jié)點的插入：在P結(jié)點前插入一個結(jié)點S雙向循環(huán)鏈表結(jié)點的刪除 第三章 棧和隊列一、棧（stack）1、棧的定義：限定僅在表的一端進行插入和刪除操作的線性結(jié)構(gòu)。 棧頂（top）： 允許進行插入和刪除操作的一端。 2、棧的特點：后進先出（或先進后出）：L

9、ast In First OutLIFO3、棧的基本操作 INISTACK(s):初始化棧。設定一個空棧。EMPTY(S):判?？蘸瘮?shù)。棧空時返回真，否則返回假。PUSH（S，x）：入棧操作函數(shù)。在棧頂插入元素x。POP（S,&e）：出棧函數(shù)。若棧不空，返回棧頂元素值，并從棧中刪除該元素，否則返回空元素NULL。GETTOP（S,&e）：取棧頂元素函數(shù)。若棧不空，返回棧頂元素值，否則返回空元素NULL。4、棧的順序存儲表示及其實現(xiàn)用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。實現(xiàn)的C描述棧的初始化進棧操作出棧操作 棧的“下溢”極其意義。5、棧的鏈式存儲結(jié)構(gòu) 鏈表頭指針

10、用Top表示。 棧空時：Top=NIL 入棧：每當一個元素進棧時，申請一個新結(jié)點，插入到表頭。 出棧：每當一個元素出棧時，從表頭釋放一個結(jié)點。 判斷進棧、出棧序列的正確性 二、隊列（Queue）定義：隊列是一種先進先出的線性表（結(jié)構(gòu)）。 特點：插入運算在表的一端進行。刪除運算在表的另一端進行。 隊頭：允許刪除的一端，用front表示。 隊尾：允許插入的一端，用rear表示。 3、隊列的基本操作INIQUEUE（Q）：初始化隊列，設置一個空隊列。EMPTY（Q）：判隊列空函數(shù)。隊列空，返回true,否則返回false。ENQUEUE（Q）：入隊操作，在隊列尾部插入一個元素。DEQUEUE（Q）：

11、出隊操作，若隊不空，出隊頭元素，并返回該元素值，否則返回NULL。4、隊列的鏈式存儲結(jié)構(gòu)-鏈隊列 C語言描述 頭指針-指向刪除的一端 尾指針-指向插入的一端 隊空時： 頭、尾指針為NULL,或都指向頭結(jié)點。 出隊操作要判斷尾指針的正確性5、隊列的順序存儲結(jié)構(gòu) 假上溢。 假上溢的原因是：頭指針和尾指針的值總是不斷增加，已使用過的存儲單元無法再使用。 解決假上溢的方法：循環(huán)隊列解決隊空隊滿都有頭尾指針相等問題： 1、一個標志字段區(qū)分隊空隊滿 2、少用一個元素空間，個元素單元最多只存放個元素，且： front=rear -隊空 （rear+1）%m=front -隊滿3、長度記數(shù)器要能夠區(qū)分線性表、

12、棧、隊列的異同第四章 串一、串及其操作1、串的邏輯結(jié)構(gòu)定義：串（字符串）：是由個或多個字符組成的有限序列。 串的長度，空串，空格串、子串，主串、主串、字符在串中的位置、子串在串中的位置。2、串的基本操作判斷相等、求串長、聯(lián)接、串復制、求子串、串的模式匹配二、 串的存儲結(jié)構(gòu) 1、靜態(tài)存儲分配：分配一組連續(xù)的存儲單元存放串的字符序列。C語言可描述 2、鏈式存儲結(jié)構(gòu)-動態(tài)存儲結(jié)構(gòu)-塊鏈存儲結(jié)構(gòu) 存儲密度=串值所占存儲位/實際分配的存儲位3、堆分配與存儲映像第五章 數(shù)組和廣義表一、 數(shù)組的邏輯結(jié)構(gòu)特點 數(shù)組元素個數(shù)一個元素都受n個關系的約束,每個關系都是線性關系。每個數(shù)組元素屬于同一數(shù)據(jù)類型。每個數(shù)組

13、元素對應于一組下標，每個下標有由一對界偶（ci,di）限定其范圍。數(shù)組的兩個定義1、一個 n維數(shù)組被定義為一個線性表，其元素是一個 n-1維數(shù)組。2、一個 n維數(shù)組的數(shù)據(jù)元素受n個關系的約束，且每個關系都是線性的。二、對數(shù)組的操作： 給定一組下標，存取相應的數(shù)據(jù)元素。 給定一組下標，修改相應數(shù)據(jù)中的某一個或幾個數(shù)據(jù)項的值。三、數(shù)組的順序存儲結(jié)構(gòu) 二維數(shù)組的兩種分配方式： 行主分配：先分配第一行的元素，以后每一行的元素緊跟其上一行的后面進行分配。列主分配：先分配第一列的元素，以后每一列的元素緊跟其前一列的后面進行分配。計算數(shù)組元素地址的公式 對于二維以上數(shù)組：行主分配為低下標優(yōu)先。列主分配為高下

14、標優(yōu)先：總是前面的下標從小變到大，后面的下標在增值。計算數(shù)組元素地址的公式四、矩陣的壓縮存儲1、 特殊矩陣：對稱矩陣、對角矩陣的壓縮存儲及其與一維數(shù)組下標的對應關系。2、 稀疏矩陣：三元組表三元組順序表。五、廣義表 1、特點：ai 可以單個元素，也可以是廣義表。 2、表頭、表尾的概念取列表表頭操作取列表表尾操作第六章 樹和二叉樹 一、樹（Tree）的定義、 遞歸定義-樹的固有特性 在任意一棵非空樹中：有一個特定的稱為根（root）的結(jié)點。當n>1時，其余結(jié)點分為（>0）個互不相交的子集,每個集合本身又是一棵樹，并且稱為根的子樹、 非遞歸定義-從樹的結(jié)點間的直接關系看 在任意一棵非空

15、樹中：有且僅有一個沒有前驅(qū)的結(jié)點-根。當n>1時，其余結(jié)點有且僅有一個直接前驅(qū)。所有結(jié)點都可以有個或多個后繼。3、樹的基本術語: 樹的結(jié)點：包含一個數(shù)據(jù)元素及若干指向子樹的分支(關系的表示)。 結(jié)點的度、樹葉、非葉結(jié)點、樹的度、結(jié)點的孩子、雙親結(jié)點的層次、樹的深度、有序樹、森林二、二叉樹（binery tree）1、二叉樹的定義：由一個根結(jié)點加上兩個互不相交的被稱為該根的左右兩個子樹組成。 2、二叉樹的特點：結(jié)點的度最大為（但不一定有度為2的結(jié)點）；子樹有左右之分，不能顛倒。3、二叉樹的五種形態(tài)4、二叉樹的特性第層的結(jié)點數(shù)最大為i-1；深度為的二叉樹的結(jié)點總數(shù)最大為k-1； 02+1；滿

16、二叉樹、完全二叉樹具有個結(jié)點的完全二叉樹深度為 (int)(log2n)+1具有個結(jié)點的完全二叉樹，對任一結(jié)點，1<=i<=n 有： i=1 根結(jié)點，無雙親 i>1 其雙親結(jié)點為 int(i/2) (PARENTi) 2i>n 結(jié)點i無左孩。否則結(jié)點i的左孩lchildi=2i 2i+1>n 結(jié)點i無右孩。否則結(jié)點i的右孩rchildi=2i+1 5、二叉樹的存儲結(jié)構(gòu) 、順序表示法 ：k 、鏈式存儲結(jié)構(gòu)：二叉鏈表存儲結(jié)構(gòu)：（標準形式的存儲結(jié)構(gòu)）結(jié)點結(jié)構(gòu) 空指針個數(shù)三、遍歷二叉樹 1、遍歷二叉樹：指以一定的次序訪問二叉樹的每個結(jié)點，且每個結(jié)點僅訪問一次。 DLR-前

17、序遍歷 先根遍歷 先序遍歷 LDR-中序遍歷 中根遍歷 LRD-后序遍歷 后根遍歷知道前序和中序，或知道中序和后序序列，構(gòu)造其二叉樹。通過某種遍歷方式：求二叉樹的深度、求葉結(jié)點數(shù)、求左右子樹的深度等 2、線索二叉樹 在中序遍歷過程中建立中序線索樹算法在中序線索二叉樹中求結(jié)點的前驅(qū)和后繼在中序線索二叉樹中刪除一個結(jié)點的算法。四、 樹和森林1、樹的二叉樹表示 2、由樹轉(zhuǎn)換成二叉樹有兩個特點： 根結(jié)點沒有右子樹。 轉(zhuǎn)換生成的二叉樹中各結(jié)點的右孩子是原樹中該結(jié)點的兄弟。3、森林轉(zhuǎn)換成二叉樹4、二叉樹轉(zhuǎn)換成森林5、樹的先根遍歷何后根遍歷及其與對應二叉樹遍歷的關系，樹的層次遍歷五、哈夫曼樹及其應用1、哈夫

18、曼樹-最優(yōu)二叉樹 路徑、路徑長度、樹的路徑長度、結(jié)點的帶權路徑長度、樹的帶權路徑長度哈夫曼樹；哈夫曼算法哈夫曼編碼第七章 圖一、基本概念1、圖的定義 （，）。2、概念：有向圖、無圖、無向完全圖、有向完全圖、稀疏圖、稠密圖、網(wǎng)、子圖。鄰接、頂點的度、頂點的入度、頂點的出度、圖的頂點的度與邊的關系；路徑、路徑長度、簡單路徑、回路、簡單回路 連通圖、連通分量、強連通圖、強連通分量、生成樹、連通圖的生成樹二、圖的存儲結(jié)構(gòu)1、鄰接矩陣表示法圖的順序存儲結(jié)構(gòu)用一個一維數(shù)組存儲數(shù)據(jù)元素（頂點）的信息。用一個二維數(shù)組來存儲數(shù)據(jù)元素之間的相鄰關系（邊或?。┑男畔ⅰ｀徑泳仃嚤硎镜奶攸c：無向圖的鄰接矩陣是對稱的。2

19、、鄰接表(adjacency list)表示法-圖的鏈式存儲結(jié)構(gòu) 無向圖：個結(jié)點，條邊，個表頭結(jié)點，表結(jié)點。每個鏈表表結(jié)點的個數(shù)就是對應頂點的度。 有向圖：表結(jié)點數(shù)等于邊數(shù)。 每個鏈表表結(jié)點的個數(shù)就是對應頂點的出度。 若要求頂點的入度，必須對鄰接鏈表進行掃描統(tǒng)計。 逆鄰接表：對每個頂點Vi建立一個以Vi為頭的弧的鏈表。 三、圖的遍歷1、圖的遍歷定義2、深度優(yōu)先搜索法-縱向優(yōu)先搜索法 圖的深度優(yōu)先搜索算法. 算法時間復雜度分析： 鄰接矩陣：對每個頂點，都要查遍所有的鄰接點，時間復雜度為O(n2)。 鄰接表：查找鄰接點的時間復雜度為O(e),整個算法的時間復雜度為O(n+e)。 3、廣度優(yōu)先搜索法

20、-橫向優(yōu)先搜索 圖的廣度優(yōu)先搜索算法.四、圖的連通性1、連通圖的生成樹：是連通圖的極小連通子圖，它包含圖中所有頂點，但只有構(gòu)成n個頂點的一棵樹的n-1條邊。深度優(yōu)先搜索樹、廣度優(yōu)先搜索樹。廣度優(yōu)先搜索樹的深度不大于深度優(yōu)先搜索樹生成森林。2、最小生成樹 邊賦以權值的圖稱為網(wǎng)或帶權圖。 最小生成樹 MST性質(zhì)。普里姆（Prim）算法：克魯斯卡爾(Kruskl)算法： 五、拓撲排序 有向無環(huán)圖DAG圖拓撲有序序列、拓撲排序拓撲排序方法六、最短路徑從某個源點到其余個頂點的最短路徑：迪杰斯特拉（Dijkstra）算法：按路徑長度遞增的次序產(chǎn)生最短路徑。第九章 查找查找表、靜態(tài)查找表、動態(tài)查找表。關鍵字

21、查找：根據(jù)給定的某個值，在查找表中確定一個其關鍵字值等于給定值的數(shù)據(jù)元素或記錄（在列表中的位置）的過程。一、順序表的查找 哨兵元素。 查找操作的性能分析： 空間復雜度：O(1)，增加了一個元素的輔助空間。 時間復雜度：成功查找所需平均次數(shù)為： （）n(n+1)/(2n)=（n+1）/2 若八哨兵放在n+1的位置，算法如何實現(xiàn)。 二、有序表的查找折半查找有序表。元素按關鍵字非遞減（或非遞增）順序排列。查找方法：折半查找-二叉判定樹。優(yōu)點：效率高。不適合經(jīng)常的插入和刪除元素的表。折半查找條件：元素關鍵字非遞減有序，順序存儲結(jié)構(gòu) 三、索引順序查找-分塊查找分塊查找方法：將表中元素均勻地分成塊，塊間按

22、大小排序，塊內(nèi)可以不排序索引表中關鍵字按從小到大排序。各塊內(nèi)記錄可以按或不按關鍵字排序。 查找過程：第一步：根據(jù)給定值在索引表中進行順序或折半查找。第二步：在塊中進行順序查找。 查找效率：平均查找長度塊的最佳長度：sqrt()，平均查找長度sqrt(n)+1四、二叉排序樹特點：所有左子樹的結(jié)點值都小于根結(jié)點，所有右子樹的結(jié)點值都大于根結(jié)點 二叉排序樹的構(gòu)造方法； 對二叉排序樹按中序遍歷輸出每個結(jié)點的值，就得到了從小到大的排列順序。在二叉排序樹上插入結(jié)點的三個特點：無需遍歷樹，只需從根結(jié)點出發(fā)，走一條從根到葉結(jié)點的路徑。每次插入的新結(jié)點都是二叉排序樹的葉結(jié)點。這樣，在二叉排序樹上插入結(jié)點不必移動

23、其它結(jié)點。二叉排序樹的構(gòu)造依賴于數(shù)據(jù)元素的插入次序，即同一組數(shù)，插入次序不同，構(gòu)造出的二叉排序樹也不同。五、B_樹B_樹的定義n個結(jié)點的B_樹的深度B_樹數(shù)據(jù)插入和刪除的基本要點六、哈希法查找（hashing search）-散列地址編碼法哈希函數(shù)哈希函數(shù)是一個壓縮函數(shù)?？赡軐е虏煌P鍵字值映射到同一散列地址的情況。 同義詞哈希函數(shù)構(gòu)造的基本方法 直接定址法 數(shù)字分析法 平方取中法 折疊法與移位法除留余數(shù)法模除取余法解決沖突的常用方法 開放定址法：線性探測再散列鏈地址法哈希表的查找及其分析查找過程中需與給定值進行比較的關鍵字的個數(shù)取決于下面三種因素： 哈希函數(shù)：哈希函數(shù)的好壞首先影響沖突的頻繁程度。 處理沖突方法：對同一組關鍵字，哈希函數(shù)相同，則不同的沖突處理方法得到不同的哈希表，其平均查找程度也不相同。 哈希表的裝填因子：相同的哈希函數(shù)和相同的沖突處理方法，填滿程度不同，發(fā)生沖突的多少不同。裝滿程度用裝填因子表示：=表中填入的記錄數(shù)/哈希表的長度越小，產(chǎn)生沖突的可能性就越小。第十章 內(nèi)部排序-分類一、基本概念1、排序：將記錄關鍵字無序的序列調(diào)整為一個