nets:[[../else/数据结构]] 课程笔记

4.1 串的定义类型

基本操作：
StrAssign (&T,chars)
初始条件：chars是字符串常量。
操作结果：把chars赋为T的值。

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

StrCopy (&T,S)
初始条件：串S存在。
操作结果：串S被销毁。

StrLength(S)
初始条件：串S存在。
操作结果：若S为空串，则返回TRUE,否则返回FALSE。
”表示空串，空串的长度为零。

StrCompare (S,T)
初始条件：串S和T存在。
操作结果：若S>T,则返回值>0；
若S=T,则返回值=0；
若S<T,则返回值<0.

Concat (&T,S1,S2)
初始条件：串S1和S2存在。
操作结果：用T返回由S1和S2联接而成的新串。

StrEmpty (S)

SubString (&Sub,S,pos,len)
初始条件：
串S存在，1≤os≤StrLength(S)且Olen≤StrLength(S)-pos+1。
操作结果：
用Sub返回串S的第pos个字符起长度为len的子串。

ClearString (&S)
初始条件：串S,T和V均已存在，且T是非空串。
操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串

Index (S,T,pos)
初始条件：串S和T存在，T是非空1<=pos<=StrLength(S)。
操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第p0s个字符之后第一次出现的位置；否则函数0。

Replace (&S,T,V)
初始条件：串S,T和V均已存在，且T是非空串。
操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串

StrInsert (&S,pos,T)
初始条件：串S和T存在，lpos≤StrLength(S)+1。
操作结果：在串S的第pos个字符之前插入串T。

StrDelete (&S,pos,len)
初始条件：串S存在1<=pos<=StrLength(S)-len+l。
操作结果：从串S中删除第pos个字符起长度为len的子串。

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

串赋值StrAssign、串复制Strcopy、
串比较StrCompare、求串长StrLength、
串联接Concati以及求子串SubString
等六种操作构成串类型的最小操作子集。

4.2 串的表示和实现

一、串的定长顺序存储表示

1
2
3
4
#define MAXSTRLEN 255
//用户可在255以内定义最大串长
typedef unsigned char Sstring [MAXSTRLEN 1];
//0号单元存放串的长度
  • 串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”
  • 按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //例如：串的联接算法中需分三种情况处理：
    Status Concat(SString S1,SString S2,SString &T){
    //用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE,否则FALSE。
    if(S1[O]+S2[O]<=MAXSTRLEN){//未截断}
    else if(S1[O]<MAXSTRSIZE){//截断}
    else{//截断（仅取S1)
    T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[O]=S1[0=MAXSTRLEN
    uncut=FALSE;
    }
    return uncut;
    }∥Concat

二、串的堆分配存储表示

1
2
3
4
5
typedef struct{
char *ch;
//若是非空串，则按串长分配存储区，否则c为NULL
int length;//串长度
}HString;

通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和fee()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”
C语言中的串以一个空字符为结束符，串长是一个隐含值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Status Concat(HString &T,HString S1,HString S2)
//用T返回由S1和S2联接而成的新串
if (T.ch)free(T.ch);
//释放旧空间
if (!(T.ch=(char *malloc((S1.length+S2.length)*sizeof(char))))
exit (OVERFLOW);
T.ch[0..S1.length-1]=S1.ch[0..S1.length-1];
T.length=S1.length S2.length;
T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];
return OK;
}//Concat

Status SubString(HString &Sub,HString S,int pos,int len){
//用Sub返回串S的第pos个字符起长度为len的子串
if(pos<1||pos>S.length||en<0||len>S.length-pos+l)
return ERROR;
if (Sub.ch)free(Sub.ch);
//释放旧空间
if(!len){Sub.ch=NULL;Sub.length=0;}//空子串
else {Sub.ch =(char *)malloc(len*sizeof(char));
Sub.ch[0..len-1]=S[pos-1..pos+len-2];
Sub.length=len;
}//完整子串
return OK:
}//SubString

三、串的块链存储表示

也可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。

1
2
3
4
5
6
7
8
9
#define CHUNKSIZE 80//可由用户定义的块大小
typedef struct Chunk{//结点结构
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{//串的链表结构
Chunk*head,*tail//串的头和尾指针
int curlen;//串的当前长度
}LString;

4.3 串的操作举例

字符串匹配算法（重点）

简单模式匹配

1
2
3
4
5
6
7
8
9
10
int Index(SString S,SString T,int pos){
//返回子串T在主串S中第pos个字符之后的位置。若不存在，
//则函数值为0。其中，T非空，1≤pos≤StrLength(S)。
i=pos,j=1;
while (i<=S[0]&&j<=T[0]){
if(S[i]==T[j]){++i;++j;}//继续比较后继字符
else{i=ij+2,j=1;}//指针后退重新开始匹配
if (j>T[O])return i-T[O];
else return 0;
}//Index

KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void get_next(SString T,int next[]){
//求模式串T的next函数并存入数组next。
i=1;next[1]=0;j=0;
while (i <T[0]){
if (j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
}//get_next

int Index_KMP(SString S,SString T,int pos){
i=pos,j=1;
while (i<=S[0]&j<=T[0]){
if(j==0||S[i]=T[j]){++i;++j;}
//继续比较后继字符
else j=next[j];
//指针后退重新开始匹配
}
if (j>T[0])return i-T[0];
else return 0;
}//Index

References