高等教育自學考試 （自考）數(shù)據(jù)結構導論 全冊講義（完整版）

高等教育自學輔導資料數(shù)據(jù)結構導論79/79第一章概論一、學習目的與要求理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念及其相互關系；理解數(shù)據(jù)結構的含義；理解邏輯結構、基本運算和存儲結構的概念，意義和分類；理解存儲結構與邏輯結構的關系；理解算法的概念；理解衡量一個算法效率的兩個標準：時間復雜度和空間復雜度。二、課程內容1.1引言計算機處理問題的一般步驟：（1）從具體的問題抽象出一個適當?shù)臄?shù)學模型；（2）設計一個求解該數(shù)學模型的算法；（3）用某種計算機語言編寫實現(xiàn)該算法的程序，調試和運行程序直至最終得到問題的解答。1.2基本概念和術語1.2.1數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項數(shù)據(jù)：所有被計算機存儲、處理的對象。數(shù)值、布爾值等擴展到字符串、表格、圖像甚至聲音等。數(shù)據(jù)元素（元素）：數(shù)據(jù)的基本單位，在程序中作為一個整體而加以考慮和處理。數(shù)據(jù)項：一般情況下，數(shù)據(jù)元素由數(shù)據(jù)項組成。在數(shù)據(jù)庫中數(shù)據(jù)項又稱為字段或域。.它是數(shù)據(jù)的不可分割的最小標識單位。結合表1-1，理解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項三個概念及之間的聯(lián)系表1-1學生檔案信息表學號姓名性別年齡入學成績1001王韜男205891002潘小欣女215801003張艷女195681004趙李軍男185801005劉勇男225851.2.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間的邏輯關系。所謂邏輯關系是指數(shù)據(jù)元素之間的關聯(lián)方式或“鄰接關系”四種基本的邏輯結構：●集合：集合中任意兩個結點之間都沒有鄰接關系，組織形式松散。●線性結構：一對一●樹形結構：一對多●圖結構：多對多a）集合b）線性結構C）樹形結構d）圖結構1.2.3數(shù)據(jù)的存儲結構數(shù)據(jù)的邏輯結構在計算機中的實現(xiàn)稱為數(shù)據(jù)的存儲結構（或物理結構）。一般情況下，一個存儲結構包括以下兩個部分：（1）存儲數(shù)據(jù)元素；（2）數(shù)據(jù)元素之間的關聯(lián)方式。主要的存儲方式：順序存儲、鏈式存儲。順序存儲方式是指所有存儲結點存放在一個連續(xù)的存儲區(qū)里。利用結點在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。鏈式存儲方式是指每個存儲結點除了含有一個數(shù)據(jù)元素外，還包含指針，每個指針指向一個與本結點有邏輯關系的結點，用指針表示數(shù)據(jù)元素之間的邏輯關系。除了上述兩種存儲方式之外，還有索引存儲方式和散列存儲方式。1.2.4運算運算是指在某種邏輯結構上施加的操作，即對邏輯結構的加工。這種加工以數(shù)據(jù)的邏輯結構為對象。一般來說，在每個邏輯結構上，都定義了一組基本運算，這些運算包括：建立、查找、讀取、插入和刪除等。1.3算法及描述一個算法給規(guī)定了求解給定問題所需的處理步驟及其執(zhí)行順序，使得給定問題能夠在有限的時間內被求解。本書采用類C語言來描述算法1）函數(shù)描述形式.函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）//算法說明{語句序列}2）輸入、輸出語句輸入語句：scanf（格式串，變量1，...，變量n）；輸出語句：printf（格式串，變量1，變量n）；3）賦值語句變量名=表達式；4）選擇語句1>條件語句：if（表達式）語句；或if（表達式）語句；else語句；2>分支語句：switch｛case條件1：語句序列；break；case條件2：語句序列；break；case條件n：語句序列；break；default：語句序列；｝其中“default：語句序列；”可以省略。5）循環(huán)語句for（賦初值表達式序列；條件；修改表達式序列）語句；while（條件）語句；do{語句；}while（條件）；6）結束語句1>函數(shù)結束語句：return表達式；2>case結束語句break；3>異常結束語句：exit（異常代碼）；7）出錯語句：error（"錯誤描述"）8）注釋單行注釋：//注釋內容多行注釋：/*注釋內容*/1.4算法分析通常評價算法好壞的因素包括以下幾個方面：1）正確性：能正確地實現(xiàn)預定的功能，滿足具體問題的需要。2）易讀性：易于閱讀、理解和交流，便于調試、修改和擴充。3）健壯性：即使輸入非法數(shù)據(jù)，算法也能適當?shù)刈龀龇磻蜻M行處理，不會產(chǎn)生預料不到的運行結果。4）時空性：一個算法的時空性是指該算法的時間性能（或時間效率）和空間性能（或空間效率），前者是算法包含的計算量，后者是算法需要的存儲量。1.4.1時間復雜度【例1-4】編制函數(shù)求1!+2!+...+n!?！痉治觥繉τ谶@個問題，可以寫出兩個算法，如圖所示。兩個算法的計算量不同，如何估算算法的計算量?可在算法中合理地選擇一種或幾種操作作為“基本操作”，對給定的輸入，確定算法共執(zhí)行了多少次基本操作，可將基本操作次數(shù)作為該算法的時間度量。假如問題的輸入規(guī)模為n，—般情況下，一個算法的計算量是問題規(guī)模n的函數(shù)。設函數(shù)fact1中乘法、加法和賦值的次數(shù)記為T（n），則T（n）=n（n+1）/2+n+n（n+1）/2+2n+1=2（n2+n）/2+3n+1=n2+4n+1當n充分大時，n2這一項對T（n）的值起著支配作用，采用數(shù)學記號Ｏ（n2）表示T（n）的近似值，寫為T（n）=Ｏ（n2），這種表示法稱為大Ｏ表示法，它的含義是：當n充分大時，算法的執(zhí)行時間與n2成正比。大Ｏ表示法的具體提法是：當且僅當存在正常數(shù)c和n0，使得：T（n）<=cf（n）。對所有n>n0成立。其中，f（n）為問題的規(guī)模n的某個函數(shù)，大Ｏ表示法也稱為漸進表示法，它不考慮具體的運行時間，只給出算法在問題規(guī)模n下執(zhí)行時間的上界。T（n）=Ｏ（f（n））稱為算法的漸進時間復雜度，簡稱時間復雜度。常見的時間復雜度有：常數(shù)階Ｏ（1），對數(shù)階Ｏ（log2n），線性階Ｏ（n），多項式階Ｏ（n2）、Ｏ（n3），指數(shù)階Ｏ（2n）最壞時間復雜度、平均時間復雜度、最好時間復雜度1.4.2空間復雜度一個算法的空間復雜度定義為該算法所耗費的存儲空間，它也是問題規(guī)模n的函數(shù)。通?？捎洖椋篠（n）=0（g（n））其中，g（n）為問題規(guī)模n的某個函數(shù)?？臻g復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在執(zhí)行期間所需要的存儲空間量應包括以下三個部分：（1）程序代碼所占用的空間（2）輸入數(shù)據(jù)所占用的空間（3）輔助變量所占用的空間三、考核的知識點與考核要求1.數(shù)據(jù)結構、數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念識記：數(shù)據(jù)結構；數(shù)據(jù)；數(shù)據(jù)元素；數(shù)據(jù)項。領會：數(shù)據(jù)結構的作用；數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項三者關系。2.數(shù)據(jù)邏輯結構和數(shù)據(jù)存儲結構識記：數(shù)據(jù)邏輯結構、數(shù)據(jù)存儲結構。領會：四類基本邏輯結構的特點；順序存儲結構；鏈式存儲結構；邏輯結構與存儲結構的關系。3.運算、算法和算法分析識記：運算；基本運算；算法分析；時間復雜度；空間復雜度。領會：運算與數(shù)據(jù)結構的關系；算法的描述方法；算法的評價因素；時間復雜度分析方法；空間復雜度分析方法。簡單應用：運用類C語言描述算法；簡單算法時間復雜度分析；簡單算法的空間復雜度分析。四、本章重點、難點本章重點：數(shù)據(jù)結構、數(shù)據(jù)邏輯結構、數(shù)據(jù)存儲結構以及運算等概念。本章難點：算法時間復雜度分析。五、練習【例題·單選題】與數(shù)據(jù)元素本身的形式、內容、相對位置、個數(shù)無關的是數(shù)據(jù)的（）。A.存儲結構B.邏輯結構C.類型D.運算實現(xiàn)『正確答案』B『答案解析』數(shù)據(jù)的物理存儲、數(shù)據(jù)類型、運算實現(xiàn)與數(shù)據(jù)元素本身的形式、內容、相對位置，個數(shù)都密切相關，而邏輯結構反映的是數(shù)據(jù)元素之間的鄰接方式。參見教材P25?！纠}·單選題】算法時間復雜度指的是（）。A.一個算法的確切執(zhí)行時間B.一個程序的確切執(zhí)行時間C.算法在給定輸入下的計算量D.算法在給定時間下的計算量『正確答案』C『答案解析』首先算法的時間復雜度是對計算量的估算，其含義是對給定的輸入，確定算法共執(zhí)行了多少次基本操作。參見教材P29。【例題·單選題】下面幾種算法時間復雜度階數(shù)中（）最小。A.O（logn）B.O（n）C.O（n2）D.O（2n）『正確答案』A『答案解析』對于常見的幾種算法時間復雜度而言：O（1）<O（logn）<O（n）<O（nlogn）<O（n2）<O（n3）<O（2n）<O（n!）<O（nn）。參見教材P30。【例題·單選題】下面幾種算法時間復雜度階數(shù)中（）最大。A.O（logn）B.O（n）C.O（n2）D.O（nlogn）『正確答案』C『答案解析』對于常見的幾種算法時間復雜度而言：O（1）<O（logn）<O（n）<O（nlogn）<O（n2）<O（n3）<O（2n）<O（n!）<O（nn）。參見教材P30?！纠}·單選題】算法的空間復雜度指的是（）。A.算法本身所占用的存儲空間的大小B.算法中輸入數(shù)據(jù)所占用的存儲空間的大小C.算法中所占用的所有存儲空間的大小D.算法中除輸入數(shù)據(jù)占用的存儲空間之外所需的附加存儲空間的大小『正確答案』D『答案解析』算法的空間復雜度定義為該算法所耗費的存儲空間。參見教材P31?！纠}·填空題】從數(shù)據(jù)結構的觀點看，通常所說的“數(shù)據(jù)”應分成三個不同的層次，即___________、___________和___________『正確答案』數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項『答案解析』這道題考察關于數(shù)據(jù)的相關概念。參見教材P24?！纠}·填空題】數(shù)據(jù)項又稱為____或_____，它是數(shù)據(jù)的不可分割的最小標識單位?！赫_答案』字段、域『答案解析』這道題考察關于數(shù)據(jù)的相關概念。參見教材P24。【例題·填空題】根據(jù)數(shù)據(jù)元素之間關系的不同特性，通常有______、_______、________和________四類基本邏輯結構，它們反映了四種基本的數(shù)據(jù)組織形式?！赫_答案』集合、線性結構、樹形結構、圖結構『答案解析』這道題考察關于數(shù)據(jù)的四種邏輯結構。參見教材P25。【例題·填空題】一般情況下，一個算法的時間復雜度是___________的函數(shù)『正確答案』算法輸入規(guī)?！捍鸢附馕觥贿@道題考察時間復雜度的概念。參見教材P29?！纠}·填空題】常見算法時間復雜度的階數(shù)有常數(shù)階O（________）、對數(shù)階O（_________）、線性階O（_________）、平方階O（_________）和指數(shù)階O（_________）。通常認為，具有指數(shù)階量級的算法是________的，而量級低于平方階的算法是________?！赫_答案』1、logn、n、n2、2n、實際不可計算、高效『答案解析』這道題對考察時間復雜度的理解，應該掌握常見的幾種時間復雜度的大小關系及其含義。參見教材P30?！纠}·填空題】下述算法的時間復雜度T（n）=________for（i=l；i<=n；i++）{k++；for（j=l；j<=n；j++）m+=k；}『正確答案』O（n2）『答案解析』這道題考察算法時間復雜度的計算。參見教材P30。第二章線性表一、學習目的與要求順序表和單鏈表分別是簡單、基本的順序存儲結構和鏈式存儲結構。順序表和單鏈表上實現(xiàn)基本運算的算法是數(shù)據(jù)結構中簡單和基本的算法。這些內容構成以下各章的重要基礎，因此本章是本課程的重點之一。本章要求：理解線性表的概念；熟練掌握順序表和鏈表的組織方法及實現(xiàn)基本運算的算法；掌握在順序表和鏈表上進行算法設計的基本技能；了解順序表與鏈表的優(yōu)缺點。二、課程內容2.1線性表的基本概念線性表中結點具有一對一的關系，如果結點數(shù)不為零，則除起始結點沒有直接前驅外，其他每個結點有且僅有一個直接前驅；除終端結點沒有直接后繼外，其他每個結點有且僅有一個直接后繼。線性表基本運算有：初始化、求表長、讀表元素、定位、插入、刪除。2.2線性表的順序存儲2.2.1線性表的順序存儲線性表的順序存儲：邏輯結構相鄰的結點其存儲位置也相鄰。用順序存儲實現(xiàn)的線性表稱為順序表，一般用數(shù)組來表示順序表，如圖2-1所示【例2-1】學生檔案信息表的順序存儲實現(xiàn)。【分析】根據(jù)學生檔案信息，給出順序表具體的類型定義。2.2.2線性表的基本運算在順序表上的實現(xiàn)插入順序表的插入運算InsertSeqlist（SeqListL,DataTypex,inti）是指在順序表的第i（1<=i<=n+1）個元素之前，插入一個新元素x。使長度為n的線性表（a1，a2，...，ai-1，ai，...，an）變?yōu)殚L度為n+1的線性表（a1，a2，...，ai-1，x，ai，...，an）。具體算法描述如下：2）刪除刪除運算DeleteSeqlist（SeqListL，inti）是指將線性表的第i（1<=i<=n）個數(shù)據(jù)元素刪去，使長度為n的線性表（a1，a2，...，ai-1，ai，ai+1，...，an）變?yōu)殚L度為n-1的線性表（a1，a2，...，ai-1，ai+1，...，an）。具體算法描述如下：3）定位定位運算LocateSeqlist（SeqListL,DataTypex）的功能是查找出線性表L中值等于x的結點序號的最小值，當找不到值為x的結點時，返回結果0。下列算法從左往右掃描順序表中的元素，考察元素的值是否等于X，描述算法如下：2.2.3順序表實現(xiàn)算法的分析插入：O（n）刪除：O（n）定位：O（n）2.3線性表的鏈接存儲2.3.1單鏈表的類型定義線性表的鏈接存儲是指它的存儲結構是鏈式的。線性表常見的鏈式存儲結構有單鏈表、循環(huán)鏈表和雙向循環(huán)鏈表，其中最簡單的是單鏈表。下面舉個例子說明單鏈表的結構：單鏈表的一個結點由兩部分組成：數(shù)據(jù)元素和指針，相當于火車的車廂和車鉤。各個結點在內存中的存儲位置并不一定連續(xù)。鏈表的結點可以重新連接，相當于火車的編組。如圖所示，data部分稱為數(shù)據(jù)域，用于存儲線性表的一個數(shù)據(jù)元素，next部分稱為指針域或鏈域，用于存放一個指針，該指針指向本結點所含數(shù)據(jù)元素的直接后繼結點。非空的單鏈表和空單鏈表，如圖所示a）非空的單鏈表b）空單鏈表我們通常用結構體類型來定義單鏈表的結點數(shù)據(jù)類型：單鏈表的類型定義如下：Typedefstructnode{DataTypedata；//數(shù)據(jù)域structnode*next；//指針域}Node,*LinkList；【例2-2】學生檔案信息鏈表的類型完整描述則學生檔案信息鏈式存儲實現(xiàn)，如圖2-7所示為了便于運算實現(xiàn)，在單鏈表的第一個結點之前增設一個類型相同的結點，稱之為頭結點，其他結點稱為表結點。a）帶頭結點的非空單鏈表b）帶頭結點的空單鏈表2.3.2線性表的基本運算在單鏈表上的實現(xiàn)我們首先來討論單鏈表的一些基本運算，這是使用單鏈表的開始。初始化初始化的工作是建立一個空表，空表由一個頭指針和一個頭結點組成。算法描述如下：2.求表長在單鏈表存儲結構中，線性表的表長等于單鏈表中數(shù)據(jù)元素的結點個數(shù)，即除了頭結點以外的結點的個數(shù)。圖2-9所示為數(shù)據(jù)域為整數(shù)的單鏈表，其表長為4。通過結點的指針域來從頭至尾訪問每一個結點求表長，讓工作指針p通過指針域逐個結點向尾結點移動，工作指針每向尾部移動一個結點，讓計數(shù)器加1。這樣，直到工作指針p->next為NULL。算法描述如下：3.讀表元素通常給定一個序號i，查找線性表的第i個元素。從頭指針出發(fā)，一直往后移動，直到第i個結點。單鏈表的讀表元素算法描述如下：4.定位線性表的定位運算，就是對給定表元素的值，找出這個元素的位置。從頭至尾訪問鏈表，直至找到需要的結點，返回其序號。若未找到，返回0。定位運算算法描述如下：5.插入單鏈表的插入運算是將給定值為x的元素插入到鏈表head的第i個結點之前。插入結點的指針變化如圖2-10所示。插入算法描述如下：注意：p->next=q->next和q->next=p兩條語句的執(zhí)行順序不能顛倒。6.刪除刪除運算是給定一個值i,將鏈表中第i個結點從鏈表中移出，并修改相關結點的指針域，以維持剩余結點的鏈接關系。刪除結點的指針變化如圖2-11所示。單鏈表的刪除運算算法描述如下：注意，free（p）是必不可少的，無用結點需要釋放它的空間。2.4其他運算在單鏈表上的實現(xiàn)2.4.1建表我們討論建立含頭結點的單鏈表。方法一：尾插法，這個過程分為三部，首先建立帶頭結點的空表；其次建立一個新結點，然后將結點連接到頭結點之后；重復后面兩個步驟，直到線性表中所有元素鏈接到單鏈表中。代碼描述如下：方法二：上面的算法由于每次插入都從表頭開始查找，比較浪費時間。因為每次都是把新的結點鏈接到表尾，我們可以用一個指針指向尾結點，這樣就為下一個新結點指明了插入位置。代碼描述如下：方法中的鏈接操作如圖2-12，它的時間與元素個數(shù)成正比，故其時間復雜度為O（n）。圖2-12建表算法中的表尾鏈入操作方法三：頭插法，始終將新增加的結點插入到頭結點之后，第一個數(shù)據(jù)之前。如圖2-13所示。圖2-13建表算法中的在表頭鏈入操作代碼描述如下：2.4.2刪除重復結點在線性表中，可能有多個結點的元素值是相同的，它們是重復結點?？梢栽O計算法刪除重復結點，只保留結點序號最小的那個結點。例如，線性表（4，7，2，5，2，4），刪除重復結點后結果為（4，7，2，5）。用鏈表作為存儲結構，細化上述算法得到最后的算法描述：單鏈表上刪除結點時的指針變化如圖2-14所示：圖2-142.5其他鏈表2.5.1循環(huán)鏈表在單鏈表中，如果讓最后一個結點的指針域指向第一個結點可以構成循環(huán)鏈表。在循環(huán)鏈表中，從任一結點出發(fā)能夠掃描整個鏈表。圖2-15給出常見的循環(huán)鏈表，圖2-15a、b分別表示帶頭結點的非空循環(huán)鏈表和空循環(huán)鏈表，頭指針是head。在這種結構下，要找到尾結點可以從頭指針head出發(fā)掃描所有的結點。在圖2-15c、d中，鏈表沒有設頭指針，只設尾指針rear。這樣，首結點表示為：rear->next->next,首尾結點都能方便地訪問。圖2-15a）帶頭結點的非空循環(huán)鏈表b）帶頭結點的空循環(huán)鏈表c）設立尾指針的非空循環(huán)鏈表d）設立尾指針的空循環(huán)鏈表2.5.2雙向循環(huán)鏈表雙向循環(huán)鏈表的結點結構如圖2-16所示：圖2-16雙向循環(huán)鏈表結點結構雙向循環(huán)鏈表示意圖如圖2-17所示，prior與next類型相同，它指向直接前驅結點。頭結點的prior指向最后一個結點，最后一個結點的next指向頭結點。圖2-17雙向循環(huán)鏈表示意圖a）空表b）非空表雙向循環(huán)鏈表與單鏈表類似，用C語言描述如下：雙向循環(huán)鏈表是一種對稱結構，可以用下列等式表示：p=p->prior->next=p->next->prior在單鏈表中，找直接后繼結點的時間復雜度是O（1）。在雙向循環(huán)鏈表中，找直接后繼結點和前驅結點的時間復雜度都是O（1）。雙向循環(huán)鏈表的求表長、定位、按序查找等運算的實現(xiàn)和單鏈表基本相同，這里我們討論它的插入和刪除操作。1.刪除在單鏈表中刪除結點時，需要用一個指針指向待刪結點的前驅結點，在雙循環(huán)鏈表中，設p指向待刪結點，刪除*p可通過下述語句完成，執(zhí)行效果如圖2-18所示。（1）p->prior->next=p->next；//p前驅結點的后鏈指向p的后繼結點（2）p->next->prior=p->prior；//p后繼結點的前鏈指向p的前驅結點（3）free（p）；//釋放*p的空間（1）、（2）這兩個語句的執(zhí)行順序可以顛倒。圖2-18雙向循環(huán)鏈表上結點的刪除a）刪除結點*p之前b）刪除結點*p后2.插入在p所指結點的后面插入一個新結點*t，需要修改四個指針：（1）t->prior=p；（2）t->next=p->next；（3）p->next->prior=t；（4）p->next=t；插入操作過程如圖2-19所示，注意這些語句之間的順序。圖2-19雙向循環(huán)鏈表上結點的插入a）插入前b）插入后2.6順序實現(xiàn)與連接實現(xiàn)的比較查找：對于按位置查找運算，順序表是隨機存取，時間復雜度為O（1）。單鏈表需要對表元素進行掃描，它時間為復雜度為O（n）。定位：基本操作是比較，順序表和單鏈表上的實現(xiàn)算法的時間復雜度是相同的，均為O（n）插入和刪除：在順序表和鏈表中，都需要進行定位。在順序表中，其基本操作是元素的比較和結點的移動，平均時間復雜度為O（n）。在單鏈表中，由于需要定位，基本操作是元素的比較，盡管不需要移動結點，其平均時間復雜度仍然為O（n）。單鏈表的每個結點包括數(shù)據(jù)域與指針域，指針域需要占用額外空間。從整體考慮，順序表要預分配存儲空間，如果預先分配得過大，將造成浪費，若分配得過小，又將發(fā)生上溢；單鏈表不需要預先分配空間，只要內存空間沒有耗盡，單鏈表中的結點個數(shù)就沒有限制。三、考核的知識點與考核要求1.線性表概念識記：線性表概念；線性表的基本特征。領會：線性表表長；線性表初始化、求表長、讀表元素、定位、插入、刪除等基本運算的功能。2.線性表的順序存儲結構—順序表識記：順序表表示法、特點和類C語言描述。領會：順序表的容量；順序表表長；插入、刪除和定位運算實現(xiàn)的關鍵步驟。簡單應用：順序表插入、刪除和定位運算的實現(xiàn)算法。綜合應用：順序表上的簡單算法；順序表實現(xiàn)算法的分析。3.線性表的鏈式存儲結構—單鏈表識記：結點的結構；單鏈表的類C語言描述。領會：頭指針；頭結點；首結點；尾結點；空鏈表；單鏈表插入、刪除和定位運算的關鍵步驟。簡單應用：單鏈表插入、刪除和定位等基本運算的實現(xiàn)算法。綜合應用：用單鏈表設計解決應用問題的算法。4.循環(huán)鏈表和雙向循環(huán)鏈表識記：循環(huán)鏈表的結點結構；雙向循環(huán)鏈表結點結構；循環(huán)鏈表和雙向循環(huán)鏈表類C語言描述。領會：循環(huán)鏈表插入和刪除運算的關鍵步驟；雙向循環(huán)鏈表插入和刪除運算的關鍵步驟。四、本章重點、難點本章重點線性表概念和基本特征；線性表的基本運算；順序表和單鏈表的組織方法和算法設計。難點：單鏈表上的算法設計。五、練習【例題：單選題】若某線性表最常用的操作是在最后一個結點之后插入一個新結點或刪除最后一個結點，要使操作時間最少，應選擇（）存儲結構。A.無頭結點的單向鏈表B.帶頭結點的單向鏈表C.帶頭結點的雙循環(huán)鏈表D.帶頭結點的單循環(huán)鏈表『正確答案』C『答案解析』雙循環(huán)鏈表的找直接前驅和直接后繼結點的時間復雜度都是0（1）。參見教材P53。【例題：單選題】在表長為n的順序表上做刪除運算，其平均時間復雜度為（）。A.0（1）B.0（n）C.0（nlog2n）D.0（n2）『正確答案』B『答案解析』在順序表上做刪除運算，需要后續(xù)結點向前移動一個位置以保證順序表的連續(xù)。參見教材P39。【例題：單選題】在表長為n的順序表上做插入運算，平均要移動的點數(shù)為（）。A.n/4B.n/3C.n/2D.n『正確答案』C『答案解析』如果在順序表的尾部插入，則移動0個結點，如果在順序表的頭部插入，則移動n個結點。參見教材P39。【例題：單選題】若線性表最常用的操作是存取第i個元素及其前驅的值，那么最節(jié)省操作時間的存儲方式是（）。A.單鏈表B.雙向循環(huán)鏈表C.單循環(huán)鏈表D.順序表『正確答案』D『答案解析』順序表的特點是邏輯上相鄰的在物理存儲上也相鄰。參見教材P40?！纠}：單選題】設順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數(shù)為（）。A.5B.6C.7D.9『正確答案』C『答案解析』第三個元素前插入一個元素，即第3到9個元素都要移動，故答案是7。參見教材P39?！纠}：單選題】從一個長度為n的順序表中刪除第i個元素（1<=i<=n）時，需向前移動的元素個數(shù)為（）。A.n-iB.n-i+1C.n-i-1D.i『正確答案』A『答案解析』刪除第i個元素，則后面n-i個元素都要前移。參見教材P39。【例題：單選題】對于長度為n的順序表執(zhí)行刪除操作，則其結點的移動次數(shù)（）。A.最少為0，最多為nB.最少為1，最多為nC.最少為0，最多為n-1D.最少為1，最多為n-l『正確答案』C『答案解析』如果在順序表尾部刪除，移動次數(shù)為0，如果在順序表頭部刪除，移動次數(shù)為n-1。參見教材P40。【例題：單選題】設單鏈表中指針p指向結點A，要刪除A之后的結點（若存在），則修改指針的操作為（）。A.p->next=p->next->nextB.p=p->nextC.p=p->next—>nextD.p->next=p『正確答案』A『答案解析』要刪除A之后的結點，即將A的指針域指向A之后的結點的下一個結點。參見教材P47?！纠}：填空題】設r指向單鏈表的最后一個結點，要在最后一個結點之后插入S所指的結點，需執(zhí)行的語句序列是________；r=s；r->next=NULL。『正確答案』r->next=s『答案解析』在單鏈表中用尾插法插入一個結點，將尾結點的指針域指向待插結點，帶插結點的指針域指向NULL。參見教材P46?！纠}：填空題】在單鏈表中，指針p所指的結點為最后一個結點的條件是（）?！赫_答案』p->next==NULL『答案解析』最后一個結點的指針域指向空。參見教材P42?！纠}：填空題】在帶頭結點的單鏈表L中，第一個數(shù)據(jù)元素結點的指針為（）?！赫_答案』L->next『答案解析』本題考察對單鏈表結點結構的理解。參見教材P41。【例題：填空題】在雙向循環(huán)鏈表中，在指針p所指結點前插入指針s所指的結點，需執(zhí)行下列語句：s->next=p；s->prior=p->prior；p->prior=s；___________=s?！赫_答案』（s->prior）->next『答案解析』在雙向循環(huán)鏈表中插入一個結點，需要做四件事情：待插結點后指針域指向P結點，P的前指針域指向待插結點；帶插結點的前指針域指向P的前驅結點；P的前驅結點的后指針域指向待插結點。參見教材P53?！纠}：填空題】帶頭結點的雙向循環(huán)鏈表L為空的條件是___________。『正確答案』（L->next==L）&&（L->prior==L）『答案解析』判斷雙向循環(huán)鏈表為空的條件是前指針域和后指針域都指向NULL。參見教材P52。第二章線性表一、學習目的與要求順序表和單鏈表分別是簡單、基本的順序存儲結構和鏈式存儲結構。順序表和單鏈表上實現(xiàn)基本運算的算法是數(shù)據(jù)結構中簡單和基本的算法。這些內容構成以下各章的重要基礎，因此本章是本課程的重點之一。本章要求：理解線性表的概念；熟練掌握順序表和鏈表的組織方法及實現(xiàn)基本運算的算法；掌握在順序表和鏈表上進行算法設計的基本技能；了解順序表與鏈表的優(yōu)缺點。二、課程內容2.1線性表的基本概念線性表中結點具有一對一的關系，如果結點數(shù)不為零，則除起始結點沒有直接前驅外，其他每個結點有且僅有一個直接前驅；除終端結點沒有直接后繼外，其他每個結點有且僅有一個直接后繼。線性表基本運算有：初始化、求表長、讀表元素、定位、插入、刪除。2.2線性表的順序存儲2.2.1線性表的順序存儲線性表的順序存儲：邏輯結構相鄰的結點其存儲位置也相鄰。用順序存儲實現(xiàn)的線性表稱為順序表，一般用數(shù)組來表示順序表，如圖2-1所示【例2-1】學生檔案信息表的順序存儲實現(xiàn)?！痉治觥扛鶕?jù)學生檔案信息，給出順序表具體的類型定義。2.2.2線性表的基本運算在順序表上的實現(xiàn)插入順序表的插入運算InsertSeqlist（SeqListL,DataTypex,inti）是指在順序表的第i（1<=i<=n+1）個元素之前，插入一個新元素x。使長度為n的線性表（a1，a2，...，ai-1，ai，...，an）變?yōu)殚L度為n+1的線性表（a1，a2，...，ai-1，x，ai，...，an）。具體算法描述如下：2）刪除刪除運算DeleteSeqlist（SeqListL，inti）是指將線性表的第i（1<=i<=n）個數(shù)據(jù)元素刪去，使長度為n的線性表（a1，a2，...，ai-1，ai，ai+1，...，an）變?yōu)殚L度為n-1的線性表（a1，a2，...，ai-1，ai+1，...，an）。具體算法描述如下：3）定位定位運算LocateSeqlist（SeqListL,DataTypex）的功能是查找出線性表L中值等于x的結點序號的最小值，當找不到值為x的結點時，返回結果0。下列算法從左往右掃描順序表中的元素，考察元素的值是否等于X，描述算法如下：2.2.3順序表實現(xiàn)算法的分析插入：O（n）刪除：O（n）定位：O（n）2.3線性表的鏈接存儲2.3.1單鏈表的類型定義線性表的鏈接存儲是指它的存儲結構是鏈式的。線性表常見的鏈式存儲結構有單鏈表、循環(huán)鏈表和雙向循環(huán)鏈表，其中最簡單的是單鏈表。下面舉個例子說明單鏈表的結構：單鏈表的一個結點由兩部分組成：數(shù)據(jù)元素和指針，相當于火車的車廂和車鉤。各個結點在內存中的存儲位置并不一定連續(xù)。鏈表的結點可以重新連接，相當于火車的編組。如圖所示，data部分稱為數(shù)據(jù)域，用于存儲線性表的一個數(shù)據(jù)元素，next部分稱為指針域或鏈域，用于存放一個指針，該指針指向本結點所含數(shù)據(jù)元素的直接后繼結點。非空的單鏈表和空單鏈表，如圖所示a）非空的單鏈表b）空單鏈表我們通常用結構體類型來定義單鏈表的結點數(shù)據(jù)類型：單鏈表的類型定義如下：Typedefstructnode{DataTypedata；//數(shù)據(jù)域structnode*next；//指針域}Node,*LinkList；【例2-2】學生檔案信息鏈表的類型完整描述則學生檔案信息鏈式存儲實現(xiàn)，如圖2-7所示為了便于運算實現(xiàn)，在單鏈表的第一個結點之前增設一個類型相同的結點，稱之為頭結點，其他結點稱為表結點。a）帶頭結點的非空單鏈表b）帶頭結點的空單鏈表2.3.2線性表的基本運算在單鏈表上的實現(xiàn)我們首先來討論單鏈表的一些基本運算，這是使用單鏈表的開始。初始化初始化的工作是建立一個空表，空表由一個頭指針和一個頭結點組成。算法描述如下：2.求表長在單鏈表存儲結構中，線性表的表長等于單鏈表中數(shù)據(jù)元素的結點個數(shù)，即除了頭結點以外的結點的個數(shù)。圖2-9所示為數(shù)據(jù)域為整數(shù)的單鏈表，其表長為4。通過結點的指針域來從頭至尾訪問每一個結點求表長，讓工作指針p通過指針域逐個結點向尾結點移動，工作指針每向尾部移動一個結點，讓計數(shù)器加1。這樣，直到工作指針p->next為NULL。算法描述如下：3.讀表元素通常給定一個序號i，查找線性表的第i個元素。從頭指針出發(fā)，一直往后移動，直到第i個結點。單鏈表的讀表元素算法描述如下：4.定位線性表的定位運算，就是對給定表元素的值，找出這個元素的位置。從頭至尾訪問鏈表，直至找到需要的結點，返回其序號。若未找到，返回0。定位運算算法描述如下：5.插入單鏈表的插入運算是將給定值為x的元素插入到鏈表head的第i個結點之前。插入結點的指針變化如圖2-10所示。插入算法描述如下：注意：p->next=q->next和q->next=p兩條語句的執(zhí)行順序不能顛倒。6.刪除刪除運算是給定一個值i,將鏈表中第i個結點從鏈表中移出，并修改相關結點的指針域，以維持剩余結點的鏈接關系。刪除結點的指針變化如圖2-11所示。單鏈表的刪除運算算法描述如下：注意，free（p）是必不可少的，無用結點需要釋放它的空間。2.4其他運算在單鏈表上的實現(xiàn)2.4.1建表我們討論建立含頭結點的單鏈表。方法一：尾插法，這個過程分為三部，首先建立帶頭結點的空表；其次建立一個新結點，然后將結點連接到頭結點之后；重復后面兩個步驟，直到線性表中所有元素鏈接到單鏈表中。代碼描述如下：方法二：上面的算法由于每次插入都從表頭開始查找，比較浪費時間。因為每次都是把新的結點鏈接到表尾，我們可以用一個指針指向尾結點，這樣就為下一個新結點指明了插入位置。代碼描述如下：方法中的鏈接操作如圖2-12，它的時間與元素個數(shù)成正比，故其時間復雜度為O（n）。圖2-12建表算法中的表尾鏈入操作方法三：頭插法，始終將新增加的結點插入到頭結點之后，第一個數(shù)據(jù)之前。如圖2-13所示。圖2-13建表算法中的在表頭鏈入操作代碼描述如下：2.4.2刪除重復結點在線性表中，可能有多個結點的元素值是相同的，它們是重復結點?？梢栽O計算法刪除重復結點，只保留結點序號最小的那個結點。例如，線性表（4，7，2，5，2，4），刪除重復結點后結果為（4，7，2，5）。用鏈表作為存儲結構，細化上述算法得到最后的算法描述：單鏈表上刪除結點時的指針變化如圖2-14所示：圖2-142.5其他鏈表2.5.1循環(huán)鏈表在單鏈表中，如果讓最后一個結點的指針域指向第一個結點可以構成循環(huán)鏈表。在循環(huán)鏈表中，從任一結點出發(fā)能夠掃描整個鏈表。圖2-15給出常見的循環(huán)鏈表，圖2-15a、b分別表示帶頭結點的非空循環(huán)鏈表和空循環(huán)鏈表，頭指針是head。在這種結構下，要找到尾結點可以從頭指針head出發(fā)掃描所有的結點。在圖2-15c、d中，鏈表沒有設頭指針，只設尾指針rear。這樣，首結點表示為：rear->next->next,首尾結點都能方便地訪問。圖2-15a）帶頭結點的非空循環(huán)鏈表b）帶頭結點的空循環(huán)鏈表c）設立尾指針的非空循環(huán)鏈表d）設立尾指針的空循環(huán)鏈表2.5.2雙向循環(huán)鏈表雙向循環(huán)鏈表的結點結構如圖2-16所示：圖2-16雙向循環(huán)鏈表結點結構雙向循環(huán)鏈表示意圖如圖2-17所示，prior與next類型相同，它指向直接前驅結點。頭結點的prior指向最后一個結點，最后一個結點的next指向頭結點。圖2-17雙向循環(huán)鏈表示意圖a）空表b）非空表雙向循環(huán)鏈表與單鏈表類似，用C語言描述如下：雙向循環(huán)鏈表是一種對稱結構，可以用下列等式表示：p=p->prior->next=p->next->prior在單鏈表中，找直接后繼結點的時間復雜度是O（1）。在雙向循環(huán)鏈表中，找直接后繼結點和前驅結點的時間復雜度都是O（1）。雙向循環(huán)鏈表的求表長、定位、按序查找等運算的實現(xiàn)和單鏈表基本相同，這里我們討論它的插入和刪除操作。1.刪除在單鏈表中刪除結點時，需要用一個指針指向待刪結點的前驅結點，在雙循環(huán)鏈表中，設p指向待刪結點，刪除*p可通過下述語句完成，執(zhí)行效果如圖2-18所示。（1）p->prior->next=p->next；//p前驅結點的后鏈指向p的后繼結點（2）p->next->prior=p->prior；//p后繼結點的前鏈指向p的前驅結點（3）free（p）；//釋放*p的空間（1）、（2）這兩個語句的執(zhí)行順序可以顛倒。圖2-18雙向循環(huán)鏈表上結點的刪除a）刪除結點*p之前b）刪除結點*p后2.插入在p所指結點的后面插入一個新結點*t，需要修改四個指針：（1）t->prior=p；（2）t->next=p->next；（3）p->next->prior=t；（4）p->next=t；插入操作過程如圖2-19所示，注意這些語句之間的順序。圖2-19雙向循環(huán)鏈表上結點的插入a）插入前b）插入后2.6順序實現(xiàn)與連接實現(xiàn)的比較查找：對于按位置查找運算，順序表是隨機存取，時間復雜度為O（1）。單鏈表需要對表元素進行掃描，它時間為復雜度為O（n）。定位：基本操作是比較，順序表和單鏈表上的實現(xiàn)算法的時間復雜度是相同的，均為O（n）插入和刪除：在順序表和鏈表中，都需要進行定位。在順序表中，其基本操作是元素的比較和結點的移動，平均時間復雜度為O（n）。在單鏈表中，由于需要定位，基本操作是元素的比較，盡管不需要移動結點，其平均時間復雜度仍然為O（n）。單鏈表的每個結點包括數(shù)據(jù)域與指針域，指針域需要占用額外空間。從整體考慮，順序表要預分配存儲空間，如果預先分配得過大，將造成浪費，若分配得過小，又將發(fā)生上溢；單鏈表不需要預先分配空間，只要內存空間沒有耗盡，單鏈表中的結點個數(shù)就沒有限制。三、考核的知識點與考核要求1.線性表概念識記：線性表概念；線性表的基本特征。領會：線性表表長；線性表初始化、求表長、讀表元素、定位、插入、刪除等基本運算的功能。2.線性表的順序存儲結構—順序表識記：順序表表示法、特點和類C語言描述。領會：順序表的容量；順序表表長；插入、刪除和定位運算實現(xiàn)的關鍵步驟。簡單應用：順序表插入、刪除和定位運算的實現(xiàn)算法。綜合應用：順序表上的簡單算法；順序表實現(xiàn)算法的分析。3.線性表的鏈式存儲結構—單鏈表識記：結點的結構；單鏈表的類C語言描述。領會：頭指針；頭結點；首結點；尾結點；空鏈表；單鏈表插入、刪除和定位運算的關鍵步驟。簡單應用：單鏈表插入、刪除和定位等基本運算的實現(xiàn)算法。綜合應用：用單鏈表設計解決應用問題的算法。4.循環(huán)鏈表和雙向循環(huán)鏈表識記：循環(huán)鏈表的結點結構；雙向循環(huán)鏈表結點結構；循環(huán)鏈表和雙向循環(huán)鏈表類C語言描述。領會：循環(huán)鏈表插入和刪除運算的關鍵步驟；雙向循環(huán)鏈表插入和刪除運算的關鍵步驟。四、本章重點、難點本章重點線性表概念和基本特征；線性表的基本運算；順序表和單鏈表的組織方法和算法設計。難點：單鏈表上的算法設計。五、練習【例題：單選題】若某線性表最常用的操作是在最后一個結點之后插入一個新結點或刪除最后一個結點，要使操作時間最少，應選擇（）存儲結構。A.無頭結點的單向鏈表B.帶頭結點的單向鏈表C.帶頭結點的雙循環(huán)鏈表D.帶頭結點的單循環(huán)鏈表『正確答案』C『答案解析』雙循環(huán)鏈表的找直接前驅和直接后繼結點的時間復雜度都是0（1）。參見教材P53?！纠}：單選題】在表長為n的順序表上做刪除運算，其平均時間復雜度為（）。A.0（1）B.0（n）C.0（nlog2n）D.0（n2）『正確答案』B『答案解析』在順序表上做刪除運算，需要后續(xù)結點向前移動一個位置以保證順序表的連續(xù)。參見教材P39。【例題：單選題】在表長為n的順序表上做插入運算，平均要移動的點數(shù)為（）。A.n/4B.n/3C.n/2D.n『正確答案』C『答案解析』如果在順序表的尾部插入，則移動0個結點，如果在順序表的頭部插入，則移動n個結點。參見教材P39?！纠}：單選題】若線性表最常用的操作是存取第i個元素及其前驅的值，那么最節(jié)省操作時間的存儲方式是（）。A.單鏈表B.雙向循環(huán)鏈表C.單循環(huán)鏈表D.順序表『正確答案』D『答案解析』順序表的特點是邏輯上相鄰的在物理存儲上也相鄰。參見教材P40。【例題：單選題】設順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數(shù)為（）。A.5B.6C.7D.9『正確答案』C『答案解析』第三個元素前插入一個元素，即第3到9個元素都要移動，故答案是7。參見教材P39?！纠}：單選題】從一個長度為n的順序表中刪除第i個元素（1<=i<=n）時，需向前移動的元素個數(shù)為（）。A.n-iB.n-i+1C.n-i-1D.i『正確答案』A『答案解析』刪除第i個元素，則后面n-i個元素都要前移。參見教材P39?！纠}：單選題】對于長度為n的順序表執(zhí)行刪除操作，則其結點的移動次數(shù)（）。A.最少為0，最多為nB.最少為1，最多為nC.最少為0，最多為n-1D.最少為1，最多為n-l『正確答案』C『答案解析』如果在順序表尾部刪除，移動次數(shù)為0，如果在順序表頭部刪除，移動次數(shù)為n-1。參見教材P40。【例題：單選題】設單鏈表中指針p指向結點A，要刪除A之后的結點（若存在），則修改指針的操作為（）。A.p->next=p->next->nextB.p=p->nextC.p=p->next—>nextD.p->next=p『正確答案』A『答案解析』要刪除A之后的結點，即將A的指針域指向A之后的結點的下一個結點。參見教材P47?！纠}：填空題】設r指向單鏈表的最后一個結點，要在最后一個結點之后插入S所指的結點，需執(zhí)行的語句序列是________；r=s；r->next=NULL?！赫_答案』r->next=s『答案解析』在單鏈表中用尾插法插入一個結點，將尾結點的指針域指向待插結點，帶插結點的指針域指向NULL。參見教材P46?！纠}：填空題】在單鏈表中，指針p所指的結點為最后一個結點的條件是（）。『正確答案』p->next==NULL『答案解析』最后一個結點的指針域指向空。參見教材P42?！纠}：填空題】在帶頭結點的單鏈表L中，第一個數(shù)據(jù)元素結點的指針為（）?！赫_答案』L->next『答案解析』本題考察對單鏈表結點結構的理解。參見教材P41?！纠}：填空題】在雙向循環(huán)鏈表中，在指針p所指結點前插入指針s所指的結點，需執(zhí)行下列語句：s->next=p；s->prior=p->prior；p->prior=s；___________=s。『正確答案』（s->prior）->next『答案解析』在雙向循環(huán)鏈表中插入一個結點，需要做四件事情：待插結點后指針域指向P結點，P的前指針域指向待插結點；帶插結點的前指針域指向P的前驅結點；P的前驅結點的后指針域指向待插結點。參見教材P53?！纠}：填空題】帶頭結點的雙向循環(huán)鏈表L為空的條件是___________?！赫_答案』（L->next==L）&&（L->prior==L）『答案解析』判斷雙向循環(huán)鏈表為空的條件是前指針域和后指針域都指向NULL。參見教材P52。第四章樹和二叉樹—、學習目的與要求樹形結構用于表示具有分支和層次結構，有著廣泛的應用背景。樹和二叉樹是重要的樹形結構。本章總的要求是：理解樹形結構的基本概念和術語；深刻領會二叉樹的定義及其存儲結構，理解二叉樹的遍歷的概念并掌握二叉樹的遍歷算法；掌握樹和森林的定義、樹的存儲結構以及樹、森林與二叉樹之間的相互轉換方法；熟練掌握構造哈夫曼樹和設計哈夫曼編碼的方法。二、課程內容4.1樹的基本概念4.1.1樹的概念線性結構中的一個結點至多只有一個直接后繼，而樹形結構中一個結點可以有一個或多個直接后繼。例圖4－1所示的樹形結構老虎家族關系。樹（Tree）是一類重要的數(shù)據(jù)結構，其定義如下：樹是n（n≥0）個結點的有限集合，一棵樹滿足以下兩個條件：（1）當n=0時，稱為空樹；（2）當n>0時，有且僅有一個稱為根的結點，除根結點外，其余結點分為m（m≥0）個互不相交的非空集合T1，T2，…，Tm，這些集合中的每一個都是一棵樹，稱為根的子樹。如圖4－2所示的幾種結構都不是樹。4.1.2樹的相關術語結點的度：樹上任一結點所擁有的子樹的數(shù)目稱為該結點的度。葉子：度為0的結點稱為葉子或終端結點。樹的度：一棵樹中所有結點的度的最大值稱為該樹的度。一個結點的子樹的根稱為該結點的孩子（或稱子結點）。相應地該結點稱為孩子的雙親（也稱父結點）。結點的層次：從根開始算起，根的層次為1，其余結點的層次為其雙親的層次加1。樹的高度：一棵樹中所有結點層次數(shù)的最大值稱為該樹的高度或深度。有序樹：若樹中各結點的子樹從左到右是有次序的，不能互換，稱為有序樹。有序樹中最左邊子樹的根稱為第1個孩子，左邊第i個子樹的根稱為第i個孩子。無序樹：若樹中各結點的子樹是無次序的，可以互換，則稱為無序樹。樹的基本運算有：（1）求根（2）求雙親（3）求孩子（4）建樹（5）剪枝（6）遍歷4.2二叉樹4.2.1二叉樹的基本概念二叉樹（BinaryTree）是n（n≥0）個元素的有限集合，該集合或者為空，或者由一個根及兩棵互不相交的左子樹和右子樹組成，其中左子樹和右子樹也均為二叉樹。二叉樹的任一結點都有兩棵子樹（它們中的任何一個都可以是空子樹），并且這兩棵子樹之間有次序關系。如圖4－3a、b、c分別是含兩個結點A、B且以A為根的二叉樹和樹的示意圖。a）右子樹為空的二叉樹b）左子樹為空的二叉樹c）含一棵子樹的樹二叉樹有五種基本形態(tài)如圖4－4所示其中方塊表示子樹a）空二叉樹b）左右子樹均為空的二叉樹c）右子樹為空的二叉樹d）左子樹為空的二叉樹e）左、右子樹都非空的二叉樹二叉樹的基本運算：（1）初始化（2）求雙親（3）求左孩子（4）建立二叉樹（5）先序遍歷（6）中序遍歷（7）后序遍歷（8）層序遍歷4.2.2二叉樹的性質性質1：二叉樹第i（i≥1）層上至多有2i-1個結點。性質2：深度為k（k≥1）的二叉樹至多有2k-1個結點。性質3：對任何一棵二叉樹，若度數(shù)為0的結點（葉結點）個數(shù)為n0，度數(shù)為2的結點個數(shù)為n2，則n0=n2+1。滿二叉樹：深度為k（k≥1）且有2k-1個結點的二叉樹稱為滿二叉樹。完全二叉樹：如果對滿二叉樹按從上到下，從左到右的順序編號，并在最下一層刪去部分結點（刪后最后一層仍有結點），如果刪除的這些結點的編號是連續(xù)的且刪除的結點中含有最大編號的結點，那么這棵二叉樹就是完全二叉樹。圖4－5滿二叉樹、完全二叉樹和非完全二叉樹a）滿二叉樹b）完全二叉樹c）非完全二叉樹d）非完全二叉樹對于完全二叉樹，還有以下兩個重要性質：性質4：含有n個結點的完全二叉樹的深度為。性質5：如果將一棵有n個結點的完全二叉樹按層編號，按層編號是指：將一棵二叉樹中的所有n個結點按從第一層到最大層，每層從左到右的順序依次標記為1，2，…，n。則對任一編號為i（1≤i≤n）的結點A有：（1）若i=1，則結點A是根；若i>1，則A的雙親Parent（A）的編號為；（2）若2*i>n，則結點A既無左孩子，也無右孩子；否則A的左孩子Lchild（X）的編號為2*i；（3）若2*i＋1>n，則結點A無右孩子；否則，A的右孩子Rchild（A）的編號為2*i＋1。圖4－6完全二叉樹上父、子結點編號之間的關系a）i為偶數(shù)b）i為奇數(shù)4.3二叉樹的存儲結構二叉樹通常有兩類存儲結構：順序存儲結構和鏈式存儲結構。4.3.1二叉樹的順序存儲結構二叉樹的順序存儲結構可以用一維數(shù)組來實現(xiàn)，二叉樹上的結點按某種次序分別存入該數(shù)組的各個單元中。圖4－7為完全二叉樹的順序存儲，圖4－8為非完全二叉樹的順序實現(xiàn)。圖4－7完全二叉樹的順序存儲示例a）—棵完全二叉樹b）順序存儲示意圖4－8非完全二叉樹的順序實現(xiàn)a）—棵非完全二叉樹BTb）增設虛擬結點后的BTc）BT的一種不恰當?shù)捻樞虼鎯）BT的順序存儲4.3.2二叉樹的鏈式存儲結構二叉樹有不同的鏈式存儲結構，其中最常用的是二叉鏈表與三叉鏈表。二叉鏈表和三叉鏈表的結點形式如圖4－9a、b所示。圖4－9二叉鏈表和三叉鏈表結點結構a）二叉鏈表的結點b）三叉鏈表的結點二叉鏈表的類型定義如下：typedefstructbtnode{DataTypedata;//指向左右孩子的指針structbtnode*lchild,*rchild;}*BinTree;三叉鏈表的類型定義如下：typedefstructttnode{datatypedata;structttnode*lchild,*parent,*rchild;}*TBinTree;TBinTreeroot;二叉樹的鏈式存儲示意圖如圖4－10所示：圖4－10二叉樹的鏈式存儲結構a）一棵二叉樹b）二叉鏈表示意c）三叉鏈表示意4.4二叉樹的遍歷4.4.1二叉樹遍歷的遞歸實現(xiàn)二叉樹的遍歷是指按某種次序訪問二叉樹上的所有結點，使每個結點被訪問一次且僅被訪問一次。1.先序遍歷若被遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。2.中序遍歷.若被遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。3.后序遍歷若被遍歷的二叉樹為空，執(zhí)行空操作；否則，依次執(zhí)行下列操作：（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點?！纠?－1】分別給出圖4－11a的二叉樹先序遍歷、中序遍歷、后序遍歷三種訪問方式的結點訪問序列。圖4－11二叉樹及其劃分a）二叉樹b）二叉樹劃分得到先序遍歷的結點序列是：ABDEGCF得到中序遍歷的結點序列是：DBGEACF得到后序遍歷的結點序列是：DGEBFCA三種遍歷的遞歸算法描述先序：voidpreorder（BinTreebt）{if（bt!=NULL）{visit（bt）;//訪問根節(jié)點btpreorder（bt->lchild）;//先序遍歷左子樹preorder（bt->rchild）;//先序遍歷右子樹}}中序：voidinorder（BinTreebt）{if（bt!=NULL）{inorder（bt->lchild）;//中序遍歷左子樹visit（bt）;//訪問根節(jié)點btinorder（bt->rchild）;//中序遍歷右子樹}}后序：voidpostorder（BinTreebt）{if（bt!=NULL）{postorder（bt->lchild）;//后序遍歷左子樹postorder（bt->rchild）;//后序遍歷右子樹visit（bt）;//訪問根節(jié)點bt}}4.4.2二叉樹的層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的根結點的這一層開始，逐層向下遍歷，在每一層上按從左到右的順序對結點逐個訪問。該二叉樹按層次遍歷所得到的結點序列為A、B、C、D、E、F。4.4.3應用舉例【案例】假設一棵二叉樹的中序序列與后序序列分別為：BACDEFGH和BCAEDGHF，建立該二叉樹。4.5樹和森林4.5.1樹的存儲結構1.孩子鏈表表示法孩子鏈表表示法是樹的一種鏈式存儲結構。它的主體是一個數(shù)組元素個數(shù)和樹中結點個數(shù)相同的一維數(shù)組。樹上的一個結點X以及該結點的所有孩子結點組成一個帶頭結點的單鏈表，單鏈表的頭結點含有兩個域：數(shù)據(jù)域和指針域。其中，數(shù)據(jù)域用于存儲結點X中的數(shù)據(jù)元素，指針域用于存儲指向X第一個孩子結點的指針。2.孩子兄弟鏈表表示法存儲時每個結點除了數(shù)據(jù)域外，還有指向該結點的第一個孩子和下一個兄弟結點的指針。結點結構如圖4－14所示。二叉鏈表中結點的左、右指針分別指向左、右孩子；而孩子兄弟鏈表中結點的兩個指針分別指向孩子和兄弟。3.雙親表示法雙親表示法由一個一維數(shù)組構成。數(shù)組的每個分量包含兩個域：數(shù)據(jù)域和雙親域。數(shù)據(jù)域用于存儲樹上一個結點中數(shù)據(jù)元素，雙親域用于存儲本結點的雙親結點在數(shù)組中的序號（下標值）。圖4－13a中樹的雙親表示法如圖4－16所示。4.5.2樹、森林與二叉樹的關系1.樹轉換為二叉樹任何一棵樹可唯一地與一棵二叉樹對應。相應地，一棵二叉樹也唯一地對應一棵樹，即樹與二叉樹可以互相轉換。將樹轉換成二叉樹的方法如下：（1）將所有兄弟結點連接起來；（2）保留第一個兄弟結點與父結點的連接，斷開其他兄弟結點與父結點的連接，然后以根結點為軸心按順時針的方向旋轉45°角。2.森林轉換為二叉樹森林F轉換成二叉樹的方法如下：（1）將每棵樹轉換成相應的二叉樹；（2）將（1）中得到的各棵二叉樹的根結點看作是兄弟連接起來。圖4－18為森林轉換到二叉樹的過程。a）森林Fb）與樹T1對應的二叉樹c）與樹T2對應的二叉樹d）與T3對應的二叉樹e）與F對應的二叉樹3.二叉樹轉換為森林將二叉樹轉換成對應的森林的方法如下：（1）在待轉換的二叉樹中，斷開根結點與右孩子的連線，得到兩棵二叉樹，其中一棵是以二叉樹B的根結點為根的二叉樹，另一棵是以根結點的右孩子E為根結點的二叉樹。圖4－19a中，斷開A與E的連線后得到兩棵如圖4－19b所示兩棵的二叉樹B1和B2。（2）在二叉樹B1中，連接A與C，A與D。然后將B和C的連線斷開，C和D的連線斷開。（3）重復步驟（1）（2）對B2進行轉換。a）二叉樹Bb）第一次轉換結果c）第二次轉換結果d）第三次轉換結果4.5.3樹與森林的遍歷1.樹的遍歷與二叉樹類似，這里我們定義樹的先序遍歷、后序遍歷和層次遍歷。（1）先序遍歷：①訪問根結點；②依次先序遍歷根的各棵子樹T1，…，Tm。對圖4－13a所示的樹來說，先序遍歷得到結點訪問序列為H，A，B，E，G，F(xiàn)，D，C；（2）后序遍歷①依次后序遍歷根的各棵子樹T1，…，Tm；②訪問根結點。對圖4－13a所示的樹來說，后序遍歷得到結點訪問序列為B，G，F(xiàn)，D，E，A，C，H；（3）層序遍歷①若樹非空，訪問根結點；②若第i（i≥1）層結點已被訪問，第i＋1層結點尚未訪問，則從左到右依次訪問第i＋1層結點。對圖4－13a所示的樹來說，層次遍歷得到結點訪問序列為H，A，C，B，E，G，F(xiàn)，D。2.森林的遍歷森林有兩種遍歷方法：（1）先序遍歷森林。若森林非空，則①訪問森林中第一棵樹的根結點；②先序遍歷森林第一棵樹的根結點的子樹組成的森林；③先序遍歷除去第一棵樹之外其余的樹組成的森林。對圖4－18a中的森林進行先序遍歷，得到的先序序列為ABCDEFGHJI。（2）中序遍歷森林。若森林非空，則①中序遍歷森林中第一棵樹的根結點的子樹組成的森林；②訪問第一棵樹的根結點；③中序遍歷除去第一棵樹之外其余的樹組成的森林。對圖4－18a中的森林進行中序遍歷，得到的中序序列為BCDAFEJHIG。4.6判定樹和哈夫曼樹4.6.1分類與判定樹類別ABCD年齡值age/歲age<1818≤age<4545≤age<60age≥60百分比（%）0.20.30.250.25表4－1人口按年齡分類問題用于描述分類過程的二叉樹稱為判定樹。對上述分類問題可以畫出兩棵不同的判定樹，如圖4－20所示。4.6.2哈夫曼樹與哈夫曼算法我們來討論如何構造一棵哈夫曼樹，（1）由給定的值{pi，…，pk）構造森林F={Ti，…，Tk}，其中每個Ti為一棵只有根結點且其權為Pi的二叉樹。（2）從F中選取根結點的權最小的兩棵二叉樹Ti和Tj，構造一棵分別以Ti和Tj為左、右子樹的新的二叉樹Th，置Th根結點的權為Ti、Tj根結點的權值之和。（3）從F中刪去Ti、Tj，并將Th加入F。若F中仍多于一棵二叉樹，則返回②，直到F中只含一棵二叉樹為止，這棵二叉樹就是哈夫曼樹。4.6.3哈夫曼編碼通常希望字符在傳輸過程中總的編碼長度越短越好。考慮到一個待傳輸?shù)奈谋局胁煌址霈F(xiàn)的頻率是不同的，直觀的想法是讓出現(xiàn)頻率較多的字符采用較短的編碼，則傳輸?shù)淖址偩幋a長度會減少。用哈夫曼樹就可以解決這一問題。將{p1，……，pn}作為一組葉結點的權值，用哈夫曼算法，可以構造出一棵具有最小帶權路徑長度的二叉樹。將該二叉樹中每個結點的左分支標志為“0”，每個結點的右分支標志為“1”，這樣，從根到每個葉結點形成“0”/“1”序列，將該序列作為葉結點對應字符的編碼，由此得到的二進制編碼稱為哈夫曼編碼?！景咐吭O某通信系統(tǒng)中一個待傳輸?shù)奈谋居?個不同字符，它們的出現(xiàn)頻率分別是0.5，0.8，1.4，2.2，2.3，2.8，試設計哈夫曼編碼?！痉治觥坑深}意，共有n=6個不同的字符，字符的頻率序列為p={0.5，0.8，1.4，2.2，2.3，2.8}，以這些頻率作為權值，構造一棵哈夫曼樹，并對其進行哈夫曼編碼，結果如圖4－22所示。出現(xiàn)頻率為0.5的字符編碼為1000出現(xiàn)頻率為0.8的字符編碼為1001出現(xiàn)頻率為1.4的字符編碼為101出現(xiàn)頻率為2.2的字符編碼為00出現(xiàn)頻率為2.3的字符編碼為01出現(xiàn)頻率為2.8的字符編碼為11三、考核的知識點與考核要求1.樹結構、森林識記：樹的基本概念；術語；森林基本概念。領會：樹的基本運算。簡單應用：結點的度計算；樹的度計算；樹的高度計算；結點的層次數(shù)計算。2.二叉樹識記：二叉樹的概念；左子樹；右子樹。領會：二叉樹的基本運算；二叉樹的性質；二叉樹順序存儲及類C語言描述；二叉樹鏈式存儲及類C語言描述；二叉樹的遍歷算法。簡單應用：二叉樹結點數(shù)計算；二叉樹深度計算；給出二叉樹先序序列、中序序列和后序序列；由二叉樹先序序列、中序序列和后序序列構造二叉樹。綜合應用：設計二叉樹上基于先序遍歷、中序遍歷和后序遍歷的應用算法。3.樹和森林識記：樹的先序遍歷方法；樹的后序遍歷方法；樹的層次遍歷方法；森林的先序遍歷方法；森林的中序遍歷方法。領會：樹、森林與二叉樹的關系；樹轉換成二叉樹方法；森林轉換成二叉樹方法；二叉樹轉換成對應森林方法。4.判定樹和哈夫曼樹識記：判定樹概念；哈夫曼樹概念；哈夫曼編碼。領會：分類與判定樹的關系；哈夫曼樹構造過程；哈夫曼算法。簡單應用：由一組葉結點的權值構造一棵對應的哈夫曼樹，設計哈夫曼編碼。四、本章重點、難點本章重點：樹形結構的概念；二叉樹的定義、存儲結構和遍歷算法。本章難點：二叉樹的遍歷算法和哈夫曼樹構造算法。五、練習【例題：單選】具有n個結點的完全二叉數(shù)的深度是（）?！赫_答案』C『答案解析』參照二叉樹的性質4。參考教材P98【例題：單選】已知二叉樹的先序遍歷序列為ABCFHIDGJE，中序遍歷序列為AHIFCJGDEB，其后序遍歷序列為（）。A.IHFJGEDBCAB.HIFJGEDCBAC.IHFJGEDCBAD.IHFCBJGEDA『正確答案』C『答案解析』我們可以根據(jù)二叉樹的中序遍歷和先序遍歷，或者中序遍歷和后序遍歷得出一個二叉樹。參考教材P104【例題：單選】深度為6（根的層次為1）的二叉樹至多有（）個結點。A.64B.32C.31D.63『正確答案』D『答案解析』當該二叉樹為滿二叉樹時結點個數(shù)最多，為2k-1，其中k為二叉樹的深度。參考教材P97【例題：單選】將含100個結點的完全二叉樹從根這一層開始，每層上從左到右依次對結點編號，根結點的編號為1。編號為49的結點X的雙親的編號為（）。A.24B.25C.23D.無法確定『正確答案』A『答案解析』參照二叉樹的性質5。參考教材P98【例題：單選】下面的二叉樹中，（）不是完全二叉樹。『正確答案』A『答案解析』根據(jù)完全二叉樹的定義，從滿二叉樹中刪除的結點應該連續(xù)并且包括最大編號的結點，故A不是完全二叉樹。參考教材P98【例題：單選】若一棵具有n（n>0）個結點的二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）。A.結點均無左孩子的二叉樹B.結點均無右孩子的二叉樹C.高度為n的二叉樹D.存在度為2的結點的二叉樹『正確答案』C『答案解析』如果一棵二叉樹的先序序列和后序序列正好相反，說明該二叉樹每一層只有一個節(jié)點，故答案為C。需要注意的是根據(jù)題意并不能得出該二叉樹一定是一顆斜樹的結論。參考教材P103【例題：單選】若一棵二叉樹中度為1的結點個數(shù)是3，度為2的結點個數(shù)是4，則該二叉樹葉子結點的個數(shù)是（）。A.4B.5C.7D.8『正確答案』B『答案解析』根據(jù)二叉樹的性質3，葉子結點個數(shù)比度為2的結點的個數(shù)多1，故答案為B。參考教材P97【例題：單選】若一棵非空二叉樹的先序序列與后序序列相同，則該二叉樹可能的形狀是（）。A.樹中沒有度為2的結點B.樹中只有一個根結點C.樹中非葉結點均只有左子樹D.樹中非葉結點均只有右子樹『正確答案』B『答案解析』在先序序列中，根結點在最前面，在后序序列中，根結點在最后面。如果一個非空二叉樹的先序序列與后序序列相同，那么沒有別的解釋，說明樹中只有一個根結點。參考教材P103【例題：單選】若根結點的層數(shù)為1，則具有n個結點的二叉樹的最大高度是（）。A.nB.|log2（n+1）|C.|log2n|+1D.n/2『正確答案』A『答案解析』當二叉樹是一棵斜樹的時候最高，注意不要與完全二叉樹的性質4混淆。參考教材P97【例題：單選】若一棵二叉樹的任一非葉子結點的度為2，則該二叉樹為（）。A.滿二叉樹B.完全二叉樹C.哈夫曼樹D.不確定『正確答案』D『答案解析』滿二叉樹、哈夫曼樹都滿足題意。參考教材P97【例題：單選】二叉樹的中序序列中，結點P排在結點Q之前的條件是，在二叉樹中（）。A.P在Q的左邊B.P在Q的右邊C.P是Q的祖先D.P是Q的子孫『正確答案』A『答案解析』無論是先序、中序、后序，都是先遍歷左孩子再遍歷右孩子。參考教材P104【例題：填空】在二叉樹中，指針p非空，它所指結點為葉子結點的條件是________?！赫_答案』（p->lchild==NULL）&&（p->rchild==NULL）『答案解析』本題考察二叉樹的鏈式存儲，葉子結點沒有后繼結點，故左、右指針域都指向空。參考教材P101【例題：填空】已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹中有________個葉結點?！赫_答案』12『答案解析』對于任何一棵樹，總結點個數(shù)=總分支數(shù)目＋1，從題意可知總分支數(shù)：4*3＋3*2＋2*1=20，所以總結點數(shù)為21，則葉子結點數(shù)為：21－2－3－4=12。參考教材P94【例題：填空】已知完全二叉樹的第7層有20個結點，則整個完全二叉樹的葉子結點數(shù)是________?！赫_答案』42『答案解析』第7層有20個結點，則說明第七層是該完全二叉樹的最后一層，根據(jù)完全二叉樹的定義，葉子結點