数据结构第4章串类型的定义

第四章串课前导学4.1串类型的定义4.2串的表示和实现【学习目标】

1.理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。

2.理解串类型的各种存储表示方法。

【重点和难点】

了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。【知识点】串的类型定义、串的存储表示【课前思考】从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。区别1、它的数据元素都是字符，它的存储结构和线性表有很大不同;

区别2、串的基本操作通常以"串的整体"作为操作对象，而不像线性表是以"数据元素"作为操作对象。“串就是线性表”的结论是否正确？二者之间有何区别?4.1串类型的定义1.基本概念串（string）：由0个或多个字符组成的有限序列，也称字符串。记为：

s=’

a1a2a3……an

’

(n≥0)

式中s是串的名，a1a2a3……an是串的值，ai（1≤i≤n）可以是字母、数字或其它字符。串长度：串中字符的数目n。空串：不含任何字符的串，串长度=0空格串：仅由一个或多个空格组成的串子串：由串中任意个连续的字符组成的子序列主串：包含子串的串。串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。注意：（1）串值必须用一对单引号括起来（2）串值大小是按词典次序进行比较的

StrCompare(‘data’,’Stru’)<0

StrCompare(‘cat’,’case’)>0

显然，只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。2.串的抽象数据类型的定义ADTString{

数据对象：D＝{ai

|ai∈CharacterSet,i=1,2,...,n,n≥0}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

StrAssign(&T,chars)

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

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

StrCopy(&T,S)

初始条件：串S存在。操作结果：由串S复制得串T。

DestroyString(&S)

初始条件：串S存在。

操作结果：串S被销毁。

StrEmpty(S)

初始条件：串S存在。

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

StrCompare(S,T)

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

操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。

StrLength(S)

初始条件：串S存在。

操作结果：返回S的元素个数，称为串的长度。

Concat(&T,S1,S2)

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

操作结果：用T返回由S1和S2联接而成的新串。

SubString(&Sub,S,pos,len)

初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。

操作结果：用Sub返回串S的第pos个字符起长度为len的子串。

Index(S,T,pos)

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

操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。

Replace(&S,T,V)

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

操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。

StrInsert(&S,pos,T)

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

操作结果：在串S的第pos个字符之前插入串T。

StrDelete(&S,pos,len)

初始条件：串S存在，1≤pos≤StrLength(S)-len+1。

操作结果：从串S中删除第pos个字符起长度为len的子串。

ClearString(&S)

初始条件：串S存在。操作结果：将S清为空串。

}ADTString

在以上操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现。思考：串的基本操作和线性表一样，无非也就是查找、插入和删除等，那么它们能否用线性表的操作来替代呢？串的基本操作和线性表有很大的区别，同样是查找、插入和删除，但对线性表而言操作对象是“数据元素”，而对串言，是以整个串作为操作对象。由此可见，串类型不能和线性表类型混为一谈。4．2串的表示和实现

1.定长顺序存储用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存储结构。

可以用定长数组来描述：#defineMAXSTRLEN255//用户可在255以内定义最大串长

typedefcharSString[Maxstrlen+1];

//0号单元存放串的长度

3boy……串长[0][255]SString类型图示SString有效字符1.定长顺序存储时串的操作串联结Contcat（&T,S1,S2）

算法描述：

StatusConcat(SString&T,SStringS1,SStringS2){//用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE。

if(S1[0]+S2[0]<=Maxstrlen){//未截断

T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];

T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]<Maxstrsize){//

截断

T[1..S1[0]]=S1[1..S1[0]];

T[S1[0]+1..Maxstrlen]=S2[1..Maxstrlen－S1[0]];

T[0]=Maxstrlen;uncut=FALSE;}

else{//截断(仅取S1)

T[0..Maxstrlen]=S1[0..Maxstrlen];

//T[0]==S1[0]==Maxstrlen

uncut=FALSE;}

returnuncut;}//Concat（2）求子串SubString(&Sub,S,pos,len)

StatusSubString(SString&Sub,SStringS,int

pos,int

len){

//用Sub返回串S的第pos个字符起长度为len的子串。

//其中1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1

if(pos<1||pos>S[0]||

len<0||len>S[0]-pos+1)

returnERROR;

Sub[1……len]=S[pos…pos+len-1]；

Sub[0]=len；

returnOK;

}//SubString例：SubString(Sub,“commander”,4,3)得到的结果是：Sub="man"。

2.堆分配存储

堆:一块自由存储区，,C语言用malloc()分配，C++用new

分配。

串的堆存储：以一组地址连续的存储单元存储串值的字符序列，在程序执行过程中由动态分配而得到。

串的堆分配存储表示：

typedef

struct{

char*ch;//若非空串则按串长分配存储区,否则为NULL

intlength;//串长度

}HString;chlengthHStringchar注：1、C语言中提供的串类型就是以这种存储方式实现的2、系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。

C++中用new和delete操作符来进行堆空间的分配和回收.3、C语言中的串以一个空字符\0为结束符，串长是一个隐含值。3boyT“boy”的堆存储结构null0空串结构3.串的块链存储表示串值也可用链表来存储，和线性表的链接存储类似，不同的是一个结点中存放的不一定是一个字符，可以是一个子串，当串长不是结点大小的整数倍时，最后一个结点用其他字符补上（如：#）。例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。

块链结构：为了便于进行串的操作，当以链表存储串值时，除头指针外还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。

#defineCHUNKSIZE4//可由用户定义的块大小

typedef

structChunk{//结点结构

charch[CHUNKSIZE];

structChunk*next;

}Chunk;

ch[0]ch[1]ch[2]h[3]nextChunkChunktypedef

struct{//串的链表结构

Chunk*head,*tail;//

串的头