文章目录
前言
T_T此专栏用于记录数据结构及算法的（痛苦）学习历程，便于日后复习（这种事情不要啊）。所用教材为《数据结构 C语言版 第2版》严蔚敏。
一、顺序串的具体实现
有关串的相关概念见串的概念及定义，下面给出串的顺序存储结构的基本操作的具体实现。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
using namespace std;
#define maxlen 255
#define ok 1
#define fail 0
#define true 1
#define false 0
#define Not_Exist -1
#define overflow -2
typedef int Status;
typedef struct {
char *ch;
int length;
}HString;
//初始化，创建空主串S
Status StrAssign(HString& S)
{
S.ch = new char[maxlen + 1];
S.length = 0;
return ok;
}
//初始化，创建空主串S
Status StrValueInit(HString& S,const char* chars)
{
strcpy(S.ch, chars);
S.length = strlen(S.ch);
return ok;
}
//由串S复制得到串T
Status StrCopy(HString S, HString& T)
{
if (!S.ch)return Not_Exist;
strcpy(T.ch, S.ch);
T.length = strlen(T.ch);
return ok;
}
//判断串S是否为空
Status StrEmpty(HString S)
{
if (!S.ch)return Not_Exist;
if (!S.length)return true;
return false;
}
//比较两个串的值
Status StrCompare(HString S, HString T)
{
if (!S.ch || !T.ch)return Not_Exist;
return strcmp(S.ch, T.ch);
}
//返回串的长度
Status StrLength(HString& S)
{
if (!S.ch)return Not_Exist;
return S.length;
}
//清空串
Status ClearString(HString& S)
{
if (!S.ch)return Not_Exist;
S.length = 0;
return ok;
}
//将两个串联接成新串
Status Concat(HString& T, HString S1, HString S2)
{
if (!S1.ch || !S2.ch)return Not_Exist;
HString ch1; StrAssign(ch1); StrCopy(S1, ch1);
T.ch = strcat(ch1.ch, S2.ch);
T.length = strlen(T.ch);
return ok;
}
// 用Sub返回串s的第pos个字符起长度为len的子串
Status SubString(HString& Sub,HString S,int pos,int len)
{
if (!S.ch)return Not_Exist;
if (pos<1 || pos>S.length)return fail;
if (len<0 || len>S.length - pos + 1)return fail;
strncpy(Sub.ch, S.ch + pos - 1, len);
*(Sub.ch + len) = '\0';
Sub.length = len;
return ok;
}
//若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0
Status Index(HString S, HString T, int pos)
{
if (!S.ch || !T.ch)return Not_Exist;
if (T.length == 0)return fail;
if (pos<1 || pos>S.length)return fail;
return strstr(S.ch + pos - 1, T.ch) - S.ch + 1;
}
//用V替换主串S中出现的所有与T相等的不重叠的子串
Status Replace(HString& S, HString T,HString V)
{
if (!S.ch || !T.ch || !V.ch)return Not_Exist;
if (!T.length)return fail;
char * pos = strstr(S.ch, T.ch);
char * ch1=new char[maxlen+1];
while (pos)
{
strcpy(ch1, pos + T.length);
strcpy(pos, V.ch);
strcpy(pos + V.length, ch1);
pos = strstr(pos + V.length, T.ch);
}
S.length = strlen(S.ch);
delete[] ch1;
return ok;
}
//从串s中第pos个字符起插入长度的子串T
Status StrInsert(HString& S, int pos, HString T)
{
if (!S.ch || !T.ch)return Not_Exist;
if (pos<1 || pos>S.length + 1)return fail;
char * ch1 = new char[maxlen + 1];
strcpy(ch1, S.ch+pos-1); //保存第pos个字符右边的字符
strcpy(S.ch + pos - 1, T.ch); //插入T
strcpy(S.ch + pos - 1 + T.length, ch1); //在T的尾部加上原本在第pos个字符右边的字符
S.length = S.length + T.length;
delete[] ch1;
return ok;
}
//从串s中删除第pos个字符起长度为len的子串
Status StrDelete(HString& S, int pos, int len)
{
if (!S.ch)return Not_Exist;
if (pos<1 || pos>S.length)return fail;
if (len<1 || len>S.length - pos + 1)return fail;
char* ch1 = new char[maxlen + 1];
strcpy(ch1, S.ch + pos + len - 1);
strcpy(S.ch + pos - 1, ch1);
S.length = S.length - len;
delete[] ch1;
return ok;
}
//获取next数组
Status GetNext(HString S,int next[])
{
int i = 1, j = 0;
next[1] = 0;
while (i < S.length)
{
if (j == 0 || *(S.ch + i - 1) == *(S.ch + j - 1))
{
++i; ++j; next[i] = j;
}
else j = next[j];
}
return ok;
}
//获取nextval数组
Status GetNextval(HString S, int nextval[])
{
int i = 1, j = 0;
nextval[1] = 0;
while (i < S.length)
{
if (j == 0 || *(S.ch + i - 1) == *(S.ch + j - 1))
{
++i; ++j;
if (*(S.ch + i - 1) != *(S.ch + j - 1))
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else j = nextval[j];
}
return ok;
}
//KMP算法，利用模式串 T 的 nextval 函数求 T 在主串 S 中第 pos 个字符之后的位置
Status KMP(HString S,HString T,int pos,int nextval[])
{
if (!S.ch || !T.ch)return Not_Exist;
if (pos<1 || pos>S.length + 1)return fail;
int i = pos, j = 1;
while (i <= S.length && j <= T.length)
{
if (j == 0 || *(S.ch + i - 1) == *(T.ch + j - 1))
{
++i; ++j;
}
else j = nextval[j];
}
if (j > T.length)return i - T.length;
return 0;
}
HString s,t,q,sub;
int nextval[maxlen];
int main() //测试程序
{
StrAssign(s); StrAssign(t); StrAssign(q); StrAssign(sub);
StrValueInit(s, "abcbbcc");puts(s.ch);
StrCopy(s, t);puts(t.ch);
cout << StrEmpty(s) << endl;
cout << StrCompare(s, t) << endl;
Concat(q, s, t); puts(q.ch); puts(s.ch); puts(t.ch);
SubString(sub, s, 2, 2); puts(sub.ch);
cout << Index(s, sub, 3) << endl;
Replace(s, sub, t); puts(s.ch); cout << s.length << endl;
StrValueInit(t, "xyz"); StrInsert(s, 18, t); puts(s.ch); cout << s.length << endl;
StrDelete(s, 3, 2); puts(s.ch);
GetNextval(s, nextval);
cout << KMP(s, t, 1, nextval) << endl;
return 0;
}
测试现象：
二、串的模式匹配算法
1.BF算法
即暴力遍历法，思维简单，但时间效率低至O（n²）。
2.KMP算法
思维复杂，但时间效率高，为O（n）。
有关KMP算法的原理见KMP和next数组。（太复杂了，还是看大神的讲解吧）
//获取next数组
Status GetNext(HString S,int next[])
{
int i = 1, j = 0;
next[1] = 0;
while (i < S.length)
{
if (j == 0 || *(S.ch + i - 1) == *(S.ch + j - 1))
{
++i; ++j; next[i] = j;
}
else j = next[j];
}
return ok;
}
//获取nextval数组
Status GetNextval(HString S, int nextval[])
{
int i = 1, j = 0;
nextval[1] = 0;
while (i < S.length)
{
if (j == 0 || *(S.ch + i - 1) == *(S.ch + j - 1))
{
++i; ++j;
if (*(S.ch + i - 1) != *(S.ch + j - 1))
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else j = nextval[j];
}
return ok;
}
//KMP算法，利用模式串 T 的 nextval 函数求 T 在主串 S 中第 pos 个字符之后的位置
Status KMP(HString S,HString T,int pos,int nextval[])
{
if (!S.ch || !T.ch)return Not_Exist;
if (pos<1 || pos>S.length + 1)return fail;
int i = pos, j = 1;
while (i <= S.length && j <= T.length)
{
if (j == 0 || *(S.ch + i - 1) == *(T.ch + j - 1))
{
++i; ++j;
}
else j = nextval[j];
}
if (j > T.length)return i - T.length;
return 0;
}
总结
路漫漫其修远兮，吾将上下而摆烂。（希望明天还能记得原理5555…）
有任何疑问和补充，欢迎交流。（但我显然不会T_T）