掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.25355

ソート
投稿者---toto(2006/01/14 20:46:50)


はじめましてtotoです。テキストの中にある文字の出題頻度を調べるプログラムを書いています。出題頻度のところはなんとかなったのですが、頻度の高い順に文字と出題頻度を並べ替えることができません。このプログラムに適したソートはどのようなものがいいのでしょうか?またソートを実装するためにはどうすればよいのでしょうか?
プログラミング環境はcygwinです。

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define MAX_TNG 50
#define TNG_SIZ 1

typedef struct{
    char    tango[TNG_SIZ+1];    /* 単語 */
    int        count;            /* カウント */
} TangoHyo ;

enum{ NO,YES } ;

int WordCnt( TangoHyo * tp, int num, const char * ptr )
{
    int pos ;
    int find;
    char buf[TNG_SIZ+1], *p ;
    while( *ptr != '\0' ){
        while( *ptr != '\0' && !isalpha(*ptr)){
            ptr++ ;
        }
        if( *ptr == '\0' ){
            break ;
        }
        p= buf ;
        for( pos= 0 ; pos < TNG_SIZ && isalpha(*ptr) ; pos++ ){
            *p++ = *ptr++ ;
        }
        *p= '\0';
        find= NO ;
        for( pos= 0 ; pos < num ; pos++ ){
            if( strcmp(tp[pos].tango,buf) == 0 ){
                tp[pos].count++ ;
                find= YES ;
                break ;
            }
        }
        if( !find ){
            strcpy(tp[num].tango,buf);
            tp[num].count= 1 ;
            num++ ;
        }
    }

    return num ;
}

int main(void)
{
    FILE *fp;
    char line[1024];
    TangoHyo tangohyo[ MAX_TNG ];
    int num=0;
    int cnt ;

    /* ファイルの読み込み */
    if((fp=fopen("styles.txt","r"))==NULL)
    {
        printf("File not open...\n");
        exit(1);
    }

    /* 判断 */
    while( fgets( line, sizeof line, fp ) != 0){
        num= WordCnt( tangohyo, num, line ) ;
        if( MAX_TNG < num ){
            break ;
        }
    }
    fclose(fp);

    for( cnt= 0 ; cnt < num ; cnt++ )
    {
            printf("%s\t%d\n",tangohyo[cnt].tango, tangohyo[cnt].count);
    }

    return 0;
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:ソート 25356 επιστημη 2006/01/14 22:28:56


No.25356

Re:ソート
投稿者---επιστημη(2006/01/14 22:28:56)


> このプログラムに適したソートはどのようなものがいいのでしょうか?

要素数がたいした量ではないのでどんなソートでも大差ないでしょう。

> またソートを実装するためにはどうすればよいのでしょうか?

実装する必要はありません。関数 qsort を呼ぶだけ。



この投稿にコメントする

削除パスワード

No.25362

Re:ソート
投稿者---toto(2006/01/15 06:17:45)


>実装する必要はありません。関数 qsort を呼ぶだけ。

とありますが、数字では大きさの比較でできるのですが、文字の場合にはどのようにひかくすればいいのでしょうか?

qsort関数の例
void qsort(void *base, size_t num, size_t size,
int (*compare)(const void*, const void*))

よろしくお願いします。



この投稿にコメントする

削除パスワード

No.25363

Re:ソート
投稿者---επιστημη(2006/01/15 08:14:57)


>文字の場合にはどのようにひかくすればいいのでしょうか?

関数 strcmp を呼べばいい。


この投稿にコメントする

削除パスワード

No.25375

Re:ソート
投稿者---toto(2006/01/15 15:07:04)


>関数 strcmp を呼べばいい。
関数を呼びましたがどうもうまくいきません。すいませんまたアドバイスお願いします。コンパイルして実行はできました。

#include&lt;ctype.h&gt;
#include&lt;stdlib.h&gt;

#define MAX_TNG 50
#define TNG_SIZ 1

typedef struct{
char tango[TNG_SIZ+1]; /* 単語 */
int count; /* カウント */
}TangoHyo;

enum{ NO,YES } ;

int WordCnt( TangoHyo * tp, int num, const char * ptr )
{
int pos ;
int find;
char buf[TNG_SIZ+1], *p ;
while( *ptr != '\0' ){
while( *ptr != '\0'&amp;&amp; !isalpha(*ptr))
{
ptr++ ;
}

p= buf ;
for( pos= 0 ; pos &lt; TNG_SIZ &amp;&amp; isalpha(*ptr) ; pos++ )
{
*p++ = *ptr++ ;
}

*p= '\0';
find= NO ;
for( pos= 0 ; pos &lt; num ; pos++ ){
if( strcmp(tp[pos].tango,buf) == 0 ){
tp[pos].count++ ;
find= YES ;
break ;
}
}

if( !find )
{
strcpy(tp[num].tango,buf);
tp[num].count= 1 ;
num++ ;
}
}
return num ;
}


int fnCompare(const TangoHyo* data1, const TangoHyo* data2)
{
return strcmp(data1-&gt;tango, data2-&gt;tango);
}

int main(int argc, char *argv[] )
{
FILE *fp;
char line[1024];
TangoHyo tangohyo[ MAX_TNG ];
int num=0;
int cnt ;

/* ファイルの読み込み */
if((fp=fopen( argv[1], &quot;r&quot;))==NULL)
{
printf(&quot;File not open...\n&quot;);
exit(1);
}

/* 判断 */
while( fgets( line, sizeof line, fp ) != 0)
{
num= WordCnt( tangohyo, num, line ) ;
if( MAX_TNG &lt; num )
{
break ;
}
}
fclose(fp);

qsort(tangohyo, num, sizeof tangohyo[0], fnCompare);

/*ファイルに出力*/
fp=fopen(&quot;tangohyo.txt&quot;,&quot;w&quot;);
for( cnt= 0 ; cnt &lt; num ; cnt++ )
{
printf(&quot;%s\t%d\n&quot;,tangohyo[cnt].tango, tangohyo[cnt].count);
fprintf(fp,&quot;%s\t%d\n&quot;,tangohyo[cnt].tango, tangohyo[cnt].count);
}
fclose(fp);

return 0;
}
</pre>




この投稿にコメントする

削除パスワード

No.25382

Re:ソート
投稿者---επιστημη(2006/01/15 15:57:53)


>関数を呼びましたがどうもうまくいきません。

なにがどううまくいかないか、説明してください。
「具合が悪い」の一言で治療してくれる医者はいません。

こんなんでいかが? 出現頻度の多い順、同じ場合は辞書順に並べています。

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

#define TNG_SIZ 31

typedef struct{
    char    tango[TNG_SIZ+1];    /* 単語 */
    int     count;            /* カウント */
} TangoHyo ;

int compare(const void* x, const void* y) {
  const TangoHyo* tx = (const TangoHyo*)x;
  const TangoHyo* ty = (const TangoHyo*)y;
  int diff = tx->count - ty->count;
  if ( diff != 0 ) return -diff;
  return strcmp(tx->tango, ty->tango);
}

int main() {
  int num = 5;
  int cnt;
  
  TangoHyo tangohyo[5] = {
    { "apple",  3 },
    { "banana", 2 },
    { "cherry", 5 },
    { "grape",  2 },
    { "peach",  2 }
  };

  qsort(tangohyo, num, sizeof(TangoHyo), &compare);

  for( cnt= 0 ; cnt < num ; cnt++ ) {
    printf("%s\t%d\n",tangohyo[cnt].tango, tangohyo[cnt].count);
  }

    return 0;
}




この投稿にコメントする

削除パスワード

No.25384

Re:ソート
投稿者---toto(2006/01/15 16:18:52)


επιστημη様、RAPTアドバイスありがとうございました。
以下のようになりました。επιστημη様、strcmpの関数の意味を理解していませんでした。じっくり勉強させていただきます。

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

#define MAX_TNG 10
#define TNG_SIZ 1

    typedef struct{
    char tango[TNG_SIZ+1];  /* 単語 */
    int count;        /* カウント */
    }TangoHyo;

enum{ NO,YES } ;

int WordCnt( TangoHyo * tp, int num, const char * ptr )
{
    int pos ;
    int find;
    char buf[TNG_SIZ+1], *p ;
    while( *ptr != '\0' ){
        while( *ptr != '\0'&& !isalpha(*ptr))
        {
            ptr++ ;
        }

        if( *ptr == '\0' )
        {
            break ;
        }

        p= buf ;
        for( pos= 0 ; pos < TNG_SIZ && isalpha(*ptr) ; pos++ )
        {
            *p++ = *ptr++ ;
        }

        *p= '\0';
        find= NO ;
        for( pos= 0 ; pos < num ; pos++ ){
            if( strcmp(tp[pos].tango,buf) == 0 ){
                tp[pos].count++ ;
                find= YES ;
                break ;
            }
        }

        if( !find )
        {
            strcpy(tp[num].tango,buf);
            tp[num].count= 1 ;
            num++ ;
        }
    }
    return num ;
}


int compare(const void* x, const void* y)
{
  const TangoHyo* tx = (const TangoHyo*)x;
  const TangoHyo* ty = (const TangoHyo*)y;
  int diff = tx->count - ty->count;
  if ( diff != 0 ) return -diff;
  return strcmp(tx->tango, ty->tango);
}

int main(int argc, char *argv[] )
{
    FILE *fp;
    char line[1024];
    TangoHyo tangohyo[ MAX_TNG ];
    int num=0;
    int cnt;
    
    /* ファイルの読み込み */
    if((fp=fopen( argv[1], "r"))==NULL)
    {
        printf("File not open...\n");
        exit(1);
    }

    /* 判断 */
    while( fgets( line, sizeof line, fp ) != 0)
    {
        num= WordCnt( tangohyo, num, line ) ;
        if( MAX_TNG <= num )
        {
            break ;
        }
    }
    fclose(fp);

    qsort(tangohyo, num, sizeof(TangoHyo), &compare);

    /*ファイルに出力*/
    fp=fopen("out.txt","w");
    for( cnt= 0 ; cnt < num ; cnt++ )
    {
        printf("%s\t%d\n",tangohyo[cnt].tango, tangohyo[cnt].count);
        fprintf(fp,"%s\t%d\n",tangohyo[cnt].tango, tangohyo[cnt].count);
    }
    fclose(fp);
    
    return 0;
}



後、バグにきずいたのですがMAX_TNGを10にしても12個表示されてしまいます。これはどのようにすれば回避できるのでしょうか?


この投稿にコメントする

削除パスワード

No.25385

Re:ソート
投稿者---επιστημη(2006/01/15 16:26:03)


>後、バグにきずいたのですがMAX_TNGを10にしても12個表示されてしまいます。これはどのようにすれば回避できるのでしょうか?

int WordCnt( TangoHyo * tp, int num, const char * ptr )
のインタフェースを見直すべし。

このままではMAX_TNG以上の単語を勘定してしまいます。
引数として最大登録数を与えないと。



この投稿にコメントする

削除パスワード

No.25386

Re:ソート
投稿者---επιστημη(2006/01/15 16:28:30)


#define TNG_SIZ 1

typedef struct{
char tango[TNG_SIZ+1];
int count;
}TangoHyo;

…ところで別件なんですけど、単語って"たった一文字"なんですか?



この投稿にコメントする

削除パスワード

No.25387

Re:ソート
投稿者---toto(2006/01/15 16:40:46)


>…ところで別件なんですけど、単語って"たった一文字"なんですか?
実は、3にして連続する3文字の出現頻度をもとめたいのですが、1〜3の間の中で出題頻度が多い順に出力されていまうのです。

A 2
AN 1
By 1
CON 1
DOY 1
DY 1
IN 1
LE 1
RLE 1
SCA 1
STU 1
T 1

これの解決策が全然おもいつかなくて途方にくれています。





この投稿にコメントする

削除パスワード

No.25398

Re:ソート
投稿者---επιστημη(2006/01/15 18:07:39)


>>…ところで別件なんですけど、単語って"たった一文字"なんですか?
>実は、3にして連続する3文字の出現頻度をもとめたいのですが、1〜3の間の中で出題頻度が多い順に出力されていまうのです。
> ...
>これの解決策が全然おもいつかなくて途方にくれています。

一文字以上の単語があるんなら思いっきりバグじゃん。
それがわかってて、なぜに
#define TNG_SIZ 1
なんですか?

ソートうんぬん以前にここらへんを何とかするのが先決。



この投稿にコメントする

削除パスワード

No.25401

Re:ソート
投稿者---toto(2006/01/15 19:43:57)


そこはソートのために、分かりやすいようにしました。
説明不足でごめんなさい^^;

#define MAX_TNG 50
#define TNG_SIZ 3

実際はこちらで行っています。



この投稿にコメントする

削除パスワード

No.25402

Re:ソート
投稿者---επιστημη(2006/01/15 19:50:29)


>#define TNG_SIZ 3
>実際はこちらで行っています。

なんだそりゃー orz

ともかく、仕様を明確に。
「文字数が3である単語のみを出現頻度の大きい順に並べよ」
ですか?

解法としてはいくつもあります。
- 短い単語は単語表に登録しない
- 短い単語の頻度は符号(+/-)を反転させてソート、そのご元に戻す
などなど。




この投稿にコメントする

削除パスワード

No.25403

Re:ソート
投稿者---επιστημη(2006/01/15 19:56:05)


>解法としてはいくつもあります。
>- 短い単語は単語表に登録しない
>- 短い単語の頻度は符号(+/-)を反転させてソート、そのご元に戻す

- まず「文字数の多いものが大きい」とする
 文字数が同じなら辞書順で比較
という比較関数食わせるだけかな?



この投稿にコメントする

削除パスワード

No.25406

Re:ソート
投稿者---επιστημη(2006/01/15 21:38:11)


>- まず「文字数の多いものが大きい」とする
> 文字数が同じなら辞書順で比較

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

#define TNG_SIZ 31

typedef struct{
    char    tango[TNG_SIZ+1];    /* 単語 */
    int     count;            /* カウント */
} TangoHyo ;

int compare(const void* x, const void* y) {
  const TangoHyo* tx = (const TangoHyo*)x;
  const TangoHyo* ty = (const TangoHyo*)y;
  int diff;
  diff = strlen(tx->tango) - strlen(ty->tango);
  if ( diff != 0 ) return -diff;
  diff = tx->count - ty->count;
  if ( diff != 0 ) return -diff;
  return strcmp(tx->tango, ty->tango);
}

int main() {
  int num = 15;
  int cnt;
  
  TangoHyo tangohyo[15] = {
    { "a",    3 },
    { "b",    2 },
    { "c",    5 },
    { "d",    2 },
    { "e",    2 },
    { "aa",   3 },
    { "bb",   2 },
    { "cc",   5 },
    { "dd",   2 },
    { "ee",   2 },
    { "aaa",  3 },
    { "bbb",  2 },
    { "ccc",  5 },
    { "ddd",  2 },
    { "eee",  2 },
  };

  qsort(tangohyo, num, sizeof(TangoHyo), &compare);

  for( cnt= 0 ; cnt < num ; cnt++ ) {
    printf("%s\t%d\n",tangohyo[cnt].tango, tangohyo[cnt].count);
  }

  return 0;
}



ってことで。


この投稿にコメントする

削除パスワード

No.25524

Re:ソート
投稿者---toto(2006/01/20 23:21:48)


とて参考になりました。皆様ありがとうございました。


この投稿にコメントする

削除パスワード

No.25383

Re:ソート
投稿者---RAPT(2006/01/15 15:58:09)


変換に失敗しています。確認画面でなぜ気付かない?
HTML変換しただけのものを貼り付けます。
# CSrcConv って、改行文字の後のCスタイルのコメント処理がうまくないですね。。

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

#define MAX_TNG 50
#define TNG_SIZ 1

typedef struct{
    char tango[TNG_SIZ+1]; /* 単語 */
    int count; /* カウント */
}TangoHyo;

enum{ NO,YES } ;

int WordCnt( TangoHyo * tp, int num, const char * ptr )
{
    int pos ;
    int find;
    char buf[TNG_SIZ+1], *p ;
    while( *ptr != '\0' ){
        while( *ptr != '\0'&& !isalpha(*ptr))
        {
            ptr++ ;
        }
        
        p= buf ;
        for( pos= 0 ; pos < TNG_SIZ && isalpha(*ptr) ; pos++ )
        {
            *p++ = *ptr++ ;
        }
        
        *p= '\0';
        find= NO ;
        for( pos= 0 ; pos < num ; pos++ ){
            if( strcmp(tp[pos].tango,buf) == 0 ){
                tp[pos].count++ ;
                find= YES ;
                break ;
            }
        }
        
        if( !find )
        {
            strcpy(tp[num].tango,buf);
            tp[num].count= 1 ;
            num++ ;
        }
    }
    return num ;
}

int fnCompare(const TangoHyo* data1, const TangoHyo* data2)
{
    return strcmp(data1->tango, data2->tango);
}

int main(int argc, char *argv[] )
{
    FILE *fp;
    char line[1024];
    TangoHyo tangohyo[ MAX_TNG ];
    int num=0;
    int cnt;

    /* ファイルの読み込み */
    if((fp=fopen( argv[1], "r"))==NULL)
    {
        printf("File not open...\n");
        exit(1);
    }

    /* 判断 */
    while( fgets( line, sizeof line, fp ) != 0)
    {
        num= WordCnt( tangohyo, num, line ) ;
        if( MAX_TNG < num )
        {
            break ;
        }
    }
    fclose(fp);
    
    qsort(tangohyo, num, sizeof tangohyo[0], fnCompare);

    /*ファイルに出力*/
    fp=fopen("tangohyo.txt","w");
    for( cnt= 0 ; cnt < num ; cnt++ )
    {
        printf("%s\t%d\n",tangohyo[cnt].tango, tangohyo[cnt].count);
        fprintf(fp,"%s\t%d\n",tangohyo[cnt].tango, tangohyo[cnt].count);
    }
    fclose(fp);
    
    return 0;
}



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧