lantern

用户名：dotcpp0630548

访问量：2259

签　名：

等　　级
排　　名	247
经　　验	6050
参赛次数	8
文章发表	105
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

如有疑问，加QQ：2429936707

TA的其他文章

题解，结构体数组解法
浏览：5

循环链表解法（c语言代码）
浏览：4

题解，标记
浏览：3

你可能喜欢

使用qsort函数和结构体数组

　　作者: lantern　　　　发表时间：2024-11-19 18:49:52 浏览：4　|　评论：0　

原题链接：蓝桥杯2022年第十三届省赛真题-数位排序

**思路：
1.输入处理：
输入两个整数 n 和 m。n 是要处理的数字的个数（从 1 到 n），m 是要输出排序后第 m 个数字的索引。
2.数据结构设计：
定义一个结构体 Number，包含两个成员：
num：保存数字的原始值。
wei_shu_he：保存该数字的“位数和”（即该数字各个数位的数字之和）。
3.计算位数和：
对于每个数字 1 到 n，将其转化为字符串，然后计算其各个字符（数字）的总和，这个总和就是该数字的“位数和”。
4.排序：
使用 qsort 函数对结构体数组 arr 进行排序。排序规则是：
首先根据 wei_shu_he（位数和）升序排序。
如果位数和相等，则根据原始数字 num 升序排序。**
```c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 定义一个结构体 Number，用于存储数字及其位数和
typedef struct
{
    int num;        // 原始数字
    int wei_shu_he; // 该数字的位数和
} Number;

// 排序函数，先比较位数和，再比较原始数字
int cmp(const void *a, const void *b)
{
    Number A = *(Number *)a; // 将 a 转换为 Number 类型
    Number B = *(Number *)b; // 将 b 转换为 Number 类型

// 先按位数和排序，位数和相同则按原始数字排序
    if (A.wei_shu_he == B.wei_shu_he)
    {
        return A.num - B.num;
    }
    else
    {
        return A.wei_shu_he - B.wei_shu_he;
    }
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    Number arr[n]; // 创建一个结构体数组，大小为 n
    // 填充结构体数组
    for (int i = 0, k = 1; i < n; i++, k++)
    {
        arr[i].num = k;                               // 将原始数字 k 存入结构体成员 num
        char *str = (char *)malloc(sizeof(char) * 7); // 分配内存用于存储数字的字符串表示（最多 6 位数）

// 将整数 k 转换为字符串
        sprintf(str, "%d", k);

// 计算位数和
        int len_str = strlen(str); // 获取数字的长度
        arr[i].wei_shu_he = 0;     // 初始化位数和为 0

// 计算每一位数字的和
        for (int j = 0; j < len_str; j++)
        {
            arr[i].wei_shu_he += str[j] - '0'; // 字符转为数字并累加
        }

free(str); // 释放动态分配的内存
    }

// 使用 qsort 对结构体数组 arr 进行排序
    qsort(arr, n, sizeof(Number), cmp);

// 输出排序后第 m 个数字的原始值
    printf("%d", arr[m - 1].num);

return 0;
}
```
**结构体定义：**
Number 结构体包含两个字段：
num：保存数字的原始值。
wei_shu_he：保存数字的位数和（该数字所有数位的数字之和）。

**排序函数 cmp：**
该函数用于 qsort 排序时比较两个 Number 结构体。排序规则是：
优先排序位数和 wei_shu_he，位数和小的排在前面。
如果位数和相等，则根据数字的原始值 num 排序，数字小的排在前面。

**位数和的计算：**
对每个数字 k（从 1 到 n），先将其转换为字符串，再逐个字符减去 '0' 得到对应的整数值，将这些值累加得到 wei_shu_he。

**字符串处理：**
每次转换数字为字符串时，动态分配内存给字符串 str，使用后释放内存，避免影响下一次的转换

**排序与输出：**
使用 qsort 对 arr 数组按位数和（以及原始数字）排序，最后输出排序后的第 m 个数字的原始值。

时间复杂度：
计算位数和：每个数字的位数和需要遍历数字的每一位，时间复杂度为 O(n * d)，其中 n 是数字个数，d 是数字的最大位数（对于最大值 n = 10^6，d 大致为 6）。
排序：使用 qsort 排序，时间复杂度为 O(n log n)。
总体时间复杂度：O(n log n)，这是因为排序的时间复杂度占主导地位。
空间复杂度：
数组 arr 占用 O(n) 的空间。
字符串 str 动态分配内存，最多为 O(7)，可以认为常数空间。
总体空间复杂度：O(n)。

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

lantern

TA的其他文章

你可能喜欢

printf基础练习2 （C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

使用qsort函数和结构体数组

评论区

精彩推荐

Pascal三角（C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

校门外的树（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

Tom数（C语言代码）

简单的a+b （C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）

C二级辅导-阶乘数列（C语言代码）

上车人数（C语言代码）

lantern

TA的其他文章

你可能喜欢

printf基础练习2 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

使用qsort函数和结构体数组

评论区

精彩推荐

Pascal三角 （C语言代码）

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

校门外的树 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

Tom数 （C语言代码）

简单的a+b （C语言代码）

C语言训练-亲密数 （C语言描述,反正怎么都能对）

C二级辅导-阶乘数列 （C语言代码）

上车人数 （C语言代码）

母牛的故事（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

　　评论区

Pascal三角（C语言代码）

校门外的树（C语言代码）

Tom数（C语言代码）

C语言训练-亲密数（C语言描述,反正怎么都能对）

C二级辅导-阶乘数列（C语言代码）

上车人数（C语言代码）