0

私は、テキスト ファイルからコンテンツを読み取り、次の出力例を生成する単語頻度分析プログラムの作成を任されました。

SUMMARY:

27340 words
2572 unique words

WORD FREQUENCIES (TOP 10):

the 1644
and  872
to  729
a  632
it  595
she  553
i 545
of  514
said 462
you 411

そのような出力を達成するためのプログラムを作成しようとしました。私は C プログラミングに非常に慣れていないので、ある程度は機能しますが、おそらく多くの効率の問題/欠陥があります。これまでに書いたものは次のとおりです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_WORD 32
#define MAX_TEXT_LENGTH 10000

// ===========================================
//                 STRUCTURE
//============================================


typedef struct word {
char *str;              /* Stores the word */
int freq;               /* Stores the frequency */
struct word *pNext;     /* Pointer to the next word counter in the list */
} Word;

// ===========================================
//             FUNCTION PROTOTYPES
//============================================

int getNextWord(FILE *fp, char *buf, int bufsize);   /* Given function to get words */
void addWord(char *pWord);                          /* Adds a word to the list or updates exisiting word */
void show(Word *pWordcounter);        /* Outputs a word and its count of occurrences */
Word* createWordCounter(char *word);  /* Creates a new WordCounter structure */

// ===========================================
//             GLOBAL VARIABLES
//============================================

Word *pStart = NULL;                  /* Pointer to first word counter in the list */

int totalcount = 0;                  /* Total amount of words */
int uniquecount = 0;                /* Amount of unique words */



// ===========================================
//                 MAIN
//============================================      


int main () {

    /* File pointer */
    FILE * fp;
    /* Read text from here */
    fp = fopen("./test.txt","r");

    /* buf to hold the words */
    char buf[MAX_WORD];

    /* Size */
    int size = MAX_TEXT_LENGTH;


    /* Pointer to Word counter */
    Word *pCounter = NULL;


    /* Read all words from text file */

    while (getNextWord(fp, buf, size)) {

        /* Add the word to the list */
        addWord(buf); 

        /* Increment the total words counter */
        totalcount++;
    }


    /* Loop through list and figure out the number of unique words */
    pCounter = pStart;
    while(pCounter != NULL)
    {
        uniquecount++;
        pCounter = pCounter->pNext;
    }

    /* Print Summary */

    printf("\nSUMMARY:\n\n");
    printf("   %d words\n", totalcount); /* Print total words */
    printf("   %d unique words\n", uniquecount); /* Print unique words */




    /* List the words and their counts */
    pCounter = pStart;
    while(pCounter != NULL)
    {
        show(pCounter);
        pCounter = pCounter->pNext;
    }
    printf("\n");


    /* Free the allocated  memory*/
    pCounter = pStart;
    while(pCounter != NULL)
    {
        free(pCounter->str);        
        pStart = pCounter;           
        pCounter = pCounter->pNext;  
        free(pStart);                  
    }

    /* Close file */
    fclose(fp);

    return 0;

}


// ===========================================
//                 FUNCTIONS
//============================================


void show(Word *pWordcounter)
{
  /* output the word and it's count */
  printf("\n%-30s   %5d", pWordcounter->str,pWordcounter->freq);

}

void addWord(char *word)
{
  Word *pCounter = NULL;
  Word *pLast = NULL;

  if(pStart == NULL)
  {
    pStart = createWordCounter(word);
    return;
  }

  /* If the word is in the list, increment its count */
  pCounter = pStart;
  while(pCounter != NULL)
  {
    if(strcmp(word, pCounter->str) == 0)
    {
      ++pCounter->freq;

      return;
    }
    pLast = pCounter;            
    pCounter = pCounter->pNext;  
  }

  /* Word is not in the list, add it */
  pLast->pNext = createWordCounter(word);
}

Word* createWordCounter(char *word)
{
  Word *pCounter = NULL;
  pCounter = (Word*)malloc(sizeof(Word));
  pCounter->str = (char*)malloc(strlen(word)+1);
  strcpy(pCounter->str, word);
  pCounter->freq = 1;
  pCounter->pNext = NULL;
  return pCounter;
}

int getNextWord(FILE *fp, char *buf, int bufsize) {
    char *p = buf;
    char c;


    //skip all non-word characters
    do {
        c = fgetc(fp);
        if (c == EOF) 
            return 0;
        } while (!isalpha(c));

    //read word chars

    do {
        if (p - buf < bufsize - 1)
        *p++ = tolower(c);
        c = fgetc(fp);
        } while (isalpha(c));

        //finalize word
        *p = '\0';
        return 1;
        }

概要が正しく表示されます。言葉の量とユニークな言葉は完全に正しいです。次に、ファイル内で見つかったすべての一意の単語を一覧表示し、正しい出現回数を表示します。

私が今しなければならないこと (そして私が多くの問題を抱えていること) は、リンクされたリストを出現回数で降順にソートすることです。その上、上位 10 語のみを表示し、すべてを表示する必要はありません (これは、リンクされたリストを並べ替えると実行できるはずです)。

現在、コード自体が非常に非効率的であることはわかっていますが、現在の私の主な関心事は、正しい出力を取得することです。

誰かがソートアルゴリズムで私を助けてくれるか、少なくとも正しい方向に私を向けることができれば、それは大歓迎です.

ありがとうございました。

4

2 に答える 2

3

このアイデアは、初心者の C プログラマにとっては少し野心的かもしれませんが、標準ライブラリの関数を認識することは常に良い考えです。リンク リストの大きさがわかっている場合は、 を使用mallocして、同じデータを保持する配列にスペースを割り当てることができます。次に、 を使用qsortしてデータを並べ替えることができます。

関数mallocqsortは、標準 C ライブラリのメンバーとして頻繁に使用されます。

于 2012-08-06T00:47:35.910 に答える
2

リンクされたリストをソートしないでください。非常に効率が悪く、エラーが発生しやすくなります。関連するデータを配列にコピーし、qsortメソッドを使用します。

そして、アルゴリズムをより効率的にするために行くとき、私はtrie.

于 2012-08-06T00:47:58.077 に答える