數(shù)據(jù)結(jié)構(gòu)物流信息管理系統(tǒng)課程設(shè)計

1、計算機(jī)與信息工程系 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告學(xué)號2014-2015學(xué)年 第一學(xué)期1308010119數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目：圖形染色問題求解專業(yè)：計算機(jī)科學(xué)與技術(shù)班級：13級計科（1）班姓名：劉爽爽學(xué)號：1308010119指導(dǎo)教師：王源成績：計算機(jī)與信息工程系二零一四年十月二十五日目 錄1 設(shè)計內(nèi)容及要求.11.1 設(shè)計內(nèi)容.11.2 設(shè)計任務(wù)及具體要求.12 概要設(shè)計.12.1 該系統(tǒng)的功能簡介.12.2 總體程序框圖.22.3 各個模塊之間的主要關(guān)系.23 設(shè)計過程或程序代碼.33.1 各個模塊的程序流程圖.33.2 對關(guān)鍵代碼加以分析說明.54 程序調(diào)試分析.75 小結(jié).9參考文獻(xiàn).9附

2、： 源程序.10 1 設(shè)計內(nèi)容及要求1.1設(shè)計內(nèi)容 圖形染色問題是將圖形的各個區(qū)域進(jìn)行染色，且相鄰區(qū)域所染色彩不同，該程序功能主要包括兩個模塊：1) 主程序模塊 void main()初始化；while接受命令；處理命令； 2) 圖形模塊實現(xiàn)圖形抽象數(shù)據(jù)類型模塊調(diào)用關(guān)系如下： 主程序模塊 地圖模塊1.2 設(shè)計任務(wù)及具體要求 主要利用數(shù)據(jù)結(jié)構(gòu)中的圖的存儲結(jié)構(gòu)等將圖形抽象化開發(fā)一個圖形染色問題的解決方案程序，應(yīng)擁有輸入圖，輸出圖，并輸出解決方案等功能。操作界面要符合用戶的一般習(xí)慣，圖形或文本界面都可以。 要求：明確課程設(shè)計的目的，能根據(jù)課程設(shè)計的要求，查閱相關(guān)文獻(xiàn)，為完成設(shè)計準(zhǔn)備必要的知識；提高學(xué)

3、生用高級語言進(jìn)行程序設(shè)計的能力，重點提高用數(shù)據(jù)結(jié)構(gòu)進(jìn)行文件操作和繪圖應(yīng)用的編程技術(shù)水平；進(jìn)一步了解軟件開發(fā)的一般方法和步驟；提高撰寫技術(shù)文檔的能力。 2 概要設(shè)計2.1 程序的功能簡介 該程序的主要功能是將圖形抽象化，并實現(xiàn)圖的輸入，圖的輸出和輸出圖形染色問題的解決方案2.2 總體程序框圖主程序調(diào)用LocateVex函數(shù)創(chuàng)建圖輸出圖調(diào)用trycolor函數(shù)當(dāng)s>G.vnum時，調(diào)用output函數(shù)輸出當(dāng)s<=G.vnum時，調(diào)用colorsame函數(shù)，判斷這個顏色能不能滿足要求結(jié)束開始2.3 各個板塊之間的關(guān)系 該程序的功能是實現(xiàn)圖的輸入，圖的輸出和該圖形的染色方案的輸出。各個模塊

4、之間是相互聯(lián)系的。首先，主函數(shù)包含了輸入圖，輸出圖和染色方案的輸出三個功能子函數(shù)，而這三個子函數(shù)也包含了其他子函數(shù)。主函數(shù)是整個函數(shù)的核心。子函數(shù)之間也有聯(lián)系，對圖的輸出和圖的染色方案的輸出是在圖的輸入子函數(shù)進(jìn)行后進(jìn)行的，因此對圖的輸出和圖的染色方案的輸出是非常重要的。 3 設(shè)計過程或程序代碼3.1 各個模板的程序流程圖1)主函數(shù)Graph G;/創(chuàng)建一個圖G=CreateGraph(G);/調(diào)用CreateGraph(G)函數(shù)，輸入抽象化圖形PrintGraph(G);/調(diào)用PrintGraph(G)函數(shù)，輸出該圖的鄰接矩陣printf("本次的著色方案為:n");try

5、color(1,G);/調(diào)用trycolor(1,G)函數(shù)，輸出染色方案 包含其他子函數(shù)并對其調(diào)用，主要功能為輸入抽象化圖形、輸出該圖的鄰接矩陣和輸出染色方案。2) 返回u在圖G中的位置函數(shù)int i;for(i=1;i<=G.vnum;i+)u=G.vexsi?真假return ii=G.vnum?真假printf("Error u!n");exit(1);return 0; 此函數(shù)主要功能是返回u在圖G中的位置，被CreateGraph(Graph G)調(diào)用。3) 輸入圖函數(shù)int i,j,k; vextype v1,v2;scanf("%d%d&quo

6、t;,&G.vnum,&G.arcnum);getchar();for(i=1;i<=G.vnum;i+)scanf("%c",&G.vexsi);getchar();for(i=0;i<=G.vnum;i+)for(j=0;j<=G.vnum;j+)G.arcsij=MAX;for(k=0;k<G.arcnum;k+)scanf("%c",&v1);getchar();scanf("%c",&v2);getchar();i=Locatevex(G,v1);j=Locat

7、evex(G,v2);G.arcsij=G.arcsji=w;return G;此函數(shù)的功能是實現(xiàn)圖的輸入，首先輸入頂點和邊數(shù)，建立一個初始化全為零的鄰接矩陣，在輸入一條邊的兩個頂點，調(diào)用Locatevex(Graph G,char u) 返回v1，v2在圖G中的位置，在將鄰接矩陣中對應(yīng)位置由零變?yōu)?。返回圖G。4) 輸出圖的鄰接矩陣函數(shù)int i,j;for(i=1;i<=G.vnum;i+)printf("%c",G.vexsi);printf("n");for(i=1;i<=G.vnum;i+)for(j=1;j<=G.vnum;

8、j+)printf("%d ",G.arcsij);printf("n");此函數(shù)的功能是將由CreateGraph(Graph G)返回的鄰接矩陣G輸出，從而實現(xiàn)對圖的輸出功能。5)顏色判斷函數(shù)int i,flag=0;for(i=1;i<=s-1;i+)G.arcsis=w&&colori=colors?真假flag=1;break;return flag; 此函數(shù)的功能是判斷這個顏色能不能滿足要求，被trycolor(int s,Graph G)調(diào)用，完成解決方案。6）圖形涂色函數(shù)int i;if(s>G.vnum)ou

9、tput(G);exit(1);elsefor(i=1;i<=N;i+)colors=i;if(colorsame(s,G)=0)trycolor(s+1,G);本函數(shù)是用來實現(xiàn)染色方案功能，在這里應(yīng)用了函數(shù)的遞歸，并調(diào)用colorsame(int s,Graph G)函數(shù)來進(jìn)行判斷這個顏色能不能滿足要求，當(dāng)s>G.vnum時，跳出遞歸，并輸出解決方案。3.2 對關(guān)鍵代碼加以分析說明 1）創(chuàng)建一個圖typedef struct 定義圖vextype vexsMAXedg;/存放邊的矩陣adjtype arcsMAXedgMAXedg;/圖的鄰接矩陣int vnum,arcnum;/

10、圖的頂點數(shù)和邊數(shù)Graph; 聲明一個類型圖，同時定義變量2）輸入圖函數(shù)Graph CreateGraph(Graph G)/輸入圖int i,j,k;vextype v1,v2;printf("依次輸入頂點數(shù)和邊數(shù):n");scanf("%d%d",&G.vnum,&G.arcnum);getchar();printf("圖的各個頂點分別為:n");for(i=1;i<=G.vnum;i+)scanf("%c",&G.vexsi); getchar();for(i=0;i<=G

11、.vnum;i+) for(j=0;j<=G.vnum;j+) G.arcsij=MAX; / 將矩陣所有元素初始化為0printf("輸入每條邊的兩個點:n");for(k=0;k<G.arcnum;k+)scanf("%c",&v1);getchar();scanf("%c",&v2);getchar();i=Locatevex(G,v1); /輸出v1在圖中的位置j=Locatevex(G,v2); /輸出v2在圖中的位置G.arcsij=G.arcsji=w; /一條邊的兩點在矩陣中表示為1 ret

12、urn G; 此函數(shù)的功能是實現(xiàn)圖的輸入，首先輸入頂點和邊數(shù)，建立一個初始化全為零的鄰接矩陣，在輸入一條邊的兩個頂點，調(diào)用Locatevex(Graph G,char u) 返回v1，v2在圖G中的位置，在將鄰接矩陣中對應(yīng)位置由零變?yōu)?。返回圖G。3）輸出圖的鄰接矩陣函數(shù)void PrintGraph(Graph G) int i,j;printf("此圖的頂點為:n");for(i=1;i<=G.vnum;i+)printf("%c",G.vexsi); / 輸出頂點printf("n");printf("此圖的鄰接

13、矩陣為:n");for(i=1;i<=G.vnum;i+) for(j=1;j<=G.vnum;j+)printf("%d ",G.arcsij); /輸出鄰接矩陣printf("n"); 此函數(shù)的功能是將由CreateGraph(Graph G)返回的鄰接矩陣G輸出，從而實現(xiàn)對圖的輸出功能。用戶可以對應(yīng)抽象化圖形判斷是否出錯。4）圖形涂色函數(shù)void trycolor(int s,Graph G) /s為開始圖色的頂點，本算法從1開始int i;if(s>G.vnum)/遞歸出口output(G);exit(1);elsef

14、or(i=1;i<=N;i+) /對每一種色彩逐個測試colors=i;if(colorsame(s,G)=0)trycolor(s+1,G); /進(jìn)行下一塊的著色 本函數(shù)是用來實現(xiàn)染色方案功能，在這里應(yīng)用了函數(shù)的遞歸，并調(diào)用colorsame(int s,Graph G)函數(shù)來進(jìn)行判斷這個顏色能不能滿足要求，當(dāng)s>G.vnum時，跳出遞歸，并輸出解決方案。4設(shè)計結(jié)果與分析如下圖，為一圖形的抽象化連接圖，頂點為ABCDEFG，相鄰邊為：AB AF BC BE BF CD CE CF DE EF EG FG，現(xiàn)有四種顏色，四種顏色分別對應(yīng)1，2，3，4，在圖形的各個區(qū)域進(jìn)行染色，且相

15、鄰的區(qū)域所染的顏色不能相同。由該問題來實驗程序功能。AFGBCED實驗結(jié)果如下： AFGBCED由解決方案對其染色，可以得到上圖，顯然程序的功能可以實現(xiàn)解決圖形染色問題。5 小結(jié)本次課程設(shè)計所選題目是“圖形染色問題求解”，在本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的過程，我先是將數(shù)據(jù)結(jié)構(gòu)的一些內(nèi)容有再次復(fù)習(xí)了一遍，然后就是對著電腦不停的分析問題解決問題寫代碼實驗，不然就是去圖書館或者網(wǎng)上翻閱資料、問老師同學(xué)。因為對圖的基礎(chǔ)知識不太牢固，出現(xiàn)了很多問題。也讓我體會到只有專業(yè)知識過硬基礎(chǔ)扎牢，在設(shè)計的時候做到夠細(xì)心和夠耐心才能設(shè)計好程序。此次數(shù)據(jù)結(jié)構(gòu)設(shè)計實驗的目的不僅僅加強(qiáng)了我們的動手能力，思考能力和解決問題的能力，

16、也讓我認(rèn)識到理論和實際的差別，學(xué)會了怎樣查閱資料，怎樣把理論與實際相結(jié)合，在此次課程設(shè)計充分的認(rèn)識到了自己的不足，構(gòu)思也借鑒了許多網(wǎng)上資料，調(diào)試也遇到了很多的低級錯誤，像定義錯誤，丟符號等等，最終還是完成了自己所選的設(shè)計題目，也積累了很多的實戰(zhàn)經(jīng)驗，為以后的學(xué)習(xí)打下了良好的基礎(chǔ)，也真正的認(rèn)識了自己的知識水平。參考文獻(xiàn)【1】數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，2003.【2】數(shù)據(jù)結(jié)構(gòu)題集（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，2005.【3】數(shù)據(jù)結(jié)構(gòu)（C語言版），劉大有，高等教育出版社，2004.【4】Data Structure with C+,William Ford.William

17、 Topp, 清華大學(xué)出版社，2003.附：源程序#include<stdio.h>#include<stdlib.h>#define MAX 0#define MAXedg 100#define N 4 /著色的顏色數(shù)#define w 1 /兩點之間的權(quán)值int color30=0; /來存儲對應(yīng)塊的對應(yīng)顏色typedef char vextype;typedef int adjtype;typedef struct 定義圖vextype vexsMAXedg;/存放邊的矩陣adjtype arcsMAXedgMAXedg;/圖的鄰接矩陣int vnum,arcnu

18、m;/圖的頂點數(shù)和邊數(shù)Graph;int Locatevex(Graph G,char u)/返回u在圖G中的位置int i;for(i=1;i<=G.vnum;i+)if(u=G.vexsi)return i;if(i=G.vnum)printf("Error u!n");exit(1);return 0;Graph CreateGraph(Graph G)/輸入圖int i,j,k;vextype v1,v2;printf("依次輸入頂點數(shù)和邊數(shù):n");scanf("%d%d",&G.vnum,&G.arc

19、num);getchar();printf("圖的各個頂點分別為:n");for(i=1;i<=G.vnum;i+) scanf("%c",&G.vexsi); getchar();for(i=0;i<=G.vnum;i+) for(j=0;j<=G.vnum;j+) G.arcsij=MAX; / 將矩陣所有元素初始化為0printf("輸入每條邊的兩個點:n");for(k=0;k<G.arcnum;k+)scanf("%c",&v1);getchar();scanf(&

20、quot;%c",&v2);getchar();i=Locatevex(G,v1); /輸出v1在圖中的位置j=Locatevex(G,v2); /輸出v2在圖中的位置G.arcsij=G.arcsji=w; /一條邊的兩點在矩陣中表示為1return G;void PrintGraph(Graph G) /輸出圖的信息int i,j;printf("此圖的頂點為:n");for(i=1;i<=G.vnum;i+)printf("%c",G.vexsi); / 輸出頂點printf("n");printf("此圖的鄰接矩陣為:n");for(i=1;i<=G.vnum;i+) for(j=1;j<=G.vnum;j+)printf(&qu