c - 使用 struct 作为 "database"的任意数量单词(按字母顺序)的排序算法

Question

所以我应该把排序算法作为计算机科学作业。

它应该读取任意数量的以“\n”结尾的单词。读取“.”后，它应该按字母顺序打印单词。

例如:输入:苹果狗奥地利苹果

输出:苹果苹果奥地利狗

我想将单词存储到一个结构中。我认为为了适用于任意数量的单词，我应该创建结构数组。

到目前为止，我已经尝试创建一个仅包含一个成员(字符串)的 typedef 结构，并计划从中创建一个结构数组，然后将每个单词存储到其中。

至于字数的“随机性”，我想在查出写入了多少个字之后，在 main 中设置结构体类型，然后将每个字存储到结构体数组的每个元素中。

我的问题是:1.我不知道如何查出字数。我唯一尝试过的就是创建一个函数来计算 '\n' 出现的次数，尽管它效果不是很好。

至于数据结构，我想出了只有一个字符串成员的结构:

typedef struct{
char string[MAX];
}sort;

然后在主函数中我首先读取了一些单词(不是实际的赋值，只是为了使代码工作)

在有了“len”之后，我声明了 sort 类型的变量:

int main(){
/*code, scanf("%d", &len) and stuff*/
sort sort_t[len];

for(i = 0; i < len; i++){
    scanf("%s", sort_t[i].string);
}

问题:这样的事情“合法”吗？我是否使用了好的方法？

问题2:在开始存储它们之前，如何知道要存储的单词数(对于结构数组)？

Answer 1

恕我直言，为每个字符串保留相同的最大存储空间的想法有点浪费。您最好坚持使用以 NUL 结尾的动态字符串，就像 C 代码中通常所做的那样。这是 C 库最支持的。

至于管理未知数量的字符串，您可以选择。可能性 1 是使用 Xavier 提到的链表。可能是最优雅的解决方案，但调试起来可能很耗时，最终您必须将其转换为数组才能使用一种常见的排序算法。

可能性 2 是使用类似于 C++ std::vector 对象的东西。假设分配存储的任务被委托(delegate)给某个“包”对象。处理“bag”的代码垄断了调用 Vlad 提到的 realloc() 函数。您的主函数仅调用 bag_create() 和 bag_put(bag, string)。这不太优雅，但可能更容易实现。

由于您的重点是排序算法，因此我宁愿建议使用方法 #2。您可以使用下面的代码片段作为起点。

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

typedef struct {
    size_t    capacity;
    size_t    usedSlotCount;
    char**    storage;
} StringBag;


StringBag* bag_create()
{
    size_t initialSize = 4;  /* start small */
    StringBag*   myBag = malloc(sizeof(StringBag));

    myBag->capacity      = initialSize;
    myBag->usedSlotCount = 0;
    myBag->storage       = (char**)malloc(initialSize*sizeof(char*));

    return myBag;
}

void bag_put(StringBag* myBag, char* str)
{
    if (myBag->capacity == myBag->usedSlotCount) {
        /* have to grow storage */
        size_t  oldCapacity = myBag->capacity;
        size_t  newCapacity = 2 * oldCapacity;
        myBag->storage = realloc(myBag->storage, newCapacity*sizeof(char*));
        if (NULL == myBag->storage) {
            fprintf(stderr, "Out of memory while reallocating\n");
            exit(1);
        }
        fprintf(stderr, "Growing capacity to %lu\n", (unsigned long)newCapacity);
        myBag->capacity = newCapacity;
    }

    /* save string to new allocated memory, as this */
    /* allows the caller to always use the same static storage to house str  */

    char* str2 = malloc(1+strlen(str));
    strcpy(str2, str);
    myBag->storage[myBag->usedSlotCount] = str2;
    myBag->usedSlotCount++;
}


static char inputLine[4096];


int main()
{
    StringBag*  myBag = bag_create();

    /* read input data  */
    while(scanf("%s", inputLine) != EOF) {
        if (0 == strcmp(".", inputLine))
            break;
        bag_put(myBag, inputLine);
    }

    /* TODO: sort myBag->storage and print the sorted array */

}