プログラマ専用SNS ミクプラ

ずっと悩んで行き詰まってしまったためどうかお手伝いお願いします。
与えられた値を５で割って出来たその余りをハッシュ値としてハッシュテープルを構成し、それにデータを１．追加、２．削除、３．データの検索、４．ハッシュテーブルの全表示、を行える機能を持ったプログラムを作りたいのですがデータの追加、削除を行う関数がどうしてもわかりません。
またデータの検索を行った後に再度検索したり、またはハッシュテーブルの全表示を行った後に再度全表示を行うなど２回操作をするとセグメントエラーが起きてしまします。多分 (*table)=(*table)->next;が原因で起こっているのだとは思いますが他にどのように書けばいいのかわかりません。

長文になりましたがどうかご教授お願いします。

コード:

 
/*初期のハッシュテーブル
  0: 25->15
  1: 31->21
  2: 7->12->22
  3: 18
  4: 4->9
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 5			/* 除数y=5 */

struct node{
  int key;
  struct node *next;
};
struct queue{
  struct node *top,*rear;
};
typedef enum{
  Quit,Insert,Delete,Print,Search
}Menu;

/* メニュー選択 */
Menu selectmenu(void)
{
  int ch;
  do{
    printf("\n(1)ハッシュに新規データを追加\n(2)ハッシュのデータを削除\n");
    printf("(3)ハッシュテーブルの表示\n(4)ハッシュテーブルから検索\n");
    printf("(0)処理終了\n");
    printf("メニューを指定してください。:");    scanf("%d",&ch);
  }while(ch<Quit||ch>Search);
  return (Menu)ch;
}

/* ハッシュテーブルから探索 */
struct node *member(struct node **table, int key){

  int i=0,j=0;
  j=key%MOD;
 
  if(j<0||4<j)goto FAILURE;
  for(i=0;i<j;i++)(*table)=(*table++);
  while(1){
    (*table)=(*table)->next;	/* ここが原因 */
    if(key==(*table)->key)goto SUCCESS;  
    if((*table)->next==NULL)goto FAILURE;
  }
 SUCCESS: return (*table);
 FAILURE: return NULL;
}

/*リストに先頭からノードを挿入  */
void enqueue(struct node **table,struct queue *q,int key2,int *rear){

  struct queue q2;
 
  if(*rear==0){
    q->top=(struct node*)malloc(sizeof(struct queue));
    (*table)=(struct node*)malloc(sizeof(struct node));  //メモリの開放
    (*table)->next=q->top;
    q->top->key=key2;
    q->top->next=NULL;
    q->rear=q->top;
  }else{
    q2.top=(struct node*)malloc(sizeof(struct queue));  //メモリの開放
    q2.top->key=key2;                                  
    q2.top->next=NULL;
    (*table)->next=q2.top;
    q2.top->next=q->rear;                             //rearの指すとこの変更
    q->rear = q2.top;
  }
  (*rear)++;
}

/* ハッシュに新規データを追加 */
int insert(struct node **table, int key){
  int surplus;
  struct node *node;
  
  node=member(table,key);
  if(node!=NULL)return 0;
  else{
    surplus=key%MOD;
    // enqueue(&table[surplus],&q[surplus],key,&rear[surplus]); 
  }
  return key;
}

/* ハッシュのデータを削除 */
int delete(struct node **table, int key){

  int surplus;
  struct node *node;
  
  node=member(table,key);
  if(node==NULL)return 0;
  else{
    surplus=key%MOD;
    // dequeue(&table[surplus],&q[surplus],key,&rear[surplus]); 
  }
  return key;

}

/* ハッシュテーブルの表示 */
void print_hash(struct node **table){
  int i=0,j=0;
  printf("\nハッシュテーブルを表示します。\n");
  for(i=0;i<5;i++){
    
    printf("%d: ",i);
  
    while(1){
      (*table)=(*table)->next;	/* ここが原因 */
      printf("%d",(*table)->key);
      if((*table)->next==NULL)break;
      printf("->");
    }
    printf("\n");
    (*table)=(*table++);
    j++;
  }
  for(i=0;i<5;i++)(*table)=(*table--);
  printf("\n\n");
}

int main(){

  struct node *table[5]={NULL,NULL,NULL,NULL,NULL}; /* table->key=NULL */
  int rear[5]={0,0,0,0,0};
  int x[10]={18,9,22,4,21,12,15,31,7,25}; /* 変数宣言 */
  int i,j,tmp,surplus,search,value;
  struct queue q[5];
  struct node *tmpnode;
  Menu menu;

 
  for(j=0;j!=10;j++){
    surplus=x[j]%MOD;
    enqueue(&table[surplus],&q[surplus],x[j],&rear[surplus]); /* 初期値からハッシュテーブルの作成 */
  }
  do{
    switch (menu = selectmenu()){

    case Insert:;
      printf("ハッシュに追加する値を入力して下さい。\n");
      scanf("%d",&value);
      tmp=insert(table,value);
      if(tmp != 0)printf("\n\n%dをハッシュに追加しました。\n\n",tmp);
      else printf("\n\n既に同じデータがハッシュに含まれています。\n\n");
      break;

    case Delete:;
      printf("ハッシュから削除する値を入力して下さい。\n");
      scanf("%d",&value);
      tmp=delete(table,value);
      if(tmp != 0)printf("\n\n%dをハッシュから削除しました。\n\n",tmp);
      else printf("\n\n指定したデータがハッシュに含まれていません。\n\n");
      break;

    case Print:;
      print_hash(table); 
      break;

    case Search:;
      printf("探索する値を入力して下さい。\n");
      scanf("%d",&value);
      tmpnode=member(table,value);
      if(tmpnode != NULL)printf("\n\n%dは見付かりました。\n\n",tmpnode->key);
      else printf("\n\n%dは見付かりませんでした。\n\n",value);
      break;
    }
  }while(menu != Quit);

  for(i=0;i<5;i++)free(table[i]);
  return 0;
}

take さんが書きました:多分 (*table)=(*table)->next;が原因で起こっているのだとは思いますが他にどのように書けばいいのかわかりません。

解読をあきらめて、自己流で書いてみました。
参考にはならないかもしれませんが。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 5u

struct node {
    int key;
    struct node *next;
};

typedef enum {
    Quit, Insert, Delete, Print, Search
} Menu;

Menu selectmenu(void)
{
    int ch;
    do {
        printf("\n"
               "(1)ハッシュに新規データを追加\n"
               "(2)ハッシュのデータを削除\n"
               "(3)ハッシュテーブルの表示\n"
               "(4)ハッシュテーブルから検索\n"
               "(0)処理終了\n"
               "メニューを指定してください。:");
        scanf("%d", &ch);
    } while (ch < Quit || ch > Search);
    return (Menu)ch;
}

struct node *member(struct node **table, int key)
{
    struct node *p = table[key % MOD];
    while (p && p->key != key) p = p->next;
    return p;
}

int insert(struct node **table, int key)
{
    int i = key % MOD;
    struct node *p = table[i];
    while (p && p->key != key) p = p->next;
    if (p) return 0;
    p = malloc(sizeof *p);
    p->key = key;
    p->next = table[i];
    table[i] = p;
    return key;
}

int delete(struct node **table, int key)
{
    int i = key % MOD;
    struct node **p = &table[i], *q;
    for (; *p && (*p)->key != key; p = &(*p)->next);
    if (!*p) return 0;
    q = *p;
    *p = q->next;
    free(q);
    return key;
}

void print_hash(struct node **table)
{
    int i;
    printf("\nハッシュテーブルを表示します。\n");
    for (i = 0; i < 5; i++) {
        struct node *p = table[i];
        printf("%d: ", i);
        if (p) printf("%d", p->key);
        while (p = p->next) printf("->%d", p->key);
        printf("\n");
    }
}

void free_table(struct node **table)
{
    int i;
    for (i = 0; i < 5; i++) {
        struct node *p = table[i];
        while (p) {
            struct node *q = p;
            p = p->next;
            free(q);
        }
    }
}

int main(void)
{
    struct node *table[5] = { 0 };
    int x[10] = { 18, 9, 22, 4, 21, 12, 15, 31, 7, 25 };
    int i, value;
    Menu menu;

    for (i = 0; i < 10; i++) insert(table, x[i]);

    do {
        switch (menu = selectmenu()) {
        case Insert:
            printf("ハッシュに追加する値を入力して下さい。\n");
            scanf("%d", &value);
            if (insert(table, value))
                printf("\n\n%dをハッシュに追加しました。\n\n", value);
            else
                printf("\n\n既に同じデータがハッシュに含まれています。\n\n");
            break;

        case Delete:
            printf("ハッシュから削除する値を入力して下さい。\n");
            scanf("%d", &value);
            if (delete(table, value))
                printf("\n\n%dをハッシュから削除しました。\n\n", value);
            else
                printf("\n\n指定したデータがハッシュに含まれていません。\n\n");
            break;

        case Print:
            print_hash(table);
            break;

        case Search:
            printf("探索する値を入力して下さい。\n");
            scanf("%d", &value);
            if (member(table, value))
                printf("\n\n%dは見付かりました。\n\n", value);
            else
                printf("\n\n%dは見付かりませんでした。\n\n", value);
            break;
        }
    } while (menu != Quit);

    free_table(table);
    return 0;
}

コード:

(*table)=(*table++);

や

コード:

(*table)=(*table--);

のように変数の書き換えと読み出しを同じ式(正確にはsequencial pointの間)の中で行うのは、
undefined behaviorになるので、やってはいけません。
また、=の左辺と右辺のどっちが先に評価されるかは決まっていないので、直感的にも結果が定まらないことがわかるでしょう。

さらに、「/* ここが原因 */」と書いてあるあたりで、tableまたは*tableの値を戻さずに操作しているのもまずい気がしました。
気がしただけで詳しくは見ていないので、アドレスを出力して変な場所になっていないか確認するといいかもしれません。
例えば*tableの値を出力するには、

コード:

printf("%p\n",(void*)*table); fflush(stdout);

とするといいでしょう。
fflush(stdout);を入れないと、出力される前に強制終了してしまい、出力されないことがあるかもしれません。

かずまさん、みけCATさん、返信遅れて申し訳ございません、回答ありがとうございます。

＞みけCATさん
ご指摘通りprintf("%p\n",(void*)*table); fflush(stdout);で確認したところアドレスが書き換えられていることがわかりました。(*table)=(*table++);とかも言われて思い出しました。(*table++);だけで十分ですよね・・・。
printf("%p\n",(void*)*table);で(void*)を付けてvoid型ポインタにしてアドレスを表示している理由は型による区別無しでアドレスを見たいからでしょうか？

＞かずまさん

書いて頂いたソースコードを読ませて頂いて、ものすごく多くの発見がありました。
delete関数の引数の変数 **tableはポインタ変数であるのにstruct node **p = &tableのように配列として扱えるのはどうしてだろう？と思って調べたら配列の[]は、tableの先頭アドレスに足し算する演算子で配列＝アドレスだからなんですね・・・。
配列はただの変数かつ配列≠アドレスで、table[5]と宣言した時tableと書いた時だけが配列の先頭アドレスとして扱えると勘違いしていたのが多くの誤解の原因だったみたいです。

take さんが書きました:(*table++);だけで十分ですよね・・・。

(*table++);はtable++;とほぼ同じ意味で、tableに1を加算します。
tableが指している値に1を加算するには(*table)++;とするといいでしょう。
(どっちがここで正しいかは検証していません)

take さんが書きました:printf("%p\n",(void*)*table);で(void*)を付けてvoid型ポインタにしてアドレスを表示している理由は型による区別無しでアドレスを見たいからでしょうか？

%pには他の型のポインタではなくvoid*を渡すことになっているからです。
他の型のデータを渡すとundefined behaviorになりますし、警告も出るかもしれません。

take さんが書きました:配列の[]は、tableの先頭アドレスに足し算する演算子で配列＝アドレスだからなんですね・・・。

[]はアドレスに足し算してデリファレンスする演算子で、x[y]は*((x)+(y))と等価です。
配列＝アドレスではありません。配列は単項&演算子(アドレス演算子)とsizeof演算子以外のオペランドとして用いられると、自動的にその先頭要素へのポインタに変換されます。

プログラマ専用SNS ミクプラ

ハッシュ法について

ハッシュ法について

Re: ハッシュ法について

Re: ハッシュ法について

Re: ハッシュ法について

Re: ハッシュ法について