第四章數(shù)組、串與廣義表

1、第第四四章章 數(shù)組、串與廣義表數(shù)組、串與廣義表東南大學(xué)計(jì)算機(jī)學(xué)院東南大學(xué)計(jì)算機(jī)學(xué)院 方效林方效林本課件借鑒了清華大學(xué)殷人昆老師和哈爾濱工業(yè)大學(xué)張巖老師的課件本章主要內(nèi)容本章主要內(nèi)容n多維數(shù)組的概念與存儲(chǔ)多維數(shù)組的概念與存儲(chǔ)n特殊矩陣特殊矩陣n稀疏矩陣稀疏矩陣n字符串字符串2多維數(shù)組的概念與存儲(chǔ)多維數(shù)組的概念與存儲(chǔ)n多維數(shù)組是一維數(shù)組的擴(kuò)展多維數(shù)組是一維數(shù)組的擴(kuò)展3二維數(shù)組二維數(shù)組三維數(shù)組三維數(shù)組多維數(shù)組的概念與存儲(chǔ)多維數(shù)組的概念與存儲(chǔ)n多維數(shù)組存儲(chǔ)在連續(xù)的空間中多維數(shù)組存儲(chǔ)在連續(xù)的空間中n存儲(chǔ)地址計(jì)算方法（假設(shè)數(shù)組首地址為存儲(chǔ)地址計(jì)算方法（假設(shè)數(shù)組首地址為a ，元，元素大小為素大小為 l）r一

2、維數(shù)組：一維數(shù)組：am1r二維數(shù)組：二維數(shù)組：am1m2r三維數(shù)組：三維數(shù)組：am1m2 m3rn維數(shù)組：維數(shù)組： am1m2 mn4Loc(i)= a + i*lLoc(i, j)= a + ( i*m2 + j )*lLoc(i, j, k)= a + ( i*m2*m3 + j*m3 + k )*l特殊矩陣特殊矩陣n二維數(shù)組也稱為矩陣二維數(shù)組也稱為矩陣n特殊矩陣是指非零元素或零元素的分布有一定特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。規(guī)律的矩陣。r對(duì)稱矩陣對(duì)稱矩陣r三對(duì)角矩陣三對(duì)角矩陣n利用特殊矩陣的性質(zhì)，節(jié)省存儲(chǔ)空間利用特殊矩陣的性質(zhì)，節(jié)省存儲(chǔ)空間511nn12n11n10n

3、12n22212011n12111010n020100aaaaaaaaaaaaaaaaA11nn21nn12nn22nn32nn2322211211100100aa0000aaa00000aaa0000aaa0000aaA對(duì)稱矩陣對(duì)稱矩陣三對(duì)角矩陣三對(duì)角矩陣特殊矩陣特殊矩陣n對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的壓縮存儲(chǔ)r設(shè)有一個(gè)設(shè)有一個(gè) n n 的矩陣的矩陣 A。如果在在矩陣中，。如果在在矩陣中，aij = aji，則此矩陣是對(duì)稱矩陣。，則此矩陣是對(duì)稱矩陣。r只保存對(duì)稱矩陣的對(duì)角線和對(duì)角線以上只保存對(duì)稱矩陣的對(duì)角線和對(duì)角線以上 (或以下或以下) 的元素，則稱此為對(duì)稱矩陣的壓縮存儲(chǔ)的元素，則稱此為對(duì)稱矩

4、陣的壓縮存儲(chǔ)r壓縮存儲(chǔ)方式：用一維數(shù)組存儲(chǔ)壓縮存儲(chǔ)方式：用一維數(shù)組存儲(chǔ)611nn12n11n10n12n22212011n12111010n020100aaaaaaaaaaaaaaaaA特殊矩陣特殊矩陣n對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的壓縮存儲(chǔ)r下三角陣存儲(chǔ)：下三角陣存儲(chǔ)： 用一維數(shù)組用一維數(shù)組B存儲(chǔ)對(duì)稱矩陣存儲(chǔ)對(duì)稱矩陣A中中對(duì)對(duì)角線及對(duì)角線角線及對(duì)角線以下以下的元素的元素矩陣矩陣A中元素中元素aij對(duì)應(yīng)一維數(shù)組對(duì)應(yīng)一維數(shù)組B中的下標(biāo)為中的下標(biāo)為711nn12n11n10n222120111000aaaaaaaaaaA(i+1)*i/2 + j, i jLoc(i, j) =(j+1)*j/2 +

5、 i, i jLoc(i, j) =a00 a01 a02 a0n-1 a11 a12 a1n-1 a22 an-1n-1 0 1 2 n-1 n n+1 2n-2 2n-1 n(n+1)/2-1B稀疏矩陣稀疏矩陣n設(shè)矩陣設(shè)矩陣 A 中有中有 s 個(gè)非零元素，若個(gè)非零元素，若 s 遠(yuǎn)遠(yuǎn)小于遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即矩陣元素的總數(shù)（即s mn），則稱），則稱 A 為為稀疏矩陣。稀疏矩陣。r稀疏因子：稀疏因子： = s/(mn)r一般一般 0.05可稱為稀疏可稱為稀疏9稀疏矩陣表示稀疏矩陣表示 5200800000190090017000000006000000110030000200A76稀疏矩

6、陣稀疏矩陣n用三元組用三元組(i, j, aij)表示稀疏矩陣一個(gè)元素表示稀疏矩陣一個(gè)元素aij10三元組表示三元組表示稀疏矩陣表示稀疏矩陣表示 5200800000190090017000000006000000110030000200A76稀疏矩陣稀疏矩陣n三元組表示的稀疏矩陣轉(zhuǎn)置的直觀方法三元組表示的稀疏矩陣轉(zhuǎn)置的直觀方法r按列從小到大排序按列從小到大排序r行列交換行列交換11稀疏矩陣稀疏矩陣n三元組表示的稀疏矩陣轉(zhuǎn)置的掃描方法三元組表示的稀疏矩陣轉(zhuǎn)置的掃描方法r假設(shè)假設(shè)A有有Cols列，則掃描列，則掃描Cols趟趟r第第k趟掃描在表中找列號(hào)為趟掃描在表中找列號(hào)為k的三元組，取出，交的三

7、元組，取出，交換行列號(hào)換行列號(hào)12掃描列號(hào)為掃描列號(hào)為0的三元組的三元組掃描列號(hào)為掃描列號(hào)為1的三元組的三元組掃描列號(hào)為掃描列號(hào)為2的三元組的三元組掃描列號(hào)為掃描列號(hào)為3的三元組的三元組掃描列號(hào)為掃描列號(hào)為4的三元組的三元組掃描列號(hào)為掃描列號(hào)為5的三元組的三元組掃描列號(hào)為掃描列號(hào)為6的三元組的三元組6 5 -525 3 -174 4 193 5 -83 2 -63 1 -112 0 21 4 90 1 3稀疏矩陣稀疏矩陣n三元組表示的稀疏矩陣轉(zhuǎn)置的快速方法三元組表示的稀疏矩陣轉(zhuǎn)置的快速方法r統(tǒng)計(jì)各列非零數(shù)統(tǒng)計(jì)各列非零數(shù)rowSize(掃描三元組表掃描三元組表)r計(jì)算各列在轉(zhuǎn)置三元組中的索引位置

8、計(jì)算各列在轉(zhuǎn)置三元組中的索引位置rowStartr掃描三元組表，放入相應(yīng)索引位置，相應(yīng)索引加掃描三元組表，放入相應(yīng)索引位置，相應(yīng)索引加1 5200800000190090017000000006000000110030000200A76rowSize111311 1rowStart012367 86 5 -525 3 -174 4 193 5 -83 2 -63 1 -112 0 21 4 90 1 345321678 9字符串字符串n字符串字符串rn(n0)個(gè)字符的一個(gè)有限序列，簡(jiǎn)稱為串個(gè)字符的一個(gè)有限序列，簡(jiǎn)稱為串r記為記為S = “a0 a1 a2 an-1”rn是串的長(zhǎng)度，是串的長(zhǎng)度，

9、n等于等于0的串叫空串的串叫空串n子串子串r串中連續(xù)若干個(gè)字符組成的串串中連續(xù)若干個(gè)字符組成的串rS=“maintenance”，P=“ten”是是S的子串，的子串，P在在S中的位置為中的位置為4（從第（從第0個(gè)字符開始）個(gè)字符開始）14字符串字符串n字符串的一些基本操作字符串的一些基本操作r復(fù)制復(fù)制strcpyr連接連接strcatr比較比較strcmpr長(zhǎng)度長(zhǎng)度strlen15typedef struct char chmaxSize; int length; SeqString;字符串字符串n字符串的窮舉模式匹配算法字符串的窮舉模式匹配算法r匹配失敗時(shí)，目標(biāo)串匹配失敗時(shí)，目標(biāo)串T回溯，模

10、式串回溯，模式串P從頭開始從頭開始16PTp2p3pm-3pm-2pm-1p1p0t2t3tm-3tm-2tm-1t1t0tn-1p2p3pm-3pm-2pm-1p1p0p2p3pm-3pm-2pm-1p1p0PP第第1趟趟第第2趟趟第第3趟趟時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(m*n)字符串字符串n字符串的窮舉模式匹配算法字符串的窮舉模式匹配算法r匹配失敗時(shí)，目標(biāo)串匹配失敗時(shí)，目標(biāo)串T回溯，模式串回溯，模式串P從頭開始從頭開始17PTabaababbaPTabaababbaPTabaababbaPTabaababba第第1趟趟第第2趟趟第第3趟趟第第4趟趟字符串字符串n字符串的改進(jìn)模式匹配算法字符串的改

11、進(jìn)模式匹配算法18PTPcdabcdbaecdabcdbae例子：例子：P中重復(fù)出現(xiàn)中重復(fù)出現(xiàn)abcd，但是，但是e和和x不匹配時(shí)，不匹配時(shí)，可直接向右滑動(dòng)可直接向右滑動(dòng)4個(gè)字符開始匹配，可少匹配個(gè)字符開始匹配，可少匹配4趟趟cdabcdbax字符串字符串n字符串的改進(jìn)模式匹配算法字符串的改進(jìn)模式匹配算法19PTp2p3pj-3pj-2pj-1pjp1p0ts+2ts+3ts+j-3ts+j-2ts+j-1ts+jts+1ts=p2p3pj-3pj-2p1p0p2p3pj-3p1p0設(shè)設(shè)Ts, s+j-1 = P0, j-1，但但Ts, s+j P0, jPP若若P0, j-2 P1, j-1

12、，可少匹配，可少匹配1趟趟若又若又P0, j-3 P2, j-1，可少匹配，可少匹配2趟趟p2pj-4p1p0P若又若又P0, j-4 P3, j-1，可少匹配，可少匹配3趟趟類推直到前綴類推直到前綴P0, k+1 后綴后綴Pj-k-2, j-1但是前綴但是前綴P0, k =后綴后綴 Pj-k-1, j-1 時(shí)，時(shí)，可少匹配可少匹配 j-k-1 趟，趟，相當(dāng)于相當(dāng)于P直接向右滑動(dòng)直接向右滑動(dòng) j-k-1 個(gè)字符個(gè)字符字符串字符串n字符串的改進(jìn)模式匹配算法字符串的改進(jìn)模式匹配算法r對(duì)模式串對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符20-1，當(dāng)，當(dāng) j = 0k

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

14、 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大數(shù)的最大數(shù)next( j ) =0，其他情況，其他情況PTPcdabcdbaecdabcdbaecbnext(j)=-1表示匹配失敗時(shí)，表示匹配失敗時(shí)，T的指針加的指針加1，P的指針指向的指針指向p0next(j)=k+1表示匹配失敗時(shí)，表示匹配失敗時(shí)，P的指針指向的指針指向pk+1，next(j)=0表示匹配失敗時(shí)，表示匹配失敗時(shí)，P的指針指向的指針指向p0此例中模式串此例中模式串P的的next0=-1，T指針加指針加1，P指向指向p0，即，即T中中c與與P中中p0=a進(jìn)行比較進(jìn)行比較字符串字符串n字符串的改進(jìn)模式匹

15、配算法字符串的改進(jìn)模式匹配算法r對(duì)模式串對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符22-1，當(dāng)，當(dāng) j = 0k+1，當(dāng)，當(dāng) 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大數(shù)的最大數(shù)next( j ) =0，其他情況，其他情況PTPcdabcdbaecdabcdbaecdabcdbaxnext(j)=-1表示匹配失敗時(shí)，表示匹配失敗時(shí)，T的指針加的指針加1，P的指針指向的指針指向p0next(j)=k+1表示匹配失敗時(shí)，表示匹配失敗時(shí)，P的指針指向的指針指向pk+1，next(j)=0表示匹配失敗時(shí)，表示匹配失敗時(shí)，P的指針指向的

16、指針指向p0此例中模式串此例中模式串P的的next8=4，T中中x直接與直接與P中中p4=a比較比較字符串字符串n字符串的改進(jìn)模式匹配算法字符串的改進(jìn)模式匹配算法r對(duì)模式串對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符23-1，當(dāng)，當(dāng) j = 0k+1，當(dāng)，當(dāng) 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大數(shù)的最大數(shù)next( j ) =0，其他情況，其他情況PTPcdabcdbaecdabcdbaecxbanext(j)=-1表示匹配失敗時(shí)，表示匹配失敗時(shí)，T的指針加的指針加1，P的指針指向的指針指向p0next(j)=k+1表示匹

17、配失敗時(shí)，表示匹配失敗時(shí)，P的指針指向的指針指向pk+1，next(j)=0表示匹配失敗時(shí)，表示匹配失敗時(shí)，P的指針指向的指針指向p0此例中模式串此例中模式串P的的next3=0，T中中x直接與直接與P中中p0=a比較比較字符串字符串n字符串的改進(jìn)模式匹配算法字符串的改進(jìn)模式匹配算法r對(duì)模式串對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符24-1，當(dāng)，當(dāng) j = 0k+1，當(dāng)，當(dāng) 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大數(shù)的最大數(shù)next( j ) =0，其他情況，其他情況可按定義直接計(jì)算可按定義直接計(jì)算next，下面介紹一種快

18、速的計(jì)算，下面介紹一種快速的計(jì)算next的方法的方法假設(shè)已知假設(shè)已知next(j)=x，現(xiàn)在計(jì)算，現(xiàn)在計(jì)算next(j+1)若若px=pj，則，則next(j+1) = x+1 = next(j)+1否則，設(shè)否則，設(shè)next(x)=h，(此時(shí)有此時(shí)有p0,h-1=px-h,x-1=pj-h,j-1) 若若ph=pj，則，則next(j+1) = h+1 否則，令否則，令next(h)=t, (此時(shí)有此時(shí)有p0,t-1=ph-t,h-1=pj-t,j-1) 繼續(xù)判斷是否繼續(xù)判斷是否pt=pj，直到找到或者到，直到找到或者到next(0) = -1 j=0;k=-1;next0=-1;while(jpLength) if(k=-1 | chj=chk) j+;k+;nextj=k; else k = nextk;字符串字符串n字符串的改進(jìn)模式匹配算法字符串的改進(jìn)模式匹配算法r對(duì)模式串對(duì)模式串P進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符進(jìn)行預(yù)處理，計(jì)算可以滑過(guò)多少個(gè)字符25-1，當(dāng)，當(dāng) j = 0k+1，當(dāng)，當(dāng) 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大數(shù)的最大數(shù)next( j ) =0，其他情況，其他情況可按定義直接計(jì)算可按定義直接計(jì)算next，下面介紹一種快速的計(jì)算，下面介紹一種快速的計(jì)算next的方法的方法j=0;k=-1;next0=