#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define L 20 /*定義哈希表長*/

int K,m,j=0,p,s,z,t,y,e,low,high;int c;//int t[1]={1};int *e=t;
 struct student{char name[20];int num;
           char sex[20];int Math;
		   int English;int score;
}x[L],pivot[L],elem[L];
 
typedef struct HashTable
{
 student  elem[L];
 
}HashTable;
int a[20]; 
HashTable H;

void zhijie(int low,int high);

//*************************************************************************************
void createHash(HashTable &H,int p,int &c,int K)     // 按學號查詢
{  int t=0; 
for (t=0;t<K;t++)  {a[t]=x[t].num %K;} 
  for(int i=0;i<K;i++)
 {  p=a[i];  
  for(int t=0;t<i;t++)
  { int c=0;
	  while(a[i]==a[t])
    {  c++;    
       p=(p+c)%K;
	   a[i]=p;    
	}  
  }	   
 H.elem[p].num=x[i].num;
 for(int r=0;r<15;r++)
{H.elem[p].name[r]=x[i].name[r];
 H.elem[p].sex[r]=x[i].sex[r];
}
 H.elem[p].Math=x[i].Math;
 H.elem[p].English=x[i].English;
 H.elem[p].score=x[i].score;
}
}
int EQ(int m, int s)  	  
{ if(m==s)
     return 1;
  else  return 0;
}
void collision(int c)
{  z=(z+c)%K;
j++;
}


  void search_Hash(HashTable H)
{ 
  int m,c=0;
  cout<<"請輸入要查找學生基本信息的學號:   "<<endl;
  cin>>m;  
       z=m%K;   
while ( j<K && !EQ(m,H.elem[z].num))
{ 
	collision(++c);   // 求得下一探查地址 p  
}  
	

                   	  
 if (EQ(m, H.elem[z].num)) 
	 { 
       cout<<"該學生的基本信息是: "<<endl; 
       cout<<"學號:    "; cout<<H.elem[z].num<<endl;  
       cout<<"姓名:    "; cout<<H.elem[z].name<<endl;  
       cout<<"性別:    "; cout<<H.elem[z].sex<<endl;  
       cout<<"數學:    "; cout<<H.elem[z].Math<<endl;  
       cout<<"英語:    "; cout<<H.elem[z].English<<endl;  
       cout<<"總成績:  "; cout<<H.elem[z].score<<endl; 
  } 
  else  cout<<"沒有該學生的基本信息!"<<endl;   // 查找不成功    
}

void Search_Bin ( HashTable H, int K )   // 按學號利用折半查找學生基本信息
{ 
int low,high,mid,n=0;
  zhijie(low,high);
  int v; 
  cout<<"請輸入要查找學生基本信息的學號:   "<<endl;
  cin>>v;
for(int i=0;i<K;i++)
{ 	
    low=0;high =K-1;            // 置區間初值
   while (low <= high&&n==0) 
	{ mid = (low + high)/2; 
     if (v==pivot[mid].num)  
	 { cout<<"該學生的基本信息是: "<<endl; cout<<mid<<endl;
       cout<<"學號:    "; cout<<pivot[mid].num<<endl;  
       cout<<"姓名:    "; cout<<pivot[mid].name<<endl;  
       cout<<"性別:    "; cout<<pivot[mid].sex<<endl;  
       cout<<"數學:    "; cout<<pivot[mid].Math<<endl;  
       cout<<"英語:    "; cout<<pivot[mid].English<<endl;  
       cout<<"總成績:  "; cout<<pivot[mid].score<<endl;
	   n++;
	 }         	  
     else  if ( v<pivot[mid].num)
        high = mid - 1;       // 繼續在前半區間進行查找
      else  low = mid + 1;   // 繼續在后半區間進行查找
   }               // 順序表中不存在待查元素            
}    
 if(n==0)
   cout<<"沒有該學生的基本信息!"<<endl; 
}
//***************************************************************************************



void zhijie(int low,int high)          /*直接插入排序*/
{ int k1;char g[15];
  for(j=0;j<K-1;j++)
    for(int i=0;i<K-1-j;i++)
   if(pivot[i].num>pivot[i+1].num)
  {  k1=pivot[i].num; pivot[i].num=pivot[i+1].num; pivot[i+1].num=k1;   
     k1=pivot[i].Math; pivot[i].Math=pivot[i+1].Math; pivot[i+1].Math=k1;
	 k1=pivot[i].English; pivot[i].English=pivot[i+1].English; pivot[i+1].English=k1;
	 k1=pivot[i].score; pivot[i].score=pivot[i+1].score; pivot[i+1].score=k1;
	 
  for(int z=0;z<15;z++)
{  g[z]=pivot[i].name[z]; pivot[i].name[z]=pivot[i+1].name[z];pivot[i+1].name[z]=g[z];                                       
   g[z]=pivot[i].sex[z];  pivot[i].sex[z]=pivot[i+1].sex[z];pivot[i+1].sex[z]=g[z];

}
}
}     

  	
void InsertSort()//插入排序
{   for (int i = 0; i < K; i++)   
     {   
       int t=x[i].num;
	   int m=x[i].Math;
	   int n=x[i].English;
	   int r=x[i].score;   
       int j = i;   
       while ((j > 0) && (x[j - 1].num > t)&&x[j - 1].Math>m&&x[j - 1].English>n&&x[j - 1].score>r)   
         {   
           x[j].num = x[j - 1].num;//交換順序   
           x[j].Math = x[j - 1].Math;
		   x[j].English = x[j - 1].English;
           x[j].score = x[j - 1].score;
		   --j;   
            }   
         x[j].num = t;x[j].Math=m;  x[j].English=n; x[j].score=r; 
        }   
cout<<"學生的學號排序:   "<<endl;
for (i=0;i<K;i++)   cout<<x[i].num<<endl;
cout<<"學生的數學成績排序:   "<<endl;
for (i=0;i<K;i++)   cout<<x[i].Math<<endl;
cout<<"學生的英語成績排序:   "<<endl;
for (i=0;i<K;i++)   cout<<x[i].English<<endl;
cout<<"學生的總成績排序:   "<<endl;
for (i=0;i<K;i++)   cout<<x[i].score<<endl;
}

 void main()
 { 
HashTable H;
int t; 
while(1){ 
cout<<"1.請輸入學生基本信息\n"; 
cout<<"2.哈希表查找\n"; 
cout<<"3.折半法查找\n"; 
cout<<"4.起泡排序\n"; 
cout<<"5.快速排序\n"; 
cout<<"0.退出\n";
cout<<"\n請選擇以上的操作:\n"; 
 
cin>>t; 
switch(t){ 
case 0:return; 
case 1: 
	{cout<<"請輸入學生的個數:"<<endl; 
	 cin>>K;
	for(int i=0;i<K;i++)
	{ 
 cout<<"輸入學號:  "; cin>>x[i].num; pivot[i].num=x[i].num;
 cout<<"輸入姓名:  "; cin>>x[i].name; for(int z=0;z<15;z++) pivot[i].name[z]=x[i].name[z];
 cout<<"輸入性別:  "; cin>>x[i].sex; for(z=0;z<15;z++)   pivot[i].sex[z]=x[i].sex[z];
 cout<<"輸入數學成績:  "; cin>>x[i].Math; pivot[i].Math=x[i].Math; 
 cout<<"輸入英語成績:  "; cin>>x[i].English;pivot[i].English=x[i].English; 
 x[i].score=x[i].Math+x[i].English; 
pivot[i].score=x[i].score;
	}	
break; }

case 2: 
	{ createHash(H, p,c,K);
        search_Hash(H);
break;	} 
	
case 3:
	{  createHash(H, p,c,K);
	   Search_Bin ( H,K);
break;	}	 

case 4:
{ createHash(H, p,c,K);
	zhijie( low, high);
 cout<<"學生的學號排序:   "<<endl;
 for(int i=0;i<K;i++)  cout<<pivot[i].num<<endl;
 cout<<"學生的數學成績排序:   "<<endl;
 for( i=0;i<K;i++)  cout<<pivot[i].Math<<endl;
 cout<<"學生的英語成績排序:   "<<endl;
 for( i=0;i<K;i++)  cout<<pivot[i].English<<endl;
 cout<<"學生的總成績排序:   "<<endl;
 for( i=0;i<K;i++)  cout<<pivot[i].score<<endl;

break;} 

case 5:
	{createHash(H, p,c,K);
	   InsertSort();
break;	}   

default: 
    cout<<"請確認選擇項:\n"; 
}//end switch 
}//end while 


 }