mergesort 的合并函数删除最大的按字母顺序排列的条目结构

Question

合并排序函数正确排序直到最后一次迭代，其中最大的字母值从完成的数组中完全删除。我是 C 的新手，并且正在努力解决这个问题，因为合并排序 完美地 与 ENTRY 结构的 OCCURRENCES 属性一起工作，但在使用 strcmp 时不与 char 数组 WORDS 一起工作。它应该工作方式相同，这里是结构以及合并和排序函数的代码：

这是我的输出示例：文件包含 "Hello world how how are you doing"

| hello                | 1          |
| world                | 1          |
| how                  | 2          |
| are                  | 1          |
| you                  | 1          |
| doing                | 1          |
+-----------------------------------+

+_____________________________+
| Word          | Occurrences |
+-----------------------------+
| how          | 2            |
| doing        | 1            |
| you          | 1            |
| are          | 1            |
| world        | 1            |
| hello        | 1            |
+-----------------------------+

+___________________________________+
| Word           | Occurrences      |
+-----------------------------------+
| are                  | 1          |
| doing                | 1          |
| hello                | 1          |
| how                  | 2          |
| world                | 1          |
+-----------------------------------+
zoe@zoe-VirtualBox:~/Analysis$ ^C

Answer 1

您的 merge 函数中似乎有 copy/paste 错误。而不是：

while(l <= high) b[i++] = a[l++];

你想要：

while(m <= high) b[i++] = a[m++];

在此之后您的排序代码可以正常工作。

这是一些测试代码。我称它为：

./sortTest hello world hello rabbit dog fox hen worm world 01234567890123456789012345678901234567890123456789 01234567890123456789012345678901234567890123456789 ant

输出返回为：

Results ... 
01234567890123456789012345678901234567890123 2
ant 1
dog 1
fox 1
hello 2
hen 1
rabbit 1
world 2
worm 1

这里是测试代码：

ENTRY *find_dup(ENTRY* entries, const char *str, int N)
{
    ENTRY *dup = NULL;
    int i;
    for(i=0; i < N; ++i)
    {
        if (strncmp(entries[i].WORD, str, sizeof(entries[i].WORD)-1) == 0)
        {
            dup = entries + i;
            break;
        }
    }
    return dup;
}

void print_entries(const ENTRY* entries, int N)
{
    int i;
    for(i=0; i < N; ++i)
    {
        fprintf(stdout, "%s %d\n", entries[i].WORD, entries[i].OCCURRENCES);
    }
}

int main(int argc, const char **argv)
{
    int i, N=0;
    ENTRY *entries = malloc((argc-1)*sizeof(*entries));
    ENTRY *scratch = malloc((argc-1)*sizeof(*entries));
    for(i=1; i < argc; ++i)
    {
        ENTRY *dup = find_dup(entries, argv[i], N);
        if (dup == NULL)
        {
            strncpy(entries[N].WORD, argv[i], sizeof(entries[N].WORD));
            entries[N].WORD[sizeof(entries[N].WORD)-1] = 0;
            entries[N].OCCURRENCES = 1;
            ++N;
        }
        else
        {
            ++dup->OCCURRENCES;
        }
    }

    sort(entries, scratch, 0, N-1, 0);

    fprintf(stdout, "Results ... \n");
    print_entries(entries, N);    

    free(entries);
    free(scratch);

    return 0;
}

mergesort 的合并函数删除最大的按字母顺序排列的条目结构

Merge function of mergesort removing the largest alphabetically valued entry struct

c

memory

arrays

sorting

allocation