C言語関係掲示板

過去ログ

No865 ファイルの中の文字を使われている文字数順でソート

[戻る] [ホームページ]
No.11211

この問題を教えて貰いたいのですが・・・。
投稿者---not(2003/12/15 17:29:34)


与えられたファイルの中の文字を使われている文字数順に、文字と文字数を出力しなさい。但し、日本語と空白以外の文字は全て数えることとします。

例.
入力:
This is a pen.
出力:
i: 2
s: 2
T: 1
h: 1
a: 1
p: 1
e: 1
n: 1
.: 1

サンプルなのですが・・・。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tr {
  char *key;
  int num;
  struct tr *left,*right;
} TREE;
int get(TREE *t, char *k){
  int res;
  if(t==NULL){
    return 0;
  }else{
    res=strcmp(t->key,k);
    if(res==0){
      return t->num;
    }else if(res<0){
      return get(t->left,k);
    }else{
      return get(t->right,k);
    }
  }
}
void set(TREE **t, char *k, int i){
  int res;
  TREE *newnode;
  if(*t==NULL){
    *t=(TREE *)malloc(sizeof(TREE));
    (*t)->key=k;
    (*t)->num=i;
    (*t)->left=NULL;
    (*t)->right=NULL;
  }else{
    res=strcmp((*t)->key,k);
    if(res==0){
      (*t)->num=i;
    }else if(res<0){
      return set(&((*t)->left),k,i);
    }else{
      return set(&((*t)->right),k,i);
    }
  }
}
void show(TREE *t){
  if(t!=NULL){
    show(t->left);
    printf("%s: %d\n",t->key,t->num);
    show(t->right);
  }
}
main(){
  TREE *t=NULL;
  set(&t,"abc",50);
  set(&t,"def",20);
  printf("%d\n",get(t,"abc"));
  printf("%d\n",get(t,"def"));
}



No.11212

Re:この問題を教えて貰いたいのですが・・・。
投稿者---not(2003/12/15 17:33:29)


サンプルは木構造を利用して、文字列がキーとなる配列を作ってます。 set(ポインタの番地, キー, 値) と get(ポインタ, キー) で値の格納、取り出しを行うようになってます。




No.11256

助けて下さい・・・。
投稿者---not(2003/12/17 19:39:11)


自分で作ったら上手くいかないので、どなたかご教授して下さい。
お願いします!

<pre>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
typedef struct tr {
char *key;
int num;
struct tr *left,*right;
} TREE;
int get(TREE *t, char k){
int res;
if(t-&gt;key==k){
return 0;
}else{
res=strcmp(t-&gt;key&lt;k);
if(res==0){
return t-&gt;num;
}else if(res&lt;0){
return get(t-&gt;left,k);
}else{
return get(t-&gt;right,k);
}
}
}
void set(TREE **t, char *k, int i){
int res;
TREE *newnode;
if(*t==NULL){
*t=(TREE *)malloc(sizeof(TREE));
(*t)-&gt;key=k;
(*t)-&gt;num=i;
(*t)-&gt;left=NULL;
(*t)-&gt;right=NULL;
}else{
res=strcmp((*t)-&gt;key,k);
if(res==0){
(*t)-&gt;num=i;
}else if(res&lt;0){
return set(&amp;((*t)-&gt;left),k,i);
}else{
return set(&amp;((*t)-&gt;right),k,i);
}
}
}
void show(TREE *t){
if(t!=NULL){
show(t-&gt;left);
printf(&quot;%c: %d\n&quot;,t-&gt;key,t-&gt;num);
show(t-&gt;right);
}
}
main(){
char c;
TREE *t=NULL;
while((c=getchar())!==EOF){
if(c!='\n'){
set(&amp;t,c,get(t,c)+1);
}
}
show(t);

}

No.11257

間違えました・・・。
投稿者---not(2003/12/17 19:42:34)


#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tr {
  char *key;
  int num;
  struct tr *left,*right;
} TREE;
int get(TREE *t, char k){
  int res;
  if(t->key==k){
    return 0;
  }else{
    res=strcmp(t->key<k);
    if(res==0){
      return t->num;
    }else if(res<0){
      return get(t->left,k);
    }else{
      return get(t->right,k);
    }
  }
}
void set(TREE **t, char *k, int i){
  int res;
  TREE *newnode;
  if(*t==NULL){
    *t=(TREE *)malloc(sizeof(TREE));
    (*t)->key=k;
    (*t)->num=i;
    (*t)->left=NULL;
    (*t)->right=NULL;
  }else{
    res=strcmp((*t)->key,k);
    if(res==0){
      (*t)->num=i;
    }else if(res<0){
      return set(&((*t)->left),k,i);
    }else{
      return set(&((*t)->right),k,i);
    }
  }
}
void show(TREE *t){
  if(t!=NULL){
    show(t->left);
    printf("%c: %d\n",t->key,t->num);
    show(t->right);
  }
}
main(){
  char c;
  TREE *t=NULL;
  while((c=getchar())!==EOF){
    if(c!='\n'){
      set(&t,c,get(t,c)+1);
      }
  }
  show(t);
  
}


No.11262

Re:間違えました・・・。
投稿者---NykR(2003/12/17 21:27:24)


・要求されているのは文字列じゃない。
・例を見る限り、(辞書順ではなくて)入力された順番+数の二つのキーで整列されていなくてはならない。

というわけで、文字列を(辞書順で)キーとした二分探索木は使えないと思います。

それ以外のやり方だと例えばこんな感じですかね。main関数はずしてますけど。

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

typedef struct {
    int ch;
    int cnt;
} Chset;

typedef struct {
    Chset       chset[0x80];
    int  idxcnv[0x80];
    int  last_entry;
} CharCounter;

CharCounter     char_counter = {{{0, 0}}, {0}, 0};
Chset      workarray[0x80];

void set(int ch)
{
    if (!isgraph(ch))
        return;

    if (char_counter.idxcnv[ch] == 0) {
        char_counter.idxcnv[ch] = ++char_counter.last_entry;
        char_counter.chset[char_counter.idxcnv[ch]].ch = ch;
    }
    char_counter.chset[char_counter.idxcnv[ch]].cnt++;
}

void merge_sort(Chset *array, int size)
{
    int i, j, k;

    if (size <= 1)
        return;

    merge_sort(array, size / 2);
    merge_sort(array + size / 2, size / 2);

    for (k = 0; k < size / 2; k++) {
        workarray[k] = array[k];
        workarray[size-1-k] = array[k+size/2];
    }

    i = 0;
    j = size - 1;
    for (k = 0; k < size; k++) {
        if (workarray[i].cnt >= workarray[j].cnt && i < size / 2) {
            array[k] = workarray[i++];
        } else {
            array[k] = workarray[j--];
        }
    }
}


No.11265

Re:間違えました・・・。
投稿者---NykR(2003/12/17 21:40:49)


>main関数はずしてますけど。

マージソートが珍しい書き方なので呼び出し部分だけ書いておきますね。
第2引数は2^nなら何でもいいけど(もちろん要素数より大きくないとだめです)。

merge_sort(char_counter.chset, 0x80);

No.11308

Re:間違えました・・・。
投稿者---NykR(2003/12/19 08:50:50)


>マージソートが珍しい書き方なので

サイズに限定付けた方が簡単だと思ったんですけど、そうでもなかったんで普通のやり方に変えます。
文字の種類が少ないときはこっちの方が早いし。
#全体からみると誤差の範囲ですが

void merge_sort(Chset *array, int size)
{
    int i, j, k;

    if (size <= 1)
        return;

    merge_sort(array, size / 2);
    merge_sort(array + size / 2, size - size / 2);

    for (i = 0; i < size / 2; i++) {
        workarray[i] = array[i];
    }
    for (i = k = 0, j = size / 2; i < size / 2 && j < size; k++) {
        if (workarray[i].cnt >= array[j].cnt) {
            array[k] = workarray[i];
            i++;
        } else {
            array[k] = array[j];
            j++;
        }
    }
    for ( ; i < size / 2; i++, k++) {
        array[k] = workarray[i];
    }
}


No.11275

Re:間違えました・・・。
投稿者---NykR(2003/12/18 09:39:30)


<stdlib.h>と<string.h>は残骸なので削ってください。

No.11291

返信有難う御座います。
投稿者---not(2003/12/18 16:42:01)


ソースの詳しい説明をして頂けると、とても有難いのですが・・・。
お手数ですが、宜しくお願いします!!


No.11385

再度質問なのですが・・・。
投稿者---not(2003/12/21 22:44:59)


初心者なもので、プログラムの流れや、どのようにして作ったのかを具体的に、
説明して頂けないでしょうか?

No.11388

Re:再度質問なのですが・・・。
投稿者---RAPT(2003/12/21 23:31:54)


ソートなどは、基本的なアルゴリズムなので、アルゴリズムに関する
勉強をして下さい。

基本情報処理技術者(だっけ?)なんかのテキストなどにも掲載
されていると思います。

# ソートのアルゴリズムを理解した上で、それをC言語として
# 利用する際の技術的な質問をしているのならいいのですが。

No.11390

Re:再度質問なのですが・・・。
投稿者---NykR(2003/12/22 11:17:51)


>プログラムの流れや、どのようにして作ったのかを具体的に、

説明するつもりはまったくありません。
そういう気があるならはじめからソースなど書かずに説明だけして済ませています。

set()は、紙と鉛筆を使って処理を追って行けば何をやってるかぐらいはわかるでしょうし、
merge_sort()は片仮名で「マージソート」とはっきり書いてあるのだから自分で調べられるはずです。

それをやった上でわからないことがあるのなら、再度質問をどうぞ。

RAPTさん>
フォローありがとうございます

No.11393

Re:再度質問なのですが・・・。
投稿者---NykR(2003/12/22 12:23:20)


>set()は、紙と鉛筆を使って処理を追って行けば何をやってるかぐらいはわかるでしょうし、

set()は文字を受け取る関数です。
例えば'T'を受け取ったとき、'T'の文字コードは(ASCIIでは)
84なので、関数5行目の

if (char_counter.idxcnv[ch] == 0)

は、char_counter.idxcnvという配列の
84番目の要素が0かどうか調べています。