顺序串

溯影

《数据结构C++描述》 清华大学出版社   任燕编著

小弟改了程序中的一个bug，看来数据结构还是要自己来运行一下，不能光看不练啊

1. #include <iostream>
   
2. #include <assert.h>
   
3. using namespace std;
   
4. 
   
5. class SqString{
   
6. public:
   
7.         //把顺序串置空
   
8.         void clear();
   
9. 
   
10.         //获取第i个字符
    
11.         bool getChar(int i, char &c);
    
12. 
    
13.         //求顺序串的长度
    
14.         int getLength();
    
15. 
    
16.         //求模式串的next数组
    
17.         void get_next(int *next, int display = 1);
    
18. 
    
19.         //串的朴素匹配(有回溯查找)
    
20.         int index(SqString p, int pos);
    
21. 
    
22.         //模式匹配(无回溯KMP查找)
    
23.         int index_KMP(SqString p, int pos);
    
24. 
    
25.         //在第i个字符前插入另一个字符串
    
26.         bool insert(int i, SqString t);
    
27. 
    
28.         //判断顺序串是否为空
    
29.         bool isEmpty();
    
30. 
    
31.         //重载赋值运算符   char类型字符串
    
32.         SqString operator=(char *s);
    
33. 
    
34.         //重载赋值运算符  SqString类型顺序串
    
35.         SqString operator=(SqString s);
    
36. 
    
37.         //重载加法运算符    被加是char类型
    
38.         SqString operator+(char* s);
    
39. 
    
40.         //重载加法运算符   SqString类型顺序串
    
41.         SqString operator+(SqString s);
    
42. 
    
43.         //重载是否小于运算符  SqString类型
    
44.         bool operator <(SqString s);
    
45. 
    
46.         //重载是否相等运算符  char
    
47.         int operator ==(char *s);
    
48. 
    
49.         //重载是否相等运算符   SqString
    
50.         int operator==(SqString s);
    
51. 
    
52. protected:
    
53.         //把char类型的顺序串赋值给当前顺序串的赋值函数
    
54.         void strAssign_aux(char *s);
    
55. 
    
56. public:
    
57.         //删除第i个字符起的长度为len的子串
    
58.         bool strDelete(int i, int len);
    
59. 
    
60.         //取顺序串的子串
    
61.         bool subString(SqString& sub, int i, int len);
    
62. 
    
63.         SqString();
    
64.         virtual ~SqString();
    
65. 
    
66.         SqString(char* s);
    
67.         SqString(SqString &s);
    
68. 
    
69. 
    
70.         //重载输出函数
    
71.         friend ostream& operator <<(ostream& out, SqString s);
    
72. 
    
73. protected:
    
74.         int length;//顺序串长度
    
75.         char *ch;//顺序串动态存储空间的首地址
    
76. };
    
77. 
    
78. void SqString::clear(){
    
79.         if (ch){
    
80.                 delete[]ch;
    
81.                 ch = NULL;
    
82.                 length = 0;
    
83.         }
    
84. }
    
85. 
    
86. bool SqString::getChar(int i, char &c){
    
87.         if (i<1 || i>length){
    
88.                 return false;
    
89.         }
    
90.         c = ch[i - 1];
    
91.         return true;
    
92. }
    
93. 
    
94. int SqString::getLength(){
    
95.         return length;
    
96. }
    
97. 
    
98. 
    
99. void SqString::get_next(int *next, int display){
    
100.         int j = -1, i = 0;//前后字符指针，初始化为-1和0
     
101.         int first_i;//当前组第一个元素的下标
     
102.         char no[5] = "[ i]";
     
103. 
     
104.         //生成next数组每个元素的值
     
105.         next[0] = -1;//-1为终止标志
     
106.         while (i < length){
     
107.                 if (j == -1 || ch[j] == ch[i]){
     
108.                         j++;
     
109.                         i++;
     
110.                         next[i] = j;
     
111.                 }
     
112.                 else{
     
113.                         j = next[j];
     
114.                 }
     
115.         }
     
116.         if (display == 1){
     
117.                 cout << "   当前模式串的next[]数组为:" << endl;
     
118.                 first_i = 0;
     
119.                 while (first_i < length){
     
120.                         i = first_i;
     
121.                         cout << "       ";
     
122.                         do{
     
123.                                 //修正元素下标的字符表示
     
124.                                 if (i < 10){
     
125.                                         no[2] = i + '0';//数组中元素的小标小于10
     
126.                                 }
     
127.                                 else{
     
128.                                         no[1] = i / 10 + '0';//数组中元素的下标大于等于10
     
129.                                         no[2] = i % 10 + '0';
     
130.                                 }
     
131.                                 //每个元素的序号显示占5个字符，不足以空格补齐，靠右对齐
     
132.                                 cout.width(5);
     
133.                                 cout.fill(' ');
     
134.                                 cout.setf(ios::right, ios::adjustfield);
     
135.                                 cout << no;
     
136.                                 i++;
     
137.                         } while (i % 10 && i < length);
     
138. 
     
139.                         cout << endl;
     
140.                         cout << "      ";//显示模式串中的字符
     
141.                         i = first_i;
     
142.                         do{
     
143.                                 cout.width(5);
     
144.                                 cout.fill(' ');
     
145.                                 cout.setf(ios::right, ios::adjustfield);
     
146.                                 cout << ch[i];
     
147.                                 i++;
     
148.                         } while (i % 10 && i < length);
     
149.                         cout << endl;
     
150. 
     
151.                         //显示next[]数组中每个元素的值
     
152.                         cout << "    ";
     
153.                         i = first_i;
     
154.                         do{
     
155.                                 cout.width(5);
     
156.                                 cout.fill(' ');
     
157.                                 cout.setf(ios::right, ios::adjustfield);
     
158.                                 cout << ch[i];
     
159.                                 i++;
     
160.                         } while (i % 10 && i < length);
     
161. 
     
162.                         first_i = i;//下一组第一个元素的下标
     
163.                         cout << endl << endl;
     
164.                 }
     
165.         }
     
166. }
     
167. 
     
168. 
     
169. //朴素查找
     
170. int SqString::index(SqString p, int pos){
     
171.         int i = pos - 1;//指向第pos个字符的下标
     
172.         int j = 0;
     
173. 
     
174.         while (i < length && j < p.length){
     
175.                 if (ch[i] == p.ch[j]){
     
176.                         i++;
     
177.                         j++;
     
178.                 }
     
179.                 else{//下标的重置
     
180.                         i = i - j + 1;
     
181.                         j = 0;
     
182.                 }
     
183. 
     
184.         }
     
185.         if (j == p.length){
     
186.                 return i - p.length + 1;//找到了
     
187.         }
     
188.         else{
     
189.                 return 0;//没找到
     
190.         }
     
191. }
     
192. 
     
193. 
     
194. //KMP查找
     
195. int SqString::index_KMP(SqString p, int pos){
     
196.         int i = pos - 1;
     
197.         int j = -1;//模式串当前字符，初始化为-1，就是没有指向
     
198. 
     
199.         int *next;
     
200.         next = new int[p.length];
     
201.         assert(next != 0);
     
202. 
     
203.         p.get_next(next, 0);//求模式串的next函数的数组
     
204. 
     
205.         //从主串的第pos个字符开始，与模式串的对应字符逐一比较
     
206.         while (i < length && j < p.length){
     
207.                 if (j == -1 || ch[i] == p.ch[j]){
     
208.                         i++;
     
209.                         j++;
     
210.                 }
     
211.                 else{
     
212.                         j = next[j];//重置，无回溯
     
213.                 }
     
214.         }
     
215.         if (j == p.length){
     
216.                 return i - p.length + 1;//找到了
     
217.         }
     
218.         else{
     
219.                 return 0;//没找到
     
220.         }
     
221. }
     
222. 
     
223. 
     
224. bool SqString::insert(int i, SqString t){
     
225.         char *temp;
     
226.         if (i<1 || i>length || t.isEmpty()){
     
227.                 return false;
     
228. 
     
229.         }
     
230.         temp = new char[length + t.length];
     
231.         assert(temp != 0);
     
232. 
     
233.         //其实这里感觉用指针也是比较方便
     
234.         int j;
     
235.         for (j = 0; j < i - 1; j++){
     
236.                 temp[j] = ch[j];
     
237.         }
     
238.         for (; j < i - 1 + t.length; j++){
     
239.                 temp[j] = t.ch[j - i + 1];
     
240.         }
     
241.         for (; j < length + t.length; j++){
     
242.                 temp[j] = ch[j - t.length];
     
243.         }
     
244. 
     
245.         delete[]ch;
     
246.         ch = temp;
     
247.         length = length + t.length;
     
248.         return true;
     
249. }
     
250. 
     
251. bool SqString::isEmpty(){
     
252.         return length ? false : true;
     
253. }
     
254. 
     
255. SqString SqString::operator=(char *s){
     
256.         strAssign_aux(s);//赋值辅助函数
     
257.         return *this;
     
258. }
     
259. 
     
260. SqString SqString::operator =(SqString right){
     
261.         if (this != &right){
     
262.                 clear();
     
263.                 ch = new char[right.length];
     
264.                 assert(ch != 0);
     
265. 
     
266.                 length = right.length;
     
267.                 for (int i = 0; i < right.length; i++){
     
268.                         ch[i] = right.ch[i];
     
269.                 }
     
270.         }
     
271.         return *this;
     
272. }
     
273. 
     
274. SqString SqString::operator +(char* s){
     
275.         insert(length + 1, s);//调用insert函数
     
276.         return *this;
     
277. }
     
278. 
     
279. SqString SqString::operator +(SqString right){
     
280.         insert(length + 1, right);
     
281.         return *this;
     
282. }
     
283. 
     
284. bool SqString::operator <(SqString right){
     
285.         int i;
     
286.         for (i = 0; i < length && i < right.length; i++){
     
287.                 if (ch[i] < right.ch[i]){
     
288.                         return true;
     
289.                 }
     
290.         }
     
291.         if (i < right.length){
     
292.                 return true;
     
293.         }
     
294.         else{
     
295.                 return false;
     
296.         }
     
297. }
     
298. 
     
299. int SqString::operator ==(char *s){
     
300.         int s_length;//获取s的长度
     
301.         for (int i = 0; s[i]; i++){
     
302.                 s_length = i;
     
303.         }
     
304.         for (int i = 0; i < length&&i < s_length; i++){
     
305.                 if (ch[i] != s[i]){
     
306.                         return ch[i] - s[i];
     
307.                 }
     
308.         }
     
309.         return length - s_length;
     
310. }
     
311. 
     
312. int SqString::operator ==(SqString right){
     
313.         for (int i = 0; i < length&&i < right.length; i++){
     
314.                 if (ch[i] != right.ch[i]){
     
315.                         return ch[i] - right.ch[i];
     
316.                 }
     
317.         }
     
318.         return length - right.length;
     
319. }
     
320. 
     
321. 
     
322. 
     
323. //赋值辅助函数
     
324. void SqString::strAssign_aux(char *s){
     
325.         clear();
     
326.         length = 0;
     
327.         for (int i = 0; s[i]; ++i){
     
328.                 length++;
     
329.         }
     
330.         cout << length << endl;
     
331. 
     
332.         ch = new char[length];
     
333.         assert(ch != 0);
     
334.         for (int i = 0; i < length; i++){
     
335.                 ch[i] = s[i];
     
336.         }
     
337. }
     
338. 
     
339. //删除第i个字符起长度为len的字符串
     
340. bool SqString::strDelete(int i, int len){
     
341.         char *temp;
     
342. 
     
343.         if (i<1 || i>length + 1){
     
344.                 return false;
     
345.         }
     
346.         temp = new char[length - len];
     
347. 
     
348.         assert(temp != 0);
     
349.         for (int j = 0; j < i - 1; j++){//前半段
     
350.                 temp[j] = ch[j];
     
351.         }
     
352.         for (int j = i - 1 + len; j < length; j++){//后半段
     
353.                 temp[j - len] = ch[j];
     
354.         }
     
355.         delete[]ch;
     
356.         ch = temp;
     
357.         length -= len;
     
358.         return true;
     
359. }
     
360. 
     
361. 
     
362. //取子串
     
363. bool SqString::subString(SqString &sub, int i, int len){
     
364.         if (i<1 || i>length || len < 0 || len>length - i + 1){
     
365.                 return false;
     
366.         }
     
367.         sub.clear();
     
368. 
     
369.         sub.ch = new char[len];
     
370.         assert(sub.ch != 0);
     
371.         for (int j = 0; j < len; j++){
     
372.                 sub.ch[j] = ch[i - 1 + j];
     
373.         }
     
374.         sub.length = len;
     
375.         return true;
     
376. }
     
377. 
     
378. 
     
379. //构造函数
     
380. SqString::SqString(){
     
381.         ch = NULL;
     
382.         length = 0;
     
383. }
     
384. 
     
385. SqString::~SqString(){
     
386.         clear();
     
387. }
     
388. 
     
389. //拷贝构造函数char类型
     
390. SqString::SqString(char *s){
     
391.         ch = NULL;
     
392.         strAssign_aux(s);
     
393. }
     
394. 
     
395. //拷贝构造函数
     
396. SqString::SqString(SqString &other){
     
397.         ch = new char[other.length];
     
398.         assert(ch != 0);
     
399.         length = other.length;
     
400.         for (int i = 0; i < length; i++){
     
401.                 ch[i] = other.ch[i];
     
402.         }
     
403. }
     
404. 
     
405. 
     
406. 
     
407. ostream& operator<<(ostream& out, SqString s){
     
408.         for (int i = 0; i < s.length; i++){
     
409.                 out << s.ch[i] << "  ";
     
410.         }
     
411.         cout << endl;
     
412.         return out;
     
413. }
     
414. 
     
415. int main(int argc, char* argv[]){
     
416.         SqString s1("Hello World!");
     
417.         cout << s1;
     
418.         SqString s2("haha,welcome to the program world,Hello World!,enjoy it");
     
419.         cout << s2;
     
420.         cout << "回溯法查找:";
     
421.         cout << s2.index(s1, 0) << endl;
     
422. 
     
423.         cout << "KMP查找:";
     
424.         cout << s2.index_KMP(s1, 0) << endl;
     
425.         return 0;
     
426. }
     

复制代码