#include<iostream>
using namespace std;

struct ListNode;
typedef struct ListNode *Position;
struct Hash_table;
typedef Hash_table *Hashtab;
typedef Position List;

#define Min_table_size 10

struct ListNode
{
   int Emelent;
   Position Next;
};

struct Hash_table
{
   int Table_size;
   List *Thelist;
};

//////////////相关函数声明//////////////////////
Hashtab Inittable (int Table_size);     //初始化一个散列
Position Find (int x,Hashtab H);      //查找元素x,返回对应的位置
int Hash (int x,int Table_size);  //散列函数
void Insert (int Key, Hashtab H);   //在散列中插入元素Key
void Delete (int Key, Hashtab H);   //在散列中删除元素Key



///////////////相关函数定义////////////////////
Hashtab Inittable (int table_size)
{
	Hashtab H;
	if(table_size < Min_table_size)
	{
	    cout << "Table size is too small" << endl;
		return NULL;
	}

	H = (Hashtab)malloc(sizeof(Hash_table));
	if(H == NULL)  cout << "out of space" << endl;
	H->Table_size = table_size;
	H->Thelist  = (List*)malloc(sizeof(Position) * H->Table_size);
	if(H->Thelist == NULL) cout << "out of space" << endl;
	for(int i = 0; i != H->Table_size; ++i)
	{
	   H->Thelist[i] = (Position)malloc(sizeof(ListNode));
	   if(H->Thelist[i] == NULL) cout << "out of space" << endl;
	   else
	   {
	      H->Thelist[i]->Next = NULL;
		  H->Thelist[i]->Emelent = i;
	   }
		   
	}
	return H;
}

int Hash (int x)   //对10取余数
{
   return x % 10;
}

Position Find (int x,Hashtab H)
{
  Position P;
  List L;

  L = H->Thelist[Hash(x)];  //指向含有那个元素的表头
  P = L->Next;
  while(P != NULL && P->Emelent != x)
	  P = P->Next;
  return P;
}

void Insert (int Key, Hashtab H)
{
   Position Pos, Newcell;
   List L;
   Pos = Find(Key, H);  //先找找看，有没有Key,有就算了
   if(Pos == NULL )
   {
      Newcell = (Position)malloc(sizeof(ListNode));
	  if(Newcell == NULL)  cout << "out of space" << endl;
	  else    //插入到槽后面的第一个位置
	  {
	     L = H->Thelist[Hash(Key)];
		 Newcell->Next = L->Next ;
		 Newcell->Emelent = Key;
		 L->Next = Newcell;
	  }
   }
}

void Delete (int Key, Hashtab H)
{
   Position p,Tmpcell;
   List L;
   p = Find(Key,H);
   if(p == NULL)
	   cout << "not find the " << Key << endl;
   else
   {
      L = H->Thelist[Hash(Key)];
	  p = L ;
	  while(p->Next != NULL && p->Next->Emelent != Key)   //寻找Key的前驱节点
	  {
	     p = p->Next;
	  }
	  //
	  Tmpcell = p->Next;
	  p->Next = Tmpcell->Next;
	  free(Tmpcell);
   }

}
int main ()
{
  Hashtab H = Inittable (11);
  Insert (1, H);
  Insert (4, H);
  Insert (9, H);
  Insert (16, H);
  Insert (25, H);
   Insert (19, H);
   Insert (29, H);
   Delete(19,H);
 
  cout << H->Thelist[9]->Next->Next->Emelent << endl;
   return 0;
}