質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

5955閲覧

英文ファイルを英単語ごとにハッシュ表に格納してソースを行う

kt3302y

総合スコア27

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2015/07/18 12:52

編集2015/07/19 11:56

前回投稿させてもらった件の続きなのですが,英単語を登録して出現回数も記録するハッシュ表を作成しました.今悩んでいますのがlexと入力したら英単語を辞書順にoccと入力したら出現回数を降順に回数が一致するなら辞書順に並べるというプログラムを作成したソースコードが下のものになるのですが,これを実行するとqsortを実行しようとするとアクセス違反が起きてしまいます.何故起きてしまうのか原因と解決方法を教えてくれないでしょうか
hash.c```/*

  • hash.c: ハッシュ表の型とその操作用関数の定義
  • (ハッシュ表のキー:文字列,値:非負の整数)

*/
#include "hash.h"

#define HASH_SIZE 997 /* ハッシュ表の内部配列のサイズ /
#define HASH_RADIX 97 /
ハッシュ関数用の基数 */

/* ハッシュ表内の連結リストに含まれるノードとそのポインタの型. */
typedef struct hash_node HashNode;
typedef HashNode *HashNodePtr;

/* ハッシュ表内の連結リストに含まれるノードの構造体. /
struct hash_node { /
ハッシュ表内の連結リストのノード */
char key; / キー /
int value; /
キーに対応する値 /
int id; /
キーに付与された通し番号 */
struct hash_node next; / 次のノードへのポインタ */
};

/* ハッシュ表の構造体. */
struct hashtable {
HashNodePtr heads; / 内部配列 /
int serial_id; /
通し番号管理用の変数 /
int size; /
内部配列のサイズ */
};

/* static 関数のプロトタイプ宣言 */
static unsigned int hash(char *s);
static int get_index(HashTablePtr t, char *key);

/* 文字列 s のハッシュ値を計算する. */
static unsigned int hash(char *s) {
unsigned int v;

v = 0; while (*s != '\0') { v = v * HASH_RADIX + *s; s++; } return v;

}

/* ハッシュ表を一つ生成し,そのポインタを返す.*/
HashTablePtr create_hashtable(void) {
HashTablePtr t = NULL;
int i;

t = malloc(sizeof(HashTable)); if (t == NULL) { fprintf(stderr, "Couldn't allocate memory for a hashtable\n"); exit(EXIT_FAILURE); } t->serial_id = 0; t->size = HASH_SIZE; t->heads = malloc(sizeof(HashNodePtr) * t->size); if (t->heads == NULL) { fprintf(stderr, "Couldn't allocate memory for a hashtable's header array\n"); exit(EXIT_FAILURE); } /* 各連結リストの先頭要素へのポインタは必ず NULL に初期化する */ for (i = 0; i < t->size; i++) { t->heads[i] = NULL; } return t;

}

/* ハッシュ表の実質的な解放作業を行う.

  • (次々と free() するので free() 後の NULL 代入は省略)

*/
void delete_hashtable0(HashTablePtr t) {
HashNodePtr n = NULL, m = NULL;
int i;

/* free() と同様,NULLポインタに対しては何も行わない */ if (t == NULL) { return; } /* 各連結リストの領域を解放 */ for (i = 0; i < t->size; i++) { n = t->heads[i]; while (n != NULL) { m = n; n = n->next; free(m); } } /* 最後に連結リストの先頭ポインタの領域を解放 */ free(t->heads); free(t);

}

/* ハッシュ表 t に登録されているキーと値のペアの数を返す.*/
int get_cardinality(HashTablePtr t) {
assert(t);
return t->serial_id;
}

/* ハッシュ表 t の内部配列の添え字を返す */
static int get_index(HashTablePtr t, char *key) {
return hash(key) % t->size;
}

/* ハッシュ表 t にてキー key が登録されていれば1,

  • されていなければ0を返す.

*/
int has_key(HashTablePtr t, char *key) {
assert(t && key);
return (lookup(t, key) >= 0) ? 1 : 0;
}

/* ハッシュ表 t にてキー key に対応する値を返す.

  • 値が見つからなかったら -1 を返す.
  • (ハッシュ表の値として登録できるのは非負の整数値と仮定)

*/
int lookup(HashTablePtr t, char *key) {
HashNodePtr n = NULL;
int index;

assert(t && key); /* ハッシュ表の内部配列の添え字を計算 */ index = get_index(t, key); /* index 番目の連結リストを先頭から順に走査 */ n = t->heads[index]; while (n != NULL) { /* 引数で指定された key とハッシュ表内のキーが一致したら 直ちに対応する値を返す */ if (strcmp(key, n->key) == 0) { return n->value; } /* 走査を次に進める */ n = n->next; } /* キーが見つからなかったので -1 を返す */ return -1;

}

/* キー key と値 value のペアをハッシュ表 t に登録し,その通し番号を返す.

  • (値 value は非負であると仮定)

*/
int enter(HashTablePtr t, char *key, int value) {
HashNodePtr n = NULL, m = NULL;
int index;

assert(t && key); /* 仕様上のエラーなので非負の値が渡されたときはメッセージを出す */ if (value < 0) { fprintf(stderr, "Invalid value %d for key %s\n", value, key); exit(EXIT_FAILURE); } /* 内部配列の添え字を計算 */ index = get_index(t, key); /* キー key が既に登録されているか探し, * 登録されている場合は値を value に更新する. */ n = t->heads[index]; /* index 番目の head を出発点とする */ if (n != NULL) { while (n != NULL) { if (strcmp(key, n->key) == 0) { /* 登録されていた */ n->value += 1; /* 値を更新 */ return n->id; } n = n->next; } } /* 新しいノードを生成 */ m = malloc(sizeof(HashNode)); if (m == NULL) { fprintf(stderr, "Couldn't allocate memory for a hash node\n"); exit(EXIT_FAILURE); } m->key = _strdup(key); m->id = t->serial_id; m->value = value; /* 新しいノードを先頭に挿入 */ m->next = t->heads[index]; t->heads[index] = m; t->serial_id++; /* 次の通し番号に更新 */ return m->id; /* 登録したキーと値のペアに付与された通し番号を返す */

}

/*

  • ハッシュ表 t に登録されるキーの配列を返す.

*(この配列のサイズは get_hash_cardinality() で取得可能)
*/
char **get_keys(HashTablePtr t) {
char **keys = NULL;
HashNodePtr n;
int i;

assert(t); keys = malloc(sizeof(char *) * t->serial_id); if (keys == NULL) { fprintf(stderr, "Couldn't allocate memory for hashtable keys\n"); exit(EXIT_FAILURE); } /* 各連結リストを走査し,配列に詰め込む */ for (i = 0; i < t->size; i++) { n = t->heads[i]; while (n != NULL) { keys[n->id] = n->key; /* 通し番号を配列添え字に */ n = n->next; } } return keys; /* 後で free() する必要あり */

}

/* ハッシュ表の内容を表示する.*/
void print_hashtable(HashTablePtr t, FILE *fp) {
HashNodePtr n = NULL;
int i;

assert(t); for (i = 0; i < t->size; i++) { n = t->heads[i]; while (n != NULL) { fprintf(fp, "%s => %d\n", n->key, n->value); n = n->next; } }

}

void sort1(HashTablePtr t)
{
qsort(t->heads, t->size, sizeof(HashNodePtr), compare1);
}

void sort2(HashTablePtr t)
{
qsort(t->heads, t->size, sizeof(HashNodePtr), compare2);
}

/qsortの比較関数/
int compare1(const void *p, const void *q)
{
HashNodePtr u = NULL;
HashNodePtr v = NULL;

u = (HashNodePtr )p; v = (HashNodePtr )q; return strcmp(u->key, v->key);

}

int compare2(const void *p, const void *q)
{
HashNodePtr u = NULL;
HashNodePtr v = NULL;

u = (HashNodePtr)p; v = (HashNodePtr)q; if (u->value < v->value)return 1; if (u->value > v->value)return -1; if (u == v)return strcmp(u->key, v->key);

}

main.c ```C #define _CRT_SECURE_NO_WARNINGS #include "hash.h" #include "vector.h" #include "etc.h" #define MAX 256 int main(void) { char buf[MAX] = { 0 }; char *copy, *s,*b; char *str = "occ"; VectorPtr v = NULL; HashTablePtr t = NULL; FILE *fp1,*fp2; fp1 = fopen("input1.txt", "r"); fp2 = fopen("write.txt", "w"); t = create_hashtable(); /*全行文の文字列を格納する*/ while (fgets(buf, sizeof(buf), fp1) != NULL) { *buf = *Strtolower(buf); s = copy = _strdup(buf); while (b = strtok(s, "(), .;'![]?\n\"")) { enter(t, b, 1); s = NULL; } free(copy); } if (strcmp(str, "lex")==0)sort1(t); else if (strcmp(str,"occ")==0)sort2(t); print_hashtable(t, fp2); fclose(fp1); fclose(fp2); return 0; }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

上のコメントでも書きましたが、私の回答が間違っていました。
別の原因を見つけて訂正した回答を投稿し直しました。

投稿2015/07/18 14:08

eripong

総合スコア1546

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

eripong

2015/07/18 14:09

コメントと間違って投稿したので、この回答は無視してください。
guest

0

ベストアンサー

lang

1 if (str == "lex")sort1(t); 2 else if (str =="occ")sort2(t);

ここで文字列を==で比較していますが、
strcmpstrncmpなどを使うべきと思います。

このままではメモリアドレスの比較になって、
どちらも通らないため、ハッシュ表が作成されず、
結果としてアクセス違反になっているのだと思います。

訂正

上の記述は、「このままでは………なっているのだと思います。」
という部分が誤っていました。
また、この問題の原因でもなさそうです。

lang

1sort(t, sizeof(t), sizeof(t), compare1);

がおかしいと思います。

void * data:ソート対象データ
size_t data_cnt:ソート対象データ件数
size_t data_size:ソート対象データ1件当りのサイズ
int func:int型の比較関数(プログラマが作成する関数)

なので、

lang

1sort(t->heads, t->size, sizeof(HashNodePtr), compare1);

ではないかと思うのですが、どうでしょうか?

投稿2015/07/18 13:40

編集2015/07/18 14:14
eripong

総合スコア1546

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

eripong

2015/07/18 13:41

それはそれとして、前の質問の回答のどれかをベストアンサーにして 質問を締めた方が良いのではと思います。
eripong

2015/07/18 13:46

すみません。 よく見ると初期化の流れは別だったのでこの回答は取り下げます。
kt3302y

2015/07/18 13:48

解答ありがとうございます. おっしゃられたとおりに if (strcmp(str,"lex")==0)としてみましたがアクセス違反が起きてしまいました. この表記では違いますか?
eripong

2015/07/18 14:10

上のコメントでも書きましたが、私の回答が間違っていました。 すみません。 別の原因を見つけて訂正した回答を投稿し直しました。
kt3302y

2015/07/18 14:33

してみましたがうまくいきませんでした nextポインタがつながってないんですかね
eripong

2015/07/18 14:39 編集

うーん、そうですか。 sort1、sort2を呼び出さなければ、 print_hashtableは正常動作するのでしょうか? それと、sort1についてしか記述しませんでしたが、 sort2についても同様の修正が必要ですが、 実施されたでしょうか?
kt3302y

2015/07/18 14:54

sortを呼び出さなければ正常に起動します. あと、このqsort条件に変更した場合,そのqsortのところでアクセス違反が起きていました sort1,2両方行いましたがエラーが起こりました
eripong

2015/07/18 15:13 編集

よく見ると、compare1、compare2で、 引数がNULLのケースが想定されていませんね。 NULLチェックして、NULLの要素が前か後ろかになるようにすれば、 アクセス違反は出なくなるのではと思います。
eripong

2015/07/18 15:17

ただ、それだけでは意図したコードにはならなそうです。 ハッシュ表の内容を配列に格納し直して、 それからソートするなど、直さなければならないと思います。
kt3302y

2015/07/19 00:03

keyのソートの場合、get_keys関数を使用してkeyを配列に格納してqsortを使用すればよいのでしょうか
eripong

2015/07/19 00:10

keyのソートならそれで良いですが、 valueもソートに使うなら、 HashNodePtr *get_entries(HashTablePtr t)というような関数を作って、 その結果をcompare1やcompare2でqsortすれば良いと思います。
kt3302y

2015/07/19 10:18 編集

そのkeyとvalueの値を格納する配列というのはどのようにすればよいのでしょうか. あと、別の配列に入れてその配列をソートを行ったとしてもハッシュ表の内容を表示するため、結局ソートしたことにならないと思うのですが違うのですか? すいません、初心者のため初歩的な質問をしてしまい
eripong

2015/07/19 15:02

まず、ハッシュ表をハッシュ表のままソートする、 ということはできません。 ハッシュ表はハッシュの順になっていて、 別の順序にしては、ハッシュ表でなくなってしまうためです。 ソートしたい場合は、 ソートしたい要素を配列などにする必要があります。 配列であれば、順序が変わっても問題ないためです。 表示も、ハッシュ表を表示する処理を使うのではなく、 配列に格納した内容を表示する処理が必要になります。 今回の場合、全てのHashNodePtrを配列を作れば、 それをソートすることができます。 注意点としては、HashNodePtrはnextでつながっているものもあるので、 それもは配列の一要素として格納する必要があることです この全てのHashNodePtrの配列を作る処理によく似た処理があります。 それは、get_keys関数です。 これをほぼそのままコピーして、HashNodePtr *get_entries(HashTablePtr t)という関数を作り、mallocをHashNodePtrのサイズで行い、keyでなくHashNodePtrを配列に格納すれば、期待する関数になるはずです。 この説明でどうでしょうか?
kt3302y

2015/07/21 05:25

とても詳しい説明ありがとうございました.うまく作成することができました. qsortがこの方法でできない原因も知ることができましたし,本当にありがとうございました
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問