首页 > 代码库 > 串操作，C++实现
串操作，C++实现
对串的基本操作都全已经实现
对kmp,kf字符串替换等功能全都已经实现
由于时间原因。没来得及注释，希望大家参考见谅。
串操作hstring.h头文件实现
//kallen
1 #ifndef _HSTRING_H_ 2 #define _HSTRING_H_ 3 #include <iostream> 4 class mString 5 { 6 public: 7 mString(); 8 void newString(const char *ms); 9 ~mString(); 10 bool isEmpty()const; 11 int lengthString()const; 12 void copyString(const mString &src); 13 friend int compareString(const mString &lhs,const mString &rhs); 14 void clearStirng(); 15 void concatString(const mString &lhs_src,const mString &rhs_src); 16 void subString(const mString &src,int pos,int len); 17 void insertString(int pos,const mString &ms); 18 void deleteString(int pos,int len); 19 int indexkfString(const mString &mt,int pos); 20 int indexkmpString(const mString &mt,int pos,int *next); 21 void replaceString(int repos,const mString& mt,const mString &mv,int *next); 22 23 void insaftposString(int pps,const mString& mt,const mString& mv); 24 void printString()const; 25 private: 26 char *base; 27 int length; 28 void nextSt(const mString& mt,int *next); 29 }; 30 31 #endif //_HSTRING_H_
hstring.cpp的实现代码
1 #include "hstring.h" 2 3 mString::mString() 4 { 5 base = NULL; 6 length = 0; 7 } 8 9 mString::~mString() 10 { 11 if (base!=NULL) 12 { 13 delete base; 14 } 15 base = NULL; 16 } 17 18 void mString::newString(const char *ms) 19 { 20 int i = 0; 21 while(ms[i]!=‘\0‘) 22 { 23 ++i; 24 } 25 length = i; 26 base = new char[length + 1]; 27 for (int j = 0;j<length;++j) 28 { 29 base[j] = ms[j]; 30 } 31 base[length] = ‘\0‘; 32 } 33 34 bool mString::isEmpty()const 35 { 36 if (0 == length) 37 { 38 return true; 39 } 40 else 41 { 42 return false; 43 } 44 } 45 46 int mString::lengthString()const 47 { 48 return length; 49 } 50 51 void mString::copyString(const mString &src) 52 { 53 int i = 0; 54 for (; i<this->length;++i) 55 { 56 base[i] = src.base[i]; 57 } 58 } 59 60 int compareString(const mString &lhs,const mString &rhs) 61 { 62 int i = 0; 63 while (lhs.base[i]!=‘\0‘&&lhs.base[i]!=‘\0‘) 64 { 65 if (lhs.base[i] > rhs.base[i]) 66 { 67 return 1; 68 } 69 else if (lhs.base[i] < rhs.base[i]) 70 { 71 return -1; 72 } 73 else 74 { 75 ++i; 76 } 77 } 78 if (lhs.base[i] ==‘\0‘&&rhs.base[i]!=‘\0‘) 79 { 80 return -1; 81 } 82 else if (lhs.base[i] !=‘\0‘&&rhs.base[i]==‘\0‘) 83 { 84 return 1; 85 } 86 else 87 { 88 return 0; 89 } 90 } 91 92 void mString::clearStirng() 93 { 94 length = 0; 95 } 96 97 void mString::concatString(const mString &lhs_src,const mString &rhs_src) 98 { 99 100 length = lhs_src.length + rhs_src.length; 101 this->base = new char[length+1]; 102 103 for (int i = 0; i<lhs_src.length; ++i ) 104 { 105 this->base[i] = lhs_src.base[i]; 106 } 107 for (int i = lhs_src.length,j = 0; j < rhs_src.length; ++j,++i ) 108 { 109 this->base[i] = rhs_src.base[j]; 110 } 111 this->base[length] = ‘\0‘; 112 113 } 114 115 void mString::printString()const 116 { 117 int i = 0; 118 for (;i<length;++i) 119 { 120 std::cout<<base[i]; 121 } 122 std::cout<<std::endl; 123 } 124 125 void mString::subString(const mString &src,int pos,int len) 126 { 127 if (src.length != 0 ) 128 { 129 if (pos>src.length) 130 { 131 std::cout<<"The location of pos is illegal!"<<std::endl; 132 } 133 else 134 { 135 if (pos+len-1 <=src.length) 136 { 137 length = len; 138 this->base = new char[length+1]; 139 140 for(int i = 0; i < length; ++i,++pos) 141 { 142 this->base[i] = src.base[pos-1]; 143 } 144 } 145 else 146 { 147 length = src.length-pos+1; 148 this->base = new char[length+1]; 149 int j = 0; 150 for (;j<length;++j,++pos) 151 { 152 this->base[j] = src.base[pos-1]; 153 } 154 this->base[j] = ‘\0‘; 155 } 156 } 157 158 } 159 else 160 { 161 std::cout<<"The string is empty!"<<std::endl; 162 } 163 } 164 165 void mString::deleteString(int pos,int len) 166 { 167 if (0 == length) 168 { 169 std::cout<<"The string is empty!"<<std::endl; 170 } 171 else 172 { 173 if (pos>length) 174 { 175 std::cout<<"The location of pos is illegal!"<<std::endl; 176 } 177 else 178 { 179 if (pos+len-1>=length) //delete all char after pos, 180 //but it don‘t move any char 181 { 182 int i = pos - 1; 183 for (;i<length;++i) 184 { 185 base[i] = ‘\0‘; 186 } 187 } 188 else //pos+len-1<length,we have to move the char that 189 //from pos+len to length 190 { 191 int i = pos-1,j=pos+len-1,k=length-(pos+len)+1; 192 for (;k>0;--k,++i,++j) 193 { 194 base[i] = base[j]; 195 } 196 for (int m = len,n = length;m>0;--n,--m) 197 { 198 base[n-1] = ‘\0‘; 199 } 200 } 201 } 202 203 } 204 } 205 206 void mString::insertString(int pos,const mString &ms)//insert ms before pos 207 { 208 if (0!=length&&0!=ms.length) 209 { 210 if (pos>length) 211 { 212 std::cout<<"The location of pos is illegal!"<<std::endl; 213 } 214 else 215 { 216 int len = ms.length,i = length-1,j=length+len-1,k = length-pos+1; 217 int m = pos,n=0; 218 base = (char *)realloc(base,(length+len)*sizeof(char)); 219 length = length+len; 220 if (base==NULL) 221 { 222 std::cout<<"Create memory is failed!"<<std::endl; 223 } 224 for (;k>0;--k,--i,--j) 225 { 226 base[j] = base[i]; 227 } 228 base[length]=‘\0‘; 229 for (;n<len;++m,++n) 230 { 231 base[m-1] = ms.base[n]; 232 } 233 } 234 } 235 else 236 { 237 std::cout<<"The string is empty!"<<std::endl; 238 } 239 } 240 241 int mString::indexkfString(const mString &mt,int pos) 242 { 243 if (length != 0 &&mt.length!=0) 244 { 245 if (pos>length-mt.length+1) 246 { 247 std::cout<<"The location of pos is illegal!"<<std::endl; 248 return 0; 249 } 250 else 251 { 252 int i = 1,j = pos; 253 while(i<=mt.length&&j<=length) 254 { 255 if (mt.base[i-1]==base[j-1]) 256 { 257 ++i; 258 ++j; 259 } 260 else 261 { 262 j = j-i+2; 263 i = 1; //it‘s wrong if example : i = 1; j =j-i+2; 264 if (j>length-mt.length +1) 265 { 266 break; 267 } 268 } 269 } 270 if (i > mt.length) 271 { 272 return (j-i+1); 273 } 274 else 275 { 276 return 0; 277 } 278 } 279 } 280 else 281 { 282 std::cout<<"The string is empty!"<<std::endl; 283 return 0; 284 } 285 } 286 287 int mString::indexkmpString(const mString &mt,int pos,int *next) 288 { 289 int i = pos,j = 0; 290 nextSt(mt,next); 291 while(j<mt.length&&i<=length) 292 { 293 if (j == -1||mt.base[j]==base[i-1]) 294 { 295 ++i; 296 ++j; 297 } 298 else 299 { 300 j = next[j]; 301 } 302 } 303 if (j==mt.length) 304 { 305 std::cout<<i-j<<std::endl; 306 return (i - j); 307 } 308 else 309 { 310 std::cout<<"nothing"<<std::endl; 311 return 0; 312 } 313 } 314 315 void mString::nextSt(const mString& mt,int *next) 316 { 317 int i = 0,j = -1; 318 next[0] = -1; 319 while (i<mt.length) 320 { 321 if (j==-1||mt.base[i]==mt.base[j]) 322 { 323 ++i; 324 ++j; 325 next[i] = j; 326 } 327 else 328 { 329 j = next[j]; 330 } 331 } 332 //for (int i = 0;i<mt.length;++i) 333 //{ 334 //std::cout<<next[i]; 335 //} 336 } 337 338 void mString::replaceString(int repos,const mString& mt,const mString &mv,int *next) 339 { 340 if (length!=0) 341 { 342 int pos = repos; 343 if (mt.length!=0&&mv.length!=0) 344 { 345 int pps = pos; 346 while(pos!=0) 347 { 348 pos = indexkmpString(mt,pps,next); 349 if (pos!=0) //when pos == 0,maybe execute copy in the head 350 { //example;a = "abcaabcacbc";mt = "bc";mv = "ff"; 351 insaftposString(pos,mt,mv); //but the result is; "fffaaffacff". 352 } 353 pps = pos+mv.length; //from pos+mv.length 354 } 355 } 356 else 357 { 358 std::cout<<"The string of mt or mv is empty!"<<std::endl; 359 } 360 361 } 362 else 363 { 364 std::cout<<"The main string is empty!"<<std::endl; 365 } 366 367 } 368 369 void mString::insaftposString(int pps,const mString& mt,const mString& mv) 370 { 371 if (mt.length<mv.length) 372 { 373 int n = length - (pps+mt.length-1); //the sum of movement 374 int dis = mv.length - mt.length; 375 int k = length+dis-1; 376 int j = length-1; 377 base = (char *)realloc(base,(length+dis)*sizeof(char)); 378 length = length+dis; 379 if (base==NULL) 380 { 381 std::cout<<"Create memory is failed!"<<std::endl; 382 } 383 for (int i = 1;i<=n;++i,--k,--j) 384 { 385 base[k] = base[j]; 386 } 387 base[length] = ‘\0‘; 388 for (int i = 0,j=pps-1;i<mv.length;++i,++j) 389 { 390 base[j] = mv.base[i]; 391 } 392 } 393 else if (mt.length>mv.length) 394 { 395 int n = length - (pps+mt.length-1); 396 int dis = mt.length-mv.length; 397 int i = pps+mv.length-1; 398 int j = pps+mt.length-1; 399 for (int k = pps-1,l = 0;l<mv.length;++l,++k) 400 { 401 base[k] = mv.base[l]; 402 } 403 for (int k=1;k<=n;++k,++i,++j) 404 { 405 base[i]=base[j]; 406 } 407 for (int k=1,l = length-1;k<=dis;++k) 408 { 409 base[l] = ‘\0‘; 410 } 411 length = length-dis; 412 } 413 else 414 { 415 for (int i = 0;i<mv.length;++i,++pps) 416 { 417 base[pps-1] = mv.base[i]; 418 } 419 printString();//inserts without thinks 420 } 421 422 }
以上代码都经过正确测试
这里仅仅列出对kmp算法应用的测试。
1 #include "hstring.h" 2 3 4 int main(void) 5 { 6 char d[100]; 7 char e[10]; 8 char f[10]; 9 std::cout<<"Please Enter a string!"<<std::endl; 10 std::cin>>d; 11 std::cout<<"Please Enter a string mt"<<std::endl; 12 std::cin>>e; 13 std::cout<<"Please Enter a string mt"<<std::endl; 14 std::cin>>f; 15 char *p1 = d; //= "abcaabcacbcabc"; 16 char *p2 = e;//"abc"; 17 char *p3 = f;//"ffff"; 18 int p[100]; 19 mString a,b,c; 20 a.newString(p1); 21 b.newString(p2); 22 c.newString(p3); 23 a.replaceString(1,b,c,p); 24 //int p[88]; 25 //a.indexkmpString(b,1,p); 26 //std::cout<<a.indexkfString(b,2); 27 //a.insertString(4,b); 28 //a.deleteString(1,4); 29 //c.subString(a,2,3); 30 a.printString(); 31 //c.concatString(a,b); 32 //b.printString(); 33 //a.clearStirng(); 34 //std::cout<<a.isEmpty(); 35 //std::cout<<a.lengthString(); 36 //std::cout<<compareString(a,b); 37 system("pause"); 38 return 0; 39 }
测试结果：
kmp字符串替换操作测试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。