teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

3

構造体の配列を使うための修正を追加

2021/01/13 00:43

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -58,4 +58,74 @@
58
58
  if (q->key == key) { *p = q->next; free(q); return 1; }
59
59
  return 0;
60
60
  }
61
- ```
61
+ ```
62
+ **追記2**
63
+ 連結リストの先頭にダミーノードを置くと、確かに削除処理が簡単になります。
64
+ 質問の現在のコードを次のように修正すると、
65
+ ポインタの配列ではなく構造体の配列でできます。
66
+
67
+ ```diff
68
+ for(i=0; i<BUCKET_SIZE; i++)
69
+ - table->next = NULL;
70
+ + table[i].next = NULL;
71
+ }
72
+
73
+ /* キーの値を二乗してその中央値をとることで均等にしている */
74
+ -  return(s % BUCKET_SIZE);
75
+ + return(s % BUCKET_SIZE);
76
+ }
77
+
78
+ - for(p=&table[hash(key)]; p!=NULL; p=p->next)
79
+ + for (p = table[hash(key)].next; p!=NULL; p=p->next)
80
+ /* キーを持つDATAへのポインタを返す */
81
+ return p;//&p->data;
82
+ - else
83
+ - /* 等しくなければ見つからないとしてNULLを返す*/
84
+ - return NULL;
85
+ - }
86
+ + /* 等しくなければ見つからないとしてNULLを返す*/
87
+ return NULL;
88
+ }
89
+
90
+ p->data=data;//*dataだった
91
+ - p->next=&table[h];
92
+ - table[h]=*p;
93
+ + p->next = table[h].next;
94
+ + table[h].next = p;
95
+ return 1;
96
+ }
97
+
98
+
99
+ h=hash(key);
100
+ - /* そのバケットは空か */
101
+ - if(&table[h] == NULL)
102
+ - return 0;
103
+ - /* リストの先頭のセルが削除すべきデータか? */
104
+ - if(key==table[h].key){
105
+ - p=&table[h];
106
+ - table->next=p->next;//&table[h]=p->next;
107
+ - free(p);
108
+ - /* 削除に成功したら1を返す */
109
+ - return 1;
110
+ - }
111
+ -//構造体配列の場合、ここからの文がなくても削除できる
112
+ - /* リストの二番目以降のセルについて順番にチェックする */
113
+ for(q=&table[h],p=q->next; p!=NULL; q=p,p=p->next){
114
+ if(key==p->key){
115
+ q->next=p->next;
116
+
117
+ for(i = 0; i < BUCKET_SIZE; i++){
118
+ - if(&table[i] != NULL){
119
+ + if(table[i].next != NULL){
120
+ printf("table[%d]",i);
121
+ /* currentをi番目にしておく */
122
+ - current = &table[i];
123
+ + current = table[i].next;
124
+ ```
125
+ `  return(s % BUCKET_SIZE);` は return の前が全角スペースでした。
126
+ 本当にコンパイルできたコードを貼り付けていますか?
127
+ また、コメントが嘘になっています。
128
+
129
+ find の中の else の部分は削除しました。
130
+ delete の中の不要な部分を大きく削除しました。
131
+ hash_print は、ダミーノードの次からを表示します。

2

コードの修正

2021/01/13 00:43

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -54,7 +54,7 @@
54
54
 
55
55
  int delete(int key)
56
56
  {
57
- for (CELL **p = &table[hash(key)], *q; (q = *p) != NULL; p = &q->next)
57
+ for (CELL **p = &table[hash(key)], *q; q = *p; p = &q->next)
58
58
  if (q->key == key) { *p = q->next; free(q); return 1; }
59
59
  return 0;
60
60
  }

1

delete の新たなコードを追加

2021/01/12 16:42

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -45,4 +45,17 @@
45
45
  }
46
46
  }
47
47
  }
48
+ ```
49
+ **追記**
50
+ table をポインタの配列にしたときに、
51
+ リストの先頭と 2番目以降を同等に扱うコードは書けます。
52
+ ```C
53
+ CELL *table[BUCKET_SIZE];
54
+
55
+ int delete(int key)
56
+ {
57
+ for (CELL **p = &table[hash(key)], *q; (q = *p) != NULL; p = &q->next)
58
+ if (q->key == key) { *p = q->next; free(q); return 1; }
59
+ return 0;
60
+ }
48
61
  ```