數(shù)據(jù)結(jié)構(gòu)（Java語言實(shí)現(xiàn)） 課件 第4章 串、數(shù)組和廣義表

第4章串、數(shù)組和廣義表結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS4.1

串的定義和抽象數(shù)據(jù)類型4.2串的存儲(chǔ)表示4.3串的模式匹配4.6小結(jié)4.4數(shù)組的定義和抽象數(shù)據(jù)類型4.5廣義表4.1串的定義和抽象數(shù)據(jù)類型4.1.1什么是串串（String），也稱為字符串，是由零個(gè)或多個(gè)字符組成的有限序列。串是一種特殊的線性表，僅由字符組成。一般記作：S=”a1a2…an”。其中，S是串名，n是串的長(zhǎng)度。用雙引號(hào)括起來的字符序列是串的值。ai(1≤i≤n)可以是字母、數(shù)字和其他字符。n=0時(shí)，串稱為空串。例如，有四個(gè)串a(chǎn)="tinghuauniversity"、b="tinghua"、c="university"、d="tinghuauniversity"。它們的長(zhǎng)度分別為18、7、10、17，b和c是a和d的子串，b在a和d的位置都為1，c在a的位置是9，c在d的位置是8。4.1串的定義和抽象數(shù)據(jù)類型4.1.2串的抽象數(shù)據(jù)類型串的抽象數(shù)據(jù)類型定義了棧中的數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系及基本操作。棧的抽象數(shù)據(jù)類型定義如下：ADTString{數(shù)據(jù)對(duì)象：D={ai|ai∈CharacterSet，i=1，2，…，n，n≥0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}基本操作：（1）StrAssign(&S,cstr)初始條件：cstr是字符串常量。操作結(jié)果：生成一個(gè)其值等于cstr的串S。（2）StrEmpty(S)初始條件：串S已存在。操作結(jié)果：如果是空串，則返回1，否則返回0。4.1串的定義和抽象數(shù)據(jù)類型（4）StrCopy(&T,S)初始條件：串S已存在。操作結(jié)果：由串S復(fù)制產(chǎn)生一個(gè)與S完全相同的另一個(gè)字符串T。（5）StrCompare(S,T)初始條件：串S和T已存在。操作結(jié)果：比較串S和T的每個(gè)字符的ASCII值的大小，如果S的值大于T，則返回1；如果S的值等于T，則返回0；如果S的值小于T，則返回-1。例如，StrCompare(S,T)=-1，因?yàn)榇甋和串T比較到第13個(gè)字符時(shí)，字符B的ASCII值小于字符S的ASCII值，所以返回-1。（6）StrInsert(&S,pos,T)初始條件：串S和T已存在，且1≤pos≤StrLength(S)+1。操作結(jié)果：在串S的pos個(gè)位置插入串T，如果插入成功，則返回1，否則返回0。例如，如果在串S中的第3個(gè)位置插入字符串"don’t"后，即StrInsert(S,3,"don’t")，串S="Idon’tcomefromBeijing"。4.1串的定義和抽象數(shù)據(jù)類型（7）StrDelete(&S,pos,len)初始條件：串S已存在，且1≤pos≤StrLength(S)-len+1。操作結(jié)果：如果在串S中刪除第pos個(gè)字符開始，長(zhǎng)度為len的字符串。如果找到并刪除成功，則返回1，否則返回0。例如，如果在串S中的第13個(gè)位置刪除長(zhǎng)度為7的字符串后，即StrDelete(S,13,7)，則S="Icomefrom"。（8）StrConcat(&T,S)初始條件：串S和T已存在。操作結(jié)果：將串S連接在串T的后面。如果連接成功，則返回1，否則返回0。例如，如果將串S連接在串T的后面，即StrCat(T,S)，則T="IcomefromShanghaiIcomefromBeijing"。（9）SubString(&Sub,S,pos,len)初始條件：串S已存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-len+1。操作結(jié)果：從串S中截取從第pos個(gè)字符開始，長(zhǎng)度為len的連續(xù)字符，并賦值給Sub。如果截取成功，則返回1，否則返回0。例如，如果將串S中的第8個(gè)字符開始，長(zhǎng)度為4的字符串賦值給Sub，即SubString(Sub,S,8,4)，則Sub="from"。4.1串的定義和抽象數(shù)據(jù)類型（10）StrReplace(&S,T,V)初始條件：串S、T和V已存在，且T為非空串。操作結(jié)果：如果在串S中存在子串T，則用V替換串S中的所有子串T。如果替換操作成功，則返回1，否則返回0。例如，如果將串S中的子串R替換為串V，即StrReplace(S,R,V)，則S="IcomefromChongqing"。（11）StrIndex(S,pos,T)初始條件：串S和T存在，T是非空串，且1≤len≤StrLength(S)。操作結(jié)果：如果主串S中存在與串T的值相等的子串，則返回子串T在主串S中，第pos個(gè)字符之后的第一次出現(xiàn)的位置，否則返回0。例如，在串S中的第4個(gè)字符開始查找，如果串S中存在與子串R相等的子串，則返回R在S中第一次出現(xiàn)的位置，即StrIndex(S,4,R)=13。4.2串的存儲(chǔ)表示4.2.1串的順序存儲(chǔ)結(jié)構(gòu)用Java中的字符串類型表示串，可通過一對(duì)雙引號(hào)括起來的字符表示字符串。例如：Stringstr=“HelloWorld!”;確定串的長(zhǎng)度有兩種方法（1）使用String類中的length()方法獲得串的長(zhǎng)度，（2）引入一個(gè)變量length來記錄串的長(zhǎng)度。例如，串”HelloWorld!”在內(nèi)存中，用設(shè)置串的長(zhǎng)度的方法的表示如圖4-2所示。publicclassSeqString//定義字符串結(jié)構(gòu)類型{finalintMAXSIZE=100;charstr[];intlength;SeqString(chars[]){str=newchar[MAXSIZE];for(inti=0;i<s.length;i++)str[i]=s[i];length=s.length;}}4.2串的存儲(chǔ)表示4.2.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在順序串中，對(duì)于串的插入操作、串的連接及串的替換操作，如果串的長(zhǎng)度超過了MaxLen，串會(huì)被截?cái)嗵幚?。為了克服這些缺點(diǎn)，可以使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的串進(jìn)行處理。4.2串的存儲(chǔ)表示塊鏈串類型定義如下：classChunk//串的結(jié)點(diǎn)類型定義{finalintChunkSize=4;charch[];Chunknext;

}classLinkString//鏈串的類型定義{Chunkhead,tail;intlength;}其中，head表示頭指針，指向鏈串的第一個(gè)結(jié)點(diǎn)。tail表示尾指針，指向鏈串的最后一個(gè)結(jié)點(diǎn)。length表示鏈串中字符的個(gè)數(shù)。4.3串的模式匹配4.3.1樸素模式匹配算法——模式匹配算法Brute-Force子串的定位操作串通常稱為模式匹配，是各種串處理系統(tǒng)中最重要的操作之一。設(shè)有主串S和子串T，如果在主串S中找到一個(gè)與子串T相等的串，則返回串T的第一個(gè)字符在串S中的位置。其中，主串S又稱為目標(biāo)串，子串T又稱為模式串。4.3串的模式匹配例如，主串S="abaababaddecab"，子串T="abad"，S的長(zhǎng)度為n=13，T的長(zhǎng)度為m=4。用變量i表示主串S中當(dāng)前正在比較字符的下標(biāo)，變量j表示子串T中當(dāng)前正在比較字符的下標(biāo)。模式匹配的過程如圖4-8所示。4.3串的模式匹配publicintB_FIndex(SeqStringS,SeqStringT,intpos){//在主串S中的第pos個(gè)位置開始查找模式串T，如果找到返回子串在主串的位置；否則，返回-1

inti=pos-1;intj=0;

count=0;

while(i<S.length&&j<T.length){

if(S.str[i]==T.str[j])//若串S和T字符相等，則繼續(xù)比較下一個(gè)字符

{

i+=1;j+=1;}

else//若對(duì)應(yīng)字符不相等，則從串S的下一個(gè)字符、T的第0個(gè)字符開始比較

{i=i-j+1;j=0;}

count++;

}

if(j>=T.length)//如果在S中找到串T，則返回子串T在主串S的位置

returni-j+1;

else

return-1;

}4.3串的模式匹配例如設(shè)主串S="aaaaaaaaaaaaab"，模式串T="aaab"。其中，n=14，m=4。因?yàn)槟Ｊ酱那?個(gè)字符是"aaa"，主串的前13個(gè)字符也是"aaa"，每趟比較模式串的最后一個(gè)字符與主串中的字符不相等，所以均需要將主串的指針回退，從主串的下一個(gè)字符開始與模式串的第一個(gè)字符重新比較。在整個(gè)匹配過程中，主串的指針需要回退9次，匹配不成功的比較次數(shù)是10*4，成功匹配的比較次數(shù)是4次，因此總的比較次數(shù)是10*4+4=11*4即(n-m+1)*m。Brute-Force匹配算法在最好的情況下，即主串的前m個(gè)字符剛好與模式串相等，時(shí)間復(fù)雜度為O(m)。在最壞的情況下，Brute-Force匹配算法的時(shí)間復(fù)雜度是O(n*m)。4.3串的模式匹配4.3.2KMP算法KMP算法是由D.E.Knuth、J.H.Morris、V.R.Pratt共同提出的，因此稱為KMP算法（Knuth-Morris-Pratt算法）。KMP算法在Brute-Force算法的基礎(chǔ)上有較大改進(jìn)4.3串的模式匹配從圖4-9中可以看出，KMP算法的匹配次數(shù)由原來的6次減少為4次。在第一次匹配的過程中，當(dāng)i=3、j=3，主串中的字符與子串中的字符不相等，Brute-Force算法從i=1、j=0開始比較。將主串的指針回退的比較是沒有必要的，在第一次比較遇到主串與子串中的字符不相等時(shí)，有S0=T0="a"，S1=T1="b"，S2=T2="a"，S3≠T3。因?yàn)镾1=T1且T0≠T1，所以S1≠T0，S1與T0不必比較。又因?yàn)镾2=T2且T0=T2，有S2=T0，所以從S3與T1開始比較。4.3串的模式匹配假設(shè)主串S="s0s1…sn-1"，T="t0t1…tm-1"。在模式匹配過程中，如果出現(xiàn)字符不匹配的情況，即當(dāng)Si≠Tj(0≤i<n,0≤j<m)時(shí)，有："si-jsi-j+1…si-1"="t0t1…tj-1"假設(shè)子串即模式串存在可重疊的真子串，即："t0t1…tk-1"="tj-ktj-k+1…tj-1"4.3串的模式匹配如果令next[j]=k，則next[j]表示：當(dāng)子串中的第j個(gè)字符與主串中的對(duì)應(yīng)的字符不相等時(shí)，下一次子串需要與主串中該字符進(jìn)行比較的字符的位置。子串即模式串中的next函數(shù)，定義如下：4.3串的模式匹配KMP算法的模式匹配過程：如果模式串T中存在真子串"t0t1…tk-1"="tj-ktj-k+1…tj-1"，當(dāng)模式串T與主串S的si不相等，則按照next[j]=k將模式串向右滑動(dòng)，從主串中的si與模式串的tk開始比較。如果si=tk，則主串與子串的指針各自增1，繼續(xù)比較下一個(gè)字符。如果si≠tk，則按照next[next[j]]將模式串繼續(xù)向右滑動(dòng)，將主串中的si與模式串中的next[next[j]]字符進(jìn)行比較。4.3串的模式匹配publicintKMP_Index(SeqStringS,SeqStringT,intpos,intnext[])//KMP模式匹配算法。利用模式串T的next函數(shù)在主串S中的第pos個(gè)位置開始查找模式串T，如果找到返回模式串在主串的位置；否則，返回-1{

inti=pos-1;

intj=0;count=0;

while(i<S.length&&j<T.length)

{

if(j==-1||S.str[i]==T.str[j])//如果j=-1或當(dāng)前字符相等，則繼續(xù)比較后面的字符

{

i+=1;j+=1;}

else//如果當(dāng)前字符不相等，則將模式串向右移動(dòng)

{j=next[j];//next保存next函數(shù)值

}

count++;

}

if(j>=T.length)//匹配成功，返回子串在主串中的位置

returni-T.length+1;

else//否則返回-1

return-1;

}4.3串的模式匹配2.求next函數(shù)值設(shè)next[j]=k，表示在模式串T中存在以下關(guān)系："t0t1…tk-1"="tj-ktj-k+1…tj-1"其中，0<k<j，k為滿足等式的最大值，即不可能存在k'>k滿足以上等式。（1）如果tj=tk，則表示在模式串T中滿足關(guān)系"t0t1…tk"="tj-ktj-k+1…tj"，并且不可能存在k'>k滿足以上等式。因此有next[j+1]=k+1，即next[j+1]=next[j]+1。（2）如果tj≠tk，則表示在模式串T中滿足關(guān)系"t0t1…tk"≠"tj-ktj-k+1…tj"。把模式串T向右滑動(dòng)到k'=next[k]，如果有tj=tk'，則表示模式串中有"t0t1…tk'"="tj-k'tj-k'+1…tj"，因此有next[j+1]=k'+1，即next[j+1]=next[k]+1。4.3串的模式匹配模式串T="cbcaacbcbc"的next函數(shù)值如表4-1所示。在表4-1中，如果已經(jīng)求得前3個(gè)字符的next函數(shù)值，現(xiàn)在求next[3]，因?yàn)閚ext[2]=0且t2=t0，則next[3]=next[2]+1=1。接著求next[4]，因?yàn)閠2=t0，但"t2t3"≠"t0t1"，則需要將t3與下標(biāo)為next[1]=0的字符即t0比較，因?yàn)閠0≠t3，則next[4]=0。同理，在求得next[8]=3后，如何求next[9]？因?yàn)閚ext[8]=3，但t8≠t3，則比較t1與t8的值是否相等（next[3]=1），有t1=t8，則next[9]=k'+1=1+1=2。4.3串的模式匹配publicvoidGetNext(SeqStringT,intnext[])//求模式串T的next函數(shù)值并存入數(shù)組next{

intj=0;intk=-1;

next[0]=-1;

while(j<T.length-1)

{

if(k==-1||T.str[j]==T.str[k])//若k=-1或當(dāng)前字符相等，則繼續(xù)比較后面字符將函數(shù)值存入next

{

j+=1;

k+=1;

next[j]=k;

}

else//如果當(dāng)前字符不相等，則將模式串向右移動(dòng)繼續(xù)比較

k=next[k];

}

}4.3串的模式匹配3.改進(jìn)的求next函數(shù)算法例如，主串S="aaaacabacaaaba"與模式串T="aaaab"進(jìn)行匹配時(shí)，當(dāng)i=4、j=4時(shí)，s4≠t4，而因?yàn)閚ext[0]=-1、next[1]=0、next[2]=1、next[3]=2、next[4]=3，所以需要將主串的s4與子串中的t3、t2、t1、t0依次進(jìn)行比較。因模式串中的t3與t0、t1、t2都相等，沒有必要將這些字符與主串的s3進(jìn)行比較，僅需要直接將s4與t0進(jìn)行比較。4.3串的模式匹配【例4-2】編寫程序比較Brute-Force算法與KMP算法的效率。例如主串S="cabaadcabaababaabacabababab"，模式串T="abaabacababa"，統(tǒng)計(jì)Brute-Force算法與KMP算法在匹配過程中的比較次數(shù)，并輸出模式串的next函數(shù)值與nextval函數(shù)值。4.4數(shù)組的定義及抽象數(shù)據(jù)類型4.4.1數(shù)組的基本概念數(shù)組（Array）是由n個(gè)類型相同的數(shù)據(jù)元素組成的有限序列。一個(gè)m行n列的二維數(shù)組可以看成是一個(gè)線性表，其中數(shù)組中的每個(gè)元素也是一個(gè)線性表。例如，A=(p0,p1,…,pr)，其中r=n-1。表中的每個(gè)元素pj(0≤j≤r)又是一個(gè)列向量表示的線性表，pj=(a0,j,a1,j,…,am-1,j)，其中0≤j≤n-1。因此，這樣的m行n列的二維數(shù)組可以表示成由列向量組成的線性表，如圖4-13所示。4.4數(shù)組的定義及抽象數(shù)據(jù)類型4.4.3數(shù)組的順序存儲(chǔ)結(jié)構(gòu)計(jì)算機(jī)中的存儲(chǔ)器結(jié)構(gòu)是一維（線性）結(jié)構(gòu)，而數(shù)組是一個(gè)多維結(jié)構(gòu)，如果要將一個(gè)多維結(jié)構(gòu)存放在一個(gè)一維的存儲(chǔ)單元里，這就需要先將多維的數(shù)組轉(zhuǎn)換成一個(gè)一維線性序列，才能將其存放在存儲(chǔ)器中。對(duì)于二維數(shù)組A，若每個(gè)元素A的長(zhǎng)度為3個(gè)字符，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，假設(shè)數(shù)組中的元素按行優(yōu)先存放，則數(shù)組A[7][4]的起始地址是？4.4.3特殊矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的壓縮存儲(chǔ)假設(shè)用一維數(shù)組s存儲(chǔ)對(duì)稱矩陣A的上三角或下三角元素，則一維數(shù)組s的下標(biāo)k與n階對(duì)稱4.4數(shù)組的定義及抽象數(shù)據(jù)類型4.4.3特殊矩陣的壓縮存儲(chǔ)2.三角矩陣的壓縮存儲(chǔ)如果用一維數(shù)組來存儲(chǔ)三角矩陣，則需要存儲(chǔ)n*(n+1)/2+1個(gè)元素。4.4數(shù)組的定義及抽象數(shù)據(jù)類型4.4.3特殊矩陣的壓縮存儲(chǔ)3.對(duì)角矩陣的壓縮存儲(chǔ)當(dāng)i=0、j=1,2時(shí)，即第一行有2個(gè)非零元素；當(dāng)0<i<n-1、j=i-1,i,i+1時(shí)，即第2行到第n-1行之間有3個(gè)非零元素；當(dāng)i=n-1、j=n-2,n-1時(shí)，即最后一行有2個(gè)非零元素。除此以外，其他元素均為零。4.4數(shù)組的定義及抽象數(shù)據(jù)類型Loc(i,j)=Loc(0,0)+前i-1行的非零元素個(gè)數(shù)+第i行的非零元素個(gè)數(shù)，其中，前i-1行的非零元素個(gè)數(shù)為3*(i-1)-1，第i行的非零元素個(gè)數(shù)為j-i+1。4.4.3稀疏矩陣的壓縮存儲(chǔ)所謂稀疏矩陣，假設(shè)在m×n矩陣中有t個(gè)元素不為零，令δ=，δ為矩陣的稀疏因子，如果δ≤0.05，則稱矩陣為稀疏矩陣。4.4數(shù)組的定義及抽象數(shù)據(jù)類型圖4-24中的非零元素可以用三元組((0,3,6),(1,1,3),(2,2,7),(2,3,2),(3,0,9),(3,4,-2),(4,2,4),(4,3,3),(5,4,8))表示。將這些三元組按照行序?yàn)橹餍虼娣旁诮Y(jié)構(gòu)體數(shù)組中，如圖4-25所示，其中k表示數(shù)組的下標(biāo)。classTriple//三元組表示的數(shù)據(jù)元素類型定義{inti,j;inte;Triple(inti,intj,inte){this.i=i;//非零元素的行號(hào)

this.j=j;//非零元素的列號(hào)

this.e=e;}}publicclassTriSeqMat//三元組表示的矩陣類型定義{finalintMaxSize=50;Tripledata[];intm,n,len;//矩陣的行數(shù),列數(shù),非零元素的個(gè)數(shù)

TriSeqMat(){data=newTriple[MaxSize];this.m=this.n=this.len=0;}}4.4數(shù)組的定義及抽象數(shù)據(jù)類型轉(zhuǎn)置稀疏矩陣。轉(zhuǎn)置稀疏矩陣就是將矩陣中元素由原來的存放位置(i,j)變?yōu)?j,i)，也就是說將元素的行列互換。例如，圖7-13所示的6×7矩陣，經(jīng)過轉(zhuǎn)置后變?yōu)?×6矩陣，并且矩陣中的元素也要以主對(duì)角線為準(zhǔn)進(jìn)行交換。4.4數(shù)組的定義及抽象數(shù)據(jù)類型publicvoidTransposeMatrix(TriSeqMatM,TriSeqMatN)//稀疏矩陣的轉(zhuǎn)置{

N.m=M.n;N.n=M.m;N.len=M.len;

if(N.len>0){

intk=0;

for(intcol=0;col<M.n;col++)//按照列號(hào)掃描三元組順序表

{

for(inti=0;i<M.len;i++){

if(M.data[i].j==col)//是當(dāng)前列，則進(jìn)行轉(zhuǎn)置

{

N.data[k].i=M.data[i].j;

N.data[k].j=M.data[i].i;

N.data[k].e=M.data[i].e;

k+=1;}

}

}

}}4.4數(shù)組的定義及抽象數(shù)據(jù)類型4.4數(shù)組的定義及抽象數(shù)據(jù)類型（2）稀疏矩陣的快速轉(zhuǎn)置。按照M中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入N中恰當(dāng)位置。若能預(yù)先確定矩陣M中的每一列第一個(gè)非零元素在N中的應(yīng)有位置，那么對(duì)M中的三元組進(jìn)行轉(zhuǎn)置時(shí)，便可直接放到N中的恰當(dāng)位置。依次掃描三元組順序表M，可以得到每一列非零元素的個(gè)數(shù)，即num[col]。position[col]的值可以由num[col]得到，顯然，position[col]與num[col]存在如下關(guān)系。position[0]=0;position[col]=position[col-1]+num[col-1]，其中1≤col≤M.n-1。4.4數(shù)組的定義及抽象數(shù)據(jù)類型4.稀疏矩陣應(yīng)用舉例──三元組表示的稀疏矩陣相加【例4-3】有兩個(gè)稀疏矩陣A和B，相加得到C，如圖4-29所示。請(qǐng)利用三元組順序表實(shí)現(xiàn)兩個(gè)稀疏矩陣的相加，并輸出結(jié)果。（1）A中的元素aij≠0且B中的元素bij≠0，但是結(jié)果可能為零，如果結(jié)果為零，則不保存元素值；如果結(jié)果不為零，則將結(jié)果保存在C中。（2）A中的第(i,j)個(gè)位置存在非零元素aij，而B中不存在非零元素，則只需要將該值賦值給C。（3）B中的第(i,j)個(gè)位置存在非零元素bij，而A中不存在非零元素，則只需要將bij賦值給C。4.4數(shù)組的定義及抽象數(shù)據(jù)類型publicintAddMatrix(TriSeqMatM,TriSeqMatN,TriSeqMatQ){intm=0,n=0;intk=-1;//如果兩個(gè)矩陣的行數(shù)與列數(shù)不相等，則不能夠進(jìn)行相加運(yùn)算

if(M.m!=N.m||M.n!=N.n)return0;Q.m=M.m;Q.n=M.n;while(m<M.len&&n<N.len)

{switch(CompareElement(M.data[m].i,N.data[n].i))//比較兩個(gè)矩陣對(duì)應(yīng)元素的行號(hào)

{case-1:Q.data[++k]=M.data[m++];break;//如果矩陣M的行號(hào)小于N的行號(hào)case0://如果矩陣M和N的行號(hào)相等，則比較列號(hào)

{switch(CompareElement(M.data[m].j,N.data[n].j))

{case-1://如果M的列號(hào)小于N的列號(hào)，則將矩陣M的元素賦值給Q

Q.data[++k]=M.data[m++];break;4.4數(shù)組的定義及抽象數(shù)據(jù)類型

case0://如果M和N的行號(hào)、列號(hào)均相等，則將兩元素相加，存入QQ.data[++k]=M.data[m++];Q.data[k].e+=N.data[n++].e;if(Q.data[k].e==0)k--;break;//如果兩個(gè)元素的和為0，則不保存case1://如果M的列號(hào)大于N的列號(hào)，則將矩陣N的元素賦值給QQ.data[++k]=N.data[n++];break;}

break;}case1:Q.data[++k]=N.data[n++];break;}}

while(m<M.len){Q.data[++k]=M.data[m++];}//如果矩陣M的元素還沒處理完畢while(n<N.len){Q.data[++k]=N.data[n++];}//如果矩陣N的元素還沒處理完畢Q.len=k+1;//修改非零元素的個(gè)數(shù)if(k>MaxSize)return0;return1;}4.5廣義表4.5.1什么是廣義表廣義表，也稱為列表（lists），是由n個(gè)類型相同的數(shù)據(jù)元素(a1,a2,a3,…,an)組成的有限序列。其中，廣義表中的元素ai可以是單個(gè)元素，也可以是一個(gè)廣義表。通常，廣義表記做GL=(a1,a2,a3,…,an)。其中，GL是廣義表的名字，n是廣義表的長(zhǎng)度。如果廣義表中的ai是單個(gè)元素，則稱ai是原子。如果廣義表中的ai是一個(gè)廣義表，則稱ai是廣義表的子表。習(xí)慣上用大寫字母表示廣義表的名字，用小寫字母表示原子。對(duì)于非空廣義表GL，a1稱為廣義表GL的表頭（head），其余元素組成的表(a2,a3,…,an)稱為廣義表GL的表尾（tail）。廣義表是一個(gè)遞歸的定義，因?yàn)樵诿枋鰪V義表時(shí)又用到了廣義表的概念。4.5廣義表（1）A=()，廣義表A是長(zhǎng)度為0的空表。（2）B=(a)，B是一個(gè)長(zhǎng)度為1且元素為原子的廣義表（其實(shí)就是前面討論過的一般的線性表）。（3）C=(a,(b,c))，C是長(zhǎng)度為2的廣義表。其中，第1個(gè)元素是原子a，第2個(gè)元素是一個(gè)子表(b,c)。（4）D=(A,B,C)，D是一個(gè)長(zhǎng)度為3的廣義表，這3個(gè)元素都是子表，第1個(gè)元素是一個(gè)空表A。（5）E=(a,E)，E是一個(gè)長(zhǎng)度為2的遞歸廣義表，相當(dāng)于E=(a,(a,(a,(a,(a,…)))。4.5廣義表任何一個(gè)非空廣義表的表頭可以是一個(gè)原子，也可以是一個(gè)廣義表，而表尾一定是一個(gè)廣義表。例如head(B)=a，head（B）=()，head(C)=a,tail(C)=((b,c))，head(D)=A，tail(D)=(B,C)其中，head(B)表示取廣義表B的表頭元素，tail(B)表示取廣義表B的表尾元素。廣義表中的基本操作有求表頭head和表尾tail，例如，若廣義表A=(a,(b,c))，則head(A)=a,tail(A)=((b,c))。已知廣義表LS=((a,b,c),(d,e,f))，請(qǐng)運(yùn)用head和tail函數(shù)取出LS中的原子e，寫出運(yùn)算表達(dá)式。4.5廣義表4.5.3廣義表的頭尾鏈表表示廣義表的鏈表結(jié)點(diǎn)也分為原子結(jié)點(diǎn)和子表結(jié)點(diǎn)兩種，其中，子表結(jié)點(diǎn)包含標(biāo)志域、指向表頭的指針域和指向表尾的指針域3個(gè)域。原子結(jié)點(diǎn)包含標(biāo)志域和值域兩個(gè)域。表結(jié)點(diǎn)和原子結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如圖4-31所示。其中，tag=1表示是子表，hp和tp分別指向表頭結(jié)點(diǎn)和表尾結(jié)點(diǎn)，tag=0表示原子，atom用于存儲(chǔ)原子的值。4.5廣義表4.5.4廣義表的擴(kuò)展線性鏈表表示采用擴(kuò)展線性鏈表表示的廣義