---
title: "《数据结构》串"
date: 2023-07-30T19:34:35+08:00

---

## 串的定义和实现

### 定义
  * 串：字符串简称串，是由零个或多个字符组成的有限序列
  * 子串：串中任意多个连续的字符组成的子序列
  * 主串：包含子串的串
  * 某个字符在串中的序号称为该字符在串中的位置
  * 空格串：由一个或多个空格组成的串

### 定长顺序存储表示

```c

#define MAXLEN 255
typedef struct
{
    char ch[MAXLEN];
    int length;
}SString;

```

### 堆分配存储表示

```c

typedef struct
{
    char *ch;
    int length;
}SString;

```

### 块链存储表示

* 类似于线性表的链式存储结构
* 也可采用链表方式存储串值其中的节点称为块
* 最后一个节点占不满时，用#号填充

### 基本操作

|StrAssign(&T,chars)|赋值操作|
|---|---|
|StrCopy(&T,S)|赋值操作
|StrEmpty(S)|判空操作
|StrCompare(S,T)|比较操作
|StrLength(S)|求串长
|StrString(&Sub,S,pos,len)|求子串
|Concat(&T,S1,S2)|串联接
|Index(S,T)|定位操作
|ClearString(&S)|清空操作
|DestroyString(&S)|销毁串

## 串的模式匹配

* 模式匹配：子串的定位操作，求子串在主串中的位置

### 暴力匹配算法-BF算法

时间复杂度为O(mn)

![](../../images/408/《数据结构》栈、队列和数组/暴力匹配算法.jpg)

```c

int Index_BF(string s, string t)
{
    int i = 1, j = 1;
    int lens = s.length();
    int lent = t.length();
    while(i < lens && j < lent)
    {
        if(s[i] == t[j])
        {
            i++,j++;
            continue;
        }
        else
        {
            i = i - j + 2;//i指示主串S正在比较的字符位置
            j = 1;//j指示子串t正在比较的字符位置
        }
    }
    if (j == lent)
    {
        return i - j;
    }
    return -1;
}

```

### 模式匹配算法 - KMP算法

时间复杂度为O(m + n)

![](../../images/408/《数据结构》栈、队列和数组/模式匹配算法.jpg)

```c

void get_next(String T , int next[])//计算next数组
{
    int i =1,j = 0;
    next[1] = 0;
    while( i < T.length)
    {
        if( j ==0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

int Index_KMP(String S,String T,int next[])
{
    int i = 1, j = 1;
    while(i <= S.length && j <= T.length)//i永远不递减
    if ( j==0 || S.ch[i] == T.ch[j])//字符匹配成功，指针后移
    {
        ++i;
        ++j;
    }
    else //字符匹配失败，根据next跳过前面的一些字符
    {
        j = next[j];
    }
    if(j > T.length)//匹配
        return i - T.length;
    else
        return 0;
}

```