一、串顺序存储
1、定义
- 静态数组实现
#define MAXLEN 255
typedef struct {
char ch[MAXLEN];
int length;
}SString;
- 动态数组实现
typedef struct {
char* ch; //按串长分配存储区间
int length;
}HString;
2、初始化(下面都用静态数组实现)
void InitString(SString& S) {
S.length = 0;
}
3、赋值操作
bool StrAssign(SString& T, char* chars) {
while (true)
{
if (chars[T.length]) {
T.ch[T.length] = chars[T.length];
T.length++;
}
else
{
break;
}
}
return true;
}
4、复制操作
bool StrCopy(SString& T, SString S) {
for (int i = 0; i < S.length; i++) {
T.ch[i] = S.ch[i];
}
T.length = S.length;
return true;
}
5、判空
bool StrEmpty(SString S) {
if (S.length == 0)
return true;
else
return false;
}
6、求串长
int StrLength(SString S) {
return S.length;
}
7、清空操作
bool ClearString(SString& S) {
for (int i = 0; i < S.length; i++) {
S.ch[i] = NULL;
}
S.length = 0;
return true;
}
8、串连接
bool Concat(SString& T, SString S1, SString S2) {
for (int i = 0; i < S1.length; i++) {
T.ch[i] = S1.ch[i];
}
for (int i = S1.length; i < S1.length + S2.length; i++) {
T.ch[i] = S2.ch[i - S1.length];
}
T.length = S1.length + S2.length;
return true;
}
9、求子串
bool SubString(SString& Sub, SString S, int pos, int len) {
if (pos + len - 1 > S.length) {
return false;
}
for (int i = pos - 1; i < pos + len-1; i++)
Sub.ch[i - pos + 1] = S.ch[i];
Sub.length = len;
return true;
}
10、比较
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;
}
11、定位
int Index(SString S, SString T) {
int i = 0, n = StrLength(S), m = StrLength(T);
SString sub;//暂存子串
InitString(sub);
while (i<n-m)
{
SubString(sub, S, i, m);
if (StrCompare(T, sub) != 0)
i++;
else
return i;
}
return -1;
}
二、链式存储
1、定义
typedef struct StringNode {
char ch;
struct StringNode* next;
}StringNode, *String;
2、提高存储密度的定义
typedef struct StringNode {
char ch[4];
struct StringNode* next;
}StringNode, *String;
三、匹配算法
1、朴素模式匹配
int Index(SString S, SString T) {
int i = 1, j = 1;
while (i <= S.length && j <= T.length) {
if (S.ch[i] == T.ch[j]) {
i++;
j++;
}
else {
i = i - j + 2;
j = 1;
}
}
if (j > T.length)
return i - T.length;
else
return 0;
}
2、KMP
1)求next
void next(SString T, int* nexts) {
nexts[1] = 0;
nexts[2] = 1;
for (int i = 3; i <= T.length; i++) {
int j = i - 3;
int count = 0;
int temp_i = i-1;
while (j>0)
{
if (T.ch[temp_i] == T.ch[j]) {
count++;
temp_i--;
j--;
}
else
{
count = 0;
j--;
temp_i = i-1;
}
}
if (count == 0)
nexts[i] = 1;
else
nexts[i] = count+1;
}
}
2)优化KMP(优化next)求nextval
void nextval(SString T, int* nexts, int* nextvals) {
nextvals[1] = 0;
for (int i = 2; i <= T.length; i++) {
if (T.ch[i] == T.ch[nexts[i]])
nextvals[i] = nextvals[nexts[i]];
else
nextvals[i] = nexts[i];
}
}
3)KMP算法实现
int Index_KMP(SString S, SString T, int next[]) {
int i = 1, j = 1;
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;
}