数据结构基础讲解（六）——串的专项练习

本文数据结构讲解参考书目：

通过网盘分享的文件：数据结构  C语言版.pdf
链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码: ze8e

数据结构基础讲解（五）——队列专项练习-CSDN博客

个人主页：樱娆π-CSDN博客

目录

串的定义

串的类型定义、 存储结构及其运算

串的抽象数据类型的定义

基本操作

串的存储结构

顺序存储结构

链式存储结构

串的橾式匹配算法

BF 算法

【算法步骤】

【算法描述】

KMP算法

【算法描述】

计算 next 函数值

【算法描述】

算法举例说明

串的定义

串(string)(或字符串）是由零个或多个字符组成的有限序列，一般记为:

                                            s= "a1 a2 … an" (n>=0) 

其中，s是串的名， 用双引号括起来的字符序列是串的值；ai(0<=i<=n)可以是字母、 数字 或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串(null string) , 其长度为零。

串中任意个连续的字符组成的子序列称为该电的子串。包含子串的串相应地称为主串。 通常 称字符在序列中的序号为该字符在串中的位置。 子串在主串中的位置则以子串的第一个字符在主 串中的位置来表示。

只有当两个串的长度相等， 并且各个对应位置的字符都相等时才相等。

一个或多个空格组成的串" "称为空格串 (blank string, 请注意：此处不是空串）， 其长度为串 中空格字符的个数。

串的类型定义、 存储结构及其运算

串的抽象数据类型的定义

ADT String{ 数据对象： D= { ai I ai 含于 CharacterSet, i=1, 2, …, n, n>=0}

数据关系： R1= {< ai-1,ai> l ai-1 , ai含于D,i=2, …，n}

基本操作:

}ADT String

基本操作

串的存储结构

与线性表类似， 串也有两种基本存储结构：顺序存储和链式存储。但考虑到存储效率和算法 的方便性， 串多采用顺序存储结构。

顺序存储结构

//－－－－－ 串的定长顺序存储结构－ － －－－
#define MAXLEN 255 
typedef struct { 
char ch[MAXLEN+l); 
int length; 
) SString; 

 其中，MAXLEN 表示串的最大长度，ch是存储字符串的一维数组，每个分量存储一个字符，length 表示字符串的当前长度。 为了便千说明问题， 本章后面算法描述当中所用到的顺序存储的字符 串都是从下标为1的数组分量开始存储的， 下标为0的分量闲置不用

链式存储结构

顺序串的插入和删除操作不方便，需要移动大量的字符。 因此,可采用单链表方式存储串。 由于串结构的特殊性一结构中的每个数据元素是一个字符，则在用链表存储串值时，存在一个 “结 点大小＂ 的问题，即每个结点可以存放一个字符，也可以存放多个字符。

//－－－－－ 串的链式存储结构－ － －－－
#define CHUNKSIZE BO       //可由用户定义的块大小
typedef struct Chunk{ 
char ch [ CHUNKSIZE];
struct Chunk *next; 
) Chunk; 
typedef struct{ 
Chunk *head,*tail; 
int length; 
) LString; 

       在链式存储方式中，结点大小的选择直接影响着串处理的效率。 在各种串的处理系统中，所 处理的串往往很长或很多，如一本书的几百万个字符，情报资料的成千上万个条目，这就要求考 虑串值的存储密度。

       显然，存储密度小（如结点大小为1时），运算处理方便，然而，存储占用最大。如果在串处 理过程中需进行内、 外存交换的话， 则会因为内外存交换操作过多而影响处理的总效率。 应该 看到，串的字符集的大小也是一个重要因素。 一般来说，字符集小，则字符的机内编码就短，这 也影响串值存储方式的选取  

       串值的链式存储结构对某些串操作，如联接操作等，有一定方便之处，但总地说来，不如顺 序存储结构灵活，它占用存储量大且操作复杂。

串的橾式匹配算法

BF 算法

最简单直观的模式匹配算法是 BF (Brute-Force) 算法

【算法步骤】

(1)分别利用计数指针 l 和）指示主串 S 和模式 T中当前正待比较的字符位置， i初值为pos, j初值为

(2)如果两个串均未比较到串尾， 即i和j均分别小于等于S和T的长度时，则循环执行以下 操作：

1.          S[i].ch和T[j].ch比较，若相等，则i和j分别指示串中下个位置， 继续比较后续字符
2.          若不等，指针后退重新开始匹配， 从主串的下一个字符 (i=i-j+2) 起再重新和模式的 第一个字符 (j=1) 比较

(3)如果j> T.length, 说明模式T中的每个字符依次和主串S中的一个连续的字符序列相等， 则匹配成功，返回和模式T中第一个字符相等的字符在主串S中的序号(i-T.length); 否则称匹配 不成功，返回0

【算法描述】

int Index_BF(SString S,SString T,int pos} 
｛//返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在， 则返回值为0
//其中，T非空，1<=pos<=s.length
i=pos; j=l; //初始化
while (i < =S. length && j < =T. length) / /两个串均未比较到串尾
｛ 
if(S[i] .ch==T[j] .ch) {++i;++j;} //继续比较后继字符
else{i=i-j+2;j=l;} //指针后退重新开始匹配
if (j > T. length) return i-T. length; //匹配成功
else return O;
}

KMP算法

这种改进算法是由 Knuth 、 Morris 和 Pratt 同时设计实现的， 因此简称 KMP 算法

【算法描述】

int Index_KMP(SString S,SString T,int pos)
{//利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置
//其中，T非空， 1.;;;pos.;;;s. length 
i=pos;j=l; 
while (i < =S. length && j < =S. length) 
{

if (j == 0 || s [ i ] ==T [ j ])l { ++ i ; ++ j ; }
else j=next[j];
}
if (j > T [ 0]) return i-T [ 0] ; 
else return 0;
}

计算 next 函数值

【算法描述】

void get_next(SString T,int next[)) 
{//求模式串 T的 next 函数值并存入数组 next
i=l;next[l)=O;j=O; 
while (i <T[O]) 
｛ 
if(j==O II T[i)==T[j)) {++i;++j;next[i)=j; I 
else j=next[j);
}
}

算法举例说明

1.假设你有一个文本串 mississippi 和一个模式串 issi，使用 BF 算法找出模式串在文本串中的所有出现位置。

def bf_match(text, pattern):  
  """  
  BF 算法实现  

  Args:  
    text: 文本串  
    pattern: 模式串  

  Returns:  
    匹配位置列表  
  """  
  n = len(text)  
  m = len(pattern)  
  matches = []  
  for i in range(n - m + 1):  
    j = 0  
    while j < m and text[i + j] == pattern[j]:  
      j += 1  
    if j == m:  
      matches.append(i)  
  return matches  

# 测试用例  
text = "mississippi"  
pattern = "issi"  
matches = bf_match(text, pattern)  
print(f"匹配位置：{matches}")

2.假设你有一个文本串 ababaca 和一个模式串 abaca，使用 KMP 算法找出模式串在文本串中的所有出现位置

def build_next(pattern):  
  """  
  构建 next 数组  

  Args:  
    pattern: 模式串  

  Returns:  
    next 数组  
  """  
  m = len(pattern)  
  next = [-1] * m  
  j = -1  
  for i in range(1, m):  
    while j >= 0 and pattern[i] != pattern[j + 1]:  
      j = next[j]  
    if pattern[i] == pattern[j + 1]:  
      j += 1  
    next[i] = j  
  return next  

def kmp_match(text, pattern):  
  """  
  KMP 算法实现  

  Args:  
    text: 文本串  
    pattern: 模式串  

  Returns:  
    匹配位置列表  
  """  
  n = len(text)  
  m = len(pattern)  
  next = build_next(pattern)  
  matches = []  
  i = 0  
  j = 0  
  while i < n:  
    while j >= 0 and text[i] != pattern[j + 1]:  
      j = next[j]  
    if text[i] == pattern[j + 1]:  
      j += 1  
    if j == m - 1:  
      matches.append(i - m + 1)  
      j = next[j]  
    i += 1  
  return matches  

# 测试用例  
text = "ababaca"  
pattern = "abaca"  
matches = kmp_match(text, pattern)  
print(f"匹配位置：{matches}")

通过这个例题，我们可以更直观地理解 KMP 算法的工作原理。它通过构建 next 数组来记录模式串中每个位置的前缀和后缀的最长公共前缀长度，并利用 next 数组指导模式串在文本串中的移动，避免了不必要的回溯，从而提高了匹配效率。

————由于博主还是大三的在读生，时间有限，每天会不定时更新一些学习经验和一些32的项目，如果喜欢就点点关注吧，大佬们！！！！————