搜索
#includestdio.h#includestdlib.h#includestring.h#includeprocess.h#definemax30#definelen20#defineMAX100typedefstructLinedot{//站intstopno;//站号charstopname[max];//站名structLinedot*next;}linedot,*dot;typedefstructlineway{//线路intlineNo;//线路号intstopnum;//该线路上站的个数dotstop;//站}way;typedefstructlineNode{intlinenum;//线路条数waydata[len];//线路}line;typedefstructco_Node{intzhanNo;intbusNo;structco_Node*next;}co_node,*co_zhan;typedefstructNode{intfirstbus;//始发车号charstopname[max];//站名co_zhanzhan;}node,*list;typedefstructzhanNode{intvexnum;//顶点数intarcnum;//弧数nodevexs[max];//顶点}spot;typedefstructsqNode//定义双向队列{intdata;structsqNode*prior;structsqNode*next;}sqnode,*sqlist;typedefstruct//双向链队列类型{sqlistfront;sqlistrear;}LQ;voidinitqueue(LQ*Q)//初始化队列{Q-front=Q-rear=newsqnode;Q-front-data=Q-rear-data=-1;Q-front-next=Q-rear-next=NULL;Q-front-prior=Q-rear-prior=NULL;}voidenqueue(LQ*Q,inte)//进队{sqlistp;p=newsqnode;p-data=e;p-next=NULL;p-prior=Q-front;Q-rear-next=p;Q-rear=p;}voiddequeue(LQ*Q,int*e)//出队{Q-front=Q-front-next;if(Q-front!=NULL)*e=Q-front-data;else*e=-1;}typedefstructstackNode//定义栈{intfiguer;structstackNode*next;}stacknode,*stack;voidinitstack(stack*S)//初始化栈{*S=NULL;}voidpush(stack*S,inte)//进栈{stackp;p=newstacknode;p-figuer=e;p-next=*S;*S=p;}intpop(stack*S,int*e)//出栈{stackp=*S;if(p==NULL){printf(栈空!\n);return0;}*e=p-figuer;*S=(*S)-next;deletep;return1;}voidgettop(stackS,int*e)//得到栈顶{if(S==NULL){printf(栈空!\n);return;}*e=S-figuer;}intlocate(spotC,chare[]){inti;for(i=0;iC.vexnum;i++){if(strcmp(C.vexs[i].stopname,e)==0)returni;}if(iC.vexnum){printf(Notfound!\n);return-1;}}voidinit(FILE*fp,line*W,spot*C)//公交线路初始化{dotp,q;co_zhanR;inti,j,m,n,num;charvex1[max],vex2[max];if((fp=fopen(f.txt,r))==NULL)//打开文件{printf(Thefileerror!\n);getchar();exit(0);}fscanf(fp,%d,&W-linenum);for(i=0;iW-linenum;i++)fscanf(fp,%d%d,&W-data[i].lineNo,&W-data[i].stopnum);//输入线路号和该线路上站的个数for(i=0;iW-linenum;i++){W-data[i].stop=NULL;for(j=0;jW-data[i].stopnum;j++){p=newlinedot;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;iC-vexnum;i++){fscanf(fp,%s%d,C-vexs[i].stopname,&C-vexs[i].firstbus);C-vexs[i].zhan=NULL;}for(i=0;iC-arcnum;i++){fscanf(fp,%s%s%d,vex1,vex2,&num);m=locate(*C,vex1);n=locate(*C,vex2);R=newco_node;R-zhanNo=n;R-busNo=num;R-next=C-vexs[m].zhan;C-vexs[m].zhan=R;}}voidsearch1(lineW)//查询指定车次的线路及途经站点{dotp;inti,n,k=0;printf(请输入车次:);scanf(%d,&n);for(i=0;iW.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++;}}}}voidsearch2(lineW,spotC){intk,i;charvex[max];dotp;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;iW.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;}}}intstackempty(stackS){if(S==NULL)return1;return0;}voidupdown(stackS,stack*S1){stackp;while(!stackempty(S)){p=newstacknode;p-figuer=S-figuer;p-next=*S1;*S1=p;S=S-next;}}voidprintstack(spotC,stackS)//打印栈里的元素{stackS1,p;co_zhanq;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;}}voidprintqueue(sqlistQ,spotC){sqlistp;stackS,S1;initstack(&S);initstack(&S1);p=Q;while(p-data!=-1){push(&S,p-data);p=p-prior;}updown(S,&S1);printstack(C,S1);}voidsearch3(spotC,ints,inte){co_zhanp;intflag;LQQ;sqlistq;intu,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;}}}voidsearch4(spotC,ints,inte,LQ*Q,intvisit[]){intu,k;co_zhanp;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;}}}}intcount(spotC,stackS,inte){inti,j,n=0,No=-1;stackp;co_zhanq;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;}elseq=q-next;}}returnn-1;}voiddestroy(stack*S){stackp=*S;while(!stackempty(*S)){*S=(*S)-next;delete(p);p=*S;}}voidsavestack(stackS,stack*S2){stackS1;initstack(&S1);updown(S,&S1);updown(S1,S2);}voidchange(sqlistQ,stack*S){sqlistp;p=Q;while(p-data!=-1){push(S,p-data);p=p-prior;}}voidsearch5(spotC,ints,inte,stack*S,stack*S2,int*m){co_zhanp;intflag;LQQ;sqlistq;intu