可用分押宝游戏火热进行中...	专题改版：Java Web 专题

(急需）求一种高效算法，用于将一串不定长的字符串的先后顺序打乱

楼主czjcsdn（葫芦）2003-09-01 09:49:16 在 C/C++ / 工具平台和程序库提问

需要做一个函数，接收一个字符串，字符串按一定格式，如下：

112334,abcde,77322,ad324,akdfklsdf,98932q3,........

就是上面这个意思，字符串中可能有多个以逗号","分隔的字符串，具体有

多少个不一定，现在需要将类似于上面的一长串以逗号","为分隔为单位打

乱。

本人想过以链表的方式，先以逗号","为分隔标记，将字符串放入一个结构

链表，然后在链表中排序，但这样效率太低，现请求一种算法，可以将上面

的字符按逗号","分隔后打乱，生成一个打乱的字符串。

谢谢！！！问题点数：100、回复次数：11Top

1 楼tjianliang（乡关何处）回复于 2003-09-01 09:58:30 得分 5

1、开个大数组，将字符串一一读入

2、利用随机函数产生数组下标取串，并添加到新串中（新串初始为空）Top

2 楼czjcsdn（葫芦）回复于 2003-09-01 10:40:39 得分 0

Re： tjianliang(乡关何处)

　　但在C++里，创建数组时需要明确指定数组元素个数，而我的字符串有多少个是不一定的，如果将数组开得过大，则浪费内存了Top

3 楼rtdb（东临碣石）回复于 2003-09-01 10:51:07 得分 0

我说，你都到泛型技术这个版来问，还说什么“指定数组元素个数”！
一个vector<string>轻松完成。
Top

4 楼sandrowjw（我的小猫照片给弄坏了，心都碎了）回复于 2003-09-01 11:29:13 得分 10

呵呵，支持楼上。
实际上记录每个子串开始的位置，放到一个vector里，然后把这个vector打乱，然后再根据开始位置去读出子串拼接起来也可以。这样打乱的时候可以快一些，但是输出比较慢。Top

5 楼czjcsdn（葫芦）回复于 2003-09-01 12:16:39 得分 0

对不起，可能我放错位置了，我现在想要的一种算法是：尽可能高效，时间尽量少。Top

6 楼fangrk（加把油，伙计！）回复于 2003-09-01 12:21:44 得分 60

#include <algorithm>
#include <string>
#include <deque>
#include <sstream>
#include <iterator>
#include <iostream>
using namespace std;

int main()
{
const string str("112334,abcde,77322,ad324,akdfklsdf,98932q3");
string T;
istringstream ISS(str);
deque<string> strSeq;
while(getline(ISS,T,',')) strSeq.push_back(T);
copy(strSeq.begin(),strSeq.end(),ostream_iterator<string>(cout,"\n"));
cout<<"After random shuffle:"<<endl;
random_shuffle(strSeq.begin(),strSeq.end());
copy(strSeq.begin(),strSeq.end(),ostream_iterator<string>(cout,"\n"));
}

C:\temp>bcc32 -WR -WC a
Borland C++ 5.6.4 for Win32 Copyright (c) 1993, 2002 Borland
a.cpp:
Turbo Incremental Link 5.64 Copyright (c) 1997-2002 Borland

C:\temp>a
112334
abcde
77322
ad324
akdfklsdf
98932q3
After random shuffle:
abcde
98932q3
ad324
77322
112334
akdfklsdf

C:\temp>Top

7 楼sandrowjw（我的小猫照片给弄坏了，心都碎了）回复于 2003-09-01 12:26:16 得分 10

你指的是打乱的算法？用洗牌就可以了，把每个位置上的元素和一个随机位置上的交换。Top

8 楼goodboy1881（积木)(谁都别拦着我在水源升星）回复于 2003-09-01 12:42:52 得分 15

random_shuffle(strSeq.begin(),strSeq.end());

哎呀，好像有了STL之后，大家都不愿意去动脑筋写个自己的算法了
不过说实话，人家的代码写的就是有水平啊。Top

9 楼czjcsdn（葫芦）回复于 2003-09-01 13:15:00 得分 0

Re: fangrk(加把油，伙计！)

谢谢，你的程序我现在在看，不过
const string str("112334,abcde,77322,ad324,akdfklsdf,98932q3");
这一句好象不能符合我的要求，我的意思是：一个函数，接收一个字符串，字符串中以逗号分隔为若干个字符串，这若干个字符串的个数不一定，因此我在问题中用了"............"，因此这里好象不能用 const。
不知提出的异议是否有理，请指教。
Top

10 楼czjcsdn（葫芦）回复于 2003-09-01 15:23:54 得分 0

Re: fangrk(加把油，伙计！)

另外我朋友试了以后，发现每次输出的打乱结果是一样了，这就更不符合要求了，这就不是随机的了。Top

11 楼fangrk（加把油，伙计！）回复于 2003-09-01 19:07:37 得分 0

#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>bcc32 -WR -WC a
Borland C++ 5.6.4 for Win32 Copyright (c) 1993, 2002 Borland
a.cpp:
Turbo Incremental Link 5.64 Copyright (c) 1997-2002 Borland

C:\temp>a
输入一行字符串,用','分隔:
123,568,loiuk,-0oi,7,8&*,rtrtr,hehe,we will will rock you!,how are you
想随机显示几次?
3
After random shuffle:1
we will will rock you!,hehe,how are you,rtrtr,7,loiuk,123,-0oi,568,8&*,

After random shuffle:2
rtrtr,123,how are you,loiuk,hehe,-0oi,7,we will will rock you!,8&*,568,

After random shuffle:3
hehe,loiuk,we will will rock you!,8&*,rtrtr,123,568,-0oi,how are you,7,

C:\temp>Top