编码完成下面的处理函数。函数将字符串中的字符“*”移动到串的前部分，前面的非“*”字符后移，但不能改变非“*”字符的先后顺序，函数返回串中字符“*”的数量。如原始串为：ab**cd**e**12，处理后为******abcde12，且函数返回值为5（要求使用尽量少的时间和辅助空间）
     贴出自己程序的运行时间。

给你四种方法：第一种：

1. #include <iostream>
   
2. #include <iomanip>
   
3. #include <limits>
   
4. 
   
5. using namespace std;
   
6. void swap_star(char& a, char& b){
   
7.         char t;
   
8.         t = a;
   
9.         a = b;
   
10.         b = t;
    
11. }
    
12. 
    
13. 
    
14. int main()
    
15. {
    
16.         char star[] = "ab**cd**e*12";
    
17.         cout << " star : " << star << endl;
    
18.         int sz = sizeof(star);
    
19.         int starpos = sz - 2;
    
20.         int nonstar = sz - 2;
    
21.         int cnt = 0;
    
22.         while(starpos >= 0 && nonstar >= 0){
    
23.                 while(star[starpos] != '*' && starpos > 0){ //从末位开始查找‘*’的索引
    
24.                         --starpos;
    
25.                 }
    
26.                 if(starpos > 0){  // 计算非‘*’字符的起始索引，与‘*’一样，倒序搜索，因为要求不改变原非‘*’字符的顺序
    
27.                         if(starpos > nonstar){
    
28.                                 nonstar = nonstar - 1;
    
29.                         }else{
    
30.                                 nonstar = starpos - 1;
    
31.                         }
    
32.                 }else{  // 如果‘*’索引到了 0， 则说明已交换顺序完毕
    
33.                         break;
    
34.                 }
    
35.                 while(star[nonstar] == '*' && nonstar > 0){ // 找到待交换非‘*’字符索引
    
36.                         --nonstar;
    
37.                 }
    
38.                 if(star[nonstar] != '*' && nonstar >= 0){
    
39.                         swap_star(star[starpos],star[nonstar]);                       
    
40.                         starpos = starpos - 1;
    
41.                 }else{
    
42.                         cnt = starpos + 1;  // 交换完毕，‘*’字符的索引是从0开始的最后一个‘*’字符的索引
    
43.                         break;
    
44.                 }
    
45.         }
    
46. 
    
47.         cout << "finally : " << star <<  " star number : " << cnt << endl;
    
48. 
    
49.         return 0;
    
50. }

复制代码

第二种：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. void movStar(char* p)
   
5. {
   
6.         int len = strlen(p);
   
7.         int i;
   
8.         for (i = len-1; p[i]!='*';i--);        //从后向前找到第一个'*'，然后开始覆盖。
   
9.         int j = i;
   
10.         for (;i >= 0; i--)
    
11.         {
    
12.                 if (p[i]!='*')
    
13.                 {
    
14.                         p[j--]=p[i];
    
15.                 }
    
16.         }
    
17.         while(j>=0)
    
18.         {
    
19.                 p[j--]='*';
    
20.         }
    
21. }
    
22. 
    
23. int main()
    
24. {
    
25.         char p[]="ab**cd**e*12";  
    
26.         cout<<p<<endl;
    
27.         movStar(p);
    
28.         cout<<p<<endl;
    
29. }

复制代码

第三种：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. void swap(char* p, char* q)
   
5. {
   
6.         int temp = *p;
   
7.         *p = *q;
   
8.         *q = temp;
   
9. }
   
10. 
    
11. int movStar(char* p, int n)
    
12. {
    
13.         char* q1 = p+n-1, *q2 = p+n-1;
    
14.         while (q1 > p)
    
15.         {
    
16.                 while (*q2 != '*')
    
17.                         q2--;
    
18.                 q1 = q2-1;
    
19.                 while (*q1 == '*')
    
20.                         q1--;
    
21.                 swap(q1, q2);
    
22.                 cout<<p<<endl;
    
23.         }
    
24.         return q2-q1+1;
    
25. }
    
26. 
    
27. 
    
28. int main()
    
29. {
    
30.         char p[]="ab**cd**e*12";
    
31.         int cnt = movStar(p,strlen(p));
    
32.         cout<<"after movStar..."<<endl;
    
33.         cout<<"number of * is: "<<cnt<<endl;
    
34.         cout<<p<<endl;
    
35. }

复制代码

第四种：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. void swap(char* str,int i,int j)
   
5. {
   
6.         if(str[i] != str[j])
   
7.         {
   
8.                 str[i]^=str[j];
   
9.                 str[j]^=str[i];
   
10.                 str[i]^=str[j];
    
11.         }
    
12. }
    
13. int departStars(char *str)
    
14. {
    
15.         //k停留在其它字母上
    
16.         int len,i,k,cout=0;
    
17.         if(str==NULL) return 0;
    
18.         if((len=strlen(str)) < 1) return 0;
    
19.         i=k=len-1;
    
20.         while(i>=0)
    
21.         {
    
22.                 if(str[i]!='*')
    
23.                 {
    
24.                         swap(str,i--,k--);
    
25.                 }
    
26.                 else
    
27.                 {
    
28.                         --i;
    
29.                         ++cout;
    
30.                 }
    
31.         }
    
32.         return cout;
    
33. }
    
34. int main(void) {
    
35.         char str[]="*ABCD*D*BSD**d**";
    
36.         printf("%d %s",departStars(str),str);
    
37.         return 0;
    
38. }

复制代码

楼主我给你写了一个，你看看是不是你要的，你可以自己再改一下

1. 
   
2. public class Number {
   
3.         public static void main(String[] args) {
   
4.                 StringBuilder sb = new StringBuilder("ab**cd**e**12");
   
5.                 StringBuilder key = new StringBuilder(sb.length());
   
6.                 int num = 0;
   
7.                 for (int i = 0; i < sb.length(); i++) {
   
8.                         if ('*' != sb.charAt(i)) {
   
9.                                 key.append(sb.charAt(i));
   
10.                         } else {
    
11.                                 num++;
    
12.                         }
    
13.                 }
    
14.                 key = key.reverse();
    
15.                 for (int i = 0; i < num; i++) {
    
16.                         key.append('*');
    
17.                 }
    
18.                 System.out.println(key.reverse());
    
19.                 System.out.println(num);
    
20. 
    
21.         }
    
22. 
    
23. }
    

复制代码

获取长度len1，删除所有*
获取长度len2，在开始位置添加*
返回len2-len1