逻辑挑战:在C中按字母顺序排序数组

Question

我是编程的新手,目前正在学习C.我已经在这个问题上工作了一个星期了,我似乎无法理解逻辑.这直接来自我正在使用的书:

构建一个使用字符串数组来存储以下名称的程序:

• "佛罗里达"
• "俄勒冈"
• "Califoria"
• "格鲁吉亚"

使用前面的字符串数组,编写自己的sort()函数,使用该strcmp()函数按字母顺序显示每个状态的名称.

所以,让我说我有:

char *statesArray[4] = {"Florida", "Oregon", "California", "Georgia"}; 

我应该嵌套for循环strcmp(string[x], string[y])...吗？我已经入侵并砍掉了.我无法绕过解决这个问题所需的算法,甚至有效.帮助很多赞赏!!!

Answer 1

想象你必须对数组进行排序 - 想想写在卡片上的每个状态.你会把它按顺序排序吗？有很多方法可以做到这一点.每一个都称为算法

一种方法是通过查看每张卡片找到第一个状态,并在你看到的最低点的头部跟踪.看完每张卡后你会得到最低的一张.把它放在一堆新的.没有重复 - 试图找到你剩下的最低的.

重复,直到原始堆中没有卡片

这是一种众所周知的简单但缓慢的算法.这是我首先要做的

还有其他的

Answer 2

是的,您可以使用嵌套的for循环进行排序.在了解strcmp()如何工作之后,它应该是相当直接的:

strcmp(char*string1,char*string2)

• 如果返回值< 0则表示string1小于string2

• 如果返回值> 0则表示string2小于string1

• 如果返回值= 0则表示string1等于string2

然后,您可以从此处选择任何一种排序方法

该站点有大量正在执行的各种类型的图形示例,包括给定算法的伪代码.

Answer 3

您需要“任何”排序算法，还是“高效”排序算法？

为了简单起见，我可以向您展示如何实现一个简单但效率不高的排序算法。就是这个double for方法！！然后，按照相同的想法，您可以将其修改为任何其他有效的算法（例如 shell 或快速排序）。

对于数字，您可以按顺序排列数组，如下所示（您可能知道）：

int intcmp(int a, int b) {
    return (a < b)? -1: ((a > b)? +1: 0);
}

int main(void) {
   int a[5] = {3, 4, 22, -13, 9};

   for (int i = 0; i < 5; i++) {
      for (int j = i+1; j < 5; j++)
         if (intcmp(a[i], a[j]) > 0) {
            int temp = a[i]; 
            a[i] = a[j]; 
            a[j] = temp; 
         }
       printf("%d ", a[i]);
   }
}

现在唯一改变的是字符串而不是整数。因此，您必须考虑字符串数组：

 char *a[] = {"Florida", "Oregon", "Califoria", "Georgia"};

然后，您必须将 的类型更改temp为char*，
最后将函数替换strcmp()为intcmp()。

如果 s1 是“小于”s2 的字符串，则该函数strcmp(s1, s2)（来自 < string.h >）返回数字 < 0；如果 s1 “等于” s2，则返回 == 0；否则返回 > 1。

该程序如下所示：

#include <stdio.h>
#include <string.h>
int main(void) {
   char *a[] = {"Florida", "Oregon", "Califoria", "Georgia"};

   for (int i = 0; i < 4; i++) {
      for (int j = i+1; j < 4; j++)
         if (strcmp(a[i], a[j]) > 0) {
            char* temp = a[i]; 
            a[i] = a[j]; 
            a[j] = temp; 
         }
       printf("%s ", a[i]);
     }
   getchar();
   return 0;  
}

请注意，对于该printf()句子，我们已更改"%d "为"%s ", 以便正确显示字符串。

最后的评论：当您编写更好的算法（例如快速排序）时，更改比较函数就足够了，因为无论您要比较的数据类型如何，算法都是相同的。

备注：我使用了一种“棘手”的方法。如您所见，我已将变量定义a为指向 string 的指针。初始化程序采用字符串常量数组，然后a用它初始化变量。现在可以将该变量a安全地视为由 4 个指向字符串的指针组成的数组并对其进行索引。
这就是“交换”在 double-for 算法中工作良好的原因：交换内存地址而不是整个字符串。