1、1算法及數據結構算法及數據結構程序設計基礎程序設計基礎軟件軟件工程基礎工程基礎數據庫設計基礎數據庫設計基礎2345 6 7 8algorithm1 1、算法的基本概念、算法的基本概念( (漢諾塔的例子) ) 算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。算法具有可行性可行性、確定性確定性、有窮性有窮性、輸入輸入和輸出輸出（擁有足夠的情報）等個重要特性。漢 諾 塔l 1-B1-Bl 2-C 2-Cl 1-C 1-Cl 3-B 3-Bl 1-A 1-Al

2、2-B 2-Bl 1-B 1-BABC123算法：算法：算法：算法：對特定問題求解步驟的一種描述。對特定問題求解步驟的一種描述。算法的描述方法：算法的描述方法：自然語言、專用工具或某種計算機語言。自然語言、專用工具或某種計算機語言。返回102 2、算法的基本要素、算法的基本要素(1) 對數據對象的運算和操作： 算術運算、邏輯運算、關系運算、數據傳輸 算法中各操作之間的執行順序； 描述算法的工具通常有傳統流程圖、N-S結構化流程 圖、算法描述語言等； 一個算法一般可以用順序、選擇、循環三種基本結構 組合而成。(2) 算法的控制結構： 113 3、算法設計的基本方法、算法設計的基本方法及例子 列舉

3、法（列出所有可能，再逐一檢驗，得到符合條件的結果）百錢買百雞 歸納法（通過特殊情況，經過分析，最后找出一般關系） 遞推（從已知的初始條件出發，逐步推算，得到結果）猴子分食桃子 遞歸（將問題逐層分解，最后歸結為一些最簡單的問題）求年齡問題 減半遞推（重復將問題的規模減半，而問題性質不變）二分法求方程實根 回溯法（以最優方式向前試探，如果失敗，則后退再選）八皇后問題12(1)(1)時間復雜度時間復雜度v 依據算法編制的程序在計算機上運行時所消耗的時間 來度量。通常有事后統計法和事前分析估算法。v 一個算法是由控制結構（順序、分支和循環）和原操 作構成的，算法時間取決于兩者的綜合效果。v 算法中基本

4、操作重復執行次數n和算法執行時間同步 增長，稱作算法的時間復雜度。13(2)(2)空間復雜度空間復雜度v 一般是指執行這個算法所需要的內存空間。v 一個算法所占用的存儲空間包括算法程序所占的空間、 輸入的初始數據所占的存儲空間以及某種數據結構所需 要的附加存儲空間。v 一個上機執行的程序除了需要存儲空間來寄存本身所用 指令、常數、變量和輸入數據外，也需要一些對數據進 行操作的工作單元和存儲一些為實現計算所需信息的輔 助空間。143 3、例題講解、例題講解v 算法的時間復雜度是指算法的時間復雜度是指( ( C C ) ) A A、執行算法程序所需要的時間執行算法程序所需要的時間 B B、算法程序

5、的長度算法程序的長度 C C、算法執行過程中所需要的基本運算次數算法執行過程中所需要的基本運算次數 D D、算法程序中的指令條數算法程序中的指令條數v 算法的基本特征是可行性、確定性、算法的基本特征是可行性、確定性、 【1 1】和擁有足夠和擁有足夠 的情報。的情報。 【答案】【答案】: :有窮性有窮性v 算法的空間復雜度是指算法的空間復雜度是指( ( D D ) ) A) A) 算法程序的長度算法程序的長度 B) B) 算法程序中的指令條數算法程序中的指令條數 C) C) 算法程序所占的存儲空間算法程序所占的存儲空間 D) D) 執行過程中所需要的存儲空間執行過程中所需要的存儲空間 15v 在

6、計算機中，算法是指（ B B ） A) 加工方法 B) B) 解題方案的準確而完整的描述解題方案的準確而完整的描述 C) 排序方法 D) 查詢方法v 算法分析的目的是( D D ) A) 找出數據結構的合理性 B) 找出算法中輸入和輸出之間的關系 C) 分析算法的易懂性和可靠性 D) D) 分析算法的效率以求改進分析算法的效率以求改進v 算法的工作量大小和實現算法所需的存儲單元多少分別稱 為算法的 【 1 1 】 ?！敬鸢浮俊敬鸢浮? :時間復雜度和空間復雜度時間復雜度和空間復雜度 16Data Structure1 1、數據結構研究的主要內容、數據結構研究的主要內容v 當今計算機應用的特點：

7、 1、所處理的數據量大且具有一定的關系； 2、對其操作不再是單純的數值計算，而更多地是需 要對其進行組織、管理和檢索。 對數據的討論不單單是數據本身，還要包括數據與對數據的討論不單單是數據本身，還要包括數據與數據之間的關系。數據之間的關系。下面各例表示不同的數據采用不同的數據結構來組織。下面各例表示不同的數據采用不同的數據結構來組織。17 學 生 基 本 情 況 學 號 姓 名 性 別 出 生 年 月 . 99070101 李 軍 男 80 12 . 99070102 王 顏 霞 女 81 2 . 99070103 孫 濤 男 80 9 . 99070104 單 曉 宏 男 81 3 . .

8、. . . . 特點： 每個學生的信息占據一行，所有學生的信息按學號順序依次排列構成一張表格； 表中每個學生的信息依據學號的大小存在著一種前后關系，這就是我們所說的線性結構； 對它的操作通常是插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。v 應用舉例1學籍檔案管理假設一個學籍檔案管理系統應包含如下表所示的學生信息。18v 應用舉例2家庭血緣關系圖 表示家庭成員的輩分關系，使用下圖1-1所示的形式描述。3 1 21 3 21 2 31 23 2 12 3 12 1 32 11家庭血緣關系圖特點： 在求解過程中，所處理的數據之間具有層次關系，這是我們 所

9、說的樹形結構； 對它的操作有：建立樹形結構，輸出最結點內容等等。v 應用舉例3制定教學計劃 在制定教學計劃時，需要考慮各門課程的開設順序。有些課程需要先導課程，有些課程則不需要，而有些課程又是其他課程的先導課程。比如，計算機專業課程的開設情況如下表所示： 計算機專業學生的必修課程 課課程程編編號號 課課程程名名稱稱 需需要要的的先先導導 課課程程編編號號 C 1 程序設計基礎 無 C 2 離散數學 C 1 C 3 數據結構 C 1 ，C 2 C 4 匯編語言 C 1 C 5 算法分析與設計 C 3 ，C 4 C 6 計算機組成原理 C 1 1 C 7 編譯原理 C 5 ，C 3 C 8 操作系

10、統 C 3 ，C 6 C 9 高等數學 無 C 1 0 線性代數 C 9 C 1 1 普通物理 C 9 C 1 2 數值分析 C 9 ，C 1 0 ，C 1 19這種數據可以用下面的圖來表示：v 課程先后關系的圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計算機專業必修課程開設先后關系20 1 1、數據的、數據的邏輯結構邏輯結構 2 2、數據的、數據的存儲結構存儲結構 3 3、數據的、數據的運算運算：檢索、排序、插入、刪除、修改等。：檢索、排序、插入、刪除、修改等。 A A線性結構線性結構B B非線性結構非線性結構A A順序存儲順序存儲 B B鏈式存儲鏈式存儲

11、線性表線性表棧棧隊隊樹形結構樹形結構圖形結構圖形結構數據結構的三個方面數據結構的三個方面(亦稱物理結構亦稱物理結構)數據結構的主要研究問題：212 2、基本概念和術語、基本概念和術語 數據結構是一門研究組織組織、存儲存儲和運算運算的一般方法的學科。例：整數整數(1,2)、實數實數(1.1,1.2)字符串字符串(Beijing)、圖形圖形、聲音聲音。計算機管理圖書問題 ： 在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排。如何將查詢圖書的這些信息存入計算機中既要考慮查詢時間短，又要考慮節省空間。最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如：22數據元素在計算機中

12、的表示 數據結構是一門研究組織組織、存儲存儲和運算運算的一般方法的學科。如何將0,1,2,3,4,5,6,7,8,9這10個數存放在計算機中能最快地達到你所需要的目的？ 目的不同，最佳的存儲方方法就不同。從大到小排列：9,8,7,6,5,4,3,2,1,0輸出偶數：0,2,4,6,8,1,3,5,7,9 對數據結構中的節點進行操作處理對數據結構中的節點進行操作處理（插入、刪除、修改、查找、排序）（插入、刪除、修改、查找、排序）23v 數據元素數據元素( (Data Element)Data Element) 數據元素是數據的基本單位，即數據集合中的個體。 有時一個數據元素可由若干數據項數據項(

13、Data ItemData Item)組成。數據項是數據的最小單位。數據元素亦稱節點節點或記錄記錄。數據結構可描述為數據結構可描述為 Group=Group=（D D，R R）有限個數據元素的集合有限個數據元素的集合有限個節點間關系的集合有限個節點間關系的集合2425數據結構可描述為數據結構可描述為 Group=（D，R）l 例例1：一年四季的數據結構可表示成：一年四季的數據結構可表示成B=（D，R） D=春，夏，秋，冬春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）l 例例2：家庭成員數據結構可表示成：家庭成員數據結構可表示成B=（D，R）D=父親，兒

14、子，女兒父親，兒子，女兒 R=（父親，兒子），（父親，女兒）（父親，兒子），（父親，女兒）26數據結構也可用圖形表示數據結構也可用圖形表示l一年四季的數據結構可表示成一年四季的數據結構可表示成l家庭成員數據結構可表示成家庭成員數據結構可表示成冬冬春春夏夏秋秋父親父親兒子兒子女兒女兒（ 概念：結點、前件、后件、根結點、葉子 ）27v 樹形結構全校學生檔案管理的組織方式全校學生檔案管理的組織方式計算機程序管理系統也是典型的計算機程序管理系統也是典型的樹形結構樹形結構。281 14 42 23 3 D=1 , 2 , 3 , 4 D=1 , 2 , 3 , 4R=(1,2),(1,3), R=(1,

15、2),(1,3), (1,4),(2,3), (1,4),(2,3), (3,4),(2,4) (3,4),(2,4) 2 21 13 3 D= 1 , 2 , 3 D= 1 , 2 , 3 R=(1,2),(2,3),(3,2),(1,3) R=(1,2),(2,3),(3,2),(1,3)v 圖形結構圖形結構節點間的連結是任意的節點間的連結是任意的293 3、例題講解、例題講解v 數據處理的最小單位是數據處理的最小單位是( ( C C ) ) A)A)數據數據 B)B)數據元素數據元素 C) C) 數據項數據項 D) D) 數據結構數據結構v 數據結構作為計算機的一門學科，主要研究數據的邏

16、輯結構、數據結構作為計算機的一門學科，主要研究數據的邏輯結構、對各種數據結構進行的運算，以及對各種數據結構進行的運算，以及( ( A A ) ) A) A) 數據的存儲結構數據的存儲結構 B) B) 計算方法計算方法 C) C) 數據映象數據映象 D) D) 邏輯存儲邏輯存儲v 數據結構包括數據的邏輯結構、數據的數據結構包括數據的邏輯結構、數據的 【4 4】 以及對數據的以及對數據的操作運算。操作運算。 【答案【答案】物理結構（或存儲結構）物理結構（或存儲結構）30v 線性結構與非線性結構：線性結構與非線性結構：v 線性結構：有且只有一個根結點；每一個線性結構：有且只有一個根結點；每一個結點最

17、多有一個前件，也最多有一個后件。結點最多有一個前件，也最多有一個后件。 如：一年四季，如：一年四季，2626個英文字母個英文字母v非線性結構：線性以外的數據結構。非線性結構：線性以外的數據結構。 如：反映家庭成員間輩分關系的數據結構如：反映家庭成員間輩分關系的數據結構 31結點間是以線性關系聯結，結點間是以線性關系聯結，如前面提到的：一年四季26個英文字母 線性 有限 序列4、線性表、線性表（Linear List）v 線性表線性表：具有線性結構的有限序列。A AB BC CD DZ Z春春夏夏秋秋冬冬32學生成績表學生成績表線性表線性表33數據元素、結點、記錄數據項線性v 線性表的定義線性表

18、的定義: : 線性表線性表是是n n個元素的有限序列，它們之間的關系可以排成個元素的有限序列，它們之間的關系可以排成一個線性序列：一個線性序列：a1a1，a2a2， ，aiai， ，anan 其中其中n n稱作表的稱作表的長度長度，當，當n=0n=0時，稱作時，稱作空表空表。v 線性表的特點：線性表的特點： 1 1、線性表中所有元素的性質相同。、線性表中所有元素的性質相同。 2 2、除第一個和最后一個數據元素之外，其它數據元素有且、除第一個和最后一個數據元素之外，其它數據元素有且 僅有一個前驅和一個后繼。第一個數據元素無前驅，最僅有一個前驅和一個后繼。第一個數據元素無前驅，最 后一個數據元素無

19、后繼。后一個數據元素無后繼。 3 3、數據元素在表中的位置只取決于它自身的序號。、數據元素在表中的位置只取決于它自身的序號。v 在線性表上常用的運算有：在線性表上常用的運算有： 初始化、求長度、取元素、修改、前插、刪除、檢索、排序初始化、求長度、取元素、修改、前插、刪除、檢索、排序3435v 線性表的線性表的 順序存儲結構 及其及其 插入 與與 刪除 操作操作 特點：特點： 1 1、線性表中數據元素類型一致，只有數據域，存儲空間、線性表中數據元素類型一致，只有數據域，存儲空間 利用率高。利用率高。 2 2、所有元素所占的存儲空間是連續的。、所有元素所占的存儲空間是連續的。 3 3、各數據元素在

20、存儲空間中是按邏輯順序依次存放的、各數據元素在存儲空間中是按邏輯順序依次存放的 （a a）做插入、刪除時需移動大量元素。做插入、刪除時需移動大量元素。 （b b）空間估計不明時，按最大空間分配?？臻g估計不明時，按最大空間分配。 36順順序序存存儲儲存儲地址存儲地址存儲內容存儲內容元素元素n n.元素元素i i.元素元素2 2元素元素1 1L Lo o + + mL Lo o+(i-1)+(i-1)mLo+Lo+（n-1)n-1)mLoc(Loc(元素元素i)=Li)=Lo o+ +（i-1)i-1)m每個元素所占用每個元素所占用的存儲單元個數的存儲單元個數v 線性表的線性表的 順序存儲結構順序

21、存儲結構：首地址首地址起始地址起始地址基地址基地址v插入運算插入運算a ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai ia alengtlength h 插入算法的分析 假設線性表中含有n個數據元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數為：1n1iis2n1)i(n1n1E37X Xa ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai iX X在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數為：分析結論分析結論 順序存儲結構

22、表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數據元素。當線性表的數據元素量較大，并且經常要對其做插入或刪除操作時，這一點需要值得考慮。n1idl21ni)(nn1Ev刪除算法的分析刪除算法的分析38q 線性表的例題講解線性表的例題講解v 順序存儲方法是把邏輯上相鄰的結點存儲在物理位置順序存儲方法是把邏輯上相鄰的結點存儲在物理位置 【1 1】 的存儲單元中。的存儲單元中。 【答案【答案】相鄰相鄰v 長度為長度為n n的順序存儲線性表中，當在任何位置上插入一個元的順序存儲線性表中，當在任何位置上插入一個元 素概率都相等時，插入一個元素所需移動元素的平均個數素概率都相等時，插入一個元素

23、所需移動元素的平均個數 為為【2 2】 。 【答案【答案】 n/2n/2v 線性表線性表L=(a1,a2,a3,L=(a1,a2,a3,aiai，an)an)，下列說法正確的是（下列說法正確的是（D D） A) A) 每個元素都有一個直接前件和直接后件每個元素都有一個直接前件和直接后件 B) B) 線性表中至少要有一個元素線性表中至少要有一個元素 C) C) 表中諸元素的排列順序必須是由小到大或由大到小表中諸元素的排列順序必須是由小到大或由大到小 D) D) 除第一個元素和最后一個元素外，其余每個元素都有一除第一個元素和最后一個元素外，其余每個元素都有一 個且只有一個直接前件和直接后件個且只有

24、一個直接前件和直接后件 3940 數據結構中，與所使用的計算機無關的是數據的數據結構中，與所使用的計算機無關的是數據的( ( C C ) ) A) A) 存儲結構存儲結構B) B) 物理結構物理結構 C) C) 邏輯結構邏輯結構D) D) 物理和存儲結構物理和存儲結構 下列敘述中，錯誤的是（下列敘述中，錯誤的是（ B B ） A) A) 數據的存儲結構與數據處理的效率密切相關數據的存儲結構與數據處理的效率密切相關 B) B) 數據的存儲結構與數據處理的效率無關數據的存儲結構與數據處理的效率無關 C) C) 數據的存儲結構在計算機中所占的空間不一定是連續的數據的存儲結構在計算機中所占的空間不一定

25、是連續的 D) D) 一種數據的邏輯結構可以有多種存儲結構一種數據的邏輯結構可以有多種存儲結構 數據的存儲結構是指（數據的存儲結構是指（ B B ） A A）數據所占的存儲空間數據所占的存儲空間 B B）數據的邏輯結構在計算機中的表示數據的邏輯結構在計算機中的表示 C C）數據在計算機中的順序存儲方式數據在計算機中的順序存儲方式 D D）存儲在外存中的數據存儲在外存中的數據 根據數據結構中各數據元素之間前后件關系的復雜程度，一般根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分成將數據結構分成( ( C C ) ) A) A) 動態結構和靜態結構動態結構和靜態結構 B) B)

26、緊湊結構和非緊湊結構緊湊結構和非緊湊結構 C) C) 線性結構和非線性結構線性結構和非線性結構 D) D) 內部結構和外部結構內部結構和外部結構 數據的邏輯結構有線性結構和數據的邏輯結構有線性結構和 【2 2】兩大類。兩大類。非線性結構非線性結構 當線性表采用順序存儲結構實現存儲時，其主要特點是當線性表采用順序存儲結構實現存儲時，其主要特點是【1】。 【答案【答案】邏輯結構中相鄰的結點在存儲結構中仍相鄰。邏輯結構中相鄰的結點在存儲結構中仍相鄰。41 a1 a2 . an進棧進棧出棧出棧棧頂棧頂棧底棧底5 5、堆棧和隊列、堆棧和隊列q 堆棧和隊列的定義堆棧和隊列的定義 棧和隊列棧和隊列是兩種特殊

27、的線性表，它們是運算時要受到是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也稱為某些限制的線性表，故也稱為限定性的數據結構。限定性的數據結構。v 堆棧的定義堆棧的定義堆棧：堆棧：限定只能在表的一端進行插入和刪除的特殊的線性表限定只能在表的一端進行插入和刪除的特殊的線性表, ,此種此種 結構稱為結構稱為后進先出。后進先出。設棧設棧s=s=（a a1 1，a a2 2，a ai i， ，a an n）, ,其中其中a a1 1是是棧底棧底元素，元素， a an n是是棧頂棧頂元素。元素。棧頂（棧頂（top)top)：允許插入和刪除的一端；允許插入和刪除的一端；約定約定toptop始終指

28、向新數據元素將存放的位置。始終指向新數據元素將存放的位置。棧底棧底（bottom):bottom):不允許插入和刪除的一端。不允許插入和刪除的一端。42v 隊列的定義隊列的定義隊列：隊列：一種特殊的線性結構，限定只能在表的一端進行插入，一種特殊的線性結構，限定只能在表的一端進行插入， 在表的另一端進行刪除的線性表在表的另一端進行刪除的線性表 。此種結構稱為。此種結構稱為先進先進 先出（先出（FIFO）表表。 a1 , a2 , a3 , a4 , an-1 , an隊隊 列列 示示 意意 圖圖隊頭隊頭隊尾隊尾v 隊列的主要運算隊列的主要運算（1）設置一個空隊列；（2）插入一個新的隊尾元素，稱為

29、進隊；（3）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素；43q 堆棧和隊列的例題講解堆棧和隊列的例題講解v棧和隊列的共同特點是（棧和隊列的共同特點是（ C C ） A)A)都是先進先出都是先進先出 B) B) 都是先進后出都是先進后出 C) C) 只允許在端點處插入和刪除元素只允許在端點處插入和刪除元素 D) D) 沒有共同點沒有共同點v如果進棧序列為如果進棧序列為e1,e2,e3,e4e1,e2,e3,e4，則可能的出棧序列是（則可能的出棧序列是（ B B ） A) e3,e1,e4,e2 A) e3,e1,e4,e2 B) e4,e3,e2,e1B) e4,e3,e2,e1 C) e3,e

30、4,e1,e2 C) e3,e4,e1,e2 D) D) 任意順序任意順序 4445la = 42+b8 82 26 6lb = 63+clc = 32+dld = 1+2= 8 + b= 2 + c= 6 + d= 3826u 一些重要的程序語言一些重要的程序語言( (如如C C語言和語言和PascalPascal語言語言) ) 允許過程允許過程的遞歸調用。而實現遞歸調用中的存儲分配通常用（的遞歸調用。而實現遞歸調用中的存儲分配通常用（ A A ） A) A) 棧棧B) B) 堆堆 C) C) 數組數組 D) D) 鏈表鏈表v 當循環隊列非空且隊尾指針等于隊頭指針時，說明循環隊列當循環隊列非

31、空且隊尾指針等于隊頭指針時，說明循環隊列已滿，不能進行入隊運算。這種情況稱為已滿，不能進行入隊運算。這種情況稱為【2 2】。答案：答案：上溢上溢 v 由兩個棧共享一個存儲空間的好處是（由兩個棧共享一個存儲空間的好處是（ B B ） A) A) 減少存取時間，降低下溢發生的機率減少存取時間，降低下溢發生的機率 B) B) 節省存儲空間，降低上溢發生的機率節省存儲空間，降低上溢發生的機率 C) C) 減少存取時間，降低上溢發生的機率減少存取時間，降低上溢發生的機率 D) D) 節省存儲空間，降低下溢發生的機率節省存儲空間，降低下溢發生的機率v 下列關于棧的敘述中正確的是（下列關于棧的敘述中正確的是

32、（ D D ）) )在棧中只能插入數據在棧中只能插入數據 B B）在棧中只能刪除數據在棧中只能刪除數據C C）棧是先進先出的線性表棧是先進先出的線性表 D D）棧是后進先出的線性表棧是后進先出的線性表v 下列關于隊列的敘述中正確的是（下列關于隊列的敘述中正確的是（ C C ）在隊列中只能插入數據）在隊列中只能插入數據 B B）在隊列中只能刪除數據在隊列中只能刪除數據C C）隊列是先進先出的線性表隊列是先進先出的線性表 D D）隊列是后進先出的線性表隊列是后進先出的線性表 46兩個棧共享只有兩個棧兩個棧共享只有兩個棧都多時才溢出。不共享都多時才溢出。不共享的話，兩個棧只有一個的話，兩個棧只有一個

33、棧多就溢出，棧多就溢出，RearRear隊尾隊尾FrontFront隊頭隊頭v 棧底至棧頂依次存放元素棧底至棧頂依次存放元素A A、B B、C C、D D，在第五個元素在第五個元素E E 入棧前，棧中元素可以出棧，則出棧序列可能是（入棧前，棧中元素可以出棧，則出棧序列可能是（ B B ） A) ABCEDA) ABCED B) DCBEAB) DCBEA C) DBCEA C) DBCEA D) CDABE D) CDABE 47D D出出C C出出B B出出 E E出出A A出出 E E進進 順序出棧：出棧：進棧：進棧： 順序存儲結構常用于線性數據結構，將邏輯上相鄰的數據元素存儲在物理上相鄰

34、的存儲單元里。v 順序存儲結構的三個缺點： 1.作插入或刪除操作時，需移動大量元數。 2.長度變化較大時，需按最大空間分配。 3.表的容量難以擴充。存儲內容存儲內容元素元素n n.元素元素i i.元素元素2 2元素元素1 148496 6、線性表的鏈式存儲 線性鏈表線性鏈表v線性鏈表的基本概念：線性鏈表的基本概念： 線性表的鏈式存儲結構稱為線性鏈表。 為了適應線性表的鏈式存儲結構，計算機存儲空間被劃分為一個一個小塊，每一小塊占若干字節，通常稱這些小塊為存儲結點。將存儲空間中的每一個存儲結點分為兩部：v一部分稱為數據域，用于存儲數據元素的值；v另一部分稱為指針域，用于存放下一個數據元素的存儲序號

35、（即存儲結點的地址），也就是指向后件結點. 線性鏈表中存儲結點的結構如圖2.20所示501536元素21400元素11346元素3 元素4head 1346 元素3 1536 . . . 1536 元素2 1400 . . . 元素4 1346 1400 元素1 1345 指針 存儲內容存儲地址 鏈式存儲 134552 指向線性表中第一個結點的指針HEAD稱為頭指針。 當HEAD=NULL（或0）時稱為空表。 對于線性鏈表，可以從頭指針開始，沿著各個結點的指針掃描到鏈表中的所有結點。線性鏈表的邏輯結構圖所示531、比順序存儲結構的存儲密度小 (每個節點都由數據域和指針域組成，所以相同空間內假設

36、全存滿的話順序比鏈式存儲更多)。2、邏輯上相鄰的節點物理上不必相鄰。3、插入、刪除靈活 (不必移動節點，只要改變節點中的指針)。4、查找結點時鏈式存儲要比順序存儲慢。v 鏈接存儲結構特點：鏈接存儲結構特點：545455v 線性鏈表的基本運算：線性鏈表的基本運算：線性鏈表的運算主要有以下幾個：線性鏈表的運算主要有以下幾個： 在線性鏈表中包含指定元素的結點之前在線性鏈表中包含指定元素的結點之前 插入插入一個新元素。一個新元素。 在線性鏈表中在線性鏈表中刪除刪除包含指定元素的結點。包含指定元素的結點。 將兩個線性鏈表按要求將兩個線性鏈表按要求合并合并成一個線性成一個線性 鏈表。鏈表。56 線性鏈表的

37、線性鏈表的 插入插入 運算：運算： 線性鏈表的插入線性鏈表的插入是指在鏈式存儲結構下是指在鏈式存儲結構下的線性表中插入一個新元素。的線性表中插入一個新元素。 為了要在線性鏈表中插入一個新元素，為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結點，然后將存首先要給該元素分配一個新結點，然后將存放新元素值的結點鏈接到線性鏈表中指定的放新元素值的結點鏈接到線性鏈表中指定的位置。位置。575758 線性鏈表的刪除線性鏈表的刪除指在鏈式存儲結構下的指在鏈式存儲結構下的線性表中刪除包含指定元素的結點。線性表中刪除包含指定元素的結點。 為了在線性鏈表中刪除包含指定元素的為了在線性鏈表中刪除包含指定

38、元素的結點，首先要在線性鏈表中找到這個結點，結點，首先要在線性鏈表中找到這個結點，然后將要刪除結點放回到可利用棧。然后將要刪除結點放回到可利用棧。 線性鏈表的線性鏈表的 刪除刪除 運算：運算：5959a1a2ana3L.線性表的鏈式存儲結構可用線性表的鏈式存儲結構可用 “結構指針結構指針”來描述來描述帶頭結點的線性鏈表帶頭結點的線性鏈表datanexttypedef struct LNode int data; Struct LNode *next; JD;babaxPP單鏈表的插入運算單鏈表的插入運算S在在P所指向的結點之后插入新的結點所指向的結點之后插入新的結點babaxanaia1a2P

39、Pai-1xL單鏈表的插入運算單鏈表的插入運算S單鏈表的插入運算單鏈表的插入運算void lbcr (JD *p, int x) / * 在在P所指向的結點之后插入新的結點所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK; anaia1a2Pai-1L單鏈表的插入運算單鏈表的插入運算void lbcr (JD *p, int x) / * 在在P所指向的結點之

40、后插入新的結點所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK;anaia1a2Pai-1L單鏈表的插入運算單鏈表的插入運算void lbcr (JD *p, int x) / * 在在P所指向的結點之后插入新的結點所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針定義指向結點類型的指針 */ s=(JD *)malloc(size

41、of(JD ); /* 生成新結點生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK; Sanaia1a2Pai-1xL單鏈表的插入運算單鏈表的插入運算void lbcr (JD *p, int x) / * 在在P所指向的結點之后插入新的結點所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK;Sanaia

42、1a2Pai-1xL單鏈表的插入運算單鏈表的插入運算void lbcr (JD *p, int x) / * 在在P所指向的結點之后插入新的結點所指向的結點之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK;Sanaia1a2Pai-1xL單鏈表的插入運算單鏈表的插入運算void lbcr (JD *p, int x) / * 在在P所指向的結點之后插入新的結點所指向的結點

43、之后插入新的結點 */ JD *s; /* 定義指向結點類型的指針定義指向結點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結點生成新結點 */ s-data=x; s-next=p-next; p-next=s; return OK;void lbsc(JD *p) /* 刪除刪除p指針指向結點的后一個結點指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結點的后繼結點 */ p-next=q-next; /* 修改修改p結點的指針域結點的指針域 */ free(q); /

44、* 刪除并釋放結點刪除并釋放結點 */ 單鏈表的刪除運算單鏈表的刪除運算ai-1a1aiai+1Lpvoid lbsc(JD *p) /* 刪除刪除p指針指向結點的后一個結點指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結點的后繼結點 */ p-next=q-next; /* 修改修改p結點的指針域結點的指針域 */ free(q); /* 刪除并釋放結點刪除并釋放結點 */ 單鏈表的刪除運算單鏈表的刪除運算ai-1a1aiai+1Lpvoid lbsc(JD *p) /* 刪除刪除p指針指向結點的后一個結點指

45、針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結點的后繼結點 */ p-next=q-next; /* 修改修改p結點的指針域結點的指針域 */ free(q); /* 刪除并釋放結點刪除并釋放結點 */ 單鏈表的刪除運算單鏈表的刪除運算a1q qai-1a1aiai+1Lpqvoid lbsc(JD *p) /*刪除刪除p指針指向結點的后一個結點指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結點的后繼結點 */ p-next=q

46、-next; /* 修改修改p結點的指針域結點的指針域 */ free(q); /* 刪除并釋放結點刪除并釋放結點 */ 單鏈表的刪除運算單鏈表的刪除運算ai-1a1aiai+1Lpqvoid lbsc(JD *p) /*刪除刪除p指針指向結點的后一個結點指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結點的后繼結點 */ p-next=q-next; /* 修改修改p結點的指針域結點的指針域 */ free(q); /* 刪除并釋放結點刪除并釋放結點 */ 單鏈表的刪除運算單鏈表的刪除運算ai-1a1aiai+

47、1Lpvoid lbsc(JD *p) /*刪除刪除p指針指向結點的后一個結點指針指向結點的后一個結點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結點的后繼結點 */ p-next=q-next; /* 修改修改p結點的指針域結點的指針域 */ free(q); /* 刪除并釋放結點刪除并釋放結點 */ 單鏈表的刪除運算單鏈表的刪除運算線性鏈表的查找操作：線性鏈表的查找操作：設無表頭結點的線性鏈表的頭指針為設無表頭結點的線性鏈表的頭指針為h, h, 沿著鏈表的沿著鏈表的開始往后找結點開始往后找結點x x，若找到，則返回該結點在鏈表中

48、，若找到，則返回該結點在鏈表中的位置，否則返回空地址。的位置，否則返回空地址。JD *lbcz (JD *h,int x) JD *p; p=h; while (p!=NULL & p-data!=x) p=p-next; return(p); 2.5.2 2.5.2 循環鏈表循環鏈表: : 首尾相接的鏈表。首尾相接的鏈表。 將最后一個結點的空指針改為指向頭結點，從任一將最后一個結點的空指針改為指向頭結點，從任一結點出發均可找到其它結點。結點出發均可找到其它結點。a1a2ana3L.帶頭結點的單鏈表帶頭結點的單鏈表a1a2ana3L.循環單鏈表循環單鏈表LS28375PR(1) L=P

49、-next;28375PRSLL 對以下單鏈表分別執行下列各程序段對以下單鏈表分別執行下列各程序段,并并畫出結果示意圖畫出結果示意圖.LS28375PR(2) R-data=P-data;28575PRS(3) R-data=P-next-data;28775PRSLS28375PR(4) P-next-next-next-data=P-data;25375PRSLS28375PR(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;LS28375PR(7) P=(JD*)malloc(sizeof(JD); P-data=10

50、; R-link=P; P-link=S;PLS28375PRLS28375PR(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-next=P; P-next=S;P10LS28375PRLS28375PR(5) P=(JD*)malloc(sizeof(JD); P-data=10; R-next=P; P-next=S;LS28375RP10LS28375PR(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-next=P; P-next=S;LS28375RP10LS28375PR(8) T=L; T-next=P-n

51、ext; free(P);LS2837PRT5LS28375PR(9) S-next=L;LS28375PR如果如果 S-next= =L 則則S所指向的結點為尾結點所指向的結點為尾結點.LS28375PR 循環鏈表的結構與前面所討論的線性鏈表相比，具有以下循環鏈表的結構與前面所討論的線性鏈表相比，具有以下兩個特點：兩個特點： 循環鏈表的頭指針指向表頭結點。循環鏈表的頭指針指向表頭結點。 在循環鏈表中，所有結點的指針構成了一個環狀鏈。在循環鏈表中，所有結點的指針構成了一個環狀鏈。 圖圖2.292.29是循環鏈表的示意圖。是循環鏈表的示意圖。v循環鏈表：循環鏈表：8889 在實際應用中，循環鏈表

52、與線性單鏈表相在實際應用中，循環鏈表與線性單鏈表相比主要有以下兩個方面的優點：比主要有以下兩個方面的優點： 在循環鏈表中，只要指出表中任何一個結點在循環鏈表中，只要指出表中任何一個結點 的位置，就可以從它出發訪問到表中其他所的位置，就可以從它出發訪問到表中其他所 有的結點。有的結點。 由于在循環鏈表中設置了一個表頭結點，因由于在循環鏈表中設置了一個表頭結點，因 此，在任何情況下，循環鏈表中至少有一個此，在任何情況下，循環鏈表中至少有一個 結點存在，結點存在，從而使空表與非空表的運算統一從而使空表與非空表的運算統一。v鏈表不具有的特點是（鏈表不具有的特點是（ B B ） A) A) 不必事先估計

53、存儲空間不必事先估計存儲空間 B) B) 可隨機訪問任一元素可隨機訪問任一元素 C) C) 插入刪除不需要移動元素插入刪除不需要移動元素 D) D) 所需空間與線性表長度成正比所需空間與線性表長度成正比v數據結構分為邏輯結構與存儲結構，線性鏈表屬于數據結構分為邏輯結構與存儲結構，線性鏈表屬于 【1 1】 。 【答案【答案】存儲結構存儲結構u 棧通常采用的兩種存儲結構是（棧通常采用的兩種存儲結構是（ A A ） A) A) 順序存儲結構和鏈表存儲結構順序存儲結構和鏈表存儲結構 B) B) 散列方式和索引方式散列方式和索引方式 C) C) 鏈表存儲結構和數組鏈表存儲結構和數組 D) D) 線性存儲

54、結構和非線性存儲結構線性存儲結構和非線性存儲結構q 線性鏈表的例題講解線性鏈表的例題講解9091u 線性表的順序存儲結構和線性表的鏈式存儲結構分別是線性表的順序存儲結構和線性表的鏈式存儲結構分別是( ( C C ) )A) A) 順序存取的存儲結構、順序存取的存儲結構順序存取的存儲結構、順序存取的存儲結構B) B) 順序存取的存儲結構、隨機存取的存儲結構順序存取的存儲結構、隨機存取的存儲結構C) C) 隨機存取的存儲結構、順序存取的存儲結構隨機存取的存儲結構、順序存取的存儲結構D) D) 任意存取的存儲結構、任意存取的存儲結構任意存取的存儲結構、任意存取的存儲結構順序存儲結構的地址在內存中是連

55、續的所以可以通過計算地址實現隨機存取，而鏈式存儲結構的存儲地址不一定連續，只能通過第1個結點的指針順序存取； 927 7、樹與二叉樹：、樹與二叉樹：v 樹的基本概念：樹的基本概念： 前面我們討論的線性表，棧、隊列和數組等都是線性結構。而樹是一種非線性數據結構，它的每一個結點，都可以有不止一個直接后繼，除根外的所有結點，都有且只有一個直接前趨。這些數據結點按分支關系組織起來，清晰地反映了數據元素之間的層次關系。 93現實世界中，能用樹的結構表示的例子現實世界中，能用樹的結構表示的例子：學校的行政關系、書的層次結構、人類的家族血緣關系等。學校的行政關系、書的層次結構、人類的家族血緣關系等。9494

56、9595 二叉樹(binary tree)是一種很有用的非線性結構。 二叉樹具有以下兩個特點：（1）非空二叉樹只有一個根結點；（2）每一個結點最多有兩棵子樹，且分別 稱為該結點的左子樹與右子樹。v 二叉樹（二叉樹（Binary TreeBinary Tree）：）： 因為樹的每個結點的度不同，存儲困難，使對樹的處理算法很復雜。所以引出二叉樹的討論。969797性質性質1 1：在任意一棵二叉樹中，度為0的結點 （即葉子結點）總是比度為2的結點多一個。二叉樹的性質：二叉樹的性質： 特別要注意：二叉樹是樹的特殊情況。a aa ab bb b兩棵不同的二叉樹98例子例子1 1：某二叉樹中度為2的結點有

57、18個，則 該二叉樹中有 19 19 個葉子結點。99性質性質2 2：二叉樹的第i層上至多有2 i-1（i 1）個結點二叉樹的性質：二叉樹的性質：423167891011121314155第三層上(i=3)，有23-1=4個節點。第四層上(i=4)，有24-1=8個節點。100二叉樹的性質：二叉樹的性質：性質性質3 3：深度為深度為h h的二叉樹中的二叉樹中至多至多含有含有2 2h h-1 -1個結點個結點423167891011121314155此樹的深度此樹的深度h=4h=4，共有共有2 24 4-1=15-1=15個節點。個節點。101v滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹 滿二叉樹

58、是指除最后一層外，每一層上的所有結點都有兩個子結點。 完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。 注意：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。102v 滿二叉樹的特點：滿二叉樹的特點：每一層上都含有最大結點數。每一層上都含有最大結點數。102103v完全二叉樹的特點：完全二叉樹的特點：除最后一層外，每一層都取最大除最后一層外，每一層都取最大 結點數，最后一層結點都集中在該層最左邊的若干位置結點數，最后一層結點都集中在該層最左邊的若干位置103104 對于對于完全二叉樹完全二叉樹而言而言如果它的結點個數為如果它的結點個數

59、為偶偶數，則該二叉樹中：數，則該二叉樹中：葉子結點的個數葉子結點的個數=非葉子結點的個數非葉子結點的個數如果它的結點個數為如果它的結點個數為奇奇數，則該二叉樹中：數，則該二叉樹中：葉子結點的個數葉子結點的個數=非葉子結點的個數非葉子結點的個數+1+1（即葉子結點數比非葉子結點數（即葉子結點數比非葉子結點數多一個多一個）規律總結：規律總結：105v 例題講解例題講解1、設一棵完全二叉樹共有700個結點，則在該二叉樹中有 350 350 個葉子結點。2、在深度為5的滿二叉樹中，葉子結點的個數為（ C C ）(即第5層的葉子個數2i-1) A) 32 B) 31 C) 16 D) 15 v二叉樹的遍

60、歷二叉樹的遍歷 二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。 二叉樹的遍歷可以分為三種：前序前序遍歷、中序中序遍歷、后序后序遍歷。 設訪問根結點記作設訪問根結點記作V V；遍歷根的左子樹記作遍歷根的左子樹記作L L；遍遍歷根的右子樹記作歷根的右子樹記作R R； 前序：前序： VLRVLR（即即根根左右）左右） 中序：中序： LVRLVR（即左即左根根右）右） 后序：后序： LRVLRV（即左右即左右根根）1061071071081 1、設一棵二叉樹的中序遍歷結果為、設一棵二叉樹的中序遍歷結果為DBEAFC,DBEAFC, 前序遍歷結果為前序遍歷結果為ABDECFABDECF，則后序遍歷結則后序遍歷