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

 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，显然是对的。

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