公交路线查询系统（基于数据结构和C语言）#include#include#include#include#define max 30#define len 20#define MAX 100typedef struct Linedot{//站int stopno;//站号char stopname[max];//站名struct Linedot *next;}linedot,*dot;typedef struct lineway{//线路int lineNo;//线路号int stopnum;//该线路上站的个数dot stop;//站}way;typedef struct lineNode{int linenum;//线路条数way data[len];//线路}line;typedef struct co_Node{int zhanNo;int busNo;struct co_Node *next;}co_node,*co_zhan;typedef struct Node{int firstbus;//始发车号char stopname[max];//站名co_zhan zhan;}node,*list;typedef struct zhanNode{int vexnum;//顶点数int arcnum;//弧数node vexs[max];//顶点}spot;typedef struct sqNode//定义双向队列{int data;struct sqNode *prior;struct sqNode *next;}sqnode,*sqlist;typedef struct//双向链队列类型{sqlist front;sqlist rear;}LQ;void initqueue(LQ *Q)//初始化队列{Q->front=Q->rear=new sqnode;Q->front->data=Q->rear->data=-1;Q->front->next=Q->rear->next=NULL; Q->front->prior=Q->rear->prior=NULL; }void enqueue(LQ *Q,int e)//进队{sqlist p;p=new sqnode;p->data=e;p->next=NULL;p->prior=Q->front;Q->rear->next=p;Q->rear=p;}void dequeue(LQ *Q,int *e)//出队{Q->front=Q->front->next;if(Q->front!=NULL)*e=Q->front->data;else*e=-1;}typedef struct stackNode//定义栈{int figuer;struct stackNode *next;}stacknode,*stack;void initstack(stack *S)//初始化栈{*S=NULL;}void push(stack *S,int e)//进栈{stack p;p=new stacknode;p->figuer=e;p->next=*S;*S=p;}int pop(stack *S,int *e)//出栈{stack p=*S;if(p==NULL){printf("栈空!\n");return 0;}*e=p->figuer;*S=(*S)->next;delete p;return 1;}void gettop(stack S,int *e)//得到栈顶{if(S==NULL){printf("栈空!\n");return;}*e=S->figuer;}int locate(spot C,char e[]){int i;for(i=0;i<c.vexnum;i++){if(strcmp(C.vexs[i].stopname,e)==0)return i;}if(i>C.vexnum){printf("Not found!\n");return -1;}}void init(FILE *fp,line *W,spot *C)//公交线路初始化{dot p,q;co_zhan R;int i,j,m,n,num;char vex1[max],vex2[max];if((fp=fopen("f.txt","r"))==NULL)//打开文件{printf("The file error!\n");getchar();exit(0);}fscanf(fp,"%d",&W->linenum);for(i=0;ilinenum;i++)fscanf(fp,"%d%d",&W->data[i].lineNo,&W->data[i].stopnu m);//输入线路号和该线路上站的个数for(i=0;ilinenum;i++){W->data[i].stop=NULL;for(j=0;jdata[i].stopnum;j++){p=new linedot;p->next=NULL;fscanf(fp,"%d%s",&p->stopno,p->stopname);//输入站名q=W->data[i].stop;if(!q)W->data[i].stop=p;else{while(q->next)q=q->next;</c.vexnum;i++)q->next=p;}}}fscanf(fp,"%d%d",&C->vexnum,&C->arcnum);for(i=0;ivexnum;i++){fscanf(fp,"%s%d",C->vexs[i].stopname,&C->vexs[i].firstbus); C->vexs[i].zhan=NULL;}for(i=0;iarcnum;i++){fscanf(fp,"%s%s%d",vex1,vex2,&num);m=locate(*C,vex1);n=locate(*C,vex2);R=new co_node;R->zhanNo=n;R->busNo=num;R->next=C->vexs[m].zhan;C->vexs[m].zhan=R;}}void search1(line W)//查询指定车次的线路及途经站点{dot p;int i,n,k=0;printf("请输入车次:");scanf("%d",&n);for(i=0;i<w.linenum;i++){if(W.data[i].lineNo==n){p=W.data[i].stop;while(p){if(k==0)printf("%s",p->stopname);elseprintf("->%s",p->stopname);p=p->next;k++;}}}}void search2(line W,spot C){int k,i;char vex[max];dot p;printf("请输入站点名:");scanf("%s",vex);k=locate(C,vex);if(C.vexs[k].firstbus!=0)printf("该站点的始发车有:%d\n",C.vexs[k].firstbus); elseprintf("该站无始发车!\n");printf("该站点的过路车有:");for(i=0;i<w.linenum;i++)p=W.data[i].stop;if(!p)continue;while(p){if(strcmp(p->stopname,vex)==0&&p!=W.data[i].stop) printf("%d ",W.data[i].lineNo);p=p->next;}}}int stackempty(stack S){if(S==NULL)return 1;return 0;}void updown(stack S,stack *S1){stack p;while(!stackempty(S)){p=new stacknode;p->figuer=S->figuer;p->next=*S1;*S1=p;S=S->next;}void printstack(spot C,stack S)//打印栈里的元素{stack S1,p;co_zhan q;initstack(&S1);updown(S,&S1);p=S1;while(p){ q=C.vexs[p->figuer].zhan;while(q){if(p->next==NULL)break;if(q->zhanNo!=p->next->figuer)q=q->next;elsebreak;}printf("%s-%d->",C.vexs[p->figuer].stopname,q->busNo); p=p->next;}}void printqueue(sqlist Q,spot C){sqlist p;stack S,S1;initstack(&S);initstack(&S1);p=Q;while(p->data!=-1){push(&S,p->data);p=p->prior;}updown(S,&S1);printstack(C,S1);}void search3(spot C,int s,int e) {co_zhan p;int flag;LQ Q;sqlist q;int u,k,i=1;initqueue(&Q);enqueue(&Q,s);while(Q.front!=Q.rear){dequeue(&Q,&u);p=C.vexs[u].zhan;if(u==e){printf("-->>Line%d:",i++); printqueue(Q.front->prior,C); printf("%s\n",C.vexs[e].stopname);dequeue(&Q,&u);if(u==-1)break;p=C.vexs[u].zhan;}while(p){k=p->zhanNo;q=Q.front;while(q->prior!=NULL){if(q->data!=k){q=q->prior;flag=1;}else{flag=0;break;}}if(k!=s&&flag==1)enqueue(&Q,k);p=p->next;}}}void search4(spot C,int s,int e,LQ *Q,int visit[]){int u,k;co_z</w.linenum;i++)</w.linenum;i++)han p;if(!visit[s]){visit[s]=1;enqueue(Q,s);while(Q->front!=Q->rear){dequeue(Q,&u);p=C.vexs[u].zhan;if(u==e){printf("-->>Line:");printqueue(Q->front->prior,C); printf("%s\n",C.vexs[e].stopname); break;}while(p){k=p->zhanNo;if(!visit[k]){visit[k]=1;enqueue(Q,k);}}}}}int count(spot C,stack S,int e){int i,j,n=0,No=-1;stack p;co_zhan q;p=S;while(p){i=p->figuer;p=p->next;if(!p)break;j=p->figuer;q=C.vexs[i].zhan;while(q){if(q->zhanNo==j&&q->busNo!=No) {n++;No=q->busNo;break;}else}}return n-1;}void destroy(stack *S){stack p=*S;while(!stackempty(*S)){*S=(*S)->next;delete(p);p=*S;}}void savestack(stack S,stack *S2) {stack S1;initstack(&S1);updown(S,&S1);updown(S1,S2);}void change(sqlist Q,stack *S) {sqlist p;p=Q;while(p->data!=-1){push(S,p->data);p=p->prior;}}void search5(spot C,int s,int e,stack *S,stack *S2,int *m) {co_zhan p;int flag;LQ Q;sqlist q;int u,k,n1,n=MAX,i=1;initqueue(&Q);enqueue(&Q,s);while(Q.front!=Q.rear){dequeue(&Q,&u);p=C.vexs[u].zhan;if(u==e){change(Q.front,S);n1=count(C,*S,e);if(n1<n){savestack(*S,S2);n=n1;*m=n;}destroy(S);dequeue(&Q,&u);if(u==-1)break;p=C.vexs[u].zhan;}while(p){k=p->zhanNo;q=Q.front;while(q->prior!=NULL) {if(q->data!=k){q=q->prior;flag=1;}else{flag=0;break;}}if(k!=s&&flag==1) enqueue(&Q,k);p=p->next;}}}int menu(){int n;printf("*******************欢迎使用K城公交查询系统******************\n");printf("**************1.查询指定车次的线路及途经站点****************\n");printf("**************2.查询指定站点的始发车和过路车****************\n");printf("**************3.查询指定起点和终点所经的所有线路************\n");printf("**************4.查询指定起点和终点所经站点最少的线路********\n");printf("**************5.查询指定起点和终点换乘次数最少的乘车路线****\n");printf("**************0.退出****************************************\n");printf("******************************************************* *****\n");printf("-----起点站:电力大学/朱辛庄/北郊农场桥东/京昌路回龙观/北京师\n");printf(" 范大学/德胜门西/清华大学西门/圆明园/颐和园/香山\n");printf("-----终点站:电力大学/朱辛庄/北郊农场桥东/京昌路回龙观/北京师\n");printf(" 范大学/德胜</n)门西/清华大学西门/中关村/圆明园/颐和园\n");printf(" /西单\n");printf("-----公交线路:345/442/696/681/699/826\n");printf("******************************************************* *****\n");printf("请选择:");scanf("%d",&n);getchar();return n;}void main(){stack S,S2,S3;LQ Q;int n,m,i,s,e,k=1,visit[len],u; char ch='Y',start[max],end[max]; FILE *fp;line W;spot C;init(fp,&W,&C);do{n=menu();switch(n){case 1:search1(W);break;case 2:search2(W,C);break; case 3:for(i=0;i<len;i++)visit[i]=0;initstack(&S);printf("请输入起点和终点:"); scanf("%s%s",start,end);s=locate(C,start);e=locate(C,end);printf("%s到%s的所有路线如下:\n",C.vexs[s].stopname,C.vexs[e].stopname);search3(C,s,e);break;case 4:for(i=0;i<len;i++)visit[i]=0;initqueue(&Q);printf("请输入起点和终点:");scanf("%s%s",start,end);s=locate(C,start);e=locate(C,end);printf("%s到%s的最短路线如下:\n",C.vexs[s].stopname,C.vexs[e].stopname);search4(C,s,e,&Q,visit);break;case 5:initstack(&S);initstack(&S2);initstack(&S3);printf("请输入起点和终点:");scanf("%s%s",start,end);s=locate(C,start);e=locate(C,end);printf("%s到%s的最少换乘路线如下:\n",C.vexs[s].stopname,C.vexs[e].stopname);search5(C,s,e,&S,&S2,&m);updown(S2,&S3);pop(&S3,&u);printf("-->>Line:");printstack(C,S3);printf("%s\n",C.vexs[e].stopname); printf("共换乘%d次\n",m);break; case 0:exit(0);break;default:printf("error!\n");}getchar();printf("\n继续吗？Y/N:");scanf("%c",&ch);}while(ch=='Y'||ch=='y');}</len;i++)</len;i++)。
