C語言算法與數據結構.ppt

第十二章 算法與數據結構12.1 算法的基本概念,該節知識點所占試題比重為12，屬于重點考查對象，基本上每次必考，主要考查算法的定義和對算法復雜度的理解。歷次試題分值在04分之間波動。,12.1.1 考點1 算法的定義,算法是對一個問題求解步驟的一種描述，是求解問題的方法，它是指令的有限序列，其中每條指令表示一個或者多個操作。一般來說，一個算法具有以下5個主要特性。 有窮性一個算法(對任何合法的輸入)在執行有窮步后能夠結束，并且在有限的時間內完成。 確定性算法中的每一步都有確切的含義。 可行性算法中的操作能夠用已經實現的基本運算執行有限次來實現。 輸入一個算法有零個或者多個輸入，零個輸入就是算法本身確定了初始條件。 輸出一個算法有一個或者多個輸出，以反映出數據加工的結果。,12.1.2 考點2算法復雜度,算法復雜度包括時間復雜度和空間復雜度，是衡量一個算法好壞的度量。 1、時間復雜度基本操作重復執行的次數的階數 Tnofn 2、空間復雜度是算法所需空間的度量。 G(n) Ofn,例1NXN矩陣相乘 fori1;in;i forj1;jn;j cij0; fork1;kn;k cijcijaik*bkj; ,12.2 數據結構的定義,該節知識點所占試題比重為12，屬于重點考查對象，基本上每次必考，主要考查數據的邏輯結構和存儲結構。歷次試題分值在04分之間波動。,12.2.1考點1什么是數據結構,一、基本概念和術語 數據(data所有能輸入到計算機中去的描述客觀事物的符號 數據元素(data element)數據的基本單位，也稱節點(node)或記錄(record) 數據項(data item)有獨立含義的數據最小單位，也稱域field 數據結構(data structure數據元素和數據元素關系的集合,數據的邏輯結構只抽象反映數據元素的邏輯關系 數據的存儲(物理)結構數據的邏輯結構在計算機存儲器中的實現 存儲結構分為 順序存儲結構借助元素在存儲器中的相對位置來表示數據元素間的邏輯關系 鏈式存儲結構借助指示元素存儲地址的指針表示數據元素間的邏輯關系,1536,元素21400,元素11346,元素3,元素41345,h,鏈式存儲h,12.2.2考點2數據結構的圖形表示,根據數據元素之間關系的不同，通常有4種結構集合、線性結構、樹型結構和圖狀結構。,12.3線性表,線性表一般和其他知識點結合起來出題。在每次所考的數據結構、棧、隊列、鏈表、查找、排序等試題中，均涉及線性表的概念。,12.3.1考點1線性表,一、線性結構特點在數據元素的非空有限集中 存在唯一的一個被稱作“第一個”的數據元素 存在唯一的一個被稱作“最后一個”的數據元素 除第一個外，集合中的每個數據元素均只有一個前驅 除最后一個外，集合中的每個數據元素均只有一個后繼,二、線性表的邏輯結構 定義一個線性表是n個數據元素的有限序列,例 英文字母表(A,B,C,Z是一個線性表,特征 元素個數n表長度，n0空表 1in時 ai的直接前驅是ai-1，a1無直接前驅 ai的直接后繼是ai1，an無直接后繼,12.3.2考點2線性表的順序存儲結構 它用一組地址連續的存儲單元來存儲線性表的元素。 線性表中第i1個元素的存儲位置locai1和第i個元素的存儲位置loc(ai)滿足以下關系 Locai1locaiS其中 S一個元素占用的存儲單元個數 LOCai線性表第i個元素的地址 特點 實現邏輯上相鄰物理地址相鄰 實現隨機存取 實現可用C語言的一維數組實現,12.3.2考點2線性表的順序存儲結構,線性表的第i個元素的存儲位置為 Locailoca1i-1s 其中，loca1表示第1個數據元素的存儲位置，一般被稱為線性表的基地址。,12.3.3考點3線性表的插入和刪除操作,線性表的插入操作是指在線性表的第i個元素與第i1個元素之間插入一個新的數據元素a，使長度為n的線性表 (a1，ai,ai1an) 變成長度為n1的線性表 (a1，ai,a,ai1an) 算法時間復雜度Tn 在長度為n的線性表中插入一個元素時，所需移動的元素的平均次數為n/2,12.3.3考點3線性表的插入和刪除操作,刪除操作是在線性表中刪除一個元素ai，使長度為n的線性表 (a1，ai,ai1an) 變成長度為n-1的線性表 (a1，ai-1,ai1an) 算法時間復雜度Tn 在長度為n的線性表中刪除一個元素所需移動的元素的平均次數為n-1/2,12.4棧,該節知識點所占試題比重為12，屬于重點考查對象，基本上每次必考，主要考查棧的定義、存儲結構及基本運算。歷次試題分值在02分之間波動。,12.4.1 考點1什么是棧,棧是限定僅在表尾進行插入和刪除操作的線性表。 允許插入和刪除的一端叫做棧頂，另一端叫做棧底。 不含有元素的棧叫做空棧。,12.4.2 考點2棧的順序存儲結構,棧的順序存儲結構是利用一組連續地址的存儲單元來存儲從棧底到棧頂的數據元素，同時附設一個指針top指示棧頂元素在順序棧中的位置，一個指針base指示棧底元素的位置。,12.4.3 考點3棧的插入和刪除運算,棧的插入和刪除運算只能在棧頂進行。,12.5隊列,該節知識點占試題比重為12，屬于一般考查對象，主要考查隊列的定義、存儲結構及基本運算。從歷次試題來看，隊列還沒有單獨出過試題，一般以和其他知識點結合起來的試題形式出現。歷次試題分值在02分之間波動。,12.5.1 考點1什么是隊列,隊列是限定了插入和刪除操作的線性表。它只允許在表的一端進行插入操作，而在另外一端進行刪除操作。隊列中，允許插入元素的一端稱為隊尾，允許刪除元素的一端稱為隊頭。,12.5.2 考點2隊列的順序存儲結構,與順序棧類似，隊列的順序存儲結構是利用一組連續地址的存儲單元來存儲從隊頭到隊尾的數據元素，同時附設一個指針front指示隊頭元素在隊列中的位置，一個指針rear指示隊尾元素的位置。當插入新的隊列元素時，rear增1；當刪除隊頭元素時，front增1。,12.5.3 考點3隊列的插入和刪除運算,隊列只允許在表的一端進行插入，而在表的另外一端進行刪除，和我們生活中的隊列一樣是按照先進先出的原則，所以隊列又稱為先進先出的線性表。,12.6 線性單鏈表、雙向鏈表與循環鏈表,該節知識點占試題比重為3，屬于非重點考查對象，主要考查線性單鏈表、雙向鏈表與循環鏈表的結構及基本運算。,12.7樹,該節知識點所占試題比重為31，屬于重點考查對象，每次必考，主要考查二叉樹的定義、存儲結構及3種遍歷算法。,12.7.1 考點1樹的定義,樹型結構是一類重要的非線性數據結構。 樹是n(n0)個結點的有限集。在任意一棵非空樹中有且僅有一個特定的稱為根的結點；當n1時，其余結點可分為m(m0)個互不相交的有限集T1，T2Tm，其中每一個集合本身又是一棵樹，稱為子樹。,第六章 樹和二叉樹,樹是一類重要的非線性數據結構，以分支關系描述數據元素之間的層次結構 6.1 樹 定義樹tree是nn 0個結點的有限集合T，其中 有且僅有一個特殊的結點，稱為樹的根結點root 當n1時，除根結點之外的其余結點可分為mm0個互不相交的有限集合T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹subtree 特點 樹中至少有一個結點根結點 樹中各子樹是互不相交的集合根,子樹T1B,E,F,K,LT2C,GT3D,H,I.J.M,TA,TA,B,C,D,M,樹的特點 1.樹的根結點沒有前驅結點，除根之外的所有結點都有且只有一個前驅結點； 2.樹中所有的結點可以有0個或多個后繼結點。 下圖所示結構均不是樹結構,基本術語 結點node表示樹中的數據元素，包括數據項及若干指向其子樹的分支 結點的度degree結點擁有的子樹個數 樹的度樹中所有結點的度的最大值 葉子leaf結點度為0的結點 分支結點除葉子結點外的所有結點 孩子child結點子樹的根稱為該結點的孩子 雙親parents孩子結點的上層結點叫該結點的雙親,基本術語 兄弟sibling具有同一雙親的孩子結點 結點的層次level從根結點算起，根為第一層，它的孩子為第二層 深度depth樹中結點的最大層次數 有序樹樹中各結點的子樹按照從左到右的次序安排 無序樹與上一情況相反 森林forestmm0棵互不相交的樹的集合,結點A的度3 結點B的度2 結點M的度0,葉子K，L，F，G，M，I，J,結點A的孩子B，C，D 結點B的孩子E，F,結點I的雙親D 結點L的雙親E,結點B，C，D為兄弟 結點K，L為兄弟,樹的度3,結點A的層次1 結點M的層次4,樹的深度4,A,D,H是M的祖先 I是A,D的子孫,6.2 二叉樹 定義 定義二叉樹是nn0個結點的有限集，它或為空樹n0，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成 特點 每個結點至多有二棵子樹即不存在度大于2的結點 二叉樹的子樹有左、右之分，且其次序不能任意顛倒,基本形態,二叉樹性質 性質1 在二叉樹的第i層上至多有2i1結點 i2,i1時，只有一個根結點，2i1201是對的。 假設對所有j1ji命題成立，即第j層上至多有2j1個結點。那么，第i-1層至多有 2i2 個結點。 又二叉樹每個結點的度至多為2 第i層上最大結點數是第i-1層的2倍，即22i22i1 故命題得證,證明用歸納法證明之,二叉樹性質,證明由性質1，可得深度為k 的二叉樹最大結點數是,性質2深度為k的二叉樹至多有2k1 個結點k1,性質3對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0n21,證明n1為二叉樹T中度為1的結點數 因為二叉樹中所有結點的度均小于或等于2 所以其結點總數nn0n1n2 又二叉樹中，除根結點外，其余結點都只有一個 分支進入 設B為分支總數，則nB1 又分支由度為1和度為2的結點發出， Bn12n2 于是，nB1n12n21n0n1n2 n0n21,幾種特殊形式的二叉樹 滿二叉樹 定義一棵深度為k且有2k1 個結點的二 叉,特點每一層上的結點數都是最大結點數樹稱為滿二叉樹。,幾種特殊形式的二叉樹,完全二叉樹 定義深度為k，有n個結點的二叉樹當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為 特點 葉子結點只可能在層次最大的兩層上出現 對任一結點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l1,證明設所求完全二叉樹的深度為k，由完全二叉樹定義及性質2可得2k-1-1n2k-1 或 2k-1n2k 取對數后有k-1log2nk，即log2nklog2n1 又k必為整數， klog2n1,性質4 具有n個結點的完全二叉樹的深度為,log2n1,性質5如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i1in，有 1 如果i1，則結點i是二叉樹的根，無雙 親；如果i1，則其雙親是i/2 2 如果2in，則結點i無左孩子；如果 2in，則其左孩子是2i 3 如果2i1n，則結點i無右孩子；如果 2i1n，則其右孩子是2i1,二叉樹的存儲結構 順序存儲結構 實現按滿二叉樹的結點層次編號，依次存放二叉樹中的數據元素 特點 結點間關系蘊含在其存儲位置中 浪費空間，適于存滿二叉樹和完全二叉樹,鏈式存儲結構 二叉鏈表,typedef struct node datatype data; struct node *lchild, *rchild; JD;,在n個結點的二叉鏈表中，有n1個空指針域,12.7.5 考點5二叉樹的遍歷,遍歷按照一定次序訪問樹中的所有結點， 且每個結點僅被訪問一次的過程。,遍歷二叉樹的方法 先序遍歷先訪問根結點,然后分別先序遍歷左子樹、右子樹 中序遍歷先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹 后序遍歷先后序遍歷左、右子樹，然后訪問根結點 按層次遍歷從上到下、從左到右訪問各結點,D L R,先序遍歷序列A B D C,先序遍歷,若二叉樹為空，遍歷結束。否則 (1)訪問根結點； (2)先序遍歷根結點的左子樹； (3)先序遍歷根結點的右子樹。,L D R,中序遍歷序列B D A C,中序遍歷若二叉樹為空，遍歷結束。否則 (1)中序遍歷根結點的左子樹； (2)訪問根結點； (3)中序遍歷根結點的右子樹。,L R D,后序遍歷序列 D B C A,后序遍歷,若二叉樹為空，遍歷結束。否則 (1)后序遍歷根結點的左子樹； (2)后序遍歷根結點的右子樹； (3)訪問根結點。,先序遍歷,中序遍歷,后序遍歷,層次遍歷,-,,a,*,b,-,c,d,/,e,f,-,,a,*,b,-,c,d,/,e,f,-,,a,*,b,-,c,d,/,e,f,-,,a,*,b,-,c,d,/,e,f,12.8 查找算法,該節知識點占試題比重為9，屬于一般考查對象，主要考查順序查找和二分查找。歷次試題分值在02分之間波動。,12.8 查找算法,查找表由同一類型的數據元素(或記錄)構成的集合 關鍵字是數據元素中某個數據項的值，它可以標識一個數據元素 查找也叫檢索，是根據給定的某個值，在表中確定一個關鍵字等于給定值的記錄或數據元素,12.8 查找算法,查找方法評價 時間復雜度 空間復雜度 平均查找長度ASLAverage Search Length為確定記錄在表中的位置，需和給定值進行比較的關鍵字的個數的期望值叫查找算法的,12.8.1 考點1 順序查找 查找過程從表的一端開始逐個進行記錄的關鍵字和給定值的比較,64,監視哨,比較次數5,比較次數 查找第n個元素 1 查找第n-1個元素2 . 查找第1個元素 n 查找第i個元素 n1-i 查找失敗 n1順序查找方法的ASL12.8.2 考點2二分查找 查找過程每次將待查記錄所在區間縮小一半 適用條件采用順序存儲結構的有序表 算法實現 設表長為n，low、high和mid分別指向待查元素所在區間的上界、下界和中點,k為給定值 初始時，令low1,highn,midlowhigh/2 讓k與mid指向的記錄比較 若krmid.key，查找成功 若krmid.key，則lowmid1 重復上述操作，直至lowhigh時，查找失敗算法描述12.9排序算法,該節知識點所占試題比重為9，屬于一般考查對象，主要考查交換類排序、選擇類排序及插入類排序。從歷次試題來看，以選擇題和填空題的形式出現，分值有波動，如圖2-28所示。,12.9.1 考點1排序概述,10.1概述 排序將一個數據元素(或記錄)的任意序列，重新排列成一個按關鍵字有序的序列叫 排序分類 按待排序記錄所在位置 內部排序待排序記錄存放在內存 外部排序排序過程中需對外存進行訪問的排序 按排序依據原則 插入排序直接插入排序、折半插入排序、希爾排序 交換排序冒泡排序、快速排序 選擇排序簡單選擇排序、堆排序 歸并排序2-路歸并排序 基數排序,12.9.2 考點2插入類排序,直接插入排序 基本思想順序地把待排序列中的各個記錄按其關鍵字的大小，插入到已排序序列中的適當位置 排序過程整個排序過程為n-1趟插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序 直接插入排序方法是穩定的。,例,49 38 65 97 76 13 27,i2 38 38 49 65 97 76 13 27,i3 65 38 49 65 97 76 13 27,i4 97 38 49 65 97 76 13 27,i5 76 38 49 65 76 97 13 27,i6 13 13 38 49 65 76 97 27,i1 ,i7 13 38 49 65 76 97 27,27,97,76,65,49,38,27,10.3 交換排序 起泡排序(Bubble Sort) 基本思想通過相鄰元素之間的比較和交換，使關鍵字較小的元素逐漸從底部移向頂部。 排序過程 將第一個記錄的關鍵字與第二個記錄的關鍵字進行比較，若為逆序r1.keyr2.key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止第一趟起泡排序，結果關鍵字最大的記錄被安置在最后一個記錄上 對前n-1個記錄進行第二趟起泡排序，結果使關鍵字次大的記錄被安置在第n-1個記錄位置 重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,10.4 選擇排序 基本思想不斷從待排序列中選取關鍵字最小的記錄放到已排序列的最后一個記錄后面，直到序列中所有記錄都已排序為止。 簡單選擇排序 排序過程 首先通過n-1次關鍵字比較，從n個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換 再通過n-2次比較，從剩余的n-1個記錄中找出關鍵字次小的記錄，將它與第二個記錄交換 重復上述操作，共進行n-1趟排序后，排序結束,例初始 49 38 65 97 76 13 27 ,i1,13,49,一趟 13 38 65 97 76 49 27 ,i2,27,38,六趟 13 27 38 49 65 76 97 ,排序結束 13 27 38 49 65 76 97,

總結

以上是生活随笔為你收集整理的算法与数据结构c语言版PPT,C语言算法与数据结构.ppt的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。