陣列應用題

一、基本資料結構 ─ 陣列

在許多典型的比賽題目中，題目會要求先輸入一串背景資料，然後再一行一行輸入測試資料，並印出結果。這樣的題目，我們需要用到資料結構來儲存這一串的背景資料，常用的資料結構有陣列(Array)、堆疊(Stack)、佇列(Queue)、鏈結串列(Linked List)等，其中最簡單的就是陣列。

在使用陣列上，我們先會評估資料的最大筆數以及資料的型態(字串、整數或浮點數)，然後以類似以下的寫法宣告之(以外部變數的方式宣告)：

#define MAX 100

int X[MAX];

int n=0;

上面我們多加了一個整數變數 n 來記錄目前已經記錄了幾筆資料。接下來，我們看到輸入幾個整數後，陣列 X 以及整數 n 的變化：

首先我們加入一個整數 10：

N=0

N=0

N=1

上面的過程中，我們先把 10 放進陣列 X 的第 0 個元素中，接下來再把 N 加 1。這個過程可以寫成：

X[0]=10;

n++;

接下來我們再加入一個整數 20：

N=1

N=1

N=2

上面的過程中，可以寫成：

X[1]=20;

n++;

看了這兩段程式，我們發現， X[編號] 中間的元素編號，剛好就是還沒加 1 之前的 n 的值，所以我們可以把加進一個元素的程式改寫成：

X[n]=數值;

n++;

至於其他不是整數的例子，做法也是類似的，請各位同學自己修改。

二、#476 ─ Points in Figures: Rectangles

題目：按這裡。

說明：輸入一連串(最多 10 個)矩形的左上及右下座標，然後輸入數個點的座標，印出該點落在那幾個矩形裡面。

我們使用陣列來記錄這最多 10 個矩形的座標，利用前一段的方法，我們宣告成下面的型式：

#define MAX 10

float X1[MAX], Y1[MAX], X2[MAX], Y2[MAX];

int n=0;

接下來可以用：

X1[n]=座標1的X;

Y1[n]=座標1的Y;

X2[n]=座標2的X;

Y2[n]=座標2的Y;

n++;

的方式來增多一個矩形座標的記錄。

這一題分成兩個步驟，先輸入一串矩形座標，再逐一輸入要測試的點的座標，所以我們用兩個迴圈分別完成之。輸入矩形座標的部分，由於要整行輸入，我們先用 gets() 函數讀取一整行，然後用 s[0] 的方式檢查第一個字元，之後用 sscanf(s+1,...) 再把字串 s 的第二個以後的部分取出我們要的部分。整個程式如下：

#include <stdio.h>

#define MAX 10

float X1[MAX], Y1[MAX], X2[MAX], Y2[MAX];

int n=0;

int main()

{

 char s[80];

 float x, y;

 int i=1, j, k;

 while(1) {

   gets(s);

   if(s[0]=='*') break;

   sscanf(s+1, "%f %f %f %f", &X1[n], &Y1[n], &X2[n], &Y2[n]);

   n++;

 }

 while(1) {

   scanf("%f %f", &x, &y);

   if( (x>=9999.9) && (y>=9999.9) ) break;

   for(j=0, k=0; j<n; j++)

     if( (x>X1[j]) && (x<X2[j]) && (y<Y1[j]) && (y>Y2[j]) ) {

       printf("Point %d is contained in figure %d\n", i, j+1);

       k=1;

     }

   if(k==0) printf("Point %d is not contained in any figure\n", i);

   i++;

 }

 return 0;

}

三、#477 ─ Points in Figures: Rectangles and Circles

題目：按這裡。

說明：輸入一連串(最多 10 個)矩形座標與圓形的圓心及半徑，然後輸入數個點的座標，印出該點落在那幾個矩形或圓形裡面。

這一題是上一題的延申，而且這一題的程式拿到上一題一樣可以使用。這一題就由各位同學自行解決。(如果真的想不出來，再參考老師的程式)