#98 结构体排序引发的一连串问题

1
2
3
4
5
6
7
8
9
10
11
12
题目:
给出n个仅由小写字幕构成的字符串,仅按其首字母排序。(若首字母相同,则直接维持原来的顺序。)

输入格式:
第一行为n。
接下来n行,每行一个串。

输出格式:
n行,按排好的顺序,每行一个串。

数据规定:
n <= 1000, 串长小于100000。

话说这题前前后后每周大概抽两个小时来搞这题,未怀疑过评测系统出问题,因为我看见老师过了。 前前后后拖了一个月的时间。

放上最终的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <time.h>

using namespace std;
struct Value
{
char str[10000];
};

void structSort(Value *a, int n)
{
int i = 0, j = n;
char *temp[1000];
char *help;

//开辟临时存放字符串的空间
char *p = (char *)malloc( sizeof(char)*10000*n );

//保存地址
for( i = 0; i < n; i++ )
temp[i] = &amp;a[i].str[0];

//冒泡排序
for( j = n; j > 0; j-- )
for( i = 0; i < j-1; i++ )
if( *temp[i] > *temp[i+1] ) // 对地址进行排序
{
help = temp[i];
temp[i] = temp[i+1];
temp[i+1] = help;
}
//按地址从结构体拷出
for( i = 0; i < n; i++ )
strcpy( p + i*10000 ,temp[i] );

//拷贝回结构体
for( i = 0; i < n; i++ )
strcpy(a[i].str, p + i*10000 );

free(p);
}

int n;
Value a[5000];

int main()
{
scanf("%d", &amp;n);
for (int i = 0; i<n; i++)
{
scanf("%s", a[i].str);
}
structSort(a, n);
for (int i = 0; i<n; i++)
{
printf("%s\n", a[i].str);
}
printf("\n\nTime used = %.0lf ms\n",(double)(1000*clock()/CLOCKS_PER_SEC));
return 0;
}

下面详细说说这道题碰见的事情。

1、排序算法的选取

一开始并没有太在意这道题有什么特别之处,感觉特别平常的一道题,想想冒泡太慢,快排不熟悉,于是选择了相对简单的选择排序。

提交了好几次发现问题,选择排序并不能保证:“若首字母相同,则直接维持原来的顺序。” (排序的稳定性)

下面是反例: 数据为: wjbzbmr wa ac orz tle 如果是选择排序最后的结果会变成: ac orz tle wa wjbzbmr

于是果断滚回去用了冒泡,结果直接用冒泡会超时,这是字符串复制照成的(代码如下)。

1
2
3
4
5
6
7
8
9
10
11
12
13
void structSort(Value *a, int n)
{
int i = 0, j = n;
Value help;
for( j = n; j > 0; j-- )
for( i = 0; i < j-1; i++ )
if( a[i].str[0] >a[i+1].str[0] )
{
help = a[i];
a[i] = a[i+1];
a[i+1] = help;
}
}

刚开始没有思考是什么原因造成的,马上开始着手使用快排。

猛然想到,快排和选择排序一样,会造成上面反例的结果。所以当时瞬间傻了一阵子。

后来想到,即使冒泡没有花多少时间,但是主要时间则花在了交换两个字符串上。

所以,开始采用地址的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void structSort(Value *a, int n)
{
int i = 0, j = n;
char *temp[1000];
char *help;
char temp_str[1000][100000];

//保存地址
for( i = 0; i < n; i++ )
temp[i] = &amp;a[i].str[0];

//冒泡排序
for( j = n; j > 0; j-- )
for( i = 0; i < j-1; i++ )
if( *temp[i] > *temp[i+1] ) // 对地址进行排序
{
help = temp[i];
temp[i] = temp[i+1];
temp[i+1] = help;
}
//按地址从结构体拷出
for( i = 0; i < n; i++ )
strcpy( temp_str[i], temp[i] );

//拷贝回结构体
for( i = 0; i < n; i++ )
strcpy(a[i].str, temp_str[i] );

free(p);
}

上面的做法直接在函数内申请了char temp_str[1000][100000];直接导致栈溢出。

所以后来改成了动态内存分配的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void structSort(Value *a, int n)
{
int i = 0, j = n;
char *temp[1000];
char *help;

//开辟临时存放字符串的空间
char *p = (char *)malloc( sizeof(char)*10000*n );

//保存地址
for( i = 0; i < n; i++ )
temp[i] = &amp;a[i].str[0];

//冒泡排序
for( j = n; j > 0; j-- )
for( i = 0; i < j-1; i++ )
if( *temp[i] > *temp[i+1] ) // 对地址进行排序
{
help = temp[i];
temp[i] = temp[i+1];
temp[i+1] = help;
}
//按地址从结构体拷出
for( i = 0; i < n; i++ )
strcpy( p + i*10000 ,temp[i] );

//拷贝回结构体
for( i = 0; i < n; i++ )
strcpy(a[i].str, p + i*10000 );

free(p);
}

得到了最终的代码。

2、数据构造

但是这TNND死活就不过,十个测试数据,对两个,其他八个属于运行错误。

然后被这个错误折腾了半个月,今天终于知道了,原来我代码是正确的,错在评测系统。

构造了一个极限数据:1000*10000的数据包。

使用下面的程序来造数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <windows.h>
#include<stdlib.h>
#include<time.h>
#define R 1 //随机数启用1

int main()
{
FILE *fp;
char desktop[100];
char str1[20]={0};
unsigned long size=20;
GetUserName(str1,&amp;size);
sprintf(desktop,"C:\\Users\\%s\\Desktop\\%s",str1,"1.in");
freopen(desktop,"w",stdout);
#if(R==1)

int number;
int N=123 ; //0到?内的随机数
srand(time(NULL)*100);
number=rand()%N+1;
#endif
//开始输入到文件
printf("%d\n",1000);
for(int k=1;k<=1000;k++)
{
for(int j=1;j<=10000;j++)
{
number=rand()%N;
if(number>=97&amp;&amp;number<=122)
printf("%c",number);
}
printf("\n");
}
return 0;
}

运用重定向来测试到底会运行多长时间:

用下面这条语句来测试运行时间:

1
printf("\n\nTime used = %.0lf ms\n",(double)(1000*clock()/CLOCKS_PER_SEC));

直接在冒泡内进行字符串的交换,所花时间为:1702ms

使用指针排序所花的时间为:163ms

评测系统允许的时间最大为1s,显然是对的。

然后我就不说什么了。以后还是要有自身判断正误的能力。

如果我的文章对你起到了帮助,你可以选择金额不限的捐助,帮助我写出更多的文章。