數據結構實用課件緒論

第1章緒論?1.1數據結構?1.2基本概念和術語?1.3抽象數據類型?1.4算法和算法分析第1章緒論?1.1數據結構1引論對于一個課題，在計算機領域，一般遵循下面的解決原則：需求分析總體設計模塊分割建立數學模型解數學模型的算法程序編制調試結果數據結構涉及到：數學模型的建立和對該模型具體實現的對應的算法。數據結構的地位：數學、硬件、軟件之間。核心專業(yè)基礎課.引論對于一個課題，在計算機領域，一般遵循下面的解決原則：21.1數據結構的基本概念和術語1.基本術語（1）數據：描述客觀事物的數字、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。（數字、字符、聲音、圖形、圖像等等）（2）數據元素：數據的基本單位，在計算機程序中常常作為一個整體進行考慮和處理，如紀錄/結構。（3）數據項：數據的不可分割的最小單位，如結構中的域。（4）數據對象：性質相同的數據元素的集合，是數據的一個子集。1.1數據結構的基本概念和術語1.基本術語32.數據結構（1）定義：是相互之間存在一種或多種特定關系的數據元素的集合。數據之間不是相互獨立的，他們之間有某種特定的關系，這種數據元素之間的關系，稱為“結構”結構=關系+實體另一種定義：按照邏輯關系組織起來的一批數據,按一定的存儲方法把它存儲在計算機中,并在這些數據上定義了一個運算的集合。形式定義：二元組(D,S)其中D是數據元素的有限集，S是D上關系的有限集2.數據結構4（2）四種基本結構（邏輯結構）p5集合：元素僅屬于同一個集體，沒有其他關系。線性結構：存在一對一關系，序列相鄰，次序關系。樹型結構：存在一對多關系，層次關系。圖狀結構（網狀結構）：存在多對多關系，任意性存儲器模型：一個存儲器M是一系列固定大小的存儲單元，每個單元U有一個唯一的地址A(U)，該地址被連續(xù)地編碼。每個單元U有一個唯一的后繼單元U’=succ(U)物理結構就是邏輯結構到存儲器的一個映射。四種存儲結構：順序存儲、鏈接存儲、索引存儲、散列存儲（2）四種基本結構（邏輯結構）p55（3）實例：P1-P3例1-1——例1-3

表：計算機系人事表工號姓名性別職務教研室工作時間發(fā)表論文01系主任軟件1981.1A,B02教研室主任軟件1985.1B,C,E,F03教師軟件1990.8C,D04教師應用1987.8A,G05教師應用1975.9E,I06教師應用1992.2F,J07教師軟件1983.8D,L08教研室主任應用1986.7G,H09教師應用1995.8H,I,J,K10教師軟件1989.2L,K（3）實例：P1-P3例1-1——例1-3

表：63.數據結構的劃分（1）按數據結構的性質劃分數據的邏輯結構——數據元素之間的邏輯關系（設計算法——數學模型）數據的物理結構——數據結構在計算機中的映像（存儲結構，算法的實現）3.數據結構的劃分（1）按數據結構的性質劃分73.數據結構的劃分（2）按數據結構在計算機內的存儲方式來劃分順序存儲結構——借助元素在存儲器的相對位置來表示數據元素之間的邏輯關系。鏈式存儲結構——借助指示元素存儲地址的指針表示數據元素之間的邏輯關系。3.數據結構的劃分（2）按數據結構在計算機內的存儲方式來劃83.數據結構的劃分（2）按數據結構在計算機內的存儲方式來劃分索引存儲方法：在存儲結點的同時，還建立附加的索引表，索引表中的每一項稱為索引項，形式為：關鍵字，地址。散列存儲方法：根據結點的關鍵字直接計算出該結點的存儲地址。說明：四種存儲方法可結合起來對數據結構進行存儲映像。3.數據結構的劃分（2）按數據結構在計算機內的存儲方式來劃93.數據結構的劃分（3）按數據結構的操作來劃分靜態(tài)結構——經過操作后，數據的結構特征保持不變（如數組）。半靜態(tài)結構——經過操作后，數據的結構特性只允許很小變遷（如棧、隊列）。動態(tài)結構——經過操作后，數據的結構特性變化比較靈活，可隨機地重新組織結構（如指針）。3.數據結構的劃分（3）按數據結構的操作來劃分101.2抽象數據類型——ADT定義：是指基于一個邏輯類型的數據模型以及定義在該模型上的一組操作。每一個操作由它的輸入和輸出定義。抽象的與具體的相對應示例：inta,b;則a和b可以進行+、-、*、/的運算2和6則是具體的int數據1.2抽象數據類型——ADT定義：是指基于一個邏輯類型的111.3算法和算法分析1.算法p13定義：指一系列確定的而且是在有限步驟內能完成的操作。1.3算法和算法分析1.算法p1312算法的重要特性P13(1)有窮性：能執(zhí)行結束(2)確定性：對于相同的輸入執(zhí)行相同的路徑(3)0至多個輸入(4)1至多個輸出(5)有效性(可行性)（用于描述算法的操作都是足夠基本的）問題：程序是不是算法？如操作系統，只要系統不遭破壞，它就永遠不會停止，即使沒有作業(yè)要處理，仍處于一個等待循環(huán)中，等待新作業(yè)的進入。因此操作系統程序不是一個算法。算法的重要特性P13(1)有窮性：能執(zhí)行結束132.算法與數據結構的關系計算機科學家沃斯（N.Wirth）提出的:“算法+數據結構=程序”揭示了程序設計的本質：對實際問題選擇一種好的數據結構，加上設計一個好的算法，而好的算法很大程度上取決于描述實際問題的數據結構。算法與數據結構是互相依賴、互相聯系的。一個算法總是建立在一定數據結構上的；反之，算法不確定，就無法決定如何構造數據?！猵6圖1.6上面2行2.算法與數據結構的關系計算機科學家沃斯（N.Wirth）14算法與數據結構關系舉例例1：編寫程序查詢某城市某人的電話號碼建立一張登記表，存放2個數據項：姓名+Tel好的算法取決于這張表的結構及存儲方式：將表中結點按照姓名順序地存儲在計算機中，依次查找，可能遍歷整個表都找不到。建立一張姓氏索引表：姓+表中的起始地址則不需查找其他姓氏，查找效率得到提高。算法與數據結構關系舉例例1：編寫程序查詢某城市某人的電話號碼15算法與數據結構關系舉例例2:設計一個考試日程安排表，使在盡可能短的時間內安排完考試，要求同一個學生選修的幾門課程不能安排在同一個時間內。姓名選修1選修2選修3ABECDCEFDFABF算法與數據結構關系舉例例2:姓名選修1選修2選修3ABE16算法與數據結構關系舉例解決該問題，首先選擇一個合適的數據結構。用無向圖表示，圖中的頂點表示課程，不能同時考試的課程之間連上一條邊。則該問題就抽象成對該無向圖進行“著色”操作，即用盡可能少的顏色去給圖中每個頂點著色，使得任意兩個相鄰的頂點著不同的顏色。同一種顏色表示一個考試時間。答案：1：A,C2:B,D3:E4:F解決問題的關鍵步驟是先選取合適的數據結構表示問題，才能寫出有效的算法。算法與數據結構關系舉例解決該問題，首先選擇一個合適的數據結構173.算法設計的要求p13~p14（1）正確性四層含義p14a,b,c,d（2）可讀性首先是給人讀，然后才是機器執(zhí)行（3）健壯性容錯性（4）效率與低存儲量需求3.算法設計的要求p13~p14（1）正確性18算法的效率定義：一個算法如果能在所要求的資源限制內將問題解決好，則稱這個算法是有效率的。例如，一個資源限制是：可用來存儲數據的全部空間——可能是分離的內存空間限制和磁盤空間限制以及允許執(zhí)行每一個子任務所需要的時間。算法的效率定義：一個算法如果能在所要求的資源限制內將問題解決194.算法的分析——算法性能的評價評價標準：1）算法所需的計算時間2）算法所需的存儲空間3）算法的簡單性度量算法執(zhí)行時間的兩種方法p141）事后統計法此方法有兩個缺陷p142）事前分析估算法此方法取決于多個因素：a,b,c,d,ep144.算法的分析——算法性能的評價評價標準：205.時間復雜度（1）引例

（a）{++x;s=0；}++x的頻度為1（b）for(i=1;i<=n;++i){++x;s+=x;}++x的頻度為n（c）for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}++x的頻度為n2

5.時間復雜度（1）引例215.時間復雜度（2）定義：

一般情況下，算法中基本操作重復執(zhí)行的時間是問題規(guī)模n的某個函數f(n)，算法的時間量度記作T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱時間復雜度。語句的頻度：該語句重復執(zhí)行的次數。頻度統計法

5.時間復雜度（2）定義：22表：時間復雜度和算法運行時間的關系T(n)nO(logn)O(n)O(nlogn)O(n2)O(n3)O(n5)O(2n)O(n!))204.3us20us86.4us400us8ms3.2s1.05s771世紀405.340213160064ms1.7min12.7天2.59*1032世紀605.9603543600216ms13min366世紀2.64*1066世紀表：時間復雜度和算法運行時間的關系T(n)O(logn)O(23結論（1）當f(n)為對數函數、冪函數、或它們的乘積時，算法的運行時間是可以接受的，稱這些算法是有效算法；當f(n)為指數函數或階乘函數時，算法的運行時間是不可接受的，稱這些算法是無效的算法。（2）隨著n值的增大，增長速度各不相同，n足夠大時，存在下列關系：對數函數<冪函數<指數函數結論（1）當f(n)為對數函數、冪函數、或它們的乘積時，算法24常見函數的增長率

O(1)常量階，與n無關O(logn)logn階O(n)n階O(nlogn)nlogn階O(n2)平方階O(n3)立方階O(2n)指數階增長率由慢到快圖示見p16圖1-7盡量少用指數階的算法說明：教材p17第2行除特別指明外，均指最壞情況下的時間復雜度常見函數的增長率O(1)常256.空間復雜度（1）存儲算法本身所占用的空間（2）算法的輸入/輸出數據占用的空間（3）算法在運行過程中臨時占用的輔助空間原地工作：若輔助空間相對于輸入數據量是常數，則稱此算法是原地工作。若所占空間量依賴于特定的輸入，按最壞情況來分析。6.空間復雜度（1）存儲算法本身所占用的空間26第1章緒論?1.1數據結構?1.2基本概念和術語?1.3抽象數據類型?1.4算法和算法分析第1章緒論?1.1數據結構27引論對于一個課題，在計算機領域，一般遵循下面的解決原則：需求分析總體設計模塊分割建立數學模型解數學模型的算法程序編制調試結果數據結構涉及到：數學模型的建立和對該模型具體實現的對應的算法。數據結構的地位：數學、硬件、軟件之間。核心專業(yè)基礎課.引論對于一個課題，在計算機領域，一般遵循下面的解決原則：281.1數據結構的基本概念和術語1.基本術語（1）數據：描述客觀事物的數字、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。（數字、字符、聲音、圖形、圖像等等）（2）數據元素：數據的基本單位，在計算機程序中常常作為一個整體進行考慮和處理，如紀錄/結構。（3）數據項：數據的不可分割的最小單位，如結構中的域。（4）數據對象：性質相同的數據元素的集合，是數據的一個子集。1.1數據結構的基本概念和術語1.基本術語292.數據結構（1）定義：是相互之間存在一種或多種特定關系的數據元素的集合。數據之間不是相互獨立的，他們之間有某種特定的關系，這種數據元素之間的關系，稱為“結構”結構=關系+實體另一種定義：按照邏輯關系組織起來的一批數據,按一定的存儲方法把它存儲在計算機中,并在這些數據上定義了一個運算的集合。形式定義：二元組(D,S)其中D是數據元素的有限集，S是D上關系的有限集2.數據結構30（2）四種基本結構（邏輯結構）p5集合：元素僅屬于同一個集體，沒有其他關系。線性結構：存在一對一關系，序列相鄰，次序關系。樹型結構：存在一對多關系，層次關系。圖狀結構（網狀結構）：存在多對多關系，任意性存儲器模型：一個存儲器M是一系列固定大小的存儲單元，每個單元U有一個唯一的地址A(U)，該地址被連續(xù)地編碼。每個單元U有一個唯一的后繼單元U’=succ(U)物理結構就是邏輯結構到存儲器的一個映射。四種存儲結構：順序存儲、鏈接存儲、索引存儲、散列存儲（2）四種基本結構（邏輯結構）p531（3）實例：P1-P3例1-1——例1-3

表：計算機系人事表工號姓名性別職務教研室工作時間發(fā)表論文01系主任軟件1981.1A,B02教研室主任軟件1985.1B,C,E,F03教師軟件1990.8C,D04教師應用1987.8A,G05教師應用1975.9E,I06教師應用1992.2F,J07教師軟件1983.8D,L08教研室主任應用1986.7G,H09教師應用1995.8H,I,J,K10教師軟件1989.2L,K（3）實例：P1-P3例1-1——例1-3

表：323.數據結構的劃分（1）按數據結構的性質劃分數據的邏輯結構——數據元素之間的邏輯關系（設計算法——數學模型）數據的物理結構——數據結構在計算機中的映像（存儲結構，算法的實現）3.數據結構的劃分（1）按數據結構的性質劃分333.數據結構的劃分（2）按數據結構在計算機內的存儲方式來劃分順序存儲結構——借助元素在存儲器的相對位置來表示數據元素之間的邏輯關系。鏈式存儲結構——借助指示元素存儲地址的指針表示數據元素之間的邏輯關系。3.數據結構的劃分（2）按數據結構在計算機內的存儲方式來劃343.數據結構的劃分（2）按數據結構在計算機內的存儲方式來劃分索引存儲方法：在存儲結點的同時，還建立附加的索引表，索引表中的每一項稱為索引項，形式為：關鍵字，地址。散列存儲方法：根據結點的關鍵字直接計算出該結點的存儲地址。說明：四種存儲方法可結合起來對數據結構進行存儲映像。3.數據結構的劃分（2）按數據結構在計算機內的存儲方式來劃353.數據結構的劃分（3）按數據結構的操作來劃分靜態(tài)結構——經過操作后，數據的結構特征保持不變（如數組）。半靜態(tài)結構——經過操作后，數據的結構特性只允許很小變遷（如棧、隊列）。動態(tài)結構——經過操作后，數據的結構特性變化比較靈活，可隨機地重新組織結構（如指針）。3.數據結構的劃分（3）按數據結構的操作來劃分361.2抽象數據類型——ADT定義：是指基于一個邏輯類型的數據模型以及定義在該模型上的一組操作。每一個操作由它的輸入和輸出定義。抽象的與具體的相對應示例：inta,b;則a和b可以進行+、-、*、/的運算2和6則是具體的int數據1.2抽象數據類型——ADT定義：是指基于一個邏輯類型的371.3算法和算法分析1.算法p13定義：指一系列確定的而且是在有限步驟內能完成的操作。1.3算法和算法分析1.算法p1338算法的重要特性P13(1)有窮性：能執(zhí)行結束(2)確定性：對于相同的輸入執(zhí)行相同的路徑(3)0至多個輸入(4)1至多個輸出(5)有效性(可行性)（用于描述算法的操作都是足夠基本的）問題：程序是不是算法？如操作系統，只要系統不遭破壞，它就永遠不會停止，即使沒有作業(yè)要處理，仍處于一個等待循環(huán)中，等待新作業(yè)的進入。因此操作系統程序不是一個算法。算法的重要特性P13(1)有窮性：能執(zhí)行結束392.算法與數據結構的關系計算機科學家沃斯（N.Wirth）提出的:“算法+數據結構=程序”揭示了程序設計的本質：對實際問題選擇一種好的數據結構，加上設計一個好的算法，而好的算法很大程度上取決于描述實際問題的數據結構。算法與數據結構是互相依賴、互相聯系的。一個算法總是建立在一定數據結構上的；反之，算法不確定，就無法決定如何構造數據?！猵6圖1.6上面2行2.算法與數據結構的關系計算機科學家沃斯（N.Wirth）40算法與數據結構關系舉例例1：編寫程序查詢某城市某人的電話號碼建立一張登記表，存放2個數據項：姓名+Tel好的算法取決于這張表的結構及存儲方式：將表中結點按照姓名順序地存儲在計算機中，依次查找，可能遍歷整個表都找不到。建立一張姓氏索引表：姓+表中的起始地址則不需查找其他姓氏，查找效率得到提高。算法與數據結構關系舉例例1：編寫程序查詢某城市某人的電話號碼41算法與數據結構關系舉例例2:設計一個考試日程安排表，使在盡可能短的時間內安排完考試，要求同一個學生選修的幾門課程不能安排在同一個時間內。姓名選修1選修2選修3ABECDCEFDFABF算法與數據結構關系舉例例2:姓名選修1選修2選修3ABE42算法與數據結構關系舉例解決該問題，首先選擇一個合適的數據結構。用無向圖表示，圖中的頂點表示課程，不能同時考試的課程之間連上一條邊。則該問題就抽象成對該無向圖進行“著色”操作，即用盡可能少的顏色去給圖中每個頂點著色，使得任意兩個相鄰的頂點著不同的顏色。同一種顏色表示一個考試時間。答案：1：A,C2:B,D3:E4:F解決問題的關鍵步驟是先選取合適的數據結構表示問題，才能寫出有效的算法。算法與數據結構關系舉例解決該問題，首先選擇一個合適的數據結構433.算法設計的要求p13~p14（1）正確性四層含義p14a,b,c,d（2）可讀性首先是給人讀，然后才是機器執(zhí)行（3）健壯性容錯性（4）效率與低存儲量需求3.算法設計的要求p13~p14（1）正確性44算法的效率定義：一個算法如果能在所要求的資源限制內將問題解決好，則稱這個算法是有效率的。例如，一個資源限制是：可用來存儲數據的全部空間——可能是分離的內存空間限制和磁盤空間限制以及允許執(zhí)行每一個子任務所需要的時間。算法的效率定義：一個算法如果能在所要求的資源限制內將問題解決454.算法的分析——算法性能的評價評價標準：1）算法所需的計算時間2）算法所需的存儲空間3）算法的簡單性度量算法執(zhí)行時間的兩種方法p141）事后統計法此方法有兩個缺陷p142）事前分析估算法此方法取決于多個因素：a,b,c,d,ep144.算法的分析——算法性能的評價評價標準：465.時間復雜度（1）引例

（a）{++x;s=0；}++x的頻度為1（b）for(i=1;i<=n;++i){++x;s+=x;}++x的頻度為n（c）for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}++x的頻度為n2

5.時間復雜度（1）引例475.時間復雜度（2）定義：

一般情況下，算法中基本操作重復執(zhí)行的時間是