【数据结构】第4章串、数组和广义表串和KMP算法

我会带着你远行 2022-11-28 10:43 154阅读 0赞

【串的顺序存储结构、堆式顺序存储结构、链式存储结构、模式匹配（BF算法和KMP算法）】

--------------------

串是内容受限的线性表  
嘿嘿嘿在B站找着俩视频：  
[动画理解][Link 1]和[手算做题][Link 2]

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int ElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //------串的顺序存储结构-----
    #define MAXLEN 225
    typedef struct 
    {
        
        char ch[MAXLEN + 1];    //存储串的一维数组，从下标为1的数组分量开始存储的，下标为0的分量闲置不用 
        int length;             //串的当前长度
    }SString;
    
    //------串的堆式顺序存储结构-----
    typedef struct 
    {
        
        char *ch;       //若是非空串，则按串长分配存储区，否则ch为NULL
        int length;     //串的当前长度
    }HString;
    
    HString S, T;
    
    //-----串的链式存储结构-----
    #define CHUNKSIZE 80
    typedef struct Chunk
    {
        
        char ch[CHUNKSIZE];
        struct Chunk *next;
    }Chunk;
    typedef struct
    {
        
        Chunk *head, *tail;     //串的头指针和尾指针
        int length;             //串的当前长度
    }LString;
    
    // //1、生成串
    // StrAssign(&T, chars)
    
    // //2、复制
    // StrCopy(&T, S)
    
    // //3、判空
    // StrEmpty(S)
    
    // //4、比较
    // StrCompare(S, T)
    
    // //5、长度
    // StrLength(S)
    
    // //6、清空
    // ClearString(&S)
    
    // //7、联接
    // Concat(&T, S1, S2)
    
    // //8、子串
    // SubString(&Sub, S, pos, len)
    
    //9、串的模式匹配_BF算法 O(n * m)
    int Index_BF(HString S, HString T, int pos)
    {
        //返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在，则返回值为0
     //其中，T非空，1<=pos<=S.length
        int i = pos, j = 1;                     //初始化
        while(i <= S.length && j <= T.length)   //两串均未比较到串尾
        {
        
            if(S.ch[i] == T.ch[j])              //继续比较后继字符
            {
        
                i++;
                j++;
            }
            else                                //指针后退重新开始匹配
            {
        
                i = i - j + 2;                  //i=i-j+1回到i的起点，+2到下一个字符
                j = 1;
            }
        }
        if(j > T.length)
                return i - T.length;            //匹配成功，返回T在S中第一次出现的位置
            else
                return 0;
    }
    
    //9、串的模式匹配_KMP算法求next数组
    void get_next(HString, int next[])
    {
        //求模式串T的next函数值并存入数组next
        int j = 1, t = 0;
        next[1] = 0;
        while(j < T.length)
        {
        
            if(t == 0 || T.ch[j] == T.ch[t])
            {
        
                t++;
                j++;
                next[j] = t;
            }
            else
                t = next[t];
        }
    }
    
    //9、串的模式匹配_KMP算法求nextval数组
    void get_nextval(HString T, int nextval[])
    {
        //求模式串T的next函数修正值并存入数组nextval
        int j = 1, t = 0;
        nextval[1] = 0;
        while(j < T.length)
        {
        
            if(t == 0 || T.ch[j] == T.ch[t])
            {
        
                t++;
                j++;
                if(T.ch[j] != T.ch[t])
                    nextval[j] = t;
                else
                    nextval[j] = nextval[t];
            }
            else
                t = nextval[t];
        }
    }
    
    //9、串的模式匹配_KMP算法 O(n + m)
    int Index_KMP(HString S, HString T, int pos, int next[])
    {
        //利用模式串T的next函数求T在主串S中第pos个字符之后的位置
     //其中，T非空，1<=pos<=S.length 
        int i = pos, j = 1;
        while(i <= S.length && j <= S.length)   //两个串均未比较到串尾
        {
        
            if(j == 0 || S.ch[i] == T.ch[i])    //继续比较后继字符
            {
        
                i++;
                j++;
            }
            else
                j = next[j];                    //模式串向右移动
            if(j > T.length)                    //匹配成功
                return i - T.length;
            else
                return 0;
        }
    }
    
    // //10、插入
    // Strlnsert(&S, pos, T) 
    
    // //11、删除
    // StrDelete(&S, pos, len)
    
    // //12、销毁
    // DestroyString(&S)

（1）串是一种特殊的线性表，其特殊性体现在（ ）。  
A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符若  
答案：B

（2）串下面关于串的的叙述中，（ ）是不正确的？  
A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储  
答案：B  
解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串， 零个字符的串成为空串，其长度为零。

（3）串“ ababaaababaa ”的 next 数组为（ ） 。  
A．012345678999 B．012121111212 C．011234223456 D．0123012322345  
答案：C

（4）串“ ababaabab”的 nextval为（ ）。 A．010104101 B．010102101 C．010100011 D．010101011  
答案：A

（5）串的长度是指（ ）。  
A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数  
答案：B  
解释：串中字符的数目称为串的长度

（1）已知模式串t=‘ abcaabbabcab’ 写出用 KMP法求得的每个字符对应的next 和 nextval 函数值。  
答案： ![在这里插入图片描述][20200817215144457.png_pic_center]

（2）设目标为 t=“ abcaabbabcabaacbacba” , 模式为p=“ abcabaa”  
① 计算模式 p 的 naxtval 函数值；  
② 不写出算法, 只画出利用 KMP算法进行模式匹配时每一趟的匹配过程。  
答案：  
① p 的 nextval 函数值为0110132。（p 的 next 函数值为 0111232）  
② 利用 KMP( 改进的 nextval) 算法，每趟匹配过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]

[Link 1]: https://www.bilibili.com/video/BV17i4y1t76L?p=34
[Link 2]: https://www.bilibili.com/video/BV1d54y1q7ko?from=search&seid=8481876313327245173
[20200817215144457.png_pic_center]: /images/20221124/2597ededa5234b808176e27199b15689.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/3d9b26a60fb54542a1a9ff040ea71a8c.png