2

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

 2 years ago
source link: https://changkun.de/blog/posts/%E7%BB%93%E6%9E%84%E4%BD%93%E6%8E%92%E5%BA%8F%E5%BC%95%E5%8F%91%E7%9A%84%E4%B8%80%E8%BF%9E%E4%B8%B2%E9%97%AE%E9%A2%98/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

Published at:

2013-05-07

  |  

Reading: 1638 words ~4min

  |  

PV/UV: 5/5

题目：
给出n个仅由小写字幕构成的字符串，仅按其首字母排序。（若首字母相同，则直接维持原来的顺序。）

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

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

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

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

放上最终的代码：

#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] = &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", &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

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

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; 
            }
}

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

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

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

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

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] = &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];直接导致栈溢出。

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

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] = &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的数据包。

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

#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,&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&&number<=122)
        printf("%c",number);
        }
        printf("\n");
    }
    return 0;
}

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

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

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

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

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

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

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK