數據結構實驗指導書及答案(徐州工程學院)-資料下載頁

　　

【正文】 xnum。}return(k)。}void dfs_hc(mgraph_hc*g,int v){int w。vis[v]=TRUE。 printf(%c,gvexs[v])。for(w=firstadjvex_hc(g,v)。w=0。w=nextadjvex_hc(g,v,w))if(!vis[w])dfs_hc(g,w)。}void dfstraverse_hc(mgraph_hc*g){int v,i。char f。for(v=0。vgvexnum。v++)vis[v]=FALSE。printf(輸入遍歷開始頂點:)。flushall()。scanf(%c,amp。f)。i=locatevex_hc(g,f)。printf(深度遍歷結果為:)。for(v=i。vgvexnum。v++)if(!vis[v])dfs_hc(g,v)。for(v=0。vi。v++)if(!vis[v])dfs_hc(g,v)。}int locatevexal_hc(algraph_hc*a,char v){int i,k=0。for(i=0。iavexnum。i++)if(avertices[i].data==v){k=i。i=avexnum。} return(k)。}char createlist_hc(algraph_hc*a,arode_hc*firstl,char v){arode_hc*nextl。if(v!=39。\n39。){nextl=(arode_hc*)malloc(sizeof(arode_hc))。nextladjvex=locatevexal_hc(a,v)。nextlnextarc=NULL。nextlinfo=firstlinfo。firstlnextarc=nextl。scanf(%c,amp。v)。v=createlist_hc(a,nextl,v)。}return(v)。}algraph_hc*createaludg_hc(){algraph_hc*a。int i,incinfo。char v。a=(algraph_hc*)malloc(sizeof(algraph_hc))。akind=UDG。printf(請輸入圖頂點數、邊數及該邊相關信息:)。scanf(%d %d %d,amp。avexnum,amp。aarum,amp。incinfo)。printf(請輸入頂點信息:)。flushall()。for(i=0。iavexnum。++i)scanf(%c,amp。avertices[i].data)。for(i=0。iavexnum。++i){printf(輸入%c的鄰接點:,avertices[i].data)。flushall()。scanf(%c,amp。v)。avertices[i].firstarc=(arode_hc*)malloc(sizeof(arode_hc))。avertices[i].firstarcadjvex=locatevexal_hc(a,v)。avertices[i].firstarcnextarc=NULL。if(incinfo)avertices[i].firstarcinfo=amp。incinfo。scanf(%c,amp。v)。v=createlist_hc(a,avertices[i].firstarc,v)。}return(a)。}visited_hc vis[MAX_VERTEX_NUM]。void dfsal_hc(algraph_hc*a,arode_hc*b,int k){vis[k]=TRUE。printf(%c,avertices[k].data)。while(b){k=badjvex。if(!vis[k]){b=avertices[k].firstarc。dfsal_hc(a,b,k)。}else b=bnextarc。}}void dfstraverseal_hc(algraph_hc*a){char f。int i=0,k。for(i=0。iavexnum。i++)vis[i]=FALSE。printf(遍歷開始頂點:)。flushall()。scanf(%c,amp。f)。k=locatevexal_hc(a,f)。printf(深度遍歷結果:)。for(i=k。iavexnum。i++)if(!vis[k])dfsal_hc(a,avertices[i].firstarc,i)。for(i=0。ik。i++)if(!vis[k])dfsal_hc(a,avertices[i].firstarc,i)。}void main(){algraph_hc*a。mgraph_hc*g。char c。printf(鄰接矩陣(M)\n)。printf(鄰接表(A)\n)。printf(請選擇:)。c=getchar()。while(c!=39。E39。){if(c==39。M39。){g=createudg_hc()。dfstraverse_hc(g)。}else if(c==39。A39。){a=createaludg_hc()。dfstraverseal_hc(a)。}printf(\n請選擇:)。flushall()。c=getchar()。}實驗九 圖的最小生成樹算法的實現實驗預備知識：1．理解圖最小生成樹的意義和相應算法。2．掌握帶權圖的存儲結構。一、實驗目的1．使學生熟悉最小生成樹的算法實現。2．掌握帶權圖的存儲結構和處理方法。二、實驗環境⒈ 硬件：每個學生需配備計算機一臺。操作系統：DOS或Windows；⒉ 軟件：DOS或Windows操作系統+Turbo C； 三、實驗要求1．能夠獨立完成帶權圖的存儲和最小生成樹的生成四、實驗內容1．在自己的U盤的“姓名+學號”文件夾中創建“實驗9”文件夾，本次實驗的所有程序和數據都要求存儲到本文件夾中。2．現在某電信公司要對如下圖的幾個城市之間進行光纖連接布線，請用合適的存儲結構將下圖存儲到計算機中方便進行處理。3．現在公司想以最小的代價將所有城市連通，方便所有城市間通信，請用普里姆算法和克魯斯卡爾算法實現本圖的最小生成樹。include include include define INFINITY 32767typedef enum{FALSE,TRUE}panduan_hc。typedef struct {int fromvex。 int endvex 。 int weight 。 int tags 。 }arclist_hc。 typedef struct {char *vexs。int **vexlist。arclist_hc *gelist。int **arcs。int vexnum, edgnum。 }stgraph_hc。 int locatevex_hc(stgraph_hc*st,char v){int i,k=0。for(i=0。istvexnum。i++)if(stvexs[i]==v){k=i。i=stvexnum。} return(k)。}stgraph_hc *creategraph_hc (){stgraph_hc *st。int i,j,x,y。char a,b。if(!(st=(stgraph_hc*)malloc(sizeof(stgraph_hc)))){printf(出錯!)。exit(0)。}printf(輸入圖的頂點數和邊數:)。scanf(%d %d,amp。stvexnum,amp。stedgnum)。if(!(stvexs=(char*)malloc(stvexnum*sizeof(char)))){printf(出錯!)。exit(0)。}if(!(stgelist=(arclist_hc*)malloc(stedgnum*sizeof(arclist_hc)))){printf(出錯!)。exit(0)。}if(!(starcs=(int**)malloc(stvexnum*sizeof(int*)))){printf(出錯!)。exit(0)。}if(!(stvexlist=(int**)malloc(stvexnum*sizeof(int*)))){printf(出錯!)。exit(0)。}for(i=0。istvexnum。i++){if(!(starcs[i]=(int*)malloc(stvexnum*sizeof(int)))){printf(出錯!)。exit(0)。}if(!(stvexlist[i]=(int*)malloc(stvexnum*sizeof(int)))){printf(出錯!)。exit(0)。}}printf(輸入頂點:)。flushall()。for(i=0。istvexnum。i++)scanf(%c,amp。stvexs[i])。printf(輸入邊及權值:\n)。for(i=0。istedgnum。i++){flushall()。scanf(%c%c %d,amp。a,amp。b,amp。stgelist[i].weight)。x=locatevex_hc(st,a)。y=locatevex_hc(st,b)。if(xy)stgelist[i].fromvex=x,stgelist[i].endvex=y。else stgelist[i].fromvex=y,stgelist[i].endvex=x。stgelist[i].tags=0。}for(i=0。istvexnum。i++)for(j=0。jstvexnum。j++)starcs[i][j]=0。for(i=0。istvexnum。i++){stvexlist[i][0]=i。for(j=1。jstvexnum。j++)stvexlist[i][j]=1。}return(st)。}int minweight_hc(stgraph_hc*st){int i,min。for(i=0。istedgnum。i++)if(!stgelist[i].tags){min=i。i=stedgnum。}for(i=0。istedgnum。i++)if(!stgelist[i].tagsamp。amp。stgelist[min].weightstgelist[i].weight)min=i。stgelist[min].tags=1。return(min)。}panduan_hc samegraph_hc(stgraph_hc *st,int a,int b){int i,j,k。panduan_hc f=FALSE。for(i=0。stvexlist[a][i]!=1amp。amp。!f。i++)for(j=0。stvexlist[b][j]!=1amp。amp。!f。j++)if(stvexlist[a][i]==stvexlist[b][j])f=TRUE。if(!f){for(i=0。istvexnum。i++){for(j=0。jstvexnumamp。amp。stvexlist[i][j]!=1。j++){if(stvexlist[i][j]==a){k=+j。while(stvexlist[i][k]!=1)k++。stvexlist[i][k]=b。j=stvexnum。}else if(stvexlist[i][j]==b){k=+j。while(stvexlist[i][k]!=1)k++。stvexlist[i][k]=a。j=stvexnum。}}}}return(f)。}stgraph_hc*minspandtree_hc(stgraph_hc*st){int i,a,b,min。for(i=0。istvexnum1。i++){min=minweight_hc(st)。a=stgelist[min].fromvex。b=stgelist[min].endvex。if(samegraph_hc(st,a,b))i。else starcs[a][b]=starcs[b][a]=stgelist[min].weight。}free(stvexlist)。free(stgelist)。return(st)。}void printst(stgraph_hc*st){int i,j。printf(最小生成樹為:\n)。for(i=0。istvexnum。i++){for(j=0。jstvexnum。j++)printf(%d\t,starcs[i][j])。printf(\n)。}printf(需要連通的點有:)。for(i=0。istvexnum。i++)for(j=i。jstvexnum。j++)if(starcs[i][j])printf(%c%c ,stvexs[i],stvexs[j])。}void main(){stgraph_