數(shù)據(jù)結(jié)構(gòu)（從概念到算法）課件

第4章字符串、多維數(shù)組與廣義表01020304目錄CONTENTS05字符串多維數(shù)組廣義表應(yīng)用實(shí)例本章小結(jié)01PART字符串4.1.1字符串的定義字符串是由零個(gè)或者多個(gè)字符組成的有限序列，一般記為：S="a1

a2…an"（n≥0）其中S是字符串的名稱；雙引號(hào)（""）括起來的字符序列為串值，雙引號(hào)本身不屬于串值，只是代表串的起止標(biāo)記；序列中的ai（1≤i≤n）可以是字母、數(shù)字和其他字符，i稱為字符ai

在該串中的位置；n表示串的長(zhǎng)度，即串中包含的字符個(gè)數(shù)，當(dāng)n=0時(shí)，稱為空串（nullstring）；僅含若干個(gè)空格的串稱為空格串。將字符串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，對(duì)應(yīng)地，將包含子串的串稱為主串。子串在主串中的位置是指子串的第一個(gè)字符在主串中的位置。字符串4.1.1字符串的定義串是線性表的一個(gè)特例，其特殊性體現(xiàn)在每一個(gè)數(shù)據(jù)元素就是一個(gè)字符，因此完全可以沿用線性表定義的操作、線性表的存儲(chǔ)方案。然而，在實(shí)際應(yīng)用中，對(duì)字符串的處理較少涉及對(duì)單個(gè)字符的處理，一般都是涉及對(duì)串進(jìn)行整體操作。基于這個(gè)原因，給出如下串的抽象數(shù)據(jù)類型定義。字符串4.1.2字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)與線性表類似，通常字符串也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩大類，對(duì)應(yīng)的有順序串和鏈串。而順序存儲(chǔ)又可以細(xì)分為靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配，這樣字符串的存儲(chǔ)結(jié)構(gòu)就可以分為3類。1．靜態(tài)存儲(chǔ)分配的順序串該存儲(chǔ)結(jié)構(gòu)就是通過字符數(shù)組的方式分配連續(xù)的存儲(chǔ)空間來保存串值。數(shù)組的存儲(chǔ)空間是在編譯時(shí)確定的，并且運(yùn)行時(shí)不能改變連續(xù)空間的大小，這樣能表示的字符串長(zhǎng)度最大值就固定下來了，所以這種形式表示的串也稱為串的定長(zhǎng)順序存儲(chǔ)表示。示例如下：字符串4.1.2字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)由這個(gè)定義可知，S就是一個(gè)大小為256的字符數(shù)組，最多能存放256個(gè)字符。如果用它來表示串，我們就需要明確指示串的尾部在什么位置。一般需要1個(gè)字符的單元來表示這個(gè)邊界，還剩下255個(gè)字符單元，所以S能夠表示的串最大長(zhǎng)度就是255，如果超過這個(gè)最大值，我們就必須截取，丟棄超長(zhǎng)部分，造成數(shù)據(jù)的丟失。不同高級(jí)語(yǔ)言中會(huì)采用不同的方式表示這個(gè)邊界，如C語(yǔ)言中以“\0”表示串的結(jié)束；再如，Pascal語(yǔ)言用第一個(gè)字符的單元記錄長(zhǎng)度，即用S[0]記錄串長(zhǎng)。這樣分別對(duì)應(yīng)方式一和方式二兩種形式的順序串，如下圖所示。字符串4.1.2字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)2．動(dòng)態(tài)存儲(chǔ)分配的順序串由于定長(zhǎng)順序串的空間是在編譯階段就確定的，運(yùn)行階段不能夠改變空間大小，這樣就會(huì)出現(xiàn)一些常見的問題：預(yù)留空間太大、串長(zhǎng)較小而造成空間的浪費(fèi)；如果空間不是足夠大，在做插入、聯(lián)接操作時(shí)可能會(huì)舍棄超長(zhǎng)部分，造成數(shù)據(jù)的丟失。為此，我們可以考慮采用線性表中動(dòng)態(tài)存儲(chǔ)分配的順序表，利用動(dòng)態(tài)分配函數(shù)malloc，根據(jù)串長(zhǎng)來申請(qǐng)分配串需要的空間，并用free函數(shù)來釋放串空間。由于使用malloc函數(shù)申請(qǐng)內(nèi)存空間時(shí)是在程序運(yùn)行時(shí)邏輯空間中的堆空間（heapspace）進(jìn)行的，所以動(dòng)態(tài)存儲(chǔ)分配的順序串也被稱為串的堆存儲(chǔ)分配表示。其數(shù)據(jù)類型的定義如下：字符串4.1.2字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)這樣，通過HStringS定義的變量S來表示串“Iamastudent”時(shí)，就可以根據(jù)串長(zhǎng)在堆空間分配內(nèi)存單元，地址保存在S.ch，串長(zhǎng)記錄在S.length中，如下圖所示。字符串4.1.2字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)3．串的鏈?zhǔn)酱鎯?chǔ)與線性表類似，串也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示，如使用單鏈表，串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為鏈串，如下圖（a）所示。使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)能方便地進(jìn)行插入與刪除等操作，且能避免大量移動(dòng)字符。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類型定義如下。字符串4.1.2字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)如果在一個(gè)結(jié)點(diǎn)存放1個(gè)字符，占1字節(jié)，在32位系統(tǒng)中指針需要占4字節(jié)，所以鏈串的存儲(chǔ)密度為20%，存儲(chǔ)密度是相當(dāng)?shù)偷?；如果?4位系統(tǒng)，存儲(chǔ)密度會(huì)更低。為了提高存儲(chǔ)密度，這里可以考慮在一個(gè)結(jié)點(diǎn)中存放多個(gè)字符，比如放4個(gè)字符，如圖（b）所示。通常將一個(gè)結(jié)點(diǎn)數(shù)據(jù)域存放的字符數(shù)定義為結(jié)點(diǎn)大小。對(duì)于一個(gè)非空串，由于串的長(zhǎng)度不一定正好是結(jié)點(diǎn)大小的整數(shù)倍，因此在最后一個(gè)結(jié)點(diǎn)需要填充特殊的符號(hào)，代表串的結(jié)束。對(duì)于結(jié)點(diǎn)大小大于1的鏈?zhǔn)酱鎯?chǔ)，其類型定義的一般形式如下。字符串4.1.2字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)雖然通過調(diào)大結(jié)點(diǎn)能夠提高存儲(chǔ)密度，但同時(shí)串的操作會(huì)變得復(fù)雜，串的插入和刪除操作同樣會(huì)移動(dòng)大量的字符。例如，在圖（b）所示的串位置3之前插入串"XYZ"，就需要將位置3后續(xù)所有結(jié)點(diǎn)中的字符進(jìn)行移動(dòng)，其中一些字符還是跨結(jié)點(diǎn)移動(dòng)，結(jié)果如圖4.3（c）所示。由此可見，當(dāng)使用結(jié)點(diǎn)大小大于1的鏈?zhǔn)酱鎯?chǔ)時(shí)，對(duì)一些串的操作會(huì)變得不太方便，不如順序串的操作簡(jiǎn)單和靈活。字符串4.1.3字符串的模式匹配算法子串定位操作StrIndex(S,T,pos)，求串T在S中第pos個(gè)字符后第一次出現(xiàn)的位置。子串定位操作也稱為串的模式匹配，其中主串S稱為目標(biāo)串，子串T稱為模式串。假定目標(biāo)串S的長(zhǎng)度為n，模式串T的長(zhǎng)度為m，S和T分別表示如下。在實(shí)際應(yīng)用中，通常m遠(yuǎn)小于n，即m?n。S="s1s2…sn"T="t1t2…tm“串模式匹配操作就是在目標(biāo)串S中找到一個(gè)與模式串T相等的子串"sisi+1…si+m-1"，這里i取符合條件的最小值（pos≤i≤n-m）。如果存在這樣的i，表示匹配成功，否則表示匹配失敗，模式串T不是目標(biāo)串S的子串。字符串4.1.3字符串的模式匹配算法1．樸素的模式匹配算法假設(shè)目標(biāo)串S和模式串T都采用定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)，用指示變量i來表示每次進(jìn)行匹配時(shí)目標(biāo)串S的起點(diǎn)位置，初始值為pos。每次匹配從目標(biāo)串S第i個(gè)字符開始，與模式串T的字符依次比較，如果S[i]……S[i+m-1]與T[1]……T[m]依次對(duì)應(yīng)相等，則匹配成功，返回i值，否則i加1，測(cè)試下一個(gè)匹配起點(diǎn)，進(jìn)行下一次匹配。如果所有可能的匹配起點(diǎn)測(cè)試后都沒有匹配成功，返回0。字符串4.1.3字符串的模式匹配算法該算法采用的是暴力求解方式，該算法也稱為樸素的模式匹配算法。其中，模式匹配算法如下。字符串4.1.3字符串的模式匹配算法2．一種改進(jìn)的模式匹配算法采用樸素的模式匹配算法進(jìn)行匹配的過程中，一旦出現(xiàn)S[i]≠T[j]，就結(jié)束本次匹配過程，將模式串T向后滑動(dòng)1個(gè)字符的位置，j回到1，i回到下一輪匹配的起點(diǎn)，開始新的一輪匹配。這種算法思想簡(jiǎn)單明了，很容易理解。但由于沒有充分地分析模式串T的特征，所以該算法的效率不高。不少學(xué)者在模式匹配算法優(yōu)化方面做了大量的研究工作，提出不少效率較高的算法，其中KMP算法就是一個(gè)有代表性的改進(jìn)算法。字符串4.1.3字符串的模式匹配算法在模式匹配過程中，一旦S[i]≠T[j]，就會(huì)出現(xiàn)一次失敗的模式匹配如下圖所示。為了表示方便，下圖中用si表示S[i]，tj表示T[j]。對(duì)于模式串T

的字符tj，如果存在一個(gè)

k（1<k<j），使“t1t2…tk-1”=“tj-k+1tj-k+2…tj-1”，即模式串T

的前

k-1

個(gè)字符組成的子串與T

[j]之前k-1

個(gè)字符組成的子串是相等的，根據(jù)匹配過程，有“sj-k+1sj-k+2…sj-1”=“tj-k+1tj-k+2…tj-1”，所以可以推導(dǎo)出“sj-k+1sj-k+2…sj-1”=“t1t2…tk-1”。就沒有必要讓j恢復(fù)到1，i回到本次匹配的起點(diǎn)之后，需要做的就是將k賦予j實(shí)現(xiàn)滑動(dòng)模式串T，使T[k]（對(duì)應(yīng)tk）與S[i]（對(duì)應(yīng)si）對(duì)齊；將模式串T的第k個(gè)字符（也是T[j]）與S[i]繼續(xù)比較即可，避免了對(duì)模式串T的前k-1個(gè)字符做重復(fù)比較。這個(gè)處理方式中，i沒有回退動(dòng)作，j也不一定回到模式串T的起點(diǎn)，顯然提高了匹配效率。字符串4.1.3字符串的模式匹配算法

基于上述思想，在進(jìn)行匹配之前，首先需要對(duì)模式串T進(jìn)行分析，對(duì)模式串T的每一個(gè)位置j需要求出一個(gè)滿足上述性質(zhì)的k值，記作next[j]=k。這樣，在匹配過程中，一旦出現(xiàn)S[i]≠T[j]，就可以通過修改j值為k，實(shí)現(xiàn)滑動(dòng)模式串T的動(dòng)作，繼續(xù)進(jìn)行比較。next[j]的公式如下。

next[j]的本質(zhì)，就是求解滿足"t1t2…tk-1"="tj-k+1tj-k+2…tj-1"的最大真子串"t1t2…tk-1"，即最大k值，使得一旦出現(xiàn)S[i]≠T[j]時(shí)，通過賦值操作j=k，將模式串T向后滑動(dòng)j-k字符的位置，T[k]與S[i]對(duì)齊，最大限度減少重復(fù)比較次數(shù)，從而提高算法效率。字符串4.1.3字符串的模式匹配算法

其中，KMP算法如下。字符串4.1.3字符串的模式匹配算法

下面是對(duì)模式串T進(jìn)行分析，求next[j]值的算法。該算法采用遞推的思想，根據(jù)next[1],…,next[j]的值來求解next[j+1]。02PART多維數(shù)組4.2.1多維數(shù)組概念的引入

多維數(shù)組4.2.2多維數(shù)組的順序存儲(chǔ)本小節(jié)介紹分配連續(xù)的存儲(chǔ)單元，保存全部的數(shù)組元素，即數(shù)組的順序表示。在順序表示中，要考慮的有這樣幾個(gè)問題：①需要多大的空間；②如何來放置數(shù)組的元素；③如何管理這個(gè)連續(xù)的空間；④如何訪問數(shù)組元素。一維數(shù)組A=(a1,a2,…,an)需要一個(gè)能存儲(chǔ)n

個(gè)元素的連續(xù)空間，并依據(jù)元素的邏輯次序a1到an，將元素依次存放到這個(gè)連續(xù)空間中。為了管理這些數(shù)據(jù)元素，還需要一個(gè)結(jié)構(gòu)變量A，如下圖所示。該結(jié)構(gòu)變量中要包含連續(xù)空間起始地址、數(shù)組的維數(shù)、每一維的下界和上界。多維數(shù)組4.2.2多維數(shù)組的順序存儲(chǔ)假定b為連續(xù)單元的起始地址，每個(gè)元素占L個(gè)存儲(chǔ)單元，則元素ai前面有i-1個(gè)元素，占有的單元數(shù)為(i-1)L，所以元素ai的地址計(jì)算公式為：LOC(i)=b+(i-1)L=LOC(1)+(i-1)L這個(gè)公式也稱為尋址公式或映像函數(shù)。通過尋址公式，當(dāng)下標(biāo)i合法時(shí)，可以隨機(jī)地訪問元素ai。至于存放方式，二維以上的多維數(shù)組就會(huì)涉及一個(gè)存放次序的問題。第一種方式稱為行序優(yōu)先，即將二維數(shù)組的元素逐行地保存在連續(xù)存儲(chǔ)空間中，存放結(jié)果如左圖所示。多維數(shù)組4.2.2多維數(shù)組的順序存儲(chǔ)第二種方式稱為列序優(yōu)先，即將二維數(shù)組的元素逐列地保存在連續(xù)存儲(chǔ)空間中，存放結(jié)果如下圖所示。同理分析出列序優(yōu)先時(shí)aij的地址計(jì)算公式為：LOC(i,j)=b+((j-1)×m+i-1)L=LOC(1,1)+((j-1)×m+i-1)L多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)對(duì)于一些規(guī)模不大的矩陣，使用二維數(shù)組的順序存儲(chǔ)方式，通常是能夠有效地完成計(jì)算的。但在實(shí)際應(yīng)用中，往往會(huì)出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)矩陣中可能會(huì)出現(xiàn)很多值相同的元素或零元素，這時(shí)，如果還采用順序存儲(chǔ)方式，存儲(chǔ)開銷就會(huì)很大，甚至系統(tǒng)無法滿足存儲(chǔ)要求。基于這個(gè)原因，我們對(duì)這類矩陣需要進(jìn)行壓縮存儲(chǔ)。對(duì)值相同的元素只分配一個(gè)元素的存儲(chǔ)單元，對(duì)零元素則不需要保存，這種存儲(chǔ)方式稱為矩陣的壓縮存儲(chǔ)。矩陣的壓縮存儲(chǔ)有兩類：一類是特殊矩陣的壓縮存儲(chǔ)；另一類是稀疏矩陣的壓縮存儲(chǔ)。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)1．特殊矩陣的壓縮存儲(chǔ)在特殊矩陣中值相同的元素或零元素，其分布都有著一定規(guī)律。考慮其特殊性，不一定要保存全部的數(shù)據(jù)元素，如只保存部分?jǐn)?shù)據(jù)元素，沒有保存

的數(shù)據(jù)元素可以通過分析它們與已保存數(shù)據(jù)元素之間的關(guān)系進(jìn)行訪問。這種矩陣的存儲(chǔ)方式稱為特殊矩陣的壓縮存儲(chǔ)。（1）對(duì)稱矩陣一個(gè)

n

階方陣

A

中的元素如果滿足

aij=aji（1≤i，j≤n），則稱方陣

A

為對(duì)稱矩陣。右圖所示為一個(gè)6

階方陣且為對(duì)稱矩陣。考慮圖中元素之間的對(duì)稱性，這里可以保存約一半多的數(shù)據(jù)元素；剩下未保存的利用其對(duì)稱性進(jìn)行訪問。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)首先，需要明確對(duì)一個(gè)對(duì)稱矩陣需要保存哪些數(shù)據(jù)元素，以及有多少個(gè)元素。由其對(duì)稱性可知aij等于aji，所以對(duì)稱元素只需要保存其中一個(gè)，訪問aij等價(jià)于訪問aji，反之亦然。這樣就只需保存對(duì)角線以下的所有數(shù)據(jù)元素（含對(duì)角線），即下三角部分；或者只需保存對(duì)角線以上的所有數(shù)據(jù)元素（含對(duì)角線），即上三角部分。如圖所示，以行序優(yōu)先的方式將下三角存儲(chǔ)到一維數(shù)組SA中，其中aij對(duì)應(yīng)存儲(chǔ)在SA[k]。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)（2）三對(duì)角矩陣右圖所示為三對(duì)角矩陣。除其對(duì)角線上的元素外，其他元素值都是0（也可以都是取某一個(gè)特殊值的數(shù)）。三對(duì)角矩陣，只需要存儲(chǔ)3條對(duì)角線上的元素，零元素不需要保存或只保存一個(gè)。下圖以行序優(yōu)先的方式將對(duì)角線上元素存儲(chǔ)到一維數(shù)組SA中，其中aij對(duì)應(yīng)存儲(chǔ)在SA[k]，零元素（或某一個(gè)特殊值的數(shù)）存儲(chǔ)在SA[0]中。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)2．稀疏矩陣的壓縮存儲(chǔ)實(shí)際應(yīng)用中，常常會(huì)遇到一種矩陣，其零元素很多，非零元素很少，且非零元素在矩陣中的位置沒有特定的規(guī)律，稱這種矩陣為稀疏矩陣。稀疏矩陣沒有一個(gè)明確的定義，只是從形式上看，非零元素的個(gè)數(shù)占元素總數(shù)的比例低于某特定的閾值。下圖中矩陣M和其轉(zhuǎn)置矩陣N各有42個(gè)數(shù)組元素，其中只有8個(gè)是非零元素。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)由于圖中非0元素很少，因此只需保存這些非零元素，沒有保存的都是零元素。為了標(biāo)明每個(gè)非零元素在矩陣中的位置，可以用(行,列,值)的三元組形式來表示非零元素。將所有的非零元素，按行序優(yōu)先的方式排列起來，就得到一個(gè)三元組的線性表，再加上稀疏矩陣的行數(shù)和列數(shù)這兩個(gè)屬性值組成的二元組，得到的這種特殊線性表稱為三元組表。由三元組表能唯一地確定稀疏矩陣。三元組表這種特殊線性表參照線性表的存儲(chǔ)結(jié)構(gòu)，既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)（1）三元組順序表以順序存儲(chǔ)結(jié)構(gòu)來表示三元組表，得到稀疏矩陣的一種壓縮存儲(chǔ)方式，我們稱這種存儲(chǔ)方式為三元組順序表。數(shù)據(jù)類型定義如下。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)有了三元組順序表類型TriSeqList的定義后，就可以使用它定義結(jié)構(gòu)變量來表示一個(gè)稀疏矩陣的三元組表。下表所示為前面圖中稀疏矩陣M和N的三元組順序表。（a）M

的三元組順序表

（b）N

的三元組順序表行號(hào)列號(hào)值11101616321234365228638974517566………………768行號(hào)列號(hào)值11102312252836894336475157666116………………678多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)（2）十字鏈表以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示三元組表，得到稀疏矩陣的另一種壓縮存儲(chǔ)方式。由于二維數(shù)組元素有行關(guān)系和列關(guān)系，因此三元組的結(jié)點(diǎn)需要兩個(gè)指針來維護(hù)這兩個(gè)關(guān)系，于是有了帶兩個(gè)指針的三元組結(jié)點(diǎn)。采用三元組表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，首先是每行非零元素的三元組結(jié)點(diǎn)構(gòu)成一個(gè)單鏈表，然后需要一個(gè)行頭指針數(shù)組來保存所有行的頭指針，同樣需要一個(gè)列頭指針數(shù)組。為了管理這兩個(gè)頭指針數(shù)組，同時(shí)提供完整的矩陣信息，使用一個(gè)結(jié)構(gòu)型數(shù)據(jù)（包含兩個(gè)頭指針數(shù)組的信息及稀疏矩陣的行、列數(shù)等），這種存儲(chǔ)結(jié)構(gòu)稱為十字鏈表。右圖為稀疏矩陣M。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)稀疏矩陣M的十字鏈表存儲(chǔ)結(jié)構(gòu)如下圖所示?？梢姡啃械姆橇阍亟Y(jié)點(diǎn)構(gòu)成一個(gè)單鏈表，其中結(jié)點(diǎn)中的列號(hào)遞增有序；每列的非零元素結(jié)點(diǎn)也構(gòu)成一個(gè)單鏈表，其中結(jié)點(diǎn)中的行號(hào)遞增有序。多維數(shù)組4.2.3矩陣的壓縮存儲(chǔ)十字鏈表的數(shù)據(jù)類型定義如下。03PART廣義表4.3.1廣義表的定義廣義表是線性表的推廣，其也稱為列表。廣義表是n（n≥0）個(gè)元素的有限序列，記為：LS=(a1,a2,L,an)其中，LS表示廣義表名；n表示廣義表LS的長(zhǎng)度；元素ai（1≤i≤n）或者是數(shù)據(jù)元素，或者是廣義表（通常約定用大寫字母表示廣義表的名稱，小寫字母表示數(shù)據(jù)元素）。當(dāng)廣義表的元素是一個(gè)數(shù)據(jù)元素時(shí)，稱其為原子，否則稱該元素為廣義表或子表。廣義表有別于線性表，線性表中的元素僅限于原子項(xiàng)，而廣義表中的元素既可以是原子項(xiàng)，也可以是一個(gè)廣義表這樣的數(shù)據(jù)結(jié)構(gòu)。當(dāng)廣義表非空時(shí)，稱第一個(gè)元素

a1為廣義表

LS

的表頭（head），稱其余元素組成的表(a2,…,an)為廣義表LS

的表尾（tail）。廣義表4.3.1廣義表的定義下面通過一些廣義表的例子，可以幫助理解什么是廣義表。A=()：A

是一個(gè)空廣義表，其長(zhǎng)度為0。B=(x,y)：B

是一個(gè)長(zhǎng)度為2

的廣義表。由于其元素都是原子，因此它也是線性表C=(a,(b,c))：C

是一個(gè)長(zhǎng)度為2

的廣義表。其第一個(gè)元素是原子，第二個(gè)元素是廣義表。D=(A,B,C)：D

是一個(gè)長(zhǎng)度為3

的廣義表。其每個(gè)元素都是廣義表，將A、B

和C

帶入后，D=((),(x,y),(a,(b,c)))。E=(A,D)：E

是一個(gè)長(zhǎng)度為2

的廣義表。其每個(gè)元素都是廣義表，其中A

也是D

的元素。這個(gè)例子表明廣義表允許共享子表。F=(a,F)：F

是一個(gè)長(zhǎng)度為2

的廣義表。其第一個(gè)元素是原子，第二個(gè)元素是廣義表自身。展開后，F(xiàn)=(a,(a,(a,…)))就是一個(gè)無限的廣義表。這個(gè)例子表明廣義表允許遞歸定義。廣義表4.3.1廣義表的定義除了按元素的序列形式定義廣義表外，還可以用圖形的方式表示廣義表，如用小圓圈表示廣義表，如果廣義表有名稱，則將廣義表名稱附在小圓圈內(nèi)；用小正方形表示原子。廣義表結(jié)點(diǎn)用箭頭依次指向它的各個(gè)元素。例如，上面給出的D、E、F這3個(gè)廣義表對(duì)應(yīng)的圖形表示如下圖所示。稱形狀像一棵倒長(zhǎng)著樹的廣義表（如廣義表D）為純表，允許結(jié)點(diǎn)共享的廣義表（如廣義表E）為再入表，形如廣義表F的稱為遞歸表。廣義表4.3.2廣義表的存儲(chǔ)由于廣義表的元素既可以是原子也可以是廣義表，每個(gè)元素所需的空間大小無法統(tǒng)一，很難用一種有效的順序存儲(chǔ)結(jié)構(gòu)表示，因此通常采用鏈?zhǔn)浇Y(jié)構(gòu)表示。根據(jù)元素的類型不同，廣義表中的結(jié)點(diǎn)可分為兩種：一種是原子結(jié)點(diǎn)，它包括兩個(gè)屬性值，即結(jié)點(diǎn)類型和原子的值；另一種是廣義表結(jié)點(diǎn)，由于廣義表非空時(shí)可以分解成表頭和表尾，這樣廣義表結(jié)點(diǎn)包括3個(gè)屬性值，即結(jié)點(diǎn)類型、表頭指針和表尾指針。為了統(tǒng)一管理這兩種結(jié)點(diǎn)，可以采用聯(lián)合形式來為這兩種結(jié)點(diǎn)定義結(jié)點(diǎn)類型。在這個(gè)類型中，公共部分是結(jié)點(diǎn)類型，用以識(shí)別當(dāng)前結(jié)點(diǎn)是原子結(jié)點(diǎn)還是廣義表結(jié)點(diǎn)。根據(jù)結(jié)點(diǎn)類型確定對(duì)結(jié)點(diǎn)的訪問方式，如果是原子結(jié)點(diǎn)，聯(lián)合成員atom有效，否則就是聯(lián)合成員ptr有效，它包含表頭和表尾兩個(gè)指針。廣義表4.3.2廣義表的存儲(chǔ)廣義表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的定義如下。廣義表4.3.2廣義表的存儲(chǔ)這樣就可以通過GList定義一個(gè)廣義表結(jié)點(diǎn)的指針變量來表示一個(gè)廣義表。根據(jù)這個(gè)定義，以廣義表A、B、C和D為例，其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖如下圖所示。廣義表4.3.2廣義表的存儲(chǔ)當(dāng)廣義表的存儲(chǔ)結(jié)構(gòu)確定后，就可以實(shí)現(xiàn)廣義表的基本操作。下面介紹了幾個(gè)常用基本操作的遞歸算法實(shí)現(xiàn)。（1）創(chuàng)建廣義表假定將廣義表定義形式表示成一個(gè)字符串，根據(jù)這個(gè)字符串構(gòu)造廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該算法有兩個(gè)遞歸出口：一個(gè)是字符串為“()”時(shí)，生成空廣義表；另一個(gè)是字符串只包含一個(gè)字符時(shí)，表示原子元素的值，需要生成原子結(jié)點(diǎn)。對(duì)非空廣義表形式的字符串進(jìn)行遞推處理，首先生成一個(gè)廣義表結(jié)點(diǎn)，取廣義表字符串的表頭和表尾字符串，分別由這兩個(gè)字符串構(gòu)造鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)作為廣義表結(jié)點(diǎn)的表頭和表尾。廣義表4.3.2廣義表的存儲(chǔ)（2）廣義表的輸出廣義表的輸出需要根據(jù)廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，輸出其字符串的定義形式。該算法有兩個(gè)遞歸出口：一個(gè)是對(duì)空廣義表，輸出字符串“()”；另一個(gè)是對(duì)原子結(jié)點(diǎn)，顯示原子元素值。對(duì)廣義表結(jié)點(diǎn)，需要采用遞推處理，先輸出表頭，再輸出表尾。

下圖展示了輸出廣義表L的過程。①開始時(shí)L指向的是整個(gè)廣義表，輸出左小括號(hào)；②當(dāng)廣義表結(jié)點(diǎn)表頭指針指向一個(gè)原子結(jié)點(diǎn)時(shí)，輸出原子元素值，如a；③當(dāng)廣義表結(jié)點(diǎn)表頭指針指向廣義表結(jié)點(diǎn)時(shí)，輸出左小括號(hào)（特別地，當(dāng)廣義表結(jié)點(diǎn)表頭指針為空時(shí)，對(duì)應(yīng)輸出是一個(gè)小括號(hào)）；④當(dāng)廣義表結(jié)點(diǎn)表尾指針指向廣義表結(jié)點(diǎn)時(shí)，輸出逗號(hào)；⑤當(dāng)廣義表結(jié)點(diǎn)表尾指針為空時(shí)，輸出右小括號(hào)。這樣下圖的輸出結(jié)果為(a,(b,c,())。廣義表4.3.2廣義表的存儲(chǔ)

04PART應(yīng)用實(shí)例4.4.1最大匹配分詞算法在漢字語(yǔ)言處理中，如何準(zhǔn)確地將漢字序列分離成一個(gè)個(gè)具有實(shí)際意義的詞是其最基礎(chǔ)、最重要的功能之一，這個(gè)功能稱為中文分詞。通常中文分詞算法可分為三大類：基于字符串匹配的分詞算法、基于理解的分詞算法和基于統(tǒng)計(jì)的分詞算法。在基于字符串匹配的分詞算法中，中文分詞需要借助詞典來實(shí)現(xiàn)，詞典的結(jié)構(gòu)以及查找算法的設(shè)計(jì)往往對(duì)分詞算法的效率有很大影響?；谧址ヅ涞姆衷~通常采用最大匹配法算法，它能夠保證將詞典中存在的最長(zhǎng)復(fù)合詞在句子中切分出來。最大匹配法算法又分為正向最大匹配算法和逆向最大匹配算法兩種。應(yīng)用實(shí)例4.4.1最大匹配分詞算法（1）正向最大匹配算法正向最大匹配算法（MaximumMatchingMethod），簡(jiǎn)稱MM算法。具體策略是在計(jì)算機(jī)中存放一個(gè)已知的詞典，假定詞典中的最長(zhǎng)詞有k個(gè)漢字，則在對(duì)句子進(jìn)行分詞時(shí)，首先取句子的前k個(gè)漢字作為匹配串，在詞典中查找。若詞典中存在一個(gè)長(zhǎng)度為k個(gè)漢字的詞與之相等，則匹配成功，將匹配串作為一個(gè)詞從句子中切分出來，對(duì)句子剩余部分繼續(xù)按MM算法進(jìn)行分詞處理；如果詞典中找不到這樣一個(gè)長(zhǎng)度為k個(gè)漢字的詞，則匹配失敗，再取句子的前k-1個(gè)漢字作為匹配串，繼續(xù)在詞典中進(jìn)行匹配處理，如此進(jìn)行下去，直到匹配成功，或者匹配串的長(zhǎng)度為1（注意我們可以默認(rèn)單個(gè)漢字就是一個(gè)詞，即使在詞典中沒有也算一個(gè)詞）。將該詞從句子中切分出來，再對(duì)句子剩余部分繼續(xù)按MM算法進(jìn)行分詞處理，直到句子剩余部分為空，完成句子的分詞。應(yīng)用實(shí)例4.4.1最大匹配分詞算法（2）逆向最大匹配算法逆向最大匹配算法（Reverse

Maximum

Matching

Method），簡(jiǎn)稱

RMM

算法。具體策略與

MM算法相同，兩者區(qū)別是RMM切詞時(shí)，掃描方向是從句子的右到左取匹配串進(jìn)行匹配。以句子“華中科技大學(xué)今日開學(xué)”為例，。采用正向最大匹配算法分詞時(shí)，首先查以“華”字開頭的詞，這里假定字典中的詞最長(zhǎng)為10，這時(shí)就要取出前10個(gè)漢字的匹配串“華中科技大學(xué)今日開學(xué)”在詞典中查找，查找失敗后再取前9個(gè)漢字的匹配串詞典中查找，……匹配串的長(zhǎng)度不斷減1，到了6時(shí)，匹配成功得到第一個(gè)詞“華中科技大學(xué)”；然后將其從句子中去掉，剩下部分為“今日開學(xué)”，假定詞典中沒有這個(gè)詞，但有“今日”和“開學(xué)”，按算法思想，最終得到分詞結(jié)果為：華中科技大學(xué)/今日/開學(xué)。應(yīng)用實(shí)例4.4.1最大匹配分詞算法顯然，這個(gè)算法有很大的盲目性，詞庫(kù)中詞的最大長(zhǎng)度不好確定；另外，在取出匹配串后，可能要與相應(yīng)漢字開頭的所有字符串進(jìn)行比較，

效率大打折扣。為此，需要在詞典的存儲(chǔ)結(jié)構(gòu)和算法流程上進(jìn)行綜合考慮，以提高分詞的效率。首先考慮詞典的存儲(chǔ)結(jié)構(gòu)。在詞典中，將第一個(gè)漢字相同的詞按長(zhǎng)度遞減的方式進(jìn)行存放。為了消除詞庫(kù)中詞的最大長(zhǎng)度對(duì)匹配串提取的影響，以及避免不必要的字符串比較，每個(gè)詞的存放格式是詞的長(zhǎng)度和詞的漢字序列，最后需要一個(gè)結(jié)束標(biāo)記（比如0）代表某漢字開頭的詞到此結(jié)束，后續(xù)是其他漢字開頭的詞。同時(shí)建立一個(gè)索引表，每個(gè)表項(xiàng)包含一個(gè)漢字和該漢字開頭的詞在詞典中的起始位置。右圖就是按這樣方式組織的詞典存儲(chǔ)結(jié)構(gòu)。應(yīng)用實(shí)例4.4.1最大匹配分詞算法算法實(shí)現(xiàn)時(shí)，消除詞庫(kù)中詞的最大長(zhǎng)度這個(gè)屬性值對(duì)算法的影響，根據(jù)實(shí)際情況來取出匹配串進(jìn)行比較，可以避免盲目取匹配串進(jìn)行比較操作。給定一個(gè)待分詞的句子S，依據(jù)詞庫(kù)LexTable進(jìn)行分詞，詞庫(kù)的索引表為indexTable，算法流程如下。（1）當(dāng)

S

非空時(shí)，用

S

的長(zhǎng)度初始化分詞長(zhǎng)度

LexLen，轉(zhuǎn)步驟（2），否則算法結(jié)束。（2）取S

的第一個(gè)漢字到word0，根據(jù)word0

通過indexTable查找得到以word0

中詞開頭的詞在詞庫(kù)中的起始位置

i。如果

i

不為-1，轉(zhuǎn)步驟（3），否則表示詞庫(kù)中沒有以

word0

中詞開頭的詞，此時(shí)可以單獨(dú)將

word0

中詞作為一個(gè)詞，顯示

word0，并從

S

中刪除

word0，轉(zhuǎn)步驟（1）。（3）根據(jù)S長(zhǎng)度計(jì)算S最大可能取出的漢字序列長(zhǎng)度LexLen，通過與LexTable[i]表示的詞長(zhǎng)度LexTable[i][0]進(jìn)行比較，跳過詞庫(kù)中所有以word0開頭且長(zhǎng)度大于LexLen的詞，定位到第一個(gè)長(zhǎng)度不大于LexLen的詞，避免不必要的比較。應(yīng)用實(shí)例4.4.1最大匹配分詞算法（4）當(dāng)i定位到第一個(gè)長(zhǎng)度不大于LexLen的詞LexTable[i]后，根據(jù)該詞的長(zhǎng)度在S中取一個(gè)長(zhǎng)度為L(zhǎng)exTable[i][0]的漢字