數(shù)據(jù)結(jié)構(gòu)——地圖填色問題

1、數(shù)據(jù)結(jié)構(gòu)實驗報告 院系 光電與信息工程學(xué)院 專業(yè) 電子信息工程 姓名 學(xué)號 電話2011級 2班 2013年 5月 22日實驗題目數(shù)據(jù)結(jié)構(gòu)期末綜合實驗地圖填色問題二、問題描述1976 年。美國科學(xué)家 APPEL 和 HAKEN 利用計算機(jī)證明了：對一張地圖，可以用不超過4 種顏色對其填色，使得相鄰的區(qū)域填上不同的顏色。要求輸入一張行政區(qū)地圖，用4 種顏色對其填色，要求相鄰的行政區(qū)域內(nèi)沒有相同的顏色，給出所有的填色方案，并統(tǒng)計方案個數(shù)。三、數(shù)據(jù)描述首先考慮如何存儲行政區(qū)域圖，由于鄰接矩陣能更好地描述各行政區(qū)之間的關(guān)系，所以采用鄰接矩陣 G 來存 儲地圖。G I , J =1 表示 I ， J 兩

2、個行政區(qū)域相鄰，為 0 表示不相鄰可采用二維數(shù)組來表示鄰接矩陣G；另外設(shè)一數(shù)組 COLORI 記錄各行政區(qū)域所填顏色， 分別取值為 1（紅色），2（黃色），3（藍(lán)色），4（綠色）；數(shù)據(jù)描述如下：INT GNN;INT COLORN+1;四、概要設(shè)計1） 全局變量定義#define MAX_VERTEX_NUM 26 / 最大行政區(qū)域個數(shù)/ 鄰接矩陣數(shù)據(jù)類型的定義 typedef structchar vexsMAX_VERTEX_NUM; / 行政區(qū)域 -頂點向量int acrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 鄰接矩陣int vexnum;/ 地圖當(dāng)前行政區(qū)域個數(shù)

3、Graph ;int ColorMAX_VERTEX_NUM+1;/ 地圖行政區(qū)域填充的顏色存儲數(shù)組long int Count=0;/ 統(tǒng)計總共的填色方案個數(shù)2） 本程序主要包含 6 個函數(shù) ：主函數(shù) main（）Printf_Graph ()Load_Color ()Print_Color ()顯示行政區(qū)域的鄰接矩陣關(guān)系 對地圖行政區(qū)域進(jìn)行第一次著色 對地圖行政區(qū)域進(jìn)行各種方案著色的顯判斷這個顏色對第 n 行政區(qū)域能不能滿足要求 各函數(shù)間調(diào)用關(guān)系如下：Same_ColorMainSame_Color( 3) 主函數(shù)的偽碼main() 定義一個鄰接矩陣 G； 創(chuàng)建地圖及行政區(qū)域的鄰接矩陣；

4、顯示行政區(qū)域的鄰接矩陣關(guān)系； 對地圖進(jìn)行填充顏色； 改變顏色，顯示多種方案；五、詳細(xì)設(shè)計/ 鄰接矩陣數(shù)據(jù)類型的定義 #define MAX_VERTEX_NUM 26 / 最大行政區(qū)域個數(shù) typedef structchar vexsMAX_VERTEX_NUM;/ 行政區(qū)域 -頂點向量int acrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 鄰接矩陣int vexnum;/ 地圖當(dāng)前行政區(qū)域個數(shù)Graph ;/* 函數(shù)： Create_Graph *功能：建立地圖的鄰接矩陣* 說明：輸入?yún)?shù) Graph *G 本函數(shù)很好的完成了地圖的創(chuàng)建以及行政區(qū)域之間的存儲。 在輸入

5、錯誤的時候，會有相應(yīng)的指示，使得程序更加健壯。*/void Create_Graph( Graph *G ) / 建立地圖行政區(qū)域的鄰接矩陣 輸入地圖的行政區(qū)域的個數(shù) G->vexnum ； 輸入行政區(qū)域，構(gòu)造行政區(qū)域 -頂點向量 ； 初始化鄰接矩陣都為 0；構(gòu)造行政區(qū)域鄰接矩陣； 輸入與 V1 相鄰的行政區(qū)域，存放于 S 數(shù)組中； 相鄰的行政區(qū)域 G->acrsij=1 ； /* * 函數(shù)： Printf_Graph *功能：顯示地圖行政區(qū)域的鄰接矩陣 * 說明：輸入?yún)?shù) Graph G 。本函數(shù)很好的完成了地圖行政區(qū)域的鄰接矩陣的顯示 */ void Printf_Graph(

6、 Graph G )構(gòu)造圖形； 橫向顯示 行政區(qū)域； 縱向顯示 行政區(qū)域； 顯示鄰接矩陣；/* * 函數(shù)： Same_Color*功能：判斷這個顏色對第 n 行政區(qū)域能不能滿足要求 *說明：輸入?yún)?shù) Graph G，int n ，輸出 0 則表示滿足，輸出 1 則表示不滿足int Same_Color(Graph G,int n)Colorn 分別與前面已經(jīng)著色的幾塊比較； 相鄰并且顏色一樣，則不滿足； 顏色滿足 返回 0 顏色不滿足 返回 1/* 函數(shù)： Load_Color* 功能：對地圖行政區(qū)域進(jìn)行第一次著色，始之滿足要求*說明：輸入?yún)?shù) Graph G ，int n void Load

7、_Color( Graph G , int n )取一種顏色I(xiàn)f( 顏色滿足，沒有與前面沖突 ) 下一塊行政區(qū)域著色 Load_Color(G ,n+1);Else 嘗試另一種顏色 * 函數(shù)： Print_Color*功能：對地圖行政區(qū)域進(jìn)行各種方案的顯示。 *說明：輸入?yún)?shù) Graph G ，int m 注意：調(diào)用本函數(shù)的前提是 Color 數(shù)組中有一個正確的填充顏色的方案。void Print_Color( Graph G , int m)for(i=1;i<=4;i+) 更換顏色，新的顏色不與前面沖突，顏色滿足 下一個行政區(qū)域 Print_Color( G , m+1 ) ; 直到

8、(到最后一個行政區(qū)域 ,遞歸出口) 遍歷數(shù)組 Color ，顯示所有行政區(qū)域顏色，新的方案；主函數(shù)Void main()定義一個鄰接矩陣 G； 創(chuàng)建地圖及行政區(qū)域的鄰接矩陣； 顯示行政區(qū)域的鄰接矩陣關(guān)系； 對地圖進(jìn)行填充顏色； 改變顏色，顯示多種方案；六、測試結(jié)果七、參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)八、附錄#include <stdio.h>#include <math.h>#include <stdlib.h>#include <string.h>/* 數(shù)據(jù)結(jié)構(gòu)期末綜合實驗 */題目：地圖填色問題 #define MAX_VERTEX_NUM 26 / 最大行

9、政區(qū)域個數(shù) / 鄰接矩陣數(shù)據(jù)類型的定義 typedef structchar vexsMAX_VERTEX_NUM; / 行政區(qū)域 -頂點向量 int acrsMAX_VERTEX_NUMMAX_VERTEX_NUM; / 鄰接矩陣 int vexnum; / 地圖當(dāng)前行政區(qū)域個數(shù) Graph ;/* 函數(shù)： Create_Graph*功能：建立地圖的鄰接矩陣* 說明：輸入?yún)?shù) Graph *G 本函數(shù)很好的完成了地圖的創(chuàng)建以及行政區(qū)域之間的存儲。 在輸入錯誤的時候，會有相應(yīng)的指示，使得程序更加健壯。void Create_Graph( Graph *G )int i , j , k , t

10、;char sMAX_VERTEX_NUM;char tempMAX_VERTEX_NUM;char V1 , V2 ;/ 建立地圖行政區(qū)域的鄰接矩陣/ 變量的定義/ 暫時存放與某一行政區(qū)域相鄰的行政區(qū)域/ 臨時數(shù)組/ 相鄰的兩個行政區(qū)域的頂點向量Start:G->vexnum =0;printf(" 輸入地圖的行政區(qū)域的個數(shù)/ 初始化，總的行政區(qū)域個數(shù)為(不超過 26 個 ):t");scanf("%d",&G->vexnum);gets(temp);if( G->vexnum <1|G->vexnum >2

11、7) goto Start;/ 輸入的數(shù)值不在 026 之間重新開始for(i=0;i<G->vexnum;i+)New_Input:for(t=0;t<MAX_VERTEX_NUM;t+)/ 構(gòu)造 行政區(qū)域 - 頂點向量/ 清空 temp 數(shù)組tempt=NULL;printf(" 請輸入第 %d 個行政區(qū)域 ( 用 az 單字符表示 ):",i+1);scanf("%c" , &G->vexsi); gets(temp);if(G->vexs i>'z'|G->vexs i<&#

12、39;a') / 輸入的單字符不符合，重新輸入printf(" 輸入的單字符不符合，重新輸入 n");goto New_Input;if(strlen(temp)>0) / 輸入的不為單字符，重新輸入printf(" 輸入的不為單字符，重新輸入 n");goto New_Input;for(t=0;t<i;t+) / 檢測當(dāng)前輸入的行政區(qū)域與之前有沒有沖突， 有沖突， 重新輸 入if(G->vexs i=G->vexs t)printf(" 輸入的行政區(qū)域之前已經(jīng)輸入過，重新輸入 n");goto Ne

13、w_Input;for(i=0;i<G->vexnum;i+)/初始化鄰接矩陣for(j=0;j<G->vexnum;j+)G->acrsij=0 ;/都為 0for(k=0;k<G->vexnum;k+)/構(gòu)造行政區(qū)域鄰接矩陣New_Inputs:printf(" 請輸入與 %c 相鄰的行政區(qū)域 ,已有相鄰行政區(qū)域有： " ,G->vexsk); for(t=0;t<G->vexnum ;t+) / 顯示與 Mg->vexsk 已經(jīng)相鄰的行政區(qū)域 if(G->acrskt=1) printf(&quo

14、t;%c ",G->vexst);printf("n");V1=G->vexsk;/ V1 行政區(qū)域i=k; / 確定 v1 在 G->vexs 中的位置 為 i/ 清空 S 數(shù)組/ 輸入與 V1 相鄰的行政區(qū)域，存放于 S 數(shù)組中for(t=0;t<MAX_VERTEX_NUM;t+) st=NULL;t=0;while(t<G->vexnum)scanf("%c" , &st); if(s0='n') break; if(getchar()='n') break;

15、t+;/ 沒有的話就直接跳出for(t=0;t<G->vexnum ;t+) / 確定行政區(qū)域 V1 與其相鄰的行政區(qū)域的關(guān)系，遍歷數(shù)組Sif(st!=NULL&&st!='n')V2=st;for(j=0;G->vexsj!=V2;j+);if(j>G->vexnum)/ V2 行政區(qū)域 / 確定 v2/在 G 中的位置 為 j 輸入的元素不正確則顯示錯誤 ,要求重新輸入printf(" 輸入有誤， goto New_Inputs;請重新輸入n");if(V1!=V2)/輸入的相鄰行政區(qū)域與本身不相同G->

16、;acrsij=G->acrsji=1;/置 v1,v2的對稱弧 v2,v1 /* 函數(shù)： Printf_Graph *功能：顯示地圖行政區(qū)域的鄰接矩陣* 說明：輸入?yún)?shù) Graph G 。本函數(shù)很好的完成了地圖行政區(qū)域的鄰接矩陣的顯示void Printf_Graph( Graph G )int i , j ;printf(" 地圖的鄰接矩陣表示，相鄰的用1表示 n" );printf(" " );for(i=0;i<G .vexnum ;i+) printf("%c" ,G.vexs i);printf("n

17、" );for(i=0;i<G .vexnum*4+3 ;i+) printf("-" );/ 構(gòu)造圖形/ 橫向顯示 行政區(qū)域/ 顯示相應(yīng)長度的 -printf("n" );for(i=0;i<G .vexnum ;i+)printf("%c " ,G.vexs i);/ 縱向顯示 行政區(qū)域for(j=0;j<G.vexnum ;j+)printf("%d " ,G.acrsij); / 顯示鄰接矩陣printf("n" );/ int ColorMAX_VERTEX

18、_NUM+1; / 地圖行政區(qū)域填充的顏色存儲數(shù)組 long int Count=0; / 統(tǒng)計總共的填色方案個數(shù) /* 函數(shù)： Same_Color*功能：判斷這個顏色對第 n 行政區(qū)域能不能滿足要求*說明：輸入?yún)?shù) Graph G，int n ，輸出 0 則表示滿足，輸出 1 則表示不滿足int Same_Color(Graph G,int n)int i ;for(i=0;i<n;i+)/ 分別與前面已經(jīng)著色的幾塊比較if(G.acrs ni=1&&Colori=Colorn)/相鄰并且顏色一樣，則不滿足return 1; / 與前面顏色有沖突，返回 1，表示該顏色

19、不滿足 return 0; / 沒有沖突，該顏色滿足，返回 0*函數(shù)：Load_Color*功能：對地圖行政區(qū)域進(jìn)行第一次著色，始之滿足要求*說明：輸入?yún)?shù) Graph G ，int nvoid Load_Color( Graph G , int n ) / 遞歸出口int i ;if(n>=G.vexnum )printf("n" );elsefor(i=1;i<=4;i+)Colorn=i;if(Same_Color(G ,n)=0)Load_Color(G ,n+1); break;/ 存儲顏色/ 顏色滿足，沒有與前面沖突/ 下一塊行政區(qū)域/* 函數(shù)： Print_Color *功能：對地圖行政區(qū)域進(jìn)行各種方案的顯示。*說明：輸入?yún)?shù) Graph G ，int m 注意：調(diào)用本函數(shù)的前提是 Color 數(shù)組中有一個正確的填充顏色的方案。void Print_Color( Graph G , int m) int i=0, j=0;for(i=1;i<=4;i+) Colorm=i;if(Same_Color(G,m)=0)if(m=G.vexnu