数据结构_C语言_串_串的置换操作Replace (&S, T, V)的算法、字符串反序的递推或递归算法，例如字符串为“abcsxw”，反序为“wxscba”、串的模式匹配算法及改进KMP算法
前言
串的定义：串（字符串）是由零个或多个字符组成的有限序列。
对于串的基本操作集可以有不同的定义方式，对于串类型的最小操作子集有
- 串赋值
- 串比较
- 求串长
- 串联接
- 求子串
是最基本的操作子集，其他串操作都可以在这些操作上实现
串的表示和实现
串有3种机内表示方法
-
顺序存储结构
- 定长顺序存储表示（按照预定义的大小开辟一段连续的存储单元）
- 堆分配存储表示（也是地址连续的一段存储空间，只不过是根据使用需求动态分配的）
-
链式存储结构
- 串的块链存储表示（多个字符共用一个节点，密度大）
目录
- 串的定长存储实现
- 串的堆分配表示
- 一些串操作的算法
- 串的置换
- 串的递归反序
- 串的模式匹配算法
- 串的模式匹配算法改进版KMP
开始
一、串的定长存储实现
直接上代码，很容易理解
需要注意的地方：
- SString是一种自定义的结构类型，其中能存放unsigned char 类型的元素
- 规定一般字符数组的s[0] 存放字符串的长度lemgth
- 至于为什么是255，因为无符号数的范围为 0 - 255，其实底层存储的还是ASCII码（一串01的代码），归根结底还是字节，万物皆字节
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//串的定长顺序存储表示
//char 在c语言中站1个字节，2^8 - 1 = 255
#define MAXSTRLEN 255
//规定字符数组的s[0]存放子符串的长度，这其实也就是字符串底层实现的原理
//自定义数据类型 SString
typedef unsigned char SString[MAXSTRLEN + 1] ;
int main(){
SString s = "abcde";
cout<<s<<endl;
cout<<"=================" <<endl<<endl;
SString s1;
cout<<"未赋初值的时候，存放的默认为："<<s1[0]<<endl<<endl;
cout<<"=================" <<endl<<endl;
//当然这里可以不进行长度的输入，直接s[0]就存放有效字符
cout<<"请输入这个新的字符串(第一位为字符串的长度)："<<endl;
cin>>s1;
cout<<"这个字符串为：";
int i = 1;
while(s1[i] != NULL){
cout<<s1[i];
i++;
}
cout<<endl;
cout<<"s1[0]可以设置有效字符串的长度：" <<s1[0]<<endl<<endl;
}
二、串的堆分配表示
这种存储结构的串操作，仍是 基于 “字符序列的复制”进行的
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
//串的堆分配表示
typedef struct{
char *ch;//若是非空串，则按串长分配存储区，否则ch为NULL
int length;//串长度
}HString;
int main(){
HString s;
cout<<"请输入字符串的长度"<<endl;
cin>>s.length;
s.ch = (char*)malloc(s.length * sizeof(char));
cout<<"请输入字符串："<<endl;
cin>>s.ch;
cout<<endl;
cout<<"您输入的字符串为："<<s.ch<<"长度为："<<s.length<<endl;
}
三、一些串操作的算法
3.1串的置换
3.1.1涉及：
- 串的堆分配表示
- 字符串模式匹配（这里使用最普通的算法，下面会使用KMP等改进后的算法）
- 字符串替换（也是普通的3个for来解决）
3.1.2程序运行截图
3.1.3代码
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
//串的堆分配表示
typedef struct{
char *ch;//若是非空串，则按串长分配存储区，否则ch为NULL
int length;//串长度
}HString;
//1. 实现串的初始化
void InitStr(HString &s) ;
//2. 一般的串模式匹配 ，子串定位
int Index(HString s,HString T,int pos);
//3. 实现串的置换
void Replace(HString &s,HString &new_s,HString T, HString V,int index);
int main(){
//创建第一个串
HString s;
InitStr(s);
//创建第二个串,作为匹配子串
cout<<"请输入需要进行匹配的的字符串s1" <<endl;
HString s1;
InitStr(s1);
//创建第三个串，如果匹配成功，作为替换串
//模式匹配，如果s1为s的子串，就进行接下来的操作，否则就提示匹配失败
cout<<"请输入s1从什么位置开始匹配s：( 1 <=N<="<< s.length<<")"<<endl;
int pos;
cin>>pos;
int index = Index(s,s1,pos);
//判断是否成功匹配
if(index) {
cout<<"子串s1 在 s 的位置为 ："<< index<<endl<<endl;
cout<<"请输入要替换的目标串s2" <<endl;
HString s2;
InitStr(s2);
HString new_s;
Replace(s,new_s,s1,s2,index);
for(int i = 0;i<new_s.length;i++){
cout<<new_s.ch[i];
}
}else{
cout<<"字符串 s1 不是 s 的字串！" <<endl;
}
return 0;
}
//1. 实现串的初始化
void InitStr(HString &s){
cout<<"请输入字符串的长度"<<endl;
cin>>s.length;
s.ch = (char*)malloc(s.length * sizeof(char));
cout<<"请输入字符串："<<endl;
cin>>s.ch;
cout<<"您输入的字符串为："<<s.ch<<"长度为："<<s.length<<"初始化完成！"<<endl;
cout<<endl;
}
//2. 一般的串模式匹配 ,子串定位
int Index(HString s,HString T,int pos){
int i = pos;
int j = 1;
while(i<= s.length && j<=T.length){
if(s.ch[i - 1] == T.ch[j - 1]){
++i;
++j;
}
else{
i = i - j + 2;
j = 1;
}
}
if(j>T.length){
return i - T.length;
}
else
return 0;
}
// //3. 实现串的置换
void Replace(HString &s,HString &new_s,HString T, HString V,int index){
new_s.length = s.length + (V.length - T.length);
new_s.ch = (char*)malloc(s.length * sizeof(char));
//字串之前的不动
int i;
for(i = 0;i< index - 1;i++){
new_s.ch[i] = s.ch[i];
}
//替换的目标串插入
for(int j = index - 1;j<V.length + i + 1;j++){
new_s.ch[j] = V.ch[j - index + 1];
}
//字串之后的不动
for(int k = i + V.length ;k<new_s.length;k++){
new_s.ch[k] = s.ch[k - i + V.length - T.length ] ;
}
}
3.2串的递归反序
之前记录了一篇Java版的 连续逐个输入若干字符，以 #号结束，实现结束时 输出 输入字符的逆序
就是递归实现，目前实现不太符合字符串整体性，后续有时间会优化
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
char DiGui(){
char ch;
cout<<"请输入字符串的每个字符:（一个字符一次回车，以#为结束的标志）"<<endl;
cin>>ch;
if(ch == '#'){
return NULL;
}
else{
DiGui();
cout<<ch<<" ";
}
}
int main(){
DiGui();
return 0;
}
3.3串的模式匹配算法
普通模式匹配算法 实现见上面的 3.1 已经基本实现
部分代码
//2. 一般的串模式匹配 ,子串定位
int Index(HString s,HString T,int pos){
int i = pos;
int j = 1;
while(i<= s.length && j<=T.length){
if(s.ch[i - 1] == T.ch[j - 1]){
++i;
++j;
}
else{
i = i - j + 2;
j = 1;
}
}
if(j>T.length){
//正常找到结束，还有 ++j ，返回查找到的位置
return i - T.length;
}
else
return 0;
}
注意这里我采用的是 堆顺序分配的存储结构 实现的串
3.4串的模式匹配算法改进版KMP
普通查询算法和KMP查找算法 写在一个程序里面，可以查询两次
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//串定长顺序存储表示
#define MAXSTRLEN 255
//串可以存放不止字母，还可以特殊字符
typedef unsigned char SString[MAXSTRLEN + 1];
//1. 字符串初始化函数
void InitString(SString &s);
//2. 普通模式匹配算法
int index(SString s1,SString s2,int pos);
//3. KMP模式匹配
int indexKMP(SString s1,SString s2,int pos);
void get_next(SString s2,int next[]);
int next[20];
int main(){
SString s1;
InitString(s1);
SString s2;
InitString(s2);
cout<<endl<<"=============="<<endl;
int pos1;
cout<<"请输入你要开始查找的位置："<<endl;
cin>>pos1;
int findIndex = index(s1,s2,pos1);
if(findIndex > 0){
cout<<"s2是s1的子串！所在的位置为： "<<findIndex<<endl;
}
else{
cout<<"s2不是s1的子串 ！"<<endl;
}
int pos2;
cout<<"请输入你要开始查找的位置："<<endl;
cin>>pos2;
int findIndex2 = index(s1,s2,pos2);
if(findIndex2 > 0){
cout<<"s2是s1的子串！所在的位置为： "<<findIndex2<<endl;
}
else{
cout<<"s2不是s1的子串 ！"<<endl;
}
get_next(s2,next);
indexKMP(s1,s2,pos2);
}
//1. 字符串初始化函数
void InitString(SString &s){
cout<<"请输入字符串 :(首位表示字符串的长度)"<<endl;
cin>>s;
cout<<"字符串初始化完成!";
cout<<"字符串的长度为 ："<<s[0]<<"字符串的内容为：";
int i = 1;
while(s[i] != '\0'){
cout<<s[i];
i++;
}
cout<<endl<<endl;
}
//2. 普通模式匹配算法
int index(SString s1,SString s2,int pos){
int i = pos;
int j = 1;
//这里需要进行ascii码的转换，s[0]存放的长度为字符 型的，需要转化为整形
while(i<= int(s1[0] ) - 48 && j<= int(s2[0]) - 48){
if(s1[i] == s2[j]){
i++;
j++;
}
else{
//出现不相等的，就从s1的第 i - j + 2的位置开始重新比较
//目标子串从j = 1的位置开始比较
i = i - j + 2;
j = 1;
}
}
//目标子串全部找到
// 字符0的ascii码为48
if(j > (int(s2[0]) - 48) ){
return i - int(s2[0]) + 48;
}
else{
/*
cout<<"debug"<<endl;
cout<<i<<endl;
cout<<int(s2[0])<<endl;
*/
return 0;
}
}
//3. KMP模式匹配
int indexKMP(SString s1,SString s2,int pos){
int i = pos;
int j = 1;
while(i<=int(s1[0]) - 48 && j<=int(s2[0]) - 48){
if(j == 0 || s1[i] == s2[j]){
i++;
j++;
}
else{
j = next[j];
}
}
}
void get_next(SString s2,int next[]){
int i = 1;
next[1] = 0;
int j = 0;
while(i < int(s2[0]) - 48){
if(j == 0 || s2[i] == s2[j]){
j++;
i++;
next[i] = j;
}
else{
j = next[j];
}
}
}