數(shù)據(jù)結(jié)構(gòu)-王紅梅-第4章 字符串和多維數(shù)組

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 第第 4 章章 字符串和多維數(shù)組字符串和多維數(shù)組 本章的基本內(nèi)容是：本章的基本內(nèi)容是： 字符串。在程序設(shè)計(jì)語言中大都有串變量的概字符串。在程序設(shè)計(jì)語言中大都有串變量的概 念，而且實(shí)現(xiàn)了基本的串操作，本章重點(diǎn)討論串念，而且實(shí)現(xiàn)了基本的串操作，本章重點(diǎn)討論串 的存儲結(jié)構(gòu)及模式匹配算法。的存儲結(jié)構(gòu)及模式匹配算法。 數(shù)組。在程序設(shè)計(jì)語言中大都提供了數(shù)組作為數(shù)組。在程序設(shè)計(jì)語言中大都提供了數(shù)組作為 構(gòu)造數(shù)據(jù)類型，本章重點(diǎn)討論數(shù)組以及特殊矩陣構(gòu)造數(shù)據(jù)類型，本章重點(diǎn)討論數(shù)組以及特殊矩陣 的存儲與尋址。的存儲與尋址。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)

2、（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。 限制插入、刪除位置限制插入、刪除位置 棧棧僅在表的一端進(jìn)行插入和刪除操作僅在表的一端進(jìn)行插入和刪除操作 隊(duì)列隊(duì)列在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作 第第 4 章章 字符串和多維數(shù)組字符串和多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 線性表線性表具有相同類型的數(shù)據(jù)元素的有限序列。具有相同類型的數(shù)據(jù)元素的有限序列。 將元素類型擴(kuò)充為線性表將元素類型擴(kuò)充為線性表 （多維）（多維）

3、數(shù)組數(shù)組線性表中的數(shù)據(jù)元素可以是線性表線性表中的數(shù)據(jù)元素可以是線性表 第第 4 章章 字符串和多維數(shù)組字符串和多維數(shù)組 將元素類型限制為字符將元素類型限制為字符 串串零個或多個字符組成的有限序列零個或多個字符組成的有限序列 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 4.1 字符串字符串 串的邏輯結(jié)構(gòu)串的邏輯結(jié)構(gòu) p 非空串非空串通常記為：通常記為： s= s1 s2 sn 其中：其中：s是串名，雙引號是是串名，雙引號是定界符定界符，雙引號引起來的，雙引號引起來的 部分是串值部分是串值 ，si（1in）是一個任意字符。是一個任意字符。 p 串：串：零個或多個零個或

4、多個字符字符組成的有限組成的有限序列序列。 p 串長度：串長度：串中所包含的字符個數(shù)。串中所包含的字符個數(shù)。 p 空串：空串：長度為長度為0的串，記為：的串，記為： 。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 s1=ab12cd s2=ab12 s3=ab13 s4=ab12 s5= s6= 串的邏輯結(jié)構(gòu)串的邏輯結(jié)構(gòu) p子串：子串：串中任意個連續(xù)的字符組成的子序列。串中任意個連續(xù)的字符組成的子序列。 p主串：主串：包含子串的串。包含子串的串。 p子串的位置：子串的位置：子串的第一個字符在主串中的序號。子串的第一個字符在主串中的序號。 4.1 字符串字符串 數(shù)據(jù)

5、結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 串的邏輯結(jié)構(gòu)串的邏輯結(jié)構(gòu) p 串的數(shù)據(jù)對象約束為某個字符集。串的數(shù)據(jù)對象約束為某個字符集。 p 微機(jī)上常用的字符集是標(biāo)準(zhǔn)微機(jī)上常用的字符集是標(biāo)準(zhǔn)ascii碼，由碼，由 7 位二進(jìn)制位二進(jìn)制 數(shù)表示一個字符，總共可以表示數(shù)表示一個字符，總共可以表示 128 個字符。個字符。 p 擴(kuò)展擴(kuò)展ascii碼由碼由 8 位二進(jìn)制數(shù)表示一個字符，總共可位二進(jìn)制數(shù)表示一個字符，總共可 以表示以表示 256 個字符，足夠表示英語和一些特殊符號，但個字符，足夠表示英語和一些特殊符號，但 無法滿足國際需要。無法滿足國際需要。 p unicode由

6、由 16 位二進(jìn)制數(shù)表示一個字符，總共可以表位二進(jìn)制數(shù)表示一個字符，總共可以表 示示 216個字符，能夠表示世界上所有語言的所有字符，包個字符，能夠表示世界上所有語言的所有字符，包 括亞洲國家的表意字符。為了保持兼容性，括亞洲國家的表意字符。為了保持兼容性，unicode字符字符 集中的前集中的前256個字符與擴(kuò)展個字符與擴(kuò)展ascii碼完全相同。碼完全相同。 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 串的比較：串的比較：通過組成串的通過組成串的字符字符之間的比較來進(jìn)行的。之間的比較來進(jìn)行的。 給定兩個串：給定兩個串：x=x1x2xn和和y

7、=y1y2ym，則：，則： 1. 當(dāng)當(dāng)n=m且且x1=y1，xn=ym時，稱時，稱x=y； 2. 當(dāng)下列條件之一成立時，稱當(dāng)下列條件之一成立時，稱xy： nm且且xi=yi（1 in）；）； 存在存在kmin( (m, ,n) )，使得使得xi=yi( (1ik- -1) )且且xkyk。 串的邏輯結(jié)構(gòu)串的邏輯結(jié)構(gòu) 例：例：s1=ab12cd ，s2=ab12，s3=ab13 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 方案方案1：用一個變量來表示串的實(shí)際長度。用一個變量來表示串的實(shí)際長度。 如何表示串的長度？如何表示串的長度？ 串的存儲結(jié)構(gòu)

8、串的存儲結(jié)構(gòu) 0 1 2 3 4 5 6 max- -1 a b c d e f g9 空空 閑閑 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 方案方案1：用一個變量來表示串的實(shí)際長度。用一個變量來表示串的實(shí)際長度。 串的存儲結(jié)構(gòu)串的存儲結(jié)構(gòu) 如何表示串的長度？如何表示串的長度？ 0 1 2 3 4 5 6 7 max- -1 a b c d e f g 0 空空 閑閑 方案方案2：在串尾存儲一個不會在串中出現(xiàn)的特殊字符在串尾存儲一個不會在串中出現(xiàn)的特殊字符 作為串的終結(jié)符，作為串的終結(jié)符，表示串的結(jié)尾。表示串的結(jié)尾。 4.1 字符串字符串

9、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 方案方案3：用數(shù)組的用數(shù)組的0號單元存放串的長度，從號單元存放串的長度，從1號單號單 元開始存放串值。元開始存放串值。 串的存儲結(jié)構(gòu)串的存儲結(jié)構(gòu) 如何表示串的長度？如何表示串的長度？ 方案方案2：在串尾存儲一個不會在串中出現(xiàn)的特殊字符在串尾存儲一個不會在串中出現(xiàn)的特殊字符 作為串的終結(jié)符，作為串的終結(jié)符，表示串的結(jié)尾。表示串的結(jié)尾。 方案方案1：用一個變量來表示串的實(shí)際長度。用一個變量來表示串的實(shí)際長度。 0 1 2 3 4 5 6 7 max- -1 9 a b c d e f g 空空 閑閑 4.1 字符串字符串 數(shù)

10、據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配 模式匹配：模式匹配：給定主串給定主串s=s1s2sn和模式和模式t=t1t2tm， 在在s中尋找中尋找t 的過程稱的過程稱為模式匹配為模式匹配。如果匹配成功，返如果匹配成功，返 回回t 在在s中的位置；如果匹配失敗，返回中的位置；如果匹配失敗，返回0。 算法的算法的一次執(zhí)行時間一次執(zhí)行時間不容忽視：問題規(guī)模通常很不容忽視：問題規(guī)模通常很 大，常常需要在大量信息中進(jìn)行匹配；大，常常需要在大量信息中進(jìn)行匹配； 算法改進(jìn)所取得的算法改進(jìn)所取得的積累效益積累效益不容忽視：模式匹配不容忽視：模式匹配 操作經(jīng)常被調(diào)用

11、，執(zhí)行頻率高。操作經(jīng)常被調(diào)用，執(zhí)行頻率高。 模式匹配問題有什么特點(diǎn)模式匹配問題有什么特點(diǎn)？ 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 在下面的討論中，為了和在下面的討論中，為了和c+語言中的字符數(shù)組保語言中的字符數(shù)組保 持一致，采用第持一致，采用第 2 種順序存儲方法，即從數(shù)組下標(biāo)種順序存儲方法，即從數(shù)組下標(biāo) 0開始存放字符，并且在串尾存儲終結(jié)符開始存放字符，并且在串尾存儲終結(jié)符0。 0 1 2 3 4 5 6 7 max- -1 a b c d e f g 0 空空 閑閑 4.1 字符串字符串 模式匹配模式匹配 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版

12、）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 基本思想：基本思想：從主串從主串s的第一個字符開始和模式的第一個字符開始和模式t 的第的第 一個字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后一個字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后 續(xù)字符；否則，從主串續(xù)字符；否則，從主串s的第二個字符開始和模式的第二個字符開始和模式t 的第一個字符進(jìn)行比較，重復(fù)上述過程，直到的第一個字符進(jìn)行比較，重復(fù)上述過程，直到t 中的中的 字符全部比較完畢，則說明本趟匹配成功；或字符全部比較完畢，則說明本趟匹配成功；或s中字中字 符全部比較完，則說明匹配失敗。符全部比較完，則說明匹配失敗。 模式匹配模式匹配bf算法算法 4

13、.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 si 主串主串s 模式模式t tj j i 模式匹配模式匹配bf算法算法 回溯回溯 i 回溯回溯 j 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 si 主串主串s 模式模式t j i 模式匹配模式匹配bf算法算法 tj 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b i=2，j=2

14、失??；失敗； i回溯到回溯到1，j回溯到回溯到0 i j 模式匹配模式匹配bf算法算法 i j i j 第第 1 趟趟 a b c a c 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b j 模式匹配模式匹配bf算法算法 i 第第 1 趟趟 a b c a c 4.1 字符串字符串 i=2，j=2失敗；失??； i回溯到回溯到1，j回溯到回溯到0 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主

15、串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b i=1，j=0失敗失敗 i回溯到回溯到2，j回溯到回溯到0 模式匹配模式匹配bf算法算法 第第 2 趟趟 i j a b c a c 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b 模式匹配模式匹配bf算法算法 第第 2 趟趟 i j a b c a c 4.1 字符串字符串 i=1，j=0失敗失敗 i回溯到

16、回溯到2，j回溯到回溯到0 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b a b c a c i=6，j=4失敗失敗 i回溯到回溯到3，j回溯到回溯到0 模式匹配模式匹配bf算法算法 第第 3 趟趟 i j i j i j i j i j 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c

17、b a b a b c a c 模式匹配模式匹配bf算法算法 第第 3 趟趟 i j 4.1 字符串字符串 i=6，j=4失敗失敗 i回溯到回溯到3，j回溯到回溯到0 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b a b c a c i=3，j=0失敗失敗 i回溯到回溯到4，j回溯到回溯到0 模式匹配模式匹配bf算法算法 第第 4 趟趟 i j 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：

18、主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b a b c a c 模式匹配模式匹配bf算法算法 第第 4 趟趟 i j 4.1 字符串字符串 i=3，j=0失敗失敗 i回溯到回溯到4，j回溯到回溯到0 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b a b c a c i=4，j=0失敗失敗 i回溯到回溯到5，j回溯到回溯到0 模式匹配模式匹配bf算法算法 第第 5 趟趟

19、i j 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b a b c a c 模式匹配模式匹配bf算法算法 第第 5 趟趟 i j 4.1 字符串字符串 i=4，j=0失敗失敗 i回溯到回溯到5，j回溯到回溯到0 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 例：主串例：主串s=ababcabcacbab，模式模式t=abcac a b a b c a b c a c b a b a b c a c

20、 i=10，j=5，t中全部中全部 字符都比較完畢，字符都比較完畢， 匹配成功匹配成功 模式匹配模式匹配bf算法算法 第第 6 趟趟 i j i j i j i j i j 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 1. 在串在串s和串和串t中設(shè)比較的起始下標(biāo)中設(shè)比較的起始下標(biāo)i和和j； 2. 循環(huán)直到循環(huán)直到s或或t的所有字符均比較完的所有字符均比較完 2.1 如果如果si=tj，繼續(xù)比較繼續(xù)比較s和和t的下一個字符；的下一個字符； 2.2 否則，將否則，將i和和j回溯，準(zhǔn)備下一趟比較；回溯，準(zhǔn)備下一趟比較； 3. 如果如果t中所有字符均

21、比較完，則匹配成功，返回中所有字符均比較完，則匹配成功，返回 匹配的起始比較下標(biāo)；否則，匹配失敗，返回匹配的起始比較下標(biāo)；否則，匹配失敗，返回0； 模式匹配模式匹配bf算法算法 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 int bf( (char s , char t ) ) i=0; j=0; while ( (s0!=0 j+; else i=i- -j+1; j=0; if ( (tj=0) ) return ( (i- -j+1) ); else return 0; 模式匹配模式匹配bf算法算法 int bf( (char s ,

22、char t ) ) i=0; j=0;start=0; while ( (s0!=0 j+; else start+; i=start; j=0; if ( (tj=0) ) return start; else return 0; 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配bf算法算法 設(shè)串設(shè)串s長度為長度為n，串，串t長度為長度為m，在匹配成功的情況，在匹配成功的情況 下，考慮兩種極端情況：下，考慮兩種極端情況： 例如：例如：s=aaaaaaaaaabcdccccc t=bcd 4.1 字符串字符串 最好情況：最好情況

23、：不成功的匹配都發(fā)生在串不成功的匹配都發(fā)生在串t的第的第1個字符。個字符。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配bf算法算法 設(shè)串設(shè)串s長度為長度為n，串，串t長度為長度為m，在匹配成功的情況，在匹配成功的情況 下，考慮兩種極端情況：下，考慮兩種極端情況： 最好情況：最好情況：不成功的匹配都發(fā)生在串不成功的匹配都發(fā)生在串t的第的第1個字符。個字符。 設(shè)匹配成功發(fā)生在設(shè)匹配成功發(fā)生在si處，則在處，則在i-1趟不成功的匹配中共趟不成功的匹配中共 比較了比較了i-1次，第次，第i趟成功的匹配共比較了趟成功的匹配共比較了m次，所以次，所以 總共比

24、較了總共比較了i-1+m次，所有匹配成功的可能情況共有次，所有匹配成功的可能情況共有 n-m+1種，則：種，則： )( 2 )( )1( 1 1 mno mn mi p mn i i + += = + + = = + +- - + + - - = = 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配bf算法算法 設(shè)串設(shè)串s長度為長度為n，串，串t長度為長度為m，在匹配成功的情況，在匹配成功的情況 下，考慮兩種極端情況：下，考慮兩種極端情況： 最壞情況：最壞情況：不成功的匹配都發(fā)生在串不成功的匹配都發(fā)生在串t的最后一個字符。的最后一

25、個字符。 例如：例如：s=aaaaaaaaaaabccccc t=aaab 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配bf算法算法 設(shè)串設(shè)串s長度為長度為n，串，串t長度為長度為m，在匹配成功的情況，在匹配成功的情況 下，考慮兩種極端情況：下，考慮兩種極端情況： 最壞情況：最壞情況：不成功的匹配都發(fā)生在串不成功的匹配都發(fā)生在串t的最后一個字符。的最后一個字符。 設(shè)匹配成功發(fā)生在設(shè)匹配成功發(fā)生在si處，則在處，則在i-1趟不成功的匹配中共趟不成功的匹配中共 比較了比較了(i-1)m次，第次，第i趟成功的匹配共比較了趟成功的匹配

26、共比較了m次，次， 所以總共比較了所以總共比較了im次，因此次，因此 )( 2 )2( )( 1 1 mno mnm mip mn i i = +- = +- = 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配kmp算法算法 為什么為什么bf算法時間性能低？算法時間性能低？ 在每趟匹配不成功時存在大量在每趟匹配不成功時存在大量回溯回溯，沒有利用已經(jīng)，沒有利用已經(jīng) 部分匹配的結(jié)果。部分匹配的結(jié)果。 如何在匹配不成功時主串不回溯？如何在匹配不成功時主串不回溯？ 主串不回溯，模式就需要向右滑動一段距離。主串不回溯，模式就需要向右滑動一

27、段距離。 如何確定模式的滑動距離？如何確定模式的滑動距離？ 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 i=2，j=2失?。皇?； s1=t1; t0t1 t0s1 模式匹配模式匹配kmp算法算法 a b a b c a b c a c b a b i j 第第 1 趟趟 a b c a c a b a b c a b c a c b a b 第第 2 趟趟 a b c a c 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 i=2，j=2失敗；失??； s1=t1; t0t1 t0s1 模式匹配

28、模式匹配kmp算法算法 a b a b c a b c a c b a b i j 第第 1 趟趟 a b c a c a b a b c a b c a c b a b a b c a c 第第 3 趟趟 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配kmp算法算法 a b a b c a b c a c b a b a b c a c 第第 3 趟趟 i j i=6，j=4失敗失敗 s3=t1;t0t1 t0s3 a b a b c a b c a c b a b a b c a c 第第 4 趟趟 4.1 字符串字符串 數(shù)

29、據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配kmp算法算法 a b a b c a b c a c b a b a b c a c 第第 3 趟趟 i j i=6，j=4失敗失敗 s4=t2; t0t2 t0s4 a b a b c a b c a c b a b a b c a c 第第 5 趟趟 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配kmp算法算法 a b a b c a b c a c b a b a b c a c 第第 3 趟趟 i j a b a b c a b c

30、 a c b a b a b c a c 第第 6 趟趟 匹配成功匹配成功 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 需要討論兩個問題：需要討論兩個問題： 如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動 的新比較起點(diǎn)的新比較起點(diǎn)k？ 模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的? 結(jié)論：結(jié)論： i可以不回溯，模式向右滑動到的新可以不回溯，模式向右滑動到的新 比較起點(diǎn)比較起點(diǎn)k ，并且，并且k 僅與模式串僅與模式串t有關(guān)！有關(guān)！ 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（

31、數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 抓住部分匹配時的兩個特征：設(shè)模式滑動到第抓住部分匹配時的兩個特征：設(shè)模式滑動到第 k 個字符個字符 （1）則）則t0tk-1 = si-ksi-1 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 a b a b c a b a b c a c i j a b a b c a b a b c a c i j=k 下一趟下一趟 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 抓住部分匹配時的兩個特征：設(shè)模式滑動到第抓住部分匹配時的兩個特征：設(shè)模式滑動到第 k 個字符個字符 （1）則）則t0tk-1 =

32、si-ksi-1 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 a b a b c a b a b c a c i j a b a b c a b a b c a c i j=k 下一趟下一趟 （2）則）則tj-ktj-1 = si-ksi-1 兩式聯(lián)立可得：兩式聯(lián)立可得：t0tk-1 = tj-ktj-1 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 （1） k 與與 j 具有函數(shù)關(guān)系，具有函數(shù)關(guān)系，由當(dāng)前失配位置由當(dāng)前失配位置 j ，可，可 以計(jì)算出以計(jì)算出滑動位置滑動位置 k（即比較的（即比較的新起點(diǎn)）新起點(diǎn)）； （2）滑動位置滑動位置k 僅與模式串僅

33、與模式串t有關(guān)有關(guān)。 從第從第0位往右位往右 經(jīng)過經(jīng)過k位位 從從j-1位往左位往左 經(jīng)過經(jīng)過k位位 max k | 1kj 且且t0 tk -1 = tj-k tj - 1 模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的模式應(yīng)該向右滑多遠(yuǎn)才是最高效率的? 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 p nextj函數(shù)值表示模式函數(shù)值表示模式 t 中最大相同前綴和后綴中最大相同前綴和后綴 （注意：是真子串）的長度。（注意：是真子串）的長度。 p 模式中相似部分越多，模式中相似部分越多，nextj函數(shù)值越大，表示模函數(shù)值越大，

34、表示模 式式 t 字符之間的相關(guān)度越高，模式串向右滑動得越遠(yuǎn)，字符之間的相關(guān)度越高，模式串向右滑動得越遠(yuǎn)， 與主串進(jìn)行比較的次數(shù)越少，時間復(fù)雜度就越好。與主串進(jìn)行比較的次數(shù)越少，時間復(fù)雜度就越好。 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 -1 j = 0 max k | 1kj 且且t0 tk - -1 = tj- -k tj - 1 0 其它情況其它情況 nextj= 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 n 當(dāng)當(dāng)j=0時，時，nextj=-1； /nextj=-1表示不進(jìn)行字符比較表示不進(jìn)行字符比較 n 當(dāng)當(dāng)j0時，時，nextj的值為：模

35、式串的位置從的值為：模式串的位置從0到到j(luò)-1構(gòu)構(gòu) 成的串中所出現(xiàn)的首尾相同的子串的最大長度。成的串中所出現(xiàn)的首尾相同的子串的最大長度。 n 當(dāng)無首尾相同的子串時當(dāng)無首尾相同的子串時nextj的值為的值為0。 /nextj=0表示從模式串頭部開始進(jìn)行字符比較表示從模式串頭部開始進(jìn)行字符比較 計(jì)算計(jì)算nextj的方法：的方法： 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 j=0時時, next j -1； j=1時時, next j 0； 模模 式式 串串 t： a b a b c 可能失配位可能失配位 j： 0

36、 1 2 3 4 新匹配位新匹配位k=nextj : -1 0 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 j=0時時, next j -1； j=1時時, next j 0； j=2時時, t0t1，因此，因此，k=0； 模模 式式 串串 t： a b a b c 可能失配位可能失配位 j： 0 1 2 3 4 新匹配位新匹配位k=nextj : -1 00 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 j=0時時, next

37、j -1； j=1時時, next j 0； j=2時時, t0t1，因此，因此，k=0； j=3時時, t0t2，t0t1 t1t2，因此，因此，k=1； 模模 式式 串串 t： a b a b c 可能失配位可能失配位 j： 0 1 2 3 4 新匹配位新匹配位k=nextj : -1 001 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 j=0時時, next j -1； j=1時時, next j 0； j=2時時, t0t1，因此，因此，k=0； j=3時時, t0t2，t0t1 t1t2，因此，因此，

38、k=1； j=4時時, t0 t3，t0t1 = t2t3， t0t1t2t1t2t3，因此，因此，k=2； 模模 式式 串串 t： a b a b c 可能失配位可能失配位 j： 0 1 2 3 4 新匹配位新匹配位k=nextj : -1 0012 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 i=4，j=4失?。皇?； j = next4 = 2 a b a b a a b a b c b i j 第第 1 趟趟 a b a b c nextj=-1,

39、0, 0, 1, 2 a b a b a a b a b c b i j 第第 2 趟趟 a b a b c 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹配kmp算法算法 4.1 字符串字符串 i=5，j=3失敗；失敗； j = next3 = 1 nextj=-1, 0, 0, 1, 2 a b a b a a b a b c b i j 第第 2 趟趟 a b a b c a b a b a a b a b c b i j 第第 3 趟趟 a b a b c 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 模式匹配模式匹

40、配kmp算法算法 4.1 字符串字符串 i=5，j=1失?。皇?； j = next1 = 0 nextj=-1, 0, 0, 1, 2 a b a b a a b a b c b i 第第 3 趟趟 j a b a b c a b a b a a b a b c b i 第第 4 趟趟 j a b a b c 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 1. 在串在串s和串和串t中分別設(shè)比較的起始下標(biāo)中分別設(shè)比較的起始下標(biāo)i和和j； 2. 循環(huán)直到循環(huán)直到s或或t的所有字符均比較完的所有字符均比較完 2.1 如果如果si=tj，繼續(xù)比較繼續(xù)比較s和和t的下一個字

41、符；否則的下一個字符；否則 2.2 將將j向右滑動到向右滑動到nextj位置，即位置，即j=nextj； 2.3 如果如果j=-1，則將則將i和和j分別加分別加1，準(zhǔn)備下一趟比較；，準(zhǔn)備下一趟比較； 3. 如果如果t中所有字符均比較完畢，則返回匹配的起始下標(biāo)；中所有字符均比較完畢，則返回匹配的起始下標(biāo)； 否則返回否則返回0； kmp算法的偽代碼描述算法的偽代碼描述 4.1 字符串字符串 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 數(shù)組的定義數(shù)組的定義 數(shù)組是由一組數(shù)組是由一組類型相同類型相同的數(shù)據(jù)元素構(gòu)成的的數(shù)據(jù)元素構(gòu)成的有序有序集集 合合，每個數(shù)據(jù)元素稱為一個數(shù)

42、組元素（簡稱為元每個數(shù)據(jù)元素稱為一個數(shù)組元素（簡稱為元 素），每個元素受素），每個元素受n(n1)個個線性關(guān)系線性關(guān)系的約束，的約束，每每 個元素在個元素在n個線性關(guān)系中的序號個線性關(guān)系中的序號i1、i2、in稱為稱為 該元素的下標(biāo)，并稱該數(shù)組為該元素的下標(biāo)，并稱該數(shù)組為 n 維數(shù)組。維數(shù)組。 數(shù)組的特點(diǎn)數(shù)組的特點(diǎn) 元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型；元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型； 數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合。數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合。 4.2 多維數(shù)組多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 a11 a

43、12 a1n a21 a22 a2n am1 am2 amn a= 例如，元素例如，元素a22受兩個線性關(guān)系的約束，在行上有受兩個線性關(guān)系的約束，在行上有 一個行前驅(qū)一個行前驅(qū)a21和一個行后繼和一個行后繼a23，在列上有一個列，在列上有一個列 前驅(qū)前驅(qū)a12和和一個列后繼和和一個列后繼a32。 4.2 多維數(shù)組多維數(shù)組 數(shù)組的定義數(shù)組的定義 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 a11 a12 a1n a21 a22 a2n am1 am2 amn a= a=(a1，a2，an) 其中：其中： ai=(a1i，a2i，ami) (1in) 數(shù)組數(shù)組線性表的

44、推廣線性表的推廣 二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。二維數(shù)組是數(shù)據(jù)元素為線性表的線性表。 4.2 多維數(shù)組多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 數(shù)組的基本操作數(shù)組的基本操作 在數(shù)組中插入（或）一個元素有意義嗎？在數(shù)組中插入（或）一個元素有意義嗎？ a11 a12 a1n a21 a22 a2n am1 am2 amn a= 將元素將元素 x 插入插入 到數(shù)組中第到數(shù)組中第1行第行第2列。列。 x a11 a12 a1n a21 a22 a2n am1 am2 amn a= 刪除數(shù)組中刪除數(shù)組中 第第1行第行第2列元素。列元素。 4.2 多維數(shù)組多

45、維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 數(shù)組的基本操作數(shù)組的基本操作 存?。航o定一組下標(biāo)，讀出對應(yīng)的數(shù)組元素；存取：給定一組下標(biāo)，讀出對應(yīng)的數(shù)組元素； 修改：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的修改：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的 數(shù)組元素。數(shù)組元素。 存取和修改操作本質(zhì)上只對應(yīng)一種操作存取和修改操作本質(zhì)上只對應(yīng)一種操作尋址尋址 數(shù)組應(yīng)該采用何種方式存儲？數(shù)組應(yīng)該采用何種方式存儲？ 數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間，數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間， 適合采用順序存儲。適合采用順序存儲。 4.2 多維數(shù)組多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)

46、據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 數(shù)組的存儲結(jié)構(gòu)與尋址數(shù)組的存儲結(jié)構(gòu)與尋址一維數(shù)組一維數(shù)組 設(shè)一維數(shù)組的下標(biāo)的范圍為閉區(qū)間設(shè)一維數(shù)組的下標(biāo)的范圍為閉區(qū)間l，h，每個每個 數(shù)組元素占用數(shù)組元素占用 c 個存儲單元，則個存儲單元，則其其任一元任一元素素 ai 的的 存儲地址可由下式確定：存儲地址可由下式確定： loc(ai)loc(al)(il)c c al ai-1 ai ah al+1 loc(al)loc(ai) 4.2 多維數(shù)組多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 常用的映射方法有兩種：常用的映射方法有兩種： 按按行

47、行優(yōu)先：優(yōu)先：先行后列先行后列，先存儲行號較小的元素，先存儲行號較小的元素， 行號相同者先存儲列號較小的元素。行號相同者先存儲列號較小的元素。 按按列列優(yōu)先：優(yōu)先：先列后行先列后行，先存儲列號較小的元素，先存儲列號較小的元素， 列號相同者先存儲行號較小的元素。列號相同者先存儲行號較小的元素。 數(shù)組的存儲結(jié)構(gòu)與尋址數(shù)組的存儲結(jié)構(gòu)與尋址二維數(shù)組二維數(shù)組 二維數(shù)組二維數(shù)組內(nèi)內(nèi) 存存 二維結(jié)構(gòu)二維結(jié)構(gòu)一維結(jié)構(gòu)一維結(jié)構(gòu) 4.2 多維數(shù)組多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 l2h2 l1 h1 (a) 二維數(shù)組二維數(shù)組 aij前面的元素個數(shù)前面的元素個數(shù) =

48、陰影部分的面積陰影部分的面積 =整行數(shù)每行元素個數(shù)整行數(shù)每行元素個數(shù)+本行中本行中 aij前面的元素個數(shù)前面的元素個數(shù) =( (i - -l1) )( (h2 - -l21) )( (j - -l2) ) 本行中本行中aij前面的元素個數(shù)前面的元素個數(shù) 每行元素個數(shù)每行元素個數(shù) 整整 行行 數(shù)數(shù) aij 按行優(yōu)先存儲的尋址按行優(yōu)先存儲的尋址 4.2 多維數(shù)組多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 第第l1行行第第l1+1行行 al1l2 al1h2 a(l1+1)l2 a(l1+1)h2 aij ah1h2 loc( (aij) )loc( (al1

49、l2) ) ( (i - -l1) )( (h2 - -l21) )( (j - -l2) )個元素個元素 loc(aij)loc(al1l2)(il1)(h2l21)(jl2)c 按行優(yōu)先存儲的尋址按行優(yōu)先存儲的尋址 按列優(yōu)先存儲的尋址方法與此類似。按列優(yōu)先存儲的尋址方法與此類似。 4.2 多維數(shù)組多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 loc(aijk ) = loc(a000) +( im2m3 + jm3 + k )c n（n2）維維 數(shù)組一般也采用數(shù)組一般也采用 按行優(yōu)先和按列按行優(yōu)先和按列 優(yōu)先兩種存儲方優(yōu)先兩種存儲方 法。法。請自行推導(dǎo)

50、請自行推導(dǎo) 任一元素存儲地任一元素存儲地 址的計(jì)算方法。址的計(jì)算方法。 數(shù)組的存儲結(jié)構(gòu)與尋址數(shù)組的存儲結(jié)構(gòu)與尋址多維數(shù)組多維數(shù)組 4.2 多維數(shù)組多維數(shù)組 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 p 特殊矩陣：特殊矩陣：矩陣中很多值相同的元素并且它們的矩陣中很多值相同的元素并且它們的 分布有一定的規(guī)律。分布有一定的規(guī)律。 p 稀疏矩陣：稀疏矩陣：矩陣中有很多零元素。矩陣中有很多零元素。 p 壓縮存儲的基本思想是：壓縮存儲的基本思想是： 為多個值為多個值相同相同的元素只分配的元素只分配一個一個存儲空間；存儲空間； 對對零零元

51、素元素不分配不分配存儲空間。存儲空間。 特殊矩陣和稀疏矩陣特殊矩陣和稀疏矩陣 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對稱矩陣對稱矩陣 36478 62842 48169 74605 82957 a 對稱矩陣特點(diǎn)：對稱矩陣特點(diǎn)：aij=aji 如何壓縮存儲？如何壓縮存儲？ 只存儲下三角部分的元素。只存儲下三角部分的元素。 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 (a) 下三角矩陣下三角矩陣 (b) 存儲說明存儲說明 (c) 計(jì)算方法計(jì)算方法 aij在一維

52、數(shù)組中的序號在一維數(shù)組中的序號 =陰影部分的面積陰影部分的面積 = i( (i+1) )/2+ j 一維數(shù)組下標(biāo)從一維數(shù)組下標(biāo)從0開始開始 aij在一維數(shù)組中的下標(biāo)在一維數(shù)組中的下標(biāo) k= i( (i+1) )/2+ j-1 1 i n 1 j n aij 每行元素個數(shù)每行元素個數(shù) 1 2 i-1 aij在本行中的序號在本行中的序號 aij 第第1行行 第第2行行 第第i-1行行 對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 對于下三角中的元素對于下三角中的元素aij（ij），在數(shù)組，在數(shù)組

53、sa中的下標(biāo)中的下標(biāo)k 與與i、j的關(guān)系為：的關(guān)系為：ki(i1)/2j -1。 上三角中的元素上三角中的元素aij（ij），），因?yàn)橐驗(yàn)閍ijaji，則訪問和則訪問和 它對應(yīng)的元素它對應(yīng)的元素aji即可，即：即可，即：kj(j1)/2i -1 。 對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲 第第1行行第第n-1行行第第0行行 a11 a21 a22 a31 a32 a33 aij a n1 an2 ann 第第2行行 0 1 2 3 4 5 k n(n+1)/2-1 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 特殊矩陣的壓縮存儲特

54、殊矩陣的壓縮存儲三角矩陣三角矩陣 3 cc c c 6 2c c c 4 81 c c 7 46 0 c 8 29 5 7 (a)下三角矩陣下三角矩陣 3 4 8 1 0 c2 9 4 6 cc 5 7 cc c 0 8 cc c c 7 (b)上三角矩陣上三角矩陣 如何壓縮存儲？如何壓縮存儲？ 只存儲上三角（或下三角）部分的元素。只存儲上三角（或下三角）部分的元素。 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標(biāo)中的下標(biāo)k與與i、j的對應(yīng)關(guān)系：的對應(yīng)關(guān)系： i( (i1)

55、)/2j-1 當(dāng)當(dāng)ij n( (n1) )/2 當(dāng)當(dāng)ij k= 下三角矩陣的壓縮存儲下三角矩陣的壓縮存儲 0 1 2 3 4 5 k n(n+1)/2 第第1行行第第0行行 a11 a21 a22 a31 a32 aij ann 第第2行行 c a33 存儲存儲 下三角下三角元素元素 對角線上方的常數(shù)對角線上方的常數(shù)只存一個只存一個 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標(biāo)中的下標(biāo)k與與i、j的對應(yīng)關(guān)系：的對應(yīng)關(guān)系： (i-1)(2n-i+2)/2+j-i 當(dāng)當(dāng)ij n

56、( (n1) ) /2 當(dāng)當(dāng)ij k= 上三角矩陣的壓縮存儲上三角矩陣的壓縮存儲 存儲存儲 上三角上三角元素元素 對角線上方的常數(shù)對角線上方的常數(shù)只存一個只存一個 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對角矩陣對角矩陣 對角矩陣：對角矩陣：所有非零元素都集中在以主對角線為中心所有非零元素都集中在以主對角線為中心 的帶狀區(qū)域中，除了主的帶狀區(qū)域中，除了主對角線和它的上下方若干條對對角線和它的上下方若干條對 角線的元素外，所有其他元素都為零。角線的元素外，所有其他元素都為零。 a11 a1

57、2 0 0 0 a21 a22 a23 0 0 0 a32 a33a34 0 0 0 a43a44 a45 0 0 0 a54 a55 a= 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 按行按行 存儲存儲 元素元素aij在一維數(shù)組中的序號在一維數(shù)組中的序號 =2 + 3( (i2) )+( ( ji + 2) ) =2i+ j -2 一維數(shù)組下標(biāo)從一維數(shù)組下標(biāo)從0開始開始 元素元素aij在一維數(shù)組中的下標(biāo)在一維數(shù)組中的下標(biāo) = 2i+ j -3 (b) 尋址的計(jì)算方法尋址的計(jì)算方法 (c) 壓縮到一維數(shù)組中壓縮到一維數(shù)組中 a

58、11 a12 a21 a22 a23 a32 a33 a34 a43 a44 a45 a54 a55 0 1 2 3 4 5 6 7 8 9 10 11 12 對角矩陣的壓縮存儲對角矩陣的壓縮存儲 (a) 三對角矩陣三對角矩陣 0 0 0 0 0 0 0 0 0 0 0 0 a= a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 a45 a54 a55 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 15 0 0 0 0 0 0 11 0 0 0 0 0 0 0

59、6 0 0 0 0 0 0 0 0 9 0 0 0 0 0 a= 如何只存儲非零元素？如何只存儲非零元素？ 注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。 4.3 矩陣的壓縮存儲矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c+版）第版）第2版版 清華大學(xué)出版社清華大學(xué)出版社 template struct element int row, col; /行號，列號行號，列號 datatype item /非零元素值非零元素值 ; 將稀疏矩陣中的每個非零元素表示為將稀疏矩陣中的每個非零元素表示為： ( (行號，列號，非零元素值行號，列號，非零元素值) )三元組三元組