公交路线查询系统(基于数据结构和C语言)

#include

#include

#include

#include

#define max 30

#define len 20

#define MAX 100

typedef struct Linedot{//??

int stopno;//??o?

char stopname[max];//????

struct Linedot *next;

}linedot,*dot;

typedef struct lineway{//???·

int lineNo;//???·o?

int stopnum;//?????·é???μ???êy

dot stop;//??

}way;

typedef struct lineNode{

int linenum;//???·ì?êy

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;//ê?·￠3μo?

char stopname[max];//????

co_zhan zhan;

}node,*list;

typedef struct zhanNode{

int vexnum;//?￥μ?êy

int arcnum;//??êy

node vexs[max];//?￥μ?

}spot;

typedef struct sqNode//?¨ò????ò?óáD

{

int data;

struct sqNode *prior;

struct sqNode *next;

}sqnode,*sqlist;

typedef struct//???òá′?óáDààDí

{

sqlist front;

sqlist rear;

}LQ;

void initqueue(LQ *Q)//3?ê??ˉ?óáD

{

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)//3??ó

{

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)//3?ê??ˉ?? {

*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)//3???

{

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

{

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)//1??????·3?ê??ˉ

{

dot p,q;

co_zhan R;

int i,j,m,n,num;

char vex1[max],vex2[max];

if((fp=fopen("f.txt","r"))==NULL)//′ò?a???t

{

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].stopnum);//ê?è????·o?oí?????·é???μ???êy

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;

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)//2é?ˉ???¨3μ′?μ????·?°í??-??μ?

{

dot p;

int i,n,k=0;

printf("??ê?è?3μ′?:");

scanf("%d",&n);

for(i=0;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("????μ?μ?ê?·￠3μóD:%d\n",C.vexs[k].firstbus);

else

printf("?????Tê?·￠3μ!\n");

printf("????μ?μ?1y?·3μóD:");

for(i=0;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)//′òó???à?μ??a??

{

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

{

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("*******************??ó-ê1ó?K3?1???2é?ˉ?μí3************* *****\n");

printf("**************1.2é?ˉ???¨3μ′?μ????·?°í??-??μ?*********** *****\n");

printf("**************2.2é?ˉ???¨??μ?μ?ê?·￠3μoí1y?·3μ*********** *****\n");

printf("**************3.2é?ˉ???¨?eμ?oí??μ??ù?-μ??ùóD???·******* *****\n");

printf("**************4.2é?ˉ???¨?eμ?oí??μ??ù?-??μ?×?éùμ????·*** *****\n");

printf("**************5.2é?ˉ???¨?eμ?oí??μ???3?′?êy×?éùμ?3?3μ?·??****\n");

printf("**************0.í?3?*********************************** *****\n");

printf("******************************************************* *****\n");

printf("-----?eμ???:μ?á|′ó?§/?ìDá×ˉ/±±????3?????/??2y?·??áú1?/±±??ê|\n");

printf(" ·?′ó?§/μ?ê¤???÷/???a′ó?§?÷??/?2?÷?°/ò?oí?°/??é?\n");

printf("-----??μ???:μ?á|′ó?§/?ìDá×ˉ/±±????3?????/??2y?·??áú1?/±±??ê|\n");

printf(" ·?′ó?§/μ?ê¤???÷/???a′ó?§?÷??/?D1?′?/?2?÷?°/ò?

oí?°\n");

printf(" /?÷μ￥\n");

printf("-----1??????·: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

visit[i]=0;

initstack(&S);

printf("??ê?è??eμ?oí??μ?:");

scanf("%s%s",start,end);

s=locate(C,start);

e=locate(C,end);

printf("%sμ?%sμ??ùóD?·??è???:\n",C.vexs[s].stopname,C.vexs[e].stop name);

search3(C,s,e);break;

case 4:

for(i=0;i

visit[i]=0;

initqueue(&Q);

printf("??ê?è??eμ?oí??μ?:");

scanf("%s%s",start,end);

s=locate(C,start);

e=locate(C,end);

printf("%sμ?%sμ?×??ì?·??è???:\n",C.vexs[s].stopname,C.vexs[e].s topname);

search4(C,s,e,&Q,visit);break;

case 5:

initstack(&S);

initstack(&S2);

initstack(&S3);

printf("??ê?è??eμ?oí??μ?:");

scanf("%s%s",start,end);

s=locate(C,start);

e=locate(C,end);

printf("%sμ?%sμ?×?éù??3??·??è???:\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("12??3?%d′?\n",m);break;

case 0:exit(0);break;

default:printf("error!\n");

}

getchar();

printf("\n?ìD??e￡?Y/N:");

scanf("%c",&ch);

}while(ch=='Y'||ch=='y');

}