単語の出現回数を数え、出現回数順に表示するには？

質問

標準入力または入力ファイルから単語の出現回数を調べるプログラムの一部です。ENTRY *add_entry(ENTRY *new)関数で以前に出てきた単語か（正確には以前に同一内容の行があったかを）判断し、既出ならばvoid do_one(FILE *fp)関数内部でp->count++として出現回数に加算しています。void do_one(FILE *fp)関数の最後の方のprintfで単語とその出現回数を表示します。これだとappleという単語が2回出てくれば、
apple:1
apple:2
と表示されます。この場合は
apple:2
だけ表示させ、さらに、出現回数の多い順に単語を並べて表示させたいんです。どういう風にすればいいでしょうか？

typedef struct entry_t {
char *str;
struct entry_t *next;
int count; /* 単語の出現回数 */
} ENTRY;

int main(int argc, char **argv)
{
FILE *fp;
char *s;
init_hash();
--argc;
++argv;
if (argc == 0)
do_one(stdin);
else {
while (argc--) {
if ((fp = fopen(*argv, "r")) == NULL)
cant(*argv); /* no return */
do_one(fp);
fclose(fp);
argv++;
}
}
free_all_entries();
return (0);
}

void do_one(FILE *fp)
{
ENTRY *p;
char buf[MAX_SIZE];
int i;

while (fgets(buf, MAX_SIZE, fp) != NULL) {
if ((p = malloc(sizeof(ENTRY))) == NULL)
error("can't alloc memory"); /* no return */
if ((p->str = strdup(buf)) == NULL)
error("can't alloc memory"); /* no return */
if (add_entry(p) != p) {
p->count++; /* 登録済みなので単語の出現回数を1増やす */
free(p->str); /* すでに登録されているので開放 */
free(p);
}
else /* 新しく単語を登録する場合 */
p->count =1; /* 単語の出現回数を1にする */
printf("%s : %d\n", p->str, p->count);
}
}

void init_hash(void)
{
int i;

for (i = 0; i < HASHSIZE; i++)
table[i] = NULL;
}

ENTRY *add_entry(ENTRY *new)
{
ENTRY *p;
int h;

h = hash(new->str); /* 追加する単語のハッシュ値を求める */
for (p = table[h]; p != NULL; p = p->next)
if (strcmp(p->str, new->str) == 0) { /* 追加済みの単語ならば */
return (p); /* そのデータのポインタを返す */
}
new->next = table[h];
table[h] = new; /* 単語を追加する */
return (new);
}

回答No.2

yama5140 · ベストアンサー

（英単語限定！）

★配列を使ったら「簡単」では・・？
　（短所：オーバーフロー（▼）の都度、要調整）

#define　MAXCNT　(2000)　// ▼
#define　un_char unsigned char // 大小比較あるため
int　igStoreCnt = 0;　// 出現単語カウンタ（グローバル）
typedef　struct{
　un_char　cStr[16];　// １単語１６文字以内
　int　iCount;　// 当単語の出現回数
}ENTRY;
ENTRY　sStore[MAXCNT];　// 単語収録（▼）

★まず読み込んだ１行を単語毎（◆）に分割
int　OneLineWordCount( un_char cBuf[] )
{
　int　i, iTop, iLen = 0;

　for( i = 0; i < 2048; i++ ){　// レコード長 2048 以内

　　if( 0x09 == cBuf[i] )　cBuf[i] = 0x20;　// タブ
　　if( 0x0D >= cBuf[i] ){　// 行末

　　　if( iLen )　WordCount( iTop, cBuf, i );　// ◆

　　　return( 0 );
　　}
　　if( 0x27 == cBuf[i] )　continue;　// 例) it's の '

　　if( ! isalpha( cBuf[i] ) ){　// デリミタ
　　　if( 0 == iLen )　continue;

　　　WordCount( iTop, cBuf, i );　// ◆

　　　iLen = 0;
　　　continue;
　　}
　　if( 0 == iLen )　iTop = i;
　　iLen++;
　}
　return( 0 );
}

★カウント部分
int　WordCount( int iTop, un_char cBuf[], int iii )
{
　int　k;

　cBuf[iii] = 0x00;

　for( k = 0; k < igStoreCnt; k++ ){

　　if( NULL == strcmp( sStore[k].cStr, &cBuf[iTop] ) ){

　　　sStore[k].iCount++;　// 既存

　　　return( 0 );
　　}
　}
　strncpy( sStore[igStoreCnt].cStr, &cBuf[iTop], 16 );

　sStore[igStoreCnt].iCount = 1;　// 新単語

　igStoreCnt++;

　if( MAXCNT < igStoreCnt )　ErrorStop( "Over" );　// ▼

　return( 0 );
}

★出力部分（同数の場合出現順）
void　Ranking( void )
{
　int　k, j, iMax, iBasyo;

　for( k = 0; k < igStoreCnt; k++ ){

　　iMax = 0;

　　for( j = 0; j < igStoreCnt; j++ ){

　　　if( sStore[j].iCount > iMax ){

　　　　iMax = sStore[j].iCount;

　　　　iBasyo = j;
　　　}
　　}
　　printf( "%4d ", k );
　　printf( "%-16s", sStore[iBasyo].cStr );
　　printf( "%3d\n", sStore[iBasyo].iCount );

　　sStore[iBasyo].iCount = 0;　// 用済み
　}
}
void　ErrorStop( un_char *cMess )
{
　fprintf( stderr, "Err %s\n", cMess );

　exit( 0 );
}
注：インデントに全角空白を使用しています。

お礼

具体的な説明ありがとうございました。じっくり考えてやってみます。

回答No.1

asuncion

do_one関数の中で出現回数を出力するのではなく、
線形リストを先頭から順に走査して回数を出力する関数を新たに設けて、
do_one関数の後で実行すればよいと思います。

出現回数によるソートの考え方は、線形リスト以外のデータ構造、
例えば配列、の場合と同じです。
ポインタの張り替えがややこしいかもしれませんけれど。

お礼

どうもありがとうございました。じっくり考えて見ます。