1、數據結構知識點-個人筆記數據結構與算法復習第1部分：1. 概念：數據結構，存儲結構，邏輯結構注：磁盤文件管理系統是樹狀結構。基本概念 （1）數據：指所有能夠輸入到計算機中并被計算機程序處理的符號的總稱（圖像聲音都可以通過編碼歸于數據的范圍），范圍大 （2）數據項：數據的不可分割的最小單元 （3）數據元素：是數據的基本單位，有若干數據項組成，通常作為一個整體考慮 （4）數據對象：性質相同的數據元素的集合，是數據的一個子集。例子：數據項數據元素數據對象數據 表A 科目分數是否及格數學99是語文89是 表B姓名性別身高小花女100小草男120 其中，A表為成績表，B表為學生信息表，這兩張表就是數據；

2、單獨的一張表就稱為數據對象，即A和B表都是一個數據對象；每張表中的每一行就稱為數據元素；姓名，性別，身高，科目，分數就稱為數據項數據結構 定義：相互之間存在一種或多種特定關系的數據元素的集合，這種關系包括三方面的內容，即數據邏輯結構，數據存儲結構，數據的操作。 2. 數據元素是組成數據的基本單位3. 算法，算法分析，算法特性，時間復雜度算法：描述求解問題方法操作步驟的集合。（不是所有的程序都是算法，要滿足五個特性）時間復雜度定義：在算法分析中，一般用算法中的語句的執行次數來度量算法的時間效率，時間效率也就是時間復雜度。計算方法：對于問題規模為n的某個函數f(n)，算法時間復雜度記為T(n)，存

3、在一個正常數c，使cf(n)>T(n)恒成立，則T(n)=Of(n)，稱Of(n)為時間復雜度。 時間復雜度的大O表示法：保留最高次數項，令最高次數項的系數為1。例如O(8)->O(1)，O(2n3+2n2)->O(n3)，O(n*log2 n)第2部分1. 線性表的概念，特點，存儲結構1線性表的概念：線性表是最簡單，最常見，最基本的一種線性結構（數據的邏輯結構的一種），元素之間為線性關系，即除了第一個和最后一個元素之外，所有的元素都有前驅和后繼元素，同一個線性表中的數據類型相同。 當數據元素為0時，可以是空表，但是沒有空圖的說法。線性表的特點：插入刪除算法的時間復雜度為O(

4、n)，不適合多次插入或刪除線性表的存儲方式： （1）順序存儲（又稱順序表）物理地址相連a0A1A2A3A4A5A6A7A8A9 （2）鏈式存儲（又稱鏈式表）數據域指針域 鏈式表的特點：可動態分配空間，插入刪除算法的時間復雜度為O(1) 單鏈表在特定節點插入和刪除元素之前需要遍歷鏈表，所以算法的時間復雜度為O(n)，對于單鏈表的求表長，取元素，插入刪除，釋放掉幾個操作的平均時間復雜度都是O(n)，但是鏈表只需比較元素不用移動元素，所以時間效率上優于順序表2. 順序存儲時插入、刪除（移動元素的個數）（1）定義順序表的數據類型：typedef structInt listmaxsize;Int si

5、ze （2）初始化 void listinitial(sequence *L)L->size=0; （3）插入元素：在i位置前插入一個新的元素，原順序表中i位置之后的元素都要移動，并修改L->size+1； Int insert(sequence *L, int i, int x)int j;if(L->size)>=mavsizeprintf(“線性表已滿”)else if (i<0|i>L->size) printf(“參數不合法”)else for(j=L->size;j>i;i+) 1.2.3.（1）1. 2. 3. 二叉樹轉為樹

6、即把所有右孩子節點變為兄弟節點1. 2.森林轉為樹 森林中各樹先各自轉為二叉樹;依次連到前一個二叉樹的右子樹上樹轉為森林 沿著右孩子鏈搜索，把所有右孩子連線去掉；把得到的每棵二叉樹轉換為樹第6部分 1. 圖的概念、圖的存儲結構，由圖寫矩陣或由矩陣畫圖，矩陣的特點，時空復雜度。圖的概念：由頂點集合及頂點間的關系集合組成的一種數據結構。圖是一種非線性結構，圖形結構是數據的邏輯結構的一種，節點使一對多的關系，不具有明顯的分層關系。解釋及注意事項無向圖若 n 個頂點的無向圖有 n(n-1)/2 條邊, 稱為無向完全圖有向圖若 n 個頂點的有向圖有 n(n-1) 條邊, 稱為有向完全圖無向完全圖在無向圖

7、中任意兩個頂點之間都有連線有向完全圖在有向圖中任意兩個頂點之間都有連線度頂點的度=出度+入度出度頂點指出去的邊入度指向頂點的邊權值權值可以表示從前一個工程到后一個工程所需的時間或者代價路徑長度路徑（path）上邊或者弧的數目簡單路徑若一條路徑上頂點不重復出現就稱為簡單路徑簡單回路除第一個和最后一個頂點相同外，其余點不重復的回路稱簡單回路回路第一個頂點和最后一個頂點相同的回路或環連通圖無向圖中任意兩頂點之間有是連通的，沒有孤立點稱為連通圖連通分量無向圖的最大連通子圖稱為連通分量強連通圖有向圖中任意兩頂點之間是連通的稱為連通圖強連通分量有向圖的最大連通子圖稱為連通分量極小連通子圖是指在包含所有頂點

8、并且保證連通的前提下包含原圖中最少的邊。生成樹包含圖的全部頂點的一個極小連通子圖鄰接矩陣順序存儲 （1）鄰接矩陣：用兩個數組表示圖，一個是存儲圖中頂點信息的一維數組，一個是存儲邊信息的二維數組。無向圖： 有向圖： （2）鄰接矩陣的特點：a、無向圖的鄰接矩陣是一個對稱矩陣。存放時只需要存放上三角矩陣的元素即可 b、查找圖中任一頂點的度方便，易于判定任意兩個頂點之間是否有邊相連。對于無向圖而言，頂點vi的度就是鄰接矩陣中第i行或第i列中非o或非的元素個數。對于有向圖而言，頂點vi的入度是鄰接矩陣中第i列中非0或非的元素個數，頂點vi的出度是鄰接矩陣中第i行中非0或非的元素個數。 c、查找圖中任一條

9、邊或弧的權值方便。 鄰接表順序存儲和鏈式存儲的結合 （1）用一個一維頂點數組存儲頂點信息，每個頂點元素有data域和指針域，指針域存放該頂點的鄰接表的第一個節點的地址。（3）空間復雜度：a、當用二維數組表示鄰接矩陣作圖的存儲結構時，查找每個頂點的鄰接點所需時間為O(n2),其中n為頂點數b、當以鄰接表作圖的存儲結構時，找鄰接點所需時間為O(e),其中e為無向圖中邊的數或有向圖中弧的數c、當以鄰接表作為存儲結構時，深度優先遍歷圖的時間復雜度為O(n + e).2. 圖的周游/遍歷（注意其存儲結構）遍歷：從圖的某個頂點出發，按照一定的順序訪問圖中的每個頂點，且每個頂點有且僅有一個被訪問。深度優先遍

10、歷：類似與樹的先序遍歷，遍歷的結果不唯一。通常采用棧實現解釋：從圖中某個頂點v出發，訪問此頂點，然后依次從v的未被訪問的鄰接頂點出發深度優先遍歷圖，直至圖中所有和v有路徑相通的頂點都被遍歷過。若此時圖中尚有未被訪問的頂點，則另選圖中一個未被訪問的頂點作為起始點，重復上述過程，直到圖中所有頂點都被訪問到為止。廣度優先遍歷：類似于樹的層次遍歷，采用隊列實現 解釋：在訪問了起始點v之后，依次訪問 v的鄰接點；然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點；直到所有頂點都被訪問過為止。 兩種遍歷算法的區別對于上圖的遍歷中，深度優先遍歷得到的結果是：v0,v1,v3,v7,v4,v2,v5,

11、v6 廣度優先遍歷得到的結果是: v0,v1,v2,v3,v4,v5,v6,v73. 最小生成樹算法：PRIM與KRUSKAL算法最小生成樹：連通圖的生成樹中權值總和最小的生成樹，稱為最小代價生成樹(MST)特點：必須包含所有(n)個頂點；最小生成樹有且僅有n-1條邊；不存在回路。構造方法：prim算法和kruskal算法。（1） prim算法：假設圖 G=(V,E) 中已落在生成樹上的頂點集為U，則尚未落在生成樹上的頂點集為 V-U，從 (V-U) 頂點集中選取頂點w加U集合，頂點 w 需滿足下列條件：它和生成樹上的頂點之間的邊上的權值是在聯接這兩類頂點的所有邊中權值最小。（2） krusk

12、al算法：為使生成樹上總的權值之和達到最小，則應使每一條邊上的權值盡可能地小，自然應從權值最小的邊選起，直至選出 n-1 條互不構成回路的權值最小邊為止4. 最短路徑算法：Dijkstra算法最短路徑的概念：即弧的權值之和取最小值的那條路徑算法思想：按各條最短路徑長度遞增的次序，產生最短路徑的算法。5. 拓撲排序、關鍵路徑AOE AOV網：當有一些活動必須在其他活動完成之后才能開始，用頂點表示活動，弧表示活動間的優先關系，這樣的有向圖稱為AOV網 AOE網：用頂點表示事件，弧表示活動，弧上的權值表示活動所需時間構造的有向無環圖稱為AOE網。拓撲排序算法的步驟：a、在有向圖中選擇一個入度為0的頂

13、點，輸出該頂點 b、從圖中刪除所有以它為尾的弧 c、重復執行a,b，直到找不到入度為0的頂點，拓撲排序完成。 注：若最終圖中仍有頂點存在，不存在入度為0的點，則證明有環 若拓撲排序成功則證明無環路。關鍵路徑：AOE網中存在唯一的、入度為零的頂點，叫做源點，存在唯一的、出度為零的頂點，叫做匯點。從源點到匯點的最長路徑的長度即為完成整個工程任務所需的時間，該路徑叫關鍵路徑。第7部分1. 字典的相關概念,ASL（1） 什么是字典：字典是由一些具有相同可辨認特性的數據元素（或記錄）構成的集合。（2） 關鍵字是數據元素中某個數據項的值，用它可以標識（識別）一個數據元素。（3） 檢索：根據給定的某個值，在

14、查找表中確定一個關鍵字等于給定值的數據元素。 1.基于線性表的檢索：順序檢索、二分檢索2.根據關鍵碼值直接訪問：散列檢索，基于數組下標的直接檢索3.樹索引方法：二叉搜索樹、字符樹、B樹（4）平均查找長度ASL查找過程中對關鍵字需要執行的平均比較次數 其中：n是數據元素的個數Pi是查找第i個數據元素概率（通常取等概率,即Pi=1/n）Ci是找到第i個記錄時所經歷的比較次數。（5）查找方法1.靜態查找順序表的查找 思想：從順序表的一端開始掃描，將給定的元素與每個數值比較 成功查找長度ASL: ASL=(n+1)/2，若失敗則ASL=n+1 優點：算法簡單，且對順序結構或鏈表結構均適用。缺點：ASL

15、 太大，時間效率太低。 存儲：順序表查找方法既適用于線性表的順序存儲結構，也適用于線性表的鏈式存儲結構（單鏈表）二分查找(折半查找) （1）基本思想：先給數據排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至前半部內查找；若key大，則縮小至后半部內查找。在每個區域內再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。 （2）對線性表的要求：要求線性表按關鍵字排序，排序本身是一種費時的運算，所以二分法的時間復雜度最好也是O(nlog 2 n)，增加了算法的時間復雜度 （3）算法ASL=log2 n （4）二分查找只適用于順序存儲結構的有序表，鏈表無

16、法實現二分查找。 （5）二分查找的比較次數(Ci)需要借用判定樹來計算判定樹的畫法：按照比較的次數生成判定樹,比較1次的是根結點,比較2次的在第二層,比較3次的在第三層,.一次類推,也可以說是每次的mid即形成判定樹的結點,左子樹上的結點是有序表前半部分的所有結點,右子樹是后半部分的結點.判定樹求平均成功平均查找長度和不成功平均查找長度的方法：例題：2二分查找對線性表的要求，會寫二分檢索算法。代碼如下：int BinarySearch(SequenceList R，ElemType x) int low=0，high=，mid； while(low<=high) mid=(low+hig

17、h)/2； ifmid.key= ey> 態查找二叉排序樹二叉搜索樹（1）特征a、若左子樹非空，則左子樹的所有元素均小于根元素 b若右子樹非空，則右子樹的所有元素均大于根元素 c. 左右子樹本身又各是一顆二叉排序樹（2）二叉排序樹可以通過樹的中序周游獲得關鍵字的有序序列（3）二叉排序樹的生成：每讀入一個元素，建立一個新的結點，若二叉排序樹為空，則新插入的結點成為二叉排序樹的根；若二叉排序樹為非空，則將新結點的值與根結點的值相比較，如果小于根結點的值，則插入到左子樹中，若大于根結點的值，則插入到右子樹中；若與根結點值相等，則停止插入。 （輸入序列 15 13 17 12 14 18）（4）

18、二叉排序樹的的查找（5）二叉排序樹的插入:（6）二叉排序樹的刪除： 1、要刪除無孩子結點，直接刪除該結點2、要刪除只有左孩子或右孩子結點，刪除該結點，且使被刪除結點的雙親結點指向被刪除結點的左孩子結點或右孩子結點3、要刪除有左右孩子的結點，首先尋找數據元素的關鍵字值大于要刪除結點數據元素關鍵字的最小值，即尋找要刪除結點右子樹的最左結點；然后把右子樹的最左結點的數據元素值拷貝到要刪除的結點上；最后刪除右子樹的最左結點。（7）平均查找長度：ni 是每層結點個數； Ci 是結點所在層次數；m 為樹深。最壞情況：插入的n個元素從一開始就有序（單支樹）ASL= (n+1)/2 最好情況：與折半查找中的判

19、定樹相同（即形態比較均衡）樹的深度為ëlog 2n û +1 ASL=log 2(n+1) 1（8）二叉樹排序樹的算法性能比較：a) 二叉排序樹的平均查找長度與二叉樹的形態有關。N個節點不同序可能有n！中不同二叉樹，其中有的二叉樹形態相同。b) 最壞情況下退化為深度為n的單支樹，ASL=(n+1)/2c) 最好情況下，二叉排序樹的心態比較均勻，類似于完全二叉樹，ASL=log2 n，所以需要使用平衡二叉樹（見下）。d) 二叉排序樹的插入，刪除和查找算法的時間復雜度為O(log2 n)1. 散列法中負載因子的概念,設計散列函數需要考慮的因素，拉鏈法散列表的定義 散列表的目的：

20、使用關鍵碼直接找到記錄存儲地址 散列表（哈希表）：以關鍵碼k為自變量，通過一定的函數關系h(k)計算 出對應數值的函數值，把這個值作為k的存儲地址，檢索時用同樣的方法得到存儲地址，然后得到相應的結點。沖突（碰撞）及負載因子 沖突：是指兩個不相等的關鍵碼k1,k2，用散列函數h(k)得到的結果h(k1)=h(k2),這種現象稱為沖突。 發生碰撞的兩個或多個關鍵碼稱為同義詞。 負載因子：設計散列函數需要考慮的因素：i. 計算哈希表函數所需時間ii. 關鍵字長度iii. 哈希表長度（哈希地址范圍）iv. 關鍵字分布情況v. 記錄查找頻率散列表解決沖突的方法 開放地址法：指為發生沖突的關鍵碼找到哈希表

21、中的最近的另一個尚未被使用的位置。（1） 計算第n位置查找成功的平均查找長度為：ASL1= (N1+N1+N10)/空間大小，N為每個元素查找成功的比較次數（2） 計算第n位置查找不成功時的比較次數為，第n位置到第1個沒有數據位置的距離。找不成功的平均查找長度ASL2=（n1+n2+ni）/A ,A位分配的所有空間，不是元素使用的空間（例如h(k)是%15，但是元素只使用了12格，則ASL1除以12，ASL2除以15）例題： 拉鏈法：是把相互沖突的同義詞用同一個單鏈表鏈接起來，若干組同義詞可以組成若干個單鏈表例題：給定關鍵字序列：19,14,23,1,68,20,84,27,55,11,10,

22、79，h(k)=k%13，用拉鏈法解決沖突建立哈希表。2. 二叉排序樹的生成與刪除，ASL的計算3. AVL樹的生成過程（如何調整），ASL的計算樹即平衡二叉樹 （1）特點：要么是一顆空樹，若非空則一定滿足左子樹和右子樹都是平衡二叉樹且左右子樹深度之差不大于1. （2）平衡因子：當前節點的平衡因子定義為當前節點左子樹的深度減右子樹的深度。 （3）最小不平衡子樹：離插入節點最近，且平衡因子的絕對值大于1的節點為根的子樹5.2 AVL樹的平衡調整1. 目的：保證生成的二叉排序樹的高度為log2 n，從而使二叉排序樹的插入，刪除，查找等操作的平均時間為O(log2 n)。所需調整的是最小不平衡子樹，

23、保證二叉樹始終處于平衡狀態。2. 平衡調整模式：LL型調整，LR型調整，RR型調整，RL型調整LL型調整 LR型調整 RR型調整 RL型調整 例題：關鍵字序列為：10，13，19，7，4，8，15，24，33，21試用二叉排序樹和平衡二叉樹進行檢索，給出檢索15時需要的比較次數及成功檢索的平均檢索長度。第8部分1. 排序的方法及比較。堆的定義排序算法優劣的判斷標準排序算法的分類各種算法的思想及實例1) 直接選擇排序算法思想：第一趟：從n個元素中找出關鍵字最小的記錄放在第一個位置 第二趟：從元素集合的2n個元素中找出最小關鍵記錄放在第二個位置 第三趟：.3n.三以此類推直到全部遍歷 要求寫出代碼

24、：int i,j,pos;int temp;int a; ey<ai.key) pos=j; 求從小到大排序則建立最大堆，要從大到小排序則建立最小堆 4.可以用順序存儲創建堆3) 直接插入排序算法 思想：第一步：對n個元素假定以第一個元素是有序序列，比較a0,a1進行排序，形成a0,a1的一個有序序列 第二步：再將a2與a0,a1進行排序，形成有序序列a0,a1,a2 以此類推，直至找出包含所有元素的有序序列.b算作第一趟，c算作第二趟,共需進行n-1趟排序 算法評價：1、最好情況下：總比較次數:n-1，總移動次數2(n-1)，時間復雜度O(n) 2、最壞情況，總比較次數:(n-1)(n-2)/2，總移動次數(n-1)(n-4)/2，時間復雜度O(n2) 3、平均情況下，時間復雜度為O(n2)，空間復雜度為O(1)，算法穩定 4.原始數據越有序，比較次數越少，更適合有序數據，是穩定排序算法4) 希爾排序算法思想：第一步：先把n個元素分成若干組，選擇步長序列t1,t2tk,t1=n/2,tk=1 第二步：將原序列分成若干個序列，分別對各子序列進行直接插入排序實例：算法評價：時間復雜度O(n(log2 n