回答編集履歴
3
構造体の配列を使うための修正を追加
test
CHANGED
|
@@ -119,3 +119,143 @@
|
|
|
119
119
|
}
|
|
120
120
|
|
|
121
121
|
```
|
|
122
|
+
|
|
123
|
+
**追記2**
|
|
124
|
+
|
|
125
|
+
連結リストの先頭にダミーノードを置くと、確かに削除処理が簡単になります。
|
|
126
|
+
|
|
127
|
+
質問の現在のコードを次のように修正すると、
|
|
128
|
+
|
|
129
|
+
ポインタの配列ではなく構造体の配列でできます。
|
|
130
|
+
|
|
131
|
+
|
|
132
|
+
|
|
133
|
+
```diff
|
|
134
|
+
|
|
135
|
+
for(i=0; i<BUCKET_SIZE; i++)
|
|
136
|
+
|
|
137
|
+
- table->next = NULL;
|
|
138
|
+
|
|
139
|
+
+ table[i].next = NULL;
|
|
140
|
+
|
|
141
|
+
}
|
|
142
|
+
|
|
143
|
+
|
|
144
|
+
|
|
145
|
+
/* キーの値を二乗してその中央値をとることで均等にしている */
|
|
146
|
+
|
|
147
|
+
- return(s % BUCKET_SIZE);
|
|
148
|
+
|
|
149
|
+
+ return(s % BUCKET_SIZE);
|
|
150
|
+
|
|
151
|
+
}
|
|
152
|
+
|
|
153
|
+
|
|
154
|
+
|
|
155
|
+
- for(p=&table[hash(key)]; p!=NULL; p=p->next)
|
|
156
|
+
|
|
157
|
+
+ for (p = table[hash(key)].next; p!=NULL; p=p->next)
|
|
158
|
+
|
|
159
|
+
/* キーを持つDATAへのポインタを返す */
|
|
160
|
+
|
|
161
|
+
return p;//&p->data;
|
|
162
|
+
|
|
163
|
+
- else
|
|
164
|
+
|
|
165
|
+
- /* 等しくなければ見つからないとしてNULLを返す*/
|
|
166
|
+
|
|
167
|
+
- return NULL;
|
|
168
|
+
|
|
169
|
+
- }
|
|
170
|
+
|
|
171
|
+
+ /* 等しくなければ見つからないとしてNULLを返す*/
|
|
172
|
+
|
|
173
|
+
return NULL;
|
|
174
|
+
|
|
175
|
+
}
|
|
176
|
+
|
|
177
|
+
|
|
178
|
+
|
|
179
|
+
p->data=data;//*dataだった
|
|
180
|
+
|
|
181
|
+
- p->next=&table[h];
|
|
182
|
+
|
|
183
|
+
- table[h]=*p;
|
|
184
|
+
|
|
185
|
+
+ p->next = table[h].next;
|
|
186
|
+
|
|
187
|
+
+ table[h].next = p;
|
|
188
|
+
|
|
189
|
+
return 1;
|
|
190
|
+
|
|
191
|
+
}
|
|
192
|
+
|
|
193
|
+
|
|
194
|
+
|
|
195
|
+
|
|
196
|
+
|
|
197
|
+
h=hash(key);
|
|
198
|
+
|
|
199
|
+
- /* そのバケットは空か */
|
|
200
|
+
|
|
201
|
+
- if(&table[h] == NULL)
|
|
202
|
+
|
|
203
|
+
- return 0;
|
|
204
|
+
|
|
205
|
+
- /* リストの先頭のセルが削除すべきデータか？ */
|
|
206
|
+
|
|
207
|
+
- if(key==table[h].key){
|
|
208
|
+
|
|
209
|
+
- p=&table[h];
|
|
210
|
+
|
|
211
|
+
- table->next=p->next;//&table[h]=p->next;
|
|
212
|
+
|
|
213
|
+
- free(p);
|
|
214
|
+
|
|
215
|
+
- /* 削除に成功したら1を返す */
|
|
216
|
+
|
|
217
|
+
- return 1;
|
|
218
|
+
|
|
219
|
+
- }
|
|
220
|
+
|
|
221
|
+
-//構造体配列の場合、ここからの文がなくても削除できる
|
|
222
|
+
|
|
223
|
+
- /* リストの二番目以降のセルについて順番にチェックする */
|
|
224
|
+
|
|
225
|
+
for(q=&table[h],p=q->next; p!=NULL; q=p,p=p->next){
|
|
226
|
+
|
|
227
|
+
if(key==p->key){
|
|
228
|
+
|
|
229
|
+
q->next=p->next;
|
|
230
|
+
|
|
231
|
+
|
|
232
|
+
|
|
233
|
+
for(i = 0; i < BUCKET_SIZE; i++){
|
|
234
|
+
|
|
235
|
+
- if(&table[i] != NULL){
|
|
236
|
+
|
|
237
|
+
+ if(table[i].next != NULL){
|
|
238
|
+
|
|
239
|
+
printf("table[%d]",i);
|
|
240
|
+
|
|
241
|
+
/* currentをi番目にしておく */
|
|
242
|
+
|
|
243
|
+
- current = &table[i];
|
|
244
|
+
|
|
245
|
+
+ current = table[i].next;
|
|
246
|
+
|
|
247
|
+
```
|
|
248
|
+
|
|
249
|
+
` return(s % BUCKET_SIZE);` は return の前が全角スペースでした。
|
|
250
|
+
|
|
251
|
+
本当にコンパイルできたコードを貼り付けていますか？
|
|
252
|
+
|
|
253
|
+
また、コメントが嘘になっています。
|
|
254
|
+
|
|
255
|
+
|
|
256
|
+
|
|
257
|
+
find の中の else の部分は削除しました。
|
|
258
|
+
|
|
259
|
+
delete の中の不要な部分を大きく削除しました。
|
|
260
|
+
|
|
261
|
+
hash_print は、ダミーノードの次からを表示します。
|
2
コードの修正
test
CHANGED
|
@@ -110,7 +110,7 @@
|
|
|
110
110
|
|
|
111
111
|
{
|
|
112
112
|
|
|
113
|
-
for (CELL **p = &table[hash(key)], *q;
|
|
113
|
+
for (CELL **p = &table[hash(key)], *q; q = *p; p = &q->next)
|
|
114
114
|
|
|
115
115
|
if (q->key == key) { *p = q->next; free(q); return 1; }
|
|
116
116
|
|
1
delete の新たなコードを追加
test
CHANGED
|
@@ -93,3 +93,29 @@
|
|
|
93
93
|
}
|
|
94
94
|
|
|
95
95
|
```
|
|
96
|
+
|
|
97
|
+
**追記**
|
|
98
|
+
|
|
99
|
+
table をポインタの配列にしたときに、
|
|
100
|
+
|
|
101
|
+
リストの先頭と 2番目以降を同等に扱うコードは書けます。
|
|
102
|
+
|
|
103
|
+
```C
|
|
104
|
+
|
|
105
|
+
CELL *table[BUCKET_SIZE];
|
|
106
|
+
|
|
107
|
+
|
|
108
|
+
|
|
109
|
+
int delete(int key)
|
|
110
|
+
|
|
111
|
+
{
|
|
112
|
+
|
|
113
|
+
for (CELL **p = &table[hash(key)], *q; (q = *p) != NULL; p = &q->next)
|
|
114
|
+
|
|
115
|
+
if (q->key == key) { *p = q->next; free(q); return 1; }
|
|
116
|
+
|
|
117
|
+
return 0;
|
|
118
|
+
|
|
119
|
+
}
|
|
120
|
+
|
|
121
|
+
```
|