1、航班信息查詢與檢索一、 問題描述 實(shí)現(xiàn)對飛機(jī)航班信息進(jìn)行排序和查找，可按照航班號、起點(diǎn)站、到達(dá)站、起飛時間和到達(dá)時間等信息進(jìn)行查詢。航班信息表的樣式如下：航班號起點(diǎn)站終點(diǎn)站班期起飛時間到達(dá)時間機(jī)型票價CA1544合肥北京1、2、4、510:5512：40733960MU5341上海廣州每日14:2016:15M901280CZ3869重慶深圳2、4、608:5510:357331010其中航班號一項(xiàng)的格式為：前兩個大寫字母表示航空公司的名稱，后4位為航班編號。基本要求： （1）對飛機(jī)航班信息進(jìn)行排序； （2）采用折半查找思想完成查找。可按照航班號、起點(diǎn)站、到達(dá)站、起飛時間和到達(dá)時間等信息進(jìn)行查

2、詢。測試數(shù)據(jù)要求： 測試的數(shù)據(jù)不得少于10個，不得有重復(fù)的航班。 二、 設(shè)計思想根據(jù)題目所要求，程序必須實(shí)現(xiàn)航班信息的錄入和查詢。程序首先定義了一個用于儲存航班信息的數(shù)據(jù)類型，再由用戶錄入航班數(shù)據(jù)，在錄入的同時并對數(shù)據(jù)進(jìn)行排序，最后執(zhí)行數(shù)據(jù)查詢和檢索。在查詢設(shè)計中，使用二分查找法對排好序的航班數(shù)據(jù)按航班號實(shí)現(xiàn)快速查找，按起點(diǎn)站、終點(diǎn)站、起飛時間、到達(dá)時間查找的則采用順序查詢方法。三、 數(shù)據(jù)描述typedef struct node char numberMAXN; /航班號 time start; /起飛時間 time end; /到達(dá)時間 char start_stationMAXN; /起

3、點(diǎn)站 char end_stationMAXN; /終點(diǎn)站 char typeMAXN; /飛機(jī)型號 char priceMAXN; /票價 struct node*link;NODE；四、 算法描述1、二分查找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

4、> 0) low = middle; else i = middle; return i; binSearch(getindex(n,middle),strinput,low,high);int bisect(char a,int n,char sMAXN)/二分查找 int i,j,m; i=0; j=n-1; while(i <=j) m=(i+j)/2; return(-1);2、計算鏈表長度unsigned int countit(NODE* n) unsigned int counti = 0; while(n!=NULL) counti+,n=n->link; r

5、eturn counti;五、 源代碼#include <stdio.h>#include <malloc.h>#include <string.h>#define MAXN 100typedef struct char hourMAXN; char minuteMAXN; time;typedef struct node char numberMAXN; /航班號 time start; /起飛時間 time end; /到達(dá)時間 char start_stationMAXN; /起點(diǎn)站 char end_stationMAXN; /終點(diǎn)站 char ty

6、peMAXN; /飛機(jī)型號 char priceMAXN; /票價 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=0;i <MAXN;i+) head->numberi='0' head->start.houri='0' head->start.minutei='0' head->end.ho

7、uri='0' head->end.minutei='0' head->start_stationi='0' head->end_stationi='0' head->typei='0' head->pricei='0' p=head; for(i=1;i <n;i+) printf("請輸入航班號："); scanf("%s",&(p->number); printf("請輸入起飛時間（時 分）：&

8、quot;); scanf("%s %s",&(p->start.hour),&(p->start.minute); printf("請輸入達(dá)到時間（時 分）："); scanf("%s %s",&(p->end.hour),&(p->end.minute); printf("請輸入起點(diǎn)站 終點(diǎn)站："); scanf("%s %s",&(p->start_station),&(p->end_station); p

9、rintf("請輸入飛機(jī)型號："); 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("請輸入起飛時

10、間（時 分）："); scanf("%s %s",&(p->start.hour),&(p->start.minute); printf("請輸入達(dá)到時間（時 分）："); scanf("%s %s",&(p->end.hour),&(p->end.minute); printf("請輸入起點(diǎn)站 終點(diǎn)站："); scanf("%s %s",&(p->start_station),&(p->end_sta

11、tion); printf("請輸入飛機(jī)型號："); 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; whi

12、le(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 的節(jié)點(diǎn)！ if(num<0 | num>countit(head

13、) 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

14、= middle; return i; binSearch(getindex(n,middle),strinput,low,high);int bisect(char a,int n,char sMAXN)/二分查找 int i,j,m; i=0; j=n-1; while(i <=j) m=(i+j)/2; return(-1);NODE *search1(NODE *head,char vMAXN)/起點(diǎn)站順序查找 for(;head!=NULL&&strcmp(head->start_station,&v0);head=head->link);

15、return(head);NODE *search2(NODE *head,char wMAXN)/到達(dá)站順序查找 for(;head!=NULL&&strcmp(head->end_station,&w0);head=head->link); return(head);NODE *search3(NODE *head,char xMAXN,char yMAXN)/起飛時間順序查找 for(;head!=NULL&&(strcmp(head->start.hour,&x0) | strcmp(head->start.min

16、ute,&y0);head=head->link); return(head);NODE *search4(NODE *head,char tMAXN,char uMAXN)/到達(dá)時間順序查找 for(;head!=NULL&&(strcmp(head->end.hour,&t0) | strcmp(head->end.minute,&u0);head=head->link); return(head);void output(NODE *p) while(p!=NULL) printf("航班信息：n");

17、printf("航班號：%sn",p->number); printf("起飛時間：%s點(diǎn)%s分,",p->start.hour,p->start.minute); printf("到達(dá)時間：%s點(diǎn)%s分n",p->end.hour,p->end.minute); printf("起點(diǎn)站：%s,",p->start_station); printf("到達(dá)站：%sn",p->end_station); printf("飛機(jī)型號：%s "

18、;,p->type); printf("票價：%s元nn",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(

19、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 oMAXN; char sMAXN; char vMAXN; char wMAXN; char xMAXN; char yMAXN; char tMAXN; char uMAXN; for(i=0;i <MAXN;i+) oi='0' si='0' vi=

20、'0' wi='0' xi='0' yi='0' ti='0' ui='0' while(true) printf("【航班信息的查詢與檢索】n"); printf("*n"); printf(" 1.建立航班信息n"); printf(" 2.插入航班信息n"); printf(" 3.按航班號進(jìn)行排序 n"); printf(" 4.航班信息查詢n"); printf(&quo

21、t; 5.顯示航班信息n"); printf(" 0.退出本系統(tǒng)n"); printf("*n"); printf("請輸入你的選擇："); scanf("%d",&a); getchar(); switch(a) case 1: printf("請輸入你所要建立的航班信息個數(shù)："); scanf("%d",&n); p=create_link_list(n); break; case 2: q=create_link_list(1); insert

22、(&p,q); break; case 3: p = rank(p); break; case 4: printf("n1、按照航班號查詢.n"); printf("2、按照起點(diǎn)站查詢.n"); printf("3、按照到達(dá)站查詢.n"); printf("4、按照起飛時間查詢.n"); printf("5、按照到達(dá)時間查詢.n"); scanf("%d",&b); getchar(); switch(b) case 1: p=rank(p); printf(

23、"請輸入您所要找的航班號："); scanf("%s",s); if( binSearch(p,s,1, countit(p) ) printf("scuess!n");break; case 2: printf("請輸入起點(diǎn)站"); scanf("%s",&vMAXN); if(search1(p,&vMAXN)!=NULL) printf("查詢成功!n"); r=search1(p,&vMAXN); output(r); else printf("查詢失敗，該信息錄中沒有該起點(diǎn)站!n"); break; case 3: printf("請輸入到達(dá)站"); scanf("%s&qu