c - 在C中对多维数组进行排序

Question

我有一个代码，可以创建给定字符串的后缀的多维数组:

#include <stdio.h>

int main() {
   char seq[] = {"HELLO"};
   char suff[40][40];

   //Getting the suffixes
   for(int x = 0; seq[x] != '\0'; x++){
      for(int y = x; seq[y] != '\0'; y++){
         suff[x][y] = seq[y];
         printf("%c", suff[x][y]);
      }
      printf("\n");
   }

   return 0;
}

给定字符串HELLO的后缀是:
0 你好
1 埃洛
2 洛洛
3LO
4欧


如何使用冒泡排序按升序对元素进行排序，例如:
1 埃洛
0 你好
3LO
2 洛洛
4欧


并将其排序索引存储到另一个数组中？ 索引[] = {1,0,3,2,4}

Answer 1

index 数组意味着您可以对数据进行排序，而无需移动任何字符串。此代码与 code 密切相关通过 David C. Rankin ，但会生成请求的输出，除了在 LO 之前对 LLO 进行排序(我在 comment 中注意到的问题)。我重新打包了代码，创建了一个排序函数、一个调用排序函数的打印函数以及一个针对不同字符串调用打印和排序函数的主函数。

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

static void sort_substrings(size_t length, const char seq[length], size_t index[length])
{
    const char *suff[length];

    for (size_t i = 0; seq[i] != '\0'; i++)
    {
        suff[i] = &seq[i];
        index[i] = i;
    }

    for (size_t j = 0; j < length; j++)     /* bubblesort pointers */
    {
        for (size_t i = 0; i < length - 1 - j; i++)
        {
            if (strcmp(suff[index[i]], suff[index[i + 1]]) > 0)
            {
                int tmp = index[i];
                index[i] = index[i+1];
                index[i+1] = tmp;
            }
        }
    }
}

static void test_sort_substrings(const char *str)
{
    size_t length = strlen(str);
    size_t index[length];

    sort_substrings(length, str, index);

    int width = (length > 9) ? 2 : 1;

    printf("\nString: [%s]\n", str);
    printf("Sorted data:\n");
    for (size_t i = 0; i < length; i++)
        printf("%*zu [%s]\n", width, index[i], &str[index[i]]);
    putchar('\n');

    printf("Unsorted data:\n");
    for (size_t i = 0; i < length; i++)
        printf("%*zu [%s]\n", width, i, &str[i]);
    putchar('\n');
}

int main(void)
{
    test_sort_substrings("HELLO");
    test_sort_substrings("SALAMANDER");
    test_sort_substrings("ABLE WAS I ERE I SAW ELBA");
    return 0;
}

输出:

String: [HELLO]
Sorted data:
1 [ELLO]
0 [HELLO]
2 [LLO]
3 [LO]
4 [O]

Unsorted data:
0 [HELLO]
1 [ELLO]
2 [LLO]
3 [LO]
4 [O]


String: [SALAMANDER]
Sorted data:
 1 [ALAMANDER]
 3 [AMANDER]
 5 [ANDER]
 7 [DER]
 8 [ER]
 2 [LAMANDER]
 4 [MANDER]
 6 [NDER]
 9 [R]
 0 [SALAMANDER]

Unsorted data:
 0 [SALAMANDER]
 1 [ALAMANDER]
 2 [LAMANDER]
 3 [AMANDER]
 4 [MANDER]
 5 [ANDER]
 6 [NDER]
 7 [DER]
 8 [ER]
 9 [R]


String: [ABLE WAS I ERE I SAW ELBA]
Sorted data:
20 [ ELBA]
10 [ ERE I SAW ELBA]
 8 [ I ERE I SAW ELBA]
14 [ I SAW ELBA]
16 [ SAW ELBA]
 4 [ WAS I ERE I SAW ELBA]
24 [A]
 0 [ABLE WAS I ERE I SAW ELBA]
 6 [AS I ERE I SAW ELBA]
18 [AW ELBA]
23 [BA]
 1 [BLE WAS I ERE I SAW ELBA]
13 [E I SAW ELBA]
 3 [E WAS I ERE I SAW ELBA]
21 [ELBA]
11 [ERE I SAW ELBA]
 9 [I ERE I SAW ELBA]
15 [I SAW ELBA]
22 [LBA]
 2 [LE WAS I ERE I SAW ELBA]
12 [RE I SAW ELBA]
 7 [S I ERE I SAW ELBA]
17 [SAW ELBA]
19 [W ELBA]
 5 [WAS I ERE I SAW ELBA]

Unsorted data:
 0 [ABLE WAS I ERE I SAW ELBA]
 1 [BLE WAS I ERE I SAW ELBA]
 2 [LE WAS I ERE I SAW ELBA]
 3 [E WAS I ERE I SAW ELBA]
 4 [ WAS I ERE I SAW ELBA]
 5 [WAS I ERE I SAW ELBA]
 6 [AS I ERE I SAW ELBA]
 7 [S I ERE I SAW ELBA]
 8 [ I ERE I SAW ELBA]
 9 [I ERE I SAW ELBA]
10 [ ERE I SAW ELBA]
11 [ERE I SAW ELBA]
12 [RE I SAW ELBA]
13 [E I SAW ELBA]
14 [ I SAW ELBA]
15 [I SAW ELBA]
16 [ SAW ELBA]
17 [SAW ELBA]
18 [AW ELBA]
19 [W ELBA]
20 [ ELBA]
21 [ELBA]
22 [LBA]
23 [BA]
24 [A]

使用标准C不容易qsort()函数来完成此任务，因为您确实需要排序函数中的一些辅助数据。 BSD 和 Linux 都提供了一个带有额外参数的函数 qsort_r()。遗憾的是，这两个函数的接口(interface)不同且不兼容。

此代码使用 qsort_r() 的 BSD 实现 - 使其在 Linux 上工作所需的更改很简单:

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

/*
** BSD variant of qsort_r():
**      void qsort_r(void *base, size_t nel, size_t width, void *thunk,
**                   int (*compar)(void *, const void *, const void *));
** Linux variant of qsort_r():
**      void qsort_r(void *base, size_t nel, size_t width,
**                   int (*compar)(const void *, const void *, void *),
**                   void *thunk);
** The code implemented uses the BSD variant.
*/

static int str_comparator(void *thunk, const void *v1, const void *v2)
{
    char **suff = thunk;
    int i1 = *(const int *)v1;
    int i2 = *(const int *)v2;
    return strcmp(suff[i1], suff[i2]);
}

static void sort_substrings(size_t length, const char seq[length], size_t index[length])
{
    const char *suff[length];

    for (size_t i = 0; seq[i] != '\0'; i++)
    {
        suff[i] = &seq[i];
        index[i] = i;
    }
    qsort_r(index, length, sizeof(index[0]), suff, str_comparator);
}

static void test_sort_substrings(const char *str)
{
    size_t length = strlen(str);
    size_t index[length];

    sort_substrings(length, str, index);

    int width = (length > 9) ? 2 : 1;

    printf("\nString: [%s]\n", str);
    printf("Sorted data:\n");
    for (size_t i = 0; i < length; i++)
        printf("%*zu [%s]\n", width, index[i], &str[index[i]]);
    putchar('\n');

    printf("Unsorted data:\n");
    for (size_t i = 0; i < length; i++)
        printf("%*zu [%s]\n", width, i, &str[i]);
    putchar('\n');
}

int main(void)
{
    test_sort_substrings("HELLO");
    test_sort_substrings("SALAMANDER");
    test_sort_substrings("ABLE WAS I ERE I SAW ELBA");
    return 0;
}

它产生与以前相同的输出。