數(shù)據(jù)結構實驗-圖及其應用

數(shù)據(jù)結構實驗報告三實驗名稱：圖及其應用實驗目的及實驗要求通過完成本實驗，掌握圖的兩種基本的存儲結構（鄰接矩陣、鄰接表），以及圖的基本算法實現(xiàn)（建立、遍歷），并能運用圖結構分析解決一些實際問題。本實驗訓練的要點是：圖的兩種基本存儲結構，及各種操作的算法實現(xiàn)（建立、遍歷、圖的典型應用）。2實驗內容及實驗步驟（附運行結果截屏）建立無向圖和有向圖的鄰接矩陣存儲，計算頂點的度，并輸出圖的基本信息。建立有向圖的鄰接表存儲表示，并根據(jù)存儲計算頂點的出度和入度，然后輸出圖的基本信息。編寫完整的程序實現(xiàn)AOV網的拓撲排序。編程求AOE網的關鍵路徑。編程實現(xiàn)單源點最短路徑的Dijkstra算法。注：（1）～（2）必做，（3）～（5）選做。實驗步驟： 總體來說，先編寫類模板，實現(xiàn)各自的基礎結構，之后按照要求編寫適當?shù)暮瘮?shù)方法（公共接口），最后完成封裝。編寫主函數(shù)直接調用。但這一次考慮到圖的處理方式與以往表和樹的不同，并沒有把所有功能都與類模板綁定到一起而是靈活地選擇了合適的處理方式。核心代碼：//GraphMatrix.h鄰接矩陣表示圖//類的聲明template<classT>classGraphMatrix{public:GraphMatrix(intp=0,inte=0):point_num(p),edge_num(e){};boolInsertPoint(charx);voidPrintGraph();protected:charpoint_name[maxn];doublegra[maxn][maxn];intpoint_num,edge_num;};//插入節(jié)點template<classT>boolGraphMatrix<T>::InsertPoint(charx){if(point_num==0){point_num=1;point_name[0]=x;}else{point_name[point_num]=x;for(inti=0;i<point_num;i++){cin>>gra[point_num][i];if(gra[point_num][i]!=0)edge_num++;}point_num++;}}//GraphChart.h鄰接表表示圖//類的聲明template<classNameType,classDistType>classGraph;template<classNameType,classDistType>classVertex{public:Vertex(){padjEdge=NULL;m_vertexName=0;}~Vertex(){Edge<DistType>*pmove=padjEdge;while(pmove){padjEdge=pmove->m_pnext;deletepmove;pmove=padjEdge;}}private:friendclassGraph<NameType,DistType>;NameTypem_vertexName;Edge<DistType>*padjEdge;};template<classNameType,classDistType>classGraph{public:Graph(intsize=m_nDefaultSize){m_pVertexTable=newVertex<NameType,DistType>[size];if(m_pVertexTable==NULL){exit(1);}m_numVertexs=0;m_nmaxSize=size;m_nnumEdges=0;}~Graph(){Edge<DistType>*pmove;for(inti=0;i<this->m_numVertexs;i++){pmove=this->m_pVertexTable[i].padjEdge;if(pmove){this->m_pVertexTable[i].padjEdge=pmove->m_pnext;deletepmove;pmove=this->m_pVertexTable[i].padjEdge;}}delete[]m_pVertexTable;}intGetNumEdges(){returnm_nnumEdges/2;}intGetNumVertexs(){returnm_numVertexs;}boolIsGraphFull()const{//圖滿的?returnm_nmaxSize==m_numVertexs;}boolInsertEdge(intv1,intv2,DistTypeweight=m_Infinity);boolInsertVertex(constNameTypevertex);voidPrintGraph();private:Vertex<NameType,DistType>*m_pVertexTable;intm_numVertexs;intm_nmaxSize;staticconstintm_nDefaultSize=10;staticconstDistTypem_Infinity=65536;intm_nnumEdges;intGetVertexPosTable(constNameTypevertex);};//Dijkstra算法voidDijkstra(intn,intv,int*dist,int*prev,intc[maxnum][maxnum]){bools[maxnum];for(inti=1;i<=n;++i){dist[i]=c[v][i];s[i]=0;if(dist[i]==maxint)prev[i]=0;elseprev[i]=v;}dist[v]=0;s[v]=1;for(inti=2;i<=n;++i){inttmp=maxint;intu=v;for(intj=1;j<=n;++j)if((!s[j])&&dist[j]<tmp){u=j;tmp=dist[j];}s[u]=1;for(intj=1;j<=n;++j)if((!s[j])&&c[u][j]<maxint){intnewdist=dist[u]+c[u][j];if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}}}}//AOLinttopGraph(graphg){ EdgeNode*e; inti,k,gettop; inttop=0; intcount=0; int*stack; stack=(int*)malloc(g->numVertexes*sizeof(int)); for(i=0;i<g->numVertexes;i++) { if(g->headlist[i].in==0)//把入度為0的，即沒有入度的點入棧 stack[++top]=i; } while(top) { gettop=stack[top--]; printf("%d",gettop); count++; for(e=g->headlist[gettop].fnode;e;e=e->next)//一次遍歷鏈表，減少各個子節(jié)點的入度 { k=e->data; if(!(--g->headlist[k].in)) stack[++top]=