數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述(耿國(guó)華主編)教案

西安文理學(xué)院精品課《數(shù)據(jù)結(jié)構(gòu)》教案計(jì)算機(jī)科學(xué)系韓利凱《數(shù)據(jù)結(jié)構(gòu)》第一章緒論[教學(xué)目標(biāo)]掌握數(shù)據(jù)結(jié)構(gòu)的定義、內(nèi)容、方法、描述、評(píng)價(jià)。[重點(diǎn)、難點(diǎn)]數(shù)據(jù)結(jié)構(gòu)的研究范圍，研究采用的方法，算法規(guī)那么描述的工具，對(duì)算法作性能評(píng)價(jià)。[教學(xué)方法]用多媒體課件〔ppt〕以及與生活實(shí)例相結(jié)合等方法講授，這樣便于描述相關(guān)概念及學(xué)生記筆記，加深他們的印象，使根底知識(shí)掌握地比擬牢固。[學(xué)習(xí)要點(diǎn)]1.熟悉各名詞、術(shù)語(yǔ)的含義，掌握根本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性質(zhì)，哪些是存儲(chǔ)結(jié)構(gòu)的性質(zhì)。2.了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。3．理解算法五個(gè)要素確實(shí)切含義：①動(dòng)態(tài)有窮性〔能執(zhí)行結(jié)束〕；②確定性〔對(duì)于相同的輸入執(zhí)行相同的路徑〕；③有輸入；④有輸出；⑤可行性〔用以描述算法的操作都是足夠根本的〕。4．掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。1.1

什么是數(shù)據(jù)結(jié)構(gòu)〔定義〕首先介紹數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞。1.

數(shù)據(jù)〔Data〕數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合。。

2.

數(shù)據(jù)元素〔DataElement〕數(shù)據(jù)元素是組成數(shù)據(jù)的根本單位,是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例如：學(xué)生登記表是數(shù)據(jù)，每一個(gè)學(xué)生的記錄就是一個(gè)數(shù)據(jù)元素。3.

數(shù)據(jù)對(duì)象〔DataObject〕數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。4.

數(shù)據(jù)結(jié)構(gòu)〔DATAStructure〕

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，它指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。5.

數(shù)據(jù)類型(DataType)數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。6.

數(shù)據(jù)抽象與抽象數(shù)據(jù)類型１〕數(shù)據(jù)的抽象高級(jí)語(yǔ)言中提供整型、實(shí)型、字符、記錄、文件、指針等多種數(shù)據(jù)類型，可以利用這些類型構(gòu)造出象棧、隊(duì)列、樹、圖等復(fù)雜的抽象數(shù)據(jù)類型。２〕抽象數(shù)據(jù)類型(AbstractDataType)抽象數(shù)據(jù)類型〔簡(jiǎn)稱ADT〕是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作。抽象數(shù)據(jù)類型是近年來(lái)計(jì)算機(jī)科學(xué)中提出的最重要的概念之一，它集中表達(dá)了程序設(shè)計(jì)中一些最根本的原那么：分解、抽象和信息隱藏。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來(lái)；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過(guò)程隱藏起來(lái)。用抽象數(shù)據(jù)類型的概念來(lái)指導(dǎo)問(wèn)題求解的過(guò)程，可以用圖1.4來(lái)表示：數(shù)學(xué)模型

抽象數(shù)據(jù)模型

數(shù)據(jù)結(jié)構(gòu)非形式算法

偽語(yǔ)言程序

可執(zhí)行程序

圖求解過(guò)程數(shù)據(jù)結(jié)構(gòu)是根底，抽象數(shù)據(jù)類型是中樞。1.2

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)局部。邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算集合。數(shù)據(jù)結(jié)構(gòu)是一門主要研究怎樣合理地組織數(shù)據(jù)、建立適宜的數(shù)據(jù)結(jié)構(gòu)、提高計(jì)算機(jī)執(zhí)行程序所用的時(shí)空效率的學(xué)科。1.3

算法1．

算法〔Algorithm〕定義算法是規(guī)那么的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。

2．算法的特性

⑴有限性

有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)。⑵確定性

算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性得以實(shí)現(xiàn)。⑶輸

入

有多個(gè)或0個(gè)輸入⑷輸

出

至少有一個(gè)或多個(gè)輸出。⑸可行性原那么上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)根本運(yùn)算執(zhí)行有限次而完成。在算法的五大特性中，最根本的是有限性、確定性、可行性。

3．算法設(shè)計(jì)的要求一般應(yīng)該具有以下幾個(gè)根本特征：１〕算法的正確性2)可讀性3〕健壯性4〕高效率和低存儲(chǔ)量1.4

算法描述的工具1．算法、語(yǔ)言、程序的關(guān)系先分析數(shù)據(jù)結(jié)構(gòu)中算法、語(yǔ)言、程序的關(guān)系：⑴算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系〔包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述〕。⑵描述算法的工具：〔自然語(yǔ)言、框圖或高級(jí)程序設(shè)計(jì)語(yǔ)言〕⑶程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)〔與所用計(jì)算機(jī)及所用語(yǔ)言有關(guān)〕

2．設(shè)計(jì)實(shí)現(xiàn)算法過(guò)程步驟：

找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系〔建立結(jié)構(gòu)關(guān)系〕

確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算

考慮數(shù)據(jù)元素的存儲(chǔ)表示

選擇描述算法的語(yǔ)言

設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語(yǔ)言加以描述。3．類描述算法的語(yǔ)言選擇采用了標(biāo)準(zhǔn)C語(yǔ)言作為算法描述的工具。1.5

對(duì)算法作性能評(píng)價(jià)1．性能評(píng)價(jià)對(duì)問(wèn)題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與所消耗的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。2．有關(guān)數(shù)量關(guān)系計(jì)算數(shù)量關(guān)系評(píng)價(jià)表達(dá)在時(shí)間——算法編程后在機(jī)器中所消耗時(shí)間。數(shù)量關(guān)系評(píng)價(jià)表達(dá)在空間——算法編程后在機(jī)器中所占存儲(chǔ)量。

1〕關(guān)于算法執(zhí)行時(shí)間一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。

2〕語(yǔ)句頻度語(yǔ)句頻度是指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。3〕算法的時(shí)間復(fù)雜度:所謂算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記做：

T(n)=O(f(n))它表示隨問(wèn)題規(guī)模n的增大算法的執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。4〕數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7個(gè)：

O(1)常數(shù)型

O(n)線性型

O(n2)平方型

O(n3)立方型

O(2n)指數(shù)型

O(log2n)對(duì)數(shù)型

O(nlog2n)二維型5〕最壞時(shí)間復(fù)雜度算法中根本操作重復(fù)執(zhí)行的次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集的不同而不同。6〕算法的空間復(fù)雜度關(guān)于算法的存儲(chǔ)空間需求，類似于算法的時(shí)間復(fù)雜度，我們采用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記做：S(n)=O(f(n))1.6

關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1．?dāng)?shù)據(jù)結(jié)構(gòu)課程地位

數(shù)據(jù)結(jié)構(gòu)開展趨勢(shì)包括兩個(gè)方面：一是面向?qū)ｉT領(lǐng)域中特殊問(wèn)題的數(shù)據(jù)結(jié)構(gòu)的研究和開展，如圖形數(shù)據(jù)結(jié)構(gòu)、知識(shí)數(shù)據(jù)結(jié)構(gòu)、空間數(shù)據(jù)結(jié)構(gòu)，另一方面，從抽象數(shù)據(jù)類型的角度，用面向?qū)ο笥^點(diǎn)來(lái)討論數(shù)據(jù)結(jié)構(gòu)，已成為新的開展趨勢(shì)。

2．?dāng)?shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)目標(biāo)要求學(xué)生學(xué)會(huì)分析數(shù)據(jù)對(duì)象特征，掌握數(shù)據(jù)組織方法和計(jì)算機(jī)的表示方法，以便為應(yīng)用所涉及數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)算法，初步掌握算法時(shí)間空間分析的技巧，培養(yǎng)良好的程序設(shè)計(jì)技能。第2章

線性表[教學(xué)目標(biāo)]線性結(jié)構(gòu)是一種最根本的數(shù)據(jù)結(jié)構(gòu),熟練掌握其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)各種運(yùn)算。[重點(diǎn)、難點(diǎn)]鏈表結(jié)構(gòu)，重點(diǎn)掌握單鏈表、循環(huán)鏈表、雙向鏈表，初步掌握靜態(tài)鏈表。[教學(xué)方法]首先給出線性表的抽象數(shù)據(jù)類型定義，然后分別用順序結(jié)構(gòu)和鏈表結(jié)構(gòu)實(shí)現(xiàn)線性表，最后給出一個(gè)應(yīng)用實(shí)例。[學(xué)習(xí)要點(diǎn)]1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。2.熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，如一維數(shù)組中一個(gè)區(qū)域[i..j]的上、下界和長(zhǎng)度之間的變換公式(L=j-i+1,i=j-L+1,j=i+L-1)，鏈表中指針p和結(jié)點(diǎn)*p的對(duì)應(yīng)關(guān)系(結(jié)點(diǎn)*(p->next)是結(jié)點(diǎn)*p的后繼等)，鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的根本要求。3.熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)根本操作：查找、插入和刪除的算法。4.熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表操作的根本方法，能在實(shí)際應(yīng)用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)。5.能夠從時(shí)間和空間復(fù)雜度的角度綜合比擬線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。2.1

線性表的概念及運(yùn)算

線性表的邏輯結(jié)構(gòu)線性表是n個(gè)類型相同的數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間是一對(duì)一的關(guān)系，即每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。

線性表的抽象數(shù)據(jù)類型定義一個(gè)抽象數(shù)據(jù)類型定義了一個(gè)模型，但不涉及模型的具體實(shí)現(xiàn)問(wèn)題。2.2

線性表的順序存儲(chǔ)

線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中。采用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。

線性表順序存儲(chǔ)結(jié)構(gòu)上的根本運(yùn)算1.查找操作線性表有兩種根本的查找運(yùn)算。按序號(hào)查找GetData(L,i):要求查找線性表L中第i個(gè)數(shù)據(jù)元素，其結(jié)果是L.elem[i-1]或L->elem[i-1]。按內(nèi)容查找Locate〔L,e〕:要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：假設(shè)在表L中找到與e相等的元素，那么返回該元素在表中的序號(hào)；假設(shè)找不到，那么返回一個(gè)“空序號(hào)”，如-1。2.

插入操作線性表的插入運(yùn)算是指在表的第i(1≤i≤n+1)個(gè)位置，插入一個(gè)新元素e，使長(zhǎng)度為n的線性表(e1，…，ei-1，ei，…，en)變成長(zhǎng)度為n+1的線性表〔e1，…,ei-1，e，ei，…，en〕。3.刪除操作線性表的刪除運(yùn)算是指將表的第i(1≤i≤n)個(gè)元素刪去，使長(zhǎng)度為n的線性表

(e1，…,ei-1，ei，ei+1，…，en)，變成長(zhǎng)度為n-1的線性表(e1，…,ei-1，ei+1，…，en)。2.3

線性表的鏈?zhǔn)酱鎯?chǔ)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱為鏈表。

單鏈表鏈表是用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)，在存儲(chǔ)線性表的每個(gè)數(shù)據(jù)元素值的同時(shí)，存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址〔或位置〕信息，這兩局部信息組成的存儲(chǔ)映象叫做結(jié)點(diǎn)〔Node〕，如圖2.5所示。圖2.5

單鏈表的結(jié)點(diǎn)結(jié)構(gòu)它包括兩個(gè)域：數(shù)據(jù)域用來(lái)存儲(chǔ)結(jié)點(diǎn)的值；指針域用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接后繼的地址〔或位置〕。由于鏈表的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，故將這種鏈表又稱為單鏈表。應(yīng)設(shè)一個(gè)頭指針H指向第一個(gè)結(jié)點(diǎn)，由于表中最后一個(gè)結(jié)點(diǎn)沒(méi)有直接后繼，那么指定線性表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)椤翱铡薄睳ULL〕。例如：圖所示為線性表〔A,B,C,D,E,F,G,H〕的單鏈表存儲(chǔ)結(jié)構(gòu)，整個(gè)鏈表的存取需從頭指針開始進(jìn)行，依次順著每個(gè)結(jié)點(diǎn)的指針域找到線性表的各個(gè)元素。

圖2.6單鏈表的例如圖

有時(shí)為了操作的方便，還可以在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域可以存儲(chǔ)一些關(guān)于線性表的長(zhǎng)度的附加信息，也可以什么都不存；而頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。此時(shí)帶頭結(jié)點(diǎn)單鏈表的頭指針就不再指向表中第一個(gè)結(jié)點(diǎn)而是指向頭結(jié)點(diǎn)。如果線性表為空表，那么頭結(jié)點(diǎn)的指針域?yàn)椤翱铡保缦聢D。

(a)帶頭結(jié)點(diǎn)的空單鏈表

(b)帶頭結(jié)點(diǎn)的單鏈表圖2.8帶頭結(jié)點(diǎn)單鏈表圖示

單鏈表上的根本運(yùn)算1．建立單鏈表動(dòng)態(tài)建立單鏈表的常用方法有如下兩種：1〕頭插法建表算法描述：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。2〕尾插法建表該方法是將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上。為此需增加一個(gè)尾指針r，使之始終指向當(dāng)前鏈表的表尾。2．查找1〕按序號(hào)查找算法描述：設(shè)帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，那么需要從單鏈表的頭指針L出發(fā)，從頭結(jié)點(diǎn)〔L->next〕開始順著鏈域掃描，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn),初值指向頭結(jié)點(diǎn)〔pL->next〕，用j做記數(shù)器，累計(jì)當(dāng)前掃描過(guò)的結(jié)點(diǎn)數(shù)〔初值為0〕，當(dāng)j=i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。2)

按值查找算法描述：按值查找是指在單鏈表中查找是否有結(jié)點(diǎn)值等于e的結(jié)點(diǎn)，假設(shè)有的話，那么返回首次找到的其值為e的結(jié)點(diǎn)的存儲(chǔ)位置，否那么返回NULL。3．單鏈表插入操作算法描述：要在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素e，需要首先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)并由指針pre指示，然后申請(qǐng)一個(gè)新的結(jié)點(diǎn)并由指針s指示，其數(shù)據(jù)域的值為e，并修改第i-1個(gè)結(jié)點(diǎn)的指針使其指向s，然后使s結(jié)點(diǎn)的指針域指向第i個(gè)結(jié)點(diǎn)。4．刪除算法描述：欲在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)結(jié)點(diǎn)，那么首先要通過(guò)計(jì)數(shù)方式找到第i-1個(gè)結(jié)點(diǎn)并使p指向第i-1個(gè)結(jié)點(diǎn)，而后刪除第i個(gè)結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間。刪除過(guò)程如下圖。

循環(huán)鏈表循環(huán)鏈表：是一個(gè)首尾相接的鏈表。其特點(diǎn)是將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。

〔a〕帶頭結(jié)點(diǎn)的循環(huán)單鏈表的一般形式

〔b〕帶尾結(jié)點(diǎn)的循環(huán)單鏈表的一般形式

雙向鏈表鏈表中就有兩條方向不同的鏈，我們稱之為雙(向)鏈表(DoubleLinkedList)。

圖

雙鏈表的結(jié)點(diǎn)結(jié)構(gòu)1、雙向鏈表的前插操作2、雙向鏈表的刪除操作算法描述：欲刪除雙向鏈表中的第i個(gè)結(jié)點(diǎn)，那么指針的變化情況如下圖：

圖2.17雙向鏈表的刪除操作

2.4

一元多項(xiàng)式的表示及相加對(duì)于符號(hào)多項(xiàng)式的各種操作，實(shí)際上都可以利用線性表來(lái)處理。比擬典型的是關(guān)于一元多項(xiàng)式的處理。在數(shù)學(xué)上，一個(gè)一元多項(xiàng)式Pn(x)可按升冪的形式寫成：Pn(x)=p0+p1x+p2x2+p3x3+…+pnxn〔2〕通過(guò)鍵盤輸入一組多項(xiàng)式的系數(shù)和指數(shù)，以輸入系數(shù)0為結(jié)束標(biāo)志，并約定建立多項(xiàng)式鏈表時(shí)，總是按指數(shù)從大到小的順序排列。算法描述：從鍵盤接受輸入的系數(shù)和指數(shù)；用尾插法建立一元多項(xiàng)式的鏈表。第3章

限定性線性表—棧和隊(duì)列[教學(xué)目標(biāo)]棧和隊(duì)列是兩種限定性線性表，在編譯程序、操作系統(tǒng)等各種軟件系統(tǒng)中應(yīng)用廣泛。熟練掌握邏輯、存儲(chǔ)結(jié)構(gòu)。[重點(diǎn)、難點(diǎn)]要求重點(diǎn)掌握利用棧和隊(duì)列解決實(shí)際問(wèn)題的方法。[教學(xué)方法]用棧和隊(duì)列的典型應(yīng)用引出棧和隊(duì)列的抽象數(shù)據(jù)類型定義、分別用順序結(jié)構(gòu)和單鏈表結(jié)構(gòu)實(shí)現(xiàn)棧和隊(duì)列，棧與遞歸的實(shí)現(xiàn)。[學(xué)習(xí)要點(diǎn)]1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在應(yīng)用問(wèn)題中正確選用它們。2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法，即兩種存儲(chǔ)結(jié)構(gòu)表示時(shí)的根本操作實(shí)現(xiàn)算法，特別應(yīng)注意棧滿和?？盏臈l件以及它們的描述方法。3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的根本操作算法，特別注意隊(duì)滿和隊(duì)空的描述方法。4.理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。3.1

棧

棧的定義棧又稱為后進(jìn)先出的線性表，簡(jiǎn)稱為L(zhǎng)IFO表。在日常生活中也可以見到很多“后進(jìn)先出”的例子，如：手槍子彈夾中的子彈，子彈的裝入與子彈彈出膛均在彈夾的最上端進(jìn)行，先裝入的子彈后發(fā)出，而后裝入的子彈先發(fā)出。又如：鐵路調(diào)度站，都是棧結(jié)構(gòu)的實(shí)際應(yīng)用。

棧的表示和實(shí)現(xiàn)1．順序棧順序棧是用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)由于棧的操作的特殊性，還必須附設(shè)一個(gè)位置指針top〔棧頂指針〕來(lái)動(dòng)態(tài)地指示棧頂元素在順序棧中的位置。通常以top=-1表示空棧。⑴

初始化。void

InitStack(SeqStack*S){/*構(gòu)造一個(gè)空棧S*/

S->top=-1;}⑵判?？?。intIsEmpty(SeqStack*S)

/*判棧S為空棧時(shí)返回值為真，反之為假*/{return(S->top==-1?TRUE:FALSE);}

⑶

判棧滿。intIsFull(SeqStack*S){

return(S->top==Stack_Size?TRUE:FALSE);}

⑷

進(jìn)棧。intPush(SeqStack*S,StackElementTypex){

if(S->top==Stack_Size-1)

return(FALSE);

/*棧已滿*/S->top++;S->elem[S->top]=x;return(TRUE);}⑸

出棧。intPop(SeqStack*S,StackElementType*x){

/*將棧S的棧頂元素彈出，放到x所指的存儲(chǔ)空間中*/if(S->top==-1)

/*棧為空*/return(FALSE);

else{

*x=S->elem[S->top];S->top--;

/*修改棧頂指針*/

return(TRUE);}}⑹

取棧頂元素。intGetTop〔SeqStack*S,StackElementType*x〕{

/*將棧S的棧頂元素彈出，放到x所指的存儲(chǔ)空間中，但棧頂指針保持不變*/

if(S->top==-1)

/*棧為空*/return(FALSE);

else{

*x=S->elem[S->top];

return(TRUE);}

}思考題：說(shuō)明讀棧頂元素的算法與退棧頂元素的算法的區(qū)別，并請(qǐng)寫出讀棧頂算法。2．鏈棧鏈棧即采用鏈表作為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧。⑴

進(jìn)棧操作。intPush(LinkStacktop,StackElementTypex)/*將數(shù)據(jù)元素x壓入棧top中*/

{

LinkStackNode*temp;

temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));

if(temp==NULL)

return(FALSE);

/*申請(qǐng)空間失敗*/

temp->data=x;

temp->next=top->next;top->next=temp;

/*修改當(dāng)前棧頂指針*/return(TRUE);}⑵

出棧操作。intPop(LinkStacktop,StackElementType*x){

/*將棧top的棧頂元素彈出，放到x所指的存儲(chǔ)空間中*/LinkStackNode*temp;temp=top->next;if(temp==NULL)

/*棧為空*/

return(FALSE);top->next=temp->next;*x=temp->data;free(temp);

/*釋放存儲(chǔ)空間*/return(TRUE);}思考題：將可利用空間組成鏈棧，常用的申請(qǐng)一個(gè)新結(jié)點(diǎn)〔如C語(yǔ)言中的mallock函數(shù)〕與歸還一個(gè)無(wú)用結(jié)點(diǎn)〔如C語(yǔ)言中的free函數(shù)〕操作，對(duì)可利用空間的鏈棧來(lái)說(shuō)，分別相當(dāng)做什么操作？

棧的應(yīng)用舉例棧應(yīng)用的典型例子。1.括號(hào)匹配問(wèn)題假設(shè)表達(dá)式中包含三種括號(hào)：圓括號(hào)、方括號(hào)和花括號(hào)，它們可互相嵌套，如([{}]([]))或({([][(

)])})等均為正確的格式，而{[]})}或{[()]或([]}均為不正確的格式。在檢驗(yàn)算法中可設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，假設(shè)是左括號(hào)，那么直接入棧，等待相匹配的同類右括號(hào)；假設(shè)讀入的是右括號(hào)，且與當(dāng)前棧頂?shù)淖罄ㄌ?hào)同類型，那么二者匹配，將棧頂?shù)淖罄ㄌ?hào)出棧，否那么屬于不合法的情況。另外，如果輸入序列已讀盡，而棧中仍有等待匹配的左括號(hào)，或者讀入了一個(gè)右括號(hào)，而棧中已無(wú)等待匹配的左括號(hào)，均屬不合法的情況。當(dāng)輸入序列和棧同時(shí)變?yōu)榭諘r(shí)，說(shuō)明所有括號(hào)完全匹配。2.算術(shù)表達(dá)式處理規(guī)那么：一、規(guī)定優(yōu)先級(jí)表二、設(shè)置兩個(gè)棧：OVS(運(yùn)算數(shù)棧)、OPTR(運(yùn)算符棧)三、自左向右掃描，遇操作數(shù)進(jìn)OVS(運(yùn)算數(shù)棧),操作符那么與OPTR(運(yùn)算符棧)棧頂優(yōu)先數(shù)比擬：當(dāng)前操作符>OPTR棧頂,當(dāng)前操作符進(jìn)OPTR棧,前操作符≤OPTR棧頂.圖3.7

A/B↑C+D*E的運(yùn)算過(guò)程時(shí)棧區(qū)變化情況棧區(qū)變化示意圖

隊(duì)列的定義隊(duì)列(Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊(duì)列具有先進(jìn)先出(FistInFistOut，縮寫為FIFO)的特性。在隊(duì)列中，允許插入的一端叫做隊(duì)尾(rear)，允許刪除的一端那么稱為隊(duì)頭(front)。

隊(duì)列的表示和實(shí)現(xiàn)1．鏈隊(duì)列用鏈表表示的隊(duì)列簡(jiǎn)稱為鏈隊(duì)列。

〔1〕初始化操作。intInitQueue(LinkQueue*Q){/*將Q初始化為一個(gè)空的鏈隊(duì)列*/

Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));

if(Q->front!=NULL)

{

Q->rear=Q->front;

Q->front->next=NULL;

return(TRUE);

}

else

return(FALSE);

/*溢出！*/}〔2〕入隊(duì)操作。intEnterQueue(LinkQueue*Q,QueueElementTypex){

/*將數(shù)據(jù)元素x插入到隊(duì)列Q中*/LinkQueueNode

*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(NewNode!=NULL){

NewNode->data=x;

NewNode->next=NULL;

Q->rear->next=NewNode;

Q->rear=NewNode;return(TRUE);}

else

return(FALSE);

/*溢出！*/}〔3〕出隊(duì)操作。intDeleteQueue(LinkQueue*Q,QueueElementType*x){

/*將隊(duì)列Q的隊(duì)頭元素出隊(duì)，并存放到x所指的存儲(chǔ)空間中*/LinkQueueNode*p;if(Q->front==Q->rear)

return(FALSE);p=Q->front->next;Q->front->next=p->next;

/*隊(duì)頭元素p出隊(duì)*/if(Q->rear==p)

/*如果隊(duì)中只有一個(gè)元素p，那么p出隊(duì)后成為空隊(duì)*/Q->rear=Q->front;

*x=p->data;free(p);

/*釋放存儲(chǔ)空間*/return(TRUE);

}

2．循環(huán)隊(duì)列循環(huán)隊(duì)列是隊(duì)列的一種順序表示和實(shí)現(xiàn)方法。由于只能在隊(duì)尾入隊(duì)，使得上述空單元無(wú)法使用。我們把這種現(xiàn)象稱為假溢出，真正隊(duì)滿的條件是rear-front=MAXSIZE。

為了解決假溢出現(xiàn)象并使得隊(duì)列空間得到充分利用，是將順序隊(duì)列的數(shù)組看成一個(gè)環(huán)狀的空間，即規(guī)定最后一個(gè)單元的后繼為第一個(gè)單元，稱之為循環(huán)隊(duì)列。通過(guò)取模〔求余〕運(yùn)算來(lái)實(shí)現(xiàn)：rear=〔rear+1〕modMAXSIZE，顯然，當(dāng)rear+1=MAXSIZE時(shí)，rear=0，同樣可求得最后一個(gè)單元Queue[MAXSIZE-1]的后繼：Queue[0]。隊(duì)尾指針的變化是：rear=〔rear+1〕modMAXSIZE；而出隊(duì)操作時(shí)，隊(duì)頭指針的變化是：front=〔front+1〕modMAXSIZE。圖給出了循環(huán)隊(duì)列的幾種情況。

第4章

串[教學(xué)目標(biāo)]字符串是最根本的非數(shù)值數(shù)據(jù)，在語(yǔ)言編譯、信息檢索、文字編輯等問(wèn)題中，有廣泛的應(yīng)用。熟練掌握其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)各種運(yùn)算。[重點(diǎn)、難點(diǎn)]字符串的抽象數(shù)據(jù)類型定義，定長(zhǎng)順序串、堆串的存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)。一般性了解塊鏈串。[教學(xué)方法]采用應(yīng)用實(shí)例任務(wù)驅(qū)動(dòng)給出字符串的抽象數(shù)據(jù)類型定義，然后分別用順序結(jié)構(gòu)和鏈表結(jié)構(gòu)實(shí)現(xiàn)字符串。[學(xué)習(xí)要點(diǎn)]1.了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。2.掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。3.了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法。4.掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法，學(xué)會(huì)對(duì)非空廣義表進(jìn)行分解的兩種分析方法：即可將一個(gè)非空廣義表分解為表頭和表尾兩局部或者分解為n個(gè)子表。4.1

串的定義

串(String)是零個(gè)或多個(gè)字符組成的有限序列。一般記為：

S=‘a(chǎn)1a2…an’其中S是串的名字,用單引號(hào)括起來(lái)的字符序列是串的值。n是串中字符的個(gè)數(shù),稱為串的長(zhǎng)度，n=0時(shí)的串稱為空串(NullString)。串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地稱為主串。通常將字符在串中的序號(hào)稱為該字符在串中的位置。當(dāng)且僅當(dāng)兩個(gè)串的值相等時(shí),稱這兩個(gè)串是相等的。由一個(gè)或多個(gè)稱為空格的特殊字符組成的串，稱為空格串(Blankstring),其長(zhǎng)度為串中空格字符的個(gè)數(shù)。請(qǐng)注意空串(NullString)和空格串(Blankstring)的區(qū)別。串也是線性表的一種,因此串的邏輯結(jié)構(gòu)和線性表極為相似,區(qū)別僅在于串的數(shù)據(jù)對(duì)象限定為字符集。4.2

抽象數(shù)據(jù)類型串的實(shí)現(xiàn)常用的實(shí)現(xiàn)方法有:定長(zhǎng)順序串、堆串和塊鏈串。

定長(zhǎng)順序串定長(zhǎng)順序串是將串設(shè)計(jì)成一種結(jié)構(gòu)類型,串的存儲(chǔ)分配是在編譯時(shí)完成的。用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列。在進(jìn)行串的插入時(shí)，插入位置pos將串分為兩局部〔假設(shè)為A、B,長(zhǎng)度為L(zhǎng)A、LB〕,及待插入局部〔假設(shè)為C,長(zhǎng)度為L(zhǎng)C〕,那么串由插入前的AB變?yōu)锳CB，可能有三種情況：〔1〕

插入后串長(zhǎng)(LA+LC+LB)≤MAXLEN：那么將B后移LC個(gè)元素位置，再將C插入。〔2〕

插入后串長(zhǎng)>MAXLEN且pos+LC<MAXLEN：那么B后移時(shí)會(huì)有局部字符被舍棄?！?〕

插入后串長(zhǎng)>MAXLEN且pos+LC>MAXLEN：那么B的全部字符被舍棄〔不需后移〕，并且C在插入時(shí)也有局部字符被舍棄。同上類似，在進(jìn)行串的連接時(shí)〔假設(shè)原來(lái)串為A，長(zhǎng)度為L(zhǎng)A,待連接串為B，長(zhǎng)度為L(zhǎng)B〕，也可能有三種情況：〔1〕

連接后串長(zhǎng)≤MAXLEN：那么直接將B加在A的后面?！?〕

連接后串長(zhǎng)>MAXLEN且LA<MAXLEN：那么B會(huì)有局部字符被舍棄?！?〕

連接后串長(zhǎng)>MAXLEN且LA=MAXLEN：那么B的全部字符被舍棄〔不需連接〕。置換時(shí)的情況較為復(fù)雜，假設(shè)為原串為A、長(zhǎng)度為L(zhǎng)A，被置換串為B、長(zhǎng)度為L(zhǎng)B,置換串為C、長(zhǎng)度為L(zhǎng)C，每次置換位置為pos，那么每次置換有三種可能：〔1〕

LB=LC：將C復(fù)制到A中pos起共LC個(gè)字符處?！?〕

LB>LC：將A中B后的所有字符前移LB-LC個(gè)字符位置，然后將C復(fù)制到A中pos起共LC個(gè)字符?！?〕

LB<LC：將A中B后的所有字符后移LC-LB個(gè)字符位置，然后將C復(fù)制到A中pos起共LC個(gè)字符，此時(shí)可能會(huì)出現(xiàn)串插入時(shí)的三種情況，應(yīng)按三種情況作相應(yīng)處理。

堆串系統(tǒng)將一個(gè)地址連續(xù)、容量很大的存儲(chǔ)空間作為字符串的可用空間，每當(dāng)建立一個(gè)新串時(shí)，系統(tǒng)就從這個(gè)空間中分配一個(gè)大小和字符串長(zhǎng)度相同的空間存儲(chǔ)新串的串值。假設(shè)以一維數(shù)組heap[MAXSIZE]表示可供字符串進(jìn)行動(dòng)態(tài)分配的存儲(chǔ)空間，并設(shè)intfree指向heap中未分配區(qū)域的開始地址(初始化時(shí)free=0)。在程序執(zhí)行過(guò)程中，當(dāng)生成一個(gè)新串時(shí)，就從free指示的位置起，為新串分配一個(gè)所需大小的存儲(chǔ)空間，同時(shí)建立該串的描述。這種存儲(chǔ)結(jié)構(gòu)稱為堆結(jié)構(gòu)。其中l(wèi)en域指示串的長(zhǎng)度，ch域指示串的起始地址。4.3

串的應(yīng)用舉例：文本編輯文本編輯程序用于源程序的輸入和修改，公文書信、報(bào)刊和書籍的編輯排版等。常用的文本編輯程序有Edit，WPS，Word等，文本編輯的實(shí)質(zhì)是修改字符數(shù)據(jù)的形式和格式，雖然各個(gè)文本編輯程序的功能不同，但根本操作是一樣的，都包括串的查找、插入和刪除等。為了編輯方便，可以用分頁(yè)符和換行符將文本分為假設(shè)干頁(yè)，每頁(yè)有假設(shè)干行。我們把文本當(dāng)作一個(gè)字符串，稱為文本串，頁(yè)是文本串的子串，行是頁(yè)的子串。采用堆存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)文本，同時(shí)設(shè)立頁(yè)指針、行指針和字符指針，分別指向當(dāng)前操作的頁(yè)、行和字符，同時(shí)建立頁(yè)表和行表存儲(chǔ)每一頁(yè)、每一行的起始位置和長(zhǎng)度。

第5章

數(shù)組和廣義表[教學(xué)目標(biāo)]數(shù)組和廣義表，是擴(kuò)展的線性數(shù)據(jù)結(jié)構(gòu)，其中廣義表是人工智能程序設(shè)計(jì)的根底。要求熟練掌握其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)各種運(yùn)算。[重點(diǎn)、難點(diǎn)]抽象數(shù)據(jù)類型數(shù)組的定義與實(shí)現(xiàn)，特殊矩陣的壓縮存儲(chǔ)，稀疏矩陣〔分別用三元組表、十字鏈表實(shí)現(xiàn)轉(zhuǎn)置、加減法等矩陣運(yùn)〕，廣義表的存儲(chǔ)結(jié)構(gòu)，稀疏矩陣的乘法運(yùn)算。[教學(xué)方法]設(shè)問(wèn)解疑，激發(fā)學(xué)生對(duì)數(shù)組和廣義表的求知欲望和積極的思維活動(dòng)。[學(xué)習(xí)要點(diǎn)]1.了解數(shù)組的存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。2.掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。3.了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法。4.掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法5.1

數(shù)組的定義和運(yùn)算數(shù)組實(shí)際上是線性表的推廣。數(shù)組中的每一個(gè)元素由一個(gè)值和一組下標(biāo)來(lái)描述。對(duì)于數(shù)組的操作一般只有兩類：1〕

獲得特定位置的元素值；2〕

修改特定位置的元素值。5.2

數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn)數(shù)組的順序存儲(chǔ)結(jié)構(gòu)有兩種：一種是按行序存儲(chǔ)，另一種是按列序存儲(chǔ)，。二維數(shù)組Amxn以行為主的存儲(chǔ)序列為：a11,a12,…a1n,a21,a22,…,a2n,……,am1,am2,…,amn而以列為主存儲(chǔ)序列為：a11,a21,…am1,a12,a22,…,am2,……,a1n,a2n,…,amn地址計(jì)算公式：Loc[i,j]=Loc[1,1]+n×(i-1)+(j-1)根據(jù)計(jì)算公式，可以方便的求得aij的地址是Loc[i,j]。如果每個(gè)元素占size個(gè)存儲(chǔ)單元，那么任意元素aij的地址計(jì)算公式為：Loc[i,j]=Loc[1,1]+(n×(i-1)+j-1)×size

三角矩陣三角矩陣大體分為三類：下三角矩陣、上三角矩陣、對(duì)稱矩陣。對(duì)于一個(gè)n階矩陣A來(lái)說(shuō)：假設(shè)當(dāng)i<j時(shí)，有aij=0，那么稱此矩陣為下三角矩陣；假設(shè)當(dāng)i>j時(shí)，有aij=0，那么此矩陣稱為上三角矩陣；假設(shè)矩陣中的所有元素均滿足aij=aji，那么稱此矩陣為對(duì)稱矩陣。下面以n×n下三角矩陣〔圖〕為例來(lái)討論三角矩陣的壓縮存儲(chǔ)。

對(duì)于下三角矩陣的壓縮存儲(chǔ)，只存儲(chǔ)下三角的非零元素，對(duì)于零元素那么不存。下三角矩陣中元素aij(i>j)，在一維數(shù)組A中的位置為：Loc[i,j]=Loc[1,1]+前i-1行非零元素個(gè)數(shù)+第i行中aij前非零元素個(gè)數(shù)LOC[i,j]=LOC[1,1]+i(i-1)/2+j-1

帶狀矩陣所謂的帶狀矩陣即：在矩陣A中，所有的非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。其中最常見的是三對(duì)角帶狀矩陣。對(duì)于三對(duì)角帶狀矩陣的壓縮存儲(chǔ)，以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)，并且只存儲(chǔ)非零元素。具體壓縮存儲(chǔ)方法如下：一、確定存儲(chǔ)該矩陣所需的一維向量空間的大小二、確定非零元素在一維數(shù)組空間中的位置。

稀疏矩陣所謂的稀疏矩陣，是指矩陣中大多數(shù)元素為零的矩陣。一般地，當(dāng)非零元素個(gè)數(shù)只占矩陣元素總數(shù)的25%—30%,或低于這個(gè)百分?jǐn)?shù)時(shí)，我們稱這樣的矩陣為稀疏矩陣。一、稀疏矩陣的三元組表表示法：把三元組按“行序?yàn)橹餍颉庇靡痪S數(shù)組進(jìn)行存放，即將j矩陣的任何一行的全部非零元素的三元組按列號(hào)遞增存放。由此得到矩陣M，N的三元組表.稀疏矩陣的三元組表示法雖然節(jié)約了存儲(chǔ)空間，但比起矩陣正常的存儲(chǔ)方式來(lái)講，其實(shí)現(xiàn)相同操作要消耗較多的時(shí)間，同時(shí)也增加了算法的難度。即以消耗更多時(shí)間為代價(jià)來(lái)?yè)Q取空間的節(jié)省。二、稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)----十字鏈表在十字鏈表中，同一行的非零元素通過(guò)right域鏈接成一個(gè)單鏈表。同一列的非零元素通過(guò)down域鏈接成一個(gè)單鏈表。這樣，矩陣中任一非零元素Mij所對(duì)應(yīng)的結(jié)點(diǎn)既處在第i行的行鏈表上，又處在第j列的列鏈表上，這好似是處在一個(gè)十字交叉路口上，所以稱其為十字鏈表。同時(shí)我們?cè)俑皆O(shè)一個(gè)存放所有行鏈表的頭指針的的一維數(shù)組，和一個(gè)存放所有列鏈表的頭指針的的一維數(shù)組。廣義表，顧名思義，它也是線性表的一種推廣。它被廣泛的應(yīng)用于人工智能等領(lǐng)域的表處理語(yǔ)言LISP語(yǔ)言中。在LISP語(yǔ)言中，廣義表是一種最根本的數(shù)據(jù)結(jié)構(gòu)，就連LISP語(yǔ)言的程序也表示為一系列的廣義表。由于廣義表GL=〔d1，d2，d3，…，dn〕中的數(shù)據(jù)元素既可以是單個(gè)元素，也可以是子表，因此對(duì)于廣義表，我們難以用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示它，通常我們用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)表示。表中的每個(gè)元素可用一個(gè)結(jié)點(diǎn)來(lái)表示。廣義表中有兩類結(jié)點(diǎn)，一類是單個(gè)元素結(jié)點(diǎn)，一類是子表結(jié)點(diǎn)。從上節(jié)得知，任何一個(gè)非空的廣義表都可以將其分解成表頭和表尾兩局部，反之，一對(duì)確定的表頭和表尾可以唯一地確定一個(gè)廣義表。由此，一個(gè)表結(jié)點(diǎn)可由三個(gè)域構(gòu)成：標(biāo)志域，指向表頭的指針域，指向表尾的指針域。而元素結(jié)點(diǎn)置需要兩個(gè)域：標(biāo)志域和值域。第六章樹[教學(xué)目標(biāo)]樹是一種層次結(jié)構(gòu)，在文件系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)、編譯系統(tǒng)等方面有重要應(yīng)用。熟練掌握樹與二叉樹的抽象數(shù)據(jù)類型定義和實(shí)現(xiàn)，二叉樹的遍歷與線索二叉樹，樹、森林與二叉樹的關(guān)系，哈父曼樹及其應(yīng)用。[重點(diǎn)、難點(diǎn)]二叉樹、樹、森林與二叉樹的相互轉(zhuǎn)換。[教學(xué)方法]提出樹、二叉樹和的森林問(wèn)題，在教師組織和指導(dǎo)下，通過(guò)學(xué)生比擬獨(dú)立的探究和研究活動(dòng)，探求問(wèn)題的答案。[學(xué)習(xí)要點(diǎn)]1.熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)的證明方法。2.熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。3.遍歷二叉樹是二叉樹各種操作的根底。實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。不僅要熟練掌握各種遍歷策略的遞歸和非遞歸算法，了解遍歷過(guò)程中“棧”的作用和狀態(tài)，而且能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。4.理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化過(guò)程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹的線索化過(guò)程是基于對(duì)二叉樹進(jìn)行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。5.熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握1至2種建立二叉樹和樹的存儲(chǔ)結(jié)構(gòu)的方法。6.學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。7.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。6.1

樹的概念與定義樹是n〔n≥0〕個(gè)結(jié)點(diǎn)的有限集合T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n>0時(shí)，該集合滿足如下條件：⑴其中必有一個(gè)稱為根〔root〕的特定結(jié)點(diǎn)，它沒(méi)有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。⑵其余n-1個(gè)結(jié)點(diǎn)可以劃分成m〔m≥0〕個(gè)互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼。圖6.1給出了一棵樹的邏輯結(jié)構(gòu)圖示，它如同一棵倒長(zhǎng)的樹。

結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及假設(shè)干指向其它結(jié)點(diǎn)的分支信息。

結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)稱為此結(jié)點(diǎn)的度。

葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。

分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。

孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。在圖6.1中，B、C是A的孩子。

雙親結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接前驅(qū)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。在圖6.1中，A是B、C的雙親。

兄弟結(jié)點(diǎn)：同一雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)H、I、J互為兄弟結(jié)點(diǎn)。

祖先結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)K的祖先是A、B、E。

子孫結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的直接后繼和間接后繼稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。在圖6.1中，結(jié)點(diǎn)D的子孫是H、I、J、M。

樹的度：樹中所有結(jié)點(diǎn)的度的最大值。

結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始定義，根結(jié)點(diǎn)的層次為1，根的直接后繼的層次為2，依此類推。

樹的高度〔深度〕：樹中所有結(jié)點(diǎn)的層次的最大值。

有序樹：在樹T中，如果各子樹Ti之間是有先后次序的，那么稱為有序樹。

森林：m〔m≥0〕棵互不相交的樹的集合。將一棵非空樹的根結(jié)點(diǎn)刪去，樹就變成一個(gè)森林；反之，給森林增加一個(gè)統(tǒng)一的根結(jié)點(diǎn)，森林就變成一棵樹。6.2

二叉樹

二叉樹的定義與根本操作定義：滿足以下兩個(gè)條件的樹型結(jié)構(gòu)叫做二叉樹〔BinaryTree〕：〔1〕

每個(gè)結(jié)點(diǎn)的度都不大于2；〔2〕

每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。

二叉樹的性質(zhì)性質(zhì)1:在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)。性質(zhì)2:深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)〔k≥1〕。性質(zhì)3:對(duì)任意一棵二叉樹T，假設(shè)終端結(jié)點(diǎn)數(shù)為n0，而其度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，那么n0=n2+1滿二叉樹：深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。在滿二叉樹中，每層結(jié)點(diǎn)都是滿的，即每層結(jié)點(diǎn)都具有最大結(jié)點(diǎn)數(shù)。完全二叉樹：深度為k，結(jié)點(diǎn)數(shù)為n的二叉樹，如果其結(jié)點(diǎn)1~n的位置序號(hào)分別與滿二叉樹的結(jié)點(diǎn)1~n的位置序號(hào)一一對(duì)應(yīng)，那么為完全二叉樹。滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[logN]+1性質(zhì)5:

對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號(hào)，那么對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)有：〔1〕如i=1，那么序號(hào)為i的結(jié)點(diǎn)是根結(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn)；如i>1，那么序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)為[/2]〔2〕如2×i>n，那么序號(hào)為i的結(jié)點(diǎn)無(wú)左孩子；如2×i≤n，那么序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2×i?！?〕如2×i＋1>n，那么序號(hào)為i的結(jié)點(diǎn)無(wú)右孩子；如2×i＋1≤n，那么序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2×i＋1。

二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。二叉樹的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1．順序存儲(chǔ)結(jié)構(gòu)順序的存儲(chǔ)結(jié)構(gòu)是用一組連續(xù)的存儲(chǔ)單元來(lái)存放二叉樹的數(shù)據(jù)元素。2．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、左孩子域和右孩子域：其中，LChild域指向該結(jié)點(diǎn)的左孩子，Data域記錄該結(jié)點(diǎn)的信息，RChild域指向該結(jié)點(diǎn)的右孩子域。6.3

二叉樹的遍歷與線索化

二叉樹的遍歷

二叉樹的遍歷是指按一定規(guī)律對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)進(jìn)行訪問(wèn)且僅訪問(wèn)一次。二叉樹的遍歷操作是二叉樹中最根本的運(yùn)算。

先序遍歷〔DLR〕操作過(guò)程：

假設(shè)二叉樹為空，那么空操作，否那么依次執(zhí)行如下3個(gè)操作：⑴訪問(wèn)根結(jié)點(diǎn)；

⑵按先序遍歷左子樹；

⑶按先序遍歷右子樹。

中序遍歷〔LDR〕操作過(guò)程：

假設(shè)二叉樹為空，那么空操作，否那么依次執(zhí)行如下3個(gè)操作：

⑴按中序遍歷左子樹；

⑵訪問(wèn)根結(jié)點(diǎn)；

⑶按中序遍歷右子樹。

后序遍歷〔LRD〕操作過(guò)程：

假設(shè)二叉樹為空，那么空操作，否那么依次執(zhí)行如下3個(gè)操作：

⑴按后序遍歷左子樹；

⑵按后序遍歷右子樹；

⑶訪問(wèn)根結(jié)點(diǎn)。顯然，這種遍歷是一個(gè)遞歸過(guò)程。

遍歷算法應(yīng)用1．輸出二叉樹中的結(jié)點(diǎn)遍歷算法將走遍二叉樹中的每一個(gè)結(jié)點(diǎn)，故輸出二叉樹中的結(jié)點(diǎn)并無(wú)次序要求，因此可用三種遍歷中的任何一種算法完成。2．輸出二叉樹中的葉子結(jié)點(diǎn)輸出二叉樹中的葉子結(jié)點(diǎn)要求與輸出二叉樹中的結(jié)點(diǎn)相比，是一個(gè)有條件的輸出問(wèn)題，條件是在遍歷過(guò)程中走到每一個(gè)結(jié)點(diǎn)時(shí)須進(jìn)行測(cè)試，看是否滿足葉結(jié)點(diǎn)的條件。3．統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目下面給出兩種方法均可統(tǒng)計(jì)出二叉樹葉子結(jié)點(diǎn)數(shù)目/*LeafCount保存葉子結(jié)點(diǎn)的數(shù)目的全局變量,調(diào)用之前初始化值為0*/voidleaf(BiTreeroot){

if(root!=NULL)

{leaf(root->LChild);leaf(root->RChild);if(root->LChild==NULL&&root->RChild==NULL)LeafCount++;

}}算法6.8(a)后序遍歷統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目思考：可否按中序統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)？

5．按樹狀打印的二叉樹例：假設(shè)以二叉鏈表存儲(chǔ)的二叉樹中，每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母。要求實(shí)現(xiàn)如下列圖。

圖樹狀打印的二叉樹示意這實(shí)際是一個(gè)二叉樹的橫向顯示問(wèn)題：因?yàn)槎鏄涞臋M向顯示應(yīng)是二叉樹豎向顯示的90。旋轉(zhuǎn)，又由于二叉樹的橫向顯示算法一定是中序遍歷算法，所以把橫向顯示的二叉樹算法改為先右子樹再根結(jié)點(diǎn)再左子樹的RDL結(jié)構(gòu)，實(shí)現(xiàn)算法見。voidPrintTree(TreeNodeBoot,intnLayer)

/*按豎向樹狀打印的二叉樹*/{

if(Boot==NULL)return;

PrintTree(Boot->pRight,nLayer+1);

for(inti=0;i<nLayer;i++)printf(“

”);

printf(“%c\n”,Boot->ch);

PrintTree(Boot->pLeft,nLayer+1);}算法按豎向樹狀打印的二叉樹思考：對(duì)二叉樹實(shí)現(xiàn)左右子樹交換，是否可采用前序、中序、后序中的任何一種算法實(shí)現(xiàn)，請(qǐng)說(shuō)明原因。

線索二叉樹1．根本概念指向前驅(qū)和后繼結(jié)點(diǎn)的指針叫做線索。以這種結(jié)構(gòu)組成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做線索鏈表。對(duì)二叉樹以某種次序進(jìn)行遍歷并且加上線索的過(guò)程叫做線索化。線索化了的二叉樹稱為線索二叉樹。2．二叉樹的線索化線索化的過(guò)程即為在遍歷過(guò)程中修改空指針域的過(guò)程。3．在線索二叉樹中找前驅(qū)、后繼結(jié)點(diǎn)1〕找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)對(duì)于結(jié)點(diǎn)p，當(dāng)p->Ltag=1時(shí)，p->LChild指向p的前驅(qū)。當(dāng)p->Ltag=0時(shí)，p->LChild指向p的左孩子。由中序遍歷的規(guī)律可知，作為根p的前驅(qū)結(jié)點(diǎn)，它是中序遍歷p的左子樹時(shí)訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，即左子樹的“最右下端”結(jié)點(diǎn)。2〕在中序線索樹中找結(jié)點(diǎn)后繼對(duì)于結(jié)點(diǎn)p，假設(shè)要找其后繼結(jié)點(diǎn)，當(dāng)p->Rtag=1時(shí)，p->RChild即為p的后繼結(jié)點(diǎn)；當(dāng)p->Rtag=0時(shí)，說(shuō)明p有右子樹，此時(shí)p的中序后繼結(jié)點(diǎn)即為其右子樹的“最左下端”的結(jié)點(diǎn)。6.4

樹、森林和二叉樹的關(guān)系6.4.1

樹的主要存儲(chǔ)方法有以下三種：1．雙親表示法這種方法用一組連續(xù)的空間來(lái)存儲(chǔ)樹中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)一個(gè)指示器來(lái)指示其雙親結(jié)點(diǎn)在表中的位置.2．孩子表示法這種方法通常是把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。n個(gè)結(jié)點(diǎn)共有n個(gè)孩子鏈表〔葉結(jié)點(diǎn)的孩子鏈表為空表〕，而n個(gè)結(jié)點(diǎn)的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針又組成一個(gè)順序表。3．孩子兄弟表示法以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟〔右兄弟〕結(jié)點(diǎn)。6.4.2

1．樹轉(zhuǎn)換為二叉樹將一棵樹轉(zhuǎn)換為二叉樹的方法是：⑴樹中所有相鄰兄弟之間加一條連線。⑵對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保存其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。

⑶以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次清楚。2．森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹的方法如下：〔1〕將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹?！?〕

第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。

3．二叉樹復(fù)原為樹或森林將一棵二叉樹復(fù)原為樹或森林，具體方法如下：〔1〕假設(shè)某結(jié)點(diǎn)是其雙親的左孩子，那么把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、……都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái)?！?〕刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線?！?〕整理由〔1〕、〔2〕兩步所得到的樹或森林，使之結(jié)構(gòu)層次清楚。

樹與森林的遍歷1．樹的遍歷樹的遍歷方法主要有以下兩種：1〕

先根遍歷假設(shè)樹非空，那么遍歷方法為：⑴訪問(wèn)根結(jié)點(diǎn)。⑵從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹。

2〕

后根遍歷假設(shè)樹非空，那么遍歷方法為：〔1〕從左到右，依次后根遍歷根結(jié)點(diǎn)的每一棵子樹?！?〕訪問(wèn)根結(jié)點(diǎn)。

二、森林的遍歷森林的遍歷方法主要有以下三種：1〕

先序遍歷假設(shè)森林非空，那么遍歷方法為：⑴

訪問(wèn)森林中第一棵樹的根結(jié)點(diǎn)。⑵先序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林。⑶先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。2〕

中序遍歷假設(shè)森林非空，那么遍歷方法為：⑴中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。⑵訪問(wèn)第一棵樹的根結(jié)點(diǎn)。⑶中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

3〕

后序遍歷假設(shè)森林非空，那么遍歷方法為：⑴后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林。⑵后序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。⑶訪問(wèn)第一棵樹的根結(jié)點(diǎn)。

6.5

哈夫曼樹及其應(yīng)用6.5.1

1．路徑和路徑長(zhǎng)度路徑是指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支序列，路徑長(zhǎng)度是指從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過(guò)的分支數(shù)目。2．結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度在實(shí)際的應(yīng)用中，人們常常給樹的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的實(shí)數(shù)，我們稱該實(shí)數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)。在樹型結(jié)構(gòu)中，我們把從樹根到某一結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。3．樹的帶權(quán)路徑長(zhǎng)度樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為：其中n為葉子結(jié)點(diǎn)的個(gè)數(shù)，wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值，li為第i個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。4．哈夫曼樹哈夫曼樹又叫最優(yōu)二叉樹，它是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度WPL最短的二叉樹。構(gòu)造哈夫曼算法的算法步驟如下：〔1〕

用給定的n個(gè)權(quán)值{w1,w2,…,wn}對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的森林F={T1,T2,…,Tn}，其中每一棵二叉樹Ti(1≤i≤n)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹為空?！?〕

在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標(biāo)記新二叉樹的根結(jié)點(diǎn)權(quán)值為其左右子樹的根結(jié)點(diǎn)權(quán)值之和?！?〕

從F中刪除被選中的那兩棵二叉樹，同時(shí)把新構(gòu)成的二叉樹參加到森林F中?！?〕

重復(fù)〔2〕、〔3〕操作，直到森林中只含有一棵二叉樹為止，此時(shí)得到的這棵二叉樹就是哈夫曼樹。第7章

圖[教學(xué)目標(biāo)]圖是一種重要的非線性結(jié)構(gòu)，在系統(tǒng)工程，控制論，人工智能，編譯系統(tǒng)等領(lǐng)域中有廣泛的應(yīng)用，熟練掌握其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)各種運(yùn)算。。[重點(diǎn)、難點(diǎn)]圖的抽象數(shù)據(jù)類型定義，圖的實(shí)現(xiàn)〔鄰接矩陣、鄰接表、十字鏈表〕，圖的遍歷，圖的應(yīng)用〔用普里姆算法求最小生成樹、拓?fù)渑判颉㈥P(guān)鍵路徑、用迪杰斯特拉算法求最短路徑〕。[教學(xué)方法]采用講授、提問(wèn)、論證上機(jī)等方法實(shí)現(xiàn)。[學(xué)習(xí)要點(diǎn)]1.熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系。2.熟練掌握?qǐng)D的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索的兩種形式和廣度優(yōu)先搜索的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹的遍歷算法之間的類似和差異。樹的先根遍歷是一種深度優(yōu)先搜索策略，樹的層次遍歷是一種廣度優(yōu)先搜索策略。3.應(yīng)用圖的遍歷算法求解各種簡(jiǎn)單路徑問(wèn)題。7．1

圖的定義與根本術(shù)語(yǔ)圖的定義圖(Graph)是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，其形式化定義如下：Graph=〔V，R〕DataObject為一個(gè)集合，該集合中的所有元素具有相同的特性。V中的數(shù)據(jù)元素通常稱為頂點(diǎn)〔vertex〕，VR是兩個(gè)頂點(diǎn)之間的關(guān)系的集合。P〔x，y〕表示x和y之間有特定的關(guān)聯(lián)屬性P。假設(shè)<x，y>∈VR，那么<x，y>表示從頂點(diǎn)x到頂點(diǎn)y的一條弧〔arc〕，并稱x為弧尾〔tail〕或起始點(diǎn)，稱y為弧頭〔head〕或終端點(diǎn)，此時(shí)圖中的邊是有方向的，稱這樣的圖為有向圖。假設(shè)<x，y>∈VR，必有<y，x>∈VR，即VR是對(duì)稱關(guān)系，這時(shí)以無(wú)序?qū)Α瞲，y〕來(lái)代替兩個(gè)有序?qū)Γ硎緓和y之間的一條邊〔edge〕，此時(shí)的圖稱為無(wú)向圖。根本術(shù)語(yǔ)1．完全圖、稀疏圖與稠密圖設(shè)n表示圖中頂點(diǎn)的個(gè)數(shù)，用e表示圖中邊或弧的數(shù)目，并且不考慮圖中每個(gè)頂點(diǎn)到其自身的邊或弧。即假設(shè)<vi，vj>∈VR，那么vi≠vj。對(duì)于無(wú)向圖而言，其邊數(shù)e的取值范圍是0~n〔n-1〕/2。稱有n〔n-1〕/2條邊〔圖中每個(gè)頂點(diǎn)和其余n-1個(gè)頂點(diǎn)都有邊相連〕的無(wú)向圖為無(wú)向完全圖。對(duì)于有向圖而言，其邊數(shù)e的取值范圍是0~n〔n-1〕。稱有n〔n-1〕條邊〔圖中每個(gè)頂點(diǎn)和其余n-1個(gè)頂點(diǎn)都有弧相連〕的有向圖為有向完全圖。對(duì)于有很少條邊的圖〔e<nlogn〕稱為稀疏圖，反之稱為稠密圖。2．子圖設(shè)有兩個(gè)圖G=〔V，{E}〕和圖G/=〔V/，{E/}〕,假設(shè)V/≤V且E/≤E那么稱圖G/為G的子圖。3。鄰接點(diǎn)對(duì)于無(wú)向圖G=〔V，{E}〕，如果邊〔v，v/〕∈E，那么稱頂點(diǎn)v，v/互為鄰接點(diǎn)，即v，v/相鄰接。邊〔v，v/〕依附于頂點(diǎn)v和v/，或者說(shuō)邊〔v，v/〕與頂點(diǎn)v和v/相關(guān)聯(lián)。對(duì)于有向圖G=〔V，{A}〕而言，假設(shè)弧<v，v/>∈A，那么稱頂點(diǎn)v鄰接到頂點(diǎn)v/，頂點(diǎn)v/鄰接自頂點(diǎn)v，或者說(shuō)弧<v，v/>與頂點(diǎn)v，v/相關(guān)聯(lián)。4。度、入度和出度：對(duì)于無(wú)向圖而言，頂點(diǎn)v的度是指和v相關(guān)聯(lián)的邊的數(shù)目，記作TD〔v〕。例如：圖中G2中頂點(diǎn)V3的度是3，V1的度是2；在有向圖中頂點(diǎn)v的度有出度和入度兩局部，其中以頂點(diǎn)v為弧頭的弧的數(shù)目成為該頂點(diǎn)的入度，記作ID〔v〕，以頂點(diǎn)v為弧尾的弧的數(shù)目稱為該頂點(diǎn)的出度，記作OD〔v〕那么頂點(diǎn)v的度為TD〔v〕=ID〔v〕+OD〔v〕。5。權(quán)與網(wǎng)在實(shí)際應(yīng)用中，每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或消耗等信息。將這種帶權(quán)的圖叫做賦權(quán)圖或網(wǎng)。

6．路徑與回路在一個(gè)路徑中，假設(shè)其第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)是相同的即v=v/，那么稱該路徑為一個(gè)回路或環(huán)。假設(shè)表示路徑的頂點(diǎn)序列中的頂點(diǎn)各不相同，那么稱這樣的路徑為簡(jiǎn)單路徑。除了第一個(gè)和最后一個(gè)頂點(diǎn)外，其余各頂點(diǎn)均不重復(fù)出現(xiàn)的回路為簡(jiǎn)單回路。

7。連通圖在無(wú)向圖G=〔V，{E}〕中，假設(shè)從vi到vj有路徑相通，那么稱頂點(diǎn)vi與vj是連通的。如果對(duì)于圖中的任意兩個(gè)頂點(diǎn)vi、vj∈V，vi，vj都是連通的，那么稱該無(wú)向圖G為連通圖。無(wú)向圖中的極大連通子圖稱為該無(wú)向圖的連通分量。在有向圖G=〔V，{A}〕中，假設(shè)對(duì)于每對(duì)頂點(diǎn)vi、vj∈V且vi≠vj，從vi到vj和vj到vi都有路徑，那么稱該有向圖為強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱作有向圖的強(qiáng)連通分量。8。生成樹一個(gè)連通圖的生成樹是指一個(gè)極小連通子圖，它含有圖中的全部頂點(diǎn)，但只有足已構(gòu)成一棵樹的n-1條邊。7．2

圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)方法有很多，本節(jié)我們將介紹四種比擬常用的存儲(chǔ)表示法：①鄰接矩陣表示法；②鄰接表；③鄰接多重表；④十字鏈表。7．2．1鄰接矩陣表示法圖的鄰接矩陣表示法〔AdjacencyMatrix〕也稱作數(shù)組表示法。假設(shè)G是一具有n個(gè)結(jié)點(diǎn)的無(wú)權(quán)圖，G的鄰接矩陣是具有如下性質(zhì)的n×n矩陣A：

7．2．3十字鏈表有向圖中的每一條弧對(duì)應(yīng)十字鏈表中的一個(gè)弧結(jié)點(diǎn)，同時(shí)有向圖中的每個(gè)頂點(diǎn)在十字鏈表中對(duì)應(yīng)有一個(gè)結(jié)點(diǎn)，叫做頂點(diǎn)結(jié)點(diǎn)。這兩類結(jié)點(diǎn)結(jié)構(gòu)如下圖。

7．2．4鄰接多重表鄰接多重表是指將圖中關(guān)于一條邊的信息用一個(gè)結(jié)點(diǎn)來(lái)表示，其結(jié)點(diǎn)結(jié)構(gòu)如圖〔a〕所示，圖中的每一個(gè)頂點(diǎn)也對(duì)應(yīng)一個(gè)頂點(diǎn)結(jié)點(diǎn)。7．3

圖的遍歷對(duì)于圖的遍歷，通常有兩種方法，即深度優(yōu)先搜索和廣度優(yōu)先搜索。這兩種遍歷方法對(duì)于無(wú)向圖和有向圖均適用。7．3．1深度優(yōu)先搜索所謂的深度優(yōu)先搜索〔Depth_FirstSearch〕是指按照深度方向搜索，它類似于樹的先根遍歷，是樹的先根遍歷的推廣。7．3．2廣度優(yōu)先搜索所謂的廣度優(yōu)先搜索〔Breadth_FirstSearch〕是指按照廣度方向搜索，它類似于樹的按層次遍歷，是樹的按層次遍歷的推廣。7．4

圖的連通性問(wèn)題7．4．1無(wú)向圖的連通分量可以利用圖的遍歷過(guò)程來(lái)判斷一個(gè)圖是否連通。如果在遍歷的過(guò)程中，不止一次調(diào)用搜索過(guò)程，那么說(shuō)明該圖就是一個(gè)非連通圖。幾次調(diào)用搜索過(guò)程，該圖就有幾個(gè)連通分量。7．4．2最小生成樹在一個(gè)連通網(wǎng)的所有生成樹中，各邊的代價(jià)之和最小的那棵生成樹稱為該連通網(wǎng)的最小代價(jià)生成樹〔MinimumCostSpanningTree〕，簡(jiǎn)稱為最小生成樹。7．5

有向無(wú)環(huán)圖的應(yīng)用有向無(wú)環(huán)圖〔DirectedAcyclicGraph〕是指一個(gè)無(wú)環(huán)的有向圖，簡(jiǎn)稱DAG。有向無(wú)環(huán)圖可用來(lái)描述工程或系統(tǒng)的進(jìn)行過(guò)程，如一個(gè)工程的施工圖、學(xué)生課程間的制約關(guān)系圖等。7．5．1拓?fù)渑判颉睺opologicalSort〕用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向無(wú)環(huán)圖，稱為頂點(diǎn)表示活動(dòng)的網(wǎng)〔ActivityOnVertexNetwork〕，簡(jiǎn)稱為AOV-網(wǎng)。7．5．2關(guān)鍵路徑有向圖在工程方案和經(jīng)營(yíng)管理中有著廣泛的應(yīng)用。通常用有向圖來(lái)表示工程方案時(shí)有兩種方法：

用頂點(diǎn)表示活動(dòng)，用有向弧表示活動(dòng)間的優(yōu)先關(guān)系，即上節(jié)所討論的AOV網(wǎng)。

用頂點(diǎn)表示事件，用弧表示活動(dòng)，弧的權(quán)值表示活動(dòng)所需要的時(shí)間。我們把用第二種方法構(gòu)造的有向無(wú)環(huán)圖叫做邊表示活動(dòng)的網(wǎng)〔ActivityOnEdgeNetwork〕,簡(jiǎn)稱AOE網(wǎng)。

AOE網(wǎng)在工程方案和管理中很有用。在研究實(shí)際問(wèn)題時(shí)，人們通常關(guān)心的是：

哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？

至少需要多長(zhǎng)時(shí)間能完成整個(gè)工程？在AOE網(wǎng)中存在唯一的、入度為零的頂點(diǎn)，叫做源點(diǎn)；存在唯一的、出度為零的頂點(diǎn)，叫做匯點(diǎn)。從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度即為完成整個(gè)工程任務(wù)所需的時(shí)間，該路徑叫做關(guān)鍵路徑。關(guān)鍵路徑上的活動(dòng)叫做關(guān)鍵活動(dòng)。這些活動(dòng)中的任意一項(xiàng)活動(dòng)未能按期完成，那么整個(gè)工程的完成時(shí)間就要推遲。相反，如果能夠加快關(guān)鍵活動(dòng)的進(jìn)度，那么整個(gè)工程可以提前完成。

第8章

查找[教學(xué)目標(biāo)]在非數(shù)值運(yùn)算問(wèn)題中，數(shù)據(jù)存儲(chǔ)量很大，為了在大量信息中快速找到某些數(shù)據(jù)，需要借助有效的查找技術(shù)。要求熟練掌握查找技術(shù)的思想和方法。[重點(diǎn)、難點(diǎn)]順序查找、折半查找、分塊查找、二叉排序樹、哈希表。[教學(xué)方法]采用問(wèn)答行為方法及多媒體演示。[學(xué)習(xí)要點(diǎn)]1.熟練掌握順序表和有序表的查找方法。2.熟悉靜態(tài)查找樹的構(gòu)造方法和查找算法，理解靜態(tài)查找樹和折半查找的關(guān)系。3.熟練掌握二叉排序樹的構(gòu)造和查找方法。4.熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差異。查找的根本概念列表：由同一類型的數(shù)據(jù)元素〔或記錄〕構(gòu)成的集合，可利用任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。關(guān)鍵字：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)列表中的一個(gè)或一組數(shù)據(jù)元素。如果一個(gè)關(guān)鍵字可以唯一標(biāo)識(shí)列表中的一個(gè)數(shù)據(jù)元素，那么稱其為主關(guān)鍵字，否那么為次關(guān)鍵字。當(dāng)數(shù)據(jù)元素僅有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，數(shù)據(jù)元素的值就是關(guān)鍵字。查找：根據(jù)給定的關(guān)鍵字值，在特定的列表中確定一個(gè)其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。。平均查找長(zhǎng)度：為確定數(shù)據(jù)元素在列表中的位置，需和給定值進(jìn)行比擬的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。查找的根本方法可以分為兩大類，即比擬式查找法和計(jì)算式查找法。8.2

基于線性表的查找法

方法具體可分為順序查找法、折半查找法以及分塊查找法。

順序查找法用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個(gè)比擬，直到成功或失敗。存儲(chǔ)結(jié)構(gòu)通常為順序結(jié)構(gòu)，也可為鏈?zhǔn)浇Y(jié)構(gòu)。折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。

折半查找方法的優(yōu)點(diǎn)是比擬次數(shù)少，查找速度快，平均性能好；其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。

分塊查找法分塊查找法要求將列表組織成以下索引順序結(jié)構(gòu)：首先將列表分成假設(shè)干個(gè)塊〔子表〕。一般情況下，塊的長(zhǎng)度均勻，最后一塊可以不滿。每塊中元素任意排列，即塊內(nèi)無(wú)序，但塊與塊之間有序。8.3

基于樹的查找法

基于樹的查找法又稱為樹表查找法，是將待查表組織成特定樹的形式并在樹結(jié)構(gòu)上實(shí)現(xiàn)查找的方法，主要包括二叉排序樹等。

二叉排序樹二叉排序樹又稱為二叉查找樹，它是一種特殊結(jié)構(gòu)的二叉樹，其定義為：二叉樹排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：

〔1〕假設(shè)它的左子樹非空，那么左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

〔2〕假設(shè)它的右子樹非空，那么右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；

〔3〕它的左右子樹也分別為二叉排序樹。1．二叉排序樹的插入和生成一個(gè)關(guān)鍵字值為key的結(jié)點(diǎn)s，假設(shè)將其插入到二叉排序樹中，只要保證插入后仍符合二叉排序樹的定義即可。2．二叉排序樹的刪除分三種情況討論：1)

假設(shè)p為葉結(jié)點(diǎn)，那么可直接將其刪除：f->lchild=NULL；free(p)；2)

假設(shè)p結(jié)點(diǎn)只有左子樹，或只有右子樹，那么可將p的左子樹或右子樹，直接改為其雙親結(jié)點(diǎn)f的左子樹。即：f->lchild=p->lchild〔或f->lchild=p->rchild〕；free(p)；3)

假設(shè)p既有左子樹，又有右子樹

方法1:

首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，如圖8.6(b)所示，然后將p的左子樹改為f的左子樹，而將p的右子樹改為s的右子樹：f->lchild=p->lchild；s->rchild=p->rchild；free(p)。

方法2:

首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，如圖8.6(b)所示，然后用s結(jié)點(diǎn)的值，替代p結(jié)點(diǎn)的值，再將s結(jié)點(diǎn)刪除，原s結(jié)點(diǎn)的左子樹改為s的雙親結(jié)點(diǎn)q的右子樹：p->data=s->data；q->rchild=s->lchild；free(s)；。3.二叉排序樹的查找

根據(jù)二叉排序樹的特點(diǎn)，首先將待查關(guān)鍵字k與根結(jié)點(diǎn)關(guān)鍵字t進(jìn)行比擬，如果：1〕k=t：那么返回根結(jié)點(diǎn)地址；2〕k<t：那么進(jìn)一步查左子樹；3〕k>t：那么進(jìn)一步查右子樹。8.4

計(jì)算式查找法——哈希法

哈希法又稱散列法、雜湊法以及關(guān)鍵字地址計(jì)算法等，相應(yīng)的表稱為哈希表。這種方法的根本思想是：首先在元素的關(guān)鍵字k和元素的存儲(chǔ)位置p之間建立一個(gè)對(duì)應(yīng)關(guān)系f，使得p=f(k)，f稱為哈希函數(shù)。

當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映象到哈希表的同一地址上，即k1≠k2，但H〔k1〕=H〔k2〕，這種現(xiàn)象稱為沖突，此時(shí)稱k1和k2為同義詞。1．?dāng)?shù)字分析法

如果事先知道關(guān)鍵字集合，并且每個(gè)關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時(shí)，可以從關(guān)鍵字中選出分布較均勻的假設(shè)干位，構(gòu)成哈希地址。2．平方取中法當(dāng)無(wú)法確定關(guān)鍵字中哪幾位分布較均勻時(shí)，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。3．分段疊加法

這種方法是按哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾局部〔最后一局部可以較短〕，然后將這幾局部相加，舍棄最高進(jìn)位后的結(jié)果就是該關(guān)鍵字的哈希地址。4．除留余數(shù)法假設(shè)哈