首页 > 代码库 > 串操作,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字符串替换操作测试