數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-----最小套圈設(shè)計(jì)

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p>　　最小套圈設(shè)計(jì)(課題名稱)</p><p><b>　　目 錄</b></p><p><b>　　1 設(shè)計(jì)題目1</b></p><p><b>　　2 設(shè)計(jì)分析1</b>

2、;</p><p><b>　　3 設(shè)計(jì)實(shí)現(xiàn)3</b></p><p><b>　　4.1測(cè)試目的5</b></p><p>　　4.2 測(cè)試輸入5</p><p>　　4.3 正確輸出6</p><p>　　4.4 實(shí)際輸出6</p><p&g

3、t;<b>　　5 分析與探討7</b></p><p>　　5.1 測(cè)試結(jié)果分析7</p><p>　　5.2 探討與改進(jìn)7</p><p><b>　　6 設(shè)計(jì)小結(jié)9</b></p><p>　　1 設(shè)計(jì)題目 </p><p>　　套圈游戲是游樂場(chǎng)中

4、常見的游戲之一，其規(guī)則為：游戲者將手中的圓環(huán)套圈投向場(chǎng)中的玩具，被套中的玩具就作為獎(jiǎng)品獎(jiǎng)給游戲者。</p><p>　　現(xiàn)給定一個(gè)套圈游戲場(chǎng)的布局，固定每個(gè)玩具的位置，請(qǐng)你設(shè)計(jì)圓環(huán)套圈的半徑尺寸，使得它每次最多只能套中一個(gè)玩具。但同時(shí)為了讓游戲看起來更具有吸引力，這個(gè)全套的半徑又需要盡可能大。</p><p>　　把問題進(jìn)一步簡(jiǎn)化，假設(shè)每個(gè)玩具都是平面上的一個(gè)沒有面積的點(diǎn)，套圈是簡(jiǎn)單的圓。

5、一個(gè)玩具被套住，是指這個(gè)點(diǎn)到圓心的距離嚴(yán)格小于圓半徑。如果有兩個(gè)玩具被放在同一個(gè)位置，那么輸出的圓半徑就是0。</p><p><b>　　輸入要求：</b></p><p>　　輸入由若干組測(cè)試數(shù)據(jù)組成。</p><p>　　每組數(shù)據(jù)的第1行包含一正整數(shù)N（2<=N<=100000）,代表場(chǎng)地中玩具的個(gè)數(shù)。接下來有N行輸入，每行包

6、含一個(gè)玩具的x和y的坐標(biāo)。當(dāng)N為0時(shí)，表示全部測(cè)試結(jié)束，不要對(duì)該數(shù)據(jù)做任何處理。</p><p><b>　　輸出要求：</b></p><p>　　對(duì)每一組測(cè)試，在一行里輸出符合要求的套圈半徑，精確到小數(shù)點(diǎn)后兩位。</p><p><b>　　2 設(shè)計(jì)分析</b></p><p>　　首先必須認(rèn)識(shí)

7、到，找到最小距離點(diǎn)對(duì)之后，將套圈半徑取為這個(gè)最小距離的一半，就一定滿足題目的要求。所以，問題實(shí)質(zhì)上是經(jīng)典的求最近點(diǎn)對(duì)的問題。</p><p>　　一個(gè)最簡(jiǎn)單的做法是用二重循環(huán)把所有可能的點(diǎn)對(duì)遍歷，計(jì)算全部（N-1）N/2個(gè)距離，從中找出最小值。這個(gè)算法的時(shí)間復(fù)雜度顯然是O(N²)，當(dāng)測(cè)試數(shù)據(jù)規(guī)模比較大時(shí)，會(huì)導(dǎo)致超時(shí)，必須設(shè)計(jì)時(shí)間復(fù)雜度為O(Nlog2N)的算法。</p><p>

8、　　一種解法是“分而治之”，如圖6.2所示。將所有點(diǎn)按其x坐標(biāo)排序，從中間將場(chǎng)地一分為二，遞歸地解決了兩邊場(chǎng)地的子問題，分別得到兩個(gè)子問題的最小半徑&左和&右——這個(gè)過程是“分“；在所有橫跨分界線的點(diǎn)對(duì)中找出距離最近的點(diǎn)對(duì)，并將這個(gè)距離作為&中與兩個(gè)子問題的解&左和&右進(jìn)行比較，其中最小的值即為問題的最終解——這個(gè)過程稱為”治“。這個(gè)問題的難點(diǎn)在于”治“，即求出所有橫跨分界線的點(diǎn)對(duì)中距離最近的點(diǎn)對(duì)

9、。如果這個(gè)過程的算法復(fù)雜度不能減少到O(N),則整體復(fù)雜度將仍然是O(N2),不能滿足要求。</p><p>　　圖6.2 “分而治之”示意圖</p><p>　　注意到如果&中真正能起作用，則應(yīng)有&中<&=min{&左，&右}，只須考慮中分線&范圍以內(nèi)的點(diǎn)，如圖（2-2）中陰影所示的中間帶狀區(qū)域。同理，中間帶內(nèi)若兩點(diǎn)的y坐標(biāo)之差

10、大于&，則這樣的點(diǎn)對(duì)也不必考慮，這就將搜索的范圍大大縮小了?？蓪⒅虚g帶內(nèi)的點(diǎn)按其y坐標(biāo)排序。對(duì)任一點(diǎn)Pi，只需向下比較Pj(j>i),一旦|Pi*y-Pj*y|>&,則可結(jié)束對(duì)Pi的考慮而轉(zhuǎn)向考慮Pi+1。</p><p>　　由&的定義可知，對(duì)任一P，最壞情況下也只須比較5個(gè)點(diǎn)，如圖（2-3）所示。這是因?yàn)樵谧笥覂蓚€(gè)&*&的正方形區(qū)域內(nèi)，若Pi占據(jù)了某個(gè)正方形

11、的一腳，則該正方形內(nèi)不可能有點(diǎn)，否則該點(diǎn)與Pi的距離必然小于&，與& 的定義矛盾。所以最壞情況只有6個(gè)點(diǎn)剛好落在兩個(gè)正方形的角點(diǎn)上，而其中一個(gè)點(diǎn)是Pi。</p><p>　　圖6.3 計(jì)算d中所涉及的中間帶</p><p>　　圖6.4 矩形域內(nèi)點(diǎn)的稀疏性</p><p>　　這樣就可以在O(N)時(shí)間內(nèi)解決d中的計(jì)算。</p>

12、;<p>　　還有一點(diǎn)必須注意，不可以在每次遞歸中都對(duì)點(diǎn)的y坐標(biāo)重新排序，否則整體復(fù)雜度還是不能降低。解決方法是在執(zhí)行分治法之前對(duì)點(diǎn)集進(jìn)行兩次預(yù)排序，保存兩個(gè)點(diǎn)列：一是按坐標(biāo)排序后的點(diǎn)列，另一為按y坐標(biāo)排序后的點(diǎn)列。完成預(yù)排序后，遞歸時(shí)就可以順序掃描按y坐標(biāo)排序后的點(diǎn)列，根據(jù)x坐標(biāo)所在的左右子集劃分，將點(diǎn)按其y坐標(biāo)有序地分別放進(jìn)左右兩個(gè)子集中。該過程的時(shí)間復(fù)雜度是O(N).</p><p><

13、b>　　3 設(shè)計(jì)實(shí)現(xiàn)</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <math.h></p><p>　　#define MAX_POINTS 100000 /*

14、坐標(biāo)點(diǎn)數(shù)的最大值 */</p><p>　　#define MAX_TEST 100 /*最大測(cè)試次數(shù)*/</p><p>　　typedef struct { /*定義坐標(biāo)點(diǎn)*/</p><p><b>　　float x;</b></p><p><b>　　float y;</b

15、></p><p><b>　　}Point;</b></p><p>　　float dist(Point a, Point b) { /*求兩個(gè)坐標(biāo)點(diǎn)之間的距離*/</p><p>　　return sqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));</p

16、><p><b>　　}</b></p><p>　　float Nearest(Point* points, int n){ /*求最小距離*/</p><p>　　float temp1,temp2,temp3,temp,nearest;</p><p>　　float left,right,d; /*

17、當(dāng)n小于4時(shí)，T(n)=O(1)；*/</p><p><b>　　int i,j;</b></p><p>　　if(n==1) return 999999999; /*一個(gè)點(diǎn)情形,返回值模擬無窮*/</p><p>　　if(n==2) return dist(points[0], points[1]); /*

18、兩個(gè)點(diǎn)情形*/</p><p>　　if(n==3){ /*三個(gè)點(diǎn)情形*/</p><p>　　temp1=dist(points[0], points[1]);</p><p>　　temp2=dist(points[0], points[2]);</p><p>　　temp3=dis

19、t(points[1], points[2]);</p><p>　　return temp3<((temp1<temp2)?temp1:temp2)?temp3:((temp1<temp2)?temp1:temp2);</p><p><b>　　}</b></p><p>　　/*多于3點(diǎn)的情形，用分治法*/</

20、p><p>　　left=Nearest(points,n/2); /*遞歸求解*/</p><p>　　right=Nearest(&points[n/2],n-n/2);</p><p>　　d=left<right?left:right;</p><p>　　/*綜合中間帶求得最小距離*/</p>&l

21、t;p>　　//將P1和P2中所有S的點(diǎn)按其y坐標(biāo)排好序，則對(duì)P1中所有點(diǎn)p，</p><p>　　//對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者，</p><p>　　//對(duì)P1中每一點(diǎn)最多只要檢查P2中排好序的相繼6個(gè)點(diǎn)。</p><p>　　nearest=d;</p><p>　　for(i=0;i<n/2

22、;i++)</p><p>　　/* 通過掃描子集一中每個(gè)點(diǎn)檢查子集二中與其距離在d之內(nèi)的</p><p>　　所有點(diǎn)(最多6個(gè))以完成合并*/</p><p>　　for(j=n/2;j<n&&(fabs(points[j].y-points[i].y)<d);j++){</p><p>　　temp=dist(

23、points[i],points[j]);</p><p>　　nearest=nearest<temp?nearest:temp;</p><p><b>　　}</b></p><p>　　return nearest;</p><p><b>　　}</b></p><

24、;p>　　int compx(const void* a, const void* b) {</p><p>　　/*實(shí)現(xiàn)按x排序*/</p><p>　　return ((Point*)a)->x-((Point*)b)->x;</p><p><b>　　}</b></p><p>

25、　　int compy(const void* a, const void* b) {</p><p>　　/*實(shí)現(xiàn)按y排序*/</p><p>　　return ((Point*)a)->y-((Point*)b)->y;</p><p><b>　　}</b></p><p>　　void

26、 main() {</p><p>　　int i,j=0,numPoints;</p><p>　　Point points[MAX_POINTS];</p><p>　　float result[MAX_TEST]; /*記錄結(jié)果*/</p><p>　　for(i=0;i<MAX_TEST;i++) resu

27、lt[i]=-1;</p><p>　　printf("請(qǐng)輸入數(shù)據(jù)：\n");</p><p>　　while(1){ /*進(jìn)行多次測(cè)試*/</p><p>　　loop: scanf("%d", &numPoints);</p><p>　　if(

28、!numPoints) break;</p><p>　　if(numPoints<0||numPoints>MAX_POINTS) {</p><p>　　printf("Error!\n"); /*容錯(cuò)處理*/</p><p>　　goto loop;</p><p><b>　　}&

29、lt;/b></p><p>　　for(i=0; i<numPoints; i++) /*輸入點(diǎn)的數(shù)量及點(diǎn)的坐標(biāo)值*/</p><p>　　scanf("%f %f", &points[i].x, &points[i].y);</p><p>　　/*預(yù)排序，在使用分治法之前，預(yù)先將S中的n個(gè)點(diǎn)依其y

30、坐標(biāo)排序好。*/</p><p>　　qsort(points, numPoints, sizeof(Point), compx);</p><p>　　qsort(points, numPoints/2, sizeof(Point), compy);</p><p>　　qsort(points+numPoints/2, numPoints-numPoin

31、ts/2, sizeof(Point), compy);</p><p>　　result[j]=Nearest(points, numPoints)/2;</p><p><b>　　j++;</b></p><p><b>　　}</b></p><p><b>　　i=0;<

32、/b></p><p>　　printf("\n最短距離分別為：\n");</p><p>　　while(result[i]!=-1) /*輸出測(cè)試結(jié)果*/</p><p>　　printf("%.2f\n",result[i++]);</p><p><b>　　}</b

33、></p><p><b>　　4.1測(cè)試目的</b></p><p>　?。?）處理數(shù)據(jù)速度的快慢程度。</p><p>　?。?）驗(yàn)證程序是否正確。</p><p>　?。?）在不同數(shù)據(jù)的測(cè)試下進(jìn)行數(shù)據(jù)有效性驗(yàn)證。</p><p>　?。?）檢測(cè)程序的優(yōu)越性等問題。</p>

34、<p><b>　　4.2 測(cè)試輸入</b></p><p><b>　　第一種輸入：</b></p><p><b>　　第二種輸入：</b></p><p><b>　　第三種輸入：</b></p><p><b>　　4.3 正

35、確輸出</b></p><p><b>　　(1)第一種輸出：</b></p><p><b>　　0.71</b></p><p><b>　　0.00</b></p><p><b>　　0.75</b></p><p&

36、gt;<b>　　(2)第二種輸出：</b></p><p><b>　　Error！</b></p><p><b>　　Error！</b></p><p><b>　　(3)第三種輸出：</b></p><p><b>　　0．52<

37、/b></p><p><b>　　4.4 實(shí)際輸出 </b></p><p><b>　　(1)第一種輸出：</b></p><p><b>　　(2)第二種輸出：</b></p><p><b>　　(3)第三種輸出：</b></p>

38、<p><b>　　5 分析與探討</b></p><p>　　5.1 測(cè)試結(jié)果分析 </p><p>　?。?）輸出的結(jié)果與實(shí)際預(yù)算的結(jié)果相一致。驗(yàn)證成功。</p><p>　?。?）輸出的結(jié)果與實(shí)際預(yù)算的結(jié)果相一致。驗(yàn)證成功。</p><p>　?。?）輸出的結(jié)果與實(shí)際預(yù)算的結(jié)果相一致。驗(yàn)證成功。<

39、;/p><p><b>　　5.2 探討與改進(jìn)</b></p><p>　　一種最簡(jiǎn)單的方法就是將二重循環(huán)把任何可能的點(diǎn)對(duì)進(jìn)行遍歷，計(jì)算全部（N-1）N/2的距離，計(jì)算中求出最小值。（其核心代碼設(shè)計(jì)如下）：</p><p>　　float dist(Point a,Point b) </p><p><b>

40、;　　{</b></p><p>　　return sqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));</p><p><b>　　}</b></p><p>　　float nearest(Point* points, int n) {</p><

41、;p>　　float near=100000,temp;</p><p><b>　　int i,j;</b></p><p>　　if(n==1) return 0;</p><p><b>　　else{</b></p><p>　　for(i=0; i<n; i++)</p&

42、gt;<p>　　for(j=0; j<n; j++){</p><p>　　if(i==j) continue;</p><p><b>　　else {</b></p><p>　　temp=dist(points[i],points[j]);</p><p>　　near=(near>t

43、emp)?temp:near;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return near;</p><p><b>　　}</b></p><p><b>　　}</b&

44、gt;</p><p>　　此代碼的計(jì)算時(shí)間T(n)=2T(n/2)+O(n2)。它的解為T(n)=O(n2)，即與合并步驟的耗時(shí)同階，顯示不出比用窮舉的方法好。從解遞歸方程的套用公式法，我們看到問題出在合并步驟耗時(shí)太多。這樣做算法效率與其他算法相比效率太低，需要O(n2)的計(jì)算時(shí)間。</p><p>　　因此我們需要改進(jìn)新的方法，需要高效率設(shè)計(jì)新的算法，因此不由的想到了計(jì)算時(shí)間下界為Ω(

45、nlogn)。這個(gè)下界引導(dǎo)我們?nèi)フ覇栴}的一個(gè)θ(nlogn)算法。因此選擇“分而治之”圓環(huán)套圈的方法。（其核心代碼設(shè)計(jì)如下）</p><p>　　float dist(Point a, Point b) { /*求兩個(gè)坐標(biāo)點(diǎn)之間的距離*/</p><p>　　return sqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y

46、));</p><p><b>　　}</b></p><p>　　float Nearest(Point* points, int n){ /*求最小距離*/</p><p>　　float temp1,temp2,temp3,temp,nearest;</p><p>　　float left,right

47、,d; /*當(dāng)n小于4時(shí)，T(n)=O(1)；*/</p><p><b>　　int i,j;</b></p><p>　　if(n==1) return 999999999; /*一個(gè)點(diǎn)情形,返回值模擬無窮*/</p><p>　　if(n==2) return dist(points[0], points[1

48、]); /*兩個(gè)點(diǎn)情形*/</p><p>　　if(n==3){ /*三個(gè)點(diǎn)情形*/</p><p>　　temp1=dist(points[0], points[1]);</p><p>　　temp2=dist(points[0], points[2]);</p><p>　　te

49、mp3=dist(points[1], points[2]);</p><p>　　return temp3<((temp1<temp2)?temp1:temp2)?temp3:((temp1<temp2)?temp1:temp2);</p><p><b>　　}</b></p><p>　　/*多于3點(diǎn)的情形，用分治法

50、*/</p><p>　　left=Nearest(points,n/2); /*遞歸求解*/</p><p>　　right=Nearest(&points[n/2],n-n/2);</p><p>　　d=left<right?left:right;</p><p>　　/*綜合中間帶求得最小距離*/</p&

51、gt;<p>　　for(j=n/2;j<n&&(fabs(points[j].y-points[i].y)<d);j++){</p><p>　　temp=dist(points[i],points[j]);</p><p>　　nearest=nearest<temp?nearest:temp;</p><p>&

52、lt;b>　　}</b></p><p>　　return nearest;</p><p><b>　　}</b></p><p>　　int compx(const void* a, const void* b) {</p><p>　　/*實(shí)現(xiàn)按x排序*/</p>&l

53、t;p>　　return ((Point*)a)->x-((Point*)b)->x;</p><p><b>　　}</b></p><p>　　int compy(const void* a, const void* b) {</p><p>　　/*實(shí)現(xiàn)按y排序*/</p><p>

54、;　　return ((Point*)a)->y-((Point*)b)->y;</p><p><b>　　}</b></p><p>　　經(jīng)過預(yù)排序處理后的算法所需的計(jì)算時(shí)間T(n)滿足遞歸方程：</p><p>　　顯而易見T(n)=O(nlogn)，預(yù)排序所需的計(jì)算時(shí)間為O(n1ogn)。因此，整個(gè)算法所需的計(jì)算時(shí)間為O(

55、nlogn)。在漸近的意義下，此算法已是最優(yōu)的了。</p><p><b>　　6 設(shè)計(jì)小結(jié)</b></p><p>　　這次實(shí)驗(yàn)共做了一個(gè)星期，實(shí)際算下來也就三天左右，時(shí)間很緊湊，忙忙碌碌，到最后終于完成了，在這里可以畫上一個(gè)圓滿的句號(hào)。</p><p>　　在這過程中，我明白了很多東西：1、鞏固和加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所

56、學(xué)知識(shí)的能力。2、培養(yǎng)了我選用參考書，查閱手冊(cè)及文獻(xiàn)資料的能力。培養(yǎng)獨(dú)立思考，深入研究，分析問題、解決問題的能力。3、通過實(shí)際編譯系統(tǒng)的分析設(shè)計(jì)、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計(jì)方法。4、通過課程設(shè)計(jì)，培養(yǎng)了我嚴(yán)肅認(rèn)真的工作作風(fēng)，逐步建立正確的生產(chǎn)觀念、經(jīng)濟(jì)觀念和全局觀念。</p><p>　　根據(jù)我在實(shí)習(xí)中遇到得問題，我將在以后的學(xué)習(xí)過程中注意以下幾點(diǎn)：   1、認(rèn)真上好專業(yè)實(shí)驗(yàn)課

57、，多在實(shí)踐中鍛煉自己。2、寫程序的過程中要考慮周到，嚴(yán)密。3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。4、認(rèn)真的學(xué)習(xí)課本知識(shí)，掌握課本中的知識(shí)點(diǎn)，并在此基礎(chǔ)上學(xué)會(huì)靈活運(yùn)用。5、在課余時(shí)間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯(cuò)誤，以便能節(jié)省調(diào)試程序的時(shí)間。</p><p>　　總之，通過這次課程設(shè)計(jì)，我受益匪淺。知道無論做什么事情，都要對(duì)認(rèn)真，既然是該你做的事，肯定是你應(yīng)該有這個(gè)能力，即使能力不夠，