1、【教學課題】算法（第1章 數據結構，第1節）【目的要求】掌握算法的概念，算法的特點，理解算法時間復雜度和空間復雜度的含義，掌握時間復雜度的計算方法。【教學重點】算法的概念，算法特點，時間復雜度的概念和計算【教學難點】時間復雜度的概念和計算【方法與手段】講授+多媒體演示【作業布置】1、什么是算法，算法的特征有哪些？2、算法的基本要素有哪些？3、什么是算法的時間復雜度和空間復雜度？第1章 數據結構和算法1.1 算法一、算法（Algorithm）（P1）1、基本概念解題方案準確而完整的描述（為解決某個問題而采取的方法和步驟）。（不受機器、程序設計語言、編程者等因素的限制，不等于程序，但程序可以看作是

2、算法的一種描述，程序算法+數據，更具體說：程序算法+數據結構+程序設計方法+語言和環境）2、基本特征（1）可行性（算法中每個步驟必須有效可行，如a/b，其中b不能為零）（2）確定性算法中每個步驟都有明確的意義，不允許模棱兩可，不允許歧義。（3）有窮性（避免進入無限循環）算法中的操作必須在有限時間內完成。如：循環必須有終止條件。（4）擁有足夠的情報（算法中運算對象必須有初值，可以輸入，也可直接賦值，必須輸出）3、算法基本要素（P2）（1）對數據的運算和操作基本的運算有：算術運算（加、減、乘、除等）、邏輯運算（與、或、非等）、關系運算（大于、小于、等于、不等于等）、數據傳輸（賦值、輸入、輸出等）（

3、2）算法的控制結構算法中各操作之間的執行順序（順序結構、選擇結構、循環結構）4、算法設計基本方法（P3）（1）列舉法根據問題，列舉所有可能情況。如：從一個地方到達另一個地方的途徑。（2）歸納法根據少量情況，分析歸納，得出一般關系。如：找出數列中的通項式。（3）遞推法從已知初始條件出發，逐步推出所有中間結構和最后結果。如：案件偵破中根據以有線索進行的推理。本質上是歸納。（4）遞歸法將復雜的問題一層層進行分解，最后歸結為一些簡單的問題，然后將簡單的問題解決，再沿著分解的逆過程逐步進行綜合，將最初的問題解決。如：求n！,可用n！n*（n-1）!遞歸調用來實現。遞歸法分為直接遞歸和間接遞歸。遞歸的基礎

4、也是歸納。（5）減半遞推技術又叫分治法，重復將問題的規模減半。如：設方程f（x）0在區間a，b上的實根，且f（a）與f（b）異號，利用二分法求方程在a，b上的根。減半遞推法也是歸納法的一個分支。（6）回溯法也叫試探法，基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。二、算法復雜度（P5）（算法復雜度包括：時間復雜度和空間復雜度）1、時間復雜度（1）概念所謂時間復雜度是指執行算法所需要的計算工作量。（2）計算方法在實際中常用算法中所需基本運算的執行次數來度量算法的計算工作量，即時間復雜度。算法所執行的基本運算次數還與問題的規模有關，是問題規模的函數，記作：算法的工作量f（n）

5、,其中n是問題的規模。通常也記為：T（n）（f（n）(3)舉例如下三個程序段：A、+x;s=0;、for(i=1;i<=n;i+)+x;s+=x;、for(j=1;j<=n;j+) for(k=1;k<=n;k+)+x;s+=x;以上三個程序段中，+x為基本運算，運算次數即算法的計算工作量分別為：,n，n,也就是說時間復雜度分別為：,n，n，通常用：（1）、（n）、（n）表示。（4）分析時間復雜度的方法平均性態：指用各種特定輸入下的基本運算次數的加權平均值來度量時間復雜度。最壞情況復雜性：指在規模為n時，算法所執行的基本運算的最大次數。2、空間復雜度（P6）算法的空間復雜度一

6、般是指執行這個算法所需要的內存空間。包括：算法程序所占的空間、輸入的初始數據所占的空間、算法執行過程中所需的額外空間。如果額外空間是個常數，則稱該算法是原地工作的。在實際工作中通常采用壓縮存儲技術來減少不必要的額外空間。【教學課題】數據結構有基本概念（第1章 數據結構，第2節）【目的要求】理解數據結構的概念，搞清什么是邏輯結構、什么是物理結構，掌握數據結構的圖形表示形式，線性結構和非線性結構的區別。【教學重點】邏輯結構與存儲結構，數據結構的表示方法，線性結構和非線性結構【教學難點】數據結構的表示方法，各元素間的相互關系，線性結構的特點【方法與手段】講授+多媒體演示【作業布置】1、簡述有序表的對

7、分查找規則？2、什么是數據結構，什么是數據的邏輯結構，什么是數據的存儲結構？3、什么是線性結構，什么是非線性結構？1.2 數據結構的基本概念（P7）一、概述（P7）（計算機廣泛用于數據處理，處理的數據很多，并且各有特點，如何組織并處理這些數據，節省計算機的存儲空間，最終提高數據的處理效率，就是數據結構要研究的內容）1、數據結構研究的問題（3個方面）（1）數據的邏輯結構：數據集合中各數據元素之間的固有的邏輯關系；（2）數據的存儲結構：數據集合中各數據元素在計算機中的存儲關系，又叫物理結構；（3）對各種數據結構進行的運算。2、研究數據結構的目的：（總的而言，就是提高數據的處理效率）（1）提高數據處

8、理的速度；（2）節省數據處理過程中所占用的存儲空間。（常用的數據結構是軟件設計的基礎）二、什么是數據結構（P8）1、數據處理（對數據元素的各種運算）所謂數據處理，是指對數據集合中的各元素以各種方式進行運算，具體包括：插入、刪除、查找、添加、更改等，同時也包括對數據元素進行分析。（高效率的數據處理能大大提高計算機的工作效率，如何提高數據的處理效率也就是數據結構所要研究的內容）2、數據處理效率受數據的表示方式影響（1）例1-3 無序表的順序查找和有序表的對分查找。（兩個表數據相同，只是排列方式不同）無序表順序查找分析：A、查找規則：從第1個元素開始，逐個將表中的元素與被查數進行比較，直到表中某個元

9、素與被查數相等（查找成功）或者表中所有元素與被查數都進行了比較并且都不相等（查找失敗）為止；B、這種查找法效率低，特別是對于大規模數據表特別費時；C、例如查找54時，需要進行9次比較運算，才能查找成功。有序表對分查找分析：又如果被查數大于中間元素，則表示被查數在表的后半部或不在表中，此時可拋棄前半部元素保留后半部元素又如果被查數小于中間元素，則表示被查數在表的前半部或不在表中，此時可拋棄后半部元素保留前半部元素A、 查找規則：將被查數與表的中間元素比較：如果相等，則查找成功，查找結束；如 果不等， 然后對保留的部分（后半部分或前半部分）再按上述方法查找，直到查找成功或查找失敗為止。B、對分查找

10、效率較高，只適應于有序表；C、例如查找54時，只需要進行2次比較運算，查找成功。小結：用不同的方法表示數據，對數據的處理效率有明顯的影響。（2）例1-4 在學生登記情況表中按學號查找某學生情況或者查找某個分數段的學生情況。按學號查找學生情況分析：采用適當的查找方法，把待查學號與表中學號進行比較，查找相應信息，實現容易。查找分數段學生情況分析：通常情況要將所有學生情況都掃描一遍，也就是說要掃描分數段外的同學信息，效率較低。我們可以將表中的數據按分數段重新組織。（見P10,表1.2、1.3、1.4、1.5）小結：數據的不同表示方式，影響著數據的處理效率。（數據的表示方式實際上就是數據結構的一個方面

11、，所以數據結構影響著數據的處理效率）3、什么是數據結構（P10）（1）概念數據結構是指具有相互關聯的數據元素的集合，包括數據的邏輯結構和存儲結構（又叫物理結構）。（如：季節的數據集合、家庭成員的數據集合、數值的數據集合等）（或者說：數據結構是指反映數據元素間關系的數據元素的集合，是指帶有結構的數據元素的集合）（2）數據元素A、數據元素簡稱為元素，具有廣泛的意義。（一般而言，現實世界中客觀存在的一切個體都可以是數據元素，在數據處理領域中，每一個需要處理的對象都可以抽象成數據元素）B、數據集合中的數據元素通常都具有一定的關聯（即了解），這種固有的關系常常簡單地用前后件關系（或直接前驅與直接后繼關系

12、）來描述；C、數據元素間的任何關系都可以用前后件關系來描述。（數據結構應包含兩方面的信息：表示數據元素的信息和表示數據元素之間的前后件關系）4、數據的邏輯結構（P11）（1）概念反映數據元素之間邏輯關系（前后件關系）的數據結構，就是數據的邏輯結構，與數據元素在計算機中的存儲位置無關。有兩個構成要素：數據元素的集合、前后件關系。（2）表示方式B（D，R）其中：B表示數據結構，D為數據元素的集合，R為表示數據元素間的前后關系，常用二元組表示，如二元組（a，b）表示a是b的前件，b是a的后件。（3）例如一年四季數據結構可以表示成B（D，R）D春，夏，秋，冬R（春，夏），（夏，秋），（秋，冬）（又如家

13、庭成員數據結構的表示）5、數據的存儲結構（物理結構）（P12）（數據結構中的各元素在計算機存儲空間中的位置關系與邏輯關系是不同的）（1）概念數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構，也稱數據的物理結構。存儲結構中不僅存儲數據元素信息，還要存儲元素間前后件關系的信息。（2）一種邏輯結構可以表示成多種存儲結構。常見的存儲結構有：順序、鏈接、索引等。三、數據結構的圖形表示（P13）1、數據結構表示方式二元組表示（集合的形式）圖形表示2、數據結構的圖形表示（1）構成春結點：數據結點，用中間標有數據元素值的方框表示，如：有向線段：，表示數據元素間的前后件關系，從前件結點指向后件結點。

14、（如：P13,圖1.2,圖1.3）（2）優點：形象直觀（3）說明A、根結點：沒有前件的結點；B、終端結點（葉子結點）：沒有后件的結點；C、內部結點：數據結構中除了根結點和終端結點之外的其他結點；D、數據結構中元素結點可能是動態變化的，有可能被進行多種運算；E、數據結構中各元素之間的關系也可能動態變化。（P14,圖1.4）四、線性結構與非線性結構（P14）1、空的數據結構與非空的數據結構（根據結點或元素數量分）空的數據結構：沒有元素的數據結構稱為空的數據結構（沒有結點）2、線性數據結構和非線性數據結構（根據元素間前后件關系的復雜程度分）（1）線性數據結構概念：有且只有一個根結點，每一個結點最多有

15、一個前件，也最多有一個后件的數據結構。線性結構又叫線性表。特點：在一個線性結構中插入或者刪除一個結點還應是線性結構。（2）非線性數據結構概念：如果一個數據結構不是線性結構，則稱之為非線性結構。（3）說明線性結構和非線性結構都可以是空的數據結構。如果空數據結構的運算按線性結構的規則來處理，則屬于線性結構，否則屬于非線性結構。【教學課題】線性表及其順序存儲結構（第1章 數據結構，第3節）【目的要求】理解線性表的意義，搞清線性表的順序存儲結構，掌握線性表插入與刪除操作的算法，并能用C程序編程實現。【教學重點】線性表的概念，線性表順序存儲結構，插入運算，刪除運算【教學難點】插入去處，刪除運算【方法與手

16、段】講授+多媒體演示【作業布置】1、什么是線性表？線性表有什么特點？2、線性表的順序存儲有什么特點？3、簡述線性表插入運算和刪除運算的基本規則？1.3 線性表及其順序存儲結構（P15）一、線性表的基本概念1、什么是線性表（Linear List）線性表是由n（n0）個元素a1，a2，a3，an組成的一個有限序列，表中的每個數據元素，除了第一個，有且只有一個前件，除了最后一個，有且只有一個后件。2、常見的線性表一維數組，矩陣（二維數組），數據庫表等（線性表中的數據元素可以是一個單一的數據，也可以若干數據的組合，如數據庫表中的記錄）3、線性表的表示（集合）（a1，a2，a3，ai，,an）其中：a

17、i就是相應的數據元素（結點）（線性表也可以是一個空表）4、線性表的特點是一種線性結構，元素在表中的位置由其序號決定，元素之間的相對位置是線性的。對于非空的線性表，具有如下特點：（1）有且只有一個根結點；（2）有且只有一個終端結點；（3）內部結點有且只有一個前件，有且只有一個后件。線性表中結點的個數n稱為線性表的長度。結點個數為0的線性表，稱為空表。二、線性表的順序存儲結構（P16）1、線性表通常采用順序存儲的方法來存儲各個元素。（這種方法又叫順序分配）2、順序存儲的特點（1）所有元素所占的存儲空間是連續的；（2）在存儲空間中各元素是按邏輯順序依次存放。（線性表中的前后件兩個元素在存儲空間中是緊

18、鄰的，并且前件一定在后件的前面）3、舉例例如一維、二維數組的內存表示。4、線性表存儲結構下的基本運算（1）在指定位置插入一個元素（2）刪除線性表中的指定元素（3）查找某個或某些特定的元素（4）線性表的排序（5）按要求將一個線性表拆分為多個線性表（6）將多個線性表合并為一個線性表（7）復制線性表（8）逆轉一個線性表三、插入運算（P17）1、例1.9 圖1.7（a）為一個長度為8的線性表順序存儲在長度為10的存儲空間中。現要求在第2個元素（18）之前插入一個新元素87。（具體分析見P17）2、插入運算基本規則一般情況下，要在第i（1in）個元素之前插入一個新元素，首先從最后一個元素（即第n個）開始

19、，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動結束后，第i個位置就被空出，然后將新元素放到第i個位置即可。3、具體應用定義一個有10個元素的一維數組，并輸入9個數到前面9個元素，然后插入一個數m到第n個元素處，其中插入的數m和元素位置n從鍵盤輸入。（講授時，先把m和n的值定為一個具體的數來進行）4、說明（1）上溢：當前存儲空間已滿，還往其中插入數據時，就會出現“上溢”的錯誤。（2）執行一次插入操作，線性表長度就會增加1。四、刪除運算（P18）1、例1.10 圖1.8（a）為一個長度8的線性表順序存儲在長度為10的存儲空間。現要求刪除線性表中的第1個元素（29）。（具體分析見P

20、18）2、刪除元素基本規則一般情況下，要刪除第i（1in）個元素時，就要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。3、具體應用定義一個有10個元素的一維數組，并輸入數據，然后刪除第n個元素，其中元素位置n從鍵盤輸入。4、說明一個線性表，執行一次刪除操作后，線性表的長度減小1。【教學課題】棧和隊列（第1章 數據結構，第4節）【目的要求】理解棧的意義，搞清棧的存儲方式，掌握入棧與退棧運算，理解隊列的意義與特點，搞清隊頭與隊尾指針的移動，掌握循環隊列的特點。【教學重點】棧的概念，存儲方式，入棧與退棧，隊列的概念，隊列指針的移動，循環隊列【教學難點】入棧與退棧運算，隊

21、列指針的移動，循環隊列【方法與手段】講授+多媒體演示【作業布置】1、什么是棧，棧有什么特點？2、什么是隊列，隊列有什么特點？3、簡述棧和循環隊列的基本運算.1.4 棧和隊列一、棧及其基本運算（P19）1、什么是棧（stack）（1）概念棧是只能在一端進行插入與刪除操作的線性表。其中允許插入與刪除操作的一端稱為棧頂，而不允許進行插入刪除操作的端稱為棧底，常用指針top指向棧頂位置，指針bottom指向棧底。（類似于往瓶中放東西或取東西，也類似于子彈夾的結構）（2）特點FILO（First In Last Out，先進后出）或LIFO（Last In First Out，后進先出）2、棧的順序存儲

22、及其運算（1）順序存儲通常用一維數組S（1：m）作為棧的順序存儲空間。常用棧底指針（bottom）指向棧空間的低位置端（即數組的起始位置，也就是第一個元素的位置），用棧頂指針（top）指向棧空間的高位置端（即數組中最后一個元素位置）（圖1.9、1.10）當top=0時表示棧空，top=m時表示棧滿。（2）棧的基本運算入棧運算：就是往棧中插入一個元素，即在棧頂位置插入一個新元素。具體操作是：先將棧頂指針top加1，然后新元素插入到棧頂指針指向的新位置。退棧運算：就是從棧中刪除一個元素，即取出棧頂元素賦給一個變量。具體操作是：先將當前棧頂元素賦給一個變量，然后棧頂指針top減1。（第一步操作可以省

23、略）讀棧頂元素：就是將棧頂元素賦給一個指定的變量，棧頂指針位置不變。（3）棧的上溢與棧的下溢上溢：當棧空間已滿時，如果再進行入棧操作，就會出現上溢錯誤。下溢：當棧已空時，如果再進行退棧操作，就會出現下溢錯誤。二、隊列及其基本運算（P21）1、什么是隊列（queue）（1）概念隊列就是允許在一端進行插入，而在另一端進行刪除的線性表。其中允許插入的一端稱為隊尾，常用rear指針指向隊尾元素，允許刪除的一端稱為隊頭，常用front指針指向排頭元素的前一個位置。（類似于日常生活中的排隊行為，圖1.12）（2）特點FIFO（First In First Out，先進先出）或LILO（Last In La

24、st Out，后進后出）（3）特別說明A、關于隊頭與隊尾指針的指向，總的原則：隊列中的頭尾指針不是頭空就是尾空。（圖1.11,尾空，圖1.12頭空）。B、為了描述方便，在C中約定：初始化建空隊列時，令front=rear=0,每當隊列插入新元素時，尾指針（rear）增加1,每當刪除隊列的頭元素時，頭指針（front）增加1。所以在非空的隊列中，尾指針始終指向隊列尾元素的下一個位置，頭指針始終指向隊列的頭元素。（圖1.11）C、但如果說“尾指針指向隊尾元素，頭指針指向隊頭元素的前一位置”也應認可。（圖1.12,1.13）（4）隊列運算入隊運算：往隊列的隊尾插入一個元素。具體操作：先將隊尾指針（r

25、ear）加1，然后將新的元素放入到隊尾指針指向的位置。（圖1.12 c）退隊運算：從隊列的排頭刪除一個元素。具體操作：先將隊頭指針（front）加1,然后將指針所指向的元素的值賦給一指定的變量。（圖1.12 b）（5）隊列的順序存儲在程序設計中，通常定義一維數組作為隊列的順序存儲空間。2、循環隊列及其運算（P22）（1）概念所謂循環隊列就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。（循環隊列的環形表示如右圖所示）（2）指針的指向循環隊列中常用隊尾指針指向隊列的隊尾元素，隊頭指針指向指向排頭元素的前一個位置。（頭尾指針之間的所有元素為隊列的元素，據此可以計

26、算隊列中元素的個數(r-f+m)%m)(3)循環隊列運算A、入隊運算入隊運算是在循環隊列的隊尾加入一個新元素。具體操作：先將隊尾指針rear增加1，如果rear的值超過了隊列的長度，就把rear置為1；然后，將新元素插入到隊尾指針指向的位置。B、退隊運算退隊運算是將循環隊列的排頭位置退出一個元素并賦給指定的變量。具體操作：先將隊頭指針front增加1,如果front的值超過了隊列長度，就把front置為1；然后，將排頭指針元素賦給指定的變量。（4）隊列的上溢和下溢上溢：當隊列已滿時，如果執行插入操作，則會產生上溢錯誤。下溢：當隊列已空時，如果執行退隊操作，則會產生下溢錯誤。【教學課題】線性鏈表

27、（第1章 數據結構，第5節）【目的要求】理解線性表的不足，搞清鏈式存儲結構的特點，掌握線性鏈表的插入與刪除運算，理解循環列表的特點。【教學重點】線性表的缺點，鏈式存儲結構及其特點，線性鏈表的特點，線性表的插入與刪除運算，循環列表及其特點。【教學難點】鏈式存儲結構的理解，線性鏈表的插入與刪除運算，循環列表的特點【方法與手段】講授+多媒體演示【作業布置】1、什么是鏈式存儲結構，有什么特點？2、簡述在線性鏈表中包含元素x的結點之前插入一個新元素b的過程，要求有圖示和文字描述。3、簡述在線性鏈表中刪除包含元素x的結點p的過程，要求有圖示和文字描述。4、循環鏈表有什么特點？ 1.5 線性鏈表一、線性鏈表

28、的基本概念（P24）1、線性表順序存儲的優缺點（1）優點結構簡單，運算方便，適應于長度不大且固定的線性數據（2）缺點A、工作量大：插入或刪除元素時，為保證運算后仍為順序存儲，需移動大量的數據；B、空間不便于擴充：容易出現“上溢”錯誤；C、不便于對存儲空間的動態分配：要用多個線性表時，如果平均分配空間，會出現用不著或不夠用的現象；常用的方法就是共享整個存儲空間，對某個線性表動態分配存儲空間，那么勢必在分配空間前必須將上次使用空間的線性表元素移開，這就導致工作量劇增。2、鏈式存儲結構（1）概述用一組任意的存儲單元存儲數據的存儲結構，其中存儲單元稱為存儲結點，簡稱結點（NODE），每個結點由兩部分組

29、成：一部分用于存放數據元素值，稱為數據域，一部分用于存放指針，稱為指針域，指針域中的指針總是指向該結點的前一個結點或后一個結點（即前件或后件）。（其中的“任意”主要是指各結點的位置可以連續也可以不連續，不同于順序結構各結點必須連續存放）（具體形式如圖1.16所示）（2）特點存儲空間可以連續也可以不連續，各結點的存儲順序與邏輯關系可以不一致，其邏輯關系由指針域來確定。（圖1.15與1.17代表連續存儲的線性鏈表，圖1.18代表不連續存儲的線性鏈表）（3）說明鏈式存儲可以表示線性結構也可以表示非線性結構。3、線性鏈表（P25）（1）概念線性表的鏈式存儲結構稱為線性鏈表。系統為線性表的每個元素劃分占

30、若干字節的一小塊存儲空間，同時這一小塊存儲空間一部分用于存放數據元素的值，稱為數據域，另一部分用于存放該元素后一結點的位置，稱為指針域。（2）說明A、線性鏈表中用專門的指針HEAD指向第一個元素，即第一個結點，此指針被稱為頭指針；B、線性鏈表中的最后一個元素，即終端結點沒有后件，其指針域為空，用NULL或0表示，代表鏈表終止。C、如果HEADNULL（或0）時，線性表就是一個空表；D、線性單鏈表（單向鏈表）：每個結點只有一個指針域的鏈表。這種鏈表只能順指針向鏈尾方向進行掃描，不能反向掃描；E、雙向鏈表：每個結點有左指針（Llink,指向前件）和右指針（Rlink,指向后件）兩個指針的線性鏈表。

31、（圖1.19所示）；F、程序中，通常利用結構體變量來構造鏈表。4、帶鏈的棧（又稱為可利用棧）（P26）（1）帶鏈的棧的表示（圖1.20）（2）作用：可利用棧常用來收集存儲空間中所有空閑的存儲結點。當需要存儲結點時，即從可利用的棧的頂部取出棧頂結點；當系統要釋放一個存儲結點時，將該結點空間放回到可利用棧的棧頂。存儲結點的入棧如圖1.21 a所示，出棧操作如圖1.21 b所示，都在棧頂進行。5、帶鏈的隊列（P27）（1）帶鏈的隊列的表示（圖1.22 a所示）（2）結點的插入和刪除：插入運算如圖1.22 b，在隊尾進行；刪除運算如圖1.22 c所示，在隊頭進行。二、線性鏈表的基本運算（P27）1、基

32、本運算（1）在鏈表中包含指定元素的結點之前插入一個新元素（2）在鏈表中刪除包含指定元素的結點（3）將兩個線性鏈表按要求合并成一個線性鏈表（4）將一個線性鏈表按要求進行分解（5）逆轉線性鏈表（6）復制線性鏈表（7）線性鏈表的排序（8）線性鏈表的查找2、查找指定元素查找元素X的方法：從頭指針指向的結點開始往后沿指針進行掃描，直到后面已沒有結點或下一個結點的數據域為X為止。查找元素X的作用：元素的查找，經常是為了進行插入或刪除操作而進行的。（在查找時，往往是需要記錄下該結點的前一個結點）3、插入元素（1）線性鏈表的插入是指在鏈式存儲結構的線性表中插入一個新元素。（2）例如：在線性鏈表中包含元素x的結

33、點之前插入新元素b。步驟如下（圖1.23所示）：A、從可利用棧中取得一個結點，設該結點號為p，即取得的結點的存儲序號存放在變量p中。并置結點p的數據域為插入的元素值b。B、在線性鏈表中尋找包含元素x的前一個結點，該結點的存儲序號為q。C、將結點p插入到結點q之后。具體的操作：使結點p指向包含元素x的結點；同時使結點q指向結點p。（上述操作，實際就是結點指向發生改變，具體操作時就是更改相應結點指針域的值）（3）優點線性鏈表的插入操作，新結點是為來自于可利用棧，因此不會造成線性表的溢出。同樣，由于可利用棧可被多個線性表利用，因此，不會造成存儲空間的浪費，大家動態地共同使用存儲空間。4、刪除元素（P

34、30）（1）線性鏈表的刪除是指在鏈式存儲結構下的線性表中刪除包含指定元素的結點。（2）例如：在線性鏈表中刪除包含元素x的結點。步驟如下（圖1.24）：A、在線性表中找到結點p(包含指定元素x)的前一個結點q；B、將結點p從線性鏈表中刪除，即讓結點q的指針指向p的后繼結點；C、將刪除的結點p送回可利用棧,即讓p指向棧頂元素而成為新的棧頂元素。（上述操作，實際就是結點指向發生改變，具體操作時就是更改相應結點指針域的值）（3）優點刪除一個指定的元素，不需要移動其他的元素即可實現，這是順序存儲的線性表所不能實現的。同時，被刪除的結點可被用來存放其他數據，從而更有效地利用計算機的存儲空間。三、循環鏈表及

35、其基本運算（P30）1、線性鏈表的缺點空表與非空表的運算不統一（如：插入一個新的元素）2、循環鏈表（Circular Linked List）的特點（1）在循環鏈表中增加一個表頭結點，其數據域為任意或根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。（2）循環鏈表中最后一個結點的指針域不是空的，而是指向表頭結點。在循環鏈表中，所有結點的指針構成一個環狀鏈。（圖1.25所示）3、說明（1）空的線性鏈表沒有一個結點，而空的循環鏈表有一個表頭結點，其數據域值任意，指針域指向表頭結點本身，和頭指針（HEAD）相同（圖1.25 b所示）；（嚴格上說循環列表不存在空表）（2

36、）循環列表中，只要給任何一個結點的位置，均可以從它開始掃描到所有的結點，而線性鏈表做不到，線性鏈表是一種單向的鏈表，只能按照指針的方向進行掃描；（2）循環列表的空表與非空表運算統一。【教學課題】樹和二叉樹（第1章 數據結構，第6節）【目的要求】理解樹的概念，掌握其基本的術語和特點，掌握二叉樹的概念和特點，了解其存儲結構，掌握二叉樹的遍歷。【教學重點】樹的概念和特點，二叉樹與滿二叉樹、完全二叉樹，二叉樹的存儲，二叉樹的遍歷【教學難點】二叉樹的性質，二叉樹的存儲結構，二叉樹的遍歷【方法與手段】講授+多媒體演示【作業布置】1、什么是樹，樹有什么特點？2、二叉樹有什么特點？并寫出二叉樹的基本性質。3、

37、什么是滿二叉樹，什么是完全二叉樹？4、什么是二叉樹的遍歷，簡述前序、中序、后序遍歷。1.6 樹與二叉樹一、樹的概念（tree）（P31）1、概述樹是一種簡單的非線性結構，在這種結構中所有元素之間具有明顯的層次關系，有如自然界中倒置的樹，從而把這種結構形象稱為“樹”。在樹形結構中，上端結點是前件，下端結點是后件，表示前后件關系的箭頭可以省略。如：各單位的組織結構圖、書的目錄結構等。（圖1.27、1.28）2、樹的基本術語（1）父結點：在樹中，某個結點的前件，稱為其父結點；（2）子結點：在樹中，某個結點的后件，稱為其子結點；（3）葉子結點：在樹中，沒有后件的結點稱為葉子結點；（4）根結點：在樹中，

38、沒有前件的結點，稱為根結點；（5）結點的度：一個結點所擁有的后件個數稱為該結點的度；（6）樹的度（degree）：在樹中，所有結點中的最大的度稱為樹的度；（7）樹的深度（depth）：樹的最大層次稱為樹的深度,有時也叫高度（樹的深度不是樹的度）；（8）子樹：在樹中，以某結點的一個子結點為根構成的樹稱為該結點的一棵子樹。3、樹的特點（1）在樹中，每一個結點只有一個父結點；（2）在樹中，每個結點可以有多個子結點；（3）在樹中，只有一個根結點；（4）在樹中，根結點在第一層，同層上所有結點的所有子結點都在下一層；（5）在樹中，葉子結點沒有子樹。4、用樹表示算術表達式（1）表示的原則A、表達式的運算符為

39、結點，稱為運算符結點；B、運算符的每一個運算對象是該運算符的子樹（從左至右）；C、表達式中的單個變量均為葉子結點。（2）舉例：a*(b+c/d)+e*h-g*f(s,t,x+y)（圖1.29 a、b所示）二、二叉樹及其基本性質（Binary Tree）（P34）1、什么是二叉樹（Binary Tree）（1）概述二叉樹是一種非線性結構，具有如下特點：A、非空二叉樹只有一個根結點；B、每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。（2）說明A、二叉樹中每個結點的度最大為2（可以為0或1）；B、二叉樹中每個結點的子樹被明顯分為左子樹和右子樹，兩個子樹可以都有，也可以只有一個，也可全部

40、沒有；C、二叉樹中任何子樹均為二叉樹。（圖1.31）2、二叉樹的基本性質（1）性質1：在二叉樹的第k層上，最多有2k-1（k1）個結點；（2）性質2：深度為m的二叉樹最多有2m-1個結點；（3）性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總比度為2的結點多一個；（4）性質4：具有n個結點的二叉樹，其深度至少為log2n+1，其中log2n表示log2n的整數部分。3、滿二叉樹與完全二叉樹（1）滿二叉樹除最后一層外每一層上的所有結點都有兩個子結點的二叉樹，稱為滿二叉樹。滿二叉樹中每一層的結點數都達到最大值（2），第k層上共有2k-1個結點，深度為m的滿二叉樹有2m-1個結點。（達到了二

41、叉樹性質1、2中的最大值，圖1.32）（2）完全二叉樹除最后一層外，每一層的結點數均達到最大值，且最后一層只缺少右邊的若干個結點，這樣的二叉樹稱為完全二叉樹。在完全二叉樹中，葉子結點只可能在層次最大的兩層上出現。（圖1.33）（3）說明A、滿二叉樹也是完全二叉樹，但完全二叉樹一般不是滿二叉樹；B、如果完全二叉樹的高度為h，那么除第 h 層外，其它各層 (1h-1) 的結點數都達到最大個數，第 h 層從右向左連續缺若干結點；C、性質5：具有n個結點的完全二叉樹的深度為log2n+1；D、性質6：設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1、2、n給結點編號，對于

42、編號為k（k=1,2,n）的結點有如下結論： 若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT(k/2)。 若2kn，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（當然也沒有右子結點） 若2k+1n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。三、二叉樹的存儲結構（通常采用鏈式存儲結構）（P36）1、概述：（1）存儲形式：常采用鏈式存儲結構（2）構成：數據域：存放結點的數據值。左子針域：存儲該結點的左子結點的存儲位置指針域：右指針域：存儲該結點的右子結點的存儲位置第i個結點的存儲結構如下：LchildValueRchild

43、iL(i)V(i)R(i)（3）說明：二叉樹的鏈式存儲結構也稱為二叉樹的鏈表，簡稱二叉鏈表。在二叉樹在存儲中，用一個頭指針（BT）指向二叉樹的根結點的存儲位置。2、舉例ABCDEFGHIJKLMNOPQR有如下圖所示的二叉樹（按層次將所有結點順序編號）：A1B2C3D4E5F6G7H8I9J10K11L12M13N14O15P16Q17R18BT其二叉鏈表的邏輯狀態如下圖所示（BT為二叉鏈表的頭指針，指向二叉樹的根結點，字母后的數字為結點的序號）：其二叉鏈表的物理狀態如下圖所示：iL(i)V(i)R(i)BTà12A324B536C748D9510E11612F13714G15816

44、H17918I0100J0110K0120L0130M0140N0150O0160P0170Q0180R0四、二叉樹的遍歷（P38）1、概念所謂二叉樹的遍歷就是指不重復訪問二叉樹中所有的結點。2、二叉樹遍歷的種類（3種）（1）前序遍歷（DLR，根左右）A、前序遍歷規則：先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。并且，在遍歷左子樹和遍歷右子樹時，依然是先遍歷根結點，然后是左子樹，再是右子樹。B、具體操作如下：如果：二叉樹為空，則結束返回。否則：訪問根結點®前序遍歷左子樹®前序遍歷右子樹 C、前序遍歷二叉樹的過程是一個遞歸過程，得到的結果稱為前序序列。（2）中序遍歷（LDR

45、，左根右）A、中序遍歷規則：先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。并且，在遍歷左子樹和遍歷右子樹時，依然是先遍歷左子樹，然后是根結點，再是右子樹。B、具體操作如下：如果：二叉樹為空，則結束返回。否則：中序遍歷左子樹®訪問根結點 ®中序遍歷右子樹 C、中序遍歷二叉樹的過程是一個遞歸過程，得到的結果稱為中序序列。（3）后序遍歷（LRD，左右根）A、后序遍歷規則：先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。并且，在遍歷左子樹和遍歷右子樹時，依然是先遍歷左子樹，然后是右子樹，再是根結點。B、具體操作如下：如果：二叉樹為空，則結束返回。否則：后序遍歷左子樹®后序遍歷右子樹®訪問根結點 C、后序遍歷二叉樹的過程是一