ハッシュ法のチェイン法がうまくいきません。

[TOMOKI]

今以下のようなプログラムをチェイン法を使って作っています。

enter関数：同名で生年の異なるデータを登録できる。
search関数:同名の人のすべてのデータを出力する。
delete関数:同名の人のデータを指定して削除できる。

以下がプログラムです。

コード:

#define M 257

int hash(char *v)
{
	int x;
	x = 0;
	while(*v){
		x = 256 * x + (*v++);
	}
	if(x < 0){
		x = (-x);
	}
	return(x % M);
}

コード:

#include <stdio.h>
#include <stdlib.h>
#define NIL 0
#define M 157
#define ITEMMAX 200

typedef struct CHAIN_x
{char *id; int info; struct CHAIN_x *next; } CHAIN;
static CHAIN *hashtable[M];
static int itemtop = 0;
static CHAIN table[ITEMMAX];

extern int hash();
extern int strcompare();
extern char *enterstring();

void initialize()
{
	int i;
	for(i = 0; i < M; i++)
		hashtable[i] = NIL;
}
void delete(char *id1, int info1)
{
	int x;
	int hashinfo;
	CHAIN *p1;

	x=hash(id1);
	p1=hashtable[x];

	while(p1 != NIL){
		if((search(p1->id,p1->info)) == info1){
			hashtable[x]=hashtable[x]->next;
			return ;
		}

		p1 = p1->next;
	}
	printf("not found\n");

}


void enter(char *id1, int info1)
{
	int x;
	int hashinfo;
	CHAIN *p;

	x = hash(id1);
	p = hashtable[x];


	while (p != NIL){
		if((hashinfo=search(p->id,info1)) != -1){
			if(hashinfo==info1){
				printf("This name is already resisted!!\n");
				return ;
			}
		}
		p = p->next;
	}
	if (itemtop >= ITEMMAX) {
		printf("item table overflow");
		exit(0);
	}

	table[itemtop].id = enterstring(id1);
	table[itemtop].info = info1;
	table[itemtop].next = hashtable[x];
	hashtable[x] = &table[itemtop];

	itemtop++;

	return ;

}

int search(char *id1,int info1)
{
	int x;
	CHAIN *p1;
	CHAIN *p2;

	x = hash(id1);
	p1 = hashtable[x];
	p2 = hashtable[x];

	if(info1 == 0){
		if(p1 == NIL){
			return -1;
		}
		while(p1 != NIL) {
			printf("%s %d\n",p1->id,p1->info);
			p1=p1->next;
		}
		return 0;
	}

	while(p2 != NIL) {
		if(strcompare(id1, p2->id) ==0) return(p2->info);
		p2 = p2->next;
	}

	return(-1);
}

コード:

#include <stdio.h>
#include <stdlib.h>
#define CHARMAX 10000
static int chartop = 0;
static int charbtm = CHARMAX;
static char charheap[CHARMAX];
extern void initialize();
extern void enter();
extern void delete();
extern int search();

char *enterstring(char *s)
{
	char *cp;
	int i, j, len, result;


	cp = s;
	len = 0;
	while (*cp++) len++;
	len++;
	if(charbtm - chartop < len){
		printf("identifier string buffer overflow");
		exit(1);
	}
	result = chartop;
	j = chartop;
	chartop += len;
	cp = s;
	for(i = 0; i < len; i++) charheap[j++] = (*cp++);
	return(&charheap[result]);
}

int strcompare(char *a, char *b)
{
	while(*a==*b){
		if(*a == 0)
			return 0;
		a++;
		b++;
	}
	return -1;
}

main()
{
	int t, year;
	int num;
	char name[CHARMAX];

	initialize();

	while(1){
		printf("実行したい処理を選んでください。\n");
		printf("1.登録\n");
		printf("2.探索\n");
		printf("3.削除\n");
		if(scanf("%d",&num)==EOF){
			break;
		}
		switch(num){
		case 1:

			printf("Please enter name.\n");
			if(scanf("%s",name)==EOF){
				break;
			}
			printf("Please enter year.\n");
			if(scanf("%d",&year)==EOF){
				break;
			}
			enter(name ,year);

			break;


		case 2:

			printf("Please enter name.\n");
			if(scanf("%s",name)==EOF){
				break;
			}
			year = 0;
			t = search(name,year);
			if(t==-1){
				printf("not found.\n");
			}
			break;

		case 3:
			printf("Please enter name.\n");
			if(scanf("%s", name)==EOF){
				break;
			}
			year=0;
			search(name,year);
			printf("Please enter year.\n");
			if(scanf("%d",&year)==EOF){
				break;
			}
			delete(name,year);
			break;
		}
	}
}

まず同名で年のことなる人を２人登録します。
takashi 1882
takashi 1932

次にtakashi 1932の削除を行います。

しかしdelete関数を呼び出した後not foundと出力されました。
検索で登録内容を確認してみたところやはり削除はされていませんでした。
このプログラムのおかしなところはありますか？
よろしくお願いします。

[みけCAT]

まず、症状は「同名で年の異なる人を2人登録したとき、先に登録したほうが削除できない」ですね。

[non]

delete関数が間違ってます。絵でも描いて考えてみましょう。

[みけCAT]

search関数でinfo1が0でない時、idの一致だけを見ていてinfo1の一致をチェックしていないので、
hasutableに入っていないid1とinfo1で探しても、hashtableに入っているidがid1と一致していればそのinfoが返されます。
よって、delete関数の

コード:

if((search(p1->id,p1->info)) == info1){

という条件に引っかからないので、削除されません。
また、この条件式やsearch関数を直したとしても、

コード:

hashtable[x]=hashtable[x]->next;

というコードではhashtableに入っている要素(違うidかもしれない)が削除されます。

[TOMOKI]

みなさんありがとうございます。
delete関数が根本的に違うようなので、まずは年号を関係なしに名前が一致した場合削除するというものを考えてみたいと思います。
そこで以下のようなものに変えてみました。

コード:

void delete(char *id1, int info1)
{
  int x;
	int hashinfo;
  CHAIN *p1;

  x=hash(id1);
  p1=hashtable[x];
while(p1 != NIL){
    if(strcompare(id1,p1->next->id) == 0){	
			p1->next = p1->next->next;
			
      return ;
    }
    p1 = p1->next;
  }
  printf("not found\n");

}

しかしこれではセグメントエラーとなってしまいました。
原因がわかりません。
まだdelete関数の考え方が間違っているということでしょうか？
よろしくお願いします。

[TOMOKI]

すみません、以下のようにすれば名前一致のdeleteはできました。

コード:

void delete1(char *id1)
{
  int x;
  CHAIN *p1;
	CHAIN *tmp;

  x=hash(id1);
  p1=hashtable[x];


	if(strcompare(id1,p1->id) == 0){
		p1=p1->next;
		hashtable[x]=p1;
		return;
	}
	
  while(p1 != NIL){
    if(strcompare(id1,p1->next->id) == 0){	
			p1->next = p1->next->next;
			p1=hashtable[x];
			hashtable[x]=p1;
      return ;
    }
    p1 = p1->next;
  }
  printf("not found\n");

}

何となく理解したので年号一致のほうもできそうです。
少し考えてみます。
またわからなかったら質問すると思うのでその時はよろしく尾根がします。

[non]

20行と21行は何をしているのでしょうか？

また、
#define M 157
と
#define M 257
の2種類、ありますが、なぜ？

[みけCAT]

コード:

void delete(char *id1, int info1)
{
  int x;
    int hashinfo;
  CHAIN *p1;
 
  x=hash(id1);
  p1=hashtable[x];
while(p1 != NIL){
    if(strcompare(id1,p1->next->id) == 0){  
            p1->next = p1->next->next;
            
      return ;
    }
    p1 = p1->next;
  }
  printf("not found\n");
 
}

この関数では、p1->nextがNULLの時、アクセス違反になる可能性があります。

[みけCAT]

コード:

void delete1(char *id1)
{
  int x;
  CHAIN *p1;
    CHAIN *tmp;
 
  x=hash(id1);
  p1=hashtable[x];
 
 
    if(strcompare(id1,p1->id) == 0){
        p1=p1->next;
        hashtable[x]=p1;
        return;
    }
    
  while(p1 != NIL){
    if(strcompare(id1,p1->next->id) == 0){  
            p1->next = p1->next->next;
            p1=hashtable[x];
            hashtable[x]=p1;
      return ;
    }
    p1 = p1->next;
  }
  printf("not found\n");
 
}

このコードでは、存在しない名前を削除しようとしたときにアクセス違反になります。
この関数の「while(p1 != NIL)を」「while(pi ->next != NIL)」にして、その下の

コード:

            p1=hashtable[x];
            hashtable[x]=p1;

という無駄な2行を削除すればいいと思います。