2021-12-21 数据结构 期末复习机考之四 串

我反思了一下前两篇的问题，发现讲知识点还是要简明扼要

常见的字符串里的名词

空串：不含任何字符的串，串长度=0

空格串：仅由一个或多个空格组成的串

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

主串：包含子串的串。   如：A=’Shenzhen University’  B=’University’  A为主串，B为子串

位置：字符在主串中的序号。子串在主串中的位置以子串第一个字符在主串中的位置来表示。

串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。

模式匹配：确定子串在主串中首次出现的位置的运算

 在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、在串的某个位置上插入一个子串等。很少以字符为操作单位（否则和线性表没有区别）

最小操作集：      

这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。

怎么理解这个最小操作集？

例如判断串是否为空串的函数和判断串的字符个数（长度）的函数其实可以用同一个函数经过略微修改实现，比如我只需求串长，当长度=0即为空，本质上这两个函数都是求串长，则求串长是这两个操作的最小操作。

 右边五种是#include中已有的函数。左边五种是我们自己编写的函数，有这十个函数我们可以完成串的操作。

这是字符串的静态表示

而关于字符串的动态表示 

首先是堆的概念 。

关于查找子串

int Index(SString S, SString T, int pos) {
   // 返回子串T在主串S中第pos个字符之后的位置。若不存在，
    // 则函数值为-1。其中，T非空，0≤pos≤S.length-1)。
    i = pos;   j = 0;
    while (i <= s.length-1 && j <= t.length-1) {
      if (S.ch[i] == T.ch[j]) { ++i;  ++j; }   // 继续比较后继字符
      else { i = i-j+1;   j = 0; }     // 指针后退重新开始匹配
    }
   if (j ==t.length)  return  i-t.length;
   else return -1;
} // Index`                 

 朴素算法，优点是简单直接，缺点是时间复杂度高【最少m+n，最多m*n】

改进算法：KMP算法 —— 解决掉朴素算法的冗余比较

前置：next数组

什么是next数组？怎么求？我们另开一文来讲。机考复习我们直接上程序

本质上，next数组有两个版本，有模式串从j==1开始的，也有从j==0开始的，以上是从1开始，从零开始只需要将上述结果都-1即可。

求好了next数组，我们得以真正书写KMP算法，在上KMP算法之前，请看朴素算法，两者对比学习：

#include
#include
using namespace std;
//从pos位置开始，返回子串在主串中的位置
int BF(string M,string T,int pos)
{
	int i=pos;
	int j=0;
	int Mlen=M.length();//主串的范围[0,Slen)
	int Tlen=T.length();//子串的范围[0,Tlen)
 
	if(pos<0 && pos>Mlen)
		return -1;
 
	while(i=Tlen)
		return i-Tlen;
	else 
		return -1;
}
int main()
{
	string M="abcdefabcdx";
	string T="abcdx";
	cout< 
KMP算法正是从朴素算法改进而来：
 
#include
#include
using namespace std;
//返回子串T的next数组。注意数组作为形参是传的指针
int getnext(string T,int *next,int Tlong);

int KMP(string M,string T,int pos)
{
    int i=pos;
    int j=0;
    int Mlen=M.size();//主串的范围[0,Slen)
    int Tlen=T.length();//子串的范围[0,Tlen)


    int next[255];//定义next数组 new
    getnext(T,next,Tlen);//new



    if(pos<0 && pos>Mlen)
        return -1;

    while(i=Tlen)
        return i-Tlen;
    else
        return -1;
}
int main()
{
    string M="abcdefabcdx";
    string T="abcdx";
    cout< 
不过有点问题。
 
下面是验证通过版：
 
#include
#include
using namespace std;

int *getnext(string T);

int KMP(string M,string T)
{
   int i,j;
    int *next = getnext(T);



    for(i=0,j=0;i 
 
KMP算法改进先略。