#include
#include
#include
#include
#define?M?450//定義數組的空間為不可改變的整數
using?namespace?std;
int?main（）;//申明主函數
struct?flight//航班信息
{char?terminal[10];//終點站名
char?number[10];//航班號
char?id[10];//飛機號
char?date[10];//飛行日期
int?member;//乘員定額
int?rest;//余票量
struct?flight?*?next;//指向下一個節點的指針
};
struct?custom//客戶信息
{char?name[10];//姓名
char?number[10];//航班號
int?count;//數量
int?grade;//艙位等級
struct?custom?*?next;//指向下一個節點的指針
};
struct?flight?*a[M];//flight類型的指針數組
struct?node//二叉樹節點
{?struct?custom?*?base;??
???node?*r;//左孩子
???node?*l;//右孩子
};?
char?ch[100];
int?judge（char?（&ch）[100]）
?{
????int?is=0x=0;
????if（strlen（ch）==3）
	{for（i=0;i????{
????if（ch[i]>=‘0‘&&ch[i]<=‘9‘）
????s++;
????}
????if（s==strlen（ch））
	{for（i=0;i	x=x*10+ch[i]-48;
	return?x;
	}
????else
????return?0;
	}
	else?return?0;
?}
int?hash（unsigned?long?k）
{return?k%M;}//取余
unsigned?long?hashvalue（char?*str）//將輸入字符串轉換成長整型數返回
{int?il;?
unsigned?long?ret=0;?
unsigned?short?*s;?
if?（str?==?NULL）?return（0）;?
l=（strlen（str）+1）/2;?
s=（unsigned?short?*）str;?
for?（i=0;?iret^=（s[i]<<（i&0x0f））;?
return（ret）;?
}?
void?hashlist（）//建立哈希表
{fstream?obj;
flight?*s=new?flight*t=new?flight;
int?i=0val;
obj.open（“d:\\fly.txt“ios::in）;//打開航班信息的文件
while（obj>>s->terminal>>s->number>>s->id>>s->date>>s->member>>s->rest）//提取文件信息
{val=hash（hashvalue（s->terminal））;
while（a[hash（val）]!=NULL）//如果數組中的元素不為空，建立鏈表
{if（!strcmp（a[hash（val）]->terminals->terminal））
{t=a[hash（val）];
while（t->next）//將節點往下移，直至最后節點
{t=t->next;}
t->next=s;
t=s;
t->next=NULL;//末尾節點的next賦空
break;
}
else?val++;//哈希表沖突，往數組后面的空位移動
}
if（a[hash（val）]==NULL）//如果哈希表中元素為空，賦給從文件中提取的值
{a[hash（val）]=s;
a[hash（val）]->next=NULL;}
s=new?flight;
}
obj.close（）;//關閉文件
}
void?create（node?*&rootcustom?*&s）?//生成二分查找樹
{?custom?*t=new?custom;
	if（root==NULL）??//當該節點為空時賦值
????{???root=new?node;??
????????root->base=s;
????????root->l=NULL;??
????????root->r=NULL;?
????}??
else?if（hash（hashvalue（s->name））>hash（hashvalue（root->base->name）））
create（root->rs）;?//比當前節點小，往左孩子移
else?if（hash（hashvalue（s->name））base->name）））??
create（root->ls）;?//比當前節點大，往右孩子移
else?//等于當前節點
{t=root->base;
while（t->next!=NULL）//將節點往下移，直至最后節點
t=t->next;
t->next=s;//到尾部添加形成線性表
t=s;
t->next=NULL;//末尾節點的next賦空
}
}
void?print（node?*&rootchar?*&name）//輸出要查找的值
{custom?*t=new?custom;
if（root!=NULL）//如果節點不為空
{if（root->l!=NULL?&&?hash（hashvalue（name））base->name）））
print（root->lname）;//比當前節點小
else?if（root->r!=NULL?&&?hash（hashvalue（name））>hash（hashvalue（root->base->name）））
print（root->rname）;//比當前節點大
else?if（hash（hashvalue（name））==hash（hashvalue（root->base->name）））//等于當前節點
{t=root->base;
cout<	“票量“<while（t!=NULL）//輸出找到的線性表
{cout<