数据结构-王红梅-第4章 字符串和多维数组.

1、数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 第第 4 章章 字符串和多维数组字符串和多维数组 本章的基本内容是：本章的基本内容是： 字符串。在程序设计语言中大都有串变量的概字符串。在程序设计语言中大都有串变量的概 念，而且实现了基本的串操作，本章重点讨论串念，而且实现了基本的串操作，本章重点讨论串 的存储结构及模式匹配算法。的存储结构及模式匹配算法。 数组。在程序设计语言中大都提供了数组作为数组。在程序设计语言中大都提供了数组作为 构造数据类型，本章重点讨论数组以及特殊矩阵构造数据类型，本章重点讨论数组以及特殊矩阵 的存储与寻址。的存储与寻址。 数据结构（数据结构

2、（C+版）第版）第2版版 清华大学出版社清华大学出版社 线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。 限制插入、删除位置限制插入、删除位置 栈栈仅在表的一端进行插入和删除操作仅在表的一端进行插入和删除操作 队列队列在一端进行插入操作，而另一端进行删除操作在一端进行插入操作，而另一端进行删除操作 第第 4 章章 字符串和多维数组字符串和多维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 线性表线性表具有相同类型的数据元素的有限序列。具有相同类型的数据元素的有限序列。 将元素类型扩充为线性表将元素类型扩充为线性表 （多维）（多维）

3、数组数组线性表中的数据元素可以是线性表线性表中的数据元素可以是线性表 第第 4 章章 字符串和多维数组字符串和多维数组 将元素类型限制为字符将元素类型限制为字符 串串零个或多个字符组成的有限序列零个或多个字符组成的有限序列 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 4.1 字符串字符串 串的逻辑结构串的逻辑结构 p 非空串非空串通常记为：通常记为： S= s1 s2 sn 其中：其中：S是串名，双引号是是串名，双引号是定界符定界符，双引号引起来的，双引号引起来的 部分是串值部分是串值 ，si（1in）是一个任意字符。是一个任意字符。 p 串：串：零个或多个零个或

4、多个字符字符组成的有限组成的有限序列序列。 p 串长度：串长度：串中所包含的字符个数。串中所包含的字符个数。 p 空串：空串：长度为长度为0的串，记为：的串，记为： 。 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 S1=ab12cd S2=ab12 S3=ab13 S4=ab12 S5= S6= 串的逻辑结构串的逻辑结构 p子串：子串：串中任意个连续的字符组成的子序列。串中任意个连续的字符组成的子序列。 p主串：主串：包含子串的串。包含子串的串。 p子串的位置：子串的位置：子串的第一个字符在主串中的序号。子串的第一个字符在主串中的序号。 4.1 字符串字符串 数据

5、结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 串的逻辑结构串的逻辑结构 p 串的数据对象约束为某个字符集。串的数据对象约束为某个字符集。 p 微机上常用的字符集是标准微机上常用的字符集是标准ASCII码，由码，由 7 位二进制位二进制 数表示一个字符，总共可以表示数表示一个字符，总共可以表示 128 个字符。个字符。 p 扩展扩展ASCII码由码由 8 位二进制数表示一个字符，总共可位二进制数表示一个字符，总共可 以表示以表示 256 个字符，足够表示英语和一些特殊符号，但个字符，足够表示英语和一些特殊符号，但 无法满足国际需要。无法满足国际需要。 p Unicode由

6、由 16 位二进制数表示一个字符，总共可以表位二进制数表示一个字符，总共可以表 示示 216个字符，能够表示世界上所有语言的所有字符，包个字符，能够表示世界上所有语言的所有字符，包 括亚洲国家的表意字符。为了保持兼容性，括亚洲国家的表意字符。为了保持兼容性，Unicode字符字符 集中的前集中的前256个字符与扩展个字符与扩展ASCII码完全相同。码完全相同。 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 串的比较：串的比较：通过组成串的通过组成串的字符字符之间的比较来进行的。之间的比较来进行的。 给定两个串：给定两个串：X=x1x2xn和和Y

7、=y1y2ym，则：，则： 1. 当当n=m且且x1=y1，xn=ym时，称时，称X=Y； 2. 当下列条件之一成立时，称当下列条件之一成立时，称XY： nm且且xi=yi（1 in）；）； 存在存在kmin( (m, ,n) )，使得使得xi=yi( (1ik- -1) )且且xkyk。 串的逻辑结构串的逻辑结构 例：例：S1=ab12cd ，S2=ab12，S3=ab13 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 方案方案1：用一个变量来表示串的实际长度。用一个变量来表示串的实际长度。 如何表示串的长度？如何表示串的长度？ 串的存储结构

8、串的存储结构 0 1 2 3 4 5 6 Max- -1 a b c d e f g9 空空 闲闲 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 方案方案1：用一个变量来表示串的实际长度。用一个变量来表示串的实际长度。 串的存储结构串的存储结构 如何表示串的长度？如何表示串的长度？ 0 1 2 3 4 5 6 7 Max- -1 a b c d e f g 0 空空 闲闲 方案方案2：在串尾存储一个不会在串中出现的特殊字符在串尾存储一个不会在串中出现的特殊字符 作为串的终结符，作为串的终结符，表示串的结尾。表示串的结尾。 4.1 字符串字符串

9、数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 方案方案3：用数组的用数组的0号单元存放串的长度，从号单元存放串的长度，从1号单号单 元开始存放串值。元开始存放串值。 串的存储结构串的存储结构 如何表示串的长度？如何表示串的长度？ 方案方案2：在串尾存储一个不会在串中出现的特殊字符在串尾存储一个不会在串中出现的特殊字符 作为串的终结符，作为串的终结符，表示串的结尾。表示串的结尾。 方案方案1：用一个变量来表示串的实际长度。用一个变量来表示串的实际长度。 0 1 2 3 4 5 6 7 Max- -1 9 a b c d e f g 空空 闲闲 4.1 字符串字符串 数

10、据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配 模式匹配：模式匹配：给定主串给定主串S=s1s2sn和模式和模式T=t1t2tm， 在在S中寻找中寻找T 的过程称的过程称为模式匹配为模式匹配。如果匹配成功，返如果匹配成功，返 回回T 在在S中的位置；如果匹配失败，返回中的位置；如果匹配失败，返回0。 算法的算法的一次执行时间一次执行时间不容忽视：问题规模通常很不容忽视：问题规模通常很 大，常常需要在大量信息中进行匹配；大，常常需要在大量信息中进行匹配； 算法改进所取得的算法改进所取得的积累效益积累效益不容忽视：模式匹配不容忽视：模式匹配 操作经常被调用

11、，执行频率高。操作经常被调用，执行频率高。 模式匹配问题有什么特点模式匹配问题有什么特点？ 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 在下面的讨论中，为了和在下面的讨论中，为了和C+语言中的字符数组保语言中的字符数组保 持一致，采用第持一致，采用第 2 种顺序存储方法，即从数组下标种顺序存储方法，即从数组下标 0开始存放字符，并且在串尾存储终结符开始存放字符，并且在串尾存储终结符0。 0 1 2 3 4 5 6 7 Max- -1 a b c d e f g 0 空空 闲闲 4.1 字符串字符串 模式匹配模式匹配 数据结构（数据结构（C+版

12、）第版）第2版版 清华大学出版社清华大学出版社 基本思想：基本思想：从主串从主串S的第一个字符开始和模式的第一个字符开始和模式T 的第的第 一个字符进行比较，若相等，则继续比较两者的后一个字符进行比较，若相等，则继续比较两者的后 续字符；否则，从主串续字符；否则，从主串S的第二个字符开始和模式的第二个字符开始和模式T 的第一个字符进行比较，重复上述过程，直到的第一个字符进行比较，重复上述过程，直到T 中的中的 字符全部比较完毕，则说明本趟匹配成功；或字符全部比较完毕，则说明本趟匹配成功；或S中字中字 符全部比较完，则说明匹配失败。符全部比较完，则说明匹配失败。 模式匹配模式匹配BF算法算法 4

13、.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 si 主串主串S 模式模式T tj j i 模式匹配模式匹配BF算法算法 回溯回溯 i 回溯回溯 j 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 si 主串主串S 模式模式T j i 模式匹配模式匹配BF算法算法 tj 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主

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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：

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 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 例：主串例：主串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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 1. 在串在串S和串和串T中设比较的起始下标中设比较的起始下标i和和j； 2. 循环直到循环直到S或或T的所有字符均比较完的所有字符均比较完 2.1 如果如果Si=Tj，继续比较继续比较S和和T的下一个字符；的下一个字符； 2.2 否则，将否则，将i和和j回溯，准备下一趟比较；回溯，准备下一趟比较； 3. 如果如果T中所有字符均

21、比较完，则匹配成功，返回中所有字符均比较完，则匹配成功，返回 匹配的起始比较下标；否则，匹配失败，返回匹配的起始比较下标；否则，匹配失败，返回0； 模式匹配模式匹配BF算法算法 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配BF算法算法 设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况，在匹配成功的情况 下，考虑两种极端情况：下，考虑两种极端情况： 例如：例如：S=aaaaaaaaaabcdccccc T=bcd 4.1 字符串字符串 最好情况：最好情况

23、：不成功的匹配都发生在串不成功的匹配都发生在串T的第的第1个字符。个字符。 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配BF算法算法 设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况，在匹配成功的情况 下，考虑两种极端情况：下，考虑两种极端情况： 最好情况：最好情况：不成功的匹配都发生在串不成功的匹配都发生在串T的第的第1个字符。个字符。 设匹配成功发生在设匹配成功发生在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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配BF算法算法 设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况，在匹配成功的情况 下，考虑两种极端情况：下，考虑两种极端情况： 最坏情况：最坏情况：不成功的匹配都发生在串不成功的匹配都发生在串T的最后一个字符。的最后一

25、个字符。 例如：例如：S=aaaaaaaaaaabccccc T=aaab 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配BF算法算法 设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况，在匹配成功的情况 下，考虑两种极端情况：下，考虑两种极端情况： 最坏情况：最坏情况：不成功的匹配都发生在串不成功的匹配都发生在串T的最后一个字符。的最后一个字符。 设匹配成功发生在设匹配成功发生在si处，则在处，则在i-1趟不成功的匹配中共趟不成功的匹配中共 比较了比较了(i-1)m次，第次，第i趟成功的匹配共比较了趟成功的匹配

26、共比较了m次，次， 所以总共比较了所以总共比较了im次，因此次，因此 )( 2 )2( )( 1 1 mnO mnm mip mn i i = +- = +- = 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配KMP算法算法 为什么为什么BF算法时间性能低？算法时间性能低？ 在每趟匹配不成功时存在大量在每趟匹配不成功时存在大量回溯回溯，没有利用已经，没有利用已经 部分匹配的结果。部分匹配的结果。 如何在匹配不成功时主串不回溯？如何在匹配不成功时主串不回溯？ 主串不回溯，模式就需要向右滑动一段距离。主串不回溯，模式就需要向右滑动一

27、段距离。 如何确定模式的滑动距离？如何确定模式的滑动距离？ 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配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 字符串字符串 数

29、据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 需要讨论两个问题：需要讨论两个问题： 如何由当前部分匹配结果确定模式向右滑动如何由当前部分匹配结果确定模式向右滑动 的新比较起点的新比较起点k？ 模式应该向右滑多远才是最高效率的模式应该向右滑多远才是最高效率的? 结论：结论： i可以不回溯，模式向右滑动到的新可以不回溯，模式向右滑动到的新 比较起点比较起点k ，并且，并且k 仅与模式串仅与模式串T有关！有关！ 模式匹配模式匹配KMP算法算法 4.1 字符串字符串 数据结构（

31、数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 抓住部分匹配时的两个特征：设模式滑动到第抓住部分匹配时的两个特征：设模式滑动到第 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 下一趟下一趟 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 抓住部分匹配时的两个特征：设模式滑动到第抓住部分匹配时的两个特征：设模式滑动到第 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 两式联立可得：两式联立可得：T0Tk-1 = Tj-kTj-1 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 （1） k 与与 j 具有函数关系，具有函数关系，由当前失配位置由当前失配位置 j ，可，可 以计算出以计算出滑动位置滑动位置 k（即比较的（即比较的新起点）新起点）； （2）滑动位置滑动位置k 仅与模式串仅

33、与模式串T有关有关。 从第从第0位往右位往右 经过经过k位位 从从j-1位往左位往左 经过经过k位位 max k | 1kj 且且T0 Tk -1 = Tj-k Tj - 1 模式应该向右滑多远才是最高效率的模式应该向右滑多远才是最高效率的? 模式匹配模式匹配KMP算法算法 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 p nextj函数值表示模式函数值表示模式 T 中最大相同前缀和后缀中最大相同前缀和后缀 （注意：是真子串）的长度。（注意：是真子串）的长度。 p 模式中相似部分越多，模式中相似部分越多，nextj函数值越大，表示模函数值越大，

34、表示模 式式 T 字符之间的相关度越高，模式串向右滑动得越远，字符之间的相关度越高，模式串向右滑动得越远， 与主串进行比较的次数越少，时间复杂度就越好。与主串进行比较的次数越少，时间复杂度就越好。 模式匹配模式匹配KMP算法算法 4.1 字符串字符串 -1 j = 0 max k | 1kj 且且T0 Tk - -1 = Tj- -k Tj - 1 0 其它情况其它情况 nextj= 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 n 当当j=0时，时，nextj=-1； /nextj=-1表示不进行字符比较表示不进行字符比较 n 当当j0时，时，nextj的值为：模

35、式串的位置从的值为：模式串的位置从0到到j-1构构 成的串中所出现的首尾相同的子串的最大长度。成的串中所出现的首尾相同的子串的最大长度。 n 当无首尾相同的子串时当无首尾相同的子串时nextj的值为的值为0。 /nextj=0表示从模式串头部开始进行字符比较表示从模式串头部开始进行字符比较 计算计算nextj的方法：的方法： 模式匹配模式匹配KMP算法算法 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 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 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配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 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹配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 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 模式匹配模式匹

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 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 1. 在串在串S和串和串T中分别设比较的起始下标中分别设比较的起始下标i和和j； 2. 循环直到循环直到S或或T的所有字符均比较完的所有字符均比较完 2.1 如果如果Si=Tj，继续比较继续比较S和和T的下一个字

41、符；否则的下一个字符；否则 2.2 将将j向右滑动到向右滑动到nextj位置，即位置，即j=nextj； 2.3 如果如果j=-1，则将则将i和和j分别加分别加1，准备下一趟比较；，准备下一趟比较； 3. 如果如果T中所有字符均比较完毕，则返回匹配的起始下标；中所有字符均比较完毕，则返回匹配的起始下标； 否则返回否则返回0； KMP算法的伪代码描述算法的伪代码描述 4.1 字符串字符串 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 数组的定义数组的定义 数组是由一组数组是由一组类型相同类型相同的数据元素构成的的数据元素构成的有序有序集集 合合，每个数据元素称为一个数

42、组元素（简称为元每个数据元素称为一个数组元素（简称为元 素），每个元素受素），每个元素受n(n1)个个线性关系线性关系的约束，的约束，每每 个元素在个元素在n个线性关系中的序号个线性关系中的序号i1、i2、in称为称为 该元素的下标，并称该数组为该元素的下标，并称该数组为 n 维数组。维数组。 数组的特点数组的特点 元素本身可以具有某种结构，属于同一数据类型；元素本身可以具有某种结构，属于同一数据类型； 数组是一个具有固定格式和数量的数据集合。数组是一个具有固定格式和数量的数据集合。 4.2 多维数组多维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 a11 a

43、12 a1n a21 a22 a2n am1 am2 amn A= 例如，元素例如，元素a22受两个线性关系的约束，在行上有受两个线性关系的约束，在行上有 一个行前驱一个行前驱a21和一个行后继和一个行后继a23，在列上有一个列，在列上有一个列 前驱前驱a12和和一个列后继和和一个列后继a32。 4.2 多维数组多维数组 数组的定义数组的定义 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 a11 a12 a1n a21 a22 a2n am1 am2 amn A= A=(A1，A2，An) 其中：其中： Ai=(a1i，a2i，ami) (1in) 数组数组线性表的

44、推广线性表的推广 二维数组是数据元素为线性表的线性表。二维数组是数据元素为线性表的线性表。 4.2 多维数组多维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 数组的基本操作数组的基本操作 在数组中插入（或）一个元素有意义吗？在数组中插入（或）一个元素有意义吗？ a11 a12 a1n a21 a22 a2n am1 am2 amn A= 将元素将元素 x 插入插入 到数组中第到数组中第1行第行第2列。列。 x a11 a12 a1n a21 a22 a2n am1 am2 amn A= 删除数组中删除数组中 第第1行第行第2列元素。列元素。 4.2 多维数组多

45、维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 数组的基本操作数组的基本操作 存取：给定一组下标，读出对应的数组元素；存取：给定一组下标，读出对应的数组元素； 修改：给定一组下标，存储或修改与其相对应的修改：给定一组下标，存储或修改与其相对应的 数组元素。数组元素。 存取和修改操作本质上只对应一种操作存取和修改操作本质上只对应一种操作寻址寻址 数组应该采用何种方式存储？数组应该采用何种方式存储？ 数组没有插入和删除操作，所以，不用预留空间，数组没有插入和删除操作，所以，不用预留空间， 适合采用顺序存储。适合采用顺序存储。 4.2 多维数组多维数组 数据结构（数

46、据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 数组的存储结构与寻址数组的存储结构与寻址一维数组一维数组 设一维数组的下标的范围为闭区间设一维数组的下标的范围为闭区间l，h，每个每个 数组元素占用数组元素占用 c 个存储单元，则个存储单元，则其其任一元任一元素素 ai 的的 存储地址可由下式确定：存储地址可由下式确定： Loc(ai)Loc(al)(il)c c al ai-1 ai ah al+1 Loc(al)Loc(ai) 4.2 多维数组多维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 常用的映射方法有两种：常用的映射方法有两种： 按按行

47、行优先：优先：先行后列先行后列，先存储行号较小的元素，先存储行号较小的元素， 行号相同者先存储列号较小的元素。行号相同者先存储列号较小的元素。 按按列列优先：优先：先列后行先列后行，先存储列号较小的元素，先存储列号较小的元素， 列号相同者先存储行号较小的元素。列号相同者先存储行号较小的元素。 数组的存储结构与寻址数组的存储结构与寻址二维数组二维数组 二维数组二维数组内内 存存 二维结构二维结构一维结构一维结构 4.2 多维数组多维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 l2h2 l1 h1 (a) 二维数组二维数组 aij前面的元素个数前面的元素个数 =

48、阴影部分的面积阴影部分的面积 =整行数每行元素个数整行数每行元素个数+本行中本行中 aij前面的元素个数前面的元素个数 =( (i - -l1) )( (h2 - -l21) )( (j - -l2) ) 本行中本行中aij前面的元素个数前面的元素个数 每行元素个数每行元素个数 整整 行行 数数 aij 按行优先存储的寻址按行优先存储的寻址 4.2 多维数组多维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 第第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 按行优先存储的寻址按行优先存储的寻址 按列优先存储的寻址方法与此类似。按列优先存储的寻址方法与此类似。 4.2 多维数组多维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )c n（n2）维维 数组一般也采用数组一般也采用 按行优先和按列按行优先和按列 优先两种存储方优先两种存储方 法。法。请自行推导

50、请自行推导 任一元素存储地任一元素存储地 址的计算方法。址的计算方法。 数组的存储结构与寻址数组的存储结构与寻址多维数组多维数组 4.2 多维数组多维数组 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 4.3 矩阵的压缩存储矩阵的压缩存储 p 特殊矩阵：特殊矩阵：矩阵中很多值相同的元素并且它们的矩阵中很多值相同的元素并且它们的 分布有一定的规律。分布有一定的规律。 p 稀疏矩阵：稀疏矩阵：矩阵中有很多零元素。矩阵中有很多零元素。 p 压缩存储的基本思想是：压缩存储的基本思想是： 为多个值为多个值相同相同的元素只分配的元素只分配一个一个存储空间；存储空间； 对对零零元

51、素元素不分配不分配存储空间。存储空间。 特殊矩阵和稀疏矩阵特殊矩阵和稀疏矩阵 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵对称矩阵 36478 62842 48169 74605 82957 A 对称矩阵特点：对称矩阵特点：aij=aji 如何压缩存储？如何压缩存储？ 只存储下三角部分的元素。只存储下三角部分的元素。 4.3 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 (a) 下三角矩阵下三角矩阵 (b) 存储说明存储说明 (c) 计算方法计算方法 aij在一维

52、数组中的序号在一维数组中的序号 =阴影部分的面积阴影部分的面积 = i( (i+1) )/2+ j 一维数组下标从一维数组下标从0开始开始 aij在一维数组中的下标在一维数组中的下标 k= i( (i+1) )/2+ j-1 1 i n 1 j n aij 每行元素个数每行元素个数 1 2 i-1 aij在本行中的序号在本行中的序号 aij 第第1行行 第第2行行 第第i-1行行 对称矩阵的压缩存储对称矩阵的压缩存储 4.3 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 对于下三角中的元素对于下三角中的元素aij（ij），在数组，在数组

53、SA中的下标中的下标k 与与i、j的关系为：的关系为：ki(i1)/2j -1。 上三角中的元素上三角中的元素aij（ij），），因为因为aijaji，则访问和则访问和 它对应的元素它对应的元素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 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 特殊矩阵的压缩存储特

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 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系： i( (i1)

55、)/2j-1 当当ij n( (n1) )/2 当当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 存储存储 下三角下三角元素元素 对角线上方的常数对角线上方的常数只存一个只存一个 4.3 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 矩阵中任一元素矩阵中任一元素aij在在数组数组中的下标中的下标k与与i、j的对应关系：的对应关系： (i-1)(2n-i+2)/2+j-i 当当ij n

56、( (n1) ) /2 当当ij k= 上三角矩阵的压缩存储上三角矩阵的压缩存储 存储存储 上三角上三角元素元素 对角线上方的常数对角线上方的常数只存一个只存一个 4.3 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 特殊矩阵的压缩存储特殊矩阵的压缩存储对角矩阵对角矩阵 对角矩阵：对角矩阵：所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心 的带状区域中，除了主的带状区域中，除了主对角线和它的上下方若干条对对角线和它的上下方若干条对 角线的元素外，所有其他元素都为零。角线的元素外，所有其他元素都为零。 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 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 按行按行 存储存储 元素元素aij在一维数组中的序号在一维数组中的序号 =2 + 3( (i2) )+( ( ji + 2) ) =2i+ j -2 一维数组下标从一维数组下标从0开始开始 元素元素aij在一维数组中的下标在一维数组中的下标 = 2i+ j -3 (b) 寻址的计算方法寻址的计算方法 (c) 压缩到一维数组中压缩到一维数组中 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 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 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= 如何只存储非零元素？如何只存储非零元素？ 注意：稀疏矩阵中的非零元素的分布没有规律。注意：稀疏矩阵中的非零元素的分布没有规律。 4.3 矩阵的压缩存储矩阵的压缩存储 数据结构（数据结构（C+版）第版）第2版版 清华大学出版社清华大学出版社 template struct element int row, col; /行号，列号行号，列号 DataType item /非零元素值非零元素值 ; 将稀疏矩阵中的每个非零元素表示为将稀疏矩阵中的每个非零元素表示为： ( (行号，列号，非零元素值行号，列号，非零元素值) )三元组三元组