前言
一、串类型的定义
1、基本概念与术语
练习:(加深理解)
2、串的抽象数据类型定义
(1)串的类型定义与运算(基本 *** 作)
(2)串的抽象数据类型定义
(3)串与线性表的区别
练习:
1、定长顺序存储表示
(1)串的顺序存储表示
(2)串的定长顺序存储结构
(3)特点:
(4)在定长顺序存储下串的基本 *** 作实现
2、堆分配存储表示
(1)堆分配存储特点
(2)特点
(3)串的堆分配存储结构
3、串的块链存储方式(链式存储)
(1)块链存储方式
(2)块链存储结构
(3)特点
三、串的模式匹配算法
1、BF算法(经典的、朴素的、穷举的)
(1)算法设计思想
(2)算法过程示意图
(3)具体算法描述:
2、KMP算法(特点:速度快)
(1)算法设计思想
(2)算法的推导过程
(3)算法的实现(关键:计算next[j])
(4)算法的时间复杂度
(5)练习
总结
前言
本文主要介绍数据结构(C语言版)第四章串的内容,主要包括串类型的定义、串的表示和实现、串的模式匹配算法。
希望通过本文的学习能够让你掌握串的概念、掌握在串在定长顺序存储结构上、堆分配存储结构上实现串的各种 *** 作的方法,了解串的块链存储结构并且掌握串的模式匹配算法。
一、串类型的定义 1、基本概念与术语
串——即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。 记为:S = 'a1 a2 ..... an'(n≥0) 串名为S 串值——用''括起来的部分
串长——串中字符个数(n≥0)。n=0时称为空串,记作∅。
空格串——由一个或多个空格符组成的串。
子串——串s中任意个连续的字符序列叫s的子串;S叫主串。
子串位置——子串的第一个字符在主串中(首次出现)的位置。
字符位置——字符在串中的序号。
串相等——串长度相等,且对应位置上字符相等。
ADT String {
数据对象:D = {ai|ai∈CharacterSet,i=1,2,…,n,n≥0}
数据关系:R1={|ai-1,ai∈D,i=1,2,…,n}
基本 *** 作:
(1) StrAssign (&T,chars)//串赋值
(2) StrCompare (S,T)//串比较
(3) StrLength (S)//求串长
(4) Concat(&T,S1,S2)//串连接
(5) SubString(&Sub,S,pos,len)//求子串
(6) StrCopy(&T,S)//串拷贝
(7) StrEmpty(S)//串判空
(8) ClearString (&S)//清空串
(9) Index(S,T,pos)//子串的位置
(11) Replace(&S,T,V)//串替换
(12) StrInsert(&S,pos,T)//子串插入
(12) StrDelete(&S,pos,len)//子串删除
(13) DestroyString(&S)//串销毁
}ADT String
(2)串的抽象数据类型定义
StrAssign(&T,chars)//串赋值
初始条件:chars是字符串常量。
*** 作结果:生成一个值等于chars的串T。
StrCopy(&T,S)//串复制
初始条件:串S存在。
*** 作结果:由串S复制得串T。
DestroyString (&S)
初始条件:串S存在。
*** 作结果:串S被销毁。
ClearString (&S)
初始条件:串S存在。
*** 作结果:将S清为空串。
StrEmpty(S)
初始条件:串S存在。
*** 作结果:若S为空串,则返回TRUE,否则返回FALSE。
StrCompare(S,T)//串比较
初始条件:串S和T存在。
*** 作结果:若S>T,则返回值>0;若S=T,则返回值=O;若S
对于串的基本 *** 作集可以有不同的定义方法。
C语言函数库中提供下列串处理函数:
gets(str)输入一个串;puts(str)输出一个串;
strcat(str1,str2)串联接函数;strcpy(str1,str2,k)串复制函数;
strcmp(str1,str2)串比较函数;
strlen(str)求串长函数;
在以上 *** 作中,
串赋值StrAssign、串比较StrCompare、
求串长StrLength、串联接Concat、求子串SubString
5种 *** 作构成串类型的最小 *** 作子集,即:这些 *** 作不可能利用其他串 *** 作来实现,反之,其他串 *** 作(除串清除ClearString和串销毁DestroyString外)可在这个最小 *** 作子集上实现。
例如,可利用串比较、求串长和求子串等 *** 作实现定位函数Index(S,T,pos)。
算法的基本思想——在主串s中取从第i(i初值为pos)个字符起、长度和串T相等的子串和串T比较,若相等则求得的函数值为i,否则i值增1直至串s中不存在和串T相等的子串为止。
具体算法描述:
int Index (String S, String T, int pos)
{//T为非空串。若主串S中第pos个字符之后存在与T相等的子串
//则返回第一个这样的子串在S中的位置,否则返回0
if(pos>0)
{
n = StrLength(S);
m = StrLength(T);
i= pos;
while (i <= n-m+1)//到字符串S的最后只剩长度为m-1的字符串的话就不用再进行比较了
{
SubString (sub, S, i, m);//从第i个字符开始查找长度为m的子串
if (StrCompare(sub,T) != 0) //将子串与字符串T相比较,不相等则到下一个字符的位置查找长度为m的子串
++i;
else return i ;//相等则返回第一个子串在S中的第一个字符的下标
}
return 0;//S中不存在与T相等的字串
}
(3)串与线性表的区别
●串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。
●串的基本 *** 作和线性表有很大差别。
•在线性表的基本 *** 作中,多以“单个元素”作为 *** 作对象;
•在串的基本 *** 作中,通常以“串的整体”作为 *** 作对象。
二、串的表示和实现
串与线性表一样有两种主要的存储结构——顺序存储和链式存储。而链式存储里面又包括了定长顺序存储表示与堆分配存储表示。(可以理解为静态和动态分配的不同)
1、定长顺序存储表示 (1)串的顺序存储表示用一组地址连续的存储单元来存放串中的字符序列。
(2)串的定长顺序存储结构按照预定义的大小,为每个串变量各分配一个固定长度的存储区,通常用定长字符数组来实现。
例如:
#define Maxstrlen 255 //用户可用的最大串长
typedef unsigned char SString[ Maxstrlen + 1 ];//存储字符串的静态数组
SString s;//s是一个可容纳255个字符的顺序串
(3)特点:注:
·一般用SString[0]来存放串长信息;
·C语言约定在串尾加结束符‘不计入串长’使 *** 作加速,但自动截断;
·若字符串超过Maxstrlen则上界预先给出(因为静态数组存不进去)
●串的实际长度可在这个预定义长度的范围内随意设定,超过予定义长度的串值则被舍去,称之为"截断"。
●按这种串的表示方法实现串的运算时,其基本 *** 作为“字符序列的复制”。
●存储特点:三种情况
(4)在定长顺序存储下串的基本 *** 作实现①串联接Contcat(&T,S1,S2)
由于存储空间是固定的,所以在考虑S1和S2的联结的时候要分Status Concat(SString S1, SString S2, SString &T)
{
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;//是否截断的标志
}
else if (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[0]=MAXSTRSIZE截断(仅取S1)
{
T[0...MAXSTRLEN] = S1[0...MAXSTRLEN];// T[0] == S1[0] == MAXSTRLEN
uncut = FALSE;
}
return uncut;
}
进行讨论,即两个字符串相加的长度与数组最大长度的比较。
具体算法描述:
(注:串Sub的预留长度与S一样)
②求字串SubString(&Sub,S,pos,len)——将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中动态分配
具体算法描述:
Status SubString(SString &sub, SString S, int pos, int len)
{
if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
return ERROR;//pos不合法则警告
Sub[1......len]=S[pos.....pos+len-1];
Sub[0]=len;
return OK;
}
2、堆分配存储表示
(1)堆分配存储特点
仍用一组连续的存储单元来存放串,但存储空间是在程序执行过程中malloc函数而得。
思路——利用realloc函数合理预设串长空间。
若在 *** 作中串值改变,还可以利用增加(堆砌)空间按新串长度typedef struct {
char*ch;∥若是非空串,则按串长分配存储区,否则ch为NULL
int length;//串长度
}HString;
。
●C语言中,利用malloc()和free()等动态存储管理函数来实现
●串 *** 作仍是基于“字符序列的复制”进行的。
●定长顺序存储和堆分配存储都是高级语言中常用的。
●堆存储结构既有顺序存储结构的特点,处理方便, *** 作中对串长又没有任何限制,更灵活,因此也常被采用。
先为新生成的串分配一个存储空间,然后进行串值的复制
这类串 *** 作实现的算法为——int Concat(Hstring&T,HStringS1,HstringS2)
{ //用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 1;
}
。
(4)在堆分配存储下串的基本 *** 作实现
①串联接
具体算法描述:
单链表
②取子串
具体算法描述:
int SubString(HString&Sub,HstringS,intpos,int len)
{ //用Sub返回串S的第pos个字符起长度为len的子串。
//其中1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
if (pos<1||pos>S.length||len<0||len>S.length-pos+1)//位置pos或长度len不合理
return 0;
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.ch[pos-1...pos+len-2];
Sub.length=len;
}
return 1;
}
3、串的块链存储方式(链式存储)
(1)块链存储方式
用存储密度=数据元素所占存储位 / 实际分配的存储位来存储串值。每个结点存放一个或多个字符。便于进行插入和删除运算,但空间利用率太低。
存储密度计算——块链结构
法1存储密度为 1/2; 法2存储密度为 9/15=3/5。
显然,若数据元素很多,用法2存储更优——称为#define CHUNKSIZE 80 //可由用户定义的块大小
//首先定义结点类型
typedef struct Chunk {
char ch[CHUNKSIZE];//结点中的数据域
struct Chunk * next ;//结点中的指针域
}Chunk;
//其次定义用链式存储的串类型
typedef struct{
Chunk *head;//头指针
Chunk *tail;//尾指针
int curLen;//结点个数
} Lstring; //串类型只用一次,前面可以不加Lstring
子串定位运算
(3)特点·设尾指针的目的是为了便于进行联结 *** 作
·当结点大小超过1时,联结时应注意需处理第一个串尾的无效字符
●结点大小的选择,直接影响串的处理效率
●串的字符集大小影响串值的存储方式的选取——字符集小,则字符的机内编码就短。
●串值的链式存储vs.顺序存储
•联接、插入 *** 作等有一定方便之处;但结点大小超过1时同样需要移动元素,失去链式存储的优势
•总体上不如顺序存储结构灵活,占用存储量大且 *** 作复杂。
三、串的模式匹配算法
模式匹配——即模式串(Index函数),其中子串被称为模式检测。
模式匹配的分类
●模式定位——只关心是否存在匹配而不关心具体匹配位置,比如垃圾邮件过滤
●模式计数——不仅要判断是否存在匹配,还需要确定具体匹配位置,比如带毒文件的鉴别与修复
●模式枚举——需要统计匹配子串总数,比如网络热词排行榜的更新
●初始条件——需要报告所有匹配的具体位置,比如浏览器和文本编辑器中的查找功能
算法目的——确定主串中所含子串第一次出现的位置(定位)——即如何实现Index(S,T,pos)函数
*** 作结果:串S和T存在,T是非空串,1≤pos≤StrLength(s)
注:S称为被匹配的串,T称为模式串。若S包含串T,则称“匹配成功”,否则称“匹配不成功”。通常,主串和模式串的长度都很大,即2 << StrLength(T) << StrLength(S):若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。
相等
回顾:用最小 *** 作集实现穿定位Index(S,T,int pos)
int Index (String S, String T, int pos)
{//T为非空串。若主串S中第pos个字符之后存在与T相等的子串
//则返回第一个这样的子串在S中的位置,否则返回0
if(pos>0)
{
n = StrLength(S);
m = StrLength(T);
i= pos;
while (i <= n-m+1)//到字符串S的最后只剩长度为m-1的字符串的话就不用再进行比较了
{
SubString (sub, S, i, m);//从第i个字符开始查找长度为m的子串
if (StrCompare(sub,T) != 0) //将子串与字符串T相比较,不相等则到下一个字符的位置查找长度为m的子串
++i;
else return i ;//相等则返回第一个子串在S中的第一个字符的下标
}
return 0;//S中不存在与T相等的字串
}
1、BF算法(经典的、朴素的、穷举的)
(1)算法设计思想
●将主串的第pos个字符和模式的第一个字符比较,若不等,继续逐个比较后续字符;若(其实就是你求这一个字符的next,就看前面的所有字符是否有真前缀和真后缀,有的话就在真前缀的长度上+1,比如下面的字符串中,第三位a前面是ab,没有前缀后缀,所以它的next为1,而第四位a前面为aba,有真前缀a和真后缀a,其实也就是有对称部分,然后前缀长为1,所以它的next为1+1=2;第五位b前面是abaa,也只有a和a对称,所以它的next为2,而第六位c前面是abaab,前后对称部分为ab,所以它的next为3)。(注意,找对称要求是ab和ab而不能是ab和ba),从主串的下一字符起,重新与模式的第一个字符比较。
●直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。
●否则,匹配失败,返回值0
int Index(SString S, SString T, int pos)
{
i=pos; j=1;
while(i<=S[0] && j<=T[0])
{
if(S[i]==T[j]){++i,++j}//继续比较后续字符j
else {i=i-j+2; j=1;}//指针回溯到下一首位,重新开始匹配;相当于子串向右滑动一个字符位置
}
if(j>T[0]) return i-T[0];//子串结束,成功,返回匹配的第一个字符位置;匹配成功后指针仍要回溯!因为要返回的是被匹配的首个字符位置。
else return 0;
}
时间复杂度通常为O(n+m)
2、KMP算法(特点:速度快) (1)算法设计思想(2)算法的推导过程
关于前缀和后缀:
前缀——起始于位置1的子串
后缀——终止于位置n的子串
●空串是任意串的前缀和后缀,任意串也是它自身的前缀和后缀。
字符串本身之外的所有非空子串、前缀和后缀,分别称为真子串、真前缀、真后缀。
例如:A=‘This is a string’ 、B=‘Th’、C=‘This’、D=‘string’、E=‘g'
next[j]求法示例:
void get_next(SString T, int next[])
{
i= 1; next[1]= 0; j= 0;
while(i
练习:
匹配过程
(3)算法的实现(关键:计算next[j])第一步,先把模式T所有可能的失配点j所对应的nextJj]计算出来;
第二步:执行定位函数index_kmp(与BF算法模块非常相似)
具体算法描述:
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];}//S的i指针不回溯,从T的k位置开始匹配
}
if(j>T[0]) return i-T[0];//子串结束,说明匹配成功
else return 0;
}
求next函数
(其实就是在求出next的基础上,根据next去找对应的字符,如果相等自身的nextval就等于对应字符的nextval的值,如果不等则nextval=next。例如第五位是a,它的next是2,则找第二个位置的字符是b不相等,所以它的nextval=next=2;第12位是a,它的next是4,则找第四个位置的字符是a,相等,所以nextval(12)=nextval(4)=0)
next函数的改进
举例
void get_nextval(SString T, int &nextval[])
{
i= 1; nextval[1] = 0; j = 0;
while(i
求nextval具体算法
(4)算法的时间复杂度 (5)练习
总结
本文主要介绍数据结构(C语言版)第四章串的内容,主要包括串类型的定义、串的表示和实现、串的模式匹配算法。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)