C語言課件-數(shù)據(jù)結構與算法

第1章數(shù)據(jù)結構與算法1.1算法1.2數(shù)據(jù)結構的根本概念1.3線性表及其順序存儲結構1.4棧和隊列1.5線性鏈表1.6樹和二叉樹1.7查找技術1.8排序技術算法的根本概念算法的復雜度分析1.1算法算法的根本概念通俗的定義：算法是指解題方案的準確而完整的描述。算法的根本特征1.可行性2.確定性3.有窮性4.擁有足夠的情報算法的嚴格定義： 算法是一組嚴謹?shù)囟x運算順序的規(guī)那么，并且每一個規(guī)那么都是有效的，且是明確的，此順序將在有限的次數(shù)下終止。算法的根本要素(1)算法中對數(shù)據(jù)的運算和操作①算術運算②邏輯運算③關系運算④數(shù)據(jù)傳輸(2)算法的控制結構傳統(tǒng)流程圖、N-S結構化流程圖、算法描述語言等。算法設計根本方法1.列舉法 根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗哪些是需要的，哪些是不需要的。 因此，列舉法常用于解決“是否存在”或“有多少種可能”等類型的問題，例如求解不定方程的問題。例：設每只母雞值3元，每只公雞值2元，兩只小雞值1元?，F(xiàn)要用100元錢買100只雞，設計買雞方案。假設買母雞I只，公雞J只，小雞K只。2.歸納法通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關系。3.遞推從的初始條件出發(fā)，逐次推出所要求的各中間結果和最后結果。4.遞歸將一個復雜的問題歸結為假設干個較簡單的問題，然后將這些較簡單的每一個問題再歸結為更簡單的問題，這個過程可以一直做下去，直到最簡單的問題為止。5.減半遞推技術所謂“減半”，是指將問題的規(guī)模減半，而問題的性質不變。所謂“遞推”，是指重復“減半”的過程。例：二分法求方程實根6.回溯法通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，假設試探成功，就得到問題的解，假設試探失敗，就逐步回退，換別的路線再進行試探。例：迷宮問題算法的復雜度分析算法的時間復雜度算法的空間復雜度執(zhí)行算法所需要的內存空間。1.2數(shù)據(jù)結構的根本概念什么是數(shù)據(jù)結構數(shù)據(jù)結構的圖形表示線性數(shù)據(jù)結構與非線性數(shù)據(jù)結構目的：提高數(shù)據(jù)處理的效率提高數(shù)據(jù)處理的速度盡量節(jié)省計算機存儲空間數(shù)據(jù)結構三個方面的問題：(1)數(shù)據(jù)的邏輯結構(2)數(shù)據(jù)的存儲結構(3)對各種數(shù)據(jù)結構進行的運算什么是數(shù)據(jù)結構數(shù)據(jù)結構是指相互有關聯(lián)的數(shù)據(jù)元素集合?，F(xiàn)實世界中客觀存在的一切個體都可以是數(shù)據(jù)元素。描述一年四季的季節(jié)名春，夏，秋，冬可以作為季節(jié)的數(shù)據(jù)元素；表示數(shù)值的各個數(shù)18，11，35，23，16，…可以作為數(shù)值的數(shù)據(jù)元素；前后件關系前后件關系(也稱為直接前驅和直接后繼)是數(shù)據(jù)元素之間的自然存在的一個根本關系，但前后件關系所表示的實際意義是隨具體對象的不同而不同。一般來說，數(shù)據(jù)元素之間的任何關系都可以用前后件關系來描述。數(shù)據(jù)的邏輯結構一個數(shù)據(jù)結構應包含兩方面的信息〔1〕表示數(shù)據(jù)元素的信息；〔2〕表示各數(shù)據(jù)元素之間的前后件關系〔即邏輯關系〕數(shù)據(jù)的邏輯結構是指反映數(shù)據(jù)元素之間邏輯關系的數(shù)據(jù)結構。數(shù)據(jù)的邏輯結構有兩個要素：數(shù)據(jù)元素的集合D；反映D中各數(shù)據(jù)元素之間的前后件關系R。數(shù)據(jù)的邏輯結構數(shù)據(jù)結構可以表示成B＝〔D，R〕其中B表示數(shù)據(jù)結構。為了反映D中各數(shù)據(jù)元素之間的前后件關系，一般用二元組來表示。設a與b是D中的兩個數(shù)據(jù)，那么二元組〔a，b〕表示a是b的前件，b是a的后件。數(shù)據(jù)的邏輯結構例如B＝〔D，R〕D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}家庭成員數(shù)據(jù)結構B＝〔D，R〕D＝{父親，兒子，女兒}R＝{(父親，兒子〕，(父親，女兒〕}數(shù)據(jù)的存儲結構〔數(shù)據(jù)的物理結構〕數(shù)據(jù)的邏輯結構在計算機存儲空間中的存放形式。各數(shù)據(jù)元素在計算機存儲空間中的位置關系與它們的邏輯關系不一定是相同的，而且一般也不可能相同。常用的存儲結構有：順序、鏈接、索引等存儲結構。采用不同的存儲結構，其數(shù)據(jù)處理的效率是不同的。數(shù)據(jù)結構的圖形表示數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示〔數(shù)據(jù)結點，結點〕用一條有向線段從前件結點指向后件結點。如:一年四季數(shù)據(jù)結構的圖形表示

家庭成員間輩份關系數(shù)據(jù)結的圖形表示用圖形表示數(shù)據(jù)結構B＝〔D，R〕D＝{di|1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}對數(shù)據(jù)結構的運算根本運算：插入和刪除其他運算：查找、分類、合并、分解、復制和修改等。數(shù)據(jù)結構的處理過程中，不僅結點的個數(shù)在動態(tài)地變化，而且各數(shù)據(jù)元素之間的關系也有可能在動態(tài)地變化。線性數(shù)據(jù)結構與非線性數(shù)據(jù)結構線性結構：〔1〕有且只有一個根結點；〔2〕每一個結點最多有一個前件，也最多有一個后件。線性結構又稱線性表。如果一個數(shù)據(jù)結構不是線性結構，那么稱之為非線性結構不是線性結構的數(shù)據(jù)結構特例

提示:在一個線性結構中插入或刪除任何一個結點后還應是線性結構空數(shù)據(jù)結構

1.3線性表及其順序存儲結構什么是線性表線性表的順序存儲結構線性表在順序存儲下的插入運算線性表在順序存儲下的刪除運算什么是線性表n維向量(x1，x2，…，xn)是一個長度為n的線性表英文小寫字母表(a，b，c，…，z)是一個長度為26的線性表一年中的四個季節(jié)(春，夏，秋，冬)是一個長度為4的線性表矩陣是一個比較復雜的線性表學生情況登記表是一個復雜的線性表什么是線性表(定義〕線性表是由n(n≥0)個數(shù)據(jù)元素a1，a2，…，an組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。即線性表或是一個空表，或可以表示為(a1，a2，…，ai，…，an)其中ai(i＝1，2，…，n)是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個結點。非空線性表結構特征(1)有且只有一個根結點a1，它無前件；(2)有且只有一個終端結點an，它無后件；(3)除根結點與終端結點外，其它所有結點有且只有一個前件，也有且只有一個后件。線性表中結點的個數(shù)n稱為線性表的長度。當n＝0時，稱為空表。線性表的順序存儲結構線性表的順序存儲結構根本特點：(1)線性表中所有元素所占的存儲空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。線性表中第i個元素ai在計算機存儲空間中的存儲地址為ADR(ai)＝ADR(a1)＋(i－1)k長度為n的線性表(a1，a2，…，ai，…，an)

順序存儲結構整型一維數(shù)組存放長度為8的線性表

(29,18,56,63,35,24,31,47)順序存儲結構下線性表的運算：插入刪除查找排序分解合并復制逆轉原那么：運算后仍保持線性表的特性線性表在順序存儲下的插入運算線性表在順序存儲下的刪除運算1.4棧和隊列棧及其根本運算隊列及其根本運算棧及其根本運算什么是棧棧的順序存儲及其運算棧(stack)是限定在一端進行插入與刪除的線性表。允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧是按照“先進后出”(FILO—FirstInLastOut)或“后進先出”(LIFO—LastInFirstOut)的原那么組織數(shù)據(jù)的，因此，棧也被稱為“先進后出”表或“后進先出”表。棧具有記憶作用。用指針top來指示棧頂?shù)奈恢茫弥羔榖ottom指向棧底。往棧中插入一個元素稱為入棧運算，從棧中刪除一個元素(即刪除棧頂元素)稱為退棧運算。如：主程序與子程序之間的調用關系什么是棧棧的順序存儲及其運算top＝0表示棧空；top＝m表示棧滿(1)入棧運算〔上溢〕(2)退棧運算〔下溢〕(3)讀棧頂元素〔不刪除棧頂元素〕棧的順序存儲及其運算隊列及其根本運算什么是隊列循環(huán)隊列隊列(equeue)是指允許在一端進行插入、而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，用尾指針(rear)指向隊尾元素。允許刪除的一端稱為排頭(也稱隊頭)，用排頭指針(front)指向排頭元素的前一個位置。隊列又稱為“先進先出”(FIFO—FirstInFirstOut)或“后進后出”(LILO—LastInLastOut)的線性表，表達了“先來先效勞”的原那么。往隊列的隊尾插入一個元素稱為入隊運算，從隊列的排頭刪除一個元素稱為退隊運算。什么是隊列隊列根本運算循環(huán)隊列及其運算循環(huán)隊列及其運算循環(huán)隊列的初始狀態(tài)為空，即rear=front=m入隊運算：隊尾指針進1，當隊尾指針rear=m+1時，那么置rear=1。退隊運算：排頭指針進1，當排頭指針front=m+1時，那么置front=1隊列空的條件為s＝0〔下溢〕隊列滿的條件為(s＝1)且front＝rear〔上溢〕1.5線性鏈表什么是線性表線性鏈表的根本運算循環(huán)鏈表順序存儲線性表的缺點：插入上溢共享1.線性鏈表線性表的鏈式存儲結構稱為線性鏈表。線性鏈表的根本概念頭結點：指向線性表中第一個結點的指針HEAD稱為頭指針，當HEAD=NULL(或0〕時稱為空表。線性單鏈表只能順指針向鏈尾方向進行掃描。雙向鏈表帶鏈的棧帶鏈的隊列線性鏈表的插入在鏈式存儲結構下的線性表中插入一個新元素。線性鏈表的根本運算(1)從可利用棧取得一個結點，設該結點號為p。并置結點p的數(shù)據(jù)域為插入的元素值b，即V(p)＝b。(2)在線性鏈表中尋找包含元素x的前一個結點q。(3)將結點p插入到結點q之后：①使結點p指向包含元素x的結點，即NEXT(p)＝NEXT(q)②使結點q的指針域內容改為指向結點p，即NEXT(q)＝p線性鏈表的刪除鏈式存儲結構下的線性表中刪除包含指定元素的結點。(1)尋找包含元素x的前一個結點q。那么包含元素x的結點序號p＝NEXT(q)。(2)將結點q后的結點p刪除，即NEXT(q)＝NEXT(p)。(3)將包含元素x的結點p送回可利用棧。(1)在循環(huán)鏈表中，只要指出表中任何一個結點的位置，就可以從它出發(fā)訪問到表中其他所有的結點。(2)空表與非空表的運算統(tǒng)一。循環(huán)鏈表循環(huán)鏈表的優(yōu)勢：通過任何一個結點都可以訪問到其他任意結點增加了表頭結點，使得空表與非空表的運算統(tǒng)一。樹與二叉樹樹的根本概念二叉樹及其根本性質二叉樹的存儲結構二叉樹的遍歷樹是由n(n0)個結點組成的有限集合。如果n=0，稱為空樹；如果n>0，那么:有一個特定的稱之為根的結點，它只有后繼，但沒有前驅；除根以外的其它結點劃分為m(m0)個互不相交的有限集合T0,T1,…,Tm-1，每個集合本身又是一棵樹，并且稱之為根的子樹。每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個后繼。什么是樹？1〕度〔次數(shù)、級〕〔1〕結點的度：一個結點所擁有的子樹的個數(shù)〔2〕樹的度：樹內各結點的度的最大值2〕描述上下及左右的關系孩子結點：一個結點的子樹的根雙親結點：結點的直接前驅〔前件〕兄弟結點：同一個雙親的孩子之間互稱兄弟祖先：結點的祖先是從根到該結點所經(jīng)分支上的所有結點子孫：結點的后代3〕層次〔1〕結點的層次〔2〕樹的深度〔高度〕樹的根本術語結點(node)結點的度(degree)分支(branch)結點葉(leaf)結點孩子(child)結點雙親(parent)結點兄弟(sibling)結點祖先(ancestor)結點子孫(descendant)結點結點所處層次(level)樹的深度(depth)樹的度(degree)(1)表達式中的每一個運算符在樹中對應一個結點，稱為運算符結點。(2)運算符的每一個運算對象在樹中為該運算符結點的子樹〔在樹中的順序為從左到右〕。(3)運算對象中的單變量均為葉子結點。表達式樹a*(b＋c/d)＋e*h－g*f(s，t，x＋y)a*(b＋c/d)＋e*h－g*f(s，t，x＋y)注：樹在計算機中通常用多重鏈表表示。

(1)非空二叉樹只有一個根結點；(2)每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。什么是二叉樹性質1在二叉樹的第k層上，最多有2k－1(k≥1)個結點。性質2深度為m的二叉樹最多有2m－1個結點。性質3在任意一棵二叉樹中，度為0的結點〔即葉子結點〕總是比度為2的結點多一個。性質4具有n個結點的二叉樹，其深度至少為[log2n]＋1其中[log2n]表示取log2n的整數(shù)局部。二叉樹的根本性質滿二叉樹完全二叉樹假設設二叉樹的深度為h，那么共有h層。除第h層外，其它各層(0h-1)的結點數(shù)都到達最大個數(shù)，第h層從右向左連續(xù)缺假設干結點，這就是完全二叉樹。性質5具有n個結點的完全二叉樹的深度為[log2n]＋1。性質6設完全二叉樹共有n個結點。如果從根結點開始，按層序〔每一層從左到右〕用自然數(shù)1，2，…，n給結點進行編號，那么對于編號為k(k＝1，2，…，n)的結點有以下結論：(1)假設k＝1，那么該結點為根結點，它沒有父結點；假設k＞1，那么該結點的父結點編號為INT(k/2)。(2)假設2k≤n，那么編號為k的結點的左子結點編號為2k；否那么該結點無左子結點〔顯然也沒有右子結點〕。(3)假設2k＋1≤n，那么編號為k的結點的右子結點編號為2k＋1；否那么該結點無右子結點。二叉鏈表

二叉樹的存儲結構〔鏈表存儲和順序存儲〕1.前序遍歷(DLR)假設二叉樹為空，那么結束返回。否那么：(1)訪問根結點；(2)前序遍歷左子樹；(3)前序遍歷右子樹。2.中序遍歷(LDR)假設二叉樹為空，那么結束返回。否那么：(1)中序遍歷左子樹；(2)訪問根結點；(3)中序遍歷左子樹。3.后序遍歷(LRD)假設二叉樹為空，那么結束返回。否那么：(1)后序遍歷左子樹；(2)后序遍歷左子樹；(3)訪問根結點。二叉樹的遍歷二叉樹的遍歷例題〔1〕二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是A〕acbedB〕decabC〕deabcD〕cedba

〔2〕一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，那么該二叉樹的后序遍歷為A〕GEDHFBCAB〕DGEBHFCAC〕ABCDEFGHD〕ACBFEDHG1.7查找技術順序查找二分法查找(1)如果線性表為無序表〔即表中元素的排列是無序的〕，那么不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。(2)即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。(3)最壞情況時間復雜度為n。順序查找設有序線性表的長度為n，被查元素為x。將x與線性表的中間項進行比較：假設中間項的值等于x，那么說明查到，查找結束；假設x小于中間項的值，那么在線性表的前半局部〔即中間項以前的局部〕以相同的方法進行查找；假設x大于中間項的值，那么在線性表的后半局部〔即中間項以后的局部〕以相同的方法進行查找。這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。在最壞情況下，對分查找只需比較log2n次，而順序查找需比較n次。二分法查找1.8排序技術交換類排序插入類排序選擇類排序首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。假設相鄰兩個元素中，前面的元素大于后面的元素，那么將它們互換，稱之為消去了一個逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的大者往后移動，最后就將線性表中的最大者換到了表的最后。然后從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小。假設相鄰兩個元素中，后面的元素小于前面的元素，那么將它們互換，這樣就又消去了一個逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的小者往前移動，最后就將剩下線性表中的最小者換到了表的最前。對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時的線性表已經(jīng)變?yōu)橛行颉Ｗ顗那闆r下的時間復雜度為n(n-1)/2.冒泡排序快速排序首先，在表的第一個、中間一個與最后一個元素中選取中項，設為P(k)，并將P(k)賦給T，再將表中的第一個元素移到P(k)的位置上。然后設置兩個指針i和j分別指向表的起始與最后的位置。反復作以下兩步：(1)將j逐漸減小，并逐次比較P(j)與T，直到發(fā)現(xiàn)一個P(j)＜T為止，將P(j)移到P(i)的位置上。(2)將i逐漸增大，并逐次比較P(i)與T，直到發(fā)現(xiàn)一個P(i)＞T為止，將P(i)移到P(j)的位置上。上述兩個操作交替進行，直到指針i與j指向同一個位置〔即i＝j〕為止，此時將T移到P(i)的位置上。簡單插入排序51731694286

↑j＝215731694286

↑j＝315731694286

↑j＝413571694286

↑j＝511357694286

↑j＝6

11356794286

↑j＝711356794286

↑j＝81