數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

PAGEPAGE13淮陰工學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告選題名稱:無向圖應(yīng)用問題系（院）:計算機工程學(xué)院專業(yè): 計算機科學(xué)與技術(shù) 班級:網(wǎng)絡(luò)1111姓名:1111311105指導(dǎo)教師:周海巖單勁松 學(xué)年學(xué)期: 2012~2013學(xué)年第1學(xué)期 2012 年12 月20 日

設(shè)計任務(wù)書課題名稱無向圖應(yīng)用問題設(shè)計目的1．掌握關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，如線性表、樹、圖建立過程及操作算法；2．掌握常用算法的實現(xiàn)方法及作用；3．理解利用數(shù)據(jù)結(jié)構(gòu)及算法解決實際問題的思想；4．學(xué)會資料收集與整理方法，學(xué)會撰寫實習(xí)報告；5．學(xué)會對所學(xué)知識進行總結(jié)，加深對課堂知識的理解與掌握。實驗環(huán)境1．Windows2000以上操作系統(tǒng)；2．C++，C#或Java編程工具。任務(wù)要求1．利用課余時間去圖書館或上網(wǎng)查閱課題相關(guān)資料，深入理解課題含義及設(shè)計要求，注意材料收集與整理；2．在第15周末之前完成預(yù)設(shè)計，請指導(dǎo)教師審查通過后進行下一步工作；3．按所設(shè)計方案進行軟設(shè)計；4．完成系統(tǒng)設(shè)計，寫出報告初稿方可申請參加答辯；5．結(jié)束后，及時提交實習(xí)報告（含紙質(zhì)稿、電子稿）。工作進度計劃序號起止日期工作內(nèi)容12012.11.12~2012.11.25查閱資料，提出設(shè)計方案。22012.11.26~2012.12.8根據(jù)提出設(shè)計方案逐項完成。32012.12.24~2012.12.30在機房實現(xiàn)軟件系統(tǒng)、系統(tǒng)調(diào)試。42013.1.3~2013.1.6根據(jù)教師反饋意見，修改、完善、上交實習(xí)報告。指導(dǎo)教師：2012年11月10日摘要：本課程設(shè)計是設(shè)計的關(guān)于無向圖應(yīng)用問題的課程。通過此課程，我們可以解決n個城市間設(shè)計通信網(wǎng)絡(luò)，使其造價最低。以及當(dāng)其造價最低的時候我們應(yīng)該怎樣設(shè)計。本課程實際是通過應(yīng)用Prim算法來求最小生成樹。將n個城市和各邊的權(quán)值建立成鄰接矩陣，再應(yīng)用Prim算法就能完成。關(guān)鍵詞：Prim算法；鄰接矩陣；最小生成樹；無向圖

目錄TOC\o"1-2"\h\z1需求分析 131需求分析 131.1課程設(shè)計題目 131.2課程設(shè)計任務(wù) 131.3課程設(shè)計思想 132概要設(shè)計 132.1本課程設(shè)計的總體結(jié)構(gòu) 133詳細設(shè)計和實現(xiàn) 133.1源代碼 133.2算法流程圖 133.3模塊的功能描述 133.4算法原理 133.5程序運行截圖 13總 結(jié) 13致 謝 13參考文獻 13

1需求分析1.1課程設(shè)計題目無向圖應(yīng)用問題1.2課程設(shè)計任務(wù)如果以無向網(wǎng)表示n個城市之間通信網(wǎng)絡(luò)的建設(shè)計劃，頂點表示城市，邊上的權(quán)表示該線路的造價，設(shè)計一個方案，使這個通訊網(wǎng)的總造價最低。1.3課程設(shè)計思想本課程設(shè)計主要應(yīng)用如何生成最小生成樹，以及Prim算法。2概要設(shè)計2.1本課程設(shè)計的總體結(jié)構(gòu)本課程設(shè)計的總體結(jié)構(gòu)分為4個部分。2.1.1第1部分設(shè)定了城市數(shù)目為5，并且設(shè)定了每條邊的權(quán)值。2.1.2第2部分設(shè)計了一個Prim函數(shù)。并且通過Prim算法來求最小生成樹。而Prim算法的具體實現(xiàn)步驟：1：初始化：U={u0},TE={f}。此步驟設(shè)立一個只有結(jié)點u0的結(jié)點集U和一個空的邊集TE作為最小生成樹的初始形態(tài)，在隨后的算法執(zhí)行中，這個形態(tài)會不斷的發(fā)生變化，直到得到最小生成樹為止。2：在所有u∈U,v∈V－U的邊（u,v）∈E中，找一條權(quán)最小的邊（u0,v0），將此邊加進集合TE中，并將此邊的非U中頂點加入U中。此步驟的功能是在邊集E中找一條邊，要求這條邊滿足以下條件：首先邊的兩個頂點要分別在頂點集合U和V－U中，其次邊的權(quán)要最小。找到這條邊以后，把這條邊放到邊集TE中，并把這條邊上不在U中的那個頂點加入到U中。這一步驟在算法中應(yīng)執(zhí)行多次，每執(zhí)行一次，集合TE和U都將發(fā)生變化，分別增加一條邊和一個頂點，因此，TE和U是兩個動態(tài)的集合，這一點在理解算法時要密切注意。3：如果U=V，則算法結(jié)束；否則重復(fù)步驟2。可以把本步驟看成循環(huán)終止條件。我們可以算出當(dāng)U=V時，步驟2共執(zhí)行了n－1次（設(shè)n為圖中頂點的數(shù)目），TE中也增加了n－1條邊，這n－1條邊就是需要求出的最小生成樹的邊。2.1.3第3部分設(shè)計了一個creatlist函數(shù)。該函數(shù)可以用來得出當(dāng)是最小生成樹的時候的排列順序。2.1.4第4部分設(shè)計了一個main()函數(shù)。該函數(shù)用來對整個課程設(shè)計進行運行。它調(diào)用了Prim算法和creatlist函數(shù)。對5個城市的通信網(wǎng)絡(luò)建立鄰接矩陣然后對運用Prim算法，再調(diào)用creatlist()函數(shù)，將最小生成樹時的排列進行輸出。3詳細設(shè)計和實現(xiàn)3.1源代碼#include<stdio.h>#include<iostream>#definen5#definemax1000.0typedefstructnode{ intno; floatwgt; structnode*next;}edgenode;typedefstruct{ charvtx; edgenode*link;}vexnode;floatgali[n][n]={{0,2,12,10,max},{2,0,8,max,9},{12,8,0,6,3},{10,max,6,0,7},{max,9,3,7,0}};typedefvexnodeGraph[n];GraphG;voidprim(vexnodeG[],intk){ intv2link[n],vset[n],parent[n],w[n]; edgenode*ptr; intx,s,ecount,i,y,z,f; s=-1; x=k; vset[k]=-1; v2link[n]=-1; ecount=0; for(i=0;i<n;i++) if(i!=k) vset[i]=3; while(ecount<n-1) { ptr=G[x].link; while(ptr!=NULL) { y=ptr->no; if((vset[y]==2)&&(ptr->wgt<w[y])) { parent[y]=x; w[y]=ptr->wgt; } if(vset[y]==3) { vset[y]=2; v2link[y]=s; s=y; parent[y]=x; w[y]=ptr->wgt; } ptr=ptr->next; } if(s==-1) break; z=x=s; y=v2link[x]; f=-1; while(y!=-1) { if(w[y]<w[x]) { x=y; f=z; } z=y; y=v2link[y]; } if(f==-1) s=v2link[x]; else v2link[f]=v2link[x]; vset[x]=1; ecount++; } printf("\nroot%c:\t",G[k].vtx); for(i=0;i<n;i++) { if(i!=k) { printf("%c",G[i].vtx); f=parent[i]; printf("%c\t",G[f].vtx); } }}voidcreatlist(vexnodega[]){ inti,j; edgenode*se; for(i=0;i<n;i++) { ga[i].vtx='a'+i; for(j=0;j<n;j++) { if((gali[i][j]<max)&&(gali[i][j]!=0)) { se=(edgenode*)malloc(sizeof(*se)); se->no=j; se->next=ga[i].link; se->wgt=gali[i][j]; ga[i].link=se; } } }}main(){ inti; edgenode*ve; creatlist(G); for(i=0;i<n;i++) { printf("\nv%c=link:",G[i].vtx); ve=G[i].link; while(ve!=NULL) { printf("%dw=%.2f\t",ve->no,ve->wgt);ve=ve->next; } } prim(G,4); return0;開始Prim算法開始Prim算法Creatlist函數(shù)Main()函數(shù)調(diào)用Prim()調(diào)用creatlist()輸出結(jié)果及安排結(jié)束3.2算法流程圖3.3模塊的功能描述Prim算法的功能描述：Prim算法是用來求出最小生成樹。Creatlist()函數(shù)的功能描述：creatlist()函數(shù)可以將Prim算法求出來的最小生成樹進行輸出。Main()函數(shù)的功能描述：main()函數(shù)是該程序的主函數(shù)，它先對Prim算法進行調(diào)用，將5個城市及其邊的權(quán)值進行最小生成樹的生成，然后再調(diào)用了creatliast()函數(shù)，運用creatlist()函數(shù)，將Prim算法求出的最小生成樹輸出。3.4算法原理Prim算法的基本思想：假設(shè)G=（V，E）是一個具有n個頂點的連通網(wǎng)，T=(U,TE)是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，U和TE的初值均為空集。算法開始時，首先從V中任取一個頂點（假定取V0），將它并入U中，此時U={V0}，然后只要U是V的真子集，就從那些其一個端點已在T中，另一個端點仍在T外的所有邊中，找一條最短（即權(quán)值最小）邊，假定為（i,j），其中Vi∈U,Vj∈(V-U),并把該邊（i,j）和頂點j分別并入T的邊集TE和頂點集U，如此進行下去，每次往生成樹里并入一個頂點和一條邊，直到n-1次后就把所有n個頂點都并入到生成樹T的頂點集中，此時U=V，TE中含有n-1條邊，T就是最后得到的最小生成樹?？梢钥闯?，在普利姆算法中，是采用逐步增加U中的頂點，常稱為“加點法”。為了實現(xiàn)這個算法在本設(shè)計中需要設(shè)置一個輔助數(shù)組closedge[]，以記錄從U到V-U具有最小代價的邊。當(dāng)輔助數(shù)組中存在兩個或兩個以上的最小代價的邊時，此時最小生成樹的形態(tài)就不唯一，此時可以在程序中采用遞歸的算法思想求出每個最小生成樹。而在Prim算法中需要解決2個問題①在無向網(wǎng)中，當(dāng)出現(xiàn)從一個頂點到其它頂點時，若其邊上的權(quán)值相等，則可能從某一起點出發(fā)時會得出不同的最小生成樹，但最小生成樹的權(quán)必定都相等，此時我們應(yīng)該怎樣將所有的最小生成樹求解出來；②每次如何從生成樹T中到T外的所有邊中，找出一條最短邊。例如，在第k次（1≤k≤n-1）前，生成樹T中已有k個頂點和k-1條邊，此時T中到T外的所有邊數(shù)為k(n-k)，當(dāng)然它也包括兩頂點間沒有直接邊相聯(lián)，其權(quán)值被看做常量INFINIT的邊在內(nèi)，從如此多的邊中查找最短邊，其時間復(fù)雜度為O(k(n-k))，顯然是很費時的，是否有一種好的方法能夠降低查找最短邊的時間復(fù)雜度。而針對這2個問題其解決方法如下：針對①中出現(xiàn)的問題可以通過在算法中實現(xiàn)，詳情請看PRIM算法的基本思想；針對②中出現(xiàn)的問題，通過對PRIM算法的分析，可以使查找最短邊的時間復(fù)雜度降低到O(n-k)。具體方法是假定在進行第k次前已經(jīng)保留著從T中到T外的每一頂點（共n-k個頂點）的各一條最短邊，進行第k次時，首先從這n-k條最短邊中，找出一條最最短的邊，它就是從T中到T外的所有邊中的最短邊，假設(shè)為（i,j），此步需進行n-k次比較；然后把邊（i,j）和頂點j分別并入T中的邊集TE和頂點集U中，此時T外只有n-(k+1)個頂點，對于其中的每個頂點t，若（j,t）邊上的權(quán)值小于已保留的從原T中到頂點t的最短邊的權(quán)值，則用（j,t）修改之，使從T中到T外頂點t的最短邊為（j,t），否則原有最短邊保持不變，這樣，就把第k次后從T中到T外每一頂點t的各一條最短邊都保留下來了，為進行第k+1次運算做好了準(zhǔn)備，此步需進行n-k-1次比較。所以，利用此方法求第k次的最短邊共需比較2(n-k)-1次，即時間復(fù)雜度為O(n-k)。3.5程序運行截圖

總 結(jié)在這次課程設(shè)計中，感覺自己學(xué)到了不少知識，以往在上機實驗過程中，書上總有相關(guān)的代碼可以讓我們參考，但是在這次課程設(shè)計中，是要獨立的設(shè)計出一個真正的程序，在開始的時候我們使用了上學(xué)期C++所學(xué)到的關(guān)于文本輸入輸出的程序，但是在和同伴的討論過程中，發(fā)現(xiàn)僅僅只是輸入輸出流的應(yīng)用，并沒有數(shù)據(jù)結(jié)構(gòu)中的知識，所以我們就否定了原來的程序，重新做了這個程序，在這個程序中使用了鏈表存儲相關(guān)信息，在編寫程序中，動手能力得到了很大的提高，同時對鏈表的知識得到了很大的鞏固。在編寫過程中，遇到了很多的問題，比如開始的時候算法不正確，后來的編寫程序中對程序函數(shù)不能正確認識，但是在后來查閱資料和與同伴討論中，很多的問題都得到了良好的解決?？傊@次的課程設(shè)計對我來說是受益匪淺。對于此次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計來說，我覺的我最大的收獲就是學(xué)會了如何使用最小生成樹以及Prim算法的基本原理及其應(yīng)用。讓我理解了Prim算法是不斷迭代進行的。此算法的精妙之處在于對求權(quán)值最小的邊這一問題的分解（也正是由于這種分解，而導(dǎo)致了算法理解上的困難）。按照常規(guī)的思路，這一問題應(yīng)該這樣解決：分別從集合V－U和U中取一頂點，從鄰接矩陣中找到這兩個頂點行成的邊的權(quán)值，設(shè)V－U中有m個頂點，U中有n個頂點，則需要找到m*n個權(quán)值，在這m*n個權(quán)值中，再查找權(quán)最小的邊。循環(huán)每執(zhí)行一次，這一過程都應(yīng)重復(fù)一次，相對來說計算量比較大。而本算法則利用了變量tree中第k+1到第n－1號元素來存放到上一循環(huán)為止的一些比較結(jié)果，如以第k+1號元素為例，其存放的是集合U中某一頂點到頂點tree.en的邊，這條邊是到該點的所有邊中權(quán)值最小的邊，所以，求權(quán)最小的邊這一問題，通過比較第k+1號到第n－1號元素的權(quán)的大小就可