无法按字母顺序对结构体数组进行排序

Question

我正在尝试对一个结构体数组中的字符串进行字母顺序排序，然后打印出来，但我的代码不起作用。

我已经花了几个小时来想弄清楚原因，但是一直无法弄清楚。我相信它可能是非常明显的问题，但我只学习了几周编程，所以我无法解决它。

它确实可以编译而没有错误，输出只是原始未排序数组的打印，但没有aardvark，如下所示：boy acumen addle cat affix agar ahoy aigrette ajar 以下是我目前的代码：

#include <stdio.h>

struct entry
{
    char    word[15];
    char    definition[50];
};
struct entry dictionary[100] = 
  { {"boy",         "a boy          "                   },
    {"aardvark",    "a burrowing African mammal"        },
    {"acumen",      "mentally sharp; keen"              },
    {"addle",       "to become confused"                },
    {"cat",         "a cat"                             },
    {"affix",       "to append; attach"                 },
    {"agar",        "a jelly made from seaweed"         },
    {"ahoy",        "a nautical call of greeting"       },
    {"aigrette",    "an ornamental cluster of feathers" },
    {"ajar",        "partially opened"                  } 
  };



int main(void)
{
    int i;
    void dictionarySort(struct entry dictionary[]);

    dictionarySort(dictionary);

    for(i = 0; i < 10; ++i)
    {
        printf("%s\n", dictionary[i].word);
    }

    return 0;
}

void dictionarySort(struct entry dictionary[])
{
    int i, k, j;
    struct entry temp[100];

    for(i = 0; i <=  9; ++i)
    {
        for( k = 0; dictionary[i].word[k] != '\0'; ++k)
        {
            if( (dictionary[i].word[k] > dictionary[i+1].word[k] ) )
            {
                temp[i] = dictionary[i];
                dictionary[i] = dictionary[i+1];
                dictionary[i+1] = temp[i];
            }

        }

    }
}

如果有任何建议，请不吝赐教。

- jager96

---

它能编译吗？如果可以，运行时会发生什么？如果不能，编译时会出现什么错误？ - Politank-Z

它编译没有错误，输出只是原始未排序数组的打印，但没有单词aardvark，像这样： boy acumen addle cat affix agar ahoy aigrette ajar - jager96

问题1：您还没有展示给我们struct entry是如何定义的，但如果这是C语言且word是一个char *，那么你的比较if(dictionary[i].word[k] > dictionary[i+1].word[k])将无法正常工作。您需要调用strcmp函数进行字符串比较。 - Steve Summit

i <= 9 --> i < 9 - BLUEPIXY

此外，如果您只想获得排序后的输出（而不是学习如何实现排序算法），通常更容易调用库函数 qsort。如果您需要，我们可以向您展示如何做到这一点。 - Steve Summit

Answer 1

首先，您正在尝试构建的算法不是排序算法。在修复以下问题后，您所拥有的是冒泡排序的一个迭代。为了使其实际对数组进行排序，您需要调用dictionarySort 10次。有关更多详细信息，请参见https://en.wikipedia.org/wiki/Bubble_sort。

现在来看代码中的其他问题。您可以通过只使用strcmp来简化整个循环：

for(i = 0; i <=  9; ++i)
{
    if( strcmp(dictionary[i].word, dictionary[i+1].word ) > 0 )
    {
        temp[i] = dictionary[i];
        dictionary[i] = dictionary[i+1];
        dictionary[i+1] = temp[i];
    }
}

但是，如果您正在进行某种练习，并想找出如何按照自己的方式进行操作，那么您的逻辑存在两个问题：

1. 考虑单词“azc”和“brc”。它们按字母顺序排列，因此不需要交换它们。在查看它们的第一个字符后，分别为a和b，您应该停止比较它们。相反，您应该继续到下一个字母，即z和r，并根据它们决定是否交换，这会导致错误的顺序。

2. 在交换两个单词后，您还应该停止。考虑za和rb的情况。在查看第一个字母z和r之后，您将交换这两个单词（这很好）。但是接下来您将查看第二个字母。这时候这两个单词已经被交换了，所以您将再次查看b和a，并再次交换它们。因此完整的解决方案应该是：

for(i = 0; i <=  9; ++i)
{
    for( k = 0; dictionary[i].word[k] != '\0'; ++k)
    {
        if( (dictionary[i].word[k] > dictionary[i+1].word[k] ) )
        {
            temp[i] = dictionary[i];
            dictionary[i] = dictionary[i+1];
            dictionary[i+1] = temp[i];
            break; // <<-- this is new
        }
        else if( (dictionary[i].word[k] < dictionary[i+1].word[k] ) )
        {
            break; // <<-- this is new
        }
    }
}

- Ishamael

---

是的，我正在做一本书上的练习，但它还没有涉及到strcmp。你的答案改善了结果，但由于某种原因，boy的条目仍然卡在addle和affix之间，但cat的条目已经移动到了正确的位置。 - jager96

如果您仍然只调用算法的一个迭代，那么这是可以预料的。您算法的一个迭代只会将一个最大的元素“冒泡”到顶部。发生的情况是boy被“冒泡”到了cat所在的位置，然后cat被冒泡到了顶部。正如我在答案开头建议的那样，您需要运行您的排序10次才能真正对数组进行排序。 - Ishamael

是的，抱歉。我错过了你评论的第一部分，你说只有一个迭代。谢谢回答！ - jager96

Answer 2

使用strcmp()函数来比较字符串。

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

struct Entry {
    char    word[15];
    char    definition[50];
};

struct Entry dictionary[100] =  {
    {"boy",         "a boy          "                   },
    {"aardvark",    "a burrowing African mammal"        },
    {"acumen",      "mentally sharp; keen"              },
    {"addle",       "to become confused"                },
    {"cat",         "a cat"                             },
    {"affix",       "to append; attach"                 },
    {"agar",        "a jelly made from seaweed"         },
    {"ahoy",        "a nautical call of greeting"       },
    {"aigrette",    "an ornamental cluster of feathers" },
    {"ajar",        "partially opened"                  }
};



int main(void) {
    int i;
    void dictionarySort(struct Entry dictionary[]);
    dictionarySort(dictionary);
    for(i = 0; i < 10; ++i) {
        printf("%s\n", dictionary[i].word);
    }
    return 0;
}

void dictionarySort(struct Entry dictionary[]) {
    int i, j;
    char temp[100];
    for(i = 0; i <=  9; ++i) {
        for(j = i + 1; j <= 9; j++) {
            if(strcmp(dictionary[i].word, dictionary[j].word) > 0) {
                strcpy(temp, dictionary[i].word);
                strcpy(dictionary[i].word, dictionary[j].word);
                strcpy(dictionary[j].word, temp);
            }
        }
    }
}

- Jimmy

---

word和definition必须在一起。 - BLUEPIXY