串和数组精选课件

第5章串和数组串也可以看作是一种线性表，只是其操作通常是按成组的元素来进行的。数组可以认为是线性表在维数上的一种拓展。串和数组依然属于线性结构，但在存储结构的实现方面较线性表为复杂。值得注意的是，串和数组是在高级语言层面已经实现的数据类型，在数据结构中再讨论它们是为了深入理解实现它们的基础技术。讲授本章课程大约需4课时。1第5章串和数组串也可以看作是一种线性表，只是其操作通

5.1串的定义和操作5.2串的表示和实现

5.3正文模式匹配5.4正文编辑━串操作应用举例25.1串的定义和操作25.1串的定义和操作35.1串的定义和操作3串的定义：

串（String），或称字符串是由零个或多个字符组成的有限序列。记作：S=a0a1…ai…an-1

（n≥0）

其中，ai属于字符集，n为串的长度，当n=0时串为空串。例如:

astring、a+b、

4串的定义：串（String），或称字符串是由零个或串的基本操作：

StrAssign(&T,chars)

StrCopy(&T,S)

DestroyString(&S)

StrEmpty(S)

StrCompare(S,T)

StrLength(S)

Concat(&T,S1,S2)5串的基本操作：StrAssign(&T,chars)SubString(&Sub,S,pos,len)

Index(S,T,pos)

Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)

ClearString(&S)6SubString(&Sub,S,pos,len)

StrAssign(&T,chars)

初始条件：chars是字符串常量。

操作结果：把chars赋为T的值。

7StrAssign(&T,chars)7

StrCopy(&T,S)

初始条件：串S存在。

操作结果：由串S复制得串T。8

StrCopy(&T,SDestroyString(&S)

初始条件：串S存在。

操作结果：串S被销毁。9DestroyString(&S)9

表示空串，空串的长度为零

StrEmpty(S)

初始条件：串S存在。

操作结果：若S为空串，则返回TRUE，否则返回FALSE。

表示空格，长度为1的字符串10表示空串，空串的长度

StrCompare(S,T)

初始条件：串S和T存在。

操作结果：若ST，则返回值0；

若ST，则返回值0；

若ST，则返回值0。例如：StrCompare(data,state)<0StrCompare(cat,case)>011StrCompare(

StrLength(S)

初始条件：串S存在。

操作结果：返回S的元素个数，

称为串的长度。12StrLength(S)

Concat(&T,S1,S2)

初始条件：串S1和S2存在。

操作结果：用T返回由S1和S2

联接而成的新串。例如：Concate(T,man,kind)

求得T=mankind13Concat(&T,S1,S2)

初

SubString(&Sub,S,pos,len)初始条件：

串S存在，0≤pos<StrLength(S)且0≤len≤StrLength(S)-pos。操作结果：

用Sub返回串S的位置为pos起长度为len的子串。14

SubString(&Sub,S,pos,例如：

SubString(sub,commander,3,3)

求得sub=man；SubString(sub,commander,0,9)求得sub=commander；SubString(sub,commander,8,1)求得sub=r；子串为“串”中的一个字符子序列15例如：子串为“串”中的一个字符子序列15SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串长度之间存在约束关系长度为0的子串为“合法”串16SubString(sub,commander,

Index(S,T,pos)

初始条件：串S和T存在，T是非空串，

0≤pos≤StrLength(S)-1。

操作结果：

若主串S中存在和串T值相同

的子串,则返回它在主串S中第pos个

字符之后第一次出现的位置；

否则函数值为-1。

17Index(S,T,假设S=abcaabcaaabca,T=bca

Index(S,T,1)=1；Index(S,T,3)=5；Index(S,T,11)=-1；

“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。18假设S=abcaabcaaabca,T=

Replace(&S,T,V)

初始条件：串S,T和V均已存在，

且T是非空串。

操作结果：

用V替换主串S中出现

的所有与（模式串）T

相等的不重叠的子串。19

Replace(&S,T,V例如：假设S=abcaabcaaabca，T=bca若V=

x，则经置换后得到S=axaxaax若V=bc，则经置换后得到S=abcabcaabc20例如：假设S=abcaabcaaabca，T

StrInsert(&S,pos,T)

初始条件：串S和T存在，1≤pos≤StrLength(S)。

操作结果：在串S的第pos个字符之前插入串T。例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=character21StrInsert(&S,pos,T)

StrDelete(&S,pos,len)

初始条件：串S存在

1≤pos≤StrLength(S)-len。

操作结果：从串S中删除位置pos

起长度为len的子串。

22StrDelete(&S,pos,lenClearString(&S)

初始条件：串S存在。

操作结果：将S清为空串。

23ClearString(&S)

初始条件：

对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。

gets(str)输入一个串；

puts(str)

输出一个串；

strcat(str1,str2)串联接函数；

strcpy(str1,str2)

串复制函数；

strcmp(str1,str2)串比较函数；

strlen(str)求串长函数；

char*strstr(char*s,char*sub)

如果找到子串，返回该位置的指针。如果找不到，则返回空指针。-C语言程序设计-附录C例如：C语言函数库中提供下列串处理函数：24对于串的基本操作集可以有不同的定义方法，在使用高级在上述串类型定义的13种操作中，串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。

即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。25在上述串类型定义的13种操作中，25例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。pos<=i<=n-mSubString(sub,S,i,StrLength(T))StrCompare(sub,T)

?

0

S串T串

T串iposn-m算法的基本思想为：26例如，可利用串比较、求串长和求子串等操作实现定位函数int

Index(StringS,StringT,intpos){

//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0

if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;

while(i<=n-m+1){

SubString(sub,S,i,m);

if(StrCompare(sub,T)!=0)++i;

else

returni;//S中的第一个与T相等子串的位置

}

//while

}

//if

return

-1;//S中不存在与T相等的子串}//Index27intIndex(StringS,StringT串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

串的基本操作和线性表有很大差别。

在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。28串的逻辑结构和线性表极为相似，区别串的基本操5.2串的表示和实现295.2串的表示和实现29在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。30在程序设计语言中，串只是作为输入或输出的常量出现，则一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示（在存储结构的层面讨论串的操作）31一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存一、串的定长顺序存储表示

如果利用C语言的串类型描述算法，可用一组连续的存储单元存放串的字符序列，并以‘\0’为结束标志。使用C语言的字符数组来存储字符串。如，chars[]="abc";//字符串的长度为3chara[10];//字符串最大串长为9

32一、串的定长顺序存储表示如果利用C语言的串类型描述算法

按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断”串的定长顺序存储操作特点:33按这种串的表示方法实现的串的运算时，其基本操作为“字符序void

concat_sq(char

s1[],char

s2[],char

t[

])

{

int

j=0,k=0;

while(s1[j]!='\0')

t[k++]=s1[j++];//复制S1

j=0;

while(s2[j]!=‘\0’)t[k++]=s2[j++];

//接着复制S2

t[k]='\0';//增加结束符}例如：串的联接操作concat34voidconcat_sq(chars1[],charvoidmain(){

char

s1[]="china";

char

s2[]="beijing";

char

t1[13];

//顺序分配定长空间

concat(s1,s2,t1); cout<<t1<<endl;}定长分配体现在调用程序35voidmain(){定长分配体现在调用程序35typedefstruct{char*ch;

//若是非空串，则按串长分配存储区，//否则ch为NULL

int

length;//串长度

}

HString;二、串的堆分配存储表示如果完全用伪码描述算法，可进行类型定义：36typedefstruct{二、串的堆分配存储表示如果直接用C语言描述算法，可通过函数new和delete为用户进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。

本书采用这种方式。

这类串操作实现的常用思路：先为新生成的串分配一个存储空间，然后进行串值的复制。37如果直接用C语言描述算法，可通过函数new和deleconcat

操作substring

操作串的堆分配存储表示实现38concat操作substring操作串的堆分配存储表示void

concat(char*s1,char*s2,char*&t){

inti=0,j=0;

t=new

char[strlen(s1)+strlen(s2)+1];//为t分配堆空间

while((t[i]=s1[i])!='\0')i++;

while((t[i]=s2[j])!='\0'){i++;j++;

}

}39voidconcat(char*s1,char*s2voidmain()

{

char*s1="china";

char*s2="beijing";

char*t1;//仅说明类型而不申请空间concat(s1,s2,t1);

cout<<t1<<endl;}调用程序无需预先申请空间40voidmain(){调用程序无需预先申请空间40

void

substring(char*&sub,char*s,intpos,intlen){char*p;

intk,slen=strlength(s);

if(pos<0||pos>slen-1||len<0||len>slen-pos)

ERRORMESSAGE(“参数不合法”);sub=new

char[len+1];//为sub分配堆空间p=s+pos-1;k=len;

while(k){*sub++=*p++;k--;

}*sub='\0';sub=sub-len;}41voidsubstring(char*&sub,c5.3正文模式匹配425.3正文模式匹配42先前，曾介绍过串匹配(查找)的操作INDEX(S,T,pos)在实际应用中，串的匹配查找操作使用的机会很多，现专门讨论该算法。使用串的有关操作实现了INDEX，但在效率上仍有改进的余地。43先前，曾介绍过串匹配(查找)的操作INDEX(S,T

简单算法（简单的正文模式匹配算法）

以定长顺序结构表示串abaacababaacbcaababaacbaabaacabaacST演示模型：匹配成功！44简单算法（简单的正文模式匹配算法）abaacababaacint

Index_BF(charS[],charT[],intpos){

//返回子串T在主串S中第pos个字符之后的位置。若不存在，//则函数值为-1。其中，T非空，0≤pos≤StrLength(S)-1。i=pos;j=0;

while(S[i+j]!=‘\0’&&T[j]!=‘\0’)

if(S[i+j]==T[j])j++;//继续比较后继字符

else

{i++;j=0;}

//重新开始新一轮的匹配

if(T[j]!=‘\0’)returni;

elsereturn-1;}//Index_BF45intIndex_BF(charS[],charT[若找到S中所有和模式串T匹配的子串，只需多次调用Index_BF(charS[],charT[],intpos)匹配成功后,下一次的匹配起始位置为i+Strlength(T)Index_BF不是最精巧的模式匹配算法，但比较好理解，适合于一般的使用。46若找到S中所有和模式串T匹配的子串，只需多次调用Inde5.4正文编辑

━串操作应用举例47