數(shù)據(jù)結(jié)構(gòu)課程設(shè)計地圖著色問題

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計地圖著色問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、課程設(shè)計報告課程設(shè)計題目：地圖著色問題專業(yè)：xxxxxxxxx班級：xxxxxxxxx姓名：xxxxxxxxx17一：需求分析：1)已知中國地圖，對各省進(jìn)行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少；2)將各省進(jìn)行編號，然后利用無向圖個頂點(diǎn)之間的邊來表示各省的相鄰關(guān)系；3)演示程序以用戶和計算機(jī)的對話方式進(jìn)行；4)最后對結(jié)果做出簡單分析。二：概要設(shè)計一：設(shè)計思路把34個省看成34個頂點(diǎn)，從選定的第一個頂點(diǎn)開始著色，先試第一種顏色，如果這個顏色與這個頂點(diǎn)的其他鄰接頂點(diǎn)的顏色不重復(fù)，則這個頂點(diǎn)就是用這種顏色，程序開始

2、對下一個頂點(diǎn)著色；如果著色重復(fù)，則使用下一種顏色重復(fù)上面的操作。著色過程就是一個遞歸的過程，直到所有的頂點(diǎn)都處理完后結(jié)束著色。二：數(shù)據(jù)結(jié)構(gòu)設(shè)計因?yàn)檫@個程序是對圖的操作，所以程序采用的邏輯結(jié)構(gòu)是圖狀，存儲結(jié)構(gòu)選用鄰接表，考慮用鄰接表是因?yàn)橐话愕牡貓D的某一個頂點(diǎn)并不會與很多的頂點(diǎn)相鄰接，如果用鄰接矩陣會浪費(fèi)很多的存儲空間，所以我選擇的鄰接表來存儲。其中：typedefstructArcNode{intx;（表示與當(dāng)前頂點(diǎn)所表示省份相鄰的省份的位置信息）structArcNode*next;（指向下一個弧結(jié)點(diǎn)）}ArcNode;（表示

3、省份之間相鄰關(guān)系的弧結(jié)點(diǎn)）typedefstruct{char*name;（頂點(diǎn)所表示的省份的名稱）intcolor;（省份的顏色，用數(shù)字表示不同的顏色）ArcNode*firstnext;（指向第一個?。﹠shengfen[35];17三：詳細(xì)設(shè)計該程序一共包含三個模版：分別為初始化模版、著色模版和輸出模版。1.初始化模塊聲明表示省份的頂點(diǎn)信息、省份之間相鄰關(guān)系的弧的信息，并為其賦值。2.著色模塊為各個省份著色。for(i=1;i<=34;i++){sheng[i].color=0;}for(i=1;i<=34;i++){j=

4、1;p=sheng[i].firstnext;while(p!=NULL){while(p!=NULL&&j!=sheng[p->x].color){p=p->next;}if(p!=NULL)j++;}sheng[i].color=j;}3.輸出模塊輸出各個省份的顏色信息。for(i=1;i<=34;i++){printf("%s:",sheng[i].name);printf("%d",sheng[i].color);}printf("/n0表示白色,1表示藍(lán)色,2表示紅色,3表示綠色,4表示黃色");return0;1

5、7四：調(diào)試分析因?yàn)槲覀兊某绦蛞阎侵袊貓D，為中國地圖染色，所以程序沒有輸入，只有輸出信息。從輸出的信息來看，我們最多使用了4種顏色。關(guān)于程序測試時存在的問題，我們程序在寫完之后，出現(xiàn)了沒有錯誤但是無法輸出信息的問題，從網(wǎng)上查找發(fā)現(xiàn)是對警告沒處理好的原因，隨后我們參考了網(wǎng)上的解決方案把問題解決了。關(guān)于程序的改進(jìn)，我們的程序使用的是有向圖，但省份之間的相鄰關(guān)系用無向圖就可以表示，這是程序可以改進(jìn)的地方。其次，我們的程序輸出結(jié)果描述省份顏色的是數(shù)字，也可以改進(jìn)后使之輸出具體的顏色。17五：源程序清單#include

6、#includetypedefstructArcNode{intx;structArcNode*next;}ArcNode;typedefstruct{char*name;intcolor;ArcNode*firstnext;}shengfen[35];intmain(){shengfensheng;inti,j;ArcNode*p,*hu1,*hu2,*hu3,*hu4,*hu5,*hu6,*hu7,*hu8,*hu9,*hu10,*hu11,*hu12,*hu13,*hu14,*hu15,*hu16,*h

7、u17,*hu18;ArcNode*hu19,*hu20,*hu21,*hu22,*hu23,*hu24,*hu25,*hu26,*hu27,*hu28,*hu29,*hu30,*hu31,*hu32,*hu33,*hu34,*hu35;ArcNode*hu36,*hu37,*hu38,*hu39,*hu40,*hu41,*hu42,*hu43,*hu44,*hu45,*hu46,*hu47,*hu48,*hu49,*hu50,*hu51,*hu52;ArcNode*hu53,*hu54,*hu55,*hu56,*hu57,*h

8、u58,*hu59,*hu60,*hu61,*hu62,*hu63,*hu64,*hu65,*hu66;ArcNode*hu67,*hu68,*hu69,*hu70,*hu71,*hu72,*hu73,*hu74,*hu75,*hu76,*hu77,*hu78,