急!!如何用数据结构实现公交车路线查询
同上,希望各位大虾赐教
#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');
}