C言語とC++言語コミュのハッシュテーブルについて

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

typedef struct PERSON{
char name[30];
struct PERSON *next;
}PERSON;

int hash(char n);

int main(void) {
int menu;
PERSON *hashtable[10];

while(1) {

printf("なにをしますか？\n");
printf("%d : 追加、", 1);
printf("%d : 表示、", 2);
printf("%d : 終了", 3);
scanf("%d\n", &menu);

switch (menu) {

case 1:
add( ( 1 ) );
break;

case 2:
display( ( 2 ) );
break;

case 3:
return 0;
}
}
}

void add(PERSON ( 3 ) ){

PERSON *p;
int n;

p = (PERSON *)malloc(sizeof(PERSON));
if (p == NULL) {
exit(0);
}
printf("名前を入力してください\n");
scanf("%s\n", p->name);

p->next = NULL;
n = hash(p->name);

if(table[n] != NULL){
table[n]->next = p;
table[n] = table[n]->next;
return 0;
}
table[n] = p;
return 0;
}

void display(PERSON ( 4 ) ){
PERSON *p[10];
int count;
p = table;

while(count<10){
while(p[count] != NULL){
printf("%s\n",p[count]->name);
p[count]=p[count]->next;
}
}
}

int hash(char n){
return n % 10;
}

上記の（１～４）に変数やポインタを記入して、
関数add内でmain文のhashtableにデータ追加し、
関数displayでhashtableのデータを表示していくチェイン法のハッシュテーブルを作りたいです（３、４の仮引数を記入することで、関数内のコードを変えてもかまいません）
配列のポインタを関数内で更新していく方法が知りたいので、
配列のポインタと関数の件で助言をお願いします。

１でhashtableをいれてhashtable[10]の先頭のアドレスをいれると思うのですが、仮引数にあたる３が全然わかりません。配列がないければ*tableだと思うのですが、今回は配列のデータを変更するので、これで当たっているかわかりません。
あと、他もいろいろ間違っていると思うでお願いします。

コメント(11)

最初
全て
最新の40件

[1] mixiユーザー 11月10日 17:29

>上記の（１～４）に変数やポインタを記入して、
<　?とか使ったほうが穴埋め問題として認識しやすいかもと・・・なんだろこのコードと思ったので・・・

>１でhashtableをいれてhashtable[10]の先頭のアドレスをいれると思うのですが、仮引数にあたる３が全然わかりません
<?、?は解決して?がわからないでいいのかな？？

?はadd関数内に突然出てきているこいつです。
if(table[n] != NULL){　　　　　　　　 <=
?もこの原理で見つけれると思います。

久しぶりにCコード見てみようかな程度なので間違ってたらごめんなさい。
＠インデントはしてほしい・・・。＠行番号書いてあると教えやすいかも・・・。

[2] mixiユーザー 11月11日 08:38

＞肉さん
返信ありがとうございます。
一応インデントとして行番号を書いてみました

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct PERSON{
5 char name[30];
6 struct PERSON *next;
7}PERSON;
8
9int add(PERSON *table[]);
10void display(PERSON *table[]);
11int hash(char n);
12
13int main(void) {
14 int menu;
15 PERSON *hashtable[10];
16
17 while(1) {
18
19 printf("なにをしますか？\n");
20 printf("%d : 追加、", 1);
21 printf("%d : 表示、", 2);
22 printf("%d : 終了", 3);
23
24 printf(" > ");
25 scanf("%d", &menu);
26 printf("\n");
27
28 switch (menu) {
29
30 case 1:
31 add(hashtable);
32 break;
33
34 case 2:
35 display(hashtable);
36 break;
37
38 case 3:
39 printf("終了します");
40 return 0;
41 }
42 }
43}
44
45int add(PERSON *table[]){
46
47 PERSON *p;
48 int n;
49
50 p = (PERSON *)malloc(sizeof(PERSON));
51 if (p == NULL) {
52 exit(0);
53 }
54 printf("名前を入力してください\n");
55 scanf("%s\n", p->name);
56 p->next = NULL;
57 n = hash(*p->name);
58
59 if(table[n] != NULL){
60 table[n]->next = p;
61 table[n] = table[n]->next;
62 return 0;
63 }
64 table[n] = p;
65 return 0;
66}
67
68void display(PERSON *table[]){
69
70 PERSON *p[10];
71 int count;
72 *p = *table;
73
74 while(count<10){
75 while(p[count] != NULL){
76 printf("%s\n",p[count]->name);
77 p[count]=p[count]->next;
78 }
79 }
80}
81
82
83int hash(char n){
84 return n % 10;
85}

一応、このようにいれたらコンパイルエラーがなくなったのですが、
関数addでデータを入れるとたまにエラーが発生したり、display関数でうまくデータを表示できません。何か間違っているか教えてくれませんか？

[4] mixiユーザー 11月11日 20:51

>たけちゃんさん
コンパイルエラーやバグとは関係ないですけど

構造体PERSONのnameはchar name[30]で定義されていますよね。

んで，add関数の中では

printf("名前を入力してください\n");
scanf("%s\n", p->name);

でnameを入力させているのにhash関数ではchar nで受け取っているの微妙じゃないですか？文字列が渡されるので，hash関数の仮引数はchar *nにして，ハッシュ計算の部分はreturn *n % 10になるんじゃないかと思います。

でもこの場合でも，ハッシュ計算を文字列の1文字目でやるようにしかならないので，ハッシュの役目を果たしているのかは微妙ですよね。

[5] mixiユーザー 11月12日 03:29

>鏡乃さん
ご助言ありがとうございます。
ひとまず、追加からトレースした結果、ミスを発見しました。
しかし、どのようにコーティングすれば、修正できるかわからないので
できれば教えてもらえないでしょうか？

テーブルにデータがない時は

if (table[n] == NULL) {

table[n] = p;
}
ですが、
データがあり、衝突する場合、
つまり、
if (table[n] != NULL) {
の場合、チェーンを作りたいのですが、
どのようなコードにすればいいかわかりません。

＞masutaroさん
今回は、名前の１文字目をもとに値を得るハッシュ関数を作っています。

[6] mixiユーザー 11月12日 08:54

チェーンの並び順を気にしていないのなら
先頭に追加↓するのが楽かと。

p->next = table[n];
table[n] = p;

[7] mixiユーザー 11月12日 09:34

>たけちゃんさん
あ，そっか。何か1人で勝手にaddに1文字しか渡さないんだったらPERSONのnameをchar name[30]で作る必要ないのではとか考えてしまってた。

ぜんぜん微妙ってことはないんだ。すみません＞＜

[9] mixiユーザー 11月12日 20:53

>επιστημηさん、鏡乃さん
教えて頂いてとても助かりました。
おかげで関数addが完成しました。
この流れで関数displayもトレースした結果、うまく作ることができました。

void display(PERSON *table[]){

PERSON *p[10];
int count;

for(count = 0; count < 10; count ++) {

p[count] = table[count];
}

　　　　　・・・・
}

という形をとって各テーブルのアドレスを代入して処理すれば
うまく処理できることがわかりました。
しかし、仮にテーブルの数が多いと処理にすごく時間かかってしまうのでは
と思うのですが、これで良いと思いますか？
それとも他になにか良い方法があるのでしょうか？
よろしければ教えて頂けないでしょうか？

[11] mixiユーザー 11月14日 01:23

>鏡乃さん
返信ありがとうございます。
おかげで完成しました。
本当に助かりました。

ログインすると、みんなのコメントがもっと見れるよ