ハッシュ法の実装について

Question

以下のコード(ハッシュ表)を実行するとハッシュ表にデータを挿入し、Aの長さを出力するところまではうまくいっているのですが、それ以降処理が進みません。《printf("after delete:"); 》これが出力されないのです。
ハッシュ表削除後のlength関数をコメントすると《printf("after delete:"); 》が処理されます。
間違っている部分を教えて頂きたいです
不明な部分を指摘していただければ適宜、編集・返答します。よろしくお願いします

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* 文字列関数を扱えるようにする */
#define W 10 /* W = 文字列の最大長さ，ここでは 10 に設定 */
#define m 97 /* m = ハッシュ表のサイズ，ここでは 97 に設定 */
#define maxN 50 /* maxN = 扱う文字列の最大数，ここでは 50 に設定 */

struct cell
{
  char key[W+1]; int next; /* 構造体 cell の定義 */
};

int allocate_object(struct cell *L, int *f); /* 関数 allocate_object の宣言 */
int chained_hash_search(int *A, struct cell *L, char *a); /* 関数 chained_hash_searchの宣言 */
int hash_val(char *a);
void chained_hash_insert(int *A, struct cell *L, int x);
int length(struct cell *L, int a);
void chained_hash_delete(int *A, struct cell *L, int x);
void free_object(struct cell *L, int *f, int x);
int Serch(int *A, struct cell *L, int x);

int main(void)
{
  struct cell List[maxN]; /* リストは cell の配列，数値数は n まで */
  int A[m]; /* ハッシュ表を表す配列 */
  int N; /* 数値の数は N */
  int freeL; /* 空きアドレスのリストの先頭*/
  int i, h, y, x, b;
  char word[W+1]; /* ファイルから読み込んだ文字列を格納する変数 */
char fname[128]; /* 読み込むファイルの名前 */
    FILE *fp; /* 入力ファイル */
    for (i=0; i<maxN-1; i++){ /* allocate_object, free_object のための初期化 */
      List[i].next = i+1;
    }
    List[maxN-1].next = -1;
    freeL = 0; /* 空きリストの初期化 */
    for (h=0; h<m; h++){
      A[h] = -1;
    } /* ハッシュ表の初期化 */

printf("input filename: "); /* ファイル名の入力を要求 */
    fgets(fname, sizeof(fname), stdin); /* ファイル名取得 */
    fname[strlen(fname)-1] = '\0';
    fflush(stdin);
    fp = fopen(fname, "r"); /* ファイルを読み込みモードで開く */
    fscanf(fp, "%d", &N); /* N をファイルから読み込む */
    if (N > maxN){
      printf("N is too large, setting N = %d\n", maxN);
      N = maxN;
    }
    for (i=0; i<N; i++){
      fscanf(fp, "%s", word); /* 文字列をファイルから読み込み，wordに格納 */
      y = chained_hash_search(A, List, word); /* ハッシュ表の中で文字列 word を探索 */
      if (y == -1){
        x = allocate_object(List, &freeL);
        strcpy(List[x].key, word);
        chained_hash_insert(A, List, x);
      }

    }
    fclose(fp); /* 開いたファイルを一旦閉じる */

 for (h=0; h<m; h++){
      b = length(List, A[h]);
      if(b != 0)
        {
          printf("A[%d]の長さは%d\n", h, b);
        }
      /* ハッシュ表のアドレス h が指す*/
      /* リスト A[h] の長さを出力 */
    }
    fp = fopen(fname, "r"); /* ファイルを再度読み込みモードで開く */
     fscanf(fp, "%d", &N); /* N をファイルから読み込む */
    if (N > maxN){N = maxN;}
     for (i=0; i<N; i++){
     fscanf(fp, "%s", word); /* 文字列をファイルから読み込み，wordに格納 */
     x = chained_hash_search(A, List, word);
     if(x != -1)
       {
         chained_hash_delete(A, List, x);/* データを削除する部分 */
         free_object(List, &freeL, x);
       }
     }
     fclose(fp); /* 開いたファイルを閉じる */

printf("after delete:");
     for (h=0; h<m; h++){
       b = length(List, A[h]);
      if(b != 0)
        {
           printf("A[%d]の長さは%d\n", h, h);
         }
      /* ハッシュ表のアドレス h が指す*/
       /* リスト A[h] の長さを出力 */
     }
     printf("\n");
     return 0;
}

int hash_val(char *a) /* 文字列はポインタ渡し */
{
  int h, i;
  h = 0; i = 0;
  while (a[i] != 0 && i < W) /* 文字の整数コードの和を計算 */
    {
      h = h + (int)a[i];
      i = i + 1;
    }
  h = h % m; /* m で割った余りを取る */
  return h;
}

int chained_hash_search(int *A, struct cell *L, char *a)
{
  int x,h;
  h = hash_val(a);
  x = A[h];

  while(x != -1 && strcmp(L[x].key, a) != 0)
    {
      x = L[x].next;
    }

  return x;
}

int allocate_object(struct cell *L, int *f)
{ /* リスト配列と空きアドレスリスト先頭はポインタ渡し */
  int x;
  if (*f == -1){printf("error: out of space\n"); x = -1;}
  /* 空きアドレスがなければエラーメッセージを表示*/
  else {
    x = *f;
    *f = L[*f].next;
  }
  return x;
}

void free_object(struct cell *L, int *f, int x)
{
  L[x].next = *f;
 *f = x;
}

void chained_hash_insert(int *A, struct cell *L, int x)
{
  int h;
  h = hash_val(L[x].key);
  L[x].next = A[h];
  A[h] = x;
}

int length(struct cell *L, int a)
{
  int i = 0;

  if(a != -1)
    {
      while(L[a].next != -1)
        {
          i = i + 1;
          a = L[a].next;
        }
      i = i + 1;
    }

  return i;
}

void chained_hash_delete(int *A, struct cell *L, int x)/*セルをリストから削除*/
{
  int h,z;

  h = hash_val(L[x].key);

  z = Serch(A, L, x);

  if(z != -1)
    {
      L[z].next = L[x].next;
    }

  else
    {
      A[h] = L[x].next;
    }
}

int Serch(int *A, struct cell *L, int x)
{
  int h,y=0;

  for(h=0; h<m; h++)
    {
      if(A[h] == x)
        {
          y = -1;
        }
    }
  if(y != -1){
    for(h=0; h<m; h++)
      {
        if(L[h].next == x)
          {
            y = h;
          }
      }

  }
  return y;
}

Answer 1

length関数中のwhile文が無限ループになっているのでは。
きちんと終了条件 L[a].next == -1 となるデータまで到達できているか確認すべきです。

Comments

[退会済みユーザー]

挿入した時のAの長さの計算の仕方と
削除後のAの長さの計算の仕方は変わるのでしょうか？

[hope_mucci]

length関数をコメントしたら処理が最後まで動作するという重要な情報をなぜ削除したのですか？
質問が修正されて余計問題がわからなくなりました。

挿入した際にlength関数が正常に動作しているのであれば、削除した際のデータ削除方法が誤っているのではないでしょうか。怪しい箇所にprintf文を置いて変数の動きをチェックしましょう。

なお、通常コンソールでは標準出力は改行が出力されるまで画面に表示されません。また、標準エラー出力はそのような規制がないのでデバッグ出力は標準エラー出力に出したほうが使い勝手が良いです。

[退会済みユーザー]

申し訳ありません。ハッシュ表の挿入の際には問題がなかったため削除の際に用いても問題がないものかと思ってしまい削除してしまいました。

printf文を使って動きを確認してみます