《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言描述)》教學(xué)課件匯總完整版電子教案全書(shū)整套課件幻燈片(最新)

1、21世紀(jì)高等院校規(guī)劃教材數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）第一章 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的意義學(xué)習(xí)重點(diǎn)掌握學(xué)習(xí)本課程的意義掌握本課程的主體框架和討論范圍掌握如何對(duì)算法進(jìn)行描述和分析引入： 一般情況下，用計(jì)算機(jī)解決一個(gè)實(shí)際問(wèn)題時(shí)，都是先對(duì)具體問(wèn)題抽象，建立問(wèn)題的求解模型，然后設(shè)計(jì)相應(yīng)的算法，編寫(xiě)程序并上機(jī)調(diào)試，最后解決問(wèn)題。 1.1 實(shí)例：高校選修課程管理1.2 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容1.3 算法和算法分析本章總結(jié)1.1 實(shí)例：高校選修課程管理1.1.1 問(wèn)題描述1.1.2 問(wèn)題的分析1.1.3 學(xué)習(xí)本課程的意義1.1.1 問(wèn)題描述 表1-1是一所學(xué)校學(xué)生選修課程的選修情況登記表。要求用計(jì)算機(jī)來(lái)完成對(duì)學(xué)生選修課程的全

2、程管理。 通常必備的功能有登記，修改、查詢(xún)和打印等。在本例中重點(diǎn)完成查詢(xún)功能。 學(xué)號(hào)姓名系別選修課程名學(xué)分成績(jī)課程名課程代碼等級(jí)分?jǐn)?shù)0351103王杰計(jì)算機(jī)攝影技術(shù)50130351212李麗計(jì)算機(jī)電腦音樂(lè)50210351220商立計(jì)算機(jī)攝影技術(shù)50130432233趙燕機(jī)械三維動(dòng)畫(huà)30320432118張欣機(jī)械三維動(dòng)畫(huà)30320322140王芳材料證券投資2053表1-1 某學(xué)校學(xué)生選修課程情況登記表 1.1.2 問(wèn)題的分析 利用計(jì)算機(jī)解決實(shí)際問(wèn)題的步驟：第一步：從具體問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)據(jù)模型。 第二步：進(jìn)行算法設(shè)計(jì)。 第三步：實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型定義，即從編程語(yǔ)言的角度確定抽象數(shù)據(jù)類(lèi)型的存儲(chǔ)

3、形式和確定抽象數(shù)據(jù)類(lèi)型中每一種操作的具體實(shí)現(xiàn)算法。 第四步：編制相應(yīng)的程序代碼并進(jìn)行調(diào)試。 第一步：抽象數(shù)據(jù)模型一般包括三部分：處理的數(shù)據(jù)對(duì)象、對(duì)象間的關(guān)系和需要實(shí)現(xiàn)的操作。常用以下格式描述：ADT 選修課程 數(shù)據(jù)對(duì)象：D=ai | ai記錄類(lèi)型，i=1,2,n , n0 數(shù)據(jù)關(guān)系：R=Ri | Ri記錄間關(guān)系，i=1,2,m , m0 基本操作： DengjiList ( &L) 完成功能：對(duì)學(xué)生選修情況進(jìn)行登記 EditList(&L) 完成功能：對(duì)選修情況登記表進(jìn)行修改 LocateList(&L,查詢(xún)條件) 完成功能：根據(jù)給定的查詢(xún)條件，從登記表中查找滿(mǎn)足條件的記錄 PrintList

4、(L) 完成功能：打印學(xué)生選修情況登記表 ADT選修課程第二步：根據(jù)上面給定的抽象數(shù)據(jù)類(lèi)型定義，寫(xiě)出實(shí)現(xiàn)各種操作的算法描述。下面以查詢(xún)操作為例給出偽代碼表示：int LocateList( 選修課程 &L, 查詢(xún)條件) 對(duì)給定的查詢(xún)條件進(jìn)行分析，確定是對(duì)表中哪個(gè)數(shù)據(jù)項(xiàng)進(jìn)行查詢(xún)； 對(duì)表中元素按給定的查詢(xún)條件進(jìn)行查詢(xún)； 若查詢(xún)成功，返回記錄的位置；否則返回0值，表示表中不存在滿(mǎn)足給定條件的記錄；第三步：確定表中的記錄的類(lèi)型（結(jié)構(gòu)體），表在內(nèi)存中存儲(chǔ)方式（按輸入順序存放）。具體定義如下：struct kechengsrtuct /選修課程名類(lèi)型定義char *kechengming ; / 課程名i

5、nt kechengdaima ; / 課程代碼 ;struct chengjistruct / 成績(jī)類(lèi)型定義char *dengji ; / 成績(jī)等級(jí)int fenshu ; / 分?jǐn)?shù) ;struct student / 表中學(xué)生記錄類(lèi)型定義long int num ; / 學(xué)號(hào)char *name ; / 姓名char *xibie ; / 系別kechengstruct kechent ;int xuefen ; / 學(xué)分chengjistruct chengji ; ;表在內(nèi)存中的存儲(chǔ)類(lèi)型定義：struct sqlist student *A ; / 將記錄順序存放在一個(gè)一維數(shù)組中in

6、t len ; / 表中記錄的個(gè)數(shù) ; 結(jié)論： 數(shù)據(jù)結(jié)構(gòu)的實(shí)質(zhì)就是一門(mén)研究非數(shù)值計(jì)算問(wèn)題的程序設(shè)計(jì)中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算操作的一門(mén)學(xué)科。 1.1.3 學(xué)習(xí)本課程的意義 數(shù)據(jù)結(jié)構(gòu)作為一門(mén)獨(dú)立的課程在國(guó)外是從1968年開(kāi)始設(shè)立的 。瑞士著名計(jì)算機(jī)科學(xué)家N.Wirth提出的著名公式“程序=算法+數(shù)據(jù)結(jié)構(gòu)”。數(shù)據(jù)結(jié)構(gòu)是一門(mén)介于數(shù)學(xué)、計(jì)算機(jī)硬件和軟件三者之間的核心課程。 用一句話(huà)概括：本課程就是從實(shí)際問(wèn)題抽象出數(shù)據(jù)類(lèi)型的手段。主要研究計(jì)算機(jī)所處理的數(shù)據(jù)對(duì)象、對(duì)象間存在的關(guān)系及進(jìn)行的各種操作。 1.2 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容 1.2.1 基本概念和術(shù)語(yǔ) 1.2.2 數(shù)據(jù)結(jié)構(gòu)定義 1.2.3

7、 邏輯結(jié)構(gòu)的表示方法 1.2.1 基本概念和術(shù)語(yǔ) 數(shù)據(jù)是對(duì)客觀(guān)事物的符號(hào)表示，是一種信息的載體，是所有能輸入到計(jì)算機(jī)中并被識(shí)別、存儲(chǔ)和加以處理的信息的總稱(chēng)。 數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成 。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 數(shù)據(jù)類(lèi)型是對(duì)計(jì)算機(jī)中表示的數(shù)據(jù)對(duì)象、對(duì)象特征及該數(shù)據(jù)對(duì)象上的一組操作的描述。抽象數(shù)據(jù)類(lèi)型是指一個(gè)數(shù)學(xué)模型及定義在該數(shù)學(xué)模型上的一組操作。定義取決于它的邏輯特性，與其在計(jì)算機(jī)內(nèi)部如何表示（存儲(chǔ)）和實(shí)現(xiàn)無(wú)關(guān)。 1.2.2 數(shù)據(jù)結(jié)構(gòu)定義 數(shù)據(jù)結(jié)構(gòu)是指相互間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 數(shù)據(jù)具有相同屬性的數(shù)據(jù)元素的

8、集合； 結(jié)構(gòu)數(shù)據(jù)元素間存在的一種或多種關(guān)系。對(duì)一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)進(jìn)行分析時(shí)，一般從它的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及對(duì)數(shù)據(jù)元素所進(jìn)行的操作三個(gè)方面進(jìn)行討論。（本課程的主要討論點(diǎn)） 邏輯結(jié)構(gòu)是對(duì)給定數(shù)據(jù)結(jié)構(gòu)的一種描述方式，是從實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)模型。主要描述數(shù)據(jù)元素，及元素之間存在的邏輯關(guān)系。 通常按元素間存在的邏輯關(guān)系的不同特征，將數(shù)據(jù)結(jié)構(gòu)分為四類(lèi)： 集合結(jié)構(gòu) 線(xiàn)性結(jié)構(gòu) 樹(shù)型結(jié)構(gòu) 圖型結(jié)構(gòu)集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了同屬于一個(gè)集合之外，沒(méi)有其他關(guān)系的數(shù)據(jù)結(jié)構(gòu)。例子：從大街上隨意的找五個(gè)人組成一個(gè)小組，編號(hào)分別為1、2、3、4、5，則這五個(gè)人之間除了屬于同一組以外，相互間不存在任何的關(guān)系。 組成集合的數(shù)

9、據(jù)元素之間不存在任何的關(guān)系線(xiàn)性結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對(duì)一”線(xiàn)性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。學(xué)號(hào)姓名系別學(xué)分0351103王杰計(jì)算機(jī)30351212李麗計(jì)算機(jī)1例：學(xué)生基本情況登記表中每條學(xué)生記錄都按一定的順序排列，除了第一條和最后一條以外，每條記錄都只有唯一的前驅(qū)和后繼元素。元素之間是1：1關(guān)系，都只有唯一的前驅(qū)和唯一的后繼樹(shù)型結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對(duì)多”邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。例：一個(gè)大學(xué)的人事檔案管理。每個(gè)系有多個(gè)專(zhuān)業(yè)，但一個(gè)專(zhuān)業(yè)只能屬于一個(gè)系；一個(gè)專(zhuān)業(yè)有多名學(xué)生，但一個(gè)學(xué)生只能屬于一個(gè)專(zhuān)業(yè)元素之間的關(guān)系是1：n，每個(gè)元素都只有唯一的前驅(qū)元素，但可以有多個(gè)后繼元素圖型結(jié)構(gòu)：數(shù)據(jù)元素之間存在“多對(duì)多

10、”邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。例：五個(gè)城市間的交通圖。從1可以直達(dá)5，也可以經(jīng)過(guò)2、3到達(dá)5，或也可以經(jīng)過(guò)2、4到5。元素之間的關(guān)系是m:n，每個(gè)元素都可以有多個(gè)前驅(qū)元素和多個(gè)后繼元素 存儲(chǔ)結(jié)構(gòu)又稱(chēng)物理結(jié)構(gòu)，就是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方式。它包括數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式，還包括元素之間關(guān)系在內(nèi)存中的表示。 根據(jù)存儲(chǔ)空間的不同分配方式將數(shù)據(jù)結(jié)構(gòu)分為兩類(lèi)： 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)第一方面第二方面 順序存儲(chǔ)：所有元素存放在一片連續(xù)的存儲(chǔ)空間中，邏輯上相鄰的元素在內(nèi)存中的物理位置也是相鄰的。 注意：元素存放在連續(xù)的存儲(chǔ)空間中，元素之間的邏輯關(guān)系由在內(nèi)存中的物理位置來(lái)體現(xiàn)。 例：對(duì)一個(gè)由（1，2，3，4，5）

11、五個(gè)元素組成的數(shù)據(jù)結(jié)構(gòu)采用順序存儲(chǔ)，則內(nèi)存中的存儲(chǔ)示意圖如下所示：元素1元素2元素3元素4元素5起始地址 鏈?zhǔn)酱鎯?chǔ)：所有元素存放在可以不連續(xù)的存儲(chǔ)單元中，以結(jié)點(diǎn)的形式存在，每個(gè)結(jié)點(diǎn)除了保存數(shù)據(jù)元素信息外，還通過(guò)指針來(lái)保存元素之間的關(guān)系。 注意：既元素存儲(chǔ)在不連續(xù)的存儲(chǔ)單元中，元素間的關(guān)系通過(guò)結(jié)點(diǎn)中的指針信息來(lái)體現(xiàn)。 元素1元素4元素3元素2例：對(duì)一個(gè)由（1，2，3，4）四個(gè)元素組成的數(shù)據(jù)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)，則內(nèi)存中的存儲(chǔ)示意圖如下所示：1.2.3 邏輯結(jié)構(gòu)的表示方法 二元組表示法表示形式為： D=（K，R）其中，K=a1 , a2 , , an ，為數(shù)據(jù)元素的集合 R=r1 , r2 , , r

12、 m ，為元素之間關(guān)系的集合 r1= | 其中，x,yK 序偶表示：元素x和元素y之間存在關(guān)系，并且稱(chēng)元素x為元素y的前驅(qū)，元素y為元素x的后繼。如果元素x既是元素y的前驅(qū)，也是元素y的后繼，既且，則用（x,y）形式表示。圖形表示法 用圓圈來(lái)代表數(shù)據(jù)元素，用帶箭頭的連線(xiàn)來(lái)表示元素之間的關(guān)系，如圖所示。二元組表示法：D1=( K , R ) 其中，K=a,b,c,d,e R=r r = , , , 1.3 算法和算法分析 1.3.1 算法定義 1.3.2 算法分析 1.3.1 算法定義 算法是對(duì)特定問(wèn)題求解步驟的一種描述，是一組指令的有限序列，其中每一條指令都代表解題過(guò)程中的一個(gè)或者多個(gè)操作。算

13、法特點(diǎn)： 有窮性、確定性、可行性、輸入、輸出算法描述可以有多種方式，如：用流程圖描述、用自然語(yǔ)言描述、還可用數(shù)學(xué)語(yǔ)言或特定的符號(hào)進(jìn)行描述。本書(shū)中所有算法都是用C語(yǔ)言來(lái)進(jìn)行描述 。1.3.2 算法分析 算法的設(shè)計(jì)要求如下： 正確性 可讀性 健壯性 效率與低存儲(chǔ)量的需求 其中，效率指的是算法執(zhí)行的時(shí)間。存儲(chǔ)量需求指的是算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間，通常主要考慮算法所需的輔助存儲(chǔ)空間。 這四個(gè)設(shè)計(jì)要求中最主要的是算法的執(zhí)行時(shí)間和執(zhí)行時(shí)所占的存儲(chǔ)空間大小。 算法的執(zhí)行時(shí)間是指一個(gè)算法在計(jì)算機(jī)上運(yùn)行時(shí)所花費(fèi)的時(shí)間。 =簡(jiǎn)單操作所需要的時(shí)間簡(jiǎn)單操作的次數(shù)影響算法執(zhí)行時(shí)間的兩個(gè)因素： （1）每個(gè)簡(jiǎn)單操

14、作執(zhí)行時(shí)所需時(shí)間與機(jī)器有關(guān)，而與算法無(wú)關(guān)。討論算法中包含的簡(jiǎn)單操作的執(zhí)行次數(shù)。 （2）另外一個(gè)與算法的執(zhí)行時(shí)間相關(guān)的是問(wèn)題的規(guī)模。 通常算法的執(zhí)行時(shí)間用時(shí)間復(fù)雜度表示： T(n) = O( f ( n ) ) 其中，n為問(wèn)題的規(guī)模 T（n）為時(shí)間復(fù)雜度 此式子表示，隨著問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同。所以只要求出簡(jiǎn)單操作的次數(shù)關(guān)于n的增長(zhǎng)率即可，然后用n的最高數(shù)量級(jí)來(lái)表示算法的時(shí)間復(fù)雜度。 例： for (j=1;j=n;j+) for (k=1;k=m;k+) +x; s+=x; 分析：各個(gè)簡(jiǎn)單操作的執(zhí)行次數(shù)如下所示：for (j=1;j=n;j+)/次數(shù)為1+

15、（n+1）+nfor (k=1;k=n;k+) /執(zhí)行次數(shù)為（1+（n+1）+n）n +x; /執(zhí)行次數(shù)為n*n s+=x; /執(zhí)行次數(shù)為n*n 簡(jiǎn)單操作的執(zhí)行次數(shù)之和為：4n2+4n+2，用n的最高數(shù)量級(jí)表示，時(shí)間復(fù)雜度為：O（n2）。衡量一個(gè)算法性能的另一個(gè)標(biāo)準(zhǔn)就是算法執(zhí)行時(shí)所占的存儲(chǔ)空間的大小。一般一個(gè)算法所占的存儲(chǔ)空間包括存儲(chǔ)算法所占用的存儲(chǔ)空間、算法的輸入/輸出數(shù)據(jù)所占用的存儲(chǔ)空間和程序運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間這三個(gè)方面。其中，只有算法執(zhí)行過(guò)程中所占的臨時(shí)空間與算法有著密切關(guān)系。 通常一個(gè)算法在執(zhí)行過(guò)程中所占用的臨時(shí)存儲(chǔ)空間的大小由空間復(fù)雜度來(lái)衡量，記作： S（n）= O（f（n

16、） 其中，n為問(wèn)題的規(guī)模；S（n）為空間復(fù)雜度。通常用n的最高數(shù)量級(jí)來(lái)表示。 本章總結(jié)：本章介紹了學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的意義、本課程的主題框架及相關(guān)內(nèi)容和如何對(duì)算法進(jìn)行評(píng)價(jià)。 數(shù)據(jù)結(jié)構(gòu)主要研究計(jì)算機(jī)所處理的數(shù)據(jù)對(duì)象、對(duì)象之間存在的各種關(guān)系及進(jìn)行的各種操作，是用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題與編寫(xiě)相應(yīng)程序兩者之間的紐帶。數(shù)據(jù)結(jié)構(gòu)從定義上可以理解為數(shù)據(jù)+結(jié)構(gòu)。其中，數(shù)據(jù)指的是所要處理的若干個(gè)數(shù)據(jù)元素的集合；結(jié)構(gòu)指的是數(shù)據(jù)元素之間的關(guān)系。按邏輯結(jié)構(gòu)可分為集合結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖型結(jié)構(gòu)四種。按存儲(chǔ)結(jié)構(gòu)可分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種。 算法是解決問(wèn)題步驟的一種描述，它有有窮性、確定性、可行性、輸入和輸出等五個(gè)特

17、點(diǎn)。 一個(gè)好的算法應(yīng)該滿(mǎn)足正確性、可讀性、健壯性和效率與低存儲(chǔ)量需求等四個(gè)要求，其中算法的執(zhí)行效率和低存儲(chǔ)量需求是衡量一個(gè)算法的最主要的標(biāo)準(zhǔn)。通常用時(shí)間復(fù)雜度來(lái)衡量算法的執(zhí)行時(shí)間，用空間復(fù)雜度來(lái)衡量算法執(zhí)行過(guò)程中所占用的臨時(shí)存儲(chǔ)空間的大小。它們都是問(wèn)題的規(guī)模n的一個(gè)函數(shù)，所以用n的最高數(shù)量級(jí)來(lái)表示。 第5章 數(shù)組數(shù)組的基本概念和存儲(chǔ)結(jié)構(gòu)稀疏矩陣的定義、表示方法、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)算法特殊矩陣的存儲(chǔ)廣義表的定義、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，以及相應(yīng)操作的實(shí)現(xiàn)算法。 第5章 數(shù)組 5.1 數(shù)組 5.2 數(shù)學(xué)中的應(yīng)用 5.3 廣義表 本章總結(jié)5.1 數(shù)組 5.1.1 一維數(shù)組 5.1.2 多維數(shù)組 5.1.

18、1 一維數(shù)組 一維數(shù)組在數(shù)組結(jié)構(gòu)中可以看成是一個(gè)線(xiàn)性表或一個(gè)向量，通常分配一塊連續(xù)的存儲(chǔ)單元。在C語(yǔ)言中，一維數(shù)組a n 的存儲(chǔ)單元是從a 0 至an1的一塊連續(xù)的存儲(chǔ)空間，設(shè)a 0 的存儲(chǔ)地址LOC（a 0 ），數(shù)據(jù)元素所占的存儲(chǔ)單元為k個(gè)字節(jié)，則任一元素a i 的首字節(jié)地址LOC（a i ）： LOC（a i ）= LOC（a 0 ）+ i * k (0in) 5.1.2 多維數(shù)組 多維數(shù)組的定義：1 行向量形式Amn=A，則A = （a0，a1，ai，am1）一維數(shù)組其中，aj =（aj, 0，aj, 1，aj, n-1）（0jm）是一個(gè)行向量形式的線(xiàn)性表。就是以行序?yàn)橹餍虻拇鎯?chǔ)方式。

19、2 列向量形式Amn=A，則A = （a0，a1，ai，an1），其中，ap =（a0, p，a1, p，am-1, p）(0pn)是一個(gè)列向量形式的線(xiàn)性表，如式子（5-3）所示。是以列序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)。 數(shù)組的存儲(chǔ)結(jié)構(gòu) 對(duì)于二維數(shù)組來(lái)說(shuō)，設(shè)數(shù)組的第一個(gè)元素a0, 0的地址LOC（a0, 0），每個(gè)元素所占的存儲(chǔ)單元為k，則二維數(shù)組中任一元素ai，j的存儲(chǔ)地址：LOC（ai , j）= LOC（a0 , 0）+（i * nj）* k n為列數(shù) n維數(shù)組ad1d2 dn的數(shù)據(jù)元素存儲(chǔ)位置的計(jì)算公式：5.2 數(shù)學(xué)中的應(yīng)用 5.2.1 稀疏矩陣 5.2.2 特殊矩陣 5.2.1 稀疏矩陣 稀疏矩陣

20、的概念 稀疏矩陣的三元組線(xiàn)性表表示 稀疏矩陣的順序存儲(chǔ)方式 稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)方式 稀疏矩陣各種操作的實(shí)現(xiàn) 稀疏矩陣的概念： 在一個(gè)階數(shù)較大的矩陣中非零元素個(gè)數(shù)s相對(duì)于矩陣元素的總個(gè)數(shù)t非常小，即 s sublist)+1 其它情況 實(shí)現(xiàn)算法： （略） 時(shí)間復(fù)雜度為O（n），其中n為廣義表中所有結(jié)點(diǎn)的個(gè)數(shù)。該算法的空間復(fù)雜度為O（m），m為廣義表的深度。建立廣義表 分析：建立廣義表過(guò)程可以通過(guò)遞歸實(shí)現(xiàn)。將廣義表分解成表頭和表尾，而表頭和表尾若仍是廣義表，則繼續(xù)分解為表頭和表尾。創(chuàng)建過(guò)程就是建立表頭和建立表尾。 區(qū)分表頭和表尾中的元素是單元素還是表元素的方法： （1）如果 i為“（）”，表示這是

21、一個(gè)空的表元素，字符串長(zhǎng)度為2； （2）如果 i長(zhǎng)度為1，表明它是一個(gè)單元素； （3）如果長(zhǎng)度1，這是一個(gè)表元素。 前兩種情況就可作為遞歸過(guò)程的結(jié)束條件。 實(shí)現(xiàn)算法： （略） 時(shí)間復(fù)雜度和空間復(fù)雜度：0（n），n廣義表中字符個(gè)數(shù)輸出廣義表 分析：設(shè)GL為表頭指針，則輸出時(shí)，需要對(duì)子表進(jìn)行遞歸調(diào)用。當(dāng)GL結(jié)點(diǎn)為表結(jié)點(diǎn)時(shí)，應(yīng)首先輸出作為一個(gè)表的起始符號(hào)“（”。然后再輸出以sublist為表頭指針的表；當(dāng)GL結(jié)點(diǎn)為原子結(jié)點(diǎn)時(shí)，則應(yīng)輸出該元素的值。當(dāng)以sublist為表頭指針的表輸出結(jié)束后，應(yīng)在其最后輸出一個(gè)作為表終止符的“）”。當(dāng)GL結(jié)點(diǎn)輸出結(jié)束后，若存在后繼結(jié)點(diǎn)，則應(yīng)首先輸出一個(gè)逗號(hào)作為分隔符，然

22、后再遞歸輸出由next指針?biāo)赶虻暮罄^表。 實(shí)現(xiàn)算法： （略） 時(shí)間復(fù)雜度和空間復(fù)雜度：0（n），n廣義表中結(jié)點(diǎn)個(gè)數(shù)。本章總結(jié)： 一維數(shù)組在內(nèi)存中開(kāi)辟一塊連續(xù)的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)，適合于隨機(jī)查找。多維數(shù)組可以看成是一維數(shù)組的推廣，也是一個(gè)線(xiàn)性表，表中的每個(gè)數(shù)據(jù)元素本身也是一個(gè)線(xiàn)性表。 稀疏矩陣是指非零元素個(gè)數(shù)相對(duì)于矩陣元素的總個(gè)數(shù)十分小的矩陣。稀疏矩陣的存儲(chǔ)方法有三種：第一種是三元組表示法，第二種是行邏輯鏈?zhǔn)酱鎯?chǔ)，第三種是十字鏈?zhǔn)酱鎯?chǔ)。稀疏矩陣的基本操作有五種，都采用了順序存儲(chǔ)方式。 特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。為了節(jié)省存儲(chǔ)空間可以對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)。 廣義表的元素分

23、為原子和子表，是一種遞歸結(jié)構(gòu)。表中所含元素的個(gè)數(shù)稱(chēng)為長(zhǎng)度。表中括號(hào)嵌套的最大次數(shù)稱(chēng)為深度。常用的基本操作有求廣義表的長(zhǎng)度、深度、創(chuàng)建和輸出廣義表等，操作的共同點(diǎn)是都通過(guò)遞歸實(shí)現(xiàn)。 第6章 樹(shù) 學(xué)習(xí)重點(diǎn)：樹(shù)和二叉樹(shù)的概念、性質(zhì)和相互間的轉(zhuǎn)換方法樹(shù)和二叉樹(shù)的遍歷方法和實(shí)現(xiàn)算法哈夫曼樹(shù)、線(xiàn)索二叉樹(shù)和二叉排序樹(shù)的構(gòu)造方法與應(yīng)用 第6章 樹(shù) 6.1 實(shí)例1：文件目錄管理 6.2 樹(shù)的邏輯結(jié)構(gòu)6.3 樹(shù)的遍歷 6.4 實(shí)例2：通信中電文編碼 6.5 二叉樹(shù)定義、存儲(chǔ)結(jié)構(gòu) 6.6 二叉樹(shù)遍歷 6.7 樹(shù)與二叉樹(shù)的轉(zhuǎn)換 6.8 應(yīng)用舉例 本章總結(jié) 6.1 實(shí)例1：文件目錄管理 6.1.1 問(wèn)題描述 6.1.2

24、 問(wèn)題的分析 6.1.3 實(shí)現(xiàn)算法6.1.1 問(wèn)題描述 在操作系統(tǒng)中對(duì)文件進(jìn)行訪(fǎng)問(wèn)時(shí)提供按名存取機(jī)制，只需給出文件名，就可以訪(fǎng)問(wèn)到相應(yīng)的文件，而無(wú)需知道文件的存儲(chǔ)位置。 如何實(shí)現(xiàn)按名存取機(jī)制呢？ 6.1.2 問(wèn)題的分析 文件系統(tǒng)將這些說(shuō)明部分的全部信息集中起來(lái)構(gòu)成文件控制塊（FCB），文件目錄由文件控制塊組成。再將所有的文件目錄組合在一起構(gòu)成一個(gè)目錄文件，目錄文件以樹(shù)型目錄結(jié)構(gòu)存儲(chǔ)。樹(shù)型目錄結(jié)構(gòu)中文件目錄的第一級(jí)系統(tǒng)目錄為樹(shù)的根結(jié)點(diǎn)，定義為根目錄，文件目錄的第二級(jí)和以下各級(jí)目錄均為樹(shù)的分支結(jié)點(diǎn)（非終結(jié)點(diǎn)），均定義為子目錄，只有樹(shù)的葉子結(jié)點(diǎn)（終結(jié)點(diǎn)）才為文件。所以實(shí)現(xiàn)文件的按名存取，就是從目錄結(jié)

25、構(gòu)的根目錄開(kāi)始直到所要找的文件為止 。6.1.3 實(shí)現(xiàn)算法 實(shí)現(xiàn)算法：（略）結(jié)論： 文件目錄結(jié)構(gòu)是一種樹(shù)型結(jié)構(gòu)，目錄樹(shù)中的根目錄是樹(shù)的根結(jié)點(diǎn)，根目錄下各級(jí)子目錄和文件是樹(shù)的其余結(jié)點(diǎn)。對(duì)處在同一層的各個(gè)子目錄和文件進(jìn)行比較可以發(fā)現(xiàn)各個(gè)子目錄和文件都只有一個(gè)共同的上一級(jí)目錄，而同一層的各個(gè)子目錄可以有任意多個(gè)下級(jí)子目錄和文件。 文件目錄結(jié)構(gòu)中的各個(gè)目錄和文件都滿(mǎn)足樹(shù)型結(jié)構(gòu)的特征。 6.2 樹(shù)的邏輯結(jié)構(gòu)6.2.1 樹(shù)的邏輯結(jié)構(gòu) 6.2.2 樹(shù)的相關(guān)術(shù)語(yǔ) 6.2.1 樹(shù)的邏輯結(jié)構(gòu) 樹(shù)或者是一棵空樹(shù)，或者是一棵非空樹(shù)。一棵非空樹(shù)由n（n0）個(gè)結(jié)點(diǎn)來(lái)組成。它滿(mǎn)足以下條件： l有且僅有一個(gè)根結(jié)點(diǎn)，它沒(méi)有前驅(qū)

26、結(jié)點(diǎn) l其余結(jié)點(diǎn)構(gòu)成m(m=0)棵互不相交的樹(shù)，稱(chēng)為該樹(shù)的子樹(shù)。每棵子樹(shù)又是一棵樹(shù)（遞歸定義）。 邏輯結(jié)構(gòu)：一棵樹(shù)由若干個(gè)結(jié)點(diǎn)組成，元素以結(jié)點(diǎn)的形式存在；關(guān)系：樹(shù)的各個(gè)結(jié)點(diǎn)間是一對(duì)多的關(guān)系，即除根結(jié)點(diǎn)外，所有結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，所有結(jié)點(diǎn)或者沒(méi)有后繼結(jié)點(diǎn)，或者有任意多個(gè)后繼結(jié)點(diǎn)。6.2.2 樹(shù)的相關(guān)術(shù)語(yǔ) 根結(jié)點(diǎn)：唯一沒(méi)有前驅(qū)的結(jié)點(diǎn)。所有非空樹(shù)，都有唯一的一個(gè)根結(jié)點(diǎn)。 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)，或者結(jié)點(diǎn)所擁有的后繼結(jié)點(diǎn)的個(gè)數(shù)。樹(shù)的度是指樹(shù)中所有結(jié)點(diǎn)的度的最大值。 終端結(jié)點(diǎn)（葉子結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)，或者樹(shù)中沒(méi)有后繼的結(jié)點(diǎn)。 非終端結(jié)點(diǎn)（分支結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)，或者指有后繼的結(jié)點(diǎn)。

27、 父結(jié)點(diǎn)、孩子結(jié)點(diǎn)：對(duì)一個(gè)結(jié)點(diǎn)來(lái)講，它的前驅(qū)結(jié)點(diǎn)是它的父結(jié)點(diǎn)（雙親結(jié)點(diǎn)）；它的后繼結(jié)點(diǎn)是它的孩子結(jié)點(diǎn)（子結(jié)點(diǎn)）。兄弟結(jié)點(diǎn)是指父結(jié)點(diǎn)相同的結(jié)點(diǎn)，即前驅(qū)結(jié)點(diǎn)是相同的結(jié)點(diǎn)。結(jié)點(diǎn)的深度是指該結(jié)點(diǎn)在樹(shù)中所處的層數(shù)，根結(jié)點(diǎn)所在的層為第一層。樹(shù)的深度是指樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。有序樹(shù)是指構(gòu)成樹(shù)的各子樹(shù)，從左到右有一定順序，不能互相交換的樹(shù)。無(wú)序樹(shù)是指構(gòu)成樹(shù)的各子樹(shù)是無(wú)順序的，可以互相交換的樹(shù)。森林是指若干棵互不相交的樹(shù)。 6.3 樹(shù)的遍歷 6.3.1 先根遍歷 6.3.2 后根遍歷 6.3.3 按層遍歷 樹(shù)的遍歷指的是按照某一種順序訪(fǎng)問(wèn)樹(shù)中的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)只訪(fǎng)問(wèn)一次。 樹(shù)的遍歷順序：先根遍歷（先序遍歷

28、）、后根遍歷（后序遍歷）和按層遍歷。6.3.1 先根遍歷先根遍歷指如果樹(shù)非空，則按下列規(guī)則進(jìn)行遍歷： l 先訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)。 l從左到右訪(fǎng)問(wèn)根結(jié)點(diǎn)的所有子樹(shù)。 l對(duì)子樹(shù)也按先根遍歷順序來(lái)訪(fǎng)問(wèn)所有的結(jié)點(diǎn)。 6.3.2 后根遍歷后根遍歷指如果樹(shù)非空，則按下列規(guī)則進(jìn)行遍歷： l 先從左到右訪(fǎng)問(wèn)根結(jié)點(diǎn)的所有子樹(shù)。 l 后訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)。 l 對(duì)子樹(shù)也按后根遍歷順序來(lái)訪(fǎng)問(wèn)所有的結(jié)點(diǎn)。 6.3.3 按層遍歷按層遍歷指如果樹(shù)非空，則按下列規(guī)則進(jìn)行遍歷： l 從第一層開(kāi)始，從上到下順序遍歷各層，同一層從左到右訪(fǎng)問(wèn)各個(gè)結(jié)點(diǎn)。 l 樹(shù)的根結(jié)點(diǎn)所在層定義為第一層，依次類(lèi)推。 6.4 實(shí)例2：通信中電文編碼 6.4.

29、1 問(wèn)題的描述 6.4.2 問(wèn)題的分析 6.4.3 實(shí)現(xiàn)算法 6.4.1 問(wèn)題的描述 在電信科技日新月異的今天，人們?cè)缫训?，曾?jīng)風(fēng)靡一時(shí)的電報(bào)。電報(bào)的原文發(fā)送時(shí)，都按一定的規(guī)則翻譯成編碼，以編碼的形式傳送。收到的電文中，每個(gè)文字的下面都會(huì)有一個(gè)數(shù)字編碼。下面介紹的也是一種電報(bào)的編碼方法：發(fā)送的電文翻譯成0和1的數(shù)字序列。 6.4.2 問(wèn)題的分析 電報(bào)主要依靠將傳送的文字轉(zhuǎn)換成由二進(jìn)制數(shù)組成的字符串進(jìn)行傳送。第一種解決方法：將所有傳送的文字都轉(zhuǎn)換成等長(zhǎng)的二進(jìn)制字符串來(lái)傳送，接收者只需按等長(zhǎng)進(jìn)行譯碼。第二種解決方法：對(duì)電文中出現(xiàn)的字符設(shè)計(jì)長(zhǎng)度不等的字符編碼，對(duì)電文中出現(xiàn)次數(shù)比較多的字符采用盡可

30、能短的字符編碼，則傳送的信息的長(zhǎng)度就可以減少了。 前綴編碼（哈夫曼編碼）：每個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴。 構(gòu)造字符哈夫曼編碼的方法： 將每個(gè)字符按在代碼中出現(xiàn)的次數(shù)為出現(xiàn)頻率，構(gòu)成一個(gè)頻率集合，然后畫(huà)一棵滿(mǎn)足以下條件的樹(shù)： l從頻率集合中，每次選擇出現(xiàn)頻率最小的兩個(gè)字符構(gòu)成一棵樹(shù)，所構(gòu)成樹(shù)的父結(jié)點(diǎn)的值等于這兩個(gè)字符的頻率之和。 l將選中的兩個(gè)字符的頻率從頻率集中刪除，并將它們的父結(jié)點(diǎn)加到頻率集合中。 重復(fù)上述兩個(gè)過(guò)程，直到頻率集合中只剩一個(gè)元素為止。 編碼規(guī)則：從樹(shù)的根結(jié)點(diǎn)起，左邊的孩子結(jié)點(diǎn)的編號(hào)為0，右邊的孩子結(jié)點(diǎn)的編號(hào)為1，對(duì)所有的子樹(shù)也按這個(gè)規(guī)則編碼。所畫(huà)的樹(shù)稱(chēng)之為哈夫曼樹(shù)

31、，頻率稱(chēng)之為權(quán)值。 6.4.3 實(shí)現(xiàn)算法 實(shí)現(xiàn)算法：（略）結(jié)論：哈夫曼樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，結(jié)點(diǎn)度的最大值為2，這種樹(shù)稱(chēng)為二叉樹(shù)，兩個(gè)孩子結(jié)點(diǎn)分別稱(chēng)為左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。6.5 二叉樹(shù)定義、存儲(chǔ)結(jié)構(gòu) 6.5.1 二叉樹(shù)的定義6.5.2 二叉樹(shù)的性質(zhì) 6.5.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 6.5.1 二叉樹(shù)的定義 二叉樹(shù)定義（遞歸定義）： 或者是一棵空二叉樹(shù)，或者是一棵非空二叉樹(shù)。一棵非空二叉樹(shù)由n（n0）個(gè)結(jié)點(diǎn)組成。它滿(mǎn)足以下條件： l有且僅有一個(gè)根結(jié)點(diǎn)，它沒(méi)有前驅(qū)結(jié)點(diǎn) l其余結(jié)點(diǎn)構(gòu)成兩棵互不相交的子樹(shù)，稱(chēng)為該樹(shù)的左子樹(shù)和右子樹(shù)。每棵子樹(shù)又是一棵二叉樹(shù)。 特點(diǎn)：每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)孩子

32、結(jié)點(diǎn)，也就是說(shuō)二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)。 Root (BT) 求根結(jié)點(diǎn)。ParentBT(BT,elem) 求父結(jié)點(diǎn)。LchildBT(BT,elem)和RchildBT(BT,elem)求左、右孩子結(jié)點(diǎn)。CreateBT(BT,R,n)創(chuàng)建一棵二叉樹(shù)。DepthBT(BT)求層數(shù)。PreOrdetBT(BT)先根遍歷。InOrdetBT(BT)中根遍歷。PostOrdetBT(BT)后根遍歷。 LeverOrdetBT(BT)按層遍歷。二叉樹(shù)的基本操作：6.5.2 二叉樹(shù)的性質(zhì) 性質(zhì)1：如果計(jì)二叉樹(shù)的根結(jié)點(diǎn)所在層為第一層，則第k層的結(jié)點(diǎn)數(shù)最多為2 k-1個(gè)。 性質(zhì)2：層數(shù)為k的二叉樹(shù)的最

33、大結(jié)點(diǎn)數(shù)為2 k-1個(gè)。 性質(zhì)3：在一個(gè)二叉樹(shù)中，度為0的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則n0=n2+1。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的層數(shù)為： 或 。 滿(mǎn)二叉樹(shù)是指層數(shù)為k的有2 k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)，既每層都保持它的最大結(jié)點(diǎn)數(shù)，每層結(jié)點(diǎn)都是滿(mǎn)的。 完全二叉樹(shù)是指如果一棵層數(shù)為k的n個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有結(jié)點(diǎn)都與層數(shù)為k的滿(mǎn)二叉樹(shù)中編號(hào)為1 n的結(jié)點(diǎn)一一對(duì)應(yīng)，則稱(chēng)此二叉樹(shù)為完全二叉樹(shù)。 性質(zhì)5：對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)來(lái)講，編號(hào)為i的結(jié)點(diǎn)滿(mǎn)足以下條件：（1）如果i=1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)父結(jié)點(diǎn)；如果i1，則父結(jié)點(diǎn)的編號(hào)是 。（2）如果2in，則結(jié)點(diǎn)i沒(méi)有左孩子結(jié)點(diǎn)的葉子

34、結(jié)點(diǎn)；否則其左孩子結(jié)點(diǎn)的編號(hào)是2i。（3）如果2i+1n，則結(jié)點(diǎn) i沒(méi)有右孩子結(jié)點(diǎn)；否則其右孩子結(jié)點(diǎn)的編號(hào)是2i+1 。 6.5.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 存在兩種存儲(chǔ)方式： 順序存儲(chǔ)方式 鏈?zhǔn)酱鎯?chǔ)方式 用一組連續(xù)的存儲(chǔ)空間來(lái)存放一棵二叉樹(shù)的所有結(jié)點(diǎn)。結(jié)點(diǎn)存放時(shí)對(duì)二叉樹(shù)中的所有結(jié)點(diǎn)都按滿(mǎn)二叉樹(shù)中結(jié)點(diǎn)編號(hào)來(lái)順序編號(hào)，將編號(hào)當(dāng)成存儲(chǔ)結(jié)點(diǎn)的數(shù)組元素的下標(biāo)來(lái)處理。順序存儲(chǔ)方式： 指存儲(chǔ)二叉樹(shù)中的全部結(jié)點(diǎn)信息及結(jié)點(diǎn)間的關(guān)系。結(jié)點(diǎn)間的關(guān)系通常有兩種：一種是左右孩子結(jié)點(diǎn)的關(guān)系，另一種是父結(jié)點(diǎn)的關(guān)系。 二叉鏈表存儲(chǔ)方式：每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)元素的信息外，還存儲(chǔ)該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)的信息。（常用存儲(chǔ)方式） 三叉鏈

35、表存儲(chǔ)方式：在二叉鏈表的基礎(chǔ)上，在結(jié)點(diǎn)中再增加一個(gè)存放該結(jié)點(diǎn)的父結(jié)點(diǎn)信息的指針域。鏈?zhǔn)酱鎯?chǔ)方式：typedef struct Btnode Elemtype data ; / 存儲(chǔ)二叉樹(shù)結(jié)點(diǎn)元素的信息 Btnode *lchild ; / 存儲(chǔ)該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的信息 Btnode *rchild ; / 存儲(chǔ)該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的信息 BtTree ;二叉鏈表存儲(chǔ)的結(jié)點(diǎn)類(lèi)型定義：6.6 二叉樹(shù)遍歷 6.6.1 先根遍歷 6.6.2 中根遍歷 6.6.3 后根遍歷 6.6.4 按層遍歷 6.6.5 二叉樹(shù)遍歷的應(yīng)用 一棵二叉樹(shù)是由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)組成，爭(zhēng)別用D、L和R表示，并要求左子樹(shù)在右

36、子樹(shù)前遍歷，則可得到DLR（先根遍歷）、LDR（中根遍歷）和LRD（后根遍歷）三種。除了這三種外，還可按結(jié)點(diǎn)所在層數(shù)進(jìn)行遍歷，稱(chēng)按層遍歷。 6.6.1 先根遍歷 先根遍歷（先序遍歷）定義： 若二叉樹(shù)為非空樹(shù)，則 l訪(fǎng)問(wèn)二叉樹(shù)的根結(jié)點(diǎn) l先根遍歷左子樹(shù) l先根遍歷右子樹(shù) 分析：先根遍歷是一個(gè)遞歸過(guò)程，先遍歷根結(jié)點(diǎn)，后先根遍歷左、右子樹(shù)。對(duì)左、右子樹(shù)也是按先根遍歷。 先根遍歷的遞歸算法為：（二叉鏈表形式存儲(chǔ)） void PreOrdetBT( BtTree *BT ) if ( BT ) printf( “輸出格式串”，BT-data ) ; PreOrdetBT( BT-lchild ) ; P

37、reOrdetBT( BT-rchild ) ; 先根遍歷的遞歸算法 分析：二叉樹(shù)的先根遍歷從根結(jié)點(diǎn)開(kāi)始，沿左子樹(shù)一直到左孩子為空為止。在整個(gè)過(guò)程中，訪(fǎng)問(wèn)所遇到的結(jié)點(diǎn)，然后沿線(xiàn)往回返，每返回一個(gè)結(jié)點(diǎn)都去遍歷該結(jié)點(diǎn)的右子樹(shù)，直到遍歷完右子樹(shù)為止。在沿左子樹(shù)遍歷過(guò)程中，若左子樹(shù)為空，都要往上一個(gè)訪(fǎng)問(wèn)結(jié)點(diǎn)返回（退棧）。所以需要存儲(chǔ)（進(jìn)棧）遍歷過(guò)程中每個(gè)訪(fǎng)問(wèn)到的結(jié)點(diǎn)（定義一個(gè)棧）。重復(fù)此過(guò)程，直到棧為空或指向結(jié)點(diǎn)的指針為空時(shí)停止。 先根遍歷的非遞歸算法為： （略）先根遍歷的非遞歸算法6.6.2 中根遍歷 中根遍歷（中序遍歷）的定義：若二叉樹(shù)為非空樹(shù)，則 l中根遍歷左子樹(shù) l訪(fǎng)問(wèn)二叉樹(shù)的根結(jié)點(diǎn) l中根遍

38、歷右子樹(shù)中根遍歷的遞歸算法 分析：中根遍歷是一個(gè)遞歸過(guò)程，先中根遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后中根遍歷右子樹(shù)。對(duì)左、右子樹(shù)也按中根遍。 中根遍歷的遞歸算法：（二叉鏈表形式存儲(chǔ)） void InOrdetBT( BtTree *BT ) if ( BT ) PreOrdetBT( BT-lchild ) ; printf( “輸出格式串”，BT-data )； PreOrdetBT( BT-rchild ) ; 中根遍歷的非遞歸算法 分析：中根遍歷是一個(gè)從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始，沿左子樹(shù)一直到左孩子為空時(shí)，沿線(xiàn)往回返，每返回一個(gè)結(jié)點(diǎn)都先訪(fǎng)問(wèn)該結(jié)點(diǎn)，然后去遍歷該結(jié)點(diǎn)的右子樹(shù)。在沿左子樹(shù)遍歷的過(guò)程中，

39、若左子樹(shù)為空，都要往上一個(gè)訪(fǎng)問(wèn)結(jié)點(diǎn)返回，所以需要存儲(chǔ)遍歷過(guò)程中遇到的每個(gè)結(jié)點(diǎn)（設(shè)定一個(gè)棧）。沿左子樹(shù)遍歷時(shí)每遇到一個(gè)結(jié)點(diǎn)，就將該結(jié)點(diǎn)進(jìn)棧，當(dāng)左子樹(shù)為空時(shí)，從棧頂退棧一個(gè)結(jié)點(diǎn)，先訪(fǎng)問(wèn)該結(jié)點(diǎn)，然后去訪(fǎng)問(wèn)該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。重復(fù)此過(guò)程，直到棧為空或指向結(jié)點(diǎn)的指針為空時(shí)停止。 中根遍歷的非遞歸算法：（略） 6.6.3 后根遍歷 后根遍歷（后序遍歷 ）的定義：若二叉樹(shù)為非空樹(shù)，則 l 后根遍歷左子樹(shù) l后根遍歷右子樹(shù) l訪(fǎng)問(wèn)二叉樹(shù)的根結(jié)點(diǎn)后根遍歷的遞歸算法 分析：后根遍歷過(guò)程是一個(gè)遞歸過(guò)程，先后根遍歷左、右子樹(shù)，后遍歷根結(jié)點(diǎn)。對(duì)左、右子樹(shù)也是先后根遍歷其左、右分支，后遍歷根結(jié)點(diǎn)。 后根遍歷的遞歸算法：（

40、二叉鏈表形式存儲(chǔ)） void PostOrdetBT( BtTree *BT ) if ( BT ) PreOrdetBT( BT-lchild ) ; PreOrdetBT( BT-rchild ) ; printf( “輸出格式串”，BT-data ) ; 后根遍歷的非遞歸算法 分析：后根遍歷過(guò)程從二叉樹(shù)的根結(jié)點(diǎn)開(kāi)始，沿左子樹(shù)一直到左孩子為空停止，左孩子為空時(shí)，沿線(xiàn)往回返，每返回一個(gè)結(jié)點(diǎn)都先去遍歷該結(jié)點(diǎn)的右子樹(shù)，最后才訪(fǎng)問(wèn)該結(jié)點(diǎn)。所以每個(gè)結(jié)點(diǎn)第一次出棧時(shí)，剛遍歷完該結(jié)點(diǎn)的左子樹(shù)，還需要將結(jié)點(diǎn)再次壓入棧中，等再次彈出時(shí)，已遍歷完該結(jié)點(diǎn)的右子樹(shù)，這時(shí)才可以訪(fǎng)問(wèn)該結(jié)點(diǎn)。為了區(qū)分同一結(jié)點(diǎn)的兩次進(jìn)棧

41、，可以引入一個(gè)標(biāo)志棧，當(dāng)從存放結(jié)點(diǎn)的棧中出棧一個(gè)結(jié)點(diǎn)時(shí)，從標(biāo)志棧也要出棧一個(gè)元素，根據(jù)此元素的值來(lái)確定該結(jié)點(diǎn)是再次進(jìn)棧，還是訪(fǎng)問(wèn)該結(jié)點(diǎn)。 后根遍歷的非遞歸算法：（略） 6.6.4 按層遍歷 按層遍歷的定義：若二叉樹(shù)為非空樹(shù)，則 l先訪(fǎng)問(wèn)根結(jié)點(diǎn) l按從左到右的順序遍歷根結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)l 依次類(lèi)推，由層數(shù)的從低到高，同層從左到右的順序遍歷所有結(jié)點(diǎn) 注意：二叉樹(shù)中定義根結(jié)點(diǎn)的層數(shù)為第一層 按層遍歷的非遞歸算法 分析：實(shí)現(xiàn)按層遍歷時(shí)就可以定義一個(gè)隊(duì)列來(lái)存放結(jié)點(diǎn)。整個(gè)按層遍歷的過(guò)程就從根結(jié)點(diǎn)開(kāi)始，訪(fǎng)問(wèn)完一個(gè)結(jié)點(diǎn)就讓該結(jié)點(diǎn)進(jìn)隊(duì)，然后從隊(duì)列中出隊(duì)一個(gè)結(jié)點(diǎn)，去訪(fǎng)問(wèn)該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)，每訪(fǎng)問(wèn)一個(gè)結(jié)點(diǎn)就

42、讓該結(jié)點(diǎn)進(jìn)隊(duì)。直到隊(duì)列為空時(shí)停止。二叉樹(shù)以二叉鏈表形式存儲(chǔ) 。 按層遍歷的非遞歸算法：（略） 6.6.5 二叉樹(shù)遍歷的應(yīng)用 例1：寫(xiě)出圖6-9中給出的二叉樹(shù)的先根、中根、后根和按層遍歷的結(jié)點(diǎn)序列。解： 先根遍歷：ABDEKCFG中根遍歷：DBEKAFCG后根遍歷：DKEBFGCA按層遍歷：ABCDEFGK 已知：給定的先根遍歷結(jié)點(diǎn)序列為：ABDGHCEIJF，中根遍歷結(jié)點(diǎn)序列為：GDHBAEIJCF。 分析：對(duì)一棵二叉樹(shù)先根遍歷時(shí)，第一個(gè)訪(fǎng)問(wèn)到的結(jié)點(diǎn)肯定是二叉樹(shù)的根結(jié)點(diǎn)，所以從先根遍歷的結(jié)點(diǎn)序列中可得知，二叉樹(shù)的根結(jié)點(diǎn)為A。中根遍歷先遍歷左子樹(shù)，然后遍歷根結(jié)點(diǎn)，最后遍歷右子樹(shù)，所以在結(jié)點(diǎn)序列中

43、確定根結(jié)點(diǎn)后，根結(jié)點(diǎn)前面的結(jié)點(diǎn)序列肯定是左子樹(shù)中結(jié)點(diǎn)的中根遍歷后的結(jié)果，而后面的是右子樹(shù)的中根遍歷后的所得結(jié)果。即可將二叉樹(shù)分成左子樹(shù)、根和右子樹(shù)三部分，依次類(lèi)推。 解題過(guò)程：（略） 例2：根據(jù)給定的遍歷序列，畫(huà)出相應(yīng)的二叉樹(shù)。6.7 樹(shù)與二叉樹(shù)的轉(zhuǎn)換 6.7.1 樹(shù)的存儲(chǔ)結(jié)構(gòu) 6.7.2 樹(shù)與二叉樹(shù)的轉(zhuǎn)換 6.7.3 森林與二叉樹(shù)的轉(zhuǎn)換 6.7.1 樹(shù)的存儲(chǔ)結(jié)構(gòu) 雙親表示法 孩子表示法 孩子雙親表示法 孩子兄弟表示法 雙親表示法： 實(shí)現(xiàn)：開(kāi)辟一段連續(xù)的存儲(chǔ)單元來(lái)存放結(jié)點(diǎn)信息及該結(jié)點(diǎn)的雙親結(jié)點(diǎn)信息。通常定義一個(gè)一維數(shù)組存放結(jié)點(diǎn)的元素信息及雙親結(jié)點(diǎn)的信息。（順序存儲(chǔ)）雙親表示法的存儲(chǔ)類(lèi)型定義為：

44、const int maxsize = 常數(shù) ;struct node Elemtype data ; /存放樹(shù)中結(jié)點(diǎn)元素信息int parent ; /存放雙親結(jié)點(diǎn)在數(shù)組t中的下標(biāo) ; node t maxsize ; /存儲(chǔ)結(jié)點(diǎn)及雙親信息 孩子表示法： 實(shí)現(xiàn)：將每個(gè)結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)鏈接成一個(gè)單鏈表，并將所有的單鏈表的表頭結(jié)點(diǎn)存放在一個(gè)一維數(shù)組。孩子表示法的存儲(chǔ)類(lèi)型定義為：const maxsize = 常數(shù) ; / 存儲(chǔ)空間的大小struct Link int child ; / 存放孩子結(jié)點(diǎn)在數(shù)組中的下標(biāo) Link *next ; / 指向該結(jié)點(diǎn)的下一個(gè)孩子結(jié)點(diǎn)的指針 ; / 單鏈表的

45、結(jié)點(diǎn)類(lèi)型定義 struct node Elemtype data ; / 存儲(chǔ)樹(shù)中結(jié)點(diǎn)元素的信息 Link*next ; /指向該結(jié)點(diǎn)所有子結(jié)點(diǎn)組成的單鏈表的第一個(gè)結(jié)點(diǎn) ; / 數(shù)組元素的類(lèi)型定義node t maxsize ; / 用數(shù)組來(lái)存儲(chǔ)樹(shù)中結(jié)點(diǎn)的相關(guān)信息 孩子雙親表示法 ：實(shí)現(xiàn)：將孩子表示法和雙親表示法結(jié)合在一起就是孩子雙親表示法。孩子雙親表示法存儲(chǔ)類(lèi)型定義：（略）孩子兄弟表示法： 實(shí)現(xiàn)：在孩子兄弟表示法中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了存放結(jié)點(diǎn)信息的值域外，另外兩個(gè)指針域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和與該結(jié)點(diǎn)相鄰的兄弟結(jié)點(diǎn)，是一種鏈?zhǔn)酱鎯?chǔ)方式。孩子兄弟表示法存儲(chǔ)類(lèi)型定義：（略）6.7.

46、2 樹(shù)與二叉樹(shù)的轉(zhuǎn)換 將樹(shù)轉(zhuǎn)換為二叉樹(shù)的方法： l連線(xiàn)：將每個(gè)結(jié)點(diǎn)跟與它相鄰的右邊的兄弟結(jié)點(diǎn)用線(xiàn)連起來(lái)。 l 抹線(xiàn)：對(duì)所有結(jié)點(diǎn)，除了該結(jié)點(diǎn)的最左邊的孩子結(jié)點(diǎn)外，將該結(jié)點(diǎn)與其它孩子結(jié)點(diǎn)之間的連線(xiàn)全部刪除。 l 旋轉(zhuǎn)：將樹(shù)以根結(jié)點(diǎn)為重心，順時(shí)針?lè)较蛐D(zhuǎn)大概45。角，把樹(shù)中的水平連線(xiàn)變成右分支，原有連線(xiàn)變成左分支。 將二叉樹(shù)還原為樹(shù)的方法： l 加線(xiàn)：對(duì)二叉樹(shù)中所有具有雙親結(jié)點(diǎn)的左孩子的右孩子，及右孩子的右孩子都與雙親結(jié)點(diǎn)連起來(lái)。 l 抹線(xiàn)：抹掉二叉樹(shù)中所有雙親結(jié)點(diǎn)與右孩子間的連線(xiàn)。 l 調(diào)整：以二叉樹(shù)的根結(jié)點(diǎn)作為樹(shù)的根結(jié)點(diǎn)，將其余結(jié)點(diǎn)的位置進(jìn)行調(diào)整。 結(jié)論： 1 樹(shù)轉(zhuǎn)換成的二叉樹(shù)是一棵右子樹(shù)為空的

47、二叉樹(shù)。 2 二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)在原樹(shù)中是它的最左孩子結(jié)點(diǎn)，而右孩子結(jié)點(diǎn)是它的兄弟結(jié)點(diǎn)。 3 樹(shù)的孩子兄弟表示法其實(shí)就是將樹(shù)轉(zhuǎn)換成二叉樹(shù)的方法。 6.7.3 森林與二叉樹(shù)的轉(zhuǎn)換 森林轉(zhuǎn)換成二叉樹(shù)的方法： l 轉(zhuǎn)換：將組成森林的所有樹(shù)轉(zhuǎn)換成一棵棵二叉樹(shù)。 l 連線(xiàn)：將轉(zhuǎn)換成的所有二叉樹(shù)的根結(jié)點(diǎn)連起來(lái)。 l 旋轉(zhuǎn)：以第一棵樹(shù)的根結(jié)點(diǎn)為中心，按順時(shí)針?lè)较蛐D(zhuǎn)所添加的所有的水平線(xiàn)和原有連線(xiàn)。 二叉樹(shù)轉(zhuǎn)換成森林的方法： l 抹線(xiàn)：抹掉二叉樹(shù)中根結(jié)點(diǎn)右鏈上的所有結(jié)點(diǎn)的連線(xiàn)，將二叉樹(shù)分成若干棵以右鏈上的結(jié)點(diǎn)為根結(jié)點(diǎn)的二叉樹(shù)。 l轉(zhuǎn)換：將分成的二叉樹(shù)轉(zhuǎn)換成樹(shù)。 l 調(diào)整：以樹(shù)的根結(jié)點(diǎn)為準(zhǔn)，排列成一排

48、。 6.8 應(yīng)用舉例 6.8.1 線(xiàn)索二叉樹(shù) 6.8.2 二叉排序樹(shù) 6.8.3 哈夫曼樹(shù) 6.8.4 二叉樹(shù)的綜合實(shí)例 6.8.1 線(xiàn)索二叉樹(shù) 線(xiàn)索二叉樹(shù)定義: 如果對(duì)一棵二叉樹(shù)用指針指出按某種方式遍歷時(shí)的結(jié)點(diǎn)的前驅(qū)和后繼信息，則稱(chēng)指針為線(xiàn)索，而給出線(xiàn)索的二叉樹(shù)就稱(chēng)為線(xiàn)索二叉樹(shù)，畫(huà)出線(xiàn)索的過(guò)程稱(chēng)為線(xiàn)索化。 線(xiàn)索化二叉樹(shù)(二叉鏈表的形式存儲(chǔ))： 結(jié)點(diǎn)結(jié)構(gòu)如下所示：lchildltagdatartagrchild6.8.2 二叉排序樹(shù) 二叉排序樹(shù)的定義（遞歸定義 ） 或者是一棵空二叉樹(shù)，或者是一棵滿(mǎn)足以下條件的二叉樹(shù)： l左子樹(shù)中所有結(jié)點(diǎn)的值都小于根結(jié)點(diǎn)的值 l右子樹(shù)中所有結(jié)點(diǎn)的值都大于等于根結(jié)

49、點(diǎn)的值 l左、右子樹(shù)本身也是一棵二叉排序樹(shù) 結(jié)論：中根遍歷后的結(jié)點(diǎn)序列是一個(gè)有序序列。如果用待排序數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù)，并對(duì)它進(jìn)行中根遍歷，則達(dá)到排序目的。 二叉排序樹(shù)是一種排序方法。 構(gòu)造二叉排序樹(shù) 構(gòu)造過(guò)程：從空樹(shù)逐步插入各個(gè)結(jié)點(diǎn)的過(guò)程。每插入一個(gè)結(jié)點(diǎn)時(shí)，插入位置的確定都從根結(jié)點(diǎn)開(kāi)始，根據(jù)二叉排序樹(shù)的定義，小于根結(jié)點(diǎn)的插入位置應(yīng)在左子樹(shù)中，否則，插入位置應(yīng)在右子樹(shù)中。一直進(jìn)行比較，直到找到一個(gè)合適的插入位置，將結(jié)點(diǎn)插入成為一個(gè)葉子結(jié)點(diǎn)為止。二叉排序樹(shù)的插入算法 ：（略）6.8.3 哈夫曼樹(shù) 哈夫曼樹(shù)的相關(guān)概念 路徑：連接兩個(gè)結(jié)點(diǎn)的分支 路徑長(zhǎng)度：兩個(gè)結(jié)點(diǎn)間路徑上的分支個(gè)數(shù)。 樹(shù)的路徑長(zhǎng)度

50、：從根結(jié)點(diǎn)到其余各結(jié)點(diǎn)間路徑之和。 結(jié)點(diǎn)的權(quán)：樹(shù)中結(jié)點(diǎn)所賦的數(shù)值。 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度和該結(jié)點(diǎn)的權(quán)植的乘積。 樹(shù)的帶權(quán)路徑長(zhǎng)度是指樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。通常記作： 其中，wi代表第i個(gè)結(jié)點(diǎn)的權(quán)值；li代表第i個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度；n為樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）是指帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。哈夫曼樹(shù)的構(gòu)造方法： l根據(jù)給定的n個(gè)權(quán)值（w1,w2,wn），構(gòu)成n棵二叉樹(shù)的集合。其中，每棵二叉樹(shù)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，沒(méi)有左、右子樹(shù)。 l從二叉樹(shù)的集合中，選擇權(quán)值最小的兩棵樹(shù)作為左右子樹(shù)，構(gòu)成一棵新的二叉樹(shù)，新二叉樹(shù)的根結(jié)點(diǎn)的值為左右孩子結(jié)

51、點(diǎn)的權(quán)值之和。 l從二叉樹(shù)集合中，刪除剛選取的兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)添加到二叉樹(shù)集合中。 重復(fù)上述過(guò)程，直到二叉樹(shù)集合中只有一棵二叉樹(shù)為止，該樹(shù)既為哈夫曼樹(shù)。 6.8.4 二叉樹(shù)的綜合實(shí)例 問(wèn)題的描述： 創(chuàng)建一棵二叉樹(shù)，給出此二叉樹(shù)按四種遍歷方式遍歷后的結(jié)點(diǎn)序列、計(jì)算此二叉樹(shù)的層數(shù)。問(wèn)題的分析： 設(shè)二叉鏈表形式存儲(chǔ)，結(jié)點(diǎn)值用單個(gè)字符表示。 創(chuàng)建：按先序遍歷的順序建立二叉鏈表。先建立根結(jié)點(diǎn)，然后依次建立根的左、右子樹(shù)。在建立過(guò)程中，將二叉樹(shù)當(dāng)成完全二叉樹(shù)，二叉樹(shù)中與完全二叉樹(shù)對(duì)應(yīng)的結(jié)點(diǎn)輸入結(jié)點(diǎn)元素的值；沒(méi)有對(duì)應(yīng)的結(jié)點(diǎn)時(shí)，輸入#來(lái)代替，直到二叉樹(shù)的全部結(jié)點(diǎn)輸入完畢為止。二叉樹(shù)的遍歷過(guò)程是一個(gè)

52、遞歸過(guò)程，所以建立算法也可以寫(xiě)成一個(gè)遞歸算法。遍歷：可以直接調(diào)用6.6二叉樹(shù)遍歷中給定的算法。求深度：二叉樹(shù)的深度為樹(shù)中結(jié)點(diǎn)層次的最大值，所以從上一層的根結(jié)點(diǎn)開(kāi)始往下遞推可得到樹(shù)的層數(shù)。在整個(gè)過(guò)程中也需要確定一個(gè)遍歷方式，本例中使用后序遍歷來(lái)實(shí)現(xiàn)。實(shí)現(xiàn)算法 ： （略）本章總結(jié) 本章介紹了樹(shù)和二叉樹(shù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、各種基本操作的實(shí)現(xiàn)及應(yīng)用。 樹(shù)是若干個(gè)結(jié)點(diǎn)的有限集合。主要特征是只有一個(gè)沒(méi)有前驅(qū)的結(jié)點(diǎn)為根結(jié)點(diǎn)，其余結(jié)點(diǎn)都只有一個(gè)前驅(qū)，所有結(jié)點(diǎn)可以有任意多個(gè)后繼，是一對(duì)多的關(guān)系。 樹(shù)有四種存儲(chǔ)方式：雙親表示法、孩子表示法、孩子雙親表示法和孩子兄弟表示法。樹(shù)的主要操作是樹(shù)的遍歷。遍歷是指訪(fǎng)問(wèn)樹(shù)中

53、所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)只能訪(fǎng)問(wèn)一次。樹(shù)有三種遍歷方法：先根遍歷、后根遍歷和按層遍歷。 森林是若干棵樹(shù)的集合，有先根遍歷和后根遍歷兩種遍歷方式。 二叉樹(shù)主要特征是只有一個(gè)沒(méi)有前驅(qū)的根結(jié)點(diǎn)，其余結(jié)點(diǎn)都只有一個(gè)前驅(qū)，所有結(jié)點(diǎn)最多有兩個(gè)后繼結(jié)點(diǎn)，分別為該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)。 二叉樹(shù)的存儲(chǔ)方式：順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)（二叉鏈表）。順序存儲(chǔ)適合存儲(chǔ)完全二叉樹(shù)，普通二叉樹(shù)適合用鏈?zhǔn)酱鎯?chǔ)方式。 二叉樹(shù)有四種遍歷方式：先根遍歷、中根遍歷、后根遍歷和按層遍歷。 樹(shù)、森林和二叉樹(shù)之間可以進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換的主要依據(jù)就是樹(shù)的孩子兄弟表示法，組成森林的所有樹(shù)的根結(jié)點(diǎn)之間是兄弟關(guān)系。 樹(shù)、森林與二叉樹(shù)進(jìn)行轉(zhuǎn)換結(jié)論：樹(shù)的

54、先根遍歷和后根遍歷的結(jié)點(diǎn)序列就是該樹(shù)轉(zhuǎn)換成二叉樹(shù)后的先根和中根遍歷的結(jié)點(diǎn)序列；森林的先根遍歷和后根遍歷的結(jié)點(diǎn)序列就是該森林轉(zhuǎn)換成二叉樹(shù)后的先根和中根遍歷的結(jié)點(diǎn)序列。 二叉樹(shù)的主要應(yīng)用：線(xiàn)索二叉樹(shù)、二叉排序樹(shù)和哈夫曼樹(shù)等。第7章 圖 學(xué)習(xí)重點(diǎn)：掌握?qǐng)D的基本概念、邏輯特征和圖的存儲(chǔ)結(jié)構(gòu)。掌握?qǐng)D的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的思想、遍歷過(guò)程及鄰接矩陣和鄰接表上的實(shí)現(xiàn)算法。 掌握?qǐng)D的最小生成樹(shù)的概念和求圖的最小生成樹(shù)的克魯斯卡爾算法和普里姆算法的思想、求解過(guò)程和畫(huà)出對(duì)應(yīng)的最小生成樹(shù)并求出最小生成樹(shù)的權(quán)。掌握求有向圖最短路徑和拓?fù)湫蛄械乃枷牒颓蠼膺^(guò)程。 第7章 圖 7.1 實(shí)例：求城市間最短路徑

55、7.2 圖的邏輯結(jié)構(gòu)、特征 7.3 圖的存儲(chǔ)結(jié)構(gòu) 7.4 圖的遍歷 7.5 最小生成樹(shù) 7.6 應(yīng)用舉例 本章總結(jié)7.1 實(shí)例：求城市間最短路徑 7.1.1 問(wèn)題描述 假設(shè)乘飛機(jī)旅行，想選擇一條所要參觀(guān)的兩個(gè)城市間距離最短的路線(xiàn)。 7.1.2 問(wèn)題的分析 如果以點(diǎn)代表城市，以線(xiàn)代表兩個(gè)城市之間的距離，并在線(xiàn)上標(biāo)出具體的距離值，可畫(huà)出相應(yīng)的圖。通常將解決這種問(wèn)題中的出發(fā)點(diǎn)稱(chēng)之為源點(diǎn)，則求最短路徑就變成一個(gè)求從源點(diǎn)到終點(diǎn)的最短路徑的問(wèn)題。解決此問(wèn)題時(shí)需要求出源點(diǎn)到其余各頂點(diǎn)間的最短路徑才能得到最終的答案。 第一步：先求從源點(diǎn)出發(fā)的各個(gè)路徑中的最短路徑。有兩種情況：第一種直接有線(xiàn)相連，比較路徑值的大

56、?。涣硪环N沒(méi)有直接連線(xiàn)，表示這兩個(gè)城市間不直接通。第二步：在上一結(jié)果的基礎(chǔ)上求從源點(diǎn)出發(fā)的各個(gè)路徑中的最短路徑。到達(dá)各個(gè)城市的路徑存在二種可能性：第一種是途徑剛選擇的城市仍沒(méi)有通路；第二種是途徑剛選擇的城市后，到達(dá)該城市的路徑又多出一種選擇，此時(shí)選擇短的路徑。第三步：重復(fù)第二步，每選中一個(gè)城市，都要修改一下到其余各城市間的最短路徑，直到求出源點(diǎn)到其余各城市間的最短路徑為止。 求解過(guò)程大體如下： 從畫(huà)出的圖可知，此圖是一種圖型結(jié)構(gòu)，圖中每個(gè)圓圈就是圖型結(jié)構(gòu)中的一個(gè)頂點(diǎn)，連線(xiàn)稱(chēng)之為邊，所以圖是由若干個(gè)頂點(diǎn)的集合和邊的集合組成的。 上面的例子就是圖的日常生活中的一種應(yīng)用：求從源點(diǎn)到其余各頂點(diǎn)間的最短

57、距離。 結(jié)論：7.2 圖的邏輯結(jié)構(gòu)、特征 7.2.1 圖的邏輯結(jié)構(gòu) 7.2.2 圖的特征 圖是一種復(fù)雜的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是任意的，即圖中的每個(gè)結(jié)點(diǎn)都可以有任意多個(gè)前驅(qū)結(jié)點(diǎn)和任意多個(gè)后繼結(jié)點(diǎn)，是多對(duì)多的關(guān)系。 7.2.1 圖的邏輯結(jié)構(gòu) 圖的定義： 圖（Graph）由兩個(gè)集合V和E組成，它的二元組定義可以表示成： Graph=（V，E） 其中， V是頂點(diǎn)的有窮非空集合，即V=vi | n1，viVertexType，VertexType為頂點(diǎn)值的類(lèi)型，它可以代表任何類(lèi)型，n為頂點(diǎn)數(shù)； E是V上頂點(diǎn)間二元關(guān)系的有窮集合，稱(chēng)這種關(guān)系為邊。 用V（G）表示圖的頂點(diǎn)集合；E（G

58、）來(lái)表示圖G的邊集合，E（G）可以為空集。當(dāng)E（G）為空集時(shí)，圖G稱(chēng)為空?qǐng)D。 無(wú)向圖：在圖G中，如果代表邊的頂點(diǎn)序偶關(guān)系都是對(duì)稱(chēng)的，即和同時(shí)成立，則以無(wú)序?qū)Γ╲i，vj）替代這兩個(gè)有序?qū)Α?有向圖：圖G中邊的頂點(diǎn)是有序的。在有向圖中邊表示從頂點(diǎn)vi到頂點(diǎn)vj的一條有向邊（?。旤c(diǎn)vi稱(chēng)為有向邊的尾（或始點(diǎn)），頂點(diǎn)vj稱(chēng)為有向邊的頭（或終點(diǎn)），用由起點(diǎn)指向終點(diǎn)的箭頭表示有向邊。 7.2.2 圖的特征 端點(diǎn)和鄰接點(diǎn) 在一個(gè)無(wú)向圖中，若存在一條邊（vi，vj），則稱(chēng)vi，vj為此邊的兩個(gè)端點(diǎn)，并稱(chēng)它們互為鄰接點(diǎn)。在一個(gè)有向圖中，若存在一條邊，則稱(chēng)此邊為頂點(diǎn)vi的一條出邊，頂點(diǎn)vj的一條入邊（ine

59、dge）；稱(chēng)vj是vi的出邊鄰接點(diǎn)，vi是vj的入邊鄰接點(diǎn)。頂點(diǎn)的度、入度、出度 在無(wú)向圖中，頂點(diǎn)v所具有的邊的數(shù)目稱(chēng)為該頂點(diǎn)的度。有向圖中頂點(diǎn)v的度又分為入度（以頂點(diǎn)v為終點(diǎn)的入邊的數(shù)目）和出度（以頂點(diǎn)v為始點(diǎn)的出邊的數(shù)目）。一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。完全圖、稠密圖、稀疏圖 若無(wú)向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊，有向圖中的每?jī)蓚€(gè)頂點(diǎn)之間都存在著方向相反的兩條邊，則稱(chēng)此圖為完全圖。當(dāng)一個(gè)圖接近完全圖時(shí)，則稱(chēng)它為稠密圖。相反，當(dāng)一個(gè)圖含有較少的邊數(shù)時(shí)，則稱(chēng)為稀疏圖。子圖 設(shè)有兩個(gè)圖G=（V，E）和G=(V，E)，若V是V的子集，即VV，且E是E的子集，即EE，則稱(chēng)G是G的子圖。

60、路徑和路徑長(zhǎng)度路徑（path）是一個(gè)頂點(diǎn)序列。路徑長(zhǎng)度是指該路徑上經(jīng)過(guò)的邊的數(shù)目。若一條路徑上除了開(kāi)始點(diǎn)和結(jié)束點(diǎn)可以相同外，其余頂點(diǎn)均不相同，則稱(chēng)此路徑為簡(jiǎn)單路徑?；芈坊颦h(huán)若一條路徑上的開(kāi)始點(diǎn)與結(jié)束點(diǎn)為同一個(gè)頂點(diǎn)，則此路徑被稱(chēng)為回路或環(huán)（cycle）。開(kāi)始點(diǎn)與結(jié)束點(diǎn)相同的簡(jiǎn)單路徑被稱(chēng)為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。連通、連通圖和連通分量 在無(wú)向圖G中，若從頂點(diǎn)vi 到頂點(diǎn)vj有路徑，則稱(chēng)vi和vj是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通，則稱(chēng)G為連通圖，否則稱(chēng)為非連通圖。無(wú)向圖G中極大連通子圖稱(chēng)為G的連通分量。強(qiáng)連通圖和強(qiáng)連通分量 在有向圖G中，若從頂點(diǎn)vi 到頂點(diǎn)vj有路徑，則稱(chēng)vi和vj是連通的。若任意兩