C言語関係掲示板

過去ログ

No785 ハフマン符号化をCで行う

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

ハフマン符号化をCで行う
投稿者---huffman(2003/10/14 17:00:03)


学校の授業で情報源記号としての文字を入力して、さらにその発生確率を入力すれば、符号化の木と
各々の符号語が表示されるプログラムをつくるのが課題に出たのですが、行き詰まって
しまいました。このような表示の場合は、どのような方法で表示すればいいのか
アドバイスを願います。とりあえずは、文字以外の表示方法が、graphic関数と
curses関数しかしらないので、cursesで表示しようとしています。しかし
表示位置などを表すのが本人しかわからないぐらい見辛くなってしまいました。
そのプログラムは、
#include<stdio.h>
#include<stdlib.h>
#include<curses.h>

#define MAX_DATA (10)
#define SCREEN_HEIGHT (8)
#define SCREEN_WIDTH (90)

void sort(int i);
void curses(int num);
void indicate(int num);
    /*とりあえずデータは入れる。*/
float proba[MAX_DATA]={0.3,0.4,0.25,0.1,0.7};
char chara[MAX_DATA]="abcdefg";
WINDOW * screen;


int main(){
    int i,num;
    /*取り込む文字数*/
    num = 7;
    printf("Input charactor number : \n");
    scanf("%d",&num);
    if(num != 1){
    curses(num);
        }
}



void curses(int num){

    initscr();
    cbreak();
    noecho();
    
    screen = newwin(num*4+5,SCREEN_WIDTH,0,0);
    
    wtimeout(screen,30);

    box(screen,'|','-');
    
    indicate(num);

    endwin();
}

void indicate(int num){
    int i,j,k,l,m,n;
    
    
    
    mvwaddstr(screen,1,SCREEN_WIDTH-5,"mark");
    /* first */
    
    /*下から順に二つの葉を繋げていく(こんな単純なパターンだけでは無理)*/
    for(i = 0; i<num; i++){
        mvwaddch(screen,i*4+2,SCREEN_WIDTH-18,'o');
        mvwprintw(screen,i*4+3,SCREEN_WIDTH-20,"%c(%f)",chara[i],proba[i]);
    
    }
    i--;
    
    for(j = 0; j<num-1; j++){
        
        mvwaddstr(screen,i*4+2-j*2,SCREEN_WIDTH-21-4*j,"___");
        
        for(k = 0; k<4+j*2; k++){
            mvwaddch(screen,i*4+2-j*2-k,SCREEN_WIDTH-22-4*j,'|');
        }
        for(l = 0; l<3+j*4; l++){
            mvwaddch(screen,i*4-2-j*4,SCREEN_WIDTH-19-l,'_');
        }
        mvwaddch(screen,i*4+1-j*2-k,SCREEN_WIDTH-22-4*j,'0');
        mvwaddch(screen,i*4+8-k,SCREEN_WIDTH-22-4*j,'1');
    }
    for(m = 1; m<3; m++){
        mvwaddch(screen,j+4,SCREEN_WIDTH-18-4*j-m,'_');
    }    
    wmove(screen,0,0);
    wrefresh(screen);

    sleep(60);


}



No.9762

Re:ハフマン符号化をCで行う
投稿者---huffman(2003/10/14 17:06:08)


続きです。それと入力用にとりあえず作ったプログラムが以下のものですが、
文字の取り込みのforのループがうまく行きません、どこがおかしいのか時間があれば
教えてください。
#include<stdio.h>
#include<stdlib.h>


#define MAX_DATA (10)


void sort(int i);



float proba[MAX_DATA];
char chara[MAX_DATA];



void main(){
        int i,j,sum = 0,num;
        

        printf("Input number of the charactor:");
        scanf("%d",&num);
        printf("Input probability of charactor.\n");
        for(j = 0; j < num; j++){
                printf("\ncharactor:");
                scanf("%c",&chara[j]);
                
                
                
        }       

        for(i = 0; i<num; i++){
                printf("probability:");
                scanf("%f",&proba[i]);
                sum = sum + proba[i];
                
}
                
        sort(i);
        
                
}

void sort(int i){
        int j,k;
        float temp;
        char temp2;

        for(j = 0; j<i-1; j++){
         for(k = j+1; k<i; k++){
                if(proba[j]<proba[k]){
                temp = proba[j];
                temp2 = chara[j];
                proba[j] = proba[k];
                chara[j] = chara[k];
                proba[k] = temp;
                chara[k] = temp2;
}
}}
                for(j = 0; j<i; j++){
                printf("%f : %c\n",proba[j],chara[j]);
}

}


それと一度に質問して申し訳ないんですが、Windowsでcurses関数が使えるコンパイラ
があれば教えてください。SunOSとのコンパイラとあんまり違わないのはあるのですか?

No.9763

Re:ハフマン符号化をCで行う
投稿者---huffman(2003/10/14 17:19:19)


申し訳ないです。さらに追加です。学校では、良くわからないのですが、
UNIXのSunOSで、家では、RedHatのLinuxでプログラムを勉強しています。
基本的な関数のみの場合はWindowsでCmachineというコンパイラを使っています。
質問と状況説明は以上です。時間があればアドバイス願います。

No.9768

Re:ハフマン符号化をCで行う
投稿者---物見遊山(2003/10/14 18:50:36)


#どこにレスしようか・・・?

>それと一度に質問して申し訳ないんですが、Windowsでcurses関数が使えるコンパイラ
>があれば教えてください。SunOSとのコンパイラとあんまり違わないのはあるのですか?

#ハフマン符号化とやらは全然わからないが
#このお題なら。

コンパイラじゃないんだけどcygwinでどーでしょ?
$ uname
CYGWIN_NT-5.1

$ locate libcurses
/lib/libcurses.a
/lib/libcurses.dll.a
/usr/lib/libcurses.a
/usr/lib/libcurses.dll.a

$


No.9773

Re:ハフマン符号化をCで行う
投稿者---huffman(2003/10/14 21:29:41)


レス有難うございます。なにやら難しそうですね・・・ cygwinのページも英語なので時間かかりそうですが読んで見ます。

No.9822

Re:ハフマン符号化をCで行う
投稿者---huffman : (名前:村上)(2003/10/16 14:32:09)


>続きです。それと入力用にとりあえず作ったプログラムが以下のものですが、
>文字の取り込みのforのループがうまく行きません、どこがおかしいのか時間があれば
>教えてください。
誰か考えてくれてるか分かりませんが、解決しました。scanfで文字を取り込む
時、次の文字を連続して取り込めないのは、return(Enter)キーの分も取り込まれて
いたからでした。とりあえず、配列のデータを倍にして一個飛ばしに文字を
取り込んでいきましたが。他に、連続して一つずつ文字を配列に取り込んでいく
方法があれば教えてください。

No.9827

Re:ハフマン符号化をCで行う
投稿者---あかま(2003/10/16 16:18:11)


>取り込んでいきましたが。他に、連続して一つずつ文字を配列に取り込んでいく
>方法があれば教えてください。
scanf("%c",&chara[j]);

scanf(" %c",&chara[j]);
こう直したら動くかも。


No.9830

Re:ハフマン符号化をCで行う
投稿者---huffman : (名前:村上)(2003/10/16 16:44:07)


動きました!不思議っすねスペース一個で違って来るなんて。
これで綺麗に書けます。ありがとうございました!!



No.9837

Re:ハフマン符号化をCで行う
投稿者---RAPT(2003/10/16 23:58:12)


不思議なのではなく、仕様です。
scanf()の書式指定しに着いて調べれば分かりますが、半角スペースは、
空白、タブ、改行などをスキップすることを意味します。

今回は関係無いかもしれませんが、rewind()について調べてみるのも
いいかもしれません。


No.9847

Re:ハフマン符号化をCで行う
投稿者---ムラ(2003/10/17 13:34:42)


そういう意味だったんですか、ありがとうございます。ところで、本題のハフマン符号化の問題ですが、とりあえずハフマン符号化をするプログラムを書いて、その符号語から木の表示に持っていく手順で、その符号化した際の情報源記号のデータからcursesでの表示で何とかなりそうです。