Error[8]: Undefined offset: 57, File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 121
File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 473, decode(

文章目录

前言

一、串类型的定义

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叫主串。
子串位置——子串的第一个字符在主串中(首次出现)的位置
字符位置——字符在串中的序号。
串相等——串长度相等,且对应位置上字符相等

练习:(加深理解)

2、串的抽象数据类型定义 (1)串的类型定义与运算(基本 *** 作)
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个字符的顺序串

注:
·一般用SString[0]来存放串长信息;
·C语言约定在串尾加结束符‘不计入串长使 *** 作加速,但自动截断
·若字符串超过Maxstrlen则上界预先给出(因为静态数组存不进去)

(3)特点:

●串的实际长度可在这个预定义长度的范围内随意设定,超过予定义长度的串值则被舍去,称之为"截断"。
●按这种串的表示方法实现串的运算时,其基本 *** 作为“字符序列的复制”。

●存储特点:三种情况

(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函数合理预设串长空间。

(2)特点

若在 *** 作中串值改变,还可以利用增加(堆砌)空间按新串长度typedef struct { char*ch;∥若是非空串,则按串长分配存储区,否则ch为NULL int length;//串长度 }HString;
●C语言中,利用malloc()和free()等动态存储管理函数来实现
●串 *** 作仍是基于“字符序列的复制”进行的。
●定长顺序存储和堆分配存储都是高级语言中常用的。
●堆存储结构既有顺序存储结构的特点,处理方便, *** 作中对串长又没有任何限制,更灵活,因此也常被采用。

(3)串的堆分配存储结构
先为新生成的串分配一个存储空间,然后进行串值的复制

这类串 *** 作实现的算法为——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

(2)块链存储结构
子串定位运算

·设尾指针的目的是为了便于进行联结 *** 作
·当结点大小超过1时,联结时应注意需处理第一个串尾的无效字符

(3)特点

●结点大小的选择,直接影响串的处理效率

●串的字符集大小影响串值的存储方式的选取——字符集小,则字符的机内编码就短。

●串值的链式存储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

(2)算法过程示意图

(3)具体算法描述: 
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语言版)第四章串的内容,主要包括串类型的定义、串的表示和实现、串的模式匹配算法。

)
File: /www/wwwroot/outofmemory.cn/tmp/route_read.php, Line: 126, InsideLink()
File: /www/wwwroot/outofmemory.cn/tmp/index.inc.php, Line: 166, include(/www/wwwroot/outofmemory.cn/tmp/route_read.php)
File: /www/wwwroot/outofmemory.cn/index.php, Line: 30, include(/www/wwwroot/outofmemory.cn/tmp/index.inc.php)
数据结构(C语言版)第四章 串_C_内存溢出

数据结构(C语言版)第四章 串

数据结构(C语言版)第四章 串,第1张

文章目录

前言

一、串类型的定义

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叫主串。
子串位置——子串的第一个字符在主串中(首次出现)的位置
字符位置——字符在串中的序号。
串相等——串长度相等,且对应位置上字符相等

练习:(加深理解)

2、串的抽象数据类型定义 (1)串的类型定义与运算(基本 *** 作)
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个字符的顺序串

注:
·一般用SString[0]来存放串长信息;
·C语言约定在串尾加结束符‘不计入串长使 *** 作加速,但自动截断
·若字符串超过Maxstrlen则上界预先给出(因为静态数组存不进去)

(3)特点:

●串的实际长度可在这个预定义长度的范围内随意设定,超过予定义长度的串值则被舍去,称之为"截断"。
●按这种串的表示方法实现串的运算时,其基本 *** 作为“字符序列的复制”。

●存储特点:三种情况

(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函数合理预设串长空间。

(2)特点

若在 *** 作中串值改变,还可以利用增加(堆砌)空间按新串长度typedef struct { char*ch;∥若是非空串,则按串长分配存储区,否则ch为NULL int length;//串长度 }HString;
●C语言中,利用malloc()和free()等动态存储管理函数来实现
●串 *** 作仍是基于“字符序列的复制”进行的。
●定长顺序存储和堆分配存储都是高级语言中常用的。
●堆存储结构既有顺序存储结构的特点,处理方便, *** 作中对串长又没有任何限制,更灵活,因此也常被采用。

(3)串的堆分配存储结构
先为新生成的串分配一个存储空间,然后进行串值的复制

这类串 *** 作实现的算法为——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

(2)块链存储结构
子串定位运算

·设尾指针的目的是为了便于进行联结 *** 作
·当结点大小超过1时,联结时应注意需处理第一个串尾的无效字符

(3)特点

●结点大小的选择,直接影响串的处理效率

●串的字符集大小影响串值的存储方式的选取——字符集小,则字符的机内编码就短。

●串值的链式存储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

(2)算法过程示意图

(3)具体算法描述: 
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语言版)第四章串的内容,主要包括串类型的定义、串的表示和实现、串的模式匹配算法。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1499134.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-25
下一篇 2022-06-25

发表评论

登录后才能评论

评论列表(0条)