ショッピングモール  掲示板ランキング


【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は謹んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板1こちら


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

No.3230

ハッシュ法について
投稿者---まさと(2004/12/16 13:49:46)


今、ハッシュ法についてプログラムを考えているのですが、行き詰ってしまいました。
下にプログラムを貼り付けますので、良くないところをどんどん指摘、御教授頂けたらと思います。
データは[文字列]がランダムに入っているもので、データセットの総数は現在350くらいです。
今後、800前後のデータでプログラムを実行する予定です。
環境はWindows Me、Ultra-C Pro2を使用しております。

<エラー箇所・内容>
void Chaining(Data *temp, unsigned int f)にて、
ハッシュ表のサイズを変更すると、
【*hashtable[f]=*temp;】と【*s->next=*temp;】で、
「'='左辺値オペランドが不当」と出力されます。

<C言語ソース>
/* ハッシュ法 */
/* ハッシュ関数:除算法(division method) */

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

#define HashSize 997    /*ハッシュ表のサイズ(大きさ)*/

/*ハッシュ表に格納するデータを表す構造体*/
typedef struct cell{
    char name[30];    /*名前*/
    int collision;    /*衝突回数*/
    struct cell *next;  /*次のセルへのポインタ*/
} Data;

Data *hashtable[HashSize];    /*ハッシュ表*/
FILE *fp;

void MakeHashTable(void);      /*ハッシュ表を初期化する*/
void Chaining(Data *, unsigned int);
unsigned int Hash(char *);    /*ハッシュ関数*/
void PrintAllData(void);        /*ハッシュ表の中身を出力*/
void FreeHashTable(void);      /*ハッシュ表を後始末*/

/*ハッシュ表を初期化する*/
void MakeHashTable()
{
    Data *temp;
    int i;
    
    /*ハッシュ表を初期化*/
    for(i=0; i<HashSize; i++)
        hashtable[i]=NULL;
        
    if((fp=fopen("word.txt", "r"))==NULL){
        printf("ファイルを開く事が出来ません。\n");
        exit(1);
    }
    
    for(;;){
        temp=(Data *)malloc(sizeof(Data));  /*大きさがDataバイトの領域を確保*/
        /*ここから自信がない*/
        if(fscanf(fp, "%s", temp->name)!=EOF){
            fscanf(fp, "%s", temp->name);
            temp->next=NULL;
            Chaining(temp, Hash(temp->name));
            free(temp);
        }
        else{
            free(temp);
            break;
        }
    }
}

void Chaining(Data *temp, unsigned int f)
{
    Data *s;
    
    if(hashtable[f]==NULL){
        hashtable[f]=(Data *)malloc(sizeof(Data));
        *hashtable[f]=*temp;            /*ハッシュ表サイズが992、993、994、995、996、997、999、1000、1003、1004、1005でエラー*/
    }
    else{
        s=hashtable[f];
        while(s->next)
            s=s->next;
        s->next=(Data *)malloc(sizeof(Data));
        *s->next=*temp;    /*ハッシュ表サイズが503、998、1001、1002でエラー*/
        s->next->next=NULL;
    }
}

/*ハッシュ関数(除算法)*/
unsigned int Hash(char *buf)
{
    unsigned int value;

    for(value=0; *buf!='\0'; buf++)
        value=*buf+value*11;
    return(value%HashSize); /*valueをHashSizeで割った剰余(valueとHashSizeは整数でなければならない)*/
}

/*ハッシュ表の中身を出力*/
void PrintAllData(void)
{
    Data *s;
    int i;

    for(i=0; i<HashSize; i++){
        printf("[%d]\t", i);
        s=hashtable[i];
        while(s){
            printf("%-16s %5d\t -> ", s->name, s->collision);
            s=s->next;
        }
        printf("(NULL)\n");
    }
}
/*ハッシュ表を後始末*/
void FreeHashTable(void)
{
    int i;
    Data *s, *t;

    for(i=0; i<HashSize; i++){
        s=hashtable[i];
        while(s){
            t=s->next;
            free(s);
            s=t;
        }
    }
}

int main(void)
{
    MakeHashTable();
    PrintAllData();
    FreeHashTable();
    fclose(fp);
    return(0);
}



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:ハッシュ法について 3231 まさと 2004/12/16 13:52:11
<子記事> Re:ハッシュ法について 3233 あかま 2004/12/16 15:25:09
<子記事> Re:ハッシュ法について 3244 まさと 2004/12/17 20:33:41
<子記事> Re:ハッシュ法について 3247 まさと 2004/12/18 16:31:20


No.3231

Re:ハッシュ法について
投稿者---まさと(2004/12/16 13:52:11)


ハッシュ表に読み込む(格納する)データはword.txtとし、
データの中身は、以下に記します。

<word.txt>
rejoice
duplicate
lantern
shed
chop
livestock
network
milestone
advocate
visibility
label
sociobiology
cram
synchronize
interconnect
empirical
oral
discourse
scorn
overall
incongruous
counterpart
commentary
sermon
ethnic
linguistics
totality
reassure
banal
fluently
wit
nuance
stack
discard
quotation
decree
prophecy
generalize
stick
insecure
magically
foresee
intuition
tone
botany
cynical
popularity
kingdom
turn
dominance
combat
warfare
nephew
niece
company
probe
arouse
clumsy
mastery
heed
sink
companion
liable
inspire
reverence
snob
manhood
purse
sow
unaffected
glossy
depict
breast
bundle
dental
rubber
clutch
premature
clinic
threshold
ritual
undeniable
nonetheless
pervasive
exotic
avenge
witch
devour
cast
humiliate
subdue
nightmare
apprehend
timid
scoff
nonsense
myriad
blossom
slip
dimension
passionate
deed
fairy
long
entitle
flight
chariot
laser
beam
drug
deplore
childish
acute
dwarf
sight
stature
discern
heritage
collaborate
renew
domain
capture
colleague
recruit
personality
score
aspire
barometer
insulate
inn
arrange
bargain
standardize
crack
etiquette
thrill
cape
acquaintance
rim
explore
chase
pioneer
yearn
dig
pole
whistle
rhythmic
punctuate
agenda
interval
intricate
solemn
cumulative
climax
persevere
integrity
denounce
illustrate
hinder
foster
valley
monster
embody
docile
domesticate
streak
solitary
herd
inconclusive
inscription
captivity
cemetery
coincide
preoccupy
industrialization
criterion
backward
abreast
stagger
unparalleled
stationary
tropical
ragged
shiver
amply
flaw
uninhabitable
chimney
freeze
awkward
ancestry
melancholy
twilight
brute
prehistoric
tip
spear
equate
personify
genesis
flood
ascribe
designate
poison
suspect
pledge
amity
acidity
palatable
summary
twist
duke
dedicate
omit
horizontal
column
dignity
serene
adorn
conform
barbarian
outward
saint
interior
exemplify
carve
monument
truthfulness
aesthetic
susceptible
knee
blind
astray
cease
household
reputability
unattractive
indignant
sustain
alcohol
liquor
beverage
intoxicate
addiction
seal
adhere
consultation
keenly
widespread
envelope
paradox
pollution
radioactive
minute
agent
augment
fossil
carbon
emission
discharge
trial
suppress
constrict
fuel
locate
acre
appalling
catastrophe
capital
charitable
card
impure
mineral
vaporize
confirm
unidentified
hover
quote
dispatch
modest
status
posture
prominent
colony
bear
socialist
totalitarian
scarcely
cell
incomparably
portrait
donor
understandably
historian
document
quarter
mine
stir
eccentric
contemplate
suicide
snatch
eventually
lap
hammer
dawn
recollect
soothe
ambulance
incessant
dampen
appetite
annual
soak
gloomy
rebuke
humility
admiration
secretary
divorce
ground
expire
communist
disapprove
corrupt
namely
incompatible
greediness
lament
ardent
contrive
arm
heir
invariably
unconventional
rent
beard
haunt
debt
award
will
estate
bankrupt
prompt
fury
rash
induce
vengeful
harbor
incommunicable
clarify
qualitative
restructure
stuff
central



この投稿にコメントする

削除パスワード

No.3232

Re:ハッシュ法について
投稿者---REE(2004/12/16 14:45:53)


とりあえず、mallocの戻り値がNULLになっていないかチェックしてみましょう。



この投稿にコメントする

削除パスワード

No.3234

Re:ハッシュ法について
投稿者---まさと(2004/12/16 15:26:11)


>とりあえず、mallocの戻り値がNULLになっていないかチェックしてみましょう。
>
NULLにはなっていないですね。
現に、データの220番目saintまでは正常にプログラムが動作し、ハッシュ表に格納されています。
しかし、221番目のinteriorかプログラムがエラーをお越し、ハッシュ表に格納されません。
どうしたらいいか分からなくて、途方に暮れています


この投稿にコメントする

削除パスワード

No.3233

Re:ハッシュ法について
投稿者---あかま(2004/12/16 15:25:09)


エラーの原因はわからないんですが、その部分自体いらない気がします。
実行してませんが。

void MakeHashTable()
{
    Data *temp;
    int i;
    
    /*ハッシュ表を初期化*/
    for(i=0; i<HashSize; i++)
        hashtable[i]=NULL;
        
    if((fp=fopen("word.txt", "r"))==NULL){
        printf("ファイルを開く事が出来ません。\n");
        exit(1);
    }
    
    for(;;){
        temp=(Data *)malloc(sizeof(Data));  /*大きさがDataバイトの領域を確保*/
        /*ここから自信がない*/
        if(fscanf(fp, "%s", temp->name)!=EOF){
            //fscanf(fp, "%s", temp->name);ここ2重に読み込んでるけどまずくないです?

            temp->next=NULL;
            Chaining(temp, Hash(temp->name));
            //free(temp);いらない

        }
        else{
            free(temp);
            break;
        }
    }
    fclose(fp);//もう使わないならここでクローズしたほうが

}

void Chaining(Data *temp, unsigned int f)
{
    Data *s;
    
    if(hashtable[f]==NULL){
        //hashtable[f]=(Data *)malloc(sizeof(Data));いらない

        hashtable[f]=temp;//変更

    }
    else{
        s=hashtable[f];
        while(s->next)
            s=s->next;
        //s->next=(Data *)malloc(sizeof(Data));いらない

        s->next=temp;//変更

        //s->next->next=NULL;いらない

    }
}




この投稿にコメントする

削除パスワード

No.3235

Re:ハッシュ法について
投稿者---まさと(2004/12/16 21:24:53)


><pre>エラーの原因はわからないんですが、その部分自体いらない気がします。
実行してませんが。

あかま様、返信ありがとうございます。
無事、エラーは解決いたしました。
もう一つ質問なのですが、ハッシュ表に登録したデータを、
新たに作成したテキストファイルにデータを出力する事は可能なのでしょうか?



この投稿にコメントする

削除パスワード

No.3236

Re:ハッシュ法について
投稿者---あかま(2004/12/17 00:51:27)


>もう一つ質問なのですが、ハッシュ表に登録したデータを、
>新たに作成したテキストファイルにデータを出力する事は可能なのでしょうか?
出力するだけならこう?
void PrintAllData(void)
{
    Data *s;
    int i;
    FILE *fp;
    fp = fopen("after.txt","w");
    for(i=0; i<HashSize; i++){
        printf("[%d]\t", i);
        s=hashtable[i];
        while(s){
            printf("%-16s %5d\t -> ", s->name, s->collision);
            fprintf(fp,"%-16s %5d\t -> ", s->name, s->collision);
            s=s->next;
        }
        printf("(NULL)\n");
        fprintf(fp,"(NULL)\n");
    }
    fclose(fp);
}





この投稿にコメントする

削除パスワード

No.3237

Re:ハッシュ法について
投稿者---まさと(2004/12/17 02:14:56)


>>もう一つ質問なのですが、ハッシュ表に登録したデータを、
>>新たに作成したテキストファイルにデータを出力する事は可能なのでしょうか?
>出力するだけならこう?

誠にありがとうございます。
正常に出力されました。
また、加えて自分で衝突回数を数えるプログラムを作成していますが、
どうも出力のときに変になります。間違いを指摘していただきますようお願い致します。

--衝突出力結果--
[61]discourse ( 1回衝突) -> commentary ( 0回衝突) -> (NULL)

--理想衝突出力結果--
[61]discourse ( 0回衝突) -> commentary ( 1回衝突) -> (NULL)


--C言語プログラムソース--
void Chaining(Data *temp, unsigned int f)
{
    Data *s;
    int no=1;
    s->collision=0;
    
    if(hashtable[f]==NULL){
        hashtable[f]=(Data *)malloc(sizeof(Data));
        *hashtable[f]=*temp;
    }
    else{
        s=hashtable[f];
        while(s->next)
            s=s->next;
        s->next=(Data *)malloc(sizeof(Data));
        *s->next=*temp;
        s->collision+=no;
        no;
        s->next->next=NULL;
    }
}



この投稿にコメントする

削除パスワード

No.3238

Re:ハッシュ法について
投稿者---Hermit(2004/12/17 08:48:34)


Data *s;
int no=1;
s->collision=0;
ここの's'はまだ領域確保してないから
やるんだったら、
temp->collision=0;
だと思います。


この投稿にコメントする

削除パスワード

No.3239

Re:ハッシュ法について
投稿者---まさと(2004/12/17 11:25:48)


> Data *s;
> int no=1;
> s->collision=0;
>ここの's'はまだ領域確保してないから
>やるんだったら、
>temp->collision=0;
>だと思います。
Hermit様、ご返信ありがとうございます。
直してみましたが、状況は変わりません。


この投稿にコメントする

削除パスワード

No.3240

Re:ハッシュ法について
投稿者---Hermit(2004/12/17 12:59:54)


ああ、そうですね。
もう一個抜けてますね。

    else{
        s=hashtable[f];
        while(s->next)
            s=s->next;
        s->next=(Data *)malloc(sizeof(Data));
        *s->next=*temp;
        s->next->collision+=no; //ここも
        s->next->next=NULL;

多分、これで、衝突があった後は、すべて1に設定できると思います。



この投稿にコメントする

削除パスワード

No.3241

Re:ハッシュ法について
投稿者---まさと(2004/12/17 15:12:34)


>ああ、そうですね。
>もう一個抜けてますね。
>
早速の返信ありがとうございます。
1回目の衝突の際は、「1回衝突」と出力されるのですが、2回目の衝突の際も「2回衝突」ではなくて、「1回衝突」と出力されてしまいます。
同じく3回目も「1回衝突」と出力されてしまいます。
力不足で誠に申し訳なく思っております


この投稿にコメントする

削除パスワード

No.3242

Re:ハッシュ法について
投稿者---Hermit(2004/12/17 16:42:28)



s->next->collision = s->collision + 1;

でいいんじゃないでしょうか。

ついでに、
malloc されて、迷子になってるメモリーエリアもどうにかしましょう。
もう、あかまさんが書いてるけど。


この投稿にコメントする

削除パスワード

No.3243

Re:ハッシュ法について
投稿者---Hermit(2004/12/17 20:22:05)


>ついでに、
>malloc されて、迷子になってるメモリーエリアもどうにかしましょう。
>もう、あかまさんが書いてるけど。

あ、呼び出しもとの free は、まだ残っているからいいのかな?
でも、ちょっと冗長です。


この投稿にコメントする

削除パスワード

No.3244

Re:ハッシュ法について
投稿者---まさと(2004/12/17 20:33:41)


皆様方、大変ご迷惑をおかけして誠に申し訳ございませんでした。
皆様からいろいろと御教授いただき、大変ありがたく思っております。
一応完成した、ハッシュ法(チェイン法)のプログラムです。
データも無事、格納されました。
また、現在ハッシュ法のオープンアドレス法のプログラムも作成しておりますが、
こちらのほうが難しいですね、苦労しております。
このプログラムを利用して、作成する方法とはあるのでしょうか?
/* ハッシュ法 */
/* ハッシュ関数:除算法(division method) */

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

#define HashSize 200    /*ハッシュ表のサイズ(大きさ)*/

/*ハッシュ表に格納するデータを表す構造体*/
typedef struct cell{
    char name[30];    /*名前*/
    int collision;    /*衝突回数*/
    struct cell *next;  /*次のセルへのポインタ*/
} Data;

Data *hashtable[HashSize];    /*ハッシュ表*/
FILE *fp;

void MakeHashTable(void);      /*ハッシュ表を初期化する*/
void Chaining(Data *, unsigned int);
unsigned int Hash(char *);    /*ハッシュ関数*/
void PrintAllData(void);        /*ハッシュ表の中身を出力*/
void FreeHashTable(void);      /*ハッシュ表を後始末*/

/*ハッシュ表を初期化する*/
void MakeHashTable()
{
    Data *temp;
    int i;
    
    /*ハッシュ表を初期化*/
    for(i=0; i<HashSize; i++)
        hashtable[i]=NULL;
        
    if((fp=fopen("word.txt", "r"))==NULL){
        printf("ファイルを開く事が出来ません。\n");
        exit(1);
    }
    
    for(;;){
        temp=(Data *)malloc(sizeof(Data));  /*大きさがDataバイトの領域を確保*/
        /*ここから自信がない*/
        if(fscanf(fp, "%s", temp->name)!=EOF){
            fscanf(fp, "%s", temp->name);
            temp->next=NULL;
            Chaining(temp, Hash(temp->name));
            free(temp);
        }
        else{
            free(temp);
            break;
        }
    }
}

void Chaining(Data *temp, unsigned int f)
{
    Data *s;
    int no=1;
    temp->collision=0;
    
    if(hashtable[f]==NULL){
        hashtable[f]=(Data *)malloc(sizeof(Data));
        *hashtable[f]=*temp;                }
    else{
        s=hashtable[f];
        while(s->next)
            s=s->next;
            no++;
        s->next=(Data *)malloc(sizeof(Data));
        *s->next=*temp;    
        s->next->collision=s->collision+1;
        s->next->next=NULL;
    }
}

/*ハッシュ関数(除算法)*/
unsigned int Hash(char *buf)
{
    unsigned int value;

    for(value=0; *buf!='\0'; buf++)
        value=*buf+value*11;
    return(value%HashSize); /*valueをHashSizeで割った剰余(valueとHashSizeは整数でなければならない)*/
}

/*ハッシュ表の中身を出力*/
void PrintAllData(void)
{
    Data *s;
    FILE *fp;
    int i;

    fp=fopen("output(division method)200_100.txt", "w");
    for(i=0; i<HashSize; i++){
        printf("[%d]\t", i);
        s=hashtable[i];
        while(s){
            printf("%-16s(%4d回衝突)\t -> ", s->name, s->collision);
            fprintf(fp, "[%d] %-16s(%4d回衝突)\t -> ", i, s->name, s->collision);
            s=s->next;
        }
        printf("(NULL)\n");
        fprintf(fp, "[%d] (NULL)\n", i);
    }
    fclose(fp);
}


/*ハッシュ表を後始末*/
void FreeHashTable(void)
{
    int i;
    Data *s, *t;

    for(i=0; i<HashSize; i++){
        s=hashtable[i];
        while(s){
            t=s->next;
            free(s);
            s=t;
        }
    }
}

int main(void)
{
    MakeHashTable();
    PrintAllData();
    FreeHashTable();
    fclose(fp);
    return(0);
}



この投稿にコメントする

削除パスワード

No.3245

Re:ハッシュ法について
投稿者---Hermit(2004/12/17 21:53:54)


あかまさんのコメントがわかってないようですね。
word.txt中の一行目
rejoice
は、出力されたデーター中に出てきますか?


この投稿にコメントする

削除パスワード

No.3246

Re:ハッシュ法について
投稿者---まさと(2004/12/17 23:27:10)


>あかまさんのコメントがわかってないようですね。
>word.txt中の一行目
>rejoice
>は、出力されたデーター中に出てきますか?

誠に申し訳御座いません。
訂正前のソースを貼り付けてしまいました。
正しくは、こちらです。

/* ハッシュ法 */
/* ハッシュ関数:除算法(division method) */

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

#define HashSize 10 /*ハッシュ表のサイズ(大きさ)   <<サイズを変更する>>  */

/*ハッシュ表に格納するデータを表す構造体*/
typedef struct cell{
    char name[20];    /*名前*/
    int collision;    /*衝突回数*/
    int datasum;        /*データ数*/
    struct cell *next;  /*次のセルへのポインタ*/
} Data;

Data *hashtable[HashSize];    /*ハッシュ表*/
FILE *fp;

void MakeHashTable(void);      /*ハッシュ表を初期化する*/
void Chaining(Data *, unsigned int);
unsigned int Hash(char *);    /*ハッシュ関数*/
void PrintAllData(void);        /*ハッシュ表の中身を出力*/
void FreeHashTable(void);      /*ハッシュ表を後始末*/

/*ハッシュ表を初期化する*/
void MakeHashTable()
{
    Data *temp;
    int i;
    
    /*ハッシュ表を初期化*/
    for(i=0; i<HashSize; i++)
        hashtable[i]=NULL;
        
    if((fp=fopen("wordx.txt", "r"))==NULL){
        printf("ファイルを開く事が出来ません。\n");
        exit(1);
    }
    
    for(;;){
        temp=(Data *)malloc(sizeof(Data));  /*大きさがDataバイトの領域を確保*/
        if(fscanf(fp, "%s", temp->name)!=EOF){
           
            temp->next=NULL;
            Chaining(temp, Hash(temp->name));
            
        }
        else{
            free(temp);
            break;
        }
    }
}

void Chaining(Data *temp, unsigned int f)
{
    Data *s;
    int no=1;
    temp->collision=0;
    temp->datasum=1;
    
    if(hashtable[f]==NULL){
        
        hashtable[f]=temp;
    }
    else{
        s=hashtable[f];
        while(s->next)
            s=s->next;
            no++;
        
        s->next=temp;
        s->next->collision=s->collision+1;
        s->next->datasum=s->datasum+1;
        
    }
}

/*ハッシュ関数(除算法)*/
unsigned int Hash(char *buf)
{
    unsigned int value;

    for(value=0; *buf!='\0'; buf++)
        value=*buf+value*11;
    return(value%HashSize); /*valueをHashSizeで割った剰余(valueとHashSizeは整数でなければならない)*/
}

/*ハッシュ表の中身を出力*/
void PrintAllData(void)
{
    Data *s;
    FILE *datafp;
    FILE *fp;
    int i;

    datafp=fopen("chain(division).txt", "w");   /*全データ&衝突回数を新規ファイルに出力 <<ファイル名を変更する>> */
    fp=fopen("collision(division).txt", "w");   /*衝突回数を新規ファイルに出力 <<ファイル名を変更する>> */
    for(i=0; i<HashSize; i++){
        printf("[%d]\t", i);
        s=hashtable[i];
        while(s){
            printf("%-16s:%d回衝突\t->", s->name, s->collision);
            fprintf(datafp, "[%d]%-16s:%d回衝突\t->", i, s->name, s->collision);
            fprintf(fp, "[%d]%d回衝突(データ数%d) ->", i, s->collision, s->datasum);
            s=s->next;
        }
        printf("NULL\n");
        fprintf(datafp, "[%d]NULL\n", i);
        fprintf(fp, "[%d]\n", i);
    }
    fclose(datafp);
    fclose(fp);
}


/*ハッシュ表を後始末*/
void FreeHashTable(void)
{
    int i;
    Data *s, *t;

    for(i=0; i<HashSize; i++){
        s=hashtable[i];
        while(s){
            t=s->next;
            free(s);
            s=t;
        }
    }
}

int main(void)
{
    MakeHashTable();
    PrintAllData();
    FreeHashTable();
    fclose(fp);
    return(0);
}



この投稿にコメントする

削除パスワード

No.3247

Re:ハッシュ法について
投稿者---まさと(2004/12/18 16:31:20)


先日は、皆様からたくさんのアドバイスを頂き誠にありがとう御座いました。

現在、ハッシュ法のプログラムを用いて、Excelにハッシュ表の各要素に格納されているデータ数を表示させるために、”heihoucoll997_900.xls”を用いています。Excelに出力されたファイルの画面で、以下のように表示されます。

/* --ハッシュ表の各要素のデータ数-- */
1 /*[745(例)]にデータが1つ格納されている*/
1
12
123 /*[748(例)]にデータが3つ格納されている*/
1
123456 /*[750(例)]にデータが6つ格納されている*/

つまり、末尾のノードまで各ノードの個数を数えてしまいます。目的としている、出力画面を以下のように行いたいのです。

/*目的としている出力画面*/
1 /*データが1つ格納されている*/
1
2 /*データが2つ格納されている*/
3 /*データが3つ格納されている*/
1
6   /*データが6つ格納されている*/

このように、末尾ノードだけを参照して、
各要素のノードのデータ数を出力するためには、
どのようにプログラムを改良すればいいのでしょうか?

/* --現在のプログラムソース-- */
/* ハッシュ法:チェイン法) */
/* ハッシュ関数:平方採中法(mid-square method) */

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

#define HashSize 997    /*ハッシュ表のサイズ(大きさ)   <<サイズを変更する>>  */

/*ハッシュ表に格納するデータを表す構造体*/
typedef struct cell{
    char name[20];    /*名前*/
    int collision;    /*衝突回数*/
    int datasum;        /*データ数*/
    struct cell *next;  /*次のセルへのポインタ*/
} Data;

Data *hashtable[HashSize];    /*ハッシュ表*/
FILE *fp;

void MakeHashTable(void);      /*ハッシュ表を初期化する*/
void Chaining(Data *, unsigned int);
unsigned int Hash(char *);    /*ハッシュ関数*/
void PrintAllData(void);        /*ハッシュ表の中身を出力*/
void FreeHashTable(void);      /*ハッシュ表を後始末*/

/*ハッシュ表を初期化する*/
void MakeHashTable()
{
    Data *temp;
    int i;
    
    /*ハッシュ表を初期化*/
    for(i=0; i<HashSize; i++)
        hashtable[i]=NULL;
        
    if((fp=fopen("word900.txt", "r"))==NULL){            /*  <<変更する>>  */
        printf("ファイルを開く事が出来ません。\n");
        exit(1);
    }
    
    for(;;){
        temp=(Data *)malloc(sizeof(Data));  /*大きさがDataバイトの領域を確保*/
        if(fscanf(fp, "%s", temp->name)!=EOF){
            temp->next=NULL;
            Chaining(temp, Hash(temp->name));
        }
        else{
            free(temp);
            break;
        }
    }
}

void Chaining(Data *temp, unsigned int f)
{
    Data *s;
    int no=1;
    temp->collision=0;
    temp->datasum=1;
    
    if(hashtable[f]==NULL){
        hashtable[f]=temp;
    }
    else{
        s=hashtable[f];
        while(s->next)
            s=s->next;
            no++;
        s->next=temp;
        s->next->collision=s->collision+1;
        s->next->datasum=s->datasum+1;
    }
}

/*ハッシュ関数(平方採中法)*/
unsigned int Hash(char *buf)
{
  unsigned int value;
  for(value=0; *buf!='\0'; buf++)
    value=*buf+value*11;
  return ((value*value)/HashSize)%HashSize;
}

/*ハッシュ表の中身を出力*/
void PrintAllData(void)
{
    Data *s;
    FILE *datafp;
    FILE *fp;
    int i;

    datafp=fopen("chain(mid-square)997_900.txt", "w");  /*全データ&衝突回数を新規ファイルに出力 <<ファイル名を変更する>> */
    fp=fopen("heihoucoll997_900.xls", "w"); /*衝突回数を新規ファイルに出力 <<ファイル名を変更する>> */
    for(i=0; i<HashSize; i++){
        printf("[%d]\t", i);
        s=hashtable[i];
        while(s){
            printf("%-16s:%d回衝突\t->", s->name, s->collision);
            fprintf(datafp, "[%d]%-16s:%d回衝突\t->", i, s->name, s->collision);
            fprintf(fp, "%d", s->datasum);
            s=s->next;
        }
        printf("NULL\n");
        fprintf(datafp, "[%d]NULL\n", i);
        fprintf(fp, "\n");
    }
    fclose(datafp);
    fclose(fp);
}


/*ハッシュ表を後始末*/
void FreeHashTable(void)
{
    int i;
    Data *s, *t;

    for(i=0; i<HashSize; i++){
        s=hashtable[i];
        while(s){
            t=s->next;
            free(s);
            s=t;
        }
    }
}

int main(void)
{
    MakeHashTable();
    PrintAllData();
    FreeHashTable();
    fclose(fp);
    return(0);
}



この投稿にコメントする

削除パスワード

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




掲示板提供:Real Integrity