數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--圖的遍歷和生成樹求解-展示頁
2025-01-25 14:20本頁面
【正文】 //鄰接表 AdjList vertices。//頂點信息 ArcNode *firstarc。//該弧相關(guān)信息的指針(可無)}ArcNode。/*該弧的權(quán)重*/ struct ArcNode *nextarc。2．鄰接表的存儲表示如下typedef struct ArcNode{ //弧的結(jié)點結(jié)構(gòu)類型 int adjvex。//圖的當前頂點數(shù)和弧數(shù) GraphKind kind。//頂點向量 AdjMatrix arcs。 //該弧相關(guān)信息的指針(可無)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。e)(ALGraph G,int v)(MGraph G,AdjMatrix GA,VertexType u) (ALGraph G)13. 求頂點在圖中位置LocateVex(MGraph G,VertexType u)，LocateVexG(ALGraph G,vertexType e)() 采用的數(shù)據(jù)結(jié)構(gòu)說明及類型的定義1．鄰接矩陣的存儲表示如下typedef struct ArcCell{ VRType adj。Q,int e) (LinkQueue amp。G) (MGraph G,AdjMatrix GA)(ALGraph G) (MGraph G,int n,int v) (LinkQueue amp。G,AdjMatrix amp。建立具體的功能實現(xiàn)函數(shù)，如初始化、錄入、輸出等。3)建立圖的鄰接矩陣AdjMatrix[][]，以及邊的權(quán)值。3. next域指向與改結(jié)點同類型的下一個結(jié)點nextdatadatanext 6）圖遍歷和生成樹求解的總體結(jié)構(gòu)框圖如下：圖的遍歷和生成樹的求解建立鄰接矩陣輸出鄰接矩陣BFS遍歷建立鄰接表輸出鄰接表DFS遍歷Prim求最小生成樹Kruskal求最小生成樹1）建立隊列LinkQueue，以及隊頭指針front、隊尾指針rear。 4）基于鄰接表存儲結(jié)構(gòu)，用Kruskal算法求圖的最小生成樹。 2）對圖的深度遍歷基于鄰接矩陣，廣度遍歷基于鄰接表。6）當輸入的信息出錯時，程序應(yīng)給錯誤信息提示，使程序設(shè)計得全面周密。4）選擇適當?shù)乃惴?，實現(xiàn)圖的遍歷和最小生成樹的求解等功能。2） 需要創(chuàng)建所有圖的存儲結(jié)構(gòu)(鄰接矩陣存儲結(jié)構(gòu)和鄰接表存儲結(jié)構(gòu))。課程設(shè)計是培養(yǎng)學(xué)生綜合運用所學(xué)知識,發(fā)現(xiàn),提出,分析和解決實際問題,鍛煉實踐能力的重要環(huán)節(jié),是對學(xué)生實際工作能力的具體訓(xùn)練和考察過程. 通過課程設(shè)計，鞏固和加深對隊列以及圖等理論知識的理解；掌握現(xiàn)實復(fù)雜問題的分析建模和解決方法，掌握包括問題描述、系統(tǒng)分析、設(shè)計建模、代碼實現(xiàn)、結(jié)果分析等的方法；提高利用計算機分析解決綜合性實際問題的基本能力；鍛煉個人動手能力，歷練自身素質(zhì)。關(guān)鍵詞：圖；存儲結(jié)構(gòu)；遍歷 ；最小生成樹目 錄………………………………………………………1………………………………………………1……………………………………………………1………………………………………………………1……………………………………………………1……………………………………………………23. 方案實施………………………………………………………3………………………3…………………………5，如用到的宏及代表的意義………164. 結(jié)果與結(jié)論………………………………………………… 17………………………………………17……………………………………………………19…………………………………………………19……………………………………………………20圖的遍歷和生成樹求解1. 設(shè)計背景通過本課程設(shè)計，加深對《面向?qū)ο蟪绦蛟O(shè)計C++》課程所學(xué)知識的理解，熟練掌握和鞏固C++語言的基本知識和語法規(guī)范,掌握使用面向?qū)ο蟪绦蛟O(shè)計語言C++，或面向?qū)ο箝_發(fā)平臺Visual C++等,培養(yǎng)調(diào)查研究、查閱技術(shù)文獻、資料、手冊以及編寫技術(shù)文獻的能力。對圖的遍歷分別采用了廣度優(yōu)先遍歷和深度優(yōu)先遍歷。本程序是采用鄰接矩陣、鄰接表結(jié)構(gòu)存儲來實現(xiàn)對圖的存儲。 圖的遍歷和生成樹求解摘要：圖是一種比線形表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，節(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。采用鄰接矩陣即為數(shù)組表示法，鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。圖的最小生成樹基于圖的兩種存儲結(jié)構(gòu)，采用Prim算法和Kruskal算法對圖的最小生成樹進行求解。學(xué)會編制結(jié)構(gòu)清晰、風格良好的C++語言程序，從而具備利用計算機編程分析解決綜合性實際問題的初步能力。1） 圖的遍歷和生成樹求解所有功能：圖的生成、圖的遍歷、最小生成樹求解。
公司管理相關(guān)推薦
鄂ICP備17016276號-1