《数据结构》课件-第4章 串

数据构C语言描述结第4章

串知识目标：熟悉串的十种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法理解串的堆存储结构以及在其上实现串操作的基本方法理解串的链式存储结构理解串的朴素模式匹配算法（BF算法）技能目标：能应用串的各种基本操作和模式匹配算法解决实际问题第4章串4.1串的逻辑结构4.2串的存储结构4.3串的模式匹配4.0案例导引4.4案例实现——文本文件中单词的检索和计数4.0案例导引案例：文本文件单词的检索和计数编程建立一个文本文件，每个单词都不包含空格且不跨行，单词由字符序列构成且区分大小写。要求统计给定单词在文本文件中出现的总次数，检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。案例探析：本案例需要选择合适的结构完成字符串的建立，实现串的基本操作，利用朴素模式匹配算法实现对文本文件中单词的检索和计数。第4章串线性表——具有相同类型的数据元素的有限序列栈——仅在表的一端进行插入和删除操作队列——在一端进行插入操作，而另一端进行删除操作限制插入、删除位置第4章串线性表——具有相同类型的数据元素的有限序列（多维）数组——线性表中的数据元素可以是线性表串——零个或多个字符组成的有限序列将元素类型扩充为线性表将元素类型限制为字符4.1串的逻辑结构串(string)：零个或多个字符组成的有限序列。串长度：串中所包含的字符个数。空串：长度为0的串，记为""。由一个或多个称为空格的特殊字符组成的串，称为空格串(Blank)，其长度为串中空格字符的个数。非空串通常记为：

S="s1

s2……sn"串名定界符串值4.1串的逻辑结构S1=“ab23kj” S2=“0012” S3=“” S4=“ØØ”

——长度为6的串；——长度为4的串；——空串，长度为0；——含两个空格的空格串。4.1串的逻辑结构子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。子串的位置：子串的第一个字符在主串中的序号。例如，假设A、B、C、D为如下的四个串：A=“SHANGHAI” B=“SHANGHAI”C=“SHANG” D=“HAI”串长？子串的位置？4.1串的逻辑结构串的数据对象约束为某个字符集。微机上常用的字符集是标准ASCII码，由7位二进制数表示一个字符，总共可以表示128个字符。扩展ASCII码由8位二进制数表示一个字符，总共可以表示256个字符，足够表示英语和一些特殊符号，但无法满足国际需要。Unicode由16位二进制数表示一个字符，总共可以表示216个字符，能够表示世界上所有语言的所有字符，包括亚洲国家的表意字符。为了保持兼容性，Unicode字符集中的前256个字符与扩展ASCII码完全相同。串的抽象数据类型ADTString{

数据对象：D={ai|ai∈CharacterSet,i=1,2,…,n,n≥0}

数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3…,n}

基本操作：

StrAssign(＆s,chars)：将串chars的串值赋给串变量s

StrCopy(＆t,s)：由串s复制得到串t

StrEmpty(s)：判断串s是否为空串，若是返回TRUE，否则返回FALSE

StrLength(s)：返回串s的长度

StrCompare(s,t)：比较串s和t的大小。若s>t，返回正整数；若s==t，返回0；若s<t，则返回负整数串的抽象数据类型

ClearString(＆s)：将s清为空串

StrConcat(s1,s2,＆t)：由t返回将串s2连接在串s1的末尾组成的新串

SubStr(s,pos,len)：返回串s中从第pos个字符开始长度为len的子串

StrIndex(s,t,pos)：返回串t在串s的第pos个字符之后第一次出现的位置，若t不是s的子串，则返回0

StrReplace(＆s,t,v)：用串v替换串s中出现的所有与串t相等的不重叠子串

StrInsert(＆s,pos,t)：在串s的第pos个字符之前插入串t

StrDelete(＆s,pos,len)：删除串s中从第pos个字符开始长度为len的子串

Destroystring(＆s)：销毁串s}ADTString串的基本操作在线性表的基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象。串的基本操作如下：（1）串赋值：StrAssign(&s1,s2)操作条件：s1是一个串变量，s2或者是一个串常量，或者是一个串变量(通常s2是一个串常量时称为串赋值，是一个串变量时称为串拷贝)。操作结果：将s2的串值赋值给s1，s1原来的值被覆盖掉。

例：StrAssign(s,“abcd”);例：t=“abcde”; StrAssign(s,t);串的基本操作（2）求串长：StrLength(s)操作条件：串s存在。操作结果：求出串s的长度。（3）联接运算：StrConcat(s1,s2,&s)或StrConcat(&s1,s2)操作条件：串s1，s2存在。操作结果：两个串的联接就是将一个串的串值紧接着放在另一个串的后面，联接成一个串。前者是产生新串s，s1和s2不改变；后者是在s1的后面联接s2的串值，s1改变，s2不改变。例：t="abcde“; StrLength(t);例：s1="bei"，s2="jing“; StrConcat(s1,s2,&s);

StrConcat(&s1,s2);s="beijing"，s1="bei"，s2="jing"s1="beijing"，s2="jing"

（5）串比较运算：StrCompare(s1,s2)操作条件：串s1和s2存在。操作结果：

若s1==s2，操作返回值为0；

若s1<s2，返回值<0；

若s1>s2，返回值>0

(两个字符串自左向右逐个字符按ASCII值大小相比较)。串的基本操作（4）求子串：SubStr(s,pos,len)操作条件：串s存在，1≤pos≤StrLength(s)，0≤len≤StrLength(s)-pos+1。操作结果：返回从串s的第pos个字符开始的长度为len的子串。len=0得到的是空串。例：SubStr("abcdefghi",3,4)=例：StrCompare("bei","bei") StrCompare("bei","dei") StrCompare("cat","case")"cdef"=0<0>0串的基本操作（6）串定位：StrIndex(s,t,pos)操作条件：串s和t存在。操作结果：若主串s中存在和串t值相同的子串,则返回t在主串s中第pos个字符之后第一次出现的位置，pos如果省略，默认为1，否则返回值为-1。例：StrIndex("abebebda","be") StrIndex("abcdebda","ba")例：s="chater";t="rac";pos=4; StrInsert(s,pos,t);s="character"（7）串插入操作：StrInsert(&s,pos,t)操作条件：串s和t存在，且1≤pos≤StrLength(s)+1。操作结果：将串t插入到串s的第pos个字符位置之前，s的串值发生改变。=2=-1串的基本操作（8）串删除操作：StrDelete(&s,pos,len)操作条件：串s存在，且1≤pos≤StrLength(s)，0≤len≤StrLength(s)-pos+1。操作结果：删除串s中从第pos个字符开始的长度为len的子串，s的串值改变。（9）串替换操作：StrReplace(&s,t,r)操作条件：串s，t和r存在，且t不为空。操作结果：用串r替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。例：s=“Microsoft”;pos=4;len=5; StrDelete(s,pos,len)例：s="abcacabcaca";t="abca";r="x";

StrReplace(&s,t,r);s="Mict"s="xcxca"串的基本操作（10）判相等操作：StrEqual(s,t)操作条件：串s和t存在。操作结果：若s与t的值相等则运算结果为1，否则为0。通常将前5个基本操作称为最小操作集，其他操作均可在最小操作子集上实现。例如：可利用判等、求串长和求子串等操作实现定位函数StrIndex(s,t,pos)。在主串s中取从第i（i的初值为pos）个字符起，长度与串t相等的子串同串t比较，若相等，则函数返回值为i，否则i值增1，直至串s中从第i个字符起直到串尾的子串长度小于串t的长度为止。

例：s="ab";t="abzcd";r="ab";

StrEqual(s,t)=0

StrEqual(s,r)=1串的基本操作【算法4-1】利用最小操作子集实现定位函数#defineMaxLen<最大串长>;typedefstruct{charstr[MaxLen];intcurlen;}SString;intStrIndex(SStrings,SStringt,intpos){if(pos>0){SStringsub;n=StrLength(s);m=StrLength(t);i=pos;while(i<=n-m+1){sub=SubStr(s,i,m);if(StrCompare(sub,t)!=0)++i;elsereturni;}}return-1;}

4.2串的存储结构串的顺序存储结构被称为顺序串。串的顺序存储有两种方法：在一个存储单元中存放多个字符，称为紧缩格式。一个存储单元中只存放一个字符，即所需的存储

单元个数就是串的长度，称为非紧缩格式。DATASYSTEM非紧缩格式DATA空闲SYSTEM所需的存储单元个数就是串长串的定长顺序存储一个单元串的定长顺序存储方案1：用一个变量来表示串的实际长度。串的顺序存储结构是用数组来存储串中的字符序列。那么如何表示串的长度？0123456……MaxLen-1

abcdefg7空闲串的定长顺序存储01234567……MaxLen-1

abcdefg\0空闲方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。方案1：用一个变量来表示串的实际长度。串的顺序存储结构是用数组来存储串中的字符序列。那么如何表示串的长度？串的定长顺序存储方案3：用数组的0号单元存放串的长度，从1号单元开始存放串值。01234567……MaxLen-1

7

abcdefg空闲方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。方案1：用一个变量来表示串的实际长度。串的顺序存储结构是用数组来存储串中的字符序列。那么如何表示串的长度？7串的定长顺序存储#defineMaxLen<最大串长>

／*定义能处理的最大的串长度*／typedefstruct{charstr[MaxLen];

／*定义可容纳MaxLen个字符的字符数组*／intcurlen;／*定义当前实际串长度*／}SString;顺序串的类型定义描述顺序串的实现——判相等运算StrEqual(s,t)intStrEqual(SStrings,SStringt)／*判串s和串t是否相等。相等，返回l；否则返回0*／{inti,j;if(s.curlen==t.curlen)／*首先判断两个串的长度是否相等*／{for(i=0;i<s.curlen;i++)／*长度相等则继续比较对应位置的每个字符是否相等*／

{if(s.str[i]==t.str[i])j=1;else{j=0;

break;}／*若对应位置字符出现不等，终止比较*／}}elsej=0;／*长度不相等则判定两个串不相等，返回0*／returnj;}【算法4-2】顺序串的实现——联接运算StrConcat(s,t,&ch)串的联接运算是将两个串s和t的串值分别传送到新串ch的相应位置，超过MaxLen的部分截去。其运算结果可能有3种情况：s.curlen+t.curlen≤MaxLen，得到的新串ch是正确的结果；s.curlen+t.curlen>MaxLen而s.curlen<MaxLen，则将t的一部分截去，得到的新串ch中包含s和t的一个子串；s.curlen>=MaxLen，则得到的新串ch中只含有s一个子串。voidStrConcat(SStrings,SStringt,SString&ch)

／*用ch返回由s和t联接而成的新串*／{inti;

if(s.curlen+t.curlen<=MaxLen)／*未截断*／

{ch.curlen=s.curlen+t.curlen;／*计算新串的串长度*／for(i=0;i<s.curlen;i++) ch.str[i]=s.str[i];for(i=0;i<t.curlen;i++) ch.str[s.curlen+i]=t.str[i];

ch.str[ch.curlen]=’\0’;／*在新串的最后设置串的结束符*／

}【算法4-3】顺序串的实现——联接运算StrConcat(s,t,&ch)

elseif(s.curlen<MaxLen)/*截断*／

{ch.curlen=MaxLen;/*计算新串的串长度*／for(i=0;i<s.curlen;i++) ch.str[i]=s.str[i];for(i=0;

i<MaxLen-s.curlen;i++) ch.str[s.curlen+i]=t.str[i];

ch.str[ch.curlen]=’\0’;/*在新串的最后设置串的结束符*／

}else/*截断，仅取s的一个子串*／

{ch.curlen=MaxLen;/*计算新串的串长度*／

for(i=0;i<MaxLen;i++) ch.str[i]=s.str[i];

ch.str[ch.curlen]=’\0’;／*在新串的最后设置串的结束符*／

}}【算法4-3】顺序串的实现——联接运算StrConcat(s,t,&ch)顺序串的实现——求子串运算SubStr(s,pos,len)SStringSubStr(SStrings,intpos,intlen){inti,j=0;SStringch;

if((pos>=1&&pos<=StrLength(s))&&(len>=0&&len<=StrLength(s)-pos+1)){for(i=pos-1;i<len+pos-1;i++)

ch.str[j++]=s.str[i];

ch.curlen=len;ch.str[ch.curlen]='\0';}elseprintf(“\nerror!\n”);／*参数不正确时返回错误信息*／returnch;}【算法4-4】顺序串的实现串的定长顺序存储结构适用于求串长、求子串等运算。但这种存储结构有两个缺点：一是需要预先定义一个串允许的最大长度，如果定义的空间过大，则会造成空间浪费；二是由于限定了串的最大长度，则会限制串的某些运算，如联接、置换运算等。串的堆分配存储结构实现方法：提供一个足够大的连续存储空间，作为串的可利用空间，来存储各串的串值。每当建立一个新串时，系统就从这个可利用空间中划分出一个大小和新串长度相等的空间给新串，若分配成功则返回一个指向起始地址的指针。可使用C语言中的malloc()和free()函数来管理可利用空间。虽然这种存储表示仍以一组地址连续的存储单元存放串值，但它属于一种动态分配方式，所以也可看做一种动态存储分配的顺序表。typedefstruct{intlen;/*len存放串长*/char*ch;/*ch存放串的首地址，若是空串，则ch的值为NULL*/}HString;串的堆分配存储结构串的堆分配存储结构图4-1串的堆分配存储结构示例串的赋值运算：StrAssign(&s1,s2)intStrAsssign(HString&t,char*chars)/*生成一个其值等于串常量chars的串t*/{inti,k;char*c;／*c为指向字符的指针变量*／

if(t.ch)free(t.ch);／*释放t原有的空间*／

for(i=0,c=chars;c;++i,++c);

／*求chars的长度*／if(!i)／*若chars的长度为0，则生成空串t*／

{t.ch=NULL;t.len=0;}【算法4-5】串的赋值运算：StrAssign(&s1,s2)else／*chars的长度大于0*／

{if(!(t.ch=(char*)malloc(i*sizeof(char))))return0;／*空间申请失败，返回失败标志*／

for(k=0;k<=i-1;k++)／*逐个复制元素*／

t.ch[k]=chars[k];t.len=i;／*保存串的长度*／

return1;／*成功*／

}}【算法4-5】串的联接运算：StrConcat(s1,s2,&t)intStrConcat(HStrings1,HStrings2,Hstring＆t)／*用t返回由s1和s2联接成的新串*／{intk，j=0;

if(t.ch)free(t.ch);

if(!(t.ch=(char*)malloc((s1.len+s2.len)*sizeof(char))))

return0;

for(k=0;k<=s1.len-1;k++)t.ch[k]=s1.ch[k];／*复制串s1到串t*／

t.len=s1.len+s2.len;／*串t的长度等于串s1和串s2长度之和*／

for(k=s1.len;k<=t.len-1;k++)／*复制串s2到t，s2接在s1之后*／

{t.ch[k]=s2.ch[j];

j++;

}return1;}【算法4-6】堆分配存储结构的串既有顺序存储结构的特点（简单、处理方便），操作中对串长又没有任何限制，非常灵活，因此在串处理中经常被采用。串的块链存储串的链式存储结构被称为链串。使用链表存储串值时，每个结点可以存放一个字符，也可以存放多个字符，结点中存放字符的个数称为“结点大小”。串的块链存储#defineCHUNKSIZE80/*可由用户定义的块大小*/typedefstruct/*结点结构*/{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct/*串的链表结构*/{Chunk*head,*tail;/*串的头和尾指针*/intcurlen;/*串的当前长度*/}LString;链串的类型定义描述链串的基本操作——求串长度算法intStrLength(char*s){ char*p=s; intlen=0; while(*p!='\0') {len++; p++; } returnlen;}链串的基本操作——串连接算法intStrConcat1(s1,s2,s)chars1[],s2[],s[];{inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if(len1+len2>MAXSIZE-1)return0;/*s长度不够*/

j=0;while(s1[j]!=’\0’){s[i]=s1[j];i++;j++;}

j=0;while(s2[j]!=’\0’){s[i]=s2[j];i++;j++;}s[i]=’\0’;return1;}s1=〃student〃

s2=〃teacher〃s=〃studentteacher〃链串的基本操作——求子串算法intStrSub(char*t,char*s,inti,intlen)/*用t返回串s中第个i字符开始的长度为len的子串1≤i≤串长*/{intslen;slen=StrLength(s);if(i<1||i>slen||len<0||len>slen-i+1){printf(＂参数不对＂);return0;}for(j=0;j<len;j++)

t[j]=s[i+j-1];t[j]=’\0’;return1;}链串的基本操作——串比较算法串的比较：通过组成串的字符之间的比较来进行的。给定两个串：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="ab13"链串的基本操作——串比较算法intStrComp(char*s1,char*s2){inti=0;while(s1[i]==s2[i]&&s1[i]!=’\0’)i++;return(s1[i]-s2[i]);}4.3串的模式匹配（串的定位）模式匹配：给定主串S=“s1s2…sn”和模式T=“t1t2…tm”，在主串S中寻找子串T的过程称为模式匹配。如果匹配成功，返回T在S中的位置；如果匹配失败，返回0。算法的一次执行时间不容忽视：问题规模通常很大，常常需要在大量信息中进行匹配；算法改进所取得的积累效益不容忽视：模式匹配操作经常被调用，执行频率高。模式匹配问题有什么特点？4.3串的模式匹配（串的定位）在下面的讨论中，为了和C语言中的字符数组保持一致，采用第2种顺序存储方法，即从数组下标0开始存放字符，并且在串尾存储终结符'\0'。01234567……MaxLen-1abcdefg\0空闲模式匹配——BF算法（朴素的模式匹配算法）基本思想：从主串（目标串）S的第一个字符开始和模式串T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式串T的第一个字符进行比较，重复上述过程，直到T中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。模式匹配——BF算法（朴素的模式匹配算法）

si……主串S模式T

tjji…回溯i回溯j本趟匹配开始位置模式匹配——BF算法（朴素的模式匹配算法）si……主串S模式Tji…

tj例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）ababcabcacbabi=2，j=2失败；i回溯到1，j回溯到0ijijij第1趟abcac

例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）jii=2，j=2失败；i回溯到1，j回溯到0ababcabcacbababcac

第1趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）i=1，j=0失败i回溯到2，j回溯到0ijababcabcacbababcac

第2趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）iji=1，j=0失败i回溯到2，j回溯到0ababcabcacbababcac

第2趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）ababcabcacbabi=6，j=4失败i回溯到3，j回溯到0abcacijijijijij第3趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）iji=6，j=4失败i回溯到3，j回溯到0ababcabcacbababcac第3趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）i=3，j=0失败i回溯到4，j回溯到0ijababcabcacbababcac第4趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）iji=3，j=0失败i回溯到4，j回溯到0ababcabcacbababcac第4趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）i=4，j=0失败i回溯到5，j回溯到0abcacijababcabcacbab第5趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）iji=4，j=0失败i回溯到5，j回溯到0abcacababcabcacbab第5趟例：主串S="ababcabcacbab"，模式T="abcac"模式匹配——BF算法（朴素的模式匹配算法）abcaci=10，j=5，T中全部字符都比较完毕，匹配成功ijijijijijababcabcacbab第6趟在串S和串T中设比较的起始下标i和j；循环直到S或T的所有字符均比较完毕2.1如果S[i]=T[j]，继续比较S和T的下一个字符；2.2否则，将i和j回溯，准备下一趟比较；如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0；模式匹配——BF算法（朴素的模式匹配算法）intIndex_BF(SStrings,SStringt){inti,j;i=0;/*指向串s的第1个字符*/j=0;/*指向串t的第1个字符*/while((i<s.curlen-t.curlen))&&(j<t.curlen)){if(s.str[i]==t.str[j]){++i