第5章-字符串和多维数组

数据结构与算法作者：胡明王红梅出版社：电子工业出版社邮箱：[e-mail]第5章字符串和多维数组本章的基本内容是：字符串。在程序设计语言中大都有串变量的概念，而且实现了基本的串操作，本章重点讨论串的存储结构及模式匹配算法。数组。在程序设计语言中大都提供了数组作为构造数据类型，本章重点讨论数组以及特殊矩阵的存储与寻址。线性表——具有相同类型的数据元素的有限序列。限制插入、删除位置栈——仅在表的一端进行插入和删除操作队列——在一端进行插入操作，而另一端进行删除操作第5章字符串和多维数组线性表——具有相同类型的数据元素的有限序列。将元素类型扩充为线性表（多维）数组——线性表中的数据元素可以是线性表将元素类型限制为字符串——零个或多个字符组成的有限序列第5章字符串和多维数组5.1引言假设纸牌的花色有梅花、方块、红桃和黑桃，纸牌的点数有2、3、4、5、6、7、8、9、10、J、Q、K、A，要求根据用户输入的纸牌张数n，随机发n张纸牌。在发纸牌问题的求解过程中，计算机如何保存纸牌的花色和点数，以及随机选中的纸牌呢？如何输出随机发出的n张纸牌呢？例5-1发纸牌5.1引言八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。八皇后问题首先要解决的问题就是如何表示棋盘？如何获得每个皇后的位置信息进而判断是否互相攻击？例5-2八皇后问题5.2字符串串的逻辑结构非空串通常记为：S=s1s2……sn其中：S是串名，双引号是定界符，双引号引起来的部分是串值，si（1≤i≤n）是一个任意字符。串：零个或多个字符组成的有限序列。串长度：串中所包含的字符个数。空串：长度为0的串，记为：。S1=ab12cdS2=ab12S3=ab13S4=ab12φS5=S6=φφφ串的逻辑结构子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。子串的位置：子串的第一个字符在主串中的序号。5.2字符串串的逻辑结构串的数据对象约束为某个字符集。微机上常用的字符集是标准ASCII码，由7位二进制数表示一个字符，总共可以表示128个字符。扩展ASCII码由8位二进制数表示一个字符，总共可以表示256个字符，足够表示英语和一些特殊符号，但无法满足国际需要。Unicode由16位二进制数表示一个字符，总共可以表示216个字符，能够表示世界上所有语言的所有字符，包括亚洲国家的表意字符。为了保持兼容性，Unicode字符集中的前256个字符与扩展ASCII码完全相同。5.2字符串串的比较：通过组成串的字符之间的比较来进行的。给定两个串：X=x1x2…xn和Y=y1y2…ym，则：1.当n=m且x1=y1，…，xn=ym时，称X=Y；2.当下列条件之一成立时，称X＜Y：⑴n＜m且xi=yi（1≤i≤n）；⑵存在k≤min(m,n)，使得xi=yi(1≤i≤k-1)且xk＜yk。串的逻辑结构例：S1=ab12cd，S2=ab12，S3=ab135.2字符串方案1：用一个变量来表示串的实际长度。如何表示串的长度？串的存储结构0123456……Max-1abcdefg9空闲5.2字符串方案1：用一个变量来表示串的实际长度。串的存储结构如何表示串的长度？01234567……Max-1abcdefg\0空闲方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。5.2字符串方案3：用数组的0号单元存放串的长度，从1号单元开始存放串值。串的存储结构如何表示串的长度？方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。方案1：用一个变量来表示串的实际长度。01234567……Max-19abcdefg空闲5.2字符串模式匹配模式匹配：给定主串S=s1s2…sn和模式T=t1t2…tm，在S中寻找T的过程称为模式匹配。如果匹配成功，返回T在S中的位置；如果匹配失败，返回0。⑴算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹配；⑵算法改进所取得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。模式匹配问题有什么特点？5.2字符串在下面的讨论中，为了和C++语言中的字符数组保持一致，采用第2种顺序存储方法，即从数组下标0开始存放字符，并且在串尾存储终结符'\0'。01234567……Max-1abcdefg\0空闲模式匹配5.2字符串基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，直到T中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。模式匹配——BF算法5.2字符串si……主串S模式Ttjji…模式匹配——BF算法回溯i回溯j5.2字符串si……主串S模式Tji模式匹配——BF算法…tj5.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbabi=2，j=2失败；i回溯到1，j回溯到0ij模式匹配——BF算法ijij第1趟abcac5.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbabj模式匹配——BF算法i第1趟abcaci=2，j=2失败；i回溯到1，j回溯到05.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbabi=1，j=0失败i回溯到2，j回溯到0模式匹配——BF算法第2趟ijabcac5.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbab模式匹配——BF算法第2趟ijabcaci=1，j=0失败i回溯到2，j回溯到05.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbababcaci=6，j=4失败i回溯到3，j回溯到0模式匹配——BF算法第3趟ijijijijij5.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbababcac模式匹配——BF算法第3趟iji=6，j=4失败i回溯到3，j回溯到05.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbababcaci=3，j=0失败i回溯到4，j回溯到0模式匹配——BF算法第4趟ij5.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbababcac模式匹配——BF算法第4趟iji=3，j=0失败i回溯到4，j回溯到05.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbababcaci=4，j=0失败i回溯到5，j回溯到0模式匹配——BF算法第5趟ij5.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbababcac模式匹配——BF算法第5趟iji=4，j=0失败i回溯到5，j回溯到05.2字符串例：主串S=ababcabcacbab，模式T=abcacababcabcacbababcaci=10，j=5，T中全部字符都比较完毕，匹配成功模式匹配——BF算法第6趟ijijijijij5.2字符串1.在串S和串T中设比较的起始下标i和j；2.循环直到S或T的所有字符均比较完2.1如果S[i]=T[j]，继续比较S和T的下一个字符；2.2否则，将i和j回溯，准备下一趟比较；3.如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0；模式匹配——BF算法5.2字符串intBF(charS[],charT[]){i=0;j=0;while(S[0]!='\0'&&T[0]!='\0'){if(S[i]==T[j]){i++;j++;}else{i=i-j+1;j=0;}}if(T[j]=='\0')return(i-j+1);elsereturn0;}模式匹配——BF算法intBF(charS[],charT[]){i=0;j=0;start=0;while(S[0]!='\0'&&T[0]!='\0'){if(S[i]==T[j]){i++;j++;}else{start++;i=start;j=0;}}if(T[j]=='\0')returnstart;elsereturn0;}5.2字符串模式匹配——BF算法设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：例如：S=aaaaaaaaaabcdcccccT=bcd最好情况：不成功的匹配都发生在串T的第1个字符。5.2字符串模式匹配——BF算法设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：最好情况：不成功的匹配都发生在串T的第1个字符。设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，则：)(2)()1(11mnOmnmipmnii+=+=+-´+-=5.2字符串模式匹配——BF算法设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：最坏情况：不成功的匹配都发生在串T的最后一个字符。例如：S=aaaaaaaaaaabcccccT=aaab5.2字符串模式匹配——BF算法设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：最坏情况：不成功的匹配都发生在串T的最后一个字符。设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此)(2)2()(11mnOmnmmipmnii=+-=+-=5.2字符串模式匹配——KMP算法为什么BF算法时间性能低？在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离。如何确定模式的滑动距离？5.2字符串i=2，j=2失败；s[1]=t[1];t[0]≠t[1]∴t[0]≠s[1]模式匹配——KMP算法ababcabcacbabij第1趟abcacababcabcacbab第2趟abcac5.2字符串i=2，j=2失败；s[1]=t[1];t[0]≠t[1]∴t[0]≠s[1]模式匹配——KMP算法ababcabcacbabij第1趟abcacababcabcacbababcac第3趟5.2字符串模式匹配——KMP算法ababcabcacbababcac第3趟iji=6，j=4失败s[3]=t[1];t[0]≠t[1]∴t[0]≠s[3]ababcabcacbababcac第4趟5.2字符串模式匹配——KMP算法ababcabcacbababcac第3趟iji=6，j=4失败s[4]=t[2];t[0]≠t[2]∴t[0]≠s[4]ababcabcacbababcac第5趟5.2字符串模式匹配——KMP算法ababcabcacbababcac第3趟ijababcabcacbababcac第6趟匹配成功5.2字符串需要讨论两个问题：①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？②模式应该向右滑多远才是最高效率的?结论：i可以不回溯，模式向右滑动到的新比较起点k，并且k仅与模式串T有关！模式匹配——KMP算法5.2字符串抓住部分匹配时的两个特征：设模式滑动到第k个字符（1）则T[0]~T[k-1]=S[i-k]~S[i-1]模式匹配——KMP算法ababcab……abcacijababcab……abcacij=k下一趟5.2字符串抓住部分匹配时的两个特征：设模式滑动到第k个字符（1）则T[0]~T[k-1]=S[i-k]~S[i-1]模式匹配——KMP算法ababcab……abcacijaba