第四章數(shù)組、串與廣義表本章主要內(nèi)容多維數(shù)組的概念與存儲(chǔ)特殊矩陣稀疏矩陣字符串2多維數(shù)組的概念與存儲(chǔ)多維數(shù)組是一維數(shù)組的擴(kuò)展3二維數(shù)組三維數(shù)組多維數(shù)組的概念與存儲(chǔ)多維數(shù)組存儲(chǔ)在連續(xù)的空間中存儲(chǔ)地址計(jì)算方法（假設(shè)數(shù)組首地址為a，元素大小為l）一維數(shù)組：a[m1]二維數(shù)組：a[m1][m2]三維數(shù)組：a[m1][m2][m3]n維數(shù)組：a[m1][m2]…[mn]4Loc(i)=a+i*lLoc(i,j)=a+(i*m2+j)*lLoc(i,j,k)=a+(i*m2*m3+j*m3+k)*l特殊矩陣二維數(shù)組也稱為矩陣特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。對(duì)稱矩陣三對(duì)角矩陣?yán)锰厥饩仃嚨男再|(zhì)，節(jié)省存儲(chǔ)空間5對(duì)稱矩陣三對(duì)角矩陣特殊矩陣對(duì)稱矩陣的壓縮存儲(chǔ)設(shè)有一個(gè)n

n的矩陣A。如果在在矩陣中，aij=aji，則此矩陣是對(duì)稱矩陣。只保存對(duì)稱矩陣的對(duì)角線和對(duì)角線以上(或以下)的元素，則稱此為對(duì)稱矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ)方式：用一維數(shù)組存儲(chǔ)6特殊矩陣對(duì)稱矩陣的壓縮存儲(chǔ)下三角陣存儲(chǔ)：用一維數(shù)組B存儲(chǔ)對(duì)稱矩陣A中對(duì)角線及對(duì)角線以下的元素矩陣A中元素a[i][j]對(duì)應(yīng)一維數(shù)組B中的下標(biāo)為7(i+1)*i/2+j,i≥jLoc(i,j)=(j+1)*j/2+i,i<ja00a10a11a20a21a22a30a31a32……

an-1n-1

012345678n(n+1)/2-1B特殊矩陣對(duì)稱矩陣的壓縮存儲(chǔ)上三角陣存儲(chǔ)：用一維數(shù)組B存儲(chǔ)對(duì)稱矩陣A中對(duì)角線及對(duì)角線以上的元素矩陣A中元素a[i][j]對(duì)應(yīng)一維數(shù)組B中的下標(biāo)為8(2n-i+1)*i/2+j-i,i≤j(2n-j-1)*j/2+i,i>jLoc(i,j)=a00a01a02…

a0n-1a11a12…

a1n-1a22…

an-1n-1

012n-1nn+12n-22n-1n(n+1)/2-1B稀疏矩陣設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。稀疏因子：

δ=s/(m×n)一般δ

≤0.05可稱為稀疏9稀疏矩陣表示稀疏矩陣用三元組(i,j,aij)表示稀疏矩陣一個(gè)元素aij10三元組表示稀疏矩陣表示稀疏矩陣三元組表示的稀疏矩陣轉(zhuǎn)置的直觀方法按列從小到大排序行列交換11稀疏矩陣三元組表示的稀疏矩陣轉(zhuǎn)置的掃描方法假設(shè)A有Cols列，則掃描Cols趟第k趟掃描在表中找列號(hào)為k的三元組，取出，交換行列號(hào)12掃描列號(hào)為0的三元組掃描列號(hào)為1的三元組掃描列號(hào)為2的三元組掃描列號(hào)為3的三元組掃描列號(hào)為4的三元組掃描列號(hào)為5的三元組掃描列號(hào)為6的三元組65-5253-17441935-832-631-11202149013稀疏矩陣三元組表示的稀疏矩陣轉(zhuǎn)置的快速方法統(tǒng)計(jì)各列非零數(shù)rowSize(掃描三元組表)計(jì)算各列在轉(zhuǎn)置三元組中的索引位置rowStart掃描三元組表，放入相應(yīng)索引位置，相應(yīng)索引加1rowSize1113111rowStart012367865-5253-17441935-832-631-11202149013453216789字符串字符串n(n≥0)個(gè)字符的一個(gè)有限序列，簡稱為串記為S=“a0

a1

a2…an-1”n是串的長度，n等于0的串叫空串子串串中連續(xù)若干個(gè)字符組成的串S=“maintenance”，P=“ten”是S的子串，P在S中的位置為4（從第0個(gè)字符開始）14字符串字符串的一些基本操作復(fù)制strcpy連接strcat比較strcmp長度strlen15typedefstruct{charch[maxSize];intlength;}SeqString;字符串字符串的窮舉模式匹配算法匹配失敗時(shí)，目標(biāo)串T回溯，模式串P從頭開始16PTp2p3…pm-3pm-2pm-1p1p0t2t3…tm-3tm-2tm-1…t1t0tn-1p2p3…pm-3pm-2pm-1p1p0p2p3…pm-3pm-2pm-1p1p0PP第1趟第2趟第3趟…時(shí)間復(fù)雜度O(m*n)…字符串字符串的窮舉模式匹配算法匹配失敗時(shí)，目標(biāo)串T回溯，模式串P從頭開始17PT≠abaababbaPT≠abaababbaPT≠abaababbaPTabaababba第1趟第2趟第3趟第4趟字符串字符串的改進(jìn)模式匹配算法18PT≠Pcdabcdbaecdabcdbae例子：P中重復(fù)出現(xiàn)abcd，但是e和x不匹配時(shí)，可直接向右滑動(dòng)4個(gè)字符開始匹配，可少匹配4趟cdabcdba…x…字符串字符串的改進(jìn)模式匹配算法19PTp2p3…pj-3pj-2pj-1pjp1p0ts+2ts+3…ts+j-3ts+j-2ts+j-1ts+jts+1ts……≠========p2p3…pj-3pj-2p1p0p2p3…pj-3p1p0設(shè)T[s,s+j-1]=P[0,j-1]，但T[s,s+j]≠P[0,j]PP若P[0,j-2]≠P[1,j-1]，可少匹配1趟若又P[0,j-3]≠P[2,j-1]，可少匹配2趟p2…pj-4p1p0P若又P[0,j-4]≠P[3,j-1]，可少匹配3趟……類推直到前綴P[0,k+1]≠

后綴P[j-k-2,j-1]但是前綴P[0,k]=后綴P[j-k-1,j-1]時(shí)，可少匹配j-k-1趟，相當(dāng)于P直接向右滑動(dòng)j-k-1個(gè)字符字符串字符串的改進(jìn)模式匹配算法對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過多少個(gè)字符20-1，當(dāng)

j=

0k+1，當(dāng)

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數(shù)next(j)=0，其他情況Pcdabcdbae下標(biāo)j234567108next(j)0001230-14next(j)直觀含義：[0,j-1]中前綴和后綴相等的最大長度next(j)直觀作用：可滑過j-next(j)位不用匹配字符串字符串的改進(jìn)模式匹配算法對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過多少個(gè)字符21-1，當(dāng)

j=

0k+1，當(dāng)

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數(shù)next(j)=0，其他情況PT≠Pcdabcdbaecdabcdbaecb……next(j)=-1表示匹配失敗時(shí)，T的指針加1，P的指針指向p[0]next(j)=k+1表示匹配失敗時(shí)，P的指針指向p[k+1]，next(j)=0表示匹配失敗時(shí)，P的指針指向p[0]此例中模式串P的next[0]=-1，T指針加1，P指向p[0]，即T中c與P中p[0]=a進(jìn)行比較字符串字符串的改進(jìn)模式匹配算法對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過多少個(gè)字符22-1，當(dāng)

j=

0k+1，當(dāng)

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數(shù)next(j)=0，其他情況PT≠Pcdabcdbaecdabcdbaecdabcdba…x…next(j)=-1表示匹配失敗時(shí)，T的指針加1，P的指針指向p[0]next(j)=k+1表示匹配失敗時(shí)，P的指針指向p[k+1]，next(j)=0表示匹配失敗時(shí)，P的指針指向p[0]此例中模式串P的next[8]=4，T中x直接與P中p[4]=a比較字符串字符串的改進(jìn)模式匹配算法對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過多少個(gè)字符23-1，當(dāng)

j=

0k+1，當(dāng)

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數(shù)next(j)=0，其他情況PT≠Pcdabcdbaecdabcdbaecxba……next(j)=-1表示匹配失敗時(shí)，T的指針加1，P的指針指向p[0]next(j)=k+1表示匹配失敗時(shí)，P的指針指向p[k+1]，next(j)=0表示匹配失敗時(shí)，P的指針指向p[0]此例中模式串P的next[3]=0，T中x直接與P中p[0]=a比較字符串字符串的改進(jìn)模式匹配算法對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過多少個(gè)字符24-1，當(dāng)

j=

0k+1，當(dāng)

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數(shù)next(j)=0，其他情況可按定義直接計(jì)算next，下面介紹一種快速的計(jì)算next的方法假設(shè)已知next(j)=x，現(xiàn)在計(jì)算next(j+1)若px=pj，則next(j+1)=x+1=next(j)+1否則，設(shè)next(x)=h，(此時(shí)有p[0,h-1]=p[x-h,x-1]=p[j-h,j-1])

若ph=pj，則next(j+1)=h+1

否則，令next(h)=t,(此時(shí)有p[0,t-1]=p[h-t,h-1]=p[j-t,j-1])

繼續(xù)判斷是否pt=pj，直到找到或者到next(0)=-1……j=0;k=-1;next[0]=-1;while(j<pLength){if(k==-1||ch[j]==ch[k]){j++;k++;next[j]=k;}elsek=next[k];}字符串字符串的改進(jìn)模式匹配算法對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過多少個(gè)字符25-1，當(dāng)

j=

0k+1，當(dāng)

0≤k<j-1,且使p0p1…pk=pj-k-1pj-k…pj-1的最大數(shù)next(j)=0，其他情況可按定義直接計(jì)算next，下面介紹一種快速的計(jì)算next的方法j=0;k=-1;next[0]=-1;while(j<pLength){if(k==-1||ch[j]==ch[k]){j++;k++;next[j]=k;}elsek