[C++知识库]数据结构_串_基本操作的c++实现

#include <iostream>

using namespace std;

//串
/*-------------------串的顺序存储------------------------*/
//定义----静态数组实现--------（定长顺序存储）
#define MAXLEN 255     //预定义最大串长为255
typedef struct{
    char ch[MAXLEN];     //每个分量存储一个字符
    int length;         //串的实际长度
}SString;

//定义----动态数组实现--------（堆分配存储）-------变长
typedef struct{
    char *ch;        //按串长分配存储区，ch指向串的基地址
    int length;      //串的长度
}HString;
//叫做堆分配存储是因为：malloc函数申请的一片连续空间是属于内存空间中的“堆区”，系统不会自动回收，必须手动free()。其本质仍然是一个动态数组

/*-------------------串的链式存储------------------------*/
typedef struct StringNode{
    char ch[4];    //每个结点存多个字符(因为在32位的计算机中，一个next结点占4B，若每个结点只存放一个字符，也就是1B，则存储密度太低！！)
    struct StringNode *next;
}StringNode,*String;

/*---------------------------串的基本操作----------------------*/
//求子串。用Sub返回串S的第pos个字符起长度为len的子串
bool SubString(SString &Sub, SString S,int pos, int len){
    //子串范围越界
    if(pos+len-1>S.length)
        return false;
    for(int i=pos;i<pos+len;i++)
        Sub.ch[i-pos+1] = S.ch[i];
    Sub.length=len;
    return true;
}

//比较操作。若S>T，则返回值>0;若S=T，则返回值=0;若S<T，则返回值<0。
int StrCompare(SString S, SString T){
    for(int i=0;i<S.length&&i<T.length;i++){
        if(S.ch[i]!=T.ch[i])
            return S.ch[i]-T.ch[i];
    }
    return S.length-T.length;   //扫描过的所有字符都相同，则长度更长的串更大
}

//定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
int Index(SString S, SString T){
    int i=1,n=S.length,m=T.length;
    SString sub;//用于暂存子串
    while(i<=n-m+1){
        SubString(sub,S,i,m);
        if(StrCompare(sub,T)!=0)
            ++i;
        else
            return i;   //返回子串在主串中的位置
    }
    return 0;//S中不存在与T相等的子串
}

/*-----------------串的模式匹配（即子串的定位）-----------------------*/
//朴素模式匹配算法
int Index_1(SString S,SString T){
    int k=1;
    int i=k,j=1;
    while(i<=S.length&&j<=T.length){
        if(S.ch[i]==T.ch[j]){
            ++i;
            ++j;
        }else{
            k++;
            i=k;
            //或者i=i-j+2;         (i-j倒退回当前检查串的起始地址的前一个，然后+2)
            j=1;
        }
    }
    if(j>T.length)
        return k;
    else
        return 0;
}

//KMP算法
void get_next(SString T,int next[]);  //函数声明
int Index_KMP(SString S,SString T){
    int i=1,j=1;
    int next[T.length+1];
    get_next(T,next);
    while(i<=S.length&&j<=T.length){
        if(j==0||S.ch[i]==T.ch[j]){   //!
            ++i;
            ++j;                   //继续比较后继字符
        }
        else
            j=next[j];             //!模式串向右移动
    }
    if(j>T.length)
        return i-T.length;        //匹配成功
    else
        return 0;
}
//求模式串T的next数组
void get_next(SString T,int next[]){
    int i=1,j=0;
    next[i]=0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i;++j;
            //若pi=pj，则next[j+1]=next[j]+1
            next[i]=j;
        }
        else
            //否则令j=next[j]，循环继续
            j=next[j];
    }
}

void get_nextval(SString T,int next[]);

int main()
{
    cout << "Hello world!" << endl;
    return 0;
}