【算法习作】字符串处理两例
1.按词倒置一个句子
题目：例如”I am a student”，经处理后得到”student am a I”，限定除了一个空格外单词间没有任何其他分隔符。
解析：将整个字符串倒置后分别对每一个词进行倒置即可。
1: /*
2: * =====================================================================================
3: *
4: * Filename: rotateString.cpp
5: *
6: * Description: rotate a string with the sequences of a word kept
7: *
8: * Version: 1.0
9: * Created: 04/15/2011 04:28:13 PM
10: * Revision: none
11: * Compiler: g++
12: *
13: * Author: gnuhpc (http://blog.csdn.net/gnuhpc), warmbupt@gmail.com
14: *
15: * =====================================================================================
16: */
17:
18: #include "../include/utils.h"
19:
20: void rotateString(string& target_string)
21: {
22: size_t size = target_string.size();
23: size_t begin = 0;
24: size_t end = size-1;
25: reverseString(target_string,begin,end);
26:
27: begin = 0;
28: end = 0;
29:
30: while(end!=size)
31: {
32: if(target_string[end]!= ){
33: ++end;
34: }
35: else{
36: reverseString(target_string,begin,end-1);
37: begin = end+1;
38: ++end;
39: }
40: }
41: }
42:
43: int main(int argc, char *argv[])
44: {
45: string target_string;
46: cout << "please tell me the string:"<<endl;
47: getline(cin, target_string);
48:
49: cout << target_string << endl;
50: rotateString(target_string);
51: cout << target_string << endl;
52: }
2.左旋转字符串
题目：输入：abcdefg,2 ， 输出：cdefgab ，复杂度要求：不使用额外空间存储字符串。
思路：S=abcdefg , S1=ab, S2=cdefg, !S1=ba, !S2 = gfedc => !((!S1)(!S2)) 即为所求。也就是说先按欲倒置的位置将原字符串划分为两个子串，分别倒置，然后再将整个字符串倒置即可求得。
1: /*
2: * =====================================================================================
3: *
4: * Filename: rotateString.cpp
5: *
6: * Description: rotate a string from a specific position
7: *
8: * Version: 1.0
9: * Created: 04/15/2011 04:28:13 PM
10: * Revision: none
11: * Compiler: g++
12: *
13: * Author: gnuhpc (http://blog.csdn.net/gnuhpc), warmbupt@gmail.com
14: *
15: * =====================================================================================
16: */
17:
18: #include "../include/utils.h"
19:
20: void rotateString(string& target_string, const size_t position)
21: {
22: assert((position>1)&&(position<target_string.size()));
23: int size = target_string.size();
24: size_t A_begin = 0;
25: size_t A_end = position-1;
26: size_t B_begin = position;
27: size_t B_end = size-1;
28: reverseString(target_string,A_begin,A_end);
29: reverseString(target_string,B_begin,B_end);
30: reverseString(target_string,A_begin,B_end);
31:
32: cout << target_string <<endl;
33: }
34:
35: int main(int argc, char *argv[])
36: {
37: string target_string;
38: genRandomString(target_string,10);
39: size_t position;
40: cout << target_string << endl;
41: cout << "please tell me the position:"<<endl;
42: cin >> position;
43:
44: rotateString(target_string,position);
45: }
辅助函数reverseString为：1: void reverseString(string &target_string, size_t begin, size_t end)
2: {
3: while(begin<end){
4: target_string[begin]^=target_string[end];
5: target_string[end]^=target_string[begin];
6: target_string[begin]^=target_string[end];
7: ++begin;
8: --end;
9: }
10: }
补充：综合编程 , 其他综合 ,
