首页 > 试题广场 >

整理科研数据文件

[编程题]整理科研数据文件
  • 热度指数：387 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
一位科研人员在进行一系列实验后，得到了大量的以字母和数字混合命名的数据文件，例如 `Exp-A-Run1`, `Exp-A-Run01`, `Exp-A-Run10` 等。

标准的按文件名排序（字典序）会错误地将 `Exp-A-Run10` 排在 `Exp-A-Run2` 之前，这给数据分析带来了不便。
为了解决这个问题，需要一个能够理解数字真实大小的“自然排序”程序。

您能否编写一个程序，对给定的 N 个文件名进行这种特殊的自然排序？

排序规则：
程序需要从左到右逐段比较两个文件名 A 和 B：

1. 分段处理 ：将文件名分割成“连续的非数字字符串”和“连续的数字字符串”段落。例如，`ts010tc12` 被视为 `["ts", "010", "tc", "12"]`。
2. 逐段比较 ：
如果 A 和 B 的当前段都是非数字串，则按字典序（区分大小写）进行比较。如果不同，则排序完成。
如果 A 和 B 的当前段都是数字串，则将它们转换为整数值进行比较。如果数值不同，则排序完成。
如果一个是数字串，另一个是非数字串，则规定数字串排在前面。
3. 前缀优先 ：如果一个文件名是另一个文件名的前缀（例如 `test` 和 `testcase1`），则较短的前缀名排在前面。
4. 稳定性 ：排序必须是稳定的。如果根据以上所有规则，两个文件名被认为是等价的（例如 `Run01` 和 `Run1`），它们在输入中的原始相对顺序必须在输出中保持不变。

输入描述:
第一行：一个整数 N，代表待排序的文件名数量。
(1 \le N \le 100)
接下来 N 行：每行一个文件名 F_i。
文件名仅包含大小写字母和数字。
文件名长度在 [1, 127] 范围内。
文件名中任意连续的数字串长度不超过 9。


输出描述:
共 N 行，每行输出一个排序后的文件名。
示例1

输入

3
ts1tc1
ts1tc01
ts0tc1

输出

ts0tc1
ts1tc1
ts1tc01
示例2

输入

2
testcase10
testcase9

输出

testcase9
testcase10
示例3

输入

3
ts09sc1
ts01tc1
ts010tc12

输出

ts01tc1
ts09sc1
ts010tc12

备注:
本题由牛友@Charles 整理上传
算法知识视频讲解
添加回答
C
久辰天头像 久辰天
确实复杂，涉及到数字判断，排序函数，指针数组，结构定义
#include <stdio.h> ——输入输出
#include <stdlib.h>——qsort() 排序、内存分配等函数
#include <string.h>——字符串函数相关库
#include <ctype.h>——isdigit()判断是数字   isalpha()判断是字母   isalnum()判断是字母或数字  topper()全部转换大写  tolower()全部转换小写

//定义默认值
#define MAX_N 100
#define MAX_LEN 128

//定义结构体并重命名为 File
typedef struct {          
    char name[MAX_LEN];  //定义name是个字符串
    int original_index;
} File;

// 定义比较函数：实现自然排序逻辑
//void *a---意味着 传入的指针 *a 不限制类型
int compare(const void *a, const void *b) {
    File *fa = (File *)a;
    //File *fa —— 定义指针 *fa，类型为File
    //(File *)a —— 强制类型转换，将类型不定的指针 *a的类型强制转换为 file*
    File *fb = (File *)b;
   
    const char *str1 = fa->name;
    //const定义为常量，不可变更值，但是可以变更指针指向
    //fa->name  表示fa指向对象为 File结构体 中的 name
    const char *str2 = fb->name;
   
    while (*str1 && *str2) {  //*str1 && *str2该条件意味着这个循环在遇见第一个终止符或空值时停止，如 '\0'
        //isdigit()——确认所有内容为数字，是则返回true,不是则返回false
        // 两者都是数字：解析整数比较
        //*str1指向str1[0],str1++指向str1[1],后续同理
        if (isdigit(*str1) && isdigit(*str2)) {
            long num1 = 0, num2 = 0; //整数值初始化
            while (isdigit(*str1)) {   //计算str1的数字代表的值
                num1 = num1 * 10 + (*str1 - '0');
                str1++;
            }
            while (isdigit(*str2)) {  //计算str2的数字串代表的值
                num2 = num2 * 10 + (*str2 - '0');
                str2++;
            }
            if (num1 != num2) return (num1 > num2) ? 1 : -1;
            //如果num1不等于num2————num1大则返回1，否则返回-1
        } else if (!isdigit(*str1) && !isdigit(*str2)) {
            // ！ 代表否定， !isdigit() 代表不是数字
            // 两者都不是数字：字典序比较
            if (*str1 != *str2) {  //若字符不等
                return (*str1 > *str2) ? 1 : -1;
                //*str1大就返回1，*str2大就返回-1
            }
            str1++;
            str2++;
        } else {
            // 一个是数字，一个是字符：数字优先（排前面）
            return isdigit(*str1) ? -1 : 1;
            //*str1是数字就返回-1 ，*str1是字符就返回1
        }
    }
   
    // 前缀处理  当一个指针出现空值，str1先则-1，str2先则1
    if (*str1 == '\0' && *str2 != '\0') return -1;
    if (*str1 != '\0' && *str2 == '\0') return 1;
   
    // 稳定性：如果内容逻辑相等，按输入顺序排
    return fa->original_index - fb->original_index;
    //先输入的是a，则 a-b 就是从小到大排序 b-a 就是从大到小排序
    //qsort()参数函数返回值固定写法： return *（char*)a - *(char*)b
    //固定写法含义： （char*)-强制将a转化为char，*（的星号作用是取得a这个指针存放地址里边的值
    //fa->original_index 函数定义时已写File *fa = (File *)a，所以可以直接用fa来指向
    //因为函数定义时用const char *str1 = fa->name;，所以重新使fa重定向到original_index
}

int main() {
    int N;
    scanf("%d", &N);
    File files[MAX_N]; //创建名为files的File类型结构数组
   
    for (int i = 0; i < N; i++) {
        scanf("%s", files[i].name);  //输入字符串，计入name
        files[i].original_index = i; //录入位置信息，计入original_index
    }
   
    qsort(files, N, sizeof(File), compare);
    //qsort()排序函数参数介绍
    //qsort(数组名，排序个数，单个元素大小，排序函数)
    //排序函数固定模版：
/*
int sort（ const void* a,const void* b）{
    return *（char*)a - *(char*)b
}
a-b是从小到大排序（排序函数返回值小于0），b-a是从大到小排序（排序函数返回值大于0）

*/

   
    for (int i = 0; i < N; i++) {
        printf("%s\n", files[i].name);
    }
   
    return 0;
}

发表于 2026-01-07 23:20:17 回复(0)
提交观点

问题信息

来自：2025年秋招-华为-...
难度：
1条回答 68浏览

热门推荐

相关试题

整理科研数据文件

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号