首页 > 代码库 > 串(C++实现)
串(C++实现)
本段程序实现串的存储结构是采用堆的动态分配存储表示,并实现了几乎所有常用的串的配套函数
其中逻辑性比较强的就是串的模式匹配算法,在下面的程序中,分别用BF算法和KMP算法对其进行了
实现。
#include<iostream> using namespace std; struct HString { HString() { ch = 0; length = 0; } char * ch;//字符存储区 int length;//串长 }; void ClearString(HString & T); //用C字符串进行初始化 void StrAssign(HString & T,char s[]) { free(T.ch); T.length = 0; for(;‘\0‘!=s[T.length];(T.length)++); T.ch =(char *)malloc(T.length*(sizeof(char))); if(!T.ch) exit(0); for(int i=0;‘\0‘!=s[i];i++) { T.ch[i] = s[i]; } } //串的复制 void StrCopy(HString & T,HString & S) { ClearString(T); T.length = S.length; T.ch = (char*)malloc(T.length*(sizeof(char))); if(!T.ch) exit(0); for(int i=0;i<T.length;i++) { T.ch[i] = S.ch[i]; } } //串的比较 int StrCompare(HString & T,HString & S) { for(int i=0;i<T.length&&i<S.length;i++) { if(T.ch[i]!=S.ch[i]) return T.ch[i]-S.ch[i]; } return T.length - S.length; } //返回串的长度 int StrLength(HString & T) { return T.length; } //清空串 void ClearString(HString & T) { free(T.ch); T.length = 0; } //连接两个串构成一个新串 void Concat(HString & T,HString & S1,HString & S2) { ClearString(T); T.length = S1.length + S2.length; T.ch = (char*)malloc(T.length*(sizeof(char))); if(!T.ch) exit(0); int i = 0; for(;i<S1.length;i++) { T.ch[i] = S1.ch[i]; } for(int j = 0;j<S2.length;j++,i++) { T.ch[i] = S2.ch[j]; } } //用Sub串返回S的第pos个字符起长度为len的字串Sub bool SubString(HString & Sub,HString & S,int pos,int len) { if(S.length<(pos+len-1)) return false; Sub.length = len; Sub.ch = (char*)malloc(Sub.length*(sizeof(char))); if(!Sub.ch) exit(0); for(int i = 0;i<len;i++) { Sub.ch[i] = S.ch[pos+i-1]; } return true; } /* //串的模式匹配 //若主串S中存在和串T值相同的字串,则返回它在主串S中第pos个字符之后的第一次出现的位置,否则返回-1 */ //算法一:BF算法 int Index_BF(HString &S,HString &T,int pos) { int i = pos ,j = 0; while(i<S.length&&j<T.length) { if(S.ch[i] == T.ch[j]) { i++; j++; }else { i = i-j+1; j = 0; } } if(j>=T.length) return i - T.length; else return -1; } //算法二:KMP算法 --- 辅助函数(初始化并发next数组) void Get_next(HString &T,int next[]) { int i = 1,j; next[0] = 0; next[1] = 0; j = next[1]; for(;i<T.length;) { if(0==j||T.ch[i] == T.ch[j]) { if(0==j&&T.ch[i] != T.ch[j]) {next[++i] = j;} else { next[++i] = ++j; } } else { j = next[j]; } } } //算法二:KMP算法 --- 实现函数 int Index_KMP(HString &S,HString &T,int pos) { int * next = new int[T.length]; Get_next(T,next); int i = pos,j = 0; for(;i<S.length&&j<T.length;) { if(S.ch[i] == T.ch[j]) { j++; i++; } else { if(0==j) i++; else j = next[j]; } } if(j>=T.length) { return i - T.length; } else{ return -1; } } //用V替换S中所有与T相等的不重叠的字串 //替换的前提是被替换的字符串T和替换的字符串的长度相等 Replace(str2,str3,strV); bool Replace(HString & S,HString &T,HString &V) { if(T.length!=V.length) return false; int pos =0; while (pos<S.length) { pos = Index_BF(S,T,pos); if(-1==pos) return true; else{ for(int i = 0;i<T.length;i++) { S.ch[i+pos] = V.ch[i]; } pos += V.length; } } } //在串S的第pos个字符之前插入串T bool StrInsert(HString &S,int pos,HString &T) { --pos; if(S.length<pos) return false; HString ss; StrCopy(ss,S); ClearString(S); S.length = ss.length + T.length; S.ch = (char*)malloc(S.length*(sizeof(char))); if(!S.ch) exit(0); int i =0; for(;i<pos;i++) { S.ch[i] = ss.ch[i]; } for(int j=0;j<T.length;j++) { S.ch[i++] = T.ch[j]; } for(;pos<ss.length;pos++) { S.ch[i++] = ss.ch[pos]; } return true; } //从串S中删除第pos个字符起长度为len的字串 bool StrDelete(HString &S,int pos,int len) { if(S.length<(pos+len-1))return false; HString ss; StrCopy(ss,S); ClearString(S); S.length = ss.length - len; S.ch = (char*)malloc(S.length*(sizeof(char))); if(!S.ch)exit(0); int i = 0; for(;i<pos;i++) { S.ch[i] = ss.ch[i]; } for(pos = pos+len;pos<ss.length;pos++) { S.ch[i++] = ss.ch[pos]; } return true; } //遍历访问串中的每一个字符 void Visit(HString & T,void(*visit)(char &)) { for(int i = 0;i<T.length;i++) { (*visit)(T.ch[i]); } } //测试函数 void fun(char &t) { cout<<t; } int main() { //创建一个空串 HString str; //用C字符串进行初始化 char c[] = "ILOVEYOU"; cout<<"用C字符串进行初始化 :str:"<<endl; StrAssign(str,c); //输出 Visit(str,fun); cout<<endl; //返回串的长度 cout<<"str串的长度是:"<<StrLength(str)<<endl; //串的复制 HString str1; StrCopy(str1,str); cout<<"串的复制 str1:"<<endl; //输出 Visit(str1,fun); cout<<endl; //串的比较 int s = StrCompare(str,str1); if(s==0) { cout<<"str=str1"<<endl; } if(s>0) { cout<<"str>str1"<<endl; } if(s<0) { cout<<"str<str1"<<endl; } //连接两个串构成一个新串 HString str2; Concat(str2,str,str1); cout<<"连接两个串构成一个新串 str2:"<<endl; //输出 Visit(str2,fun); cout<<endl; //用Sub串返回S的第pos个字符起长度为len的字串Sub HString str3; cout<<"用Sub串返回S的第7个字符起长度为2的字串str3: "<<endl; SubString(str3,str,7,2); //输出 Visit(str3,fun); cout<<endl; //串的模式匹配 查找子串在主串中第一次出现的位置 cout<<"BF算法:查找子串str3在主串str1中第一次出现的位置"<<endl; int index = Index_BF(str1,str3,0); if(-1==index) { cout<<"BF算法:未找到子串str3"<<endl; } else { cout<<"BF算法:查找子串str3在主串str1中第一次出现的下标为:"<<index<<endl; } cout<<"KMP算法:查找子串str3在主串str1中第一次出现的位置"<<endl; int index2 = Index_KMP(str1,str3,0); if(-1==index2) { cout<<"KMP算法:未找到子串str3"<<endl; } else { cout<<"KMP算法:查找子串str3在主串str1中第一次出现的下标为:"<<index2<<endl; } //用V替换S中所有与T相等的不重叠的字串 HString strV; StrAssign(strV,"ZR"); cout<<"用“ZR”替换主串Str2中所有的子串str3"<<endl; Replace(str2,str3,strV); //输出 Visit(str2,fun); cout<<endl; //在串str2的第pos个字符之前插入串str3 cout<<"在串str2的第2个字符之前插入串str3"<<endl; StrInsert(str2,2,str3); //输出 Visit(str2,fun); cout<<endl; //从串Str2中删除第pos个字符起长度为len的字串 cout<<"从串Str2中删除第2个字符起长度为3的字串"<<endl; StrDelete(str2,2,3); //输出 Visit(str2,fun); cout<<endl; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。