1,第四章 串,开始学习本讲前要知道：,从数据结构角度看，串也属于线性结构，具有线性结构的共同特征； 学习本章时，要注意到串所具有的线性结构的共性，更要掌握其个性； 串的特殊性主要是：串的元素是字符； 本讲具体内容见本章目录本章目录,4.1串类型的定义 4.2串的表示和实现 4.2.1 串的顺序存储结构 4.2.2 串的链式存储结构 4.3 串的模式匹配 4.3.1 朴素的模式匹配算法 4.3.2 KMP算法 4.4 串的应用举例 *4.5 算法设计举例,知识点和难点重点,知识点 基本概念 串操作 模式匹配 难点重点 根据给定操作，编写其它操作的算法 (如，根据前5个基本操作，编写index,replace操作 KMP算法 模式串的next和nextval函数值 手工模拟KMP算法的执行过程 串的其它算法5,4.1 串的基本概念及其操作,4.1.1 串的基本概念 串是由n（n≥0）个字符组成的有限序列表示为 s= “a0a1a2…an-1” 长度为零的串称为空串 由一个或多个空格组成的串称为空格串 由串中任意连续字符组成的子序列称为子串，而包含子串的串称为该子串的主串 单个字符在字符串中的序号称为该字符在串中的位置，而子串的第一个字符在主串中的位置称为子串的位置。
若两个串的长度相等且对应位置上的字符也相等，则称两个串相等6,4.1.1 串的基本概念,例如，四个字符串 S1=φ S2=“ ” S3=“Data Structure” S4=“Struct” 与线性表相比串有其特殊性： 串的数据元素只能是字符类型； 串以子串为操作单位自测题 1,下面关于串的的叙述中，哪一个是不正确的？ A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储,自测题 2,串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？ A. 数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储,自测题 3,串的长度是指（ ） 【北京工商大学 2001 一.6 （3分）】 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数,自测题 4,设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。
【中科院计算所 1997 】 A．2n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F. 其他情况,11,4.1.2 串的抽象数据类型,12,4.2 串的顺序存储结构,4.2.1 串的定长顺序存储表示 采用静态内存分配方式，分配一组地址连续的存储单元，用来存放串的字符序列 串的定长顺序存储表示用C语言描述： #define STRSIZE 100 typedef struct{ char ch[STRSIZE]; int length; }SqString;,13,4.2.1 串的定长顺序存储表示,（1）初始化串 int InitString(SqString *S,char *str){ int i, len=0; char *c=str; while(*c!='\0'){len++;c++;} /*求str的长度*/ S-length = len; /*置串的当前长度值*/ for(i = 0; i length; i++) /*赋值串值*/ S-ch[i] = str[i]; return 1; },14,4.2.1 串的定长顺序存储表示,（2）串插入 操作步骤： 判断指定的插入位置是否合法。
根据串长决定是否作截断处理： 若插入后的串长小于STRSIZE，则正常插入； 若插入后的串长大于STRSIZE，且串T可以全部插入，则主串S被部分截断； 否则串T和串S都要被部分截断 插入位置后的所有字符依次后移子串的长度 插入子串 修改串长域15,4.2.1 串的定长顺序存储表示,int StrInsert(SqString *S,int pos,SqString T){ int i; if(posS-length){ printf(“插入位置不合法，其取值范围应该是[0,length]“); return 0;} /*插入后串长小于等于STRSIZE，则正常插入*/ if (S-length + T.lengthlength-1; i=pos-1; i--) S-ch[i+T.length]=S-ch[i]; for(i=0; ich[i+pos]=T.ch[i];/*插入*/ S-length+=T.length; /*设置串长*/ },16,4.2.1 串的定长顺序存储表示,/*串长大于STRSIZE，则串T全部插入，串S部分截断*/ else if(T.length+posT.length+pos-1;i--) S-ch[i]=S-ch[i-T.length];/*插入位置后字符后移*/ for (i=0;ich[i+pos]=T.ch[i]; /*插入*/ S-length=STRSIZE; } /*串长大于STRSIZE,并且串T部分也要被截断*/ else{ for (i=0;ich[i+pos]=T.ch[i]; S-length=STRSIZE; } return 1;},17,4.2.1 串的定长顺序存储表示,（3）串删除 操作步骤： 判断所删串是否为空串。
判断指定的删除位置及删除长度是否合法 删除位置后的所有字符依次前移子串的长度 修改串长域18,4.2.1 串的定长顺序存储表示,int StrDelete(SqString *S,int pos,int len){ int i; if(S-lengthS-length){ printf(“删除位置及删除长度不合法！“); return 0; } /*当删除长度超过串长度，则只删到串尾即可*/ if(pos+lenS-length) len=S-length-pos+1; for(i=pos+len;ilength;i++)/*前移，删除*/ S-ch[i-len]=S-ch[i]; S-length-=len; /*改变串长*/ return 1; },19,4.2.1 串的定长顺序存储表示,（4）求子串 int SubStr(SqString S,int pos,int len,SqString *T){ int i; if(S.lengthS.length){ printf(“子串位置及子串长度不合法！“);return 0; } /*当子串长度超过主串长度，则只取到串尾即可*/ if(pos+lenS.length) len=S.length-pos+1; for(i=0;ich[i]=S.ch[i+pos]; T-length=len; return 1; },20,4.2.1 串的定长顺序存储表示,（5）串连接 必须考虑串截断的问题： 若串连接后，串的长度小于串的最大长度，则把T串连接到S串的尾部； 若串连接后，串的长度大于串的最大长度但S串小于串的最大长度，则对T串超出部分进行截断，截断后连接到S串的尾部； 若S串等于串的最大长度，则T串全部被截断，不做连接操作。
21,4.2.1 串的定长顺序存储表示,int Concat(SqString *S,SqString T){ int i; /* 串的长度小于串的最大长度*/ if(S-length+T.lengthch[i+S-length]=T.ch[i]; S-length+=T.length;} /*串的长度大于串的最大长度但S串小于串的最大长度*/ else if(S-lengthlength;ich[i]=T.ch[i-S-length]; S-length=STRSIZE; } return 1; },22,4.2.1 串的定长顺序存储表示,【例4-2】已知串S=“String”和串T=“ Operation”，请用串的基本操作（不包括连接算法）实现连接串S和串T的算法 int concat(SqString *s,SqString t){ StrInsert(s,s-length,t);/*使用算法4-2在S串的尾部插入串T*/ return 1; },写出一个递归算法来实现字符串逆序存储 【中科院研究生院2004四(7分)】 void InvertStore(char A[]) //字符串逆序存储的递归算法。
{char ch; static int i = 0; scanf (“%c“, //字符串结尾标记 }//结束算法,算法举例:字符串逆序存储,24,4.2.2 串的堆存储表示,采用动态内存分配方式，分配一组地址连续的存储单元，用来存放串的字符序列 C语言描述： typedef struct{ char *ch; int length; }SqVString;,堆存贮表示采用动态申请内存方法，就意味着可以随时扩展存贮空间，因而不存在截断串的问题25,4.2.2 串的堆存储表示,（2）串插入 操作步骤： 判断指定的插入位置是否合法若不合法，则算法结束 重新分配串的存储空间，使之有足够空间容纳被插入的子串 插入位置后的所有字符依次后移子串的长度 插入子串 修改串长域26,4.2.2 串的堆存储表示,int StrInsert(SqVString *S,int pos,SqVString T){ int i,len; if(posS-length){ printf(“插入位置不合法，取值范围[0,length]“);return 0;} len=S-length+T.length; /*计算插入后的串长*/ S-ch=(char*)realloc(S-ch,len*sizeof(char)); if(!S-ch){printf(“分配空间出错“);return 0;} for(i=S-length-1;i=pos;i--)/*腾出插入子串的空间*/ S-ch[i+T.length]=S-ch[i]; for(i=0; ich[i+pos]=T.ch[i]; S-length=len; return 1;},27,4.2.2 串的堆存储表示,（3）串删除 操作步骤： 判断所删串是否为空串。
判断指定的删除位置及删除长度是否合法 为临时串分配空间 把删除位置前的所有字符复制到临时串 把被删串的后半部分复制到临时串 释放原有串 把临时串作为删除后的串28,4.2.2 串的堆存储表示,int StrDelete(SqVString *S,int pos,int len){ int i,size; char *str; if(posS-length || S-lengthlength-len; if(sizech[i]; for(i=pos+len;ilength;i++) str[i-len]=S-ch[i]; free(S-ch); S-length=size; S-ch=str; return 1; },29,4.2.2 串的堆存储表示,【例4-3】设计一个串替换算法在串S中，将第pos个字符开始的len个字符构成的子串用串T替换 int StrReplace(SqVString *S,int pos,int len,SqVString T){ int i,size; char *str; if(posS-length || pos+len-1S-length){ printf(“参数不合法！“); return 0; } size=S-length-len+T.length; /。