航班.cpp

航班的信息系统

#include <stdio.h>
#include <string.h>
#define MaxSpace 100
#define keylen 6
#define Radix_n 10
#define Radix_c 26
typedef char KeyType;
typedef struct 
{
    char start[6];        /*起点*/
    char end[6];          /*终点*/
    char sche[10];         /*斑期*/
    char time1[5];        /*起飞时间*/
    char time2[5];        /*到达时间*/
    char model[4];        /*机型*/
    int price;            /*标价*/
}InfoType;                /*航班记录类型*/

typedef struct
{
    KeyType keys[keylen];      /*航班号*/
    InfoType others;
    int next;
}SLNode;                     /*静态链表接点类型*/

typedef struct
{
    SLNode sl[MaxSpace];
    int keynum;                   /*静态链表，sl[0]为头结点*/
    int length;                   /*当前表长*/
}SLList;                          /*静态链表类型*/
typedef int ArrType_n[Radix_n];   /*十进制数字指针数组*/
typedef int ArrType_c[Radix_c];   /*26个字母指针数组*/

/*一趟数字字符分配函数*/
void Distribute(SLNode *sl,int i,ArrType_n f,ArrType_n e)
{
    int j,p;
    for(j=0;j<Radix_n;j++)
    {  /*各子表置为空表*/
        f[j]=e[j]=0;
    }
    for(p=sl[0].next;p;p=sl[p].next)
    {
        j=sl[p].keys[i]%48;         /*将数字字符转换成相对应的数值型数字*/
        if(!f[j])
            f[j]=p;
        else
            sl[e[j]].next=p;
            e[j]=p;                /*将p指向的结点插入到第j个子表中*/
    }
}

/*一趟数字字符的收集函数*/
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+1;j<Radix_n-1 && !f[j];j++);      /*找下一个非空子表*/
            if(f[j])
            {
                 sl[t].next=f[j];
                 t=e[j];                              /*链接两个非空子表*/
            }
        }
        sl[t].next=0;              /*t指向最后一个非空子表中的最后一个结点*/
}

/*一趟字母字符分配函数*/
void Distribute_c(SLNode *sl,int i,ArrType_c f,ArrType_c e)
{
    int j,p;
    for(j=0;j<Radix_c;j++)
    {   /*各子表置为空表*/
        f[j]=e[j]=0;
    }
    for(p=sl[0].next;p;p=sl[p].next)
    {
        j=sl[p].keys[i]%65;      /*将字母字符转换成在字母集中相应的序号（0－25）*/
        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+1;j<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=0;i<L.length;i++)
        L.sl[i].next=i+1;            /*0号单元公存放指针，不存储内容*/
        L.sl[L.length].next=0;       /*将普通的线性表改造为静态链表*/
    for(i=L.keynum-1;i>=2;i--)
    {  /*按最低优先次序对各关键字进行分配和收集，先做低4位数字部分*/
        Distribute(L.sl,i,fn,en);
        Collect(L.sl,i,fn,en);
    }
    for(i=1;i>=0;i--)
    {  /*对高位的2位大写字母进行分配和收集*/     
        Distribute_c(L.sl,i,fc,ec);
        Collect_c(L.sl,i,fc,ec);
    }
}/*RadixSort*/

/*按指针链重新整理静态链表*/
void Arrange(SLList &L)
{
    int p,q,i;
    SLNode temp;
    p=L.sl[0].next;             /*p指向第一个记录的当前位置*/
    for(i=1;i<L.length;i++)     /*L.sl[1..i-1]已按关键字有序化*/
    {
        while(p<i)
            p=L.sl[p].next;        /*找到第i个记录，并用p指向其在L中当前位置*/
            q=L.sl[p].next;        /*q指向尚未调整的表尾*/
        if(p!=i)
        {
            temp=L.sl[p]; L.sl[p]=L.sl[i]; L.sl[i]=temp;       /*交换记录*/
            L.sl[i].next=p;
        }
        p=q;            /*p指向尚未调整的表尾，为找第i+1个记录做准备*/
    }
}/*Arrange*/

/*二分查找函数*/
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;
}/*BinSearch*/

/*顺序查找函数*/
void SeqSearch(SLList L,KeyType key[],int i)
{
    int j,k,m=0;
    printf("***********************************************************\n");
    printf("* 航班号 起点站 终点站 航班期 起飞时间 到达时间   机型  票价 *\n");
    for(j=1;j<=L.length;j++)
    {
        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);
        ++i; getchar(); 
        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);             /*输入航班记录*/
    printf("排序之后:\n");
    for(int i=1;i<=L.length;i++)
    {
	printf("航班号 起点站 终点站 航班期 起飞时间 到达时间   机型  票价\n");
	printf("%-8s%-7s%-6s%-11s%-9s%-7s%-5s%d\n",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);	
    }
	printf("总共:%d",i-1);

    searchcon(L);             /*查询菜单控制程序*/
}