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

1、第第四四章章 數(shù)組、串與廣義表數(shù)組、串與廣義表東南大學計算機學院東南大學計算機學院 方效林方效林本課件借鑒了清華大學殷人昆老師和哈爾濱工業(yè)大學張巖老師的課件本章主要內(nèi)容本章主要內(nèi)容n多維數(shù)組的概念與存儲多維數(shù)組的概念與存儲n特殊矩陣特殊矩陣n稀疏矩陣稀疏矩陣n字符串字符串2多維數(shù)組的概念與存儲多維數(shù)組的概念與存儲n多維數(shù)組是一維數(shù)組的擴展多維數(shù)組是一維數(shù)組的擴展3二維數(shù)組二維數(shù)組三維數(shù)組三維數(shù)組多維數(shù)組的概念與存儲多維數(shù)組的概念與存儲n多維數(shù)組存儲在連續(xù)的空間中多維數(shù)組存儲在連續(xù)的空間中n存儲地址計算方法（假設(shè)數(shù)組首地址為存儲地址計算方法（假設(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對稱矩陣對稱矩陣r三對角矩陣三對角矩陣n利用特殊矩陣的性質(zhì)，節(jié)省存儲空間利用特殊矩陣的性質(zhì)，節(jié)省存儲空間511nn12n11n10n

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

4、陣的壓縮存儲r壓縮存儲方式：用一維數(shù)組存儲壓縮存儲方式：用一維數(shù)組存儲611nn12n11n10n12n22212011n12111010n020100aaaaaaaaaaaaaaaaA特殊矩陣特殊矩陣n對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲r下三角陣存儲：下三角陣存儲： 用一維數(shù)組用一維數(shù)組B存儲對稱矩陣存儲對稱矩陣A中中對對角線及對角線角線及對角線以下以下的元素的元素矩陣矩陣A中元素中元素aij對應(yīng)一維數(shù)組對應(yīng)一維數(shù)組B中的下標為中的下標為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 個非零元素，若個非零元素，若 s 遠遠小于遠遠小于矩陣元素的總數(shù)（即矩陣元素的總數(shù)（即s mn），則稱），則稱 A 為為稀疏矩陣。稀疏矩陣。r稀疏因子：稀疏因子： = s/(mn)r一般一般 0.05可稱為稀疏可稱為稀疏9稀疏矩陣表示稀疏矩陣表示 5200800000190090017000000006000000110030000200A76稀疏矩

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

7、元組，取出，交換行列號換行列號12掃描列號為掃描列號為0的三元組的三元組掃描列號為掃描列號為1的三元組的三元組掃描列號為掃描列號為2的三元組的三元組掃描列號為掃描列號為3的三元組的三元組掃描列號為掃描列號為4的三元組的三元組掃描列號為掃描列號為5的三元組的三元組掃描列號為掃描列號為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)計各列非零數(shù)統(tǒng)計各列非零數(shù)rowSize(掃描三元組表掃描三元組表)r計算各列在轉(zhuǎn)置三元組中的索引位置

8、計算各列在轉(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)個字符的一個有限序列，簡稱為串個字符的一個有限序列，簡稱為串r記為記為S = “a0 a1 a2 an-1”rn是串的長度，是串的長度，

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

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

11、進模式匹配算法18PTPcdabcdbaecdabcdbae例子：例子：P中重復(fù)出現(xiàn)中重復(fù)出現(xiàn)abcd，但是，但是e和和x不匹配時，不匹配時，可直接向右滑動可直接向右滑動4個字符開始匹配，可少匹配個字符開始匹配，可少匹配4趟趟cdabcdbax字符串字符串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 時，時，可少匹配可少匹配 j-k-1 趟，趟，相當于相當于P直接向右滑動直接向右滑動 j-k-1 個字符個字符字符串字符串n字符串的改進模式匹配算法字符串的改進模式匹配算法r對模式串對模式串P進行預(yù)處理，計算可以滑過多少個字符進行預(yù)處理，計算可以滑過多少個字符20-1，當，當 j = 0k

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

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

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

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

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

18、速的計算，下面介紹一種快速的計算next的方法的方法假設(shè)已知假設(shè)已知next(j)=x，現(xiàn)在計算，現(xiàn)在計算next(j+1)若若px=pj，則，則next(j+1) = x+1 = next(j)+1否則，設(shè)否則，設(shè)next(x)=h，(此時有此時有p0,h-1=px-h,x-1=pj-h,j-1) 若若ph=pj，則，則next(j+1) = h+1 否則，令否則，令next(h)=t, (此時有此時有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字符串的改進模式匹配算法字符串的改進模式匹配算法r對模式串對模式串P進行預(yù)處理，計算可以滑過多少個字符進行預(yù)處理，計算可以滑過多少個字符25-1，當，當 j = 0k+1，當，當 0 k j-1, 且使且使p0p1pk=pj-k-1pj-kpj-1的最大數(shù)的最大數(shù)next( j ) =0，其他情況，其他情況可按定義直接計算可按定義直接計算next，下面介紹一種快速的計算，下面介紹一種快速的計算next的方法的方法j=0;k=-1;next0=