国家级精品课程数据结构与算法.ppt

国家级精品课程国家级精品课程—《《数据结构与算法数据结构与算法》》张铭、赵海燕、王腾蛟、宋国杰、高军张铭、赵海燕、王腾蛟、宋国杰、高军 版权所有，转载或翻印必究版权所有，转载或翻印必究第第4 4章章 字符串字符串““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6主要内容主要内容n字符串基本概念字符串基本概念n字符串的存储结构字符串的存储结构n字符串运算的算法实现字符串运算的算法实现n字符串的模式匹配字符串的模式匹配““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串基本概念字符串基本概念 n字符编码字符编码n字符编码顺序字符编码顺序n字符串抽象数据类型字符串抽象数据类型““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6。

基本概念基本概念n字符串字符串，由，由0个或多个字符个或多个字符/符号的顺序排列所组成的复符号的顺序排列所组成的复合数据结构，简称合数据结构，简称“串串”（（string））q串的串的长度长度：一个字符串所包含的字符个数：一个字符串所包含的字符个数q空串空串：长度为零的串，它不包含任何字符内容：长度为零的串，它不包含任何字符内容n特殊的线性表，即元素为字符的线性表特殊的线性表，即元素为字符的线性表qn ( ≥ 0 ) 个字符的有限序列，一般记作个字符的有限序列，一般记作   S : “c0c1c2…cn-1”n  其中，其中，S是串名字是串名字n  “c0c1c2…cn-1”是串值是串值n  ci是串中的字符是串中的字符n  n是串的长度是串的长度 （即字符个数），长度为（即字符个数），长度为0则为空串则为空串““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符字符/符号符号n字符字符(char) ：组成字符串的基本单位：组成字符串的基本单位 n取值依赖于字符集取值依赖于字符集Σ（结点的有限集合）（结点的有限集合）q二进制字符集：二进制字符集：Σ = {0,1}q生物信息中生物信息中DNA字符集：字符集：Σ = {A,C,G,T} q英语语言：英语语言： Σ = {26个字符，标点符号，个字符，标点符号，…} q简体中文标准字符集简体中文标准字符集 GB2312 ：：Σ = {6763个汉字，个汉字，标点符号，标点符号，… }q……““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符编码字符编码nASCII编码编码q单字节（单字节（8 bits））q对对128个符号（字符集个符号（字符集charset）进行编码）进行编码 q在在C和和C++中均采用中均采用n其他编码方式其他编码方式qANSI编码（本地化，编码（本地化，GB2312、、BIG5、、JIS等，等，不同不同ANSI编码间互不兼容）编码间互不兼容）qUNICODE（国际化，各种语言中的每一个字符（国际化，各种语言中的每一个字符具有唯一的数字编号，便于跨平台的文本转换）具有唯一的数字编号，便于跨平台的文本转换）““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符的编码顺序字符的编码顺序 n为了字符串间比较和运算的便利，字符编码表一为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的般遵循约定俗成的“偏序编码规则偏序编码规则”n字符偏序字符偏序：根据字符的自然含义，某些字符间两：根据字符的自然含义，某些字符间两两可以比较次序两可以比较次序q字典序字典序q中文字符串有些特例，例如中文字符串有些特例，例如“笔划笔划”序序““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串长度字符串长度n理论上，一个字符串的长度是任意且有限的，理论上，一个字符串的长度是任意且有限的，但在实际的语言中总有一定的长度但在实际的语言中总有一定的长度q定长定长：具有一个固定的最大长度，所用内存量始终如：具有一个固定的最大长度，所用内存量始终如一一q变长变长：根据实际需要伸缩尽管命名为变长，但实际：根据实际需要伸缩尽管命名为变长，但实际长度也有限（取决于可用的内存量）长度也有限（取决于可用的内存量）““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6子串子串n假设假设s1，，s2 是两个串：是两个串：s1 = a0a1a2…an-1s2 = b0b1b2…bm-1其中其中0 ≤ m  ≤ n, 若存在整数若存在整数i (0 ≤ i  ≤n-m)，使得，使得bj = ai+j,  j = 0,1,…,m-1    同同时成立，成立，则称串称串s2是串是串s1的子串，或称的子串，或称s1包含串包含串s2q真子串：非空且不为自身的子串。

空串是任意串的子串真子串：非空且不为自身的子串空串是任意串的子串q任意串任意串S 都是都是S本身的子串本身的子串n子串函数子串函数q提取、插入、寻找、删除提取、插入、寻找、删除  …““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串数据类型字符串数据类型n因语言而不同因语言而不同q简单类型简单类型q复合类型复合类型n字符串常数和变量字符串常数和变量q字符串常数（字符串常数（string literal））n例如：例如： “\n”, “a”，，“student”…q字符串变量字符串变量““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++的标准的标准string n标准字符串：将标准字符串：将C/C++的的函数库作为函数库作为字符串数据类型的方案字符串数据类型的方案q例如：例如：char  S[M];定义了字符串变量定义了字符串变量    e.g.,  char s1[7] = “value”;n串的结束标记：串的结束标记：'\0'q‘\0’是是ASCII码中码中8位位BIT全全0码，又称为码，又称为NULL符，符， 专专门用于结束标志门用于结束标志q字符串的实际长度为字符串的实际长度为 M-1n注意注意：：  s1 = s2““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++标准标准stringn串长函数串长函数          int strlen(char  *s);n串复制串复制              char *strcpy(char  *s1, char*s2);n串拼接串拼接              char *strcat(char  *s1, char  *s2);n串比较串比较  (注意注意)  int  strcmp(char *s1, char *s2);n输入和输出函数输入和输出函数 cin>>       cout<

String抽象数据类型抽象数据类型n字符串类（字符串类（class String）：）：q适应字符串长度动态变化的复杂性适应字符串长度动态变化的复杂性q不再以字符数组不再以字符数组char S[M]的形式出现，而采用的形式出现，而采用一种动态变长的存储结构一种动态变长的存储结构““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++ String 部分操作列表部分操作列表 操作操作类别类别方法方法描述描述子串子串substr ()返回一个串的子串返回一个串的子串拷拷贝贝/交交换换swap ()交交换换两个串的内容两个串的内容copy ()将一个串拷将一个串拷贝贝到另一个串中到另一个串中赋值赋值assign ()把一个串、一个字符、一个子串把一个串、一个字符、一个子串赋值给赋值给另一个串中另一个串中=把一个串或一个字符把一个串或一个字符赋值给赋值给另一个串中另一个串中插入插入/追加追加insert()在在给给定位置插入一个字符、多个字符或串定位置插入一个字符、多个字符或串+=将一个字符或串追加到另一个串后将一个字符或串追加到另一个串后append ()将一个或多个字符、或串追加在另一个串后将一个或多个字符、或串追加在另一个串后拼接拼接+通通过过将一个串放置在另一个串后面来构建新串将一个串放置在另一个串后面来构建新串查询查询find ()找到并返回一个子序列的开始位置找到并返回一个子序列的开始位置替替换换/清除清除replace ()替替换换一个指定字符或一个串的字串一个指定字符或一个串的字串clear ()清除串中的所有字符清除串中的所有字符统计统计size ()返回串中字符的数目返回串中字符的数目length ()返回返回size ()max_size ()返回串允返回串允许许的最大的最大长长度度““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串的存储结构和实现字符串的存储结构和实现n字符串的顺序存储字符串的顺序存储n字符串类字符串类class String的存储结构的存储结构nC++标准串的运算实现标准串的运算实现nString类的运算实现类的运算实现““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串的顺序存储字符串的顺序存储n对于串长变化不大的字符串，可以有三种处理方案：对于串长变化不大的字符串，可以有三种处理方案：（（1）用）用S[0]作为记录串长的存储单元作为记录串长的存储单元 ( Pascal)  q缺点：限制了串的最大长度不能超过缺点：限制了串的最大长度不能超过256（（2）为存储串的长度，另辟一个存储的地方）为存储串的长度，另辟一个存储的地方q缺点：串的最大长度一般是静态给定的，不是动态申请数组空缺点：串的最大长度一般是静态给定的，不是动态申请数组空间间（（3）用一个特殊的末尾标记）用一个特殊的末尾标记'\0‘  ( C/C++) q例如：例如：C++语言的语言的string函数库（＃函数库（＃include ）采用）采用这一存储结构这一存储结构““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串类字符串类class String的存储结构的存储结构 private:  // 具体实现的字符串存储结构具体实现的字符串存储结构     char *str;// 字符串的数据表示字符串的数据表示     int size;// 串的当前长度串的当前长度例如，例如，String s1 = "Hello";““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串运算的算法实现字符串运算的算法实现1.  串长函数串长函数          int strlen(char  *s);2.  串复制串复制          char *strcpy(char  *d, char*s);3．串拼接．串拼接            char *strcat(char  *s1, char  *s2);4．串比较．串比较            int  strcmp(char *s1, char *s2);5.   寻找字符寻找字符 char * strchr(char *d, char ch)char * strrchr(char *d, char ch)““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++标准串运算的实现标准串运算的实现// 字符串的复制char *strcpy(char *d, char *s) {     int i =0;    while (s[i] != '\0')   {      d[i] = s[i];   i++;    }    d[i] = '\0';    return d;}// 问题问题？？““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++标准串运算的实现标准串运算的实现// 字符串的比较 int strcmp(const char *s1, const char *s2) {int i = 0;while (s2[i] != '\0'  &&  s1[i] != '\0' ) {if (s1[i] > s2[i])return 1;else if (s1[i] < s2[i])return -1;i++;}if (s1[i] == '\0' && s2[i] != '\0')return -1;else if s2[i] == '\0' && s1[i] != '\0')return 1;return 0;}““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++标准串运算的实现标准串运算的实现// 求字符串的长度int strlen(char d[ ]) {   int i =0;   while (d[i] != 0)        i++;   return i;}““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++标准串运算的实现标准串运算的实现//寻找字符char * strchr(char *d , char ch) {      // 按照数组指针按照数组指针d依次寻找字符依次寻找字符ch，如果找到，如果找到ch，则将指针位置返回，，则将指针位置返回，     // 如果没有找到如果没有找到ch，则为，则为0值值     i = 0;    // 循环跳过那些不是循环跳过那些不是ch的字符的字符    while (d[i] != 0 && d[i] != ch )   i++;     // 当本串不含字符当本串不含字符ch，则在串尾结束；成功寻找到，则在串尾结束；成功寻找到ch，返回该位置指针，返回该位置指针   if (d[i] == 0)       return  0;    else        return  &d[i] ;} ““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++标准串运算的实现标准串运算的实现// 反向寻找字符char * strrchr(char *d , char ch) {    // 按照数组指针按照数组指针d，从其尾部反着寻找字符，从其尾部反着寻找字符ch，如果找到，则将指针位置返回，，如果找到，则将指针位置返回，   // 如果没有找到，则为如果没有找到，则为0值    i = 0; while (d[i] != '\0' )                           // 找串尾找串尾i++;  // 循环跳过那些不是循环跳过那些不是ch的字符的字符  while (d[--i] != '\0' && d[i] != ch )  ;  // 当本串不含字符当本串不含字符ch，则在串尾结束，则在串尾结束; 当成功寻找到当成功寻找到ch，返回该位置指针，返回该位置指针  if (d[i] = = '\0')     return  0;   else       return  &d[i] ; }““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6C++标准标准stringe.g,  字符串字符串s ：：寻找字符寻找字符o，，strchr(s,’o’)结果返回结果返回4；；反方向寻找反方向寻找r，， strrchr(s,’o’)结果返回结果返回7Helolwrol\0d01243568791110S strchr(s,’o’)strrchr(s, ’o’) ““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6String串运算的实现串运算的实现// 创建算子(constructor)String::String(char *s)  {     // 先要确定新创字符串实际需要的存储空间，先要确定新创字符串实际需要的存储空间，s的类型为的类型为(char *)，，     // 作为新创字符串的初值确定作为新创字符串的初值确定s的长度，用标准字符串函数的长度，用标准字符串函数 //strlen(s)计算长度计算长度     size = strlen(s) ;           // 然后，在动态存储区域开辟一块空间，用于存储初值然后，在动态存储区域开辟一块空间，用于存储初值s，把结束，把结束     // 字符也包括进来字符也包括进来     str ＝＝ new  char [size＋＋1];     // 开辟空间不成功时，运行异常，退出开辟空间不成功时，运行异常，退出     assert(str != '\0');     // 用标准字符串函数用标准字符串函数strcpy，将，将s完全复制到指针完全复制到指针str所指的存储空间所指的存储空间    strcpy(str, s);}““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6String串的创建运算串的创建运算private:char *s;int size;   //值为值为5…….Helol\0012435s1String  s1 = "Hello" ;““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6String串运算的实现串运算的实现// 析构函数String::~String() {   // 必须释放动态存储空间必须释放动态存储空间   delete [] str;}““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6String串运算的实现串运算的实现// 赋值算子赋值算子String  String::operator= (String&  s) {      // 参数参数 s 将被赋值到本串。

将被赋值到本串 若本串的串长和若本串的串长和s的串长不同，则应该释放本串的的串长不同，则应该释放本串的   // str存储空间，并开辟新的空间存储空间，并开辟新的空间   if (size != s.size)  {      delete [] str ;  // 释放原存储空间释放原存储空间      str = new char [s.size+1];      // 若开辟动态存储空间失败，则退出正常运行若开辟动态存储空间失败，则退出正常运行      assert(str != 0)；；      size = s.size;   }   strcpy(str , s.str );   // 返回本实例，作为返回本实例，作为String类的一个实例类的一个实例   return  *this;}  ““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6String的赋值运算的赋值运算String s2 = "Hello world";并通过赋值语句：并通过赋值语句：s1 = s2;private:char *str;int size;   // 值为值为 11…….Helol\0012435s1private:char *str;int size;   // 值为值为11 …….s2Helolwrol\0d01243568791110Helolwrol\0d01243568791110““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6String串运算的实现串运算的实现// 抽取子串函数 String String::Substr(int index , int count ) {     // 取出一个子串返回，自下标取出一个子串返回，自下标index开始，长度为开始，长度为count           int i;     // 本串自下标本串自下标index开始向右数直到串尾，长度为开始向右数直到串尾，长度为left     int  left = size – index ;      String temp;     char  *p, *q;     // 若下标若下标index值太大，超过本串实际串长，则返回空串值太大，超过本串实际串长，则返回空串     if (index >= size)        return temp;     // 若若count超过自超过自index以右的实际子串长度，则把以右的实际子串长度，则把count变小变小    if (count > left )        count = left;    // 释放原来的存储空间释放原来的存储空间    delete [] temp.str;    ““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6String串运算的实现串运算的实现 //  若开辟动态存储空间失败，则退出若开辟动态存储空间失败，则退出       temp.str = new char [count+1];            assert(temp.str != 0)；；       // p的内容是一个指针，指向目前暂无内容的字符数组的首字符处的内容是一个指针，指向目前暂无内容的字符数组的首字符处       p = temp.str;          // q的内容是一个指针，指向本实例串的的内容是一个指针，指向本实例串的str数组的下标数组的下标index字符字符       q = &str[index];       // 用用q指针取出它所指的字符内容后，指针加指针取出它所指的字符内容后，指针加1      // 用用p该指针所指的字符单元接受拷贝，该指针也加该指针所指的字符单元接受拷贝，该指针也加1      for (i =0; i < count;  i++)            *p++  =  *q++;      // 循环结束后，让循环结束后，让temp.str的结尾为的结尾为’\0’      *p = 0;       temp.size = count;     return temp;}““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6String抽取子串抽取子串s2 = s1.Substr(6, 5) ;private:char *str;int size;   // 值为值为11 …….s1Helolwrol\0d01243568791110private:char *str;int size;   // 值为值为 5…….s2wordl\001243568791110““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串模式匹配字符串模式匹配n模式匹配模式匹配(pattern matching)q一个目标对象一个目标对象T（字符串）（字符串）q一个模式（一个模式（pattern））P（字符串）（字符串）在目标在目标T中寻找一个给定的模式中寻找一个给定的模式P的过程的过程 n应用应用q文本编辑时的特定词、句的查找文本编辑时的特定词、句的查找qDNA信息的提取信息的提取q确认是否具有某种结构确认是否具有某种结构q …““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6模式匹配目标模式匹配目标n在大文本（诸如，句子、段落，或书本）中定位在大文本（诸如，句子、段落，或书本）中定位（查找）特定的模式（查找）特定的模式q对于大多数的算法而言，匹配的主要考虑在于其速对于大多数的算法而言，匹配的主要考虑在于其速度和效率度和效率q有相当数目的算法用于解决模式匹配问题，将介绍有相当数目的算法用于解决模式匹配问题，将介绍朴素朴素(Brute Force)、、 Knuth-Morris-Pratt (KMP) 算法算法““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串模式匹配字符串模式匹配n精确匹配（精确匹配（Exact String Matching）：一种结果或成或败）：一种结果或成或败的匹配，即，若在目标的匹配，即，若在目标T中至少一处存在模式中至少一处存在模式P，则称为匹配，则称为匹配成功，否则即使目标与模式只有一个字符不同也不能称为匹成功，否则即使目标与模式只有一个字符不同也不能称为匹配成功，亦即匹配失败配成功，亦即匹配失败q单选的，单选的，”Set” ；；q多选的，模式多选的，模式” S?t” q正则表达式表示的模式正则表达式表示的模式n近似匹配（近似匹配（Approximate String Matching）：）： 如果模式如果模式P与目标与目标T（或其子串）存在某种程度的相似，则认为匹配成（或其子串）存在某种程度的相似，则认为匹配成功。

功q常用的衡量字符串相似度的方法是根据一个串转换成另常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的基本操作数目来确定基本操作由字符串一个串所需的基本操作数目来确定基本操作由字符串的插入、删除和替换三种操作来组成的插入、删除和替换三种操作来组成““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串模式匹配字符串模式匹配n模式单选精确匹配模式单选精确匹配q用给定的模式用给定的模式P，在目标字符串，在目标字符串T中搜索与模式中搜索与模式P全同的全同的一个子串，并求出一个子串，并求出T中第一个和中第一个和P全同匹配的子串（简称全同匹配的子串（简称为为“配串配串”），返回其首字符位置），返回其首字符位置T T0 T1 …  TiTi+1  Ti+2  …   Ti+m-2   Ti+m-1 … Tn-1                  ‖‖      ‖            ‖     ‖ P              p0 p1     p2     …  pm -2 pm-1为使模式为使模式为使模式为使模式   P P 与目标与目标与目标与目标   T T 匹配，必须满足匹配，必须满足匹配，必须满足匹配，必须满足 p0 p1 p2 …pm-1  = Ti Ti+1 Ti+2 … Ti+m-1““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6单模式匹配算法单模式匹配算法AlgorithmPreprocessing timeMatching timeNaïve string search algorithm0 (no preprocessing)Θ(nm)Rabin-Karp string search algorithmΘ(m)average (n+m),worstΘ(nm)Finite automatonΘ(m |Σ|)Θ(n)Knuth-Morris-Pratt algorithmΘ(m)Θ(n)Boyer-Moore string search algorithmΘ(m)average (n/m),worst Θ(n)Bitap algorithm (shift-or, shift-and, Baeza-Yates-Gonnet)Θ(m + |Σ|)Θ(n)Shift Or AlgorithmΘ(m + |Σ|)Θ(n)““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材。

张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素模式匹配（穷举法）朴素模式匹配（穷举法）n 设设T= T0T1, T2, …,Tn，，P = p1, p2, …, pmqj为指向为指向T中字符的下标指针，中字符的下标指针，i为指向为指向P中字符的下标中字符的下标指针指针q匹配成功匹配成功 (p1 = Tj , p2 = Tj+1 , …,  pm = Tj+m-1 )n 即，即，substr(T, j, m)q匹配失败匹配失败  (pi ≠ Tj) 时，时，n  将将P右移再行比较右移再行比较q尝试所有的可能情况尝试所有的可能情况““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素模式匹配：朴素模式匹配：示例示例l把模式与目标逐一进行比较（首位置开始），直到碰到不匹配的字符把模式与目标逐一进行比较（首位置开始），直到碰到不匹配的字符为止（模式右移一位再次开始匹配）为止（模式右移一位再次开始匹配）l算法可在算法可在第一个匹配第一个匹配或是或是目标的结束目标的结束处停止处停止abacababacababacaacabcabacabaa01234587691011121314151617abacababacababacababacab…………abacab““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素匹配算法朴素匹配算法#include “String.h” #include int NaiveStrMatching (String T, String P) { int i = 0;// 模式的下标变量int j = 0;// 目标的下标变量nt pLen = P.length( ); // 模式的长度int tLen = T.length( );// 目标的长度if (tLen < pLen) // 如果目标比模式短，匹配无法成功return (-1); while ( i < pLen && j < tLen) // 反复比较对应字符来开始匹配 if (T[j] == P[i]) i++, j++;else { j = j – i + 1; i = 0;}if ( i > = pLen)return (j – pLen+1);else return (-1); }““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素匹配算法朴素匹配算法：效率分：效率分析析n假定目标假定目标T的长度为的长度为n，模式，模式P长度为长度为m，且，且 m ≤ n q在最坏的情况下，每一次循环都不成功，则一在最坏的情况下，每一次循环都不成功，则一共要进行比较（共要进行比较（n-m+1）次）次q每一次每一次“相同匹配相同匹配”比较所耗费的时间，是比较所耗费的时间，是P和和T逐个字符比较的时间，最坏情况下，共逐个字符比较的时间，最坏情况下，共m次次q因此，整个算法的最坏时间开销估计为因此，整个算法的最坏时间开销估计为O(mn)““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素匹配算法朴素匹配算法：：最差情况最差情况n模式与目标的每一个长度为模式与目标的每一个长度为m的子串进行比较的子串进行比较l目标形如目标形如an, 模模式形如式形如am-1bl总比较次数：总比较次数：O(n-m+1)l时间复杂度：时间复杂度：O(mn)AAAAAAAAAAAAAAAAAAAAAAAAAAB 5次比较AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比较AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比较AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比较…………AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比较““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素模式匹配算法：朴素模式匹配算法：最佳情况最佳情况--找到模式找到模式n在目标的前在目标的前m个位置上找到模式，设个位置上找到模式，设 m = 5l总比较次数：总比较次数：ml时间复杂度：时间复杂度：O(m)AAAAAAAAAAAAAAAAAAAAABAAAAA            5次比较次比较 ““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素匹配算法：朴素匹配算法：最佳情况最佳情况-没找到模式没找到模式n总是在第一个字符上不匹配总是在第一个字符上不匹配l总比较次数：总比较次数：n-m+1l时间复杂度：时间复杂度：O(n)AAAAAAAAAAAAAAAAAAAAAHOOOOH 1次比较AAAAAAAAAAAAAAAAAAAAAH OOOOH 1次比较AAAAAAAAAAAAAAAAAAAAAHOOOOH 1次比较AAAAAAAAAAAAAAAAAAAAAH OOOOH 1次比较…………AAAAAAAAAAAAAAAAAAAAAH 1次比较 OOOOH““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素匹配算法的问题朴素匹配算法的问题““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6朴素算法的问题：回溯朴素算法的问题：回溯n朴素算法之所以效率不高的原因朴素算法之所以效率不高的原因在于匹配过程中目标串有回溯，在于匹配过程中目标串有回溯，且这些回溯并非必要且这些回溯并非必要ne.g., q由由1）可知：）可知： P5   T5，， P0=T0, P1 = T1,,同时由同时由 P0  P1可得知可得知P0 T1  故将故将 P 右右移一位后第移一位后第2）趟比较一定不等）趟比较一定不等;  比较比较冗余冗余q那么把那么把P右移几位合适？右移几位合适？ 既能消除冗余既能消除冗余比较又保证不丢失配串呢？比较又保证不丢失配串呢？T    a b a c a a b a c c a b a c a b a aP    a b a c a b   1））P5   T5  P右移一位右移一位T   a b a c a a b a c c a b a c a b a aP  a b a c a b   2））P0   T1  P右移一位右移一位T  a b a c a a b a c c a b a c a b a aP      a b a c a b   3））P1   T3  P右移一位右移一位T  a b a c a a b a c c a b a c a b a aP         a b a c a b…….““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6无回溯匹配算法无回溯匹配算法n关键关键在于匹配过程中，一旦在于匹配过程中，一旦Pi 和和Tj比较不等时，即比较不等时，即   substr(P,1,i-1) = substr(T, j-i+1,i-1) 且且Pi   Tj    要能立即确定右移的位数和继续比较的字符，即该用要能立即确定右移的位数和继续比较的字符，即该用P中的中的哪个字符和哪个字符和Tj进行比较？进行比较？  如何定位如何定位?   保留之前比较的结果保留之前比较的结果? 若把这个字符记为若把这个字符记为Pk，显然有，显然有k

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6KMP算法思想算法思想T T0 T1 … Ti-j-1 Ti-j  Ti-j+1  Ti-j+2  …  Ti-2-2  Ti-1   Ti … Tn-1                       ‖    ‖      ‖         ‖  ‖        P                   p0    p1     p2     …   pj-2-2  pj -1 pj   则有则有则有则有       Ti-j Ti-j+1 Ti-j+2 … Ti-1 = p0 p1 p2 …pj-1                      (1) 如果如果如果如果      p0 p1 …pj-2    p1 p2 …pj-1               (2)   则立刻可以断定则立刻可以断定则立刻可以断定则立刻可以断定          p0 p1 …pj-2    Ti-j+1 Ti-j+2 … Ti-1 (朴素匹配的朴素匹配的)下一趟一定不匹配，可以跳过去，也即模式右下一趟一定不匹配，可以跳过去，也即模式右移一位后依然不匹配移一位后依然不匹配““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6KMP算法思想算法思想同样，若同样，若 p0 p1 …pj-3   p2 p3 …pj-1则模式右移则模式右移2位也不匹配，因为有位也不匹配，因为有 p0 p1 …pj-3   Ti-j+2 Ti-j+3 … Ti-1直到对于某一个直到对于某一个直到对于某一个直到对于某一个“ “k” ”值，使得值，使得值，使得值，使得 p0 p1 …pk   pj-k-1 pj-k …pj-1 且且且且 p0 p1 …pk-1 = pj-k pj-k+1 …pj-1则则则则 p0 p1 …pk-1 = Ti-k Ti-k+1 … Ti-1 Ti ‖ ‖ ‖     pj-k pj-k+1 … pj-1 pj ‖ ‖ ‖ ？？ p0 p1 … pk-1 pk 模式右移模式右移j-k位位““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6KMP算法的关键：算法的关键：模式本身模式本身模式右移模式右移模式右移模式右移j-kj-k位位位位 Ti-j Ti-j+1 Ti-j+2 … Ti-k Ti-k+1 … Ti-1 Ti ‖ ‖ ‖ ‖ ‖ ‖     p0   p1      p2          …     pj-k   pj-k+1   …  pj-1 pj ‖ ‖ ‖     p0 p1 … pk-1 pk特征向量特征向量关键关键：对每个：对每个pj，如何求，如何求k值值 ？？？？““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6。

字符串特征向量字符串特征向量n设模板设模板P由由m个字符组成，记为个字符组成，记为P  =  p0 p1p2p3…pm-1n令令特征向量特征向量 N 用来表示模板用来表示模板 P 的字符分布特的字符分布特征，简称征，简称N向量向量q和和P同长，由同长，由m个特征数个特征数n0 …nm-1整数组成，记为整数组成，记为         N ＝＝ n0n1n2n3…nm-1      N在很多文献中也称为在很多文献中也称为next数组，每个数组，每个nj对应对应 next数数组中的元素组中的元素next[j]““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串的特征向量字符串的特征向量n模式模式 P 的的前缀子串前缀子串（（首串首串））qP的前的前t 个字符：个字符： p0p1p2…pt-1  n模式模式P 的的左子串左子串（（尾串尾串））q在在P的第的第 j 位置之前的位置之前的 t 个字符，称为个字符，称为 j位置的左子位置的左子串：串： pj-t... pj-2pj-1n模式模式P第第 j 个位置的特征数个位置的特征数njq最长的（最长的（t 最大的）能够与前缀子串匹配的最大的）能够与前缀子串匹配的左子串（简称左子串（简称第第 j 位的最长前缀串位的最长前缀串））q t 即即pj的特征数的特征数nj““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6字符串特征向量的定义字符串特征向量的定义n特征数特征数nj+1 ( 0≤ nj+1 ≤ j)的递归定义如下：的递归定义如下：1.如果如果j == 0 , 令令n0 = -1；对于；对于nj+1 ，假定已知前一位置的特征数，假定已知前一位置的特征数 nj = k；；2.如果如果j > 0，，k ≥ 0 且且 Pj = Pk ，则，则nj+1 = k+1；；3.当当k ≥ 0, 且且P j ≠ Pk 时，则令时，则令k = nk，并让，并让 步骤步骤3循环直到条件不满循环直到条件不满足（变为足（变为P j == Pk 或或 k == -1）；）；4.当当 k<0 (此时，此时，k ＝＝ -1), 则则 nj＋＋1= 0““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6对应的求特征向量算法框架n在在KMP快速模式匹配中，若用快速模式匹配中，若用ni表示第表示第i位的特征位的特征值，特征数值，特征数ni +1( -1 ≤ ni  < i )可以采用如下定义：可以采用如下定义：q1.  n0 ＝＝ -1；对于；对于i > 0的的ni+1，假定已知前一位置没有优，假定已知前一位置没有优化以前的特征数化以前的特征数 ni = k；；q2. 当当k > =0，且，且Pi ≠ Pk 时，则令时，则令k = nk，并让步骤，并让步骤2循环循环直到条件不满足（变为直到条件不满足（变为Pi = =Pk ，或上一步骤，或上一步骤k == 0而导而导致致k = nk步骤后步骤后k == -1了）；了）；q3. ni+1 = k+1（这是没有优化以前的特征数，在优化前传（这是没有优化以前的特征数，在优化前传到第一步用于计算下一个特征值）；到第一步用于计算下一个特征值）；q4. 若若Pi+1 = =Pk+1 ，则，则n’i+1 = nk+1（此步骤为优化）。

此步骤为优化）一般把模式的第一个字符的特征数设置为一般把模式的第一个字符的特征数设置为-1，以尽可能地减少，以尽可能地减少冗余比较：冗余比较： ““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6特征向量的计算特征向量的计算1.求求p0, p1,…,pj-1 中最大相同的前缀与后缀的中最大相同的前缀与后缀的长度长度t2.next[j] = t计算计算next[j]时充分利用了位置时充分利用了位置j之前的各个字符之前的各个字符的的next值值““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6特征向量的计算特征向量的计算int *findNext(String P) {            // 计算向量计算向量N     int m = P.length();                //  m为模板为模板P的长度的长度     assert( m > 0);             //  若若m＝＝0，退出，退出     int *next = new  int[m];       //  动态存储区开辟整数数组动态存储区开辟整数数组     assert( next != 0);              // 若开辟存储区域失败，退出若开辟存储区域失败，退出     next[0] = -1;int i = 0; int k = -1; while (i < m-1) { while (j >= 0 && P [i] != P[k])  k= next[k];i++; k++;next[i] = k;}     return next;}i012345PjabacabNj-100101““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6特征向量的计算：特征向量的计算：优化版优化版?当当 j = 0时，时，令令next[j] = -1其实，若其实，若Pk = Pj ，，则有则有pk     Tj；此时；此时应再右移，使应再右移，使 Pnext[k]与与 Tj 比较，故比较，故 第第2步可进一步优化为：步可进一步优化为：  if  (Pk == Pj)  next[j] = next[k];   else   next[j] = k;j012345PjabacabNj-10-11-10““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6特征向量的计算：特征向量的计算：优化版优化版int *findNext(String P) {int i = 0; int k = -1; int m = P.length();    // m为字符串为字符串P的长度的长度  assert(m > 0);     // 若若m＝＝0，退出，退出  int *next = new int[m];  // 动态存储区开辟整数数组动态存储区开辟整数数组assert(next != 0);   // 若开辟存储区域失败，退出若开辟存储区域失败，退出  next[0] = -1;while (i < m-1) { // 计算计算i=1..m-1的的next值值while (k >= 0 && P[i] != P[k])  // 求最大首尾子串求最大首尾子串k = next[k];i++;  k++;if (P[i] == P[k] ) next[i] = next[k];//  P[i]和和P[k]相等，优化相等，优化else next[i] = k;// 不需要优化，就是位置不需要优化，就是位置i的首尾子串长度的首尾子串长度}return next;}““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6特征向量计算示例特征向量计算示例iknext[]P-->0-1{-1}abacab-->10{-1,0}abacab--1-->20{-1,0,-1}abacab-->31{-1,0,-1,1}abacab-1-->40{-1,0,-1,1,-1}abacab-->51{-1,0,-1,1,-1,0}abacab0abacab““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6KMP模式匹配算法模式匹配算法int KMPStrMatching(String T, String P,  int *N) {int i = 0;// 模式的下标变量模式的下标变量int j = 0;// 目标的下标变量目标的下标变量int pLen = P. length ( );             // 模式的长度模式的长度int tLen = T.length( );// 目标的长度目标的长度if (tLen < pLen) // 如果目标比模式短，匹配无法成功如果目标比模式短，匹配无法成功return (-1);          while ( i < pLen  &&  j < tLen)  {  // 反复比较对应字符来开始匹配反复比较对应字符来开始匹配   if ( i == -1  ||  T[j] == P[i]) i++,  j++;else i = N[i];}if ( i > = pLen)return (j – pLen);else return (-1); }““十一五十一五””国家级规划教材。

张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6KMP模式匹配：示例模式匹配：示例abacaacabcabacabaaabacab123456abacab7abacab14151617181910100-1NjbacabaPj543210jabacab8910 11 12abacab13““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6KMP模式匹配：示例模式匹配：示例abacaacabcabacabaaabacabj012345PjabacabNj-10-11-10123456abacab7 89 10 11abacab12 13 14 15 16 17““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6KMP算法的效率分析算法的效率分析n主要代价体现在主要代价体现在whilewhile循环语句循环语句q循环最多执行循环最多执行 n = T.length() 次次q由于循环体中由于循环体中j j只增不减的特性，语句只增不减的特性，语句j++; j++; 最多最多执行执行n n 次；故次；故i++;i++;语句也最多执行语句也最多执行n n 次次qi i超值为超值为0 0，使之减少的语句只有，使之减少的语句只有““i = i = N[iN[i];];””q由于由于 i < i < N[iN[i], ], ““i = i = N[iN[i];];””; ; ””每执行一次每执行一次必然使得必然使得i i减少减少( (至少减至少减1)1)q故，若故，若 ““i = i = N[iN[i]]; ]]; ””的执行次数不超过的执行次数不超过n n次。

次n故，故，KMP算法的时间为Ｏ算法的时间为Ｏ(n)n同理，求同理，求N数组的时间为数组的时间为O(m)““十一五十一五””国家级规划教材张铭，王腾蛟，赵海燕，国家级规划教材张铭，王腾蛟，赵海燕，《《数据结构与算法数据结构与算法》》，高教社，，高教社，2008.2008. 6 6小小 结结n字符串抽象数据类型字符串抽象数据类型n字符串的存储结构和类定义字符串的存储结构和类定义n字符串运算的算法实现字符串运算的算法实现n字符串的模式匹配字符串的模式匹配课程和教材参考信息课程和教材参考信息课程和教材参考信息课程和教材参考信息国家级精品课程国家级精品课程—《《数据结构与算法数据结构与算法》》张铭、赵海燕、王腾蛟、宋国杰、高军张铭、赵海燕、王腾蛟、宋国杰、高军 6本章主笔：赵海燕赵海燕 版权所有，转载或翻印必究版权所有，转载或翻印必究。