數(shù)據(jù)結(jié)構(gòu)實驗-圖及其應(yīng)用

數(shù)據(jù)結(jié)構(gòu)實驗報告三實驗名稱：圖及其應(yīng)用實驗?zāi)康募皩嶒炓笸ㄟ^完成本實驗，掌握圖的兩種基本的存儲結(jié)構(gòu)（鄰接矩陣、鄰接表），以及圖的基本算法實現(xiàn)（建立、遍歷），并能運用圖結(jié)構(gòu)分析解決一些實際問題。本實驗訓(xùn)練的要點是：圖的兩種基本存儲結(jié)構(gòu)，及各種操作的算法實現(xiàn)（建立、遍歷、圖的典型應(yīng)用）。2實驗內(nèi)容及實驗步驟（附運行結(jié)果截屏）建立無向圖和有向圖的鄰接矩陣存儲，計算頂點的度，并輸出圖的基本信息。建立有向圖的鄰接表存儲表示，并根據(jù)存儲計算頂點的出度和入度，然后輸出圖的基本信息。編寫完整的程序?qū)崿F(xiàn)AOV網(wǎng)的拓?fù)渑判?。編程求AOE網(wǎng)的關(guān)鍵路徑。編程實現(xiàn)單源點最短路徑的Dijkstra算法。注：（1）～（2）必做，（3）～（5）選做。實驗步驟： 總體來說，先編寫類模板，實現(xiàn)各自的基礎(chǔ)結(jié)構(gòu)，之后按照要求編寫適當(dāng)?shù)暮瘮?shù)方法（公共接口），最后完成封裝。編寫主函數(shù)直接調(diào)用。但這一次考慮到圖的處理方式與以往表和樹的不同，并沒有把所有功能都與類模板綁定到一起而是靈活地選擇了合適的處理方式。核心代碼：//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]=