将字符串中的字符'*'移到串的前部分 的一个解法

2005年11月金山笔试题。编码完成下面的处理函数。
函数将字符串中的字符'*'移到串的前部分，

前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。
如原始串为：ab**cd**e*12，
处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）

自己的算法分析:

有两个指针q1和q2，从后向前遍历，q2始终指向*，q1则指向*之前的应该与*进行交换的元素。下面附上代码：

#include <iostream>using namespace std;void swap(char* p, char* q){int temp = *p;*p = *q;*q = temp;}int movStar(char* p, int n){char* q1 = p+n-1, *q2 = p+n-1;while (q1 > p){while (*q2 != '*')q2--;q1 = q2-1;while (*q1 == '*')q1--;swap(q1, q2);cout<<p<<endl;}return q2-q1+1;}int main(){char p[]="ab**cd**e*12";int cnt = movStar(p,strlen(p));cout<<"after movStar..."<<endl;cout<<"number of * is: "<<cnt<<endl;cout<<p<<endl;}

另一种方法：

#include <iostream>using namespace std;void movStar(char* p){int len = strlen(p);int i;for (i = len-1; p[i]!='*';i--);//从后向前找到第一个'*'，然后开始覆盖。int j = i;for (;i >= 0; i--){if (p[i]!='*'){p[j--]=p[i];}}while(j>=0){p[j--]='*';}}int main(){char p[]="ab**cd**e*12";  cout<<p<<endl;movStar(p);cout<<p<<endl;}