1、淮北師范大學(xué)程序設(shè)計課程設(shè)計通訊錄管理系統(tǒng)學(xué) 院 計算機科學(xué)與技術(shù) 專 業(yè) 計算機科學(xué)與技術(shù)(師范) 學(xué) 號 20091201019 學(xué) 生 姓 名 葛晨晨 指導(dǎo)教師姓名 陳美榮 2011年4月14日設(shè)計目的要求任務(wù)目的解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。設(shè)計要求核心數(shù)據(jù)結(jié)構(gòu)用到的結(jié)構(gòu)體要采用動態(tài)內(nèi)存分配和鏈表結(jié)構(gòu)。不同的功能使用不同的函數(shù)實現(xiàn)（模塊化），對每個函

2、數(shù)的功能和調(diào)用接口要注釋清楚。對程序其它部分也進行必要的注釋。對系統(tǒng)進行功能模塊分析、畫出總流程圖和各模塊流程圖。用戶界面要求使用方便、簡潔明了、美觀大方、格式統(tǒng)一。所有程序需調(diào)試通過。任務(wù) 輸入城鎮(zhèn)的個數(shù)N，和一個N*N的矩陣A，其中元素aij表示城鎮(zhèn)i和城鎮(zhèn)j的實際距離。求解能夠連通所有城鎮(zhèn)的最小公路集（即通過prim算法或者kruskal算法求解如何在N個城鎮(zhèn)之間建設(shè)最少條（N-1）公路，且公路總里程最短，使得各個城鎮(zhèn)之間可以相互到達）。算法的基本思想運用結(jié)構(gòu)體和鏈表1. 使用如下結(jié)構(gòu)來存儲城鎮(zhèn)以及城鎮(zhèn)之間距離信息，是本程序的核心數(shù)據(jù)結(jié)構(gòu)，定義如下：typedef struct Road

3、int marked; /*修建公路標志*/int vertex1; /*城鎮(zhèn)a*/int vertex2; /*城鎮(zhèn)b*/int weight; /*城鎮(zhèn)a,b間距離*/;2.使用鏈表實現(xiàn)的存儲，鏈表中結(jié)點結(jié)構(gòu)定義如下：typedef struct node /*每個結(jié)點的數(shù)據(jù)結(jié)構(gòu)*/ struct Road data; /*數(shù)據(jù)域，放學(xué)生基本信息*/ struct node *next; /*指針域*/Node,*Edge; 程序應(yīng)具有以下基本功能：（1） 輸入一個二維數(shù)組An*n來表示每對城鎮(zhèn)間的距離，并根據(jù)A建立相應(yīng)的鏈表；（2） prim 和kruskal算法的求解最小生成樹；（3）

4、 從指定的城鎮(zhèn)出發(fā)，求解最小公路集，輸出公路建設(shè)方案，并給出最短公路長度。定義一：圖圖是有一個非空的頂點集合和一個描述頂點之間的關(guān)系即邊的集合組成。它可以形式化的定義為：G=(V,E)V= | VertexTypeE=|,VP(,)其中，G表示一個圖，V是圖G中頂點的集合，E是V中頂點偶對的有限集，這些頂點偶對稱為邊，VertexType是用于描述頂點類型，集合E中P(,)的含義是：對有向圖來說用“”表示，對無向圖來說用“（）”表示，即從到 兩個頂點之間存在邊。定義二：鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個圖，其中V=v1,v2,vn。G的鄰接矩陣是一個具有下列性質(zhì)的n階

5、方陣：（本文主要為無向圖的鄰接矩陣）（1） 無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。（1）無向圖的鄰接矩陣中第i行第j列表示i結(jié)點到j(luò)結(jié)點的度即權(quán)值，可以表示為某一具體應(yīng)用的數(shù)據(jù)。也表示i結(jié)點是否與j結(jié)點連通。定義三：鄰接表 是圖的一種鏈式存儲結(jié)構(gòu)。在鄰接表中，對圖中每個頂點建立一個單鏈表，在第i個單鏈表中的結(jié)點表示依附于頂點vi的邊每個結(jié)點由3個域組成，其中鄰接點域指示與頂點vi鄰接的點在途中的位置，鏈域指示下一條邊或弧的結(jié)點；數(shù)據(jù)域存儲和邊和弧相關(guān)的信息?？唆斔箍査惴ㄔO(shè)G=(V，E)是網(wǎng)絡(luò)，最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V，)，T中每個頂點自成

6、為一個連通分量。將集合E中的邊按權(quán)遞增順序排列，從小到大依次選擇頂點分別在兩個不同連通分量中的邊加入圖T，則原來的兩個連通分量由于該邊的連接而成為一個連通分量。依次類推，直到T中所有頂點都在同一個連通分量上為止，該連通分量就是G的一棵最小生成樹.初始時，T為只有6個頂點的非連通圖。邊(v1, v2)的兩個頂點v1，v2分別屬于兩個連通分量，將邊(v1, v2)加入T。同理，將邊(v1, v3)加入T。由于邊(v2, v3)的兩個頂點v2，v3屬于同一個連通分量，因此，舍去這條邊。同理將邊(v0, v1)、(v1, v5)加入T，邊(v3, v5)舍去，邊(v3, v4)加入T。這時T中含的邊數(shù)

7、為5條，成為一個連通分量，T就是G的一棵最小生成樹。 主要功能模塊流程圖Krushal算法描述：void kruskal(ALGraph G)int i,j,min=MAX,k=0, cost=0;/min用于記錄最小權(quán)值int setMAX_VERTEX_NUM; /判斷兩個點是否在同一集合里Node *p,*q,*s;printf(n公路最優(yōu)方案方案為：n);printf(起點 終點 路程n);for(i = 0; i G.vexnum; +i) seti = i; /初始化，將每個點自身作為一個集合while(kG.vexnum-1)for(i=0;inext) /查找最小權(quán)值的邊if(

8、p-data.weightdata.weight;q=p;j=i;if(G.verticesj.firstarc=q) G.verticesj.firstarc=q-next; /if-else用于刪除最小權(quán)值的邊elsefor(p=G.verticesj.firstarc;p!=q;p=p-next) s=p;s-next=q-next;if(setj!=setq-data.marked) /判斷兩點是否在同一集合，若不在，則輸出這條邊 printf(%s-%s %dn,G.verticesj.data.vertex1,G.verticesq-data.marked.data.vertex1

9、,q-data.weight);cost=cost+q-data.weight;k+; setj=setq-data.marked;min=MAX; /將min置為最大值printf(n公路總長為：%dn,cost);系統(tǒng)測試初始界面運行界面如下輸入城鎮(zhèn)數(shù)和邊數(shù)，按enter鍵輸入個城鎮(zhèn)的名稱運行界面如下輸入每條邊的起點終點和距離運行界面如下按enter鍵輸出結(jié)果得到鄰接矩陣和公路最優(yōu)方案的公路總長運行界面如下退出（五）結(jié)論利用數(shù)據(jù)結(jié)構(gòu)中的克魯斯卡爾算法求最小生成樹，繼而求的公路最優(yōu)求解方案，得到了個城市之間的最短路徑。通過兩周的數(shù)據(jù)結(jié)構(gòu)課程實訓(xùn)，我不僅對圖的概念有了一個新的認識，而且對算法和

10、C語言有了更深的理解，在學(xué)習(xí)離散數(shù)學(xué)的時候，總覺得圖是很抽象的東西，但是在學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)這門課后，我慢慢地體會到了其中的奧妙，圖能夠在計算機中存在，首先要捕捉他有哪些具體化、數(shù)字化的信息，比如說權(quán)值、頂點個數(shù)等，這也是說明了想要把生活中的信息轉(zhuǎn)化成到計算機中必須用數(shù)字來完整的構(gòu)成一個信息庫，而圖的存在，又涉及到了頂點之間的聯(lián)系，圖分為有向圖和無向圖，而無向圖又是有向圖在權(quán)值雙向相等下的一種特例。在這次求可使構(gòu)成n個城市的最小生成樹的程序設(shè)計中，我采用了a i j數(shù)組利用鄰接矩陣方式來儲存城市與城市間信息，再利用經(jīng)典的克魯斯克爾算法求得了最小生成樹。在這次課程設(shè)計中，我明白了編寫一段代碼，我們不

11、僅要考慮它的可行性，更應(yīng)該考慮它的算法復(fù)雜度，運行效率。做同一件事，一萬個人有一萬種做法，換而言之，一萬個人寫一段代碼實現(xiàn)同一個功能可以得到一萬段代碼。由此，我們可以看出做一件事要精益求精，多加斟酌。（六）、源程序及系統(tǒng)文件使用說明#include #include #include#define MAX 100#define MAX_NAME 5 /*頂點值最大字符數(shù)*/#define MAX_VERTEX_NUM 20 /*最大頂點數(shù)*/typedef char VertexMAX_NAME;/*(鄰接矩陣用)頂點名字串*/ typedef char VertexTypeMAX_NAME;

12、/*(鄰接鏈表用)頂點名字串*/ typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*鄰接距陣*/ typedef struct Roadint marked; /*修建公路標志*/VertexType vertex1; /*城鎮(zhèn)a*/int vertex2; /*城鎮(zhèn)b*/int weight; /*城鎮(zhèn)a,b 間距離*/Road;typedef struct node /*每個結(jié)點的數(shù)據(jù)結(jié)構(gòu)*/struct Road data; /*數(shù)據(jù)域，放學(xué)生基本信息*/struct node *next; /*指針域*/Node,*Edge;/*表

13、頭向量的結(jié)點-*/typedef struct VNodestruct Road data;/VertexType data; Node *firstarc;VNode,AdjListMAX_VERTEX_NUM;/定義圖結(jié)點/*鏈表帶權(quán)圖的結(jié)構(gòu)信息-*/typedef struct Vertex vexsMAX_VERTEX_NUM; /*頂點向量*/ AdjMatrix arcs; /*鄰接距陣*/AdjList vertices; /城鎮(zhèn) int vexnum,arcnum;ALGraph;/定義圖 int LocateVe(ALGraph G,VertexType u)/鏈表求出點u所

14、在位置 int i; for(i=0;iG.vexnum;+i)if(strcmp(G.verticesi.data.vertex1,u) = 0)return i; return -1; /*矩陣帶權(quán)圖的結(jié)構(gòu)信息-*/ struct MGraph Vertex vexsMAX_VERTEX_NUM; /*頂點向量*/ AdjMatrix arcs; /*鄰接距陣*/ int vexnum,arcnum; /*頂點數(shù)和弧數(shù)*/; int LocateVex(MGraph G,Vertex u)/矩陣求點u所在位置 int i; for(i=0;iG.vexnum;+i)if(strcmp(u,

15、G.vexsi)=0) return i; return -1; /*-*/*鄰接矩陣的存入算法-*/*-*/建立帶權(quán)鄰接矩陣結(jié)構(gòu)/建立帶權(quán)鄰接矩陣結(jié)構(gòu)void CreateGraph(MGraph &G) int i,j,k,w; char c; Vertex va,vb; printf(鄰接矩陣請輸入城鎮(zhèn)數(shù)和邊數(shù)(分別以空格為分隔):n); scanf(%d %d,&G.vexnum,&G.arcnum); printf(鄰接矩陣請輸入%d個城鎮(zhèn)名:n,G.vexnum); for(i=0;iG.vexnum;+i) /* 讀入頂點信息*/ scanf(%s,G.vexsi); for(i

16、=0;iG.vexnum;i+) /*初始化鄰接矩陣*/ for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij=9999; for(k=0;kG.arcnum;+k) /*讀入邊*/ printf(鄰接矩陣請輸入%d條邊各自的起點,終點,以及之間的距離(分別用空格分隔):n,k+1); scanf(%s%s,va,vb); scanf(%s,&c); if(0c&c9) w=c-0; else printf(ERRORn); exit (0); i=LocateVex(G,va); j=LocateVex(G,vb); G.arcsij=G.arcsji=w; /*對

17、稱*/ printf(所得到的鄰接矩陣為:n); for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) printf( %d ,G.arcsij); printf(n); void k1()MGraph g; CreateGraph(g); /*-*/*鄰接表的克魯斯卡爾算法-*/-*/鄰接表創(chuàng)建帶權(quán)圖void CreateGraph(ALGraph &G) int i,j,k,w;VertexType va,vb;printf(請輸入城鎮(zhèn)數(shù),邊數(shù)(請用空格分開):n); /*輸入頂點數(shù)、弧數(shù)*/scanf(%d %d,&G.vexnum,&G.arcnu

18、m);printf(請輸入各城鎮(zhèn)的名稱:n);for(i = 0; i G.vexnum; +i) /*初始化頂點值*/scanf(%s,G.verticesi.data.vertex1); strcpy(G.vexsi,G.verticesi.data.vertex1);/for(i = 0; i G.vexnum; +i) /初始化vertices數(shù)組G.verticesi.firstarc = NULL; for(i=0;iG.vexnum;i+) /*初始化鄰接矩陣*/ for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij=9999;for(k = 0; k

19、data.marked=j;/初始化p-data.weight=w;p-next=G.verticesi.firstarc; /插表頭G.verticesi.firstarc=p;Node *q = (Node *)malloc(sizeof(Node); q-data.marked=i;q-data.weight=w;q-next=G.verticesj.firstarc;G.verticesj.firstarc=q; printf(所得到的鄰接矩陣為:n);/*輸出矩正*/ for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) printf( %d ,G.arcsij); printf(n); /*鄰接表的克魯斯卡爾算法*/void kruskal(ALGraph G)int i,j,min=MAX,k=0, cost=0;/min用于記錄最小權(quán)值int setMAX_VERTEX_NUM; /判斷兩個點是否在同一集合里Node *p,*q,*s;printf(n公路最優(yōu)方案方案為：n);printf(起點 終點 路程n);for(i = 0; i G.vex