c - C:如何按频率编号和字母顺序从可变数量的文件中对单词进行排序

Question

我是C语言的新手，我无法编写一个C程序，该程序通过命令行参数获取可变数量的文件，并按(ASCII)字母顺序对单词进行排序，仅显示唯一的单词，但包含频率。我设法通过用户输入按字母顺序对单词进行了排序，但是我不知道如何正确编写代码以接受文件输入，而且我也不知道如何只用频率将每个唯一单词打印一次。

这是到目前为止我得到的，它使用标准输入而不是文件，并且缺少频率计数:

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

int main(void) {
char a[2048][2048];
int i = 0, 
    j = 0, 
    k = 0, 
    n;

while(i < 2048 && fgets(a[i], 2048, stdin) != NULL)
{
    n = strlen(a[i]);
    if(n > 0 && a[i][n-1] == '\n')
    a[i][n -1] = '\0';
    i++;
}

for(j = 0; j < i; j++)
{
    char max[2048];
    strcpy (max,a[j]);
    for(k = j + 1; k < i; k++)
    {
        if(strcmp(a[k], max) < 0)
        {
            char temp[2048];
            strcpy(temp, a[k]);
            strcpy(a[k], max);
            strcpy(max, temp);
        }
    }
    strcpy(a[j],max);
}

for( j = 0; j < i; j++){
    printf("%s\n", a[j]);
}
return 0;
}

Answer 1

为了将文件中的单词读入仅包含唯一单词的数组，同时跟踪每次看到单词出现的次数，可以通过两种方法来完成。一种简单而直接的方法是保留2个单独的数组。第一个是2D字符数组，其大小足以容纳预期的单词数，第二个是数字数组(unsigned int或size_t)，该数组包含每个单词在与存储该单词相同的索引处看到的次数字符数组。

从文件中读取单词时，唯一的挑战是确定一个单词之前是否曾被看到过，如果没有，则将新单词以给定的seen添加到index字符数组中，然后在该索引处更新频率数组freq以反映这个词已经被看到1时间(例如freq[index]++;)。
如果在检查seen中的单词列表时，发现当前单词已经出现在索引X中，那么您跳过将单词添加到seen中，而只是更新freq[X]++;。

下面是一个简短的示例。尝试一下，如果您有任何疑问，请告诉我:

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

#define MAXW 100
#define MAXC 32

int main (int argc, char **argv) {

    /* initialize variables & open file or stdin for reading */
    char seen[MAXW][MAXC] = {{ 0 }};
    char word[MAXC] = {0};
    size_t freq[MAXW] = {0};
    size_t i, idx = 0;
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;
    if (!fp) {
        fprintf (stderr, "error: file open failed '%s'.\n", argv[1]);
        return 1;
    }

    /* seen 1st word into 'seen' array, update index 'idx' */
    if (fscanf (fp, " %32[^ ,.\t\n]%*c", word) == 1) {
        strcpy (seen[idx], word);
        freq[idx]++;
        idx++;
    }
    else {
        fprintf (stderr, "error: file read error.\n");
        return 1;
    }

    /* read each word in file */
    while (fscanf (fp, " %32[^ ,.\t\n]%*c", word) == 1) {
        /* check against all words in seen */
        for (i = 0; i < idx; i++) {
            /* if word already in 'seen', update 'freq' count */
            if (strcmp (seen[i], word) == 0) {
                freq[i]++;
                goto skipdup;   /* skip adding word to 'seen' */
            }
        } /* add word to 'seen', update freq & 'idx' */
        strcpy (seen[idx], word);
        freq[idx]++;
        idx++;

    skipdup:

        if (idx == MAXW) { /* check 'idx' against MAXW */
            fprintf (stderr, "warning: MAXW words exceeded.\n");
            break;
        }
    }
    if (fp != stdin) fclose (fp);

    printf ("\nthe occurrence of words are:\n\n");
    for (i = 0; i < idx; i++)
        printf ("  %-28s : %zu\n", seen[i], freq[i]);

    return 0;
}

编译

gcc -Wall -Wextra -O3 -o bin/file_words_occur file_words_occur.c

输入

$ cat dat/words.txt
the quick brown fox jumps over the lazy dog. the fox jumps over the dog to avoid the squirrel.

输出

$ ./bin/file_words_occur <dat/words.txt

the occurrence of words are:

  the                          : 8
  quick                        : 1
  brown                        : 1
  fox                          : 2
  jumps                        : 2
  over                         : 2
  lazy                         : 1
  dog                          : 2
  to                           : 1
  avoid                        : 1
  squirrel                     : 2
  was                          : 1
  in                           : 1
  path                         : 1
  of                           : 1
  captain                      : 1
  jack                         : 1
  sparrow                      : 1
  a                            : 1
  pirate                       : 1
  so                           : 1
  brave                        : 1
  on                           : 1
  seven                        : 1
  seas                         : 1

注意:在被删节的词典中最长的单词是 28 chars long(反分裂主义)。它需要为nol终止字符提供空间，以用于总共 29字符。选择 MAXC的 32应该可以容纳所有普通单词。

处理多个文件+按字母顺序对单词/出现进行排序

如评论中所述，只需使用从 stdin读取的代码功能，就可以使用现有代码来处理多个文件。您需要做的只是 cat file1 file2 file3 | ./prog_name。更新代码以将多个文件作为参数来处理也不难。 (您可以只用 for (j = 1, j < argc, j++)包装现有主体，然后打开/关闭提供的每个文件名。(还需要对 fp声明进行其他一些细微调整)

但是那有什么乐趣呢？每当您考虑在程序中多次执行相同的操作时，“我应该创建一个函数”灯泡就会闪烁。这是考虑在代码中处理重复过程的正确方法。 (可以说，由于只有一件事情我们要做的不止一次，并且因为我们可以将其简单地包装在 for循环中，所以在这种情况下我们可以不用任何功能了，但是学习的地方在哪里？)

好的，所以我们知道将文件读取/频率计数代码移至某个函数，但是排序要求又如何呢？那是我们需要将数据处理从2数组更改为struct数组的地方。为什么要从2数组转到处理结构中的数据？

当按字母顺序对单词进行排序时，必须保持 seen数组和 freq数组之间的关系，因此在排序之后，使用正确的单词出现的次数正确。您不能独立地对数组进行排序并保持这种关系。但是，如果我们将单词和该单词的出现位置都放入一个结构中，则可以按该单词对结构数组进行排序，并且正确的出现次数仍与正确的单词相关联。例如像下面这样的东西会起作用:

typedef struct {
    char seen[MAXC];
    size_t freq;
} wfstruct;

( wfstruct只是单词频率结构的半描述性名称，可以是任何对您有意义的名称)

您将在程序中将哪个声明为具有以下内容的数组:

    wfstruct words[MAXW];

(您实际上会希望将每个成员初始化为零-在下面的实际代码中完成)

如何排序一个数组？ qsort是你的朋友。 qsort将对所有内容进行排序，只要您可以传递 qsort(1)数组，(2)排序多少个元素，(3)元素的大小，以及(4)使用 const void指针的比较函数它将比较的元素。这总是给新的C程序员一个合适的选择，因为您必须弄清楚(a)如何将指针数组作为指针传递，以及(b)如何处理从指针中获取所需数据在功能上进行比较。
qsort的比较函数的声明为:

int compare (const void *a, const void *b);

要编写比较功能，您需要问自己:“我需要比较什么才能以我想要的方式对集合进行排序？”在这种情况下，您知道要按 seen数组的每个元素中的单词 wfstruct对结构数组进行排序。您知道 seen将是一个简单的字符串，因此您可以使用 strcmp进行排序。

然后，您需要问自己的最后一件事是:“该如何从 seen(和 const void *a)中提取 *b字符串，以便可以将其提供给 strcmp？”在这里，您知道 const void *a必须代表要排序的基本元素 struct wfstruct。因此，您知道 const void *a是 wfstruct的指针。由于它将是一个指针，因此您必须使用 ->运算符来取消引用该结构的 seen成员。 (例如 seen成员的访问权限为 mystruct->seen。

但是“关于取消引用空指针的规则是什么？” (答案:“您不能取消引用空指针”)如何处理？很简单，您只需在 struct wfstruct函数中声明 compare类型的指针，并将 a的大小写类型为 (wfstruct *)。例:

    wfstruct *ap = (wfstruct *)a;

现在您有了一个好听的 pointer to struct wfstruct(或者简单地说是 pointer to wfstruct，因为我们在其声明中包括了 typedef的 wfstruct)。您对 b执行相同的操作，现在可以将 ap->seen和 bp->seen传递给 strcmp并对结构数组进行排序:

int compare (const void *a, const void *b)
{
    wfstruct *ap = (wfstruct *)a;
    wfstruct *bp = (wfstruct *)b;
    return (strcmp (ap->seen, bp->seen));
}

在程序中对 qsort的调用无非是:

    /* sort words alphabetically */
    qsort (words, idx, sizeof *words, compare);

有了基础知识，您现在可以将所需的代码移至一个函数，以允许您读取多个文件作为参数，保留文件之间出现的单词总数(以及它们的出现频率)，然后对结果结构按字母顺序排列。

注意:可以跟踪多个文件(调用函数)之间的单词总数，您可以返回每个文件收集的单词数量作为读取函数的返回值，并以这种方式总计，或者您可以简单地将指向总数的指针传递给read函数，并直接在函数中进行更新。我们将在下面采用第二种方法。

将各个部分放在一起，您将获得:

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

#define MAXW 100
#define MAXC 32

typedef struct {
    char seen[MAXC];
    size_t freq;
} wfstruct;

int get_word_freq (wfstruct *words, size_t *idx, FILE *fp);
int compare (const void *a, const void *b);

int main (int argc, char **argv) {

    /* initialize variables & open file or stdin for seening */
    wfstruct words[MAXW] = {{{ 0 }, 0}};
    size_t i, idx = 0;
    FILE *fp = NULL;

    if (argc < 2) { /* read from stdin */
        get_word_freq (words, &idx, stdin);
    }
    else {
        /* read each file given on command line */
        for (i = 1; i < (size_t)argc; i++)
        {   /* open file for reading */
            if (!(fp = fopen (argv[i], "r"))) {
                fprintf (stderr, "error: file open failed '%s'.\n", 
                        argv[i]);
                continue;
            }

            /* check 'idx' against MAXW */
            if (idx == MAXW) break;

            get_word_freq (words, &idx, fp);
        }
    }

    /* sort words alphabetically */
    qsort (words, idx, sizeof *words, compare);

    printf ("\nthe occurrence of words are:\n\n");
    for (i = 0; i < idx; i++)
        printf ("  %-28s : %zu\n", words[i].seen, words[i].freq);

    return 0;
}

int get_word_freq (wfstruct *words, size_t *idx, FILE *fp)
{
    char word[MAXC] = {0};
    size_t i;

    /* read 1st word into array, update index 'idx' */
    if (*idx == 0) {
        if (fscanf (fp, " %32[^ ,.\t\n]%*c", word) == 1) {
            strcpy (words[*idx].seen, word);
            words[*idx].freq++;
            (*idx)++;
        }
        else {
            fprintf (stderr, "error: file read error.\n");
            return 1;
        }
    }

    /* read each word in file */
    while (fscanf (fp, " %32[^ ,.\t\n]%*c", word) == 1) {
        /* check against all words in struct */
        for (i = 0; i < *idx; i++) {
            /* if word already 'seen', update 'words[i]. freq' count */
            if (strcmp (words[i].seen, word) == 0) {
                words[i].freq++;
                goto skipdup;   /* skip adding word to 'words[i].seen' */
            }
        } /* add to 'words[*idx].seen', update words[*idx].freq & '*idx' */
        strcpy (words[*idx].seen, word);
        words[*idx].freq++;
        (*idx)++;

    skipdup:

        if (*idx == MAXW) { /* check 'idx' against MAXW */
            fprintf (stderr, "warning: MAXW words exceeded.\n");
            break;
        }
    }
    fclose (fp);

    return 0;
}

/* qsort compare funciton */
int compare (const void *a, const void *b)
{
    wfstruct *ap = (wfstruct *)a;
    wfstruct *bp = (wfstruct *)b;
    return (strcmp (ap->seen, bp->seen));
}

输出

$ ./bin/file_words_occur_multi dat/words.txt dat/words.txt

the occurrence of words are:

  a                            : 2
  avoid                        : 2
  brave                        : 2
  brown                        : 2
  captain                      : 2
  dog                          : 4
  fox                          : 4
  in                           : 2
  jack                         : 2
  jumps                        : 4
  lazy                         : 2
  of                           : 2
  on                           : 2
  over                         : 4
  path                         : 2
  pirate                       : 2
  quick                        : 2
  seas                         : 2
  seven                        : 2
  so                           : 2
  sparrow                      : 2
  squirrel                     : 4
  the                          : 16
  to                           : 2
  was                          : 2

作为非指针传递索引(idx)

如上所述，有两种方法可以跟踪在多个文件中看到的唯一单词的数量:(1)传递索引并将总数保持在 main中，或者(2)传递指向索引的指针并直接更新其值在功能上。上面的示例传递了一个指针。由于解引用和正确使用指针值所需的其他语法对于C语言新手来说可能是个挑战，因此这里有一个示例，将 idx作为简单变量传递，并在 main中跟踪总数。

( 注意:，您需要以任何一种方式传递索引，您可以选择是否将 idx作为常规变量传递并在函数中使用变量的副本，或者是否将 idx作为指针传递并在值直接在函数中)

这是对 get_word_freq的简单更改，然后是 main所需的更改(注意:选择 size_t作为类型而不是 int，因为数组索引永远不能为负):

size_t get_word_freq (wfstruct *words, size_t idx, FILE *fp)
{
    char word[MAXC] = {0};
    size_t i;

    /* read 1st word into array, update index 'idx' */
    if (idx == 0) {
        if (fscanf (fp, " %32[^ ,.\t\n]%*c", word) == 1) {
            strcpy (words[idx].seen, word);
            words[idx].freq++;
            idx++;
        }
        else {
            fprintf (stderr, "error: file read error.\n");
            return idx;
        }
    }

    /* read each word in file */
    while (fscanf (fp, " %32[^ ,.\t\n]%*c", word) == 1) {
        /* check against all words in struct */
        for (i = 0; i < idx; i++) {
            /* if word already 'seen', update 'words[i]. freq' count */
            if (strcmp (words[i].seen, word) == 0) {
                words[i].freq++;
                goto skipdup;   /* skip adding word to 'words[i].seen' */
            }
        } /* add to 'words[*idx].seen', update words[*idx].freq & '*idx' */
        strcpy (words[idx].seen, word);
        words[idx].freq++;
        idx++;

    skipdup:

        if (idx == MAXW) { /* check 'idx' against MAXW */
            fprintf (stderr, "warning: MAXW words exceeded.\n");
            break;
        }
    }
    fclose (fp);

    return idx;
}

main中所需的更改:

    ...
    if (argc < 2) { /* read from stdin */
        idx = get_word_freq (words, idx, stdin);
    }
    else {
        /* read each file given on command line */
        for (i = 1; i < (size_t)argc; i++)
        {   /* open file for reading */
            ...
            /* check 'idx' against MAXW */
            if ((idx = get_word_freq (words, idx, fp)) == MAXW)
                break;
        }
    }
    ...

如果您还有其他问题，请告诉我。