串
2022-06-29 本文已影响0人
lxr_
1.串是由零个或者多个字符组成的有限序列，又名字符串(内容受限的线性表)
一般记为s="a1a2.....an",n为串的长度
2.空格串：只包含空格的串
3.空串：零个字符
4.子串与主串：串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串
5.子串在主串中的位置就是子串的第一个字符在主串中的序号
String.h
#pragma once
#include <iostream>
#include <string.h>
using namespace std;
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
#define MAXLEN 256
typedef char String[MAXLEN + 1]; //0号单元存放串的长度
//生成一个其值等于chars的串T
Status StrAssign(String T, const char* chars);
//打印字符串
void StrPrint(String T);
//由串S复制得到串T
Status StrCopy(String T, String S);
//S为空串返回true，否则返回false
bool StrEmpty(String S);
//比较串S和T大小，S>T,返回>0;S<T,返回<0；S=T,返回=0；
int StrCompare(String S, String T);
//返回串的元素个数
int StrLength(String S);
//初始条件：串S存在。将S清空为空串
void ClearString(String S);
//用T返回S1和S2连接而成的新串，若为截断，则返回TRUE，否则返回FALSE
bool Concat(String T, String S1, String S2);
//用Sub返回串S的第pos个字符起长度为len的子串
Status SubString(String Sub, String S, int pos, int len);
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回0
//其中，T非空，1<=pos<=StrLength(S);
int Index(String S, String T, int pos);
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回0
//其中，T非空，1<=pos<=StrLength(S);
int Index2(String S, String T, int pos);
//初始条件：串S和T存在，1<=pos<=StrLength(S)+1
//操作结果：在串S的第pos个字符之前插入串T，完全插入返回true,部分插入返回false
Status StrInsert(String S, int pos, String T);
//初始条件：串S和T存在，1<=pos<=StrLength(S)+1
//操作结果：在串S的第pos个字符之前插入串T，完全插入返回true,部分插入返回false
Status StrInsert2(String S, int pos, String T);
//初始条件：串S存在，1<=pos<=StrLength(S)-len+1
//操作：从S中删除第pos个字符起长度为len的子串
Status StrDelete(String S, int pos, int len);
//初始条件：串S,T和V存在，T是非空串，
//操作结果：用V替换主串S中出现的所有与T相等的不重叠
Status Replace(String S, String T, String V);
//计算子串T的next数组
void get_next(String T, int* next);
//求模式串T的next函数修正值并存入数组nextval
void get_nextval(String T, int* nextval);
//返回子串T在主串S中第pos个字符之后的位置，若不存在，则函数返回值为0
int Index_KMP(String S, String T, int pos);
String.cpp
#include "string.h"
//生成一个其值等于chars的串T
Status StrAssign(String T, const char* chars)
{
int i;
if (strlen(chars) > MAXLEN)
{
cout << "越界" << endl;
return ERROR;
}
else
{
T[0] = strlen(chars);
for (int i = 1; i <= T[0]; i++)
{
T[i] = *(chars + i - 1);
}
}
return OK;
}
//打印字符串
void StrPrint(String T)
{
for (int i = 1; i <= T[0]; i++)
{
cout << T[i];
}
cout << endl;
}
//由串S复制得到串T
Status StrCopy(String T, String S)
{
if (!S[0])
{
cout << "空串" << endl;
return ERROR;
}
T[0] = S[0];
for (int i = 1; i <= T[0]; i++)
{
T[i] = S[i];
}
return OK;
}
//S为空串返回true，否则返回false
bool StrEmpty(String S)
{
if (!S[0])
{
return true;
}
return false;
}
//串S和T必须存在：比较串S和T大小，S>T,返回>0;S<T,返回<0；S=T,返回=0；
int StrCompare(String S, String T)
{
for (int i = 1; i <= S[0] && i <= T[0]; i++)
{
if (S[i] != T[i])
{
return S[i] - T[i];
}
}
return S[0] - T[0];
}
//返回串的元素个数
int StrLength(String S)
{
return S[0];
}
//初始条件：串S存在。将S清空为空串
void ClearString(String S)
{
S[0] = 0;
}
//用T返回S1和S2连接而成的新串，若为截断，则返回TRUE，否则返回FALSE
bool Concat(String T, String S1, String S2)
{
StrCopy(T, S1); //将S1复制到T中
for (int i = T[0] + 1; i <= S1[0] + S2[0]; i++)
{
if (i > MAXLEN) //最多存储MAXLEN个元素
{
T[0] = MAXLEN;
return false;
}
T[i] = S2[i - T[0]];
}
T[0] += S2[0];
return true;
}
//用Sub返回串S的第pos个字符起长度为len的子串
Status SubString(String Sub, String S, int pos, int len)
{
if (pos + len > S[0] + 1 || pos < 1 || len < 0)
{
return ERROR;
}
Sub[0] = len;
for (int i = pos; i < pos + len; i++)
{
Sub[i - pos + 1] = S[i];
}
return OK;
}
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回0
//其中，T非空，1<=pos<=StrLength(S);
int Index(String S, String T, int pos)
{
if (pos<0 || pos>StrLength(S))
{
return 0;
}
for (int i = pos; i <= StrLength(S) - StrLength(T) + 1; i++)
{
for (int j = 1; j <= StrLength(T); j++)
{
if (S[j + pos] == T[j])
{
if (j == StrLength(T))
{
return i + 1;
}
}
else
{
break;
}
}
i = pos++;
}
return 0;
}
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回0
//其中，T非空，1<=pos<=StrLength(S);
int Index2(String S, String T, int pos)
{
int i = pos + 1;
int j = 1;
while (i <= S[0] - T[0] + 1 && j <= T[0])
{
String Sub;
SubString(Sub, S, i, StrLength(T)); //从S中截取与串T长度相等的子串
if (!StrCompare(Sub, T))
{
return i;
}
i++;
}
return 0;
}
//初始条件：串S和T存在，1<=pos<=StrLength(S)+1
//操作结果：在串S的第pos个字符之后插入串T，完全插入返回true,部分插入返回false
Status StrInsert(String S, int pos, String T)
{
if (pos<0 || pos>StrLength(S) + 1)
{
return false;
}
String Sub1;
SubString(Sub1, S, 1, pos); //截取插入位置前的子串
String Sub2;
if (S[0] + T[0] > MAXLEN)
{
SubString(Sub2, T, 1, MAXLEN - S[0]); //截取需要插入的子串
}
else
{
StrCopy(Sub2, T); //如果长度足够，插入整个串T
}
String Sub3;
SubString(Sub3, S, pos + 1, S[0] - pos); //截取最后一段子串
String S1;
StrAssign(S1, "");
Concat(S1, Sub1, Sub2);
ClearString(S);
Concat(S, S1, Sub3); //拼接在一起
return true;
}
//初始条件：串S和T存在，1<=pos<=StrLength(S)+1
//操作结果：在串S的第pos个字符之后插入串T，完全插入返回true,部分插入返回false
Status StrInsert2(String S, int pos, String T)
{
if (pos<1 || pos>StrLength(S) + 1)
{
return ERROR;
}
if (S[0] + T[0] > MAXLEN)
{
for (int i = S[0]; i > pos; i--)
{
S[MAXLEN + i - S[0]] = S[i];
}
for (int i = pos + 1; i < MAXLEN - StrLength(S); i++)
{
S[i] = T[i - pos];
}
S[0] = MAXLEN;
}
else
{
for (int i = S[0]; i > pos; i--)
{
S[i + StrLength(T)] = S[i];
}
for (int i = pos + 1; i < pos + 1 + StrLength(T); i++)
{
S[i] = T[i - pos];
}
S[0] += T[0];
}
return OK;
}
//初始条件：串S存在，1<=pos<=StrLength(S)-len+1
//操作：从S中删除第pos个字符起长度为len的子串
Status StrDelete(String S, int pos, int len)
{
if (pos<1 || pos>StrLength(S) - len + 1 || len < 0)
{
return ERROR;
}
for (int i = pos + len; i <= StrLength(S); i++)
{
S[pos++] = S[i];
}
S[0] -= len;
return OK;
}
//初始条件：串S,T和V存在，T是非空串，
//操作结果：用V替换主串S中出现的所有与T相等的不重叠
Status Replace(String S, String T, String V)
{
int pos = 0;
int index = 0;
if (StrEmpty(T))
{
return ERROR;
}
while (1)
{
index = Index(S, T, pos);
StrDelete(S, index, StrLength(T)); //删除要替换的串
StrInsert(S, index - 1, V); //插入用于替换的串
if (!pos)
{
break;
}
}
return OK;
}
//计算子串T的next数组
void get_next(String T, int* next)
{
int i, j;
i = 1;
j = 0;
next[1] = 0;
while (i < T[0]) //T[0]为串T的长度
{
if (j == 0 || T[i] == T[j]) //T[i]表示后缀的单个字符，T[j]表示前缀的单个字符
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j]; //字符不相同，则j回溯
}
}
}
//求模式串T的next函数修正值并存入数组nextval
void get_nextval(String T, int* nextval)
{
int i, j;
i = 1;
j = 0;
nextval[1] = 0;
while (i < T[0])
{
if (j == 0 || T[i] == T[j])
{
i++; //T[i]表示后缀的单个字符
j++; //T[j]表示前缀的单个字符
if (T[i] != T[j]) //若当前字符与前缀字符不同，
{
nextval[i] = j; //当前的j为nextval在i位置的值
}
else //若当前字符与前缀字符相同
{ //将前缀字符的nextval值赋值给nextval在i位置的值。
nextval[i] = nextval[j];
}
}
else
{
j = nextval[j]; //j回溯
}
}
}
//返回子串T在主串S中第pos个字符之后的位置，若不存在，则函数返回值为0
int Index_KMP(String S, String T, int pos)
{
if (pos<0 || pos>MAXLEN)
{
return 0;
}
/*int next[MAXLEN];
get_next(T, next);*/
int nextval[MAXLEN];
get_nextval(T, nextval);
int i = pos, j = 1; //i为主串的当前下标值，若pos不为1，则从pos位置开始匹配，j为子串T中当前位置下标值
while (i <= StrLength(S) && j <= StrLength(T))
{
if (j == 0 || S[i] == T[j])
{
i++;
j++;
}
else
{
//j = next[j];
j = nextval[j];
}
if (j > T[0])
{
return i - T[0];
}
}
return 0;
}
main.cpp
#include "String.h"
int main(int argc, char** argv)
{
const char* chars = "hello";
String T;
StrAssign(T, chars); //构造串T
StrPrint(T);
String S;
StrCopy(S, T);
StrPrint(S); //串T复制到串S中
if (StrEmpty(S)) //串S是否为空串
{
cout << "S为空串" << endl;
}
else
{
cout << "S不为空串" << endl;
}
int com = StrCompare(S, T); //比较串S与T
if (com > 0)
{
cout << "S>T" << endl;
}
else if (com < 0)
{
cout << "S<T" << endl;
}
else
{
cout << "S==T" << endl;
}
cout << "串S的长度为：" << StrLength(S) << endl; //求串S长度
ClearString(S); //清空串S
if (StrEmpty(S)) //串S是否为空串
{
cout << "S为空串" << endl;
}
else
{
cout << "S不为空串" << endl;
}
String SS;
String S1, S2;
StrAssign(S1, "hello ");
StrAssign(S2, "world");
Concat(SS, S1, S2); //字符串拼接
StrPrint(SS);
String Sub;
SubString(Sub, SS, 2, 4); //获取串SS中第2个位置长度为4的子串
StrPrint(Sub);
String s;
StrAssign(s, "ld"); //查找子串位置
int index = Index(SS, s, 0);
cout << "子串s在SS中的位置:" << index << endl;
index = Index2(SS, s, 0);
cout << "子串s在SS中的位置:" << index << endl;
ClearString(s);
StrAssign(s, " xian");
StrInsert(SS, 5, s); //串SS中插入串s
StrPrint(SS);
StrInsert2(SS, 5, s); //串SS中插入串s
StrPrint(SS);
StrDelete(SS, 6, 5); //删除串S中第6个位置处连续5个元素
StrPrint(SS);
Replace(SS, S1, s); //替换
StrPrint(SS);
//----------KMP-----------
int next[MAXLEN];
get_next(SS, next);
for (int i = 1; i <= SS[0]; i++)
{
cout << next[i] << " ";
}
cout << endl;
ClearString(s);
StrAssign(s, "world");
index = Index_KMP(SS, s, 0);
cout << "s在SS中的位置：" << index << endl;
return 0;
}
