數(shù)據(jù)機(jī)構(gòu)實(shí)驗(yàn)報(bào)告重要的

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

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

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

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

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

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

7、為5條，成為一個(gè)連通分量，T就是G的一棵最小生成樹。 主要功能模塊流程圖Krushal算法描述：void kruskal(ALGraph G)int i,j,min=MAX,k=0, cost=0;/min用于記錄最小權(quán)值int setMAX_VERTEX_NUM; /判斷兩個(gè)點(diǎn)是否在同一集合里Node *p,*q,*s;printf(n公路最優(yōu)方案方案為：n);printf(起點(diǎn) 終點(diǎn) 路程n);for(i = 0; i G.vexnum; +i) seti = i; /初始化，將每個(gè)點(diǎn)自身作為一個(gè)集合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) /判斷兩點(diǎn)是否在同一集合，若不在，則輸出這條邊 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公路總長(zhǎng)為：%dn,cost);系統(tǒng)測(cè)試初始界面運(yùn)行界面如下輸入城鎮(zhèn)數(shù)和邊數(shù)，按enter鍵輸入個(gè)城鎮(zhèn)的名稱運(yùn)行界面如下輸入每條邊的起點(diǎn)終點(diǎn)和距離運(yùn)行界面如下按enter鍵輸出結(jié)果得到鄰接矩陣和公路最優(yōu)方案的公路總長(zhǎng)運(yùn)行界面如下退出（五）結(jié)論利用數(shù)據(jù)結(jié)構(gòu)中的克魯斯卡爾算法求最小生成樹，繼而求的公路最優(yōu)求解方案，得到了個(gè)城市之間的最短路徑。通過兩周的數(shù)據(jù)結(jié)構(gòu)課程實(shí)訓(xùn)，我不僅對(duì)圖的概念有了一個(gè)新的認(rèn)識(shí)，而且對(duì)算法和

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

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

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

13、頭向量的結(jié)點(diǎn)-*/typedef struct VNodestruct Road data;/VertexType data; Node *firstarc;VNode,AdjListMAX_VERTEX_NUM;/定義圖結(jié)點(diǎn)/*鏈表帶權(quán)圖的結(jié)構(gòu)信息-*/typedef struct Vertex vexsMAX_VERTEX_NUM; /*頂點(diǎn)向量*/ AdjMatrix arcs; /*鄰接距陣*/AdjList vertices; /城鎮(zhèn) int vexnum,arcnum;ALGraph;/定義圖 int LocateVe(ALGraph G,VertexType u)/鏈表求出點(diǎn)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; /*頂點(diǎn)向量*/ AdjMatrix arcs; /*鄰接距陣*/ int vexnum,arcnum; /*頂點(diǎn)數(shù)和弧數(shù)*/; int LocateVex(MGraph G,Vertex u)/矩陣求點(diǎn)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(鄰接矩陣請(qǐng)輸入城鎮(zhèn)數(shù)和邊數(shù)(分別以空格為分隔):n); scanf(%d %d,&G.vexnum,&G.arcnum); printf(鄰接矩陣請(qǐng)輸入%d個(gè)城鎮(zhèn)名:n,G.vexnum); for(i=0;iG.vexnum;+i) /* 讀入頂點(diǎn)信息*/ 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(鄰接矩陣請(qǐng)輸入%d條邊各自的起點(diǎn),終點(diǎn),以及之間的距離(分別用空格分隔):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; /*對(duì)

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(請(qǐng)輸入城鎮(zhèn)數(shù),邊數(shù)(請(qǐng)用空格分開):n); /*輸入頂點(diǎn)數(shù)、弧數(shù)*/scanf(%d %d,&G.vexnum,&G.arcnu

18、m);printf(請(qǐng)輸入各城鎮(zhèn)的名稱:n);for(i = 0; i G.vexnum; +i) /*初始化頂點(diǎn)值*/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; /判斷兩個(gè)點(diǎn)是否在同一集合里Node *p,*q,*s;printf(n公路最優(yōu)方案方案為：n);printf(起點(diǎn) 終點(diǎn) 路程n);for(i = 0; i G.vex