|
#2
lsnaimei2012-04-11 19:53
#include<stdio.h>
#include<stdlib.h> #include<string.h> #include<process.h> #define max 30 #define len 20 #define MAX 100 typedef 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;i<W->linenum;i++) fscanf(fp,"%d%d",&W->data[i].lineNo,&W->data[i].stopnum);//输入线路号和该线路上站的个数 for(i=0;i<W->linenum;i++) { W->data[i].stop=NULL; for(j=0;j<W->data[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; q->next=p; } } } fscanf(fp,"%d%d",&C->vexnum,&C->arcnum); for(i=0;i<C->vexnum;i++) { fscanf(fp,"%s%d",C->vexs[i].stopname,&C->vexs[i].firstbus); C->vexs[i].zhan=NULL; } for(i=0;i<C->arcnum;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); else printf("->%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); else printf("该站无始发车!\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; else break; } 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_zhan 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); } p=p->next; } } } } 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 q=q->next; } } 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"); 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'); } |
同上,希望各位大虾赐教