數據結構課程設計-----最小套圈設計

1、<p><b>　　數據結構課程設計</b></p><p>　　最小套圈設計(課題名稱)</p><p><b>　　目 錄</b></p><p><b>　　1 設計題目1</b></p><p><b>　　2 設計分析1</b>

2、;</p><p><b>　　3 設計實現3</b></p><p><b>　　4.1測試目的5</b></p><p>　　4.2 測試輸入5</p><p>　　4.3 正確輸出6</p><p>　　4.4 實際輸出6</p><p&g

3、t;<b>　　5 分析與探討7</b></p><p>　　5.1 測試結果分析7</p><p>　　5.2 探討與改進7</p><p><b>　　6 設計小結9</b></p><p>　　1 設計題目 </p><p>　　套圈游戲是游樂場中

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

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

6、含一個玩具的x和y的坐標。當N為0時，表示全部測試結束，不要對該數據做任何處理。</p><p><b>　　輸出要求：</b></p><p>　　對每一組測試，在一行里輸出符合要求的套圈半徑，精確到小數點后兩位。</p><p><b>　　2 設計分析</b></p><p>　　首先必須認識

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

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

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

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

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

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

13、b>　　3 設計實現</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <math.h></p><p>　　#define MAX_POINTS 100000 /*

14、坐標點數的最大值 */</p><p>　　#define MAX_TEST 100 /*最大測試次數*/</p><p>　　typedef struct { /*定義坐標點*/</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) { /*求兩個坐標點之間的距離*/</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、當n小于4時，T(n)=O(1)；*/</p><p><b>　　int i,j;</b></p><p>　　if(n==1) return 999999999; /*一個點情形,返回值模擬無窮*/</p><p>　　if(n==2) return dist(points[0], points[1]); /*

18、兩個點情形*/</p><p>　　if(n==3){ /*三個點情形*/</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點的情形，用分治法*/</

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的點按其y坐標排好序，則對P1中所有點p，</p><p>　　//對排好序的點列作一次掃描，就可以找出所有最接近點對的候選者，</p><p>　　//對P1中每一點最多只要檢查P2中排好序的相繼6個點。</p><p>　　nearest=d;</p><p>　　for(i=0;i<n/2

22、;i++)</p><p>　　/* 通過掃描子集一中每個點檢查子集二中與其距離在d之內的</p><p>　　所有點(最多6個)以完成合并*/</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>　　/*實現按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>　　/*實現按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]; /*記錄結果*/</p><p>　　for(i=0;i<MAX_TEST;i++) resu

27、lt[i]=-1;</p><p>　　printf("請輸入數據：\n");</p><p>　　while(1){ /*進行多次測試*/</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"); /*容錯處理*/</p><p>　　goto loop;</p><p><b>　　}&

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

30、坐標排序好。*/</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) /*輸出測試結果*/</p><p>　　printf("%.2f\n",result[i++]);</p><p><b>　　}</b

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

34、<p><b>　　4.2 測試輸入</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 實際輸出 </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 測試結果分析 </p><p>　?。?）輸出的結果與實際預算的結果相一致。驗證成功。</p><p>　　（2）輸出的結果與實際預算的結果相一致。驗證成功。</p><p>　?。?）輸出的結果與實際預算的結果相一致。驗證成功。<

39、;/p><p><b>　　5.2 探討與改進</b></p><p>　　一種最簡單的方法就是將二重循環(huán)把任何可能的點對進行遍歷，計算全部（N-1）N/2的距離，計算中求出最小值。（其核心代碼設計如下）：</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>　　此代碼的計算時間T(n)=2T(n/2)+O(n2)。它的解為T(n)=O(n2)，即與合并步驟的耗時同階，顯示不出比用窮舉的方法好。從解遞歸方程的套用公式法，我們看到問題出在合并步驟耗時太多。這樣做算法效率與其他算法相比效率太低，需要O(n2)的計算時間。</p><p>　　因此我們需要改進新的方法，需要高效率設計新的算法，因此不由的想到了計算時間下界為Ω(

45、nlogn)。這個下界引導我們去找問題的一個θ(nlogn)算法。因此選擇“分而治之”圓環(huán)套圈的方法。（其核心代碼設計如下）</p><p>　　float dist(Point a, Point b) { /*求兩個坐標點之間的距離*/</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; /*當n小于4時，T(n)=O(1)；*/</p><p><b>　　int i,j;</b></p><p>　　if(n==1) return 999999999; /*一個點情形,返回值模擬無窮*/</p><p>　　if(n==2) return dist(points[0], points[1

48、]); /*兩個點情形*/</p><p>　　if(n==3){ /*三個點情形*/</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點的情形，用分治法

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>　　/*實現按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>　　/*實現按y排序*/</p><p>

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

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

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

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