数据结构-串详解（字符串）（类C语言版）

目录

串的概念

概念

实例

串相等

串的类型定义与存储结构

类型定义

存储结构

串的顺序存储结构

串的链式存储结构

串的算法

BF算法

算法步骤

实例

 时间复杂度

KMP算法

串（String）——由零个或多个任意字符组成的有限序列。

空串用∅表示。

子串：串中任意个连续字符组成的子序列称为该串的子串。

主串：包含子串的串相应地称为主串。

字符位置：字符在序列中的序号为该字符在串中的位置。

子串位置：子串第一个字符在主串中的位置。

空格串：由一个或多个空格组成的串，与空串不同。

字符串a、b、c、d

a='BEI'

b='JING'

c='BEIJING'

d='BEI JING'

它们的长度分别是：3、4、7、8

c的子串是：a、b

d的子串是：a、b

a在c中的位置是：1

a在d中的位置是：1

b在c中的位置是：4

a在d中的位置是：5

当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。

如："abcd" ≠ "abc"

所有空串是相等的。

ADT String {

        数据对象：D={ai | ai∈CharacterSet, i=1,2,...,n, n ≥ 0}

        数据关系：R1={|ai-1,ai∈D.i=1,2,...,n}

}

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN+1];    // 存储串的一维数组
    int length;           // 串的当前长度
}SString;

 优点： *** 作方便

缺点：存储密度较低

存储密度=串值所占的存储/实际分配的存储。

解决其存储密度低的方案：可将多个字符存放在一个结点中。

// 串的链式存储结构——块链结构
#define CHUNKSIZE 80    // 块的大小可由用户定义
typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
} Chunk;

typedef struct {
    Chunk *head, *tail;    // 串的头指针和尾指针
    int curlen;            // 串的当前长度
}LString;                  // 字符串的块链结构

算法目的：

        确定主串中所含子串（模式串）第一次出现的位置（定位）。

算法应用：

        搜索引擎、拼写检查、语言翻译、数据压缩

算法种类：

        · BF算法（Brute-Force，又称古典的、经典的、朴素的、穷举的）。

        · KMP算法（特点：速度快）

① 分别利用计数指针 i 和 j 指示主串 S 和模式 T中当前正待比较的字符位置， i 初值为pos, j 初值为1。
② 如果两个串均未比较到串尾， 即 i 和 j 均分别小于等于S和T的长度时，则循环执行以下 *** 作：
• S[i].ch和T[j].ch比较，若相等，则i和j分别指示串中下个位置， 继续比较后续字符；
• 若不等，指针后退重新开始匹配， 从主串的下一个字符 (i=i-j+2) 起再重新和模式的第一个字符 (j=1) 比较。
③ 如果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 0;                          //匹配失败
}

S= "aaaaaba "

T= "ba"

例：S='0000000001'，T='0001'，pos=1

若n为主串长度，m为子串长度，最坏情况是：

· 主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次。

· 最后m位也各比较了1次。

总次数为：(n-m)*m+m = (n-m+1)*m

若m< KMP算法

// 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]) { ++ 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=1;next[l]=0;j=0; 
    while (i 

// 计算 next 函数修正值
void get_nextval(SString T, int nextval[]) 
{ // 求模式串 T 的 next 函数修正值并存入数组 nextval
    i=1;nextval[1] =0; j=0; 
    while(i