數(shù)據(jù)結(jié)構(gòu)矩陣處理

1、算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 班 級(jí): 姓 名:指導(dǎo)老師：2015年6月222015年7月3日 目錄1設(shè)計(jì)方案.32實(shí)現(xiàn)過(guò)程33測(cè)試34使用說(shuō)明.135難點(diǎn)與收獲.136實(shí)現(xiàn)代碼.137可改進(jìn)的地方.25一 設(shè)計(jì)方案能根據(jù)實(shí)際問(wèn)題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)出解決問(wèn)題的有效算法，實(shí)現(xiàn)圖的一些基本操作，此次設(shè)計(jì)主要需要解決對(duì)無(wú)向圖，無(wú)向網(wǎng)，有向圖，有向網(wǎng)的一些基本操作和應(yīng)用，因此可以設(shè)計(jì)一個(gè)基于VC或VS的應(yīng)用程序，數(shù)據(jù)可以從鍵盤(pán)輸入，然后設(shè)計(jì)程序利用多級(jí)菜單實(shí)現(xiàn)各種功能。二 實(shí)現(xiàn)過(guò)程實(shí)現(xiàn)過(guò)程的主函數(shù)為：void main( )1 對(duì)無(wú)向圖的基本操作及應(yīng)

2、用的實(shí)現(xiàn) 創(chuàng)建無(wú)向圖的鄰接矩陣（void creat_mg(Mgraph G)） 創(chuàng)建無(wú)向圖的鄰接表 （void CreatAdjList(Graph* G)） 無(wú)向圖的深度優(yōu)先遍歷 （void DFS(Graph *G, int i, int visited)） 無(wú)向圖的廣度優(yōu)先遍歷 （void BFS(Graph* G,int v,int visited)）2 對(duì)無(wú)向網(wǎng)的基本操作及應(yīng)用的實(shí)現(xiàn) 創(chuàng)建無(wú)向網(wǎng)的鄰接矩陣 （CreateNDNGraphics(Graphics &G)） 創(chuàng)建無(wú)向網(wǎng)的鄰接表（CreateUDN(ALGraph &G)） 求最小生成樹(shù)（Prim(int

3、 graphMAX, int n)）3 對(duì)有向圖的基本操作及應(yīng)用的實(shí)現(xiàn) 創(chuàng)建有向圖的鄰接矩陣（CreateDGraphics(Graphics &G)） 創(chuàng)建有向圖的鄰接表（CreateDG(ALGraph &G)） 拓?fù)渑判颍═opSort(Graphaa& g)）4 對(duì)有向網(wǎng)的基本操作及應(yīng)用的實(shí)現(xiàn) 創(chuàng)建有向網(wǎng)的鄰接矩陣（CreateDNGraphics(Graphics &G)） 創(chuàng)建有向網(wǎng)的鄰接表（CreateUDN(ALGraphh &G, indegree indegree)） 關(guān)鍵路徑 （CriticalPath(ALGraphh &

4、g, indegree indegree)） 單源最短路徑（myDijstra(n,1)）三 測(cè)試 數(shù)據(jù)輸入：從鍵盤(pán)輸入操作對(duì)應(yīng)的序號(hào)1. 最初入口界面2. 無(wú)向圖：無(wú)向圖的鄰接矩陣：無(wú)向圖的鄰接表：無(wú)向圖的深度優(yōu)先遍歷：無(wú)向圖的廣度優(yōu)先遍歷：3. 無(wú)向網(wǎng)的基本操作及應(yīng)用無(wú)向網(wǎng)的鄰接矩陣：無(wú)向網(wǎng)的鄰接表：最小生成樹(shù)：4. 有向圖的基本操作及應(yīng)用創(chuàng)建有向圖的鄰接矩陣：創(chuàng)建有向圖的連接表有向圖的拓?fù)渑判?5. 有向網(wǎng)的基本操作及應(yīng)用有向網(wǎng)的鄰接矩陣：創(chuàng)建有向網(wǎng)的鄰接表;有向網(wǎng)的關(guān)鍵路徑：4.單源頂點(diǎn)路徑最短問(wèn)題：四 使用說(shuō)明 總共有三級(jí)選擇菜單，根據(jù)需要從鍵盤(pán)輸入對(duì)應(yīng)菜單序號(hào)，進(jìn)入相應(yīng)輸入界面，輸

5、入待測(cè)數(shù)據(jù)，對(duì)圖或網(wǎng)進(jìn)行相應(yīng)的操作五 難點(diǎn)與收獲用代碼實(shí)現(xiàn)各種操作時(shí)，代碼容易出現(xiàn)邏輯上的錯(cuò)，個(gè)人覺(jué)得這種錯(cuò)誤易發(fā)現(xiàn)但比較難修改，比如，在實(shí)現(xiàn)圖的深度優(yōu)先遍歷時(shí)，利用了遞歸函數(shù)（DFS(G,i,visited)），通過(guò)查找資料和看書(shū)，多次調(diào)試，在程序中實(shí)現(xiàn)調(diào)用，實(shí)現(xiàn)了對(duì)圖的深度優(yōu)先遍歷。這次通過(guò)上機(jī)實(shí)習(xí)，我更加深入的學(xué)習(xí)了圖和網(wǎng)的相關(guān)內(nèi)容和掌握了圖和網(wǎng)的一些基本操作，也學(xué)會(huì)有效利用基本調(diào)試方法，會(huì)找出程序代碼中的錯(cuò)誤并且修改，提高了自己發(fā)現(xiàn)問(wèn)題和解決問(wèn)題的能力，受益匪淺。六實(shí)現(xiàn)代碼無(wú)向圖：/=創(chuàng)建無(wú)向圖（鄰接表）=/void CreatAdjList(Graph* G) int i,j,k;e

6、dgenode * p1;edgenode * p2;cout<<"請(qǐng)輸入無(wú)向圖的頂點(diǎn)數(shù)和邊數(shù)(如：2 1):"<<endl;cin>>G->vexnum>>G->arcnum;cout<<endl;cout<<"開(kāi)始輸入頂點(diǎn)表（如：1 2）"<<endl;for (i=1;i<=G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<

7、<endl;cout<<"開(kāi)始輸入邊表信息:"<<endl; cout<<endl;for (k=1;k<=G->arcnum;k+)cout<<"請(qǐng)輸入邊<Vi,Vj>對(duì)應(yīng)的頂點(diǎn)序號(hào)（如：2 3）:"cin>>i>>j; cout<<endl;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1

8、;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因?yàn)槭菬o(wú)向圖，所以有兩次建立邊表的過(guò)程void creat_mg(Mgraph G) int i,j,k; printf ("n請(qǐng)輸入無(wú)向圖的頂點(diǎn)數(shù)和邊數(shù)，如(6,5)每次回車(chē)鍵輸入："); scanf ("%d,%d",&n,&e); for (i=1;i<=n;i+) for (j=1;j<=n;j+)Gij=0; /將

9、鄰接矩陣初始化 for (k=1;k<=e;k+) printf ("n請(qǐng)輸入每條邊的兩個(gè)頂點(diǎn)編號(hào)，如(2,5)每次回車(chē)鍵輸入:"); scanf ("%d,%d",&i,&j); Gij=1; Gji=1; int a,b; for (a=1;a<=n;a+) printf ("n"); for (b=1;b<=n;b+) printf ("%5d",Gab); printf ("n"); /-廣度優(yōu)先遍歷-/void BFS(Graph* G,int v,i

10、nt visited)/從第v個(gè)頂點(diǎn)出發(fā)非遞歸地廣度優(yōu)先搜索遍歷無(wú)向圖G。QueueList *Q=new QueueList;Q->front=Q->rear=NULL; /初始化隊(duì)列QEnQueue(Q,v); /V入隊(duì)列while(Q->rear!=NULL)int e;DeQueue(Q, &e); /隊(duì)頭(指定的)元素出隊(duì)并置值為ecout<<G->adjlistse.vertex<<" " /輸出頂點(diǎn)信息visitede=1; edgenode* p=new edgenode;p=G->adjlist

11、se.edgelink; /指向第一條依附于該頂點(diǎn)的邊的指針if(p)int m=p->endver; /該邊所指向的頂點(diǎn)的位置if(m=0)EnQueue(Q,m); while(visitedm=0) p=p->edgenext; if(p=NULL)break;m=p->endver;EnQueue(Q,m);有向網(wǎng)，無(wú)向網(wǎng)，無(wú)向圖的鄰接矩陣構(gòu)造;int CreateDGraphics(Graphics &G) / 構(gòu)造一個(gè)有向圖 printf("分別輸入弧數(shù)、頂點(diǎn)數(shù)（用空格）:"); Info info = NULL; / 這里忽略info

12、信息 scanf("%d%d", &G.arcnum, &G.vexnum); / 先把鄰接矩陣中的adj設(shè)置為0 for(int i = 0; i < G.vexnum; +i) for(int j = 0; j < G.vexnum; +j) G.arcij.adj = 0; / 掃描進(jìn)入頂點(diǎn)元素 for(i = 0; i < G.vexnum; +i) printf("請(qǐng)依次輸入頂點(diǎn)元素值:n"); scanf("%d", &G.vexsi); printf("輸入完畢!n&q

13、uot;); / 輸入弧信息 for(i = 0; i < G.arcnum; +i) printf("請(qǐng)輸入具有鄰接關(guān)系的頂點(diǎn):n"); DataType d1, d2; scanf("%d%d", &d1, &d2); int p1 = LocateVex(G, d1); int p2 = LocateVex(G, d2); G.arcp1p2.adj = 1; printf("該有向圖的鄰接矩陣構(gòu)造完畢"); return 1; / CreateDGraphics int CreateNDNGraphics

14、(Graphics &G) / 構(gòu)造一個(gè)無(wú)向網(wǎng) printf("分別輸入弧數(shù)、頂點(diǎn)數(shù)（用空格）:n"); Info info = NULL; / 這里忽略info信息 scanf("%d%d", &G.arcnum, &G.vexnum); / 先把鄰接矩陣中的adj設(shè)置為0 for(int i = 0; i < G.vexnum; +i) for(int j = 0; j < G.vexnum; +j) G.arcij.adj = 0; / 借用改值為最大值 / 掃描進(jìn)入頂點(diǎn)元素 for(i = 0; i <

15、G.vexnum; +i) printf("請(qǐng)依次輸入頂點(diǎn)元素值:n"); scanf("%d", &G.vexsi); printf("輸入完畢!n"); / 輸入弧信息 for(i = 0; i < G.arcnum; +i) printf("請(qǐng)輸入具有鄰接關(guān)系的頂點(diǎn),以及他們的權(quán)重（如2 1 3）:n"); DataType d1, d2, d3; scanf("%d%d%d", &d1, &d2, &d3); int p1 = LocateVex(G

16、, d1); int p2 = LocateVex(G, d2); G.arcp1p2.adj = d3; / 因?yàn)槭菬o(wú)向，所以對(duì)稱(chēng)設(shè)置 G.arcp2p1.adj = d3; printf("該無(wú)向網(wǎng)的鄰接矩陣構(gòu)造完畢"); return 1; / CreateNDNGraphics int CreateDNGraphics(Graphics &G) / 構(gòu)造一個(gè)有向網(wǎng) printf("分別輸入弧數(shù)、頂點(diǎn)數(shù)（用空格）:n"); Info info = NULL; / 這里忽略info信息 scanf("%d%d", &

17、;G.arcnum, &G.vexnum); / 先把鄰接矩陣中的adj設(shè)置為0 for(int i = 0; i < G.vexnum; +i) for(int j = 0; j < G.vexnum; +j) G.arcij.adj = 0; / 借用改值為最大值 / 掃描進(jìn)入頂點(diǎn)元素 for(i = 0; i < G.vexnum; +i) printf("請(qǐng)依次輸入頂點(diǎn)元素值:n"); scanf("%d", &G.vexsi); printf("輸入完畢"); / 輸入弧信息 for(i =

18、 0; i < G.arcnum; +i) printf("請(qǐng)輸入具有鄰接關(guān)系的頂點(diǎn),以及他們的權(quán)重:n"); DataType d1, d2, d3; scanf("%d%d%d", &d1, &d2, &d3); int p1 = LocateVex(G, d1); int p2 = LocateVex(G, d2); G.arcp1p2.adj = d3; printf("該有向網(wǎng)的鄰接矩陣構(gòu)造完畢"); return 1; / CreateDNGraphics /鄰接表建立無(wú)向網(wǎng)int Creat

19、eUDN(ALGraph &G) /* 鄰接表建立無(wú)向網(wǎng) */ int i,s,d,w; ArcNode *p, *q; printf("輸入結(jié)點(diǎn)數(shù)目和邊數(shù)（用空格）:"); scanf("%d%d",&G.vexnum,&G.arcnum); /* 輸入結(jié)點(diǎn)數(shù)目和邊數(shù) */ getchar(); for(i=1; i<=G.vexnum; i+) /* 輸入頂點(diǎn) */ printf("輸入頂點(diǎn)（每一個(gè)按回車(chē)鍵):"); scanf("%c",&G.verticesi.data

20、); /* 輸入頂點(diǎn) */ getchar(); G.verticesi.firstarc = NULL; /* 首先初始化為NULL */ for(i=1; i<=G.arcnum; i+) printf("依次輸入每條邊依附的頂點(diǎn)序號(hào)，權(quán)值（空格/每一個(gè)按回車(chē)鍵):"); scanf("%d%d%d",&s,&d,&w); /* 輸入一條邊依附的起點(diǎn)序號(hào)和終點(diǎn)序號(hào) */ getchar(); p = (struct ArcNode *)malloc(sizeof(struct ArcNode); q = (struct

21、ArcNode *)malloc(sizeof(struct ArcNode); p->info = (InfoType *)malloc(sizeof(InfoType); q->info = (InfoType *)malloc(sizeof(InfoType); p->adjvex = d; /* 保存該弧所指向的頂點(diǎn)位置 */ q->adjvex = s; /* 保存該弧所指向的頂點(diǎn)位置 */ *(p->info) = w; /* 保存權(quán)值到一個(gè)結(jié)點(diǎn)里 */ *(q->info) = w; /* 保存權(quán)值到一個(gè)結(jié)點(diǎn)里 */ p->nextarc

22、 = G.verticess.firstarc; G.verticess.firstarc = p; q->nextarc = G.verticesd.firstarc; G.verticesd.firstarc = q; return OK; /prime算法最小生成樹(shù)int graphMAXMAX; int Prim(int graphMAX, int n)/* lowcosti記錄以i為終點(diǎn)的邊的最小權(quán)值，當(dāng)lowcosti=0時(shí)表示終點(diǎn)i加入生成樹(shù) */int lowcostMAX; /* msti記錄對(duì)應(yīng)lowcosti的起點(diǎn)，當(dāng)msti=0時(shí)表示起點(diǎn)i加入生成樹(shù) */int

23、mstMAX; int i, j, min, minid, sum = 0; /* 默認(rèn)選擇1號(hào)節(jié)點(diǎn)加入生成樹(shù)，從2號(hào)節(jié)點(diǎn)開(kāi)始初始化 */for (i = 2; i <= n; i+)/* 最短距離初始化為其他節(jié)點(diǎn)到1號(hào)節(jié)點(diǎn)的距離 */lowcosti = graph1i; /* 標(biāo)記所有節(jié)點(diǎn)的起點(diǎn)皆為默認(rèn)的1號(hào)節(jié)點(diǎn) */msti = 1; /* 標(biāo)記1號(hào)節(jié)點(diǎn)加入生成樹(shù) */mst1 = 0; /* n個(gè)節(jié)點(diǎn)至少需要n-1條邊構(gòu)成最小生成樹(shù) */for (i = 2; i <= n; i+)min = MAXCOST;minid = 0; /* 找滿(mǎn)足條件的最小權(quán)值邊的節(jié)點(diǎn)mini

24、d */for (j = 2; j <= n; j+)/* 邊權(quán)值較小且不在生成樹(shù)中 */if (lowcostj < min && lowcostj != 0)min = lowcostj;minid = j;/* 輸出生成樹(shù)邊的信息:起點(diǎn)，終點(diǎn)，權(quán)值 */printf("%c - %c : %dn", mstminid + 'A' - 1, minid + 'A' - 1, min); /* 累加權(quán)值 */sum += min; /* 標(biāo)記節(jié)點(diǎn)minid加入生成樹(shù) */lowcostminid = 0; /*

25、更新當(dāng)前節(jié)點(diǎn)minid到其他節(jié)點(diǎn)的權(quán)值 */for (j = 2; j <= n; j+)/* 發(fā)現(xiàn)更小的權(quán)值 */if (graphminidj < lowcostj)/* 更新權(quán)值信息 */lowcostj = graphminidj; /* 更新最小權(quán)值邊的起點(diǎn) */mstj = minid;/* 返回最小權(quán)值和 */return sum;/kraskal算法求最小生成樹(shù)關(guān)鍵代碼：for(i=0;i<t;i+) scanf("%d %d %d",&ai.m,&ai.n,&ai.d); /輸入每條邊的權(quán)值 qsort(a,t,s

26、izeof(a0),cmp); min=num=0; for(i=0;i<t && num<n-1;i+) for(k=ai.m;xk!=k;k=xk) /判斷線(xiàn)段的起始點(diǎn)所在的集合 xk=xxk; for(g=ai.n;xg!=g;g=xg) /判斷線(xiàn)段的終點(diǎn)所在的集合 xg=xxg; if(k!=g) /如果線(xiàn)段的兩個(gè)端點(diǎn)所在的集合不一樣 xg=k; min+=ai.d; num+; printf("最小生成樹(shù)中加入邊：%d %dn",ai.m,ai.n); printf("最小生成樹(shù)的權(quán)值為：%dn",min); sys

27、tem("pause"); 有向圖的拓?fù)渑判颍簐oid TopSort(Graphaa& g) cout << "The topsort is:" <<endl; for (int i=0; i<g.vertexNum; i+) VertexNode& v = FindZeroIndegree(g); if (v.indegree!=NULL) cout << "The graph has cycle, can not do topsort"<<endl; / pr

28、int graph as topsort. cout<< v.data << " " / for each vertex w adjacent to v, -indegree adjVertexNode* padjv = v.list; while (padjv!=NULL) /！這個(gè)算法這里破壞了原圖中的入度信息。最后入度均為1 g.VertexNodepadjv->adjVertexPosition.indegree-; padjv = padjv->next; /避免入度信息均為零FindZeroIndegree找到刪除的頂點(diǎn)，將刪

29、除的頂點(diǎn)入度置為1 v.indegree+; cout << endl;有向網(wǎng)關(guān)鍵路徑：/求關(guān)鍵路徑void CriticalPath(ALGraphh &g, indegree indegree) /G為有向網(wǎng)，輸出G的各項(xiàng)關(guān)鍵活動(dòng) ArcNode *q; int gettop,k,j; int ee,el; /活動(dòng)最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間 TopologicalSort(g, indegree); vl=(int *)malloc( g.vexnum*sizeof(int) ); /事件最早發(fā)生時(shí)間數(shù)組 for(int i=0; i<g.vexnum; i+)

30、vli=veg.vexnum-1; /初始化 cout<<"ve:"<<endl; /輸出ve for(i=0; i<g.vexnum; i+) cout<<vei<<" " cout<<endl; while(top2!=0) /出棧是求vl gettop=stack2top2-; for(q = g.verticesgettop.firstarc; q; q = q->nextarc) /求各頂點(diǎn)事件的最遲發(fā)生時(shí)間vl值 k=q->adjvex; if(vlk - q->info1 < vlgettop) vlgettop = vlk - q->info1; /for cout<<"vl:"<<endl; /輸出vl for(i=0; i<g.vexnum; i+) cout<<vli<<" " cout<<endl; for(j=0; j<g.vexnum; j+) /求ee,el和關(guān)鍵活動(dòng) for(q = g.verticesj.firstarc; q; q = q->nextarc) k=q->adj