1、第四章第四章 串与数组串与数组第四章第四章 串与数组串与数组4.1 串的基本概念串的基本概念 4.2 串的存储结构串的存储结构 4.3 顺序串的实现顺序串的实现 4.4 串的模式匹配操作串的模式匹配操作 4.5 串的应用举例串的应用举例 4.6 数组的概念及顺序存储结构数组的概念及顺序存储结构 4.7 特殊矩阵的压缩存储特殊矩阵的压缩存储 4.8 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 第四章第四章 串与数组串与数组重点：重点：u掌握串类型定义中各基掌握串类型定义中各基本操作的定义以及本操作的定义以及串中基本操作的应用。串中基本操作的应用。u掌握数组的定义、操作和存储结构掌握数组的定义、操作和存
2、储结构难点：难点：u串的基本操作的应用，即如何运用串串的基本操作的应用，即如何运用串的基本操作来实现其它串的复杂操作。的基本操作来实现其它串的复杂操作。u矩阵的压缩存储。矩阵的压缩存储。4.1串的基本概念串的基本概念1 1、串：串：是由是由零个零个或或多个多个字符组成的有限序列。字符组成的有限序列。一般记为一般记为s=s=a a0 0a a1 1a an-1 n-1,其中其中s s为为串名串名，双引号括起来的字符序列是，双引号括起来的字符序列是串值串值。2 2、串的长度：串的长度：串中串中字符的个数字符的个数。3 3、空串：空串：长度为长度为0 0的串，即不包含任何字符的的串，即不包含任何字符
3、的串，表示为串，表示为。4 4、空白串：空白串：由一个或多个空白字符组成的串，由一个或多个空白字符组成的串，如：如：。注意：注意：空串与空白串的区别空串与空白串的区别串也是一种特殊的线性表。串也是一种特殊的线性表。4.1.1 4.1.1 串的基本概念串的基本概念4.1串的基本概念串的基本概念5 5、子串：子串：主串：主串：串中任意个串中任意个连续字符连续字符组成的组成的子子序序列称为该串的子串。列称为该串的子串。包含子串的串相应地称为包含子串的串相应地称为主主串。串。6 6、字符在串中的位置：字符在串中的位置：子串在主串中的位置：子串在主串中的位置：如：如：s1=s1=cdababefcdab
4、abef,s2=,s2=abab字符在串中的序号值。字符在串中的序号值。子串在主串中第一次子串在主串中第一次出现时的第一个字符在主串中的序号值。出现时的第一个字符在主串中的序号值。注意：注意：空串是任意串的子串空串是任意串的子串,任意串是其自任意串是其自 身的子串。身的子串。4.1.1 4.1.1 串的基本概念串的基本概念4.1串的基本概念串的基本概念7 7、两个串相等：两个串相等：长度相等长度相等各个字符对应相等各个字符对应相等串值相等串值相等4.1.1 4.1.1 串的基本概念串的基本概念4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 cle
5、ar()1 1）串的置空操作：）串的置空操作：isEmpty()2 2）串的判空操作：）串的判空操作：length()3 3）求串的长度操作：）求串的长度操作：4 4）取字符元素操作：）取字符元素操作：5 5）截取子串操作：）截取子串操作：charAT(index)substring(bengin,end)6 6）插入操作：）插入操作：insert(offset,str)4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 delete(begin,end )7 7）删除操作：）删除操作：concat(str)8 8）串的连接操作：）串的连接操作：co
6、mpareTo(str )9 9）串的比较操作：）串的比较操作：1010）子串定位操作：）子串定位操作：indexOf(str,begin)4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述charAT(index)读取并返回串中的第读取并返回串中的第indexindex个字符值个字符值,其中其中:0:0indexindexlength()-1length()-1 例如例如:当前串为当前串为abcdefg charAT(0)=?acharAT(3)=?dcharAT(6)=?g4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数据类型描述
7、串的抽象数据类型描述substring(bengin,end)截取当前串中从序号截取当前串中从序号beginbegin开始开始,到序号到序号end-1end-1为止的子串并返回其值为止的子串并返回其值,其中其中:0beginlength()-1,1 1endendlength()length()例如例如:当前串为当前串为commander substring(3,6)=?man substring(0,9)=?commander substring(8,9)=?r substring(3,10)=?substring(9,1)=?4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数
8、据类型描述串的抽象数据类型描述 将串将串strstr插入到当前串中的第插入到当前串中的第offsetoffset个字个字符的前面符的前面,并返回操作结果。其中并返回操作结果。其中:0offsetlength()例如例如:当前串为当前串为chater,则则insert(3,rac）=?character insert(offset,str)insert(0,rac)=?racchater insert(6,rac)=?chaterrac 4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述delete(bengin,end)删除当前串中从序号删除当前串中
9、从序号beginbegin开始开始,到序号到序号end-1end-1为止的子串为止的子串,并返回操作结果。其中并返回操作结果。其中:0beginlength()-1,1 1endendlength()length()例如例如:当前串为当前串为commanderdelete(3,6)=?comder delete(0,9)=?delete(8,9)=?commande delete(3,10)=?delete(9,1)=?4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 concat(str)将串将串strstr连接在当前串的后面，连接在当前串的后面
10、，并返回其值。并返回其值。例如例如:当前串为当前串为man,则则concat(kind)=?mankind 4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述 compareTo(str)将当前串与目标串将当前串与目标串strstr进行比较进行比较,若若:当前串当前串 str str，则返回值，则返回值 0 0；当前串当前串 str str，则返回值，则返回值 0 0；当前串当前串 strstr，则返回值，则返回值 0 0。例如例如:当前串为当前串为 cat compareTo(case)?0 compareTo(cate)?0compareTo(c
11、ht )?0 4.1串的基本概念串的基本概念4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述indexOf(str,begin)在当前串中从在当前串中从beginbegin位置开始去找与位置开始去找与非空串非空串strstr相等的子串相等的子串,若查找成功则返回在当前串中的位置若查找成功则返回在当前串中的位置,否则返回否则返回-1,-1,其中其中:0beginlength()-1 例如例如:当前串为当前串为 bcaabcaaabc,str=,str=bca indexOf(str,0)=?0indexOf(str,2)=?4indexOf(str,6)=?-14.1串的基本概念
12、串的基本概念public interface IString public void clear();public boolean isEmpty();public int length();public char charAt(int index);public IString substring(int begin,int end);public IString insert(int offset,IString str);4.1.2 4.1.2 串的抽象数据类型描述串的抽象数据类型描述4.1串的基本概念串的基本概念 串串的逻辑结构和的逻辑结构和线性表线性表极为相似，极为相似，区别区别仅在
13、于仅在于串的数据对象约束为字符集串的数据对象约束为字符集。但串的基本操作和线性表有很大差别但串的基本操作和线性表有很大差别:在线性表的基本操作中，大多以大多以“单个元素单个元素”作为操作对象作为操作对象；在串的基本操作中，通常以通常以“串的串的整体整体”作为操作对象作为操作对象。4.2串的存储结构串的存储结构4.2.1 4.2.1 串的顺序存储结构串的顺序存储结构 串的顺序存储结构与线性表的顺序存储结串的顺序存储结构与线性表的顺序存储结构类似，可以采用一组地址连续的存储单元构类似，可以采用一组地址连续的存储单元来存储串字符序列。顺序存储的串称为来存储串字符序列。顺序存储的串称为顺序顺序串，顺序
14、串的类型描述如下串，顺序串的类型描述如下:public class SeqString implements IString private char strvalue;/存放串值存放串值 private int curlen;/存放串的长度存放串的长度 4.2串的存储结构串的存储结构 其中：其中：strvaluestrvalue是一个字符数组，数组是一个字符数组，数组容量是容量是1111，该数组中存放字符串，该数组中存放字符串“I am a I am a dogdog，串的实际长度，串的实际长度curlencurlen的值是的值是1010。4.2.1 4.2.1 串的顺序存储结构串的顺序存储
15、结构 4.2串的存储结构串的存储结构4.2.2 4.2.2 串的链式存储结构串的链式存储结构 串的链式存储结构和线性表的链式存储结串的链式存储结构和线性表的链式存储结构类似，可以构类似，可以采用单链表来存储串值采用单链表来存储串值，串的，串的这种链式存储结构称为链串。如下图这种链式存储结构称为链串。如下图:4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements ISring private char strValue;private int curLe
16、n;public SqStack()/构造一个空串构造一个空串 /以字符串常量构造串对象以字符串常量构造串对象 public SqStack(String str)stingValue=new char0;curLen=0;char tempchararray=str.toCharArray();strValue=tempchararray;curLen=tempchararray.length;4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements
17、ISring public SqStack(char value)/以字符数组构造串对象以字符数组构造串对象 this.strValue=new charvalue.length;for(int i=0;i value.length;i+)/复制数组复制数组 this.strValuei=valuei;curLen=value.length;public void clear()/顺序串的置空函数顺序串的置空函数 curLen=0;4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class Seq
18、String implements ISring return curLen;/判判空函数空函数public boolean isEmpty()/求顺序串长度函数求顺序串长度函数 public int length()/返回顺序串中第返回顺序串中第indexindex个字符个字符 public char charAt(int index)return curLen=0;if(index=curLen)throw new StringIndexOutofBoundsException(index);return strValuei;4.3顺序串的实现顺序串的实现4.3.1 4.3.1 顺序串的类
19、定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements ISring /扩充字符串的存储容量，参数指定容量扩充字符串的存储容量，参数指定容量 public void allocate(int newCapacity)char temp=srtValue;strValue=new charnewCapacity;for(int i=0;itemp.length;i+)strValuei=tempi;/截子串操作截子串操作public IString subString(int begin,int end)4.3顺序串
20、的实现顺序串的实现4.3.1 4.3.1 顺序串的类定义顺序串的类定义（见教材（见教材P113-115P113-115）public class SeqString implements ISring /串的插入操作串的插入操作public IString insert(int offset,IString str)/串的删除操作串的删除操作public IString delete(int begin,int end)/串的比较操作串的比较操作public int compareTo(IString str)/子串的定位操作子串的定位操作 public int indexOf(IString
21、 str,int begin)4.3顺序串的实现顺序串的实现4.3.2 4.3.2 串的基本操作实现串的基本操作实现1.截子串操作截子串操作 subString(begin,end)的实现（的实现（P115/算法算法 4.1)a.a.检测参数检测参数beginbegin和和end end 是否合法是否合法 if(if(begin0begincurLenendcurLen|beginbegin=endend)抛出异常抛出异常 返回当前串中序号从返回当前串中序号从beginbegin至至end-1end-1的子的子串。起始下标串。起始下标beginbegin的范围是：的范围是：0beginleng
22、th()-10beginlength()-1；结束下标；结束下标endend的范的范围是：围是：1endlength()1endlength()。4.3顺序串的实现顺序串的实现char buffer=new charend-begin;for(int i=0;i buffer.length;i+)/复制子串复制子串 bufferi=this.strvaluei+begin;return new SeqString(buffer);if(begin=0&end=curLen)return this;else b.b.若要截取整个串，则返回原串；若要截取整个串，则返回原串；否则返回截取从否则返回截
23、取从beginbegin到到end-1end-1之间的子串之间的子串 1.截子串操作截子串操作 subString(begin,end)的实现（的实现（P115/算法算法 4.1)4.3顺序串的实现顺序串的实现char buffer=new charend-begin;for(int i=0;i 0|endend)throw new StringIndexOutOfBoundsException(参数不合法);4.3顺序串的实现顺序串的实现4.3.2 4.3.2 串的基本操作实现串的基本操作实现2.串的插入操作串的插入操作 insert(offset,str)的实现（的实现（P116/算法算法
24、 4.2)在当前串中第在当前串中第offsetoffset个字符之前插入串个字符之前插入串strstr，并返回结果串对象并返回结果串对象。其中：参数。其中：参数offsetoffset的有效范围是：的有效范围是：0offsetlength()0offsetlength()。当当offset=0offset=0，表示在当前串的，表示在当前串的开始处开始处插插入串入串strstr；当；当offset=length()offset=length()，表示在当前，表示在当前串的串的结尾处结尾处插入串插入串strstr。4.3顺序串的实现顺序串的实现a.a.检测参数的合法性检测参数的合法性 2.串的插入
25、操作串的插入操作 insert(offset,str)的实现（的实现（P116/算法算法 4.2)if(if(offset0offsetcurLenoffsetcurLen)抛出异常抛出异常b.b.判断空间是足够判断空间是足够:如果不足如果不足,则扩充空间则扩充空间,否则否则转转c cint len=str.length();/str串的长度串的长度int newcount=this.curLen+len;/插入后串的长度插入后串的长度if(newcountstrValue.length)allocate(newcount);c.c.后移：后移：将将strvaluestrvalue中从中从of
26、fsetoffset开始的所有字符开始的所有字符向后移动向后移动lenlen个位置个位置 （注意：要从后往前移动）（注意：要从后往前移动）for(int i=this.curLen-1;i=offset;i-)strValuei+len=strValuei;4.3顺序串的实现顺序串的实现d.d.插入：插入：将串将串strstr插入到指定的位置插入到指定的位置（用字符（用字符复制的方法）复制的方法）2.串的插入操作串的插入操作 insert(offset,str)的实现（的实现（P116/算法算法 4.2)for(int i=0;i len;i+)strValue offset+i=str.ch
27、arAt(i);e.e.修正串长修正串长this.curLen=newcount;4.3顺序串的实现顺序串的实现 public Istring insert(int offset,ISting str)/算法4.2结束if(offset this.curlen)throw new StringIndexOutOfBoundsException(“插入位置不合法);2.串的插入操作串的插入操作 insert(offset,str)的实现（的实现（P116/算法算法 4.2)int int len=str.length();/str串的长度串的长度int newcount=this.curLen+
28、len;/插入后串的长度插入后串的长度if(newcountstrValue.length)allocate(newcount);for(int i=this.curLen-1;i=offset;i-)/后移后移 strValuelen+i=strvaluei;for(int i=0;i len;i+)/插入插入 strValue offset+i=str.charAt(i);this.curLen=newcount;/修正串长修正串长return this;4.3顺序串的实现顺序串的实现4.3.2 4.3.2 串的基本操作实现串的基本操作实现3.串的删除操作串的删除操作 delete(beg
29、in,end)的实现（的实现（P117/算法算法 4.3)在当前串中删除从在当前串中删除从beginbegin到到end-1end-1之间的之间的子串，并返回当前串对象。子串，并返回当前串对象。参数参数beginbegin和和endend的取值范围分别是：的取值范围分别是：0beginlength()-1 0beginlength()-1 1endlength()1endlength()。4.3顺序串的实现顺序串的实现a.a.检测参数的合法性检测参数的合法性 3.串的删除操作串的删除操作 delete(begin,end)的实现（的实现（P117/算法算法 4.3)b.b.前移：前移：将将st
30、rvaluestrvalue中从中从endend开始到串尾的子串开始到串尾的子串 向前移动到从向前移动到从beginbegin开始的位置开始的位置for(int i=0;i curlen-end;i+)strValue begin+i =strValue end+i;if(if(begin0begincurLenendcurLen|beginbegin=endend)抛出异常抛出异常c.c.修正串长修正串长this.curLen=curLen-(end-begin);4.3顺序串的实现顺序串的实现 public Istring delete(int begin,int end)/算法4.3结束
31、if(begincurLen|beginend)throw new StringIndexOutOfBoundsException(“参数位置不合法);for(int i=0;i curlen-end;i+)strValue begin+i =strValue end+i;this.curLen=curLen-(end-begin);return this;3.串的删除操作串的删除操作 delete(begin,end)的实现（的实现（P117/算法算法 4.3)4.3顺序串的实现顺序串的实现4.3.2 4.3.2 串的基本操作实现串的基本操作实现4.串的比较操作串的比较操作 compareT
32、o(str)的实现（的实现（P117/算法算法 4.4)将当前串与目标串将当前串与目标串strstr进行比较进行比较,若若:当前串当前串 str str，则返回值，则返回值 0 0；当前串当前串 str str，则返回值，则返回值 0 0；当前串当前串 strstr，则返回值，则返回值 0 0。4.3顺序串的实现顺序串的实现a.a.求当前串长度和求当前串长度和strstr串长度的最小值并赋给串长度的最小值并赋给n n 3.串的比较操作串的比较操作 compareTo(str)的实现（的实现（P117/算法算法 4.4)b.b.从下标从下标0 0到到n-1n-1依次取出两个串中对应的字符进依次取
33、出两个串中对应的字符进 行比较，若不等，则返回第一个不相等的字符行比较，若不等，则返回第一个不相等的字符 的数值差。的数值差。for(int i=0;i n;i+)if(strValuei!=str.strValusei)return strValuei-str.strValusei;int len1=this.curlen;int len2=str.curlen;int n=Math.min(len1,len2);4.3顺序串的实现顺序串的实现3.串的比较操作串的比较操作 compareTo(str)的实现（的实现（P117/算法算法 4.4)c.c.若下标从若下标从0 0到到n-1n-1对
34、应的字符均相等，则返对应的字符均相等，则返 回两个串长度的差。回两个串长度的差。return len1-len2;4.3顺序串的实现顺序串的实现 public int comparTo(IString str)/算法4.4结束3.串的比较操作串的比较操作 compareTo(str)的实现（的实现（P117/算法算法 4.4)int len1=curlen;int len2=str.curlen;int n=Math.min(len1,len2);for(int i=0;i n;i+)if(strValuei!=str.strValusei)return strValuei-str.strVa
35、lusei;return len1-len2;4.3顺序串的实现顺序串的实现1.子串的定位操作子串的定位操作 indexOf(str,beging)的实现（补充）的实现（补充）在当前串中从在当前串中从beginbegin位置开始去找位置开始去找与与非空串非空串strstr相等的子串相等的子串,若查找成功则若查找成功则返回在当前串中的位置返回在当前串中的位置,否则返回否则返回-1,-1,其其中中:0beginlength()-1补充：补充：串的基本操作的应用串的基本操作的应用4.3顺序串的实现顺序串的实现1.子串的定位操作子串的定位操作 indexOf(str,begin)的实现（补充）的实现（
36、补充）可利用可利用串比较串比较、求串长和截子串等操、求串长和截子串等操作实现子串的定位操作作实现子串的定位操作indexOf(str,begin)。compareTo(substring(begin,begin+str.length()?0 this串 str 串串 str串串ibeginthis.legth()-str.length()+1 4.3顺序串的实现顺序串的实现1.子串的定位操作子串的定位操作 indexOf(str,begin)的实现（补充）的实现（补充）public int indexOf(IString Str,int bgein)while(i=0)return-1;/S中
37、不存在与T相等的子串4.3顺序串的实现顺序串的实现2.串的置换操作串的置换操作 replace(begin,s1,s2)的实现（补充）的实现（补充）在当前对象串在当前对象串this中，从下标中，从下标begin开始，将所有的开始，将所有的s1非空子串替换为非空子串替换为s2非空非空串。串。例如：例如：假设假设 this=abcaabcaaabca ，s1=bca 若若 s2=x ，则经置换后得到则经置换后得到 this=若若 s2=bc ，则经置换后得到则经置换后得到 S=axaxaax abcabcaabc 4.3顺序串的实现顺序串的实现 2.串的置换操作串的置换操作 replace(beg
38、in,s1,s2)的实现（补充）的实现（补充）source串 s1 串 s2 串 s2 串begin=index+s1.length()sub1indexss串串(初始是一个空串）初始是一个空串）sub2beginsource串串（初始为（初始为this串）串）4.3顺序串的实现顺序串的实现2.串的置换操作串的置换操作 replace(begin,s1,s2)的实现（补充）的实现（补充）P148/习题三中的第习题三中的第2题，题，作为学生课后作业完成。作为学生课后作业完成。4.4串的模式匹配操作串的模式匹配操作 这是串的一种重要操作，很多 软件，若有“编辑编辑”菜单项的话，则其中必有“查找查找
39、”子菜单项。4.4 串的模式匹配操作串的模式匹配操作4.4串的模式匹配操作串的模式匹配操作操作条件：当前串操作条件：当前串this和和t串存在，串存在，t是非空是非空 串，串，0 start S.Length()-1。操作结果：操作结果：若串若串this中存在和串中存在和串t值相值相 同的子串返回它在同的子串返回它在this中中 第第start个字符之后第一次出个字符之后第一次出 现现的位置；否则函数的位置；否则函数 值为值为0。首先，回忆一下首先，回忆一下串匹配串匹配(查找查找)的定义的定义:index(t,start)4.4 串的模式匹配操作串的模式匹配操作4.4串的模式匹配操作串的模式匹
40、配操作一、模式匹配的概念一、模式匹配的概念1 1、什么叫、什么叫模式匹配模式匹配 设设s,t s,t 是两个串，是两个串，s=s=s s0 0s s1 1s sn-1n-1,t=,t=t t0 0t t1 1t tm-1m-1(0mn)(0m=S.length()i=S.length()或或j=T.length(),j=T.length(),若若j=T.length()j=T.length()则匹配成功，则匹配成功，函数返回函数返回T T串在串在S S串串startstart位置之后首次出现的位位置之后首次出现的位序号值序号值,否则匹配失败否则匹配失败,函数返回函数返回-1-1。4.4 串的模
41、式匹配操作串的模式匹配操作-简单算法（带回溯）简单算法（带回溯）4.4串的模式匹配操作串的模式匹配操作int IndexOf(IString t,int start)/返回子串返回子串t在主串（当前串在主串（当前串this）中第）中第start个字符之个字符之后的位置。若不存在，后的位置。若不存在，则函数值为则函数值为-1。其中，。其中，t非空，非空，0startS.Length()-1。/算法4.5 结束2 2）算法：算法：int i=start,j=0,slen=this.length(),tlen=t.length();while (islen&j=tlen)return i-tlen;
42、else return-1;时间复杂度：时间复杂度：O(slenO(slen*tlen)tlen)4.4 串的模式匹配操作串的模式匹配操作-简单算法（带回溯）简单算法（带回溯）4.4串的模式匹配操作串的模式匹配操作算法算法4.54.5模拟演示模拟演示 因为在最坏情况下，对因为在最坏情况下，对i i的每的每个值，个值，j+j+需执行需执行n-1n-1次。次。动画动画4-3-24.4 串的模式匹配操作串的模式匹配操作-简单算法（带回溯）简单算法（带回溯）4.4串的模式匹配操作串的模式匹配操作 你能否举出一个使算法你能否举出一个使算法4.54.5运行处运行处最坏情况的例子？最坏情况的例子？例如例如：
43、S=aaaaaaaaaaab，T=aaab，start=0 需要执行需要执行 36 36 次对应位的比较次对应位的比较才匹配成功。才匹配成功。4.4 串的模式匹配操作串的模式匹配操作-简单算法（带回溯）简单算法（带回溯）4.4串的模式匹配操作串的模式匹配操作存在问题：存在问题：当当 Si Tj 时，时，已经得到的结果：已经得到的结果：Si-j+1.i-1=T1.j-1 若已知若已知 T1.k-1=Tj-k+1.j-1 则有则有 Si-k+1.i-1=T1.k-1所以只需将模式向右滑动至模式中第所以只需将模式向右滑动至模式中第k k个字符与个字符与主串中第主串中第i i个字符对齐。个字符对齐。如
44、：如：S=“ababcabcacbab”与与T=“abcac”的匹配过程的匹配过程动画动画4-3-34.4 串的模式匹配操作串的模式匹配操作-简单算法（带回溯）简单算法（带回溯）4.4串的模式匹配操作串的模式匹配操作KMP算法的时间复杂度可以达到 O(s.length()+t.length()模式匹配的一种改进算法模式匹配的一种改进算法KMPKMP算法算法(D.E.Knuth,J.H.Morris,V.R.Pratt)见见 P124/算法4.84.4 串的模式匹配操作串的模式匹配操作-KMP算法算法4.4串的模式匹配操作串的模式匹配操作定义：定义：模式串的next函数 模式串中，每一个模式串中
45、，每一个tjtj都有一个都有一个k k值对应，这值对应，这个个k k值仅与模式串本身有关，而与主串值仅与模式串本身有关，而与主串s s无关。无关。一般用一般用nextjnextj函数来表示函数来表示tjtj对应的对应的k k值。值。)(0 tt ttt）(jk0|maxk)0j(1-j1-jk-j1-k10其它情况且集合非空时时当next4.4 串的模式匹配操作串的模式匹配操作-KMP算法算法4.4串的模式匹配操作串的模式匹配操作由定义可推出下列模式串的由定义可推出下列模式串的nextnext函数值：函数值：j 0 1 2 3 4 5 模式串模式串 a b c a b cNextj-1 0 0
46、 0 1 24.4 串的模式匹配操作串的模式匹配操作-KMP算法算法4.4串的模式匹配操作串的模式匹配操作由定义可推出下列模式串的由定义可推出下列模式串的nextnext函数值：函数值：j 0 1 2 3 4 5 6模式串模式串 a b a b a a aNextj-1 0 0 1 2 314.4 串的模式匹配操作串的模式匹配操作-KMP算法算法4.4串的模式匹配操作串的模式匹配操作 int index_KMP(IString t,int start)/0startthis.length()-1 int next=getNext(T);/计算模式串的next函数值 int i=start,j=
47、0;while(i this.length()&j t.length)if(j=-1|this.charAti=t.charAtj)+i;+j;/继续比较后继字符 else j=nextj;/模式串向右移动 if(j=j)K=j*(j+1)/2+i (i=j,0i,jn-1)K=空空 (id的的aij不不 存存储。储。n(2d+1)-d(d+1)(其中其中d称为称为半带宽半带宽，2d+1称为称为带宽带宽）4.7.3 对角矩阵的压缩存储对角矩阵的压缩存储 1.空间分配空间分配：非零元素个数：非零元素个数：?n(2d+1）空间分配数：空间分配数：?4.7特殊矩阵的压缩存储特殊矩阵的压缩存储 2.地
48、址公式地址公式：假设以一维数组假设以一维数组S n(2d+1)作为作为n阶对阶对角矩阵角矩阵A的存储结构的存储结构存储形式如下：存储形式如下：4.7.3 对角矩阵的压缩存储对角矩阵的压缩存储 例如，例如，n=544433433322322211211100100000000000000aaaaaaaaaaaaaA书中有误书中有误P1354.7特殊矩阵的压缩存储特殊矩阵的压缩存储 若若a ij 存储到存储到Sk中，则中，则k 与与i,j 对应关对应关系为系为:i*(2d+1)+d+(j-i)K=其中：其中：K=0n(2d+1)i,j=0n-14.7.3 对角矩阵的压缩存储对角矩阵的压缩存储 所以
49、：特殊矩阵中数组元素的地址计算所以：特殊矩阵中数组元素的地址计算公式为：公式为：Loc(i,j)=Loc(0,0)+K*L其中其中L为每个数据元素所占的存储单元为每个数据元素所占的存储单元个数。个数。4.8稀疏矩阵的压缩存储稀疏矩阵的压缩存储 假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子稀疏因子。通常认为通常认为 0.05 的矩阵为稀疏矩阵且的矩阵为稀疏矩阵且零值元素分布是随机的。零值元素分布是随机的。nmt何谓稀疏矩阵？何谓稀疏矩阵？4.8 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 有较多零元素且非零元素分布无规律的矩阵为。4.8稀疏矩阵的压缩存储稀疏矩阵的压缩存储 以常规方法
50、，即以二维数组表示以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间零值元素占了很大空间;2)计算中进行了很多和零值的运算，计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。遇除法，还需判别除数是否为零。即计算效率不高。即计算效率不高。4.8 稀疏矩阵的压缩存储稀疏矩阵的压缩存储4.8稀疏矩阵的压缩存储稀疏矩阵的压缩存储1)尽可能少存或不存零值元素；尽可能少存或不存零值元素；2)尽可能减少没有实际意义的运算；尽可能减少没有实际意义的运算；3)操作方便。操作方便。即：能尽可能快地找到与下标值即：能尽可能快地找到与下标值(i，j)对
