C语言：如何使用字符串找到n中数字组成的最大数

Question

题目：从n (n<10 ^50) 中找出由数字组成的最大数和最小数。我试过如下，但在某些情况下，这是错误的

例如：

情况 1：输入 2015 输出 5210

情况2：输入47356359122输出（错误答案）请帮助我，我不知道为什么我得到了错误的答案！！！

#include <stdio.h>
#include <string.h>

void max(char s[]) {
    int l = strlen(s);
    int i, key, j;
    for (i = 1; i < l; i++) {
        key = s[i];
        j = i - 1;
 
        while (j >= 0 && s[j] > key) {
            s[j + 1] = s[j];
            j = j - 1;
        }
        s[j + 1] = key;
    }
    s[l - 1] = '[=10=]';
    printf("%s\n", s);
}

int main() {
    char s[100];
    fgets(s, sizeof(s), stdin);
    max(s);
}

Answer 1

您的方法是正确的：按降序对数字进行排序会从这些数字中产生最大的数字。

您的实施有缺陷：

你实际上是按升序排列的。您应该将 while (j >= 0 && s[j] > key) 更改为
```
 while (j >= 0 && s[j] < key)
```
空终止符设置在错误的位置：您清除了 s 中的最后一个字符。如果从 stdin 读取的行以换行符结尾，这可能会将其删除，除非用户键入 TAB 字符，但如果输入仅包含数字，则最后一个将被删除。将代码更改为：
```
 s[l - 1] = '[=11=]';
```

这是使用计数排序的替代方法：

#include <stdio.h>

void max_number(char s[]) {
    /* array to store the number of occurrences of each digit */
    int count[10] = { 0 }; 
    int i, d, c;
    /* enumerate all characters from the string, stop at the null terminator */
    for (i = 0; s[i]; i++) {
        /* only count digits from '0' to '9' */
        if (s[i] >= '0' && s[i] <= '9') {
            /* increase the digit count for this digit */
            count[s[i] - '0']++;
        }
    }
    /* output the digits from highest to lowest */
    for (i = 0, d = 10; d --> 0;) {
        for (c = count[d]; c --> 0;)
            s[i++] = '0' + d;
    }
    if (i == 0) {
       /* there were no digits in the string: store a 0 */
       s[i++] = '0';
    }
    if (s[0] == '0') {
       /* there were only zeroes in the string: keep a single 0 */
       i = 1;
    }
    /* set the null terminator */
    s[i] = '[=12=]';
    printf("%s\n", s);
}

int main() {
    char s[100];
    if (fgets(s, sizeof(s), stdin))
        max_number(s);
    return 0;
}

Answer 2

用户 chqrlie 已经提供了一个很好的一般性答案。这是一个更简单、效率稍低的方法。

观察到没有必要将结果实际存储在一个新字符串中，您还可以在找到数字时打印数字（从高到低）。该程序循环输入字符串 10 次，首先打印所有 9，然后打印所有 8，等等

#include <stdio.h>

void max(char *str) {
    for (char digit = '9'; digit >= '0'; --digit) // Assume ASCII
        for (char *strCp = str; *strCp != '[=10=]' ; ++strCp)
            if (*strCp == digit)
                putchar(digit);
    putchar('\n');
}

int main(void) {
    char s[100];
    if (fgets(s, sizeof(s), stdin) != NULL)
        max(s);
}

注：

未使用strlen函数，因此不再需要string.hheader。
将 main 签名更改为 int main(void)，这是标准建议的，以防不使用参数。
正在检查fgets的return值，所以程序可以处理空输入和输入失败。

Answer 3

对于初学者来说，该函数不应输出任何消息。是否输出消息由函数的调用者决定。

该函数应该return一个修改后的字符串，其中的字符按数字降序排列。

当向函数传递空字符串时，您的函数可以调用未定义的行为

void max(char s[]) {
    int l = strlen(s);
    int i, key, j;
    //...
    s[l - 1] = '[=10=]';
    printf("%s\n", s);
}

因为在这个语句中

s[l - 1] = '[=11=]';

试图访问传递的字符串以外的内存。一般来说，该陈述是错误的，因为终止零必须出现在 l .

位置

不需要设置终止零字符'[=16=]'，因为它已经存在于字符串中。所以上面的说法是多余的。

事实上，由于此 if 语句中的条件，您正在尝试使用插入排序方法按升序对字符串的字符进行排序。

while (j >= 0 && s[j] > key) {

在这种情况下，调用函数 fgets 后出现在字符串中的换行符 '\n' 将移到字符串的开头。

您必须按降序对字符串进行排序。

并且在调用该函数之前应从字符串中删除换行符'\n'。

可以通过以下方式声明和定义函数，如下面的演示程序所示。

#include <stdio.h>
#include <string.h>

char * max_number( char *s )
{
    if ( *s )
    {
        for ( char *p = s + 1; *p; ++p )
        {
            char c = *p;
            char *q = p;
            
            for ( ; q != s && *( q - 1 ) < c; --q )
            {
                *q = *( q - 1 );
            }
            
            if ( q != p ) *q = c;
        }
    }

    return s;
}

int main(void) 
{
    char s[100];
    
    fgets( s, sizeof( s ), stdin );
    
    s[ strcspn( s, "\n" ) ] = '[=13=]';
    
    puts( max_number( s ) );
    
    return 0;
}

如果使用 fgets 输入数字 47356359122 那么程序输出将是

97655433221

C语言：如何使用字符串找到n中数字组成的最大数

C language: How to find the largest number created by digits from n using string

c

string

max

insertion-sort

function-definition