#include "malloc.h"
#include "string.h"
#define MAXN 100
typedef struct{
char hour[MAXN]
char minute[MAXN]
} time
typedef struct node
{
char number[MAXN] //航班号
time start //起飞时间
time end //到达时间
char start_station[MAXN] //起点站
char end_station[MAXN] //终点站
char type[MAXN]//飞机型号
char price[MAXN]//票价
struct node*link
}NODE
NODE *create_link_list(int n)
{
int i
NODE *head,*p,*q
if(n==0)return(NULL)
head=(NODE*)malloc(sizeof(NODE))
for(i=0i <MAXNi++)
{
head->number[i]='\0'
head->start.hour[i]='\0'
head->start.minute[i]='\0'
head->end.hour[i]='\0'
head->end.minute[i]='\0'
head->start_station[i]='\0'
head->end_station[i]='\0'
head->type[i]='\0'
head->price[i]='\0'
}
p=head
for(i=1i <ni++)
{
printf("请输入航班号：")
scanf("%s",&(p->number))
printf("请输入起飞时间（时 分）：")
scanf("%s %s",&(p->start.hour),&(p->start.minute))
printf("请输入达到时间（时 分）：")
scanf("%s %s",&(p->end.hour),&(p->end.minute))
printf("请输入起点站 终点站：")
scanf("%s %s",&(p->start_station),&(p->end_station))
printf("请输入飞机型号：")
scanf("%s",&(p->type))
printf("请输入票价：")
scanf("%s",&(p->price))
printf("\n")
q=(NODE*)malloc(sizeof(NODE))
p->link=q
p=q
}
printf("请输入航班号：")
scanf("%s",&(p->number))
printf("请输入起飞时间（时 分）：")
scanf("%s %s",&(p->start.hour),&(p->start.minute))
printf("请输入达到时间（时 分）：")
scanf("%s %s",&(p->end.hour),&(p->end.minute))
printf("请输入起点站 终点站：")
scanf("%s %s",&(p->start_station),&(p->end_station))
printf("请输入飞机型号：")
scanf("%s",&(p->type))
printf("请输入票价：")
scanf("%s",&(p->price))
printf("\n")
getchar()
p->link=NULL
return(head)
}
void insert(NODE **p_head,NODE *q)
{
NODE *p
if(*p_head==NULL)
*p_head=q
else
{
p=*p_head
while(p!=NULL&&p->link!=NULL)
p=p->link
p->link=q
}
}
unsigned int countit(NODE* n)//计算链表长度
{
unsigned int counti = 0
while(n!=NULL)
counti++,n=n->link
return counti
}
NODE* getindex(NODE* head, int num)
NODE* getindex(NODE* head, int num)//取得index为num 的节点！
{
if(num<0 || num>countit(head))
return NULL
NODE* rn = head
while(--num>0)
rn = rn->link
return rn
}
int binSearch(NODE* n,char *strinput,int low, int high)// 二分查找
{
int i
int middle = (high+low)/2
if (high <low)
return 0
if ((i=strcmp(strinput, n->number)) <0)
high= middle
else if (i >0)
low = middle
else
{
i = middle
return i
}
binSearch(getindex(n,middle),strinput,low,high)
}
int bisect(char a[],int n,char s[MAXN])//二分查找
{
int i,j,m
i=0
j=n-1
while(i <=j)
{
m=(i+j)/2
}
return(-1)
}
NODE *search1(NODE *head,char v[MAXN])//起点站顺序查找
{
for(head!=NULL&&strcmp(head->start_station,&v[0])head=head->link)
return(head)
}
NODE *search2(NODE *head,char w[MAXN])//到达站顺序查找
{
for(head!=NULL&&strcmp(head->end_station,&w[0])head=head->link)
return(head)
}
NODE *search3(NODE *head,char x[MAXN],char y[MAXN])//起飞时间顺序查找
{
for(head!=NULL&&(strcmp(head->start.hour,&x[0]) || strcmp(head->start.minute,&y[0]))head=head->link)
return(head)
}
NODE *search4(NODE *head,char t[MAXN],char u[MAXN])//到达时间顺序查找
{
for(head!=NULL&&(strcmp(head->end.hour,&t[0]) || strcmp(head->end.minute,&u[0]))head=head->link)
return(head)
}
void output(NODE *p)
{
while(p!=NULL)
{
printf("航班信息：\n")
printf("航班号：%s\n",p->number)
printf("起飞时间：%s点%s分,",p->start.hour,p->start.minute)
printf("到达时间：%s点%s分\n",p->end.hour,p->end.minute)
printf("起点站：%s,",p->start_station)
printf("到达站：%s\n",p->end_station)
printf("飞机型号：%s ",p->type)
printf("票价：%s元\n\n",p->price)
p=p->link
}
}
NODE *rank( NODE *head)
{
NODE *q=0,*p=0,*t,*h1
h1=head->link
head->link=NULL
while(h1!=NULL)
{
t=h1
h1=h1->link
p=head
q=head
while( p!=NULL &&strcmp(t->number, p->number)>0 )
{
q=p
p=p->link
}
if(q == p)
{
t->link=p
head=t
}
else
{
t->link=p
q->link=t
}
}
return head
}
int main(int argc, char* argv[])
{
NODE *p,*q,*r
int a,b,i,j,n
int count=0
char o[MAXN]
char s[MAXN]
char v[MAXN]
char w[MAXN]
char x[MAXN]
char y[MAXN]
char t[MAXN]
char u[MAXN]
for(i=0i <MAXNi++)
{
o[i]='\0'
s[i]='\0'
v[i]='\0'
w[i]='\0'
x[i]='\0'
y[i]='\0'
t[i]='\0'
u[i]='\0'
}
while(true)
{
printf("【航班信息的查询与检索】\n")
printf("★*******************************★\n")
printf(" 1.建立航班信息\n")
printf(" 2.插入航班信息\n")
printf(" 3.按航班号进行排序 \n")
printf(" 4.航班信息查询\n")
printf(" 5.显示航班信息\n")
printf(" 6.退出本系统\n")
printf("★*******************************★\n")
scanf("%d",&a)
getchar()
switch(a)
{
case 1:
printf("请输入你所要建立的航班信息个数：")
scanf("%d",&n)
p=create_link_list(n)
break
case 2:
q=create_link_list(1)
insert(&p,q)
break
case 3:
p = rank(p)
break
case 4:
printf("\n1、按照航班号查询.\n")
printf("2、按照起点站查询.\n")
printf("3、按照到达站查询.\n")
printf("4、按照起飞时间查询.\n")
printf("5、按照到达时间查询.\n")
scanf("%d",&b)
getchar()
switch(b)
{
case 1:
p=rank(p)
printf("请输入您所要找的航班号：")
scanf("%s",s)
if( binSearch(p,s,1, countit(p)) )
printf("scuess!\n")
break
case 2:
printf("请输入起点站")
scanf("%s",&v[MAXN])
if(search1(p,&v[MAXN])!=NULL)
{
printf("查询成功!\n")
r=search1(p,&v[MAXN])
output(r)
}
else
printf("查询失败，该信息录中没有该起点站!\n")
break
case 3:
printf("请输入到达站")
scanf("%s",&w[MAXN])
if(search2(p,&w[MAXN])!=NULL)
{
printf("查询成功!\n")
r=search2(p,&w[MAXN])
output(r)
}
else
printf("查询失败，该信息录中没有该到达站!\n")
break
case 4:
printf("请输入起飞时间(时 分)")
scanf("%s %s",&x[MAXN],&y[MAXN])
if(search3(p,&x[MAXN],&y[MAXN])!=NULL)
{
printf("查询成功!\n")
r=search3(p,&x[MAXN],&y[MAXN])
output(r)
}
else
printf("查询失败，该信息录中没有该到达站!\n")
break
case 5:
printf("请输入到达时间")
scanf("%s %s",&t[MAXN],&u[MAXN])
if(search4(p,&t[MAXN],&u[MAXN])!=NULL)
{
printf("查询成功!\n")
r=search4(p,&t[MAXN],&u[MAXN])
output(r)
}
else
printf("查询失败，该信息录中没有该到达站!\n")
break
}
break
case 5:
output(p)
printf("\n")
break
case 6:
return(0)
}
}
return(0)
}
void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e){
int j,p
for(j=0j<radix_nj++)
{
f[j]=e[j]=0
}
for(p=sl[0].nextpp=sl[p].next)
{
j=sl[p].keys[i]%48
if(!f[j])
f[j]=p
else
sl[e[j]].next=p
e[j]=p
}
}
void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)
{
int j,t
for(j=0!f[j]j++)
sl[0].next=f[j]
t=e[j]
while(j<radix_n-1)
{
for(j=j+1j<radix_n-1&&!f[j]j++)
if(f[j])
{
sl[t].next=f[j]
t=e[j]
}
}
sl[t].next=0
}
void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)
{
int j,p
for(j=0j<radix_cj++)
{
f[j]=e[j]=0
}
for(p=sl[0].nextpp=sl[p].next)
{
j=sl[p].keys[i]%65
if(!f[j])
f[j]=p
else
sl[e[j]].next=p
e[j]=p
}
}
void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e)
{
int j,t
for(j=0!f[j]j++)
sl[0].next=f[j]
t=e[j]
while(j<radix_c-1)
{
for(j=j+1j<radix_c-1&&!f[j]j++)
if(f[j])
{
sl[t].next=f[j]
t=e[j]
}
}
sl[t].next=0
}
void radixsort(sllist &l)//链式
{
int i
arrtype_n fn,en
arrtype_c fc,ec
for(i=0i<l.lengthi++)
l.sl[i].next=i+1
l.sl[l.length].next=0
for(i=l.keynum-1i>=2i--)
{
distribute(l.sl,i,fn,en)
collect(l.sl,i,fn,en)
}
for(i=1i>=0i--)
{
distribute_c(l.sl,i,fc,ec)
collect_c(l.sl,i,fc,ec)
}
}
void arrange(sllist &l)//重新整理
{
int p,q,i
slnode temp
p=l.sl[0].next
for(i=1i<l.lengthi++)
{
while(p<i)
p=l.sl[p].next
q=l.sl[p].next
if(p!=i)
{
temp=l.sl[p]
l.sl[p]=l.sl[i]
l.sl[i]=temp
l.sl[i].next=p
}
p=q
}
}
int binsearch(sllist l,keytype key[])
{
int low,high,mid
low=1
high=l.length
while(low<=high)
{
mid=(low+high)/2
if(strcmp(key,l.sl[mid].keys)==0)
return mid
else if(strcmp(key,l.sl[mid].keys)<0)
high=mid-1
else
low=mid+1
}
return 0
}
void seqsearch(sllist l,keytype key[],int i)
{
int j,k,m=0
printf("*************************************************************\n")
printf("* 航班号 起始站 终点站 航班期 起飞时间 到达时间 机型 票价*\n")
for(j=1j<=l.lengthj++)
{
switch(i)
{
case 2:k=strcmp(key,l.sl[j].others.start)break
case 3:k=strcmp(key,l.sl[j].others.end)break
case 4:k=strcmp(key,l.sl[j].others.time1)break
case 5:k=strcmp(key,l.sl[j].others.time2)break
}
if(k==0)
{
m=1
printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *\n",l.sl[j].keys,l.sl[j].others.start,l.sl[j].others.end,l.sl[j].others.sche,l.sl[j].others.time1,l.sl[j].others.time2,l.sl[j].others.model,l.sl[j].others.price)
}
}
if(m==0)
printf("* 无此航班信息，可能是输入错误*\n")
printf("*************************************************************\n")
}
void searchcon(sllist l)
{
keytype key[keylen]
int i=1,k
while(i>=1&&i<=5)
{printf("\n ********************\n")
printf(" * 航班信息查询系统 *\n")
printf(" ********************\n")
printf(" * 1.航班号*\n")
printf(" * 2.起点站*\n")
printf(" * 3.终点站*\n")
printf(" * 4.起飞时间*\n")
printf(" * 5.到达时间*\n")
printf(" * 0.退出系统*\n")
printf(" ********************\n")
printf(" 请选择(0-5):")
scanf("%d",&i)
printf("\n")
switch(i)
{case 1:printf("输入要查询的航班号（字母要大写）:")
scanf("%s",key)
k=binsearch(l,key)
printf("*************************************************************\n")
if(k==0)
printf("* 无此航班信息，可能是输入错误！*\n")
else
{
printf("* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价*\n")
printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *\n",l.sl[k].keys,l.sl[k].others.start,l.sl[k].others.end,l.sl[k].others.sche,l.sl[k].others.time1,l.sl[k].others.time2,l.sl[k].others.model,l.sl[k].others.price)
}
printf("*************************************************************\n")
break
case 2:printf("输入要查询的航班起点站名:")
scanf("%s",key)
seqsearch(l,key,i)
break
case 3:printf("输入要查询的航班起点站名:")
scanf("%s",key)
seqsearch(l,key,i)
break
case 4:printf("输入要查询的航班起点站名:")
scanf("%s",key)
seqsearch(l,key,i)
break
case 5:printf("输入要查询的航班起点站名:")
scanf("%s",key)
seqsearch(l,key,i)
break
case 0:printf("\n\n\n 再 见n\n\n")
}
}
}
void inputdata(sllist &l)
{
int i=++l.length
char yn='y'
while(yn=='y'||yn=='Y')
{
printf("航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价\n")
scanf("%s%s%s%s%s%s%s%d",l.sl[i].keys,l.sl[i].others.start,l.sl[i].others.end,l.sl[i].others.sche,l.sl[i].others.time1,l.sl[i].others.time2,l.sl[i].others.model,&l.sl[i].others.price)
++igetchar()
radixsort(l)
arrange(l)
printf("继续输入吗?y/n:")
scanf("%c",&yn)
}
l.length=i-1
}
void main()
{
sllist l
l.keynum=6
l.length=0
inputdata(l)
searchcon(l)
}
