（參考）NCRE公共基礎(chǔ)知識(shí)教案(第1章)

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

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

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

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

5、,其中n是問(wèn)題的規(guī)模。通常也記為：T（n）（f（n）(3)舉例如下三個(gè)程序段：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;以上三個(gè)程序段中，+x為基本運(yùn)算，運(yùn)算次數(shù)即算法的計(jì)算工作量分別為：,n，n,也就是說(shuō)時(shí)間復(fù)雜度分別為：,n，n，通常用：（1）、（n）、（n）表示。（4）分析時(shí)間復(fù)雜度的方法平均性態(tài)：指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量時(shí)間復(fù)雜度。最壞情況復(fù)雜性：指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。2、空間復(fù)雜度（P6）算法的空間復(fù)雜度一

6、般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。包括：算法程序所占的空間、輸入的初始數(shù)據(jù)所占的空間、算法執(zhí)行過(guò)程中所需的額外空間。如果額外空間是個(gè)常數(shù)，則稱該算法是原地工作的。在實(shí)際工作中通常采用壓縮存儲(chǔ)技術(shù)來(lái)減少不必要的額外空間。【教學(xué)課題】數(shù)據(jù)結(jié)構(gòu)有基本概念（第1章 數(shù)據(jù)結(jié)構(gòu)，第2節(jié)）【目的要求】理解數(shù)據(jù)結(jié)構(gòu)的概念，搞清什么是邏輯結(jié)構(gòu)、什么是物理結(jié)構(gòu)，掌握數(shù)據(jù)結(jié)構(gòu)的圖形表示形式，線性結(jié)構(gòu)和非線性結(jié)構(gòu)的區(qū)別?！窘虒W(xué)重點(diǎn)】邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的表示方法，線性結(jié)構(gòu)和非線性結(jié)構(gòu)【教學(xué)難點(diǎn)】數(shù)據(jù)結(jié)構(gòu)的表示方法，各元素間的相互關(guān)系，線性結(jié)構(gòu)的特點(diǎn)【方法與手段】講授+多媒體演示【作業(yè)布置】1、簡(jiǎn)述有序表的對(duì)

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

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

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

10、效率較高，只適應(yīng)于有序表；C、例如查找54時(shí)，只需要進(jìn)行2次比較運(yùn)算，查找成功。小結(jié)：用不同的方法表示數(shù)據(jù)，對(duì)數(shù)據(jù)的處理效率有明顯的影響。（2）例1-4 在學(xué)生登記情況表中按學(xué)號(hào)查找某學(xué)生情況或者查找某個(gè)分?jǐn)?shù)段的學(xué)生情況。按學(xué)號(hào)查找學(xué)生情況分析：采用適當(dāng)?shù)牟檎曳椒ǎ汛閷W(xué)號(hào)與表中學(xué)號(hào)進(jìn)行比較，查找相應(yīng)信息，實(shí)現(xiàn)容易。查找分?jǐn)?shù)段學(xué)生情況分析：通常情況要將所有學(xué)生情況都掃描一遍，也就是說(shuō)要掃描分?jǐn)?shù)段外的同學(xué)信息，效率較低。我們可以將表中的數(shù)據(jù)按分?jǐn)?shù)段重新組織。（見(jiàn)P10,表1.2、1.3、1.4、1.5）小結(jié)：數(shù)據(jù)的不同表示方式，影響著數(shù)據(jù)的處理效率。（數(shù)據(jù)的表示方式實(shí)際上就是數(shù)據(jù)結(jié)構(gòu)的一個(gè)方面

11、，所以數(shù)據(jù)結(jié)構(gòu)影響著數(shù)據(jù)的處理效率）3、什么是數(shù)據(jù)結(jié)構(gòu)（P10）（1）概念數(shù)據(jù)結(jié)構(gòu)是指具有相互關(guān)聯(lián)的數(shù)據(jù)元素的集合，包括數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)（又叫物理結(jié)構(gòu)）。（如：季節(jié)的數(shù)據(jù)集合、家庭成員的數(shù)據(jù)集合、數(shù)值的數(shù)據(jù)集合等）（或者說(shuō)：數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素間關(guān)系的數(shù)據(jù)元素的集合，是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合）（2）數(shù)據(jù)元素A、數(shù)據(jù)元素簡(jiǎn)稱為元素，具有廣泛的意義。（一般而言，現(xiàn)實(shí)世界中客觀存在的一切個(gè)體都可以是數(shù)據(jù)元素，在數(shù)據(jù)處理領(lǐng)域中，每一個(gè)需要處理的對(duì)象都可以抽象成數(shù)據(jù)元素）B、數(shù)據(jù)集合中的數(shù)據(jù)元素通常都具有一定的關(guān)聯(lián)（即了解），這種固有的關(guān)系常常簡(jiǎn)單地用前后件關(guān)系（或直接前驅(qū)與直接后繼關(guān)系

12、）來(lái)描述；C、數(shù)據(jù)元素間的任何關(guān)系都可以用前后件關(guān)系來(lái)描述。（數(shù)據(jù)結(jié)構(gòu)應(yīng)包含兩方面的信息：表示數(shù)據(jù)元素的信息和表示數(shù)據(jù)元素之間的前后件關(guān)系）4、數(shù)據(jù)的邏輯結(jié)構(gòu)（P11）（1）概念反映數(shù)據(jù)元素之間邏輯關(guān)系（前后件關(guān)系）的數(shù)據(jù)結(jié)構(gòu)，就是數(shù)據(jù)的邏輯結(jié)構(gòu)，與數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。有兩個(gè)構(gòu)成要素：數(shù)據(jù)元素的集合、前后件關(guān)系。（2）表示方式B（D，R）其中：B表示數(shù)據(jù)結(jié)構(gòu)，D為數(shù)據(jù)元素的集合，R為表示數(shù)據(jù)元素間的前后關(guān)系，常用二元組表示，如二元組（a，b）表示a是b的前件，b是a的后件。（3）例如一年四季數(shù)據(jù)結(jié)構(gòu)可以表示成B（D，R）D春，夏，秋，冬R（春，夏），（夏，秋），（秋，冬）（又如家

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

14、（如：P13,圖1.2,圖1.3）（2）優(yōu)點(diǎn)：形象直觀（3）說(shuō)明A、根結(jié)點(diǎn)：沒(méi)有前件的結(jié)點(diǎn)；B、終端結(jié)點(diǎn)（葉子結(jié)點(diǎn)）：沒(méi)有后件的結(jié)點(diǎn)；C、內(nèi)部結(jié)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)中除了根結(jié)點(diǎn)和終端結(jié)點(diǎn)之外的其他結(jié)點(diǎn)；D、數(shù)據(jù)結(jié)構(gòu)中元素結(jié)點(diǎn)可能是動(dòng)態(tài)變化的，有可能被進(jìn)行多種運(yùn)算；E、數(shù)據(jù)結(jié)構(gòu)中各元素之間的關(guān)系也可能動(dòng)態(tài)變化。（P14,圖1.4）四、線性結(jié)構(gòu)與非線性結(jié)構(gòu)（P14）1、空的數(shù)據(jù)結(jié)構(gòu)與非空的數(shù)據(jù)結(jié)構(gòu)（根據(jù)結(jié)點(diǎn)或元素?cái)?shù)量分）空的數(shù)據(jù)結(jié)構(gòu)：沒(méi)有元素的數(shù)據(jù)結(jié)構(gòu)稱為空的數(shù)據(jù)結(jié)構(gòu)（沒(méi)有結(jié)點(diǎn)）2、線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)（根據(jù)元素間前后件關(guān)系的復(fù)雜程度分）（1）線性數(shù)據(jù)結(jié)構(gòu)概念：有且只有一個(gè)根結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)最多有

15、一個(gè)前件，也最多有一個(gè)后件的數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)又叫線性表。特點(diǎn)：在一個(gè)線性結(jié)構(gòu)中插入或者刪除一個(gè)結(jié)點(diǎn)還應(yīng)是線性結(jié)構(gòu)。（2）非線性數(shù)據(jù)結(jié)構(gòu)概念：如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。（3）說(shuō)明線性結(jié)構(gòu)和非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。如果空數(shù)據(jù)結(jié)構(gòu)的運(yùn)算按線性結(jié)構(gòu)的規(guī)則來(lái)處理，則屬于線性結(jié)構(gòu)，否則屬于非線性結(jié)構(gòu)?！窘虒W(xué)課題】線性表及其順序存儲(chǔ)結(jié)構(gòu)（第1章 數(shù)據(jù)結(jié)構(gòu)，第3節(jié)）【目的要求】理解線性表的意義，搞清線性表的順序存儲(chǔ)結(jié)構(gòu)，掌握線性表插入與刪除操作的算法，并能用C程序編程實(shí)現(xiàn)?！窘虒W(xué)重點(diǎn)】線性表的概念，線性表順序存儲(chǔ)結(jié)構(gòu)，插入運(yùn)算，刪除運(yùn)算【教學(xué)難點(diǎn)】插入去處，刪除運(yùn)算【方法與手

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

17、i就是相應(yīng)的數(shù)據(jù)元素（結(jié)點(diǎn)）（線性表也可以是一個(gè)空表）4、線性表的特點(diǎn)是一種線性結(jié)構(gòu)，元素在表中的位置由其序號(hào)決定，元素之間的相對(duì)位置是線性的。對(duì)于非空的線性表，具有如下特點(diǎn)：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）有且只有一個(gè)終端結(jié)點(diǎn)；（3）內(nèi)部結(jié)點(diǎn)有且只有一個(gè)前件，有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。結(jié)點(diǎn)個(gè)數(shù)為0的線性表，稱為空表。二、線性表的順序存儲(chǔ)結(jié)構(gòu)（P16）1、線性表通常采用順序存儲(chǔ)的方法來(lái)存儲(chǔ)各個(gè)元素。（這種方法又叫順序分配）2、順序存儲(chǔ)的特點(diǎn)（1）所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）在存儲(chǔ)空間中各元素是按邏輯順序依次存放。（線性表中的前后件兩個(gè)元素在存儲(chǔ)空間中是緊

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

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

20、18）2、刪除元素基本規(guī)則一般情況下，要?jiǎng)h除第i（1in）個(gè)元素時(shí)，就要從第i+1個(gè)元素開(kāi)始，直到第n個(gè)元素之間共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。3、具體應(yīng)用定義一個(gè)有10個(gè)元素的一維數(shù)組，并輸入數(shù)據(jù)，然后刪除第n個(gè)元素，其中元素位置n從鍵盤(pán)輸入。4、說(shuō)明一個(gè)線性表，執(zhí)行一次刪除操作后，線性表的長(zhǎng)度減小1?！窘虒W(xué)課題】棧和隊(duì)列（第1章 數(shù)據(jù)結(jié)構(gòu)，第4節(jié)）【目的要求】理解棧的意義，搞清棧的存儲(chǔ)方式，掌握入棧與退棧運(yùn)算，理解隊(duì)列的意義與特點(diǎn)，搞清隊(duì)頭與隊(duì)尾指針的移動(dòng)，掌握循環(huán)隊(duì)列的特點(diǎn)?！窘虒W(xué)重點(diǎn)】棧的概念，存儲(chǔ)方式，入棧與退棧，隊(duì)列的概念，隊(duì)列指針的移動(dòng)，循環(huán)隊(duì)列【教學(xué)難點(diǎn)】入棧與退棧運(yùn)算，隊(duì)

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

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

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

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

25、ear）加1，然后將新的元素放入到隊(duì)尾指針指向的位置。（圖1.12 c）退隊(duì)運(yùn)算：從隊(duì)列的排頭刪除一個(gè)元素。具體操作：先將隊(duì)頭指針（front）加1,然后將指針?biāo)赶虻脑氐闹蒂x給一指定的變量。（圖1.12 b）（5）隊(duì)列的順序存儲(chǔ)在程序設(shè)計(jì)中，通常定義一維數(shù)組作為隊(duì)列的順序存儲(chǔ)空間。2、循環(huán)隊(duì)列及其運(yùn)算（P22）（1）概念所謂循環(huán)隊(duì)列就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。（循環(huán)隊(duì)列的環(huán)形表示如右圖所示）（2）指針的指向循環(huán)隊(duì)列中常用隊(duì)尾指針指向隊(duì)列的隊(duì)尾元素，隊(duì)頭指針指向指向排頭元素的前一個(gè)位置。（頭尾指針之間的所有元素為隊(duì)列的元素，據(jù)此可以計(jì)

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

27、（第1章 數(shù)據(jù)結(jié)構(gòu)，第5節(jié)）【目的要求】理解線性表的不足，搞清鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，掌握線性鏈表的插入與刪除運(yùn)算，理解循環(huán)列表的特點(diǎn)?！窘虒W(xué)重點(diǎn)】線性表的缺點(diǎn)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其特點(diǎn)，線性鏈表的特點(diǎn)，線性表的插入與刪除運(yùn)算，循環(huán)列表及其特點(diǎn)?！窘虒W(xué)難點(diǎn)】鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的理解，線性鏈表的插入與刪除運(yùn)算，循環(huán)列表的特點(diǎn)【方法與手段】講授+多媒體演示【作業(yè)布置】1、什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，有什么特點(diǎn)？2、簡(jiǎn)述在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入一個(gè)新元素b的過(guò)程，要求有圖示和文字描述。3、簡(jiǎn)述在線性鏈表中刪除包含元素x的結(jié)點(diǎn)p的過(guò)程，要求有圖示和文字描述。4、循環(huán)鏈表有什么特點(diǎn)？ 1.5 線性鏈表一、線性鏈表

28、的基本概念（P24）1、線性表順序存儲(chǔ)的優(yōu)缺點(diǎn)（1）優(yōu)點(diǎn)結(jié)構(gòu)簡(jiǎn)單，運(yùn)算方便，適應(yīng)于長(zhǎng)度不大且固定的線性數(shù)據(jù)（2）缺點(diǎn)A、工作量大：插入或刪除元素時(shí)，為保證運(yùn)算后仍為順序存儲(chǔ)，需移動(dòng)大量的數(shù)據(jù)；B、空間不便于擴(kuò)充：容易出現(xiàn)“上溢”錯(cuò)誤；C、不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配：要用多個(gè)線性表時(shí)，如果平均分配空間，會(huì)出現(xiàn)用不著或不夠用的現(xiàn)象；常用的方法就是共享整個(gè)存儲(chǔ)空間，對(duì)某個(gè)線性表動(dòng)態(tài)分配存儲(chǔ)空間，那么勢(shì)必在分配空間前必須將上次使用空間的線性表元素移開(kāi)，這就導(dǎo)致工作量劇增。2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（1）概述用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，其中存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)（NODE），每個(gè)結(jié)點(diǎn)由兩部分組

29、成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，一部分用于存放指針，稱為指針域，指針域中的指針總是指向該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)或后一個(gè)結(jié)點(diǎn)（即前件或后件）。（其中的“任意”主要是指各結(jié)點(diǎn)的位置可以連續(xù)也可以不連續(xù)，不同于順序結(jié)構(gòu)各結(jié)點(diǎn)必須連續(xù)存放）（具體形式如圖1.16所示）（2）特點(diǎn)存儲(chǔ)空間可以連續(xù)也可以不連續(xù)，各結(jié)點(diǎn)的存儲(chǔ)順序與邏輯關(guān)系可以不一致，其邏輯關(guān)系由指針域來(lái)確定。（圖1.15與1.17代表連續(xù)存儲(chǔ)的線性鏈表，圖1.18代表不連續(xù)存儲(chǔ)的線性鏈表）（3）說(shuō)明鏈?zhǔn)酱鎯?chǔ)可以表示線性結(jié)構(gòu)也可以表示非線性結(jié)構(gòu)。3、線性鏈表（P25）（1）概念線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。系統(tǒng)為線性表的每個(gè)元素劃分占

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

31、（圖1.19所示）；F、程序中，通常利用結(jié)構(gòu)體變量來(lái)構(gòu)造鏈表。4、帶鏈的棧（又稱為可利用棧）（P26）（1）帶鏈的棧的表示（圖1.20）（2）作用：可利用棧常用來(lái)收集存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)。當(dāng)需要存儲(chǔ)結(jié)點(diǎn)時(shí)，即從可利用的棧的頂部取出棧頂結(jié)點(diǎn)；當(dāng)系統(tǒng)要釋放一個(gè)存儲(chǔ)結(jié)點(diǎn)時(shí)，將該結(jié)點(diǎn)空間放回到可利用棧的棧頂。存儲(chǔ)結(jié)點(diǎn)的入棧如圖1.21 a所示，出棧操作如圖1.21 b所示，都在棧頂進(jìn)行。5、帶鏈的隊(duì)列（P27）（1）帶鏈的隊(duì)列的表示（圖1.22 a所示）（2）結(jié)點(diǎn)的插入和刪除：插入運(yùn)算如圖1.22 b，在隊(duì)尾進(jìn)行；刪除運(yùn)算如圖1.22 c所示，在隊(duì)頭進(jìn)行。二、線性鏈表的基本運(yùn)算（P27）1、基

32、本運(yùn)算（1）在鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素（2）在鏈表中刪除包含指定元素的結(jié)點(diǎn)（3）將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表（4）將一個(gè)線性鏈表按要求進(jìn)行分解（5）逆轉(zhuǎn)線性鏈表（6）復(fù)制線性鏈表（7）線性鏈表的排序（8）線性鏈表的查找2、查找指定元素查找元素X的方法：從頭指針指向的結(jié)點(diǎn)開(kāi)始往后沿指針進(jìn)行掃描，直到后面已沒(méi)有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閄為止。查找元素X的作用：元素的查找，經(jīng)常是為了進(jìn)行插入或刪除操作而進(jìn)行的。（在查找時(shí)，往往是需要記錄下該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)）3、插入元素（1）線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中插入一個(gè)新元素。（2）例如：在線性鏈表中包含元素x的結(jié)

33、點(diǎn)之前插入新元素b。步驟如下（圖1.23所示）：A、從可利用棧中取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p，即取得的結(jié)點(diǎn)的存儲(chǔ)序號(hào)存放在變量p中。并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲。B、在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為q。C、將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后。具體的操作：使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)；同時(shí)使結(jié)點(diǎn)q指向結(jié)點(diǎn)p。（上述操作，實(shí)際就是結(jié)點(diǎn)指向發(fā)生改變，具體操作時(shí)就是更改相應(yīng)結(jié)點(diǎn)指針域的值）（3）優(yōu)點(diǎn)線性鏈表的插入操作，新結(jié)點(diǎn)是為來(lái)自于可利用棧，因此不會(huì)造成線性表的溢出。同樣，由于可利用?？杀欢鄠€(gè)線性表利用，因此，不會(huì)造成存儲(chǔ)空間的浪費(fèi)，大家動(dòng)態(tài)地共同使用存儲(chǔ)空間。4、刪除元素（P

34、30）（1）線性鏈表的刪除是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。（2）例如：在線性鏈表中刪除包含元素x的結(jié)點(diǎn)。步驟如下（圖1.24）：A、在線性表中找到結(jié)點(diǎn)p(包含指定元素x)的前一個(gè)結(jié)點(diǎn)q；B、將結(jié)點(diǎn)p從線性鏈表中刪除，即讓結(jié)點(diǎn)q的指針指向p的后繼結(jié)點(diǎn)；C、將刪除的結(jié)點(diǎn)p送回可利用棧,即讓p指向棧頂元素而成為新的棧頂元素。（上述操作，實(shí)際就是結(jié)點(diǎn)指向發(fā)生改變，具體操作時(shí)就是更改相應(yīng)結(jié)點(diǎn)指針域的值）（3）優(yōu)點(diǎn)刪除一個(gè)指定的元素，不需要移動(dòng)其他的元素即可實(shí)現(xiàn)，這是順序存儲(chǔ)的線性表所不能實(shí)現(xiàn)的。同時(shí)，被刪除的結(jié)點(diǎn)可被用來(lái)存放其他數(shù)據(jù)，從而更有效地利用計(jì)算機(jī)的存儲(chǔ)空間。三、循環(huán)鏈表及

35、其基本運(yùn)算（P30）1、線性鏈表的缺點(diǎn)空表與非空表的運(yùn)算不統(tǒng)一（如：插入一個(gè)新的元素）2、循環(huán)鏈表（Circular Linked List）的特點(diǎn)（1）在循環(huán)鏈表中增加一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來(lái)設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。（2）循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空的，而是指向表頭結(jié)點(diǎn)。在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成一個(gè)環(huán)狀鏈。（圖1.25所示）3、說(shuō)明（1）空的線性鏈表沒(méi)有一個(gè)結(jié)點(diǎn)，而空的循環(huán)鏈表有一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域值任意，指針域指向表頭結(jié)點(diǎn)本身，和頭指針（HEAD）相同（圖1.25 b所示）；（嚴(yán)格上說(shuō)循環(huán)列表不存在空表）（2

36、）循環(huán)列表中，只要給任何一個(gè)結(jié)點(diǎn)的位置，均可以從它開(kāi)始掃描到所有的結(jié)點(diǎn)，而線性鏈表做不到，線性鏈表是一種單向的鏈表，只能按照指針的方向進(jìn)行掃描；（2）循環(huán)列表的空表與非空表運(yùn)算統(tǒng)一?！窘虒W(xué)課題】樹(shù)和二叉樹(shù)（第1章 數(shù)據(jù)結(jié)構(gòu)，第6節(jié)）【目的要求】理解樹(shù)的概念，掌握其基本的術(shù)語(yǔ)和特點(diǎn)，掌握二叉樹(shù)的概念和特點(diǎn)，了解其存儲(chǔ)結(jié)構(gòu)，掌握二叉樹(shù)的遍歷?！窘虒W(xué)重點(diǎn)】樹(shù)的概念和特點(diǎn)，二叉樹(shù)與滿二叉樹(shù)、完全二叉樹(shù)，二叉樹(shù)的存儲(chǔ)，二叉樹(shù)的遍歷【教學(xué)難點(diǎn)】二叉樹(shù)的性質(zhì)，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的遍歷【方法與手段】講授+多媒體演示【作業(yè)布置】1、什么是樹(shù)，樹(shù)有什么特點(diǎn)？2、二叉樹(shù)有什么特點(diǎn)？并寫(xiě)出二叉樹(shù)的基本性質(zhì)。3、

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

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

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

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

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

42、編號(hào)為k（k=1,2,n）的結(jié)點(diǎn)有如下結(jié)論： 若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。 若2kn，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（當(dāng)然也沒(méi)有右子結(jié)點(diǎn)） 若2k+1n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）（P36）1、概述：（1）存儲(chǔ)形式：常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（2）構(gòu)成：數(shù)據(jù)域：存放結(jié)點(diǎn)的數(shù)據(jù)值。左子針域：存儲(chǔ)該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)位置指針域：右指針域：存儲(chǔ)該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)位置第i個(gè)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如下：LchildValueRchild

43、iL(i)V(i)R(i)（3）說(shuō)明：二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉樹(shù)的鏈表，簡(jiǎn)稱二叉鏈表。在二叉樹(shù)在存儲(chǔ)中，用一個(gè)頭指針（BT）指向二叉樹(shù)的根結(jié)點(diǎn)的存儲(chǔ)位置。2、舉例ABCDEFGHIJKLMNOPQR有如下圖所示的二叉樹(shù)（按層次將所有結(jié)點(diǎn)順序編號(hào)）：A1B2C3D4E5F6G7H8I9J10K11L12M13N14O15P16Q17R18BT其二叉鏈表的邏輯狀態(tài)如下圖所示（BT為二叉鏈表的頭指針，指向二叉樹(shù)的根結(jié)點(diǎn)，字母后的數(shù)字為結(jié)點(diǎn)的序號(hào)）：其二叉鏈表的物理狀態(tài)如下圖所示：iL(i)V(i)R(i)BTà12A324B536C748D9510E11612F13714G15816

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

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