| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1307 人关注过本帖
标题:急!!如何用数据结构实现公交车路线查询
只看楼主 加入收藏
sldtk1
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:624
专家分:258
注 册:2006-5-4
结帖率:100%
收藏
 问题点数:0 回复次数:1 
急!!如何用数据结构实现公交车路线查询
同上,希望各位大虾赐教
搜索更多相关主题的帖子: 数据结构 路线 公交车 查询 
2006-05-04 13:40
lsnaimei
Rank: 2
等 级:论坛游民
帖 子:25
专家分:47
注 册:2012-3-30
收藏
得分:0 
#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');
}
2012-04-11 19:53
快速回复:急!!如何用数据结构实现公交车路线查询
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028663 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved