數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(c語(yǔ)言版)飛機(jī)訂票系統(tǒng)-資料下載頁(yè)
2025-06-25 07:21本頁(yè)面
【正文】 /生成圖的鄰接表 void DFSTraverse(Graph)。 //深度優(yōu)先搜索遍歷圖 void DFS(Graph,int)。 void BFSTraverse(Graph)。 //廣度優(yōu)先搜索遍歷圖 void Initial(SqQueue amp。)。 //初始化一個(gè)隊(duì)列 BOOL QueueEmpty(SqQueue)。 //判斷隊(duì)列是否空 BOOL EnQueue(SqQueue amp。,int)。 //將一個(gè)元素入隊(duì)列 BOOL DeQueue(SqQueue amp。,int amp。)。 //將一個(gè)元素出隊(duì)列 int FirstAdjVex(Graph,int)。 //求圖中某一頂點(diǎn)的第一個(gè)鄰接頂點(diǎn) int NextAdjVex(Graph,int,int)。 //求某一頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) int main() {Graph G。 //采用鄰接表結(jié)構(gòu)的圖 char j=39。y39。 printf(題目:編制一個(gè)“圖遍歷的演示”的程序.\n)。 //程序解說(shuō) printf(\n本程序?qū)⒀菔旧梢粋€(gè)圖，并對(duì)它進(jìn)行遍歷.\n)。 printf(輸入圖的頂點(diǎn)數(shù)和弧數(shù):\n格式：頂點(diǎn)數(shù)，弧數(shù)；例如:5,4\n)。 printf(接著輸入各邊(弧尾，弧頭):\n例如:5,3\n 3,1\n 1,2\n 2,4\n)。 printf(程序會(huì)生成一個(gè)圖，并對(duì)它進(jìn)行深度和廣度遍歷.\n)。 printf(深度遍歷:12435\n廣度遍歷:12345\n)。 // while(j!=39。N39。amp。amp。j!=39。n39。) { printf(\n請(qǐng)輸入頂點(diǎn)數(shù)和弧數(shù)：)。 scanf(%d,%d,amp。,amp。)。 //輸入圖的頂點(diǎn)數(shù)和弧數(shù) CreateGraph(G)。 //生成鄰接表結(jié)構(gòu)的圖 DFSTraverse(G)。 //深度優(yōu)先搜索遍歷圖 BFSTraverse(G)。 //廣度優(yōu)先搜索遍歷圖 printf(圖遍歷完畢，繼續(xù)進(jìn)行嗎?(Y/N))。 scanf( %c,amp。j)。 } } void CreateGraph(Graph amp。G) {//構(gòu)造鄰接表結(jié)構(gòu)的圖G int i。 int start,end。 ArcNode *s。 for(i=1。i=。i++) [i]=NULL。 //初始化指針數(shù)組 for(i=1。i=。i++) {scanf(%d,%d,amp。start,amp。end)。 //輸入弧的起點(diǎn)和終點(diǎn) s=(ArcNode *)malloc(sizeof(ArcNode))。 //生成一個(gè)弧結(jié)點(diǎn) snextarc=[start]。 //插入到鄰接表中 sadjvex=end。 [start]=s。 {s=(ArcNode *)malloc(sizeof(ArcNode))。 snextarc=[end]。 sadjvex=start。 [end]=s。 } } } void DFSTraverse(Graph G) {//深度優(yōu)先遍歷圖G int i。 printf(深度優(yōu)先遍歷:)。 for(i=1。i=。i++) visited[i]=False。 //訪(fǎng)問(wèn)標(biāo)志數(shù)組初始化 for(i=1。i=。i++) if(!visited[i]) DFS(G,i)。 //對(duì)尚未訪(fǎng)問(wèn)的頂點(diǎn)調(diào)用DFS printf(\b\b \n)。 } void DFS(Graph G,int i) {//從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度遍歷圖G int w。 visited[i]=True。 //訪(fǎng)問(wèn)第i個(gè)頂點(diǎn) printf(%d,i)。 for(w=FirstAdjVex(G,i)。w0。w=NextAdjVex(G,i,w)) if(!visited[w]) DFS(G,w)。 //對(duì)尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn)w調(diào)用DFS } void BFSTraverse(Graph G) {//按廣度優(yōu)先非遞歸的遍歷圖G，使用輔助隊(duì)列Q和訪(fǎng)問(wèn)標(biāo)志數(shù)組visited int i,u,w。 SqQueue Q。 printf(廣度優(yōu)先遍歷:)。 for(i=1。i= 。i++) visited[i]=False。 //訪(fǎng)問(wèn)標(biāo)志數(shù)組初始化 Initial(Q)。 //初始化隊(duì)列 for(i=1。i=。i++) if(!visited[i]) {visited[i]=True。 //訪(fǎng)問(wèn)頂點(diǎn)i printf(%d,i)。 EnQueue(Q,i)。 //將序號(hào)i入隊(duì)列 while(!QueueEmpty(Q)) //若隊(duì)列不空，繼續(xù) {DeQueue(Q,u)。 //將隊(duì)頭元素出隊(duì)列并置為u for(w=FirstAdjVex(G,u)。w0。w=NextAdjVex(G,u,w)) if(!visited[w]) //對(duì)u的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn)w進(jìn)行訪(fǎng)問(wèn)并入隊(duì)列 {visited[w]=True。 printf(%d,w)。 EnQueue(Q,w)。 } } } printf(\b\b \n)。 } int FirstAdjVex(Graph G,int v) {//在圖G中尋找第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn) if(![v]) return 0。 else return([v]adjvex)。 } int NextAdjVex(Graph G,int v,int u) {//在圖G中尋找第v個(gè)頂點(diǎn)的相對(duì)于u的下一個(gè)鄰接頂點(diǎn) ArcNode *p。 p=[v]。 while(padjvex!=u) p=pnextarc。 //在頂點(diǎn)v的弧鏈中找到頂點(diǎn)u if(pnextarc==NULL) return 0。 //若已是最后一個(gè)頂點(diǎn)，返回 else return(pnextarcadjvex)。 //返回下一個(gè)鄰接頂點(diǎn)的序號(hào) } void Initial(SqQueue amp。Q) {//隊(duì)列初始化 ==0。 } BOOL QueueEmpty(SqQueue Q) {//判斷隊(duì)列是否已空，若空返回True,否則返回False if(==) return True。 else return False。 } BOOL EnQueue(SqQueue amp。Q,int ch) {//入隊(duì)列，成功返回True，失敗返回False if((+1)%MAXQSIZE==) return False。 []=ch。 =(+1)%MAXQSIZE。 return True。 } BOOL DeQueue(SqQueue amp。Q,int amp。ch) {//出隊(duì)列,成功返回True，并用ch返回該元素值，失敗返回False if(==) return False。 ch=[]。 =(+1)%MAXQSIZE。 return True。 //成功出隊(duì)列，返回True } 四．程序的調(diào)試：輸入為：8，10 各邊： 1，2 1，3 2，4 2，5 3，6 3，8 4，7 5，6 5，7 7，8結(jié)果為：深度優(yōu)先遍歷：13875624 廣度優(yōu)先遍歷：1328654
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1