(急需）求一种高效算法，用于将一串不定长的字符串的先后顺序打乱
需要做一个函数，接收一个字符串，字符串按一定格式，如下：
112334,abcde,77322,ad324,akdfklsdf,98932q3,........
就是上面这个意思，字符串中可能有多个以逗号","分隔的字符串，具体有
多少个不一定，现在需要将类似于上面的一长串以逗号","为分隔单位打
乱。
本人想过以链表的方式，先以逗号","为分隔标记，将字符串放入一个结构
链表，然后在链表中排序，但这样效率太低，现请求一种算法，可以将上面
的字符按逗号","分隔后打乱，生成一个打乱的字符串。
谢谢！！！
问题点数：100、回复次数：6Top
1 楼jyfcsdn（）回复于 2003-09-02 09:39:50 得分 20
VC6.0
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
typedef vector<char>::iterator strtab_iterator;
typedef pair<strtab_iterator, strtab_iterator> StrWord;
struct strtab_print
{
ostream& out;
strtab_print(ostream& os): out(os) {}
void operator() (const StrWord& s) const
{
copy(s.first, s.second, ostream_iterator<char>(out));
out << ' ';
}
};
int main()
{
//string is store in vector<char>
char values[] = "112334,abcde,77322,ad324,akdfklsdf,98932q3";
vector<char> InputString;
copy(values, values + strlen(values), back_insert_iterator<vector<char> >(InputString));
//分割查找各个单词的首尾位置，组成一个pair存在OutputStirng中
vector<StrWord> OutputString;
strtab_iterator start = InputString.begin();
strtab_iterator stop = InputString.end();
while(start != stop)
{
strtab_iterator next = find(start, stop, ',');
if(next != stop)
{
++next;
}
OutputString.push_back(make_pair(start, next));
start = next;
}
//对这些pair随机排序，就可以打乱顺序
random_shuffle(OutputString.begin(), OutputString.end()); // shulffle the order of the words
//然后就可以用这些pair构成新的字符串,我就是答应
for_each(OutputString.begin(), OutputString.end(), strtab_print(cout));
return 0;
}
Top
2 楼jyfcsdn（）回复于 2003-09-02 09:44:53 得分 0
我用的是STLPort STL4.5.3, 编译运行都正常
在VC.net中也运行正常
估计微软VC6.0配有的P.J.Plauge版本的STL也能够运行Top
3 楼meshwork（白开水）回复于 2003-09-03 17:04:52 得分 20
可以试试random_shuffle(), 不知道效率是否很好.Top
4 楼fangrk（加把油，伙计！）回复于 2003-09-03 20:04:57 得分 20
诶
#include <algorithm>
#include <string>
#include <deque>
#include <sstream>
#include <iterator>
#include <iostream>
using namespace std;
void RandomShow(const string& str,size_t i)
{
istringstream ISS(str);
deque<string> strSeq;
string T;
while(getline(ISS,T,',')) strSeq.push_back(T);
randomize();//！
for(size_t k=0;k<i;){
cout<<"After random shuffle:"<<++k<<endl;
random_shuffle(strSeq.begin(),strSeq.end());
copy(strSeq.begin(),strSeq.end(),ostream_iterator<string>(cout,","));
cout<<endl<<endl;
}
}
int main()
{
cout<<"输入一行字符串,用','分隔:"<<endl;
string S;
getline(cin,S);
size_t i;
cout<<"想随机显示几次?"<<endl;
cin>>i;
RandomShow(S,i);
}
C:\temp>a
输入一行字符串,用','分隔:
123,568,loiuk,-0oi,7,8&*,rtrtr,hehe,we will will rock you!,how are you
想随机显示几次?
2
After random shuffle:1
rtrtr,loiuk,568,123,-0oi,we will will rock you!,how are you,8&*,7,hehe,
After random shuffle:2
123,we will will rock you!,7,568,rtrtr,-0oi,loiuk,8&*,hehe,how are you,
C:\temp>a
输入一行字符串,用','分隔:
123,568,loiuk,-0oi,7,8&*,rtrtr,hehe,we will will rock you!,how are you
想随机显示几次?
2
After random shuffle:1
we will will rock you!,rtrtr,loiuk,568,123,hehe,-0oi,7,how are you,8&*,
After random shuffle:2
how are you,-0oi,hehe,123,loiuk,568,7,8&*,we will will rock you!,rtrtr,
C:\temp>Top
5 楼leechildren（里奥）回复于 2003-09-05 02:15:41 得分 20
我调用的都是系统内部的函数， 在效率上应该没什么大问题的。
在.net上运行没问题。
#include <algorithm>
#include <iterator>
#include <ctime>
using namespace std;
void filter(vector<string> & svec, string &str)
{
string::size_type prepos=0, pos=0, endpos=0;
while((pos = str.find_first_of(',', pos))!=string::npos )
{
endpos = pos - prepos;
svec.push_back(str.substr(prepos, endpos) );
prepos=++pos;
}
}
int main()
{
string str="112334,abcde,77322,ad324,akdfklsdf,98932q3";
vector<string> svec;
filter(svec, str);
srand((unsigned)time(NULL));
random_shuffle(svec.begin(), svec.end());
copy(svec.begin(), svec.end()-1, ostream_iterator<string> (cout, ","));
cout << *(svec.end()-1) << endl;
}Top
6 楼jyfcsdn（）回复于 2003-09-05 08:51:38 得分 20
我的方法参照了《General Programming and STL》第一章里的例子。
他没有对vector中的string排序，应为string是个比较复杂的类，直接对他排序要涉及到string之间的复制，也就是需要分配内存地址，内存拷贝等，效率不高。我是对指向每个单词首尾位置的iterator 的pair进行排序，这样原来的字符串没有任何位置变化，不用相互移动位置。pair的排序效率肯定比string排序效率高多了。Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
