3

我有一个程序使用（并且必须继续使用）实现 qsort 的旧排序功能。我还必须为排序函数提供适当的数据，以按升序（如果字符串包含偶数）或降序（如果字符串包含奇数）对数据进行排序。

必须更改数据才能实现这一点，不能更改排序功能。

代码是用C编写的，但我没有针对这个特定问题的相关代码片段。

真正的问题是：

如何转换数据以使输出与下面的所需输出匹配？

我有以下数据（或类似数据）

String 1
String 2
String 3
String 4
String 5
String 6

编辑：数据是多个字符串类型 char **，每个字符串中的数字是一个 int。

所需的输出是

String 5
String 3
String 1
String 2
String 4
String 6

排序通常以与输入 1:1 匹配的降序方式进行。我设法通过在字符串后面的数字前加上 1 或 0 来生成呈现以下输出的转换。

所以要排序的内部数据是这样的

String 01
String 12
String 03
String 14
String 05
String 16

这会产生以下输出（转换仅用于排序，并且是临时的）。

String 1
String 3
String 5
String 2
String 4
String 6
4

4 回答 4

3

您应该有一个包含数据和值的结构：

Struct DataValue
{
   string data;
   int value;
}

然后按值排序并输出数据，如果您想做{"01", 1} 通常的排序，排序并不难：首先按值排序以使列表像您显示的那样。（对于值）现在创建一个空的数据值数组（具有基本数组大小），从最后一项开始并将其填充如下：

    int j = 0;
    for (int i = a.Count - 1; i >= 0; i -= 2) // fill bottom of list
    {
        b[a.Count - 1 - j] = a[i];
        j++;
    }

    j = 0;
    for (int i = a.Count - 2; i >= 0; i -= 2)  // fill root of list
    {
        b[j] = a[i];
        j++;
    }

最后输出值。

我用c#写的它在c中没有太大的不同。你会得到：

  List<int> a = new List<int>{1,2,3,4,5,6,7};

   b==> 6,4,2,1,3,5,7

and for:
  List<int> a = new List<int>{1,2,3,4,5,6};
  b==> 5,3,1,2,4,6
于 2010-12-27T15:45:07.110 回答
2

这可以使用自定义比较例程就地完成（即，使用单个值数组并且不需要单独的列表）。下面的函数假设您直接对字符串进行排序。预处理数据可能会更好，以便从字符串中提取数字并将两者放入结构中。但这会给你这个想法。

您可以将指向此比较函数的指针传递给qsort.

int Comparer(void * v1, void * v2)
{
    char *s1 = (char *)v1;
    char *s2 = (char *)v2;

    // Here, extract the numbers from the ends of the strings.
    int n1 = // extract number
    int n2 = // extract number

    // First comparison sorts odd numbers above even numbers
    if ((n1 % 2) == 1)
    {
        // first number is odd
        if ((n2 % 2) == 1)
        {
            // second number is odd, so sort the numbers ascending
            return (n1 - n2);
        }
        else
        {
            // second number is even, which is "greater than" any odd number
            return -1;
        }
    }
    else
    {
        // first number is even
        if ((n2 % 2) == 0)
        {
            // second number is even, so sort the numbers descending
            return (n2 - n1);
        }
        else
        {
            // second number is odd, which is "less than" any even number
            return 1;
        }
    }
}
于 2010-12-27T17:58:01.923 回答
1

9-i如果i是奇数，请在前面添加。否则添加 9。

于 2010-12-27T15:43:08.800 回答
1
  1. 预处理：将偶数字符串放入一个列表中（我们称这个列表为_evens_），将奇数字符串放入一个单独的列表中（称为_odds_）
  2. 对两个列表进行排序
  3. 创建目的地列表
  4. 将 _odds_ 列表视为堆栈：弹出 _odds_ 的顶部并将弹出的元素放在目标列表的 *front* 上。
  5. 将 _evens_ 视为一个队列：弹出 _evens_ 的顶部并将弹出的元素放在目标列表的 *end* 处。
于 2010-12-27T16:11:40.480 回答