3

我是编程新手，目前正在学习 C。我已经在这个问题上工作了一周，但我似乎无法弄清楚逻辑。这直接来自我正在使用的书：

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

  • “佛罗里达”
  • “俄勒冈”
  • “加利福尼亚”
  • “乔治亚州”

使用前面的字符串数组，编写您自己的函数，以使用该函数sort()按字母顺序显示每个州的名称。strcmp()

所以，假设我有：

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

我应该做嵌套的for循环strcmp(string[x], string[y])...吗？我已经破解并破解了。我只是无法理解解决这个问题所需的算法，甚至有点有效。帮助 非常感谢！！！

4

6 回答 6

6

想象一下你必须对数组进行排序——想想写在卡片上的每个状态。你会如何把它排序。有很多方法可以做到这一点。每一个都称为一个算法

一种方法是通过查看每张牌并在脑海中跟踪你见过的最低一张来找到第一个状态。查看每张卡片后，您将拥有最低的一张。把它放在一个新的堆里。现在重复 - 试图找到你剩下的最低的。

重复直到没有卡片留在原来的牌堆中

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

还有其他的

于 2013-08-23T17:44:58.723 回答
5

是的，您可以使用嵌套的 for 循环进行排序。在您了解 strcmp() 的工作原理之后，它应该相当简单：

strcmp(char *string1, char *string2)

  • 如果返回值是< 0那么它表示string1小于string2

  • 如果返回值是> 0那么它表示string2小于string1

  • 如果返回值是= 0那么它表示string1等于string2

然后，您可以从这里选择任何一种排序方法

该站点有大量正在执行的各种出色的图形示例，并包含给定算法的伪代码。

于 2013-08-23T17:43:56.790 回答
4

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

为简单起见，我可以向您展示如何实现一个简单但不高效的排序算法。是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()。

strcmp(s1, s2)如果 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 个指向字符串的数组。
这就是为什么“交换”在双换算法中可以正常工作的原因：内存地址被交换而不是整个字符串。

于 2013-08-23T20:11:01.117 回答
3

您可能应该采取的步骤：

  1. 使用状态名称填充数组
  2. 创建方法来交换数组中的两个状态
  3. 至此，您拥有使用 strcmp 实现您选择的任何排序算法所需的所有工具

大多数排序方法依赖于两件事。

  1. 能够重新排列列表（即交换）
  2. 能够比较列表中的项目以查看它们是否应该交换

我会努力让这两件事正常工作，其余的应该只是学习一种特定的排序算法

于 2013-08-23T17:36:48.350 回答
1

当心一个令人头疼的问题：字符串是按 ascii 数字表示排序的，所以如果你像这样按字母顺序排序，任何大写字母都会出现在小写字母之前，例如“alpha”、“beta”、“gamma”、“Theta”将是排序为：Theta, alpha, beta, gamma

于 2014-05-03T13:14:45.167 回答
0

对于您在此处列出的示例数组，前面提到的简单算法实际上可能是最有效的。我所指的算法是你从第一个元素开始，然后将它与其他元素进行比较，并用你找到的最小元素替换，然后去下一个元素做同样的事情，只是不要将它与已经排序的元素进行比较元素。

虽然该算法的执行时间为 O(n^2)。其中 n 是数组中元素的数量。对于较小的数组，它通常比快速排序（执行时间 O(n*log(n))）更快。原因是快速排序有更多的开销。对于较大的数组，快速排序会比其他方法更好地为您服务，如果我没记错的话，这称为替换排序，尽管我在另一个答案中看到它被称为“双倍”。

于 2013-08-23T20:33:06.173 回答