??????? 問題描述: 設某城市有n個車站，并有m條公交線路連接這些車站。設這些公交車都是單向的，這n個車站被順序編號為0~n-1。編號程序，輸入該城市的公交線路數，車站個數，以及各公交線路上的各站編號。
?????? 實現要求：求得從站0出發乘公交車至站n一1的最少換車次數。
?????? 程序設計思路：利用輸入信息構建一張有向圖G(用鄰接短陣g表示)，有向圖的頂點是車站，若有某條公交線路經i站能到達j站，就在頂點i到頂點j之間設置一條權為1的有向邊＜i,j)。這樣，從站x至站y的最少上車次數便對應于圖G中從點x至點y的最短路徑長度。而程序要求的換車次數就是上車次數減1。

????? 代碼如下：

#include <stdio.h> #include <stdlib.h> #define INFINITY 9999 #define MAXVNUM 30 char ans; typedef struct {int Vnum;int arcs[MAXVNUM][MAXVNUM]; //圖的存儲結構為鄰接矩陣 }Graph;int createGraph(Graph *g,int *start,int *end) {int n,m,i,j,k,s,count;int t[MAXVNUM];printf("\n★ 請輸入公交車站數和公交車數:\n");scanf("%d %d",&n,&m);if(n<=1 || m<1)return -1;g->Vnum = n;for(i=0;i<n;i++)for(j=0;j<n;j++)g->arcs[i][j] = INFINITY; //鄰接矩陣初始化for(s=0;s<m;s++){printf("\n▲請輸入第%d輛公交車所途經各站的編號【0<=編號<=%d,-1結束】:\n",s+1,n-1);scanf("%d",&k);count = 0;while(k!=-1){t[count++]=k;scanf("%d",&k);}for(i=0;i<count-1;i++){for(j=i+1;j<count;j++) //當前線路中，從t[i]到t[j]有直達公交車g->arcs[t[i]][t[j]]=1;}}printf("\n★ 請輸入上車站編號和下車站編號【0<=編號<=%d】:\n",n-1);scanf("%d%d",start,end);if( *start<0 || *start>n-1 || *end<0 || *end>n-1)return -1;return 0; } int findMinmum(Graph g,int start,int end) //迪杰斯特拉算法找最小上車次數 {int s[MAXVNUM];int i,j,u,*dist,min;if(start==end)return 0;dist=(int *)malloc(sizeof(int));if(dist==NULL)return -1;for(i=0;i<g.Vnum;i++){dist[i]=g.arcs[start][i]; //從start可直達的站點上車次數置1s[i]=0; //所有站點的上車次數還未找到}s[start]=1; //已經找到站點start的最少上車次數dist[start]=0; //從站點start到start的最少上車次數初始化為0for(i=0;i<g.Vnum;++i){min=INFINITY;u=start;for(j=0;j<g.Vnum;++j) //u是從start出發能夠到達的所有站點中上車次數最少者{if(s[j]==0 && dist[j]<min){min=dist[j];u=j;}}s[u]=1; //已經找到從站點start到u的最少上車次數，將u加入集合sfor(j=0;j<g.Vnum;++j) //更新當前情況下其他站點的最少上車次數{if(s[j]==0 && min+g.arcs[u][j]<dist[j])dist[j]=min+g.arcs[u][j];}}return dist[end]; }int main(void) {int start,end,m;printf("\n說明：");printf("\n\t您好！歡迎使用該系統！\n");printf("\t[一] 本系統是根據有向圖創建的，請先輸入你想乘車地點到目的地共有多少站和該地點的公交車數量。站數相當于有向圖中的頂點數。\n");printf("\t[二] 請輸入每條公交車所路徑的站點，相當于有向圖中連接每條邊的頂點。輸入完后按-1進入下一輛公交車的路徑。\n ");printf("\t[三] 請輸入上車地點的站編號和下車站的編號，相當于有向圖中任意的兩個頂點。輸入完后系統將會根據所輸入的信息輸出最少換車次數。\n ");do{Graph G;if(createGraph(&G,&start,&end)==-1){printf("\n 真遺憾!\n 創建有向圖失敗! \n 請重新輸入數據 !\n");return 0;}m=findMinmum(G,start,end);if(m<INFINITY)printf(" 恭喜!\n 有車可以到達該目的地\n 從上車站%d到下車站%d的最少換車次數為： %d\n",start,end,m-1);elseprintf("\n對不起!\n沒有相應的公交車可以到達該站點 !\n");printf("\n是否繼續呢(y/n)?");fflush(stdin);ans=getchar();system("cls");}while(ans=='y' || ans=='Y');printf("\n-----------------------謝謝你使用該系統！----------------------------");system("pause");return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的数据结构课程设计---------最少换车次数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。