質問編集履歴
2
内容修正
test
CHANGED
File without changes
|
test
CHANGED
@@ -10,11 +10,13 @@
|
|
10
10
|
|
11
11
|
pen
|
12
12
|
|
13
|
-
この上のものにあたります
|
13
|
+
この上のものにあたります
|
14
|
+
|
14
|
-
|
15
|
+
このソースコードを実行した結果,すべての英文が表示されないという現象が起きたのですが何が原因なのでしょうか
|
16
|
+
|
17
|
+
読み込むファイルとしてこちらを使用しました
|
18
|
+
|
15
|
-
|
19
|
+
[リンク内容](https://rprjie.meijo-u.ac.jp/lectures/ProgIII/code/8/input1.txt)
|
16
|
-
|
17
|
-
|
18
20
|
|
19
21
|
hash.h
|
20
22
|
|
@@ -592,7 +594,7 @@
|
|
592
594
|
|
593
595
|
while (n != NULL) {
|
594
596
|
|
595
|
-
printf("%s => %d\n",
|
597
|
+
printf("%s => %d\n", n->key, n->value);
|
596
598
|
|
597
599
|
n = n->next;
|
598
600
|
|
1
本文変更
test
CHANGED
File without changes
|
test
CHANGED
@@ -1,3 +1,679 @@
|
|
1
1
|
ある英文が与えられたファイルがあり,それを所有格や空白記号類を削除し単語一つ一つを改行して表示していくプログラムを考えています.
|
2
2
|
|
3
|
+
実行結果の例としては This is a pen.
|
4
|
+
|
5
|
+
this
|
6
|
+
|
7
|
+
is
|
8
|
+
|
9
|
+
a
|
10
|
+
|
11
|
+
pen
|
12
|
+
|
13
|
+
この上のものにあたります.
|
14
|
+
|
15
|
+
これらを下記のソースコードとヘッダファイルから作成したのですが、ハッシュ表の内容を表示する関数でアクセス違反が起きてしまいます.どのようにすればよいでしょうか.また、メイン関数でファイルの処理などを行っていますがそれをファイルというモジュールにできる方法もありましたら教えていただけると助かります.
|
16
|
+
|
17
|
+
|
18
|
+
|
19
|
+
hash.h
|
20
|
+
|
21
|
+
/*
|
22
|
+
|
23
|
+
* hash.h: ハッシュ表の型とその操作用関数のヘッダファイル
|
24
|
+
|
25
|
+
* (ハッシュ表のキー:文字列,値:非負の整数)
|
26
|
+
|
27
|
+
*/
|
28
|
+
|
29
|
+
#ifndef HASH_H
|
30
|
+
|
31
|
+
#define HASH_H
|
32
|
+
|
33
|
+
|
34
|
+
|
35
|
+
#include <assert.h>
|
36
|
+
|
37
|
+
#include <stdio.h>
|
38
|
+
|
39
|
+
#include <stdlib.h>
|
40
|
+
|
41
|
+
#include <string.h>
|
42
|
+
|
43
|
+
|
44
|
+
|
45
|
+
/* ハッシュ表とそのポインタの型 */
|
46
|
+
|
47
|
+
typedef struct hashtable HashTable;
|
48
|
+
|
49
|
+
typedef HashTable *HashTablePtr;
|
50
|
+
|
51
|
+
|
52
|
+
|
53
|
+
/* ハッシュ表を一つ生成し,そのポインタを返す.*/
|
54
|
+
|
55
|
+
HashTablePtr create_hashtable(void);
|
56
|
+
|
57
|
+
|
58
|
+
|
59
|
+
/* ハッシュ表の削除を行う.*/
|
60
|
+
|
61
|
+
#define delete_hashtable(t) (delete_hashtable0(t),t=NULL)
|
62
|
+
|
63
|
+
void delete_hashtable0(HashTablePtr t);
|
64
|
+
|
65
|
+
|
66
|
+
|
67
|
+
/* ハッシュ表 t に登録されているキーと値のペアの数を返す.*/
|
68
|
+
|
69
|
+
int get_cardinality(HashTablePtr t);
|
70
|
+
|
71
|
+
|
72
|
+
|
73
|
+
/* ハッシュ表 t にてキー key が登録されていれば1, されていなければ0を返す.*/
|
74
|
+
|
75
|
+
int has_key(HashTablePtr t, char *key);
|
76
|
+
|
77
|
+
|
78
|
+
|
79
|
+
/* ハッシュ表 t にてキー key に対応する値を返す.
|
80
|
+
|
81
|
+
* (値が見つからなかったら -1 を返す)
|
82
|
+
|
83
|
+
*/
|
84
|
+
|
85
|
+
int lookup(HashTablePtr t, char *key);
|
86
|
+
|
87
|
+
|
88
|
+
|
89
|
+
/* キー key と正の整数値 value のペアをハッシュ表 t に登録し,その通し番号を返す.*/
|
90
|
+
|
91
|
+
int enter(HashTablePtr t, char *key, int value);
|
92
|
+
|
93
|
+
|
94
|
+
|
95
|
+
/* ハッシュ表 t に登録されるキーの配列を返す.
|
96
|
+
|
97
|
+
* 返ってきた配列は後で free() する必要がある.
|
98
|
+
|
99
|
+
*/
|
100
|
+
|
101
|
+
char **get_keys(HashTablePtr t);
|
102
|
+
|
103
|
+
|
104
|
+
|
105
|
+
/* ハッシュ表の内容を表示する.*/
|
106
|
+
|
107
|
+
void print_hashtable(HashTablePtr t);
|
108
|
+
|
109
|
+
|
110
|
+
|
111
|
+
#endif
|
112
|
+
|
113
|
+
|
114
|
+
|
115
|
+
hash.c
|
116
|
+
|
117
|
+
/*
|
118
|
+
|
119
|
+
* hash.c: ハッシュ表の型とその操作用関数の定義
|
120
|
+
|
121
|
+
* (ハッシュ表のキー:文字列,値:非負の整数)
|
122
|
+
|
123
|
+
*/
|
124
|
+
|
125
|
+
#include "hash.h"
|
126
|
+
|
127
|
+
|
128
|
+
|
129
|
+
#define HASH_SIZE 997 /* ハッシュ表の内部配列のサイズ */
|
130
|
+
|
131
|
+
#define HASH_RADIX 97 /* ハッシュ関数用の基数 */
|
132
|
+
|
133
|
+
|
134
|
+
|
135
|
+
/* ハッシュ表内の連結リストに含まれるノードとそのポインタの型. */
|
136
|
+
|
137
|
+
typedef struct hash_node HashNode;
|
138
|
+
|
139
|
+
typedef HashNode *HashNodePtr;
|
140
|
+
|
141
|
+
|
142
|
+
|
143
|
+
/* ハッシュ表内の連結リストに含まれるノードの構造体. */
|
144
|
+
|
145
|
+
struct hash_node { /* ハッシュ表内の連結リストのノード */
|
146
|
+
|
147
|
+
char *key; /* キー */
|
148
|
+
|
149
|
+
int value; /* キーに対応する値 */
|
150
|
+
|
151
|
+
int id; /* キーに付与された通し番号 */
|
152
|
+
|
153
|
+
struct hash_node *next; /* 次のノードへのポインタ */
|
154
|
+
|
155
|
+
};
|
156
|
+
|
157
|
+
|
158
|
+
|
159
|
+
/* ハッシュ表の構造体. */
|
160
|
+
|
161
|
+
struct hashtable {
|
162
|
+
|
163
|
+
HashNodePtr *heads; /* 内部配列 */
|
164
|
+
|
165
|
+
int serial_id; /* 通し番号管理用の変数 */
|
166
|
+
|
167
|
+
int size; /* 内部配列のサイズ */
|
168
|
+
|
169
|
+
};
|
170
|
+
|
171
|
+
|
172
|
+
|
173
|
+
/* static 関数のプロトタイプ宣言 */
|
174
|
+
|
175
|
+
static unsigned int hash(char *s);
|
176
|
+
|
177
|
+
static int get_index(HashTablePtr t, char *key);
|
178
|
+
|
179
|
+
|
180
|
+
|
181
|
+
/* 文字列 s のハッシュ値を計算する. */
|
182
|
+
|
183
|
+
static unsigned int hash(char *s) {
|
184
|
+
|
185
|
+
unsigned int v;
|
186
|
+
|
187
|
+
|
188
|
+
|
189
|
+
v = 0;
|
190
|
+
|
191
|
+
while (*s != '\0') {
|
192
|
+
|
193
|
+
v = v * HASH_RADIX + *s;
|
194
|
+
|
195
|
+
s++;
|
196
|
+
|
197
|
+
}
|
198
|
+
|
199
|
+
|
200
|
+
|
201
|
+
return v;
|
202
|
+
|
203
|
+
}
|
204
|
+
|
205
|
+
|
206
|
+
|
207
|
+
/* ハッシュ表を一つ生成し,そのポインタを返す.*/
|
208
|
+
|
209
|
+
HashTablePtr create_hashtable(void) {
|
210
|
+
|
211
|
+
HashTablePtr t = NULL;
|
212
|
+
|
213
|
+
int i;
|
214
|
+
|
215
|
+
|
216
|
+
|
217
|
+
t = malloc(sizeof(HashTable));
|
218
|
+
|
219
|
+
if (t == NULL) {
|
220
|
+
|
221
|
+
fprintf(stderr, "Couldn't allocate memory for a hashtable\n");
|
222
|
+
|
223
|
+
exit(EXIT_FAILURE);
|
224
|
+
|
225
|
+
}
|
226
|
+
|
227
|
+
|
228
|
+
|
229
|
+
t->serial_id = 0;
|
230
|
+
|
231
|
+
t->size = HASH_SIZE;
|
232
|
+
|
233
|
+
t->heads = malloc(sizeof(HashNodePtr) * t->size);
|
234
|
+
|
235
|
+
if (t->heads == NULL) {
|
236
|
+
|
3
|
-
|
237
|
+
fprintf(stderr, "Couldn't allocate memory for a hashtable's header array\n");
|
238
|
+
|
239
|
+
exit(EXIT_FAILURE);
|
240
|
+
|
241
|
+
}
|
242
|
+
|
243
|
+
|
244
|
+
|
245
|
+
/* 各連結リストの先頭要素へのポインタは必ず NULL に初期化する */
|
246
|
+
|
247
|
+
for (i = 0; i < t->size; i++) {
|
248
|
+
|
249
|
+
t->heads[i] = NULL;
|
250
|
+
|
251
|
+
}
|
252
|
+
|
253
|
+
|
254
|
+
|
255
|
+
return t;
|
256
|
+
|
257
|
+
}
|
258
|
+
|
259
|
+
|
260
|
+
|
261
|
+
/* ハッシュ表の実質的な解放作業を行う.
|
262
|
+
|
263
|
+
* (次々と free() するので free() 後の NULL 代入は省略)
|
264
|
+
|
265
|
+
*/
|
266
|
+
|
267
|
+
void delete_hashtable0(HashTablePtr t) {
|
268
|
+
|
269
|
+
HashNodePtr n = NULL, m = NULL;
|
270
|
+
|
271
|
+
int i;
|
272
|
+
|
273
|
+
|
274
|
+
|
275
|
+
/* free() と同様,NULLポインタに対しては何も行わない */
|
276
|
+
|
277
|
+
if (t == NULL) {
|
278
|
+
|
279
|
+
return;
|
280
|
+
|
281
|
+
}
|
282
|
+
|
283
|
+
|
284
|
+
|
285
|
+
/* 各連結リストの領域を解放 */
|
286
|
+
|
287
|
+
for (i = 0; i < t->size; i++) {
|
288
|
+
|
289
|
+
n = t->heads[i];
|
290
|
+
|
291
|
+
while (n != NULL) {
|
292
|
+
|
293
|
+
m = n;
|
294
|
+
|
295
|
+
n = n->next;
|
296
|
+
|
297
|
+
free(m);
|
298
|
+
|
299
|
+
}
|
300
|
+
|
301
|
+
}
|
302
|
+
|
303
|
+
|
304
|
+
|
305
|
+
/* 最後に連結リストの先頭ポインタの領域を解放 */
|
306
|
+
|
307
|
+
free(t->heads);
|
308
|
+
|
309
|
+
free(t);
|
310
|
+
|
311
|
+
}
|
312
|
+
|
313
|
+
|
314
|
+
|
315
|
+
/* ハッシュ表 t に登録されているキーと値のペアの数を返す.*/
|
316
|
+
|
317
|
+
int get_cardinality(HashTablePtr t) {
|
318
|
+
|
319
|
+
assert(t);
|
320
|
+
|
321
|
+
return t->serial_id;
|
322
|
+
|
323
|
+
}
|
324
|
+
|
325
|
+
|
326
|
+
|
327
|
+
/* ハッシュ表 t の内部配列の添え字を返す */
|
328
|
+
|
329
|
+
static int get_index(HashTablePtr t, char *key) {
|
330
|
+
|
331
|
+
return hash(key) % t->size;
|
332
|
+
|
333
|
+
}
|
334
|
+
|
335
|
+
|
336
|
+
|
337
|
+
/* ハッシュ表 t にてキー key が登録されていれば1,
|
338
|
+
|
339
|
+
* されていなければ0を返す.
|
340
|
+
|
341
|
+
*/
|
342
|
+
|
343
|
+
int has_key(HashTablePtr t, char *key) {
|
344
|
+
|
345
|
+
assert(t && key);
|
346
|
+
|
347
|
+
return (lookup(t, key) >= 0) ? 1 : 0;
|
348
|
+
|
349
|
+
}
|
350
|
+
|
351
|
+
|
352
|
+
|
353
|
+
/* ハッシュ表 t にてキー key に対応する値を返す.
|
354
|
+
|
355
|
+
* 値が見つからなかったら -1 を返す.
|
356
|
+
|
357
|
+
* (ハッシュ表の値として登録できるのは非負の整数値と仮定)
|
358
|
+
|
359
|
+
*/
|
360
|
+
|
361
|
+
int lookup(HashTablePtr t, char *key) {
|
362
|
+
|
363
|
+
HashNodePtr n = NULL;
|
364
|
+
|
365
|
+
int index;
|
366
|
+
|
367
|
+
|
368
|
+
|
369
|
+
assert(t && key);
|
370
|
+
|
371
|
+
|
372
|
+
|
373
|
+
/* ハッシュ表の内部配列の添え字を計算 */
|
374
|
+
|
375
|
+
index = get_index(t, key);
|
376
|
+
|
377
|
+
|
378
|
+
|
379
|
+
/* index 番目の連結リストを先頭から順に走査 */
|
380
|
+
|
381
|
+
n = t->heads[index];
|
382
|
+
|
383
|
+
while (n != NULL) {
|
384
|
+
|
385
|
+
/* 引数で指定された key とハッシュ表内のキーが一致したら
|
386
|
+
|
387
|
+
直ちに対応する値を返す */
|
388
|
+
|
389
|
+
if (strcmp(key, n->key) == 0) {
|
390
|
+
|
391
|
+
return n->value;
|
392
|
+
|
393
|
+
}
|
394
|
+
|
395
|
+
|
396
|
+
|
397
|
+
/* 走査を次に進める */
|
398
|
+
|
399
|
+
n = n->next;
|
400
|
+
|
401
|
+
}
|
402
|
+
|
403
|
+
|
404
|
+
|
405
|
+
/* キーが見つからなかったので -1 を返す */
|
406
|
+
|
407
|
+
return -1;
|
408
|
+
|
409
|
+
}
|
410
|
+
|
411
|
+
|
412
|
+
|
413
|
+
/* キー key と値 value のペアをハッシュ表 t に登録し,その通し番号を返す.
|
414
|
+
|
415
|
+
* (値 value は非負であると仮定)
|
416
|
+
|
417
|
+
*/
|
418
|
+
|
419
|
+
int enter(HashTablePtr t, char *key, int value) {
|
420
|
+
|
421
|
+
HashNodePtr n = NULL, m = NULL;
|
422
|
+
|
423
|
+
int index;
|
424
|
+
|
425
|
+
|
426
|
+
|
427
|
+
assert(t && key);
|
428
|
+
|
429
|
+
|
430
|
+
|
431
|
+
/* 仕様上のエラーなので非負の値が渡されたときはメッセージを出す */
|
432
|
+
|
433
|
+
if (value < 0) {
|
434
|
+
|
435
|
+
fprintf(stderr, "Invalid value %d for key %s\n", value, key);
|
436
|
+
|
437
|
+
exit(EXIT_FAILURE);
|
438
|
+
|
439
|
+
}
|
440
|
+
|
441
|
+
|
442
|
+
|
443
|
+
/* 内部配列の添え字を計算 */
|
444
|
+
|
445
|
+
index = get_index(t, key);
|
446
|
+
|
447
|
+
|
448
|
+
|
449
|
+
/* キー key が既に登録されているか探し,
|
450
|
+
|
451
|
+
* 登録されている場合は値を value に更新する.
|
452
|
+
|
453
|
+
*/
|
454
|
+
|
455
|
+
n = t->heads[index]; /* index 番目の head を出発点とする */
|
456
|
+
|
457
|
+
if (n != NULL) {
|
458
|
+
|
459
|
+
while (n != NULL) {
|
460
|
+
|
461
|
+
if (strcmp(key, n->key) == 0) { /* 登録されていた */
|
462
|
+
|
463
|
+
n->value = value; /* 値を更新 */
|
464
|
+
|
465
|
+
return n->id;
|
466
|
+
|
467
|
+
}
|
468
|
+
|
469
|
+
n = n->next;
|
470
|
+
|
471
|
+
}
|
472
|
+
|
473
|
+
}
|
474
|
+
|
475
|
+
|
476
|
+
|
477
|
+
/* 新しいノードを生成 */
|
478
|
+
|
479
|
+
m = malloc(sizeof(HashNode));
|
480
|
+
|
481
|
+
if (m == NULL) {
|
482
|
+
|
483
|
+
fprintf(stderr, "Couldn't allocate memory for a hash node\n");
|
484
|
+
|
485
|
+
exit(EXIT_FAILURE);
|
486
|
+
|
487
|
+
}
|
488
|
+
|
489
|
+
|
490
|
+
|
491
|
+
m->key = _strdup(key);
|
492
|
+
|
493
|
+
m->id = t->serial_id;
|
494
|
+
|
495
|
+
m->value = value;
|
496
|
+
|
497
|
+
|
498
|
+
|
499
|
+
/* 新しいノードを先頭に挿入 */
|
500
|
+
|
501
|
+
m->next = t->heads[index];
|
502
|
+
|
503
|
+
t->heads[index] = m;
|
504
|
+
|
505
|
+
|
506
|
+
|
507
|
+
t->serial_id++; /* 次の通し番号に更新 */
|
508
|
+
|
509
|
+
|
510
|
+
|
511
|
+
return m->id; /* 登録したキーと値のペアに付与された通し番号を返す */
|
512
|
+
|
513
|
+
}
|
514
|
+
|
515
|
+
|
516
|
+
|
517
|
+
/*
|
518
|
+
|
519
|
+
* ハッシュ表 t に登録されるキーの配列を返す.
|
520
|
+
|
521
|
+
*(この配列のサイズは get_hash_cardinality() で取得可能)
|
522
|
+
|
523
|
+
*/
|
524
|
+
|
525
|
+
char **get_keys(HashTablePtr t) {
|
526
|
+
|
527
|
+
char **keys = NULL;
|
528
|
+
|
529
|
+
HashNodePtr n;
|
530
|
+
|
531
|
+
int i;
|
532
|
+
|
533
|
+
|
534
|
+
|
535
|
+
assert(t);
|
536
|
+
|
537
|
+
|
538
|
+
|
539
|
+
keys = malloc(sizeof(char *) * t->serial_id);
|
540
|
+
|
541
|
+
if (keys == NULL) {
|
542
|
+
|
543
|
+
fprintf(stderr, "Couldn't allocate memory for hashtable keys\n");
|
544
|
+
|
545
|
+
exit(EXIT_FAILURE);
|
546
|
+
|
547
|
+
}
|
548
|
+
|
549
|
+
|
550
|
+
|
551
|
+
/* 各連結リストを走査し,配列に詰め込む */
|
552
|
+
|
553
|
+
for (i = 0; i < t->size; i++) {
|
554
|
+
|
555
|
+
n = t->heads[i];
|
556
|
+
|
557
|
+
while (n != NULL) {
|
558
|
+
|
559
|
+
keys[n->id] = n->key; /* 通し番号を配列添え字に */
|
560
|
+
|
561
|
+
n = n->next;
|
562
|
+
|
563
|
+
}
|
564
|
+
|
565
|
+
}
|
566
|
+
|
567
|
+
|
568
|
+
|
569
|
+
return keys; /* 後で free() する必要あり */
|
570
|
+
|
571
|
+
}
|
572
|
+
|
573
|
+
|
574
|
+
|
575
|
+
/* ハッシュ表の内容を表示する.*/
|
576
|
+
|
577
|
+
void print_hashtable(HashTablePtr t) {
|
578
|
+
|
579
|
+
HashNodePtr n = NULL;
|
580
|
+
|
581
|
+
int i;
|
582
|
+
|
583
|
+
|
584
|
+
|
585
|
+
assert(t);
|
586
|
+
|
587
|
+
|
588
|
+
|
589
|
+
for (i = 0; i < t->size; i++) {
|
590
|
+
|
591
|
+
n = t->heads[i];
|
592
|
+
|
593
|
+
while (n != NULL) {
|
594
|
+
|
595
|
+
printf("%s => %d\n", i, n->key, n->value);
|
596
|
+
|
597
|
+
n = n->next;
|
598
|
+
|
599
|
+
}
|
600
|
+
|
601
|
+
}
|
602
|
+
|
603
|
+
}
|
604
|
+
|
605
|
+
main.c
|
606
|
+
|
607
|
+
#define _CRT_SECURE_NO_WARNINGS
|
608
|
+
|
609
|
+
#include "hash.h"
|
610
|
+
|
611
|
+
#include "vector.h"
|
612
|
+
|
613
|
+
#include "file.h"
|
614
|
+
|
615
|
+
|
616
|
+
|
617
|
+
#define MAX 256
|
618
|
+
|
619
|
+
|
620
|
+
|
621
|
+
int main(void)
|
622
|
+
|
623
|
+
{
|
624
|
+
|
625
|
+
char buf[MAX] = { 0 };
|
626
|
+
|
627
|
+
char *copy, *s,*b;
|
628
|
+
|
629
|
+
VectorPtr v = NULL;
|
630
|
+
|
631
|
+
HashTablePtr t = NULL;
|
632
|
+
|
633
|
+
FILE *fp1,*fp2;
|
634
|
+
|
635
|
+
fp1 = fopen("input1.txt", "r");
|
636
|
+
|
637
|
+
//fp2 = fopen("write.txt", "w");
|
638
|
+
|
639
|
+
|
640
|
+
|
641
|
+
t = create_hashtable();
|
642
|
+
|
643
|
+
|
644
|
+
|
645
|
+
/*全行文の文字列を格納する*/
|
646
|
+
|
647
|
+
while (fgets(buf, sizeof(buf), fp1) != NULL)
|
648
|
+
|
649
|
+
{
|
650
|
+
|
651
|
+
*buf = *Strtolower(buf);
|
652
|
+
|
653
|
+
s = copy = _strdup(buf);
|
654
|
+
|
655
|
+
while (b = strtok(s, ","))
|
656
|
+
|
657
|
+
{
|
658
|
+
|
659
|
+
enter(t, b, 1);
|
660
|
+
|
661
|
+
s = NULL;
|
662
|
+
|
663
|
+
print_hashtable(t);
|
664
|
+
|
665
|
+
}
|
666
|
+
|
667
|
+
free(copy);
|
668
|
+
|
669
|
+
}
|
670
|
+
|
671
|
+
fclose(fp1);
|
672
|
+
|
673
|
+
|
674
|
+
|
675
|
+
|
676
|
+
|
677
|
+
return 0;
|
678
|
+
|
679
|
+
}
|