• /  15
  • 下載費用: 20.00積分  

數據結構圖的基本運算方法及飛機換乘次數最少問題.doc

'數據結構圖的基本運算方法及飛機換乘次數最少問題.doc'
?實習題名:圖的基本運算及飛機換乘次數最少問題一、 問題描述1. 圖的基本運算①驗證在鄰接矩陣和鄰接表兩種不同存儲結構上實現圖的基本運算的算法;②在鄰接矩陣存儲結構上實現圖的深度和寬度優先遍歷算法。2. 飛機最少換乘次數問題設有n個城市,編號為0~n?1,m條航線的起點和終點由用戶輸入提供。尋找一條換乘次數最少的線路方案。(提示:可以使用有向圖表示城市間的航線。只要兩城市間有航班,則圖中這兩點間存在一條權為1的邊??梢允褂肈ijkstra算法實現。)二、概要設計End 調用迪杰斯特拉算法,求出最短路徑調用MGraph類,建立鄰接矩陣輸入城市個數和航線條數Start三、程序代碼(1)圖的基本運算#include const int INFTY=2147483640; enum ResultCode{Underflow,Duplicate,Failure,Success,NotPresent}; template class Graph //抽象類 { public: virtual ResultCode Insert(int u,int v,T&w)=0; virtual ResultCode Remove(int u,int v)=0; virtual bool Exist(int u,int v)const=0; protected: int n,e; }; template //循環隊列類 class SeqQueue { public: SeqQueue(int mSize); ~SeqQueue(){delete []q;} bool IsEmpty() const{return front==rear;} bool IsFull() const{return (rear+1)%maxSize==front;} bool Front(T &x)const; bool EnQueue(T x); bool DeQueue(); void Clear(){front=rear=0;} private: int front,rear; int maxSize; T *q; }; template SeqQueue::SeqQueue(int mSize) //構造函數 { maxSize=mSize; q=new T[maxSize]; front=rear=0; } template bool SeqQueue::Front(T &x)const //取隊頭元素 { if(IsEmpty()) { return false; } x=q[(front+1)%maxSize]; return true; } template bool SeqQueue::EnQueue(T x) //在隊尾插入x { if(IsFull()) { cout<<"Full"<<endl; return false; } q[rear=(rear+1)%maxSize]=x; return true; } template bool SeqQueue::DeQueue() //刪除隊頭元素 { if(IsEmpty()) { cout<<"Underflow"<<endl; return false; } front=(front+1)%maxSize; return true; } template class MGraph:public Graph //鄰接矩陣類 { public: MGraph(int mSize,const T& noedg); ~MGraph(); ResultCode Insert(int u,int v,T&w); ResultCode Remove(int u,int v); bool Exist(int u,int v)const; void DFS(); void BFS(); protected: T **a; T noEdge; void DFS(int v,bool *visited); void BFS(int v,bool *visited); }; template MGraph::MGraph(int mSize,const T&noedg) //構造函數 { n=mSize; e=0; noEdge=noedg; a=new T*[n]; for(int i=0;i<n;i++) { a[i]=new T[n]; for(int j=0;j<n;j++) a[i][j]=noEdge; a[i][i]=0; } } template MGraph::~MGraph() //析構函數 { for(int i=0;i<n;i++) delete []a[i]; delete []a; } template ResultCode MGraph::Insert(int u,int v,T&w) //插入函數 { if(u<0||vn-1||v>n-1||u==v) return Failure; if(a[u][v]!=noEdge) return Duplicate;。省略部分。ove(int u,int v) { if(u<0||vn-1||v>n-1||u==v) return Failure; if(a[u][v]==noEdge) return NotPresent; a[u][v]=noEdge; e--; return Success; } template bool MGraph::Exist(int u,int v)const { if(u<0||vn-1||v>n-1||u==v||a[u][v]==noEdge) return false; return true; } template int MGraph::Choose(int *d,bool *s) //求最小d[i] { int i,minpos; T min; min=INF; minpos=-1; for(i=0;i<n;i++) if(d[i]<=min&&!s[i]) { min=d[i]; minpos=i; } return minpos; } template void MGraph::Dijkstra(int v,T *d,int *path) //迪杰斯特拉算法 { int i,k,w; if(vn-1) throw OutOfBounds; bool *s=new bool[n]; for(i=0;i<n;i++) { s[i]=false; d[i]=a[v][i]; if(i!=v&&d[i]<INF) path[i]=v; else path[i]=-1; } s[v]=true; d[v]=0; for(i=1;i<n;i++) { k=Choose(d,s); s[k]=true; for(w=0;w<n;w++) if(!s[w]&&(d[k]+a[k][w])<d[w]) { d[w]=d[k]+a[k][w]; path[w]=k; } } } int main() { int n,m; cout<>n; cout<>m; MGraphA(n,INF); int c,f; cout<<"請輸入每條航線的起點和終點: "<<endl; for(int i=0;i<m;i++) { cout << "航線" << i+1 <>c>>f; A.Insert(c,f,1); } char s; do{ int v,w; cout<>v>>w; while(v<0||wn-1||v>n-1) { cout<>v>>w; } int *b=new int[n]; int *d=new int[n]; int *path=new int[n]; A.Dijkstra(v,d,path); int e=n-1; for(int j=0;j<n;j++) b[j]=-2; if(w!=v) { j=w; while(path[j]!=-1) { b[e]=path[j]; e--; j=path[j]; } if(e==n-1||d[j]==INF) cout<<"該路間無線路!"<<endl; else { cout<<"從"<<v<<"到"<<w<<"的換乘次數最小的線路方案為:"; for(int k=0;k<n;k++) { if(b[k]!=-2) cout<<b[k]<<","; } cout<<w<<endl; } } if(w==v) cout<<"從"<<v<<"到"<<i<<"該路間無需乘飛機!"<<endl; delete []b; delete []d; delete []path; cout<>s; while(s!='Y'&&s!='y'&&s!='n'&&s!='N') { cout<>s; } }while(s=='Y'||s=='y'); return 0; }四、測試結果1. 圖的基本運算2. 飛機最少換乘次數問題
關 鍵 詞:
換乘 飛機 運算方法 次數 基本 結構圖 最少 數據 問題
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:數據結構圖的基本運算方法及飛機換乘次數最少問題.doc
鏈接地址: http://www.094347.live/p-53670181.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.094347.live 網站版權所有

粵ICP備19057495號 

收起
展開
有没有苹果软件赚钱的 快赢481出号计算公式 长江证券股票 股市行情走势 上海天天彩选4开奖情况 股票是怎么涨跌的 江苏快3遗漏数据电脑版 快乐彩玩法 股票推荐群 融资融券 北京11选五购买网站 重庆时时开奖结果查询2020