[愛迪生系列文] 01 - 陣列妙用好處多

edisonx

[註 1] 系列文不會講基本語法與概念，這部份筆者做太多了，有點膩。
[註 2] 系列文都屬原創，基於知識無價原則，您可以自由使用、修改，唯基於網路品德，請註明出處，避免誤觸智財權。
[註 3] 系列文參考書籍可能很多，唯筆者一些經驗與整理後之發表。

版上實在有點冷清，發個文好了。

[1] 純粹存資料

一般陣列的用法最常見的用法是拿來存資料而已。像是存 10 個整數時，int num[10] ;
又像是存學生3科成績，有10個學生時，int score[10][3] ;
這些沒什麼特別的，每本書都會提，就不講了。

[2] 做統計用 - 出現次數

做統計最常用到的是「出現次數」，一個有名的排序法是「計數排序法」，假設有一個陣列 int Arr[1000]，要對 Arr 由小而大排序。假設我們已經知道 Arr 的內容是從 0~100 。

這時候我們可以開一個陣列做統計用，叫 Count[100-0+1]，然後分別紀錄每個數字出現的次數。再用 for 回圈填回 Arr 即可。

int

i, j;
int  arr[1000], num[101] = {0};

for(i=0;i<1000; ++i) // 產生資料     
     arr[ i ] = rand() % 101;
for(i=0;i<1000;++i) // 做統計     
     ++num[ arr[ i ] ];  
for(j=i=0;  i<=100; ++i)  //

依出現次數填回去
     while(num[ i ]) arr[j++] = i, --num[ i ];

上面只是 demo, 實際上的 Counting Sort 會考慮 Stable 問題，所以不會寫成這樣，有興趣可以再找相關資料。

[3] 做統計 - 累計

一個簡單的問題是，要求某個日期，是該年的第幾天，假設 1/1 是第1天。

一開始就給它開個陣列，代表每個月份的累計天數，然後加上判斷潤年、月份是否大於 2 的判斷式，很容易求出。


int is_leap_year(int year)
{
     return

(year%400==0)|| ( (year%4==0)&& (year%100!=0)) ;
}

const int column_days[] = {
     0, 0, 31, 59, 90, 120, 151,
     181, 212, 243, 273, 304, 334};

int find_nday(int year, int

month, int day)
{
     return column_days[month] +day +
         (month> 2 && is_leap_year(year));
}


再來另一個問題，假設 int Arr[10]，給定 Low, Up  ( Low < Up < 10)，怎麼求得 Arr[Low:Up] 的總合？

一種方式是直接用 for( i =low; i<=up ; ++i) s+=arr;  但這動作每次都要做的話其實有更好的方法。我們直接先用一個統計的概念去做

#include<stdio.h>

int main()

{

     int Arr[10]= {1,2,3,4,5,6,7,8,9,10};

     int ColArr[10]={0};

     int i, low,up;

     //

做累計

     for(ColArr[0]=Arr[0],i=1; i<10; ++i)

         ColArr[ i ] = ColArr[i-1] + Arr;

     

     // 輸出測試

     while(scanf("%d%d",&low,&up)==2) {

         if

(low<up&& low>=0 && up < 10)

              if(low) printf("%dn", ColArr[up]-ColArr[low-1]);

              else printf("%dn", ColArr[up]);

         else puts("error");

     }

     return 0;

}

還有另一個問題，是算每個字母出現次數，這個就不再附了。

[4] 做統計 - 累計 (II)

另一種累計是不均勻亂數的問題。假設有 4 個數字，{0,1,2,3}，出現機率想調成 {0.5, 0.25, 0.15, 0.1}。作法很多種，這裡只講一種。

一開始直接先做累計機率統計，{0.0, 0.5, 0.75, 0.90, 1.0}，做完後再隨機產生一個 [0,1] 亂數，判斷是落在哪個區間，範例如下

#include <stdio.h>
#include<stdlib.h>

#include<time.h>

int main()
{
     int i, interval;
     int Num[4] = {0,1,2,3};
     double Prob[4]= {0.5, 0.25, 0.15, 0.1}; // 各數字機率
     double ColProb[4] = {0};// 累計機率

     int Appear[4] = {0};    //出現次數統計
     double rnd;

     
     for(ColProb[0]= Prob[0],i=1; i<4; ++i) // 做機率累計
         ColProb[ i ] = ColProb[i-1] +Prob;

     srand( (unsigned)time(NULL));

     

// 做 1000 次測試統計
     for(i=0;i<1000; ++i){
         rnd = (double)rand()/ RAND_MAX ;
         for(interval=0;interval<4 && ColProb[interval]<rnd; ++interval);
         ++Appear[interval]; //做累計,Num[interval] 就是取得的數字

     }
     // 輸出結果
     for(i=0;i<4; ++i)
         printf("Num%d : %3d, %.2lf %%n", Num[ i ], Appear[ i ], Appear[ i ]/10.0);   
     return0;
}

執行結果參考

Num 0 : 489, 48.90 %
Num 1 : 272, 27.20 %
Num 2 : 151, 15.10 %
Num 3 :  88, 8.80 %

[5] 做轉換

一問題：怎麼將一個 unsigned int (假設 32bits) 以二進位方式，固定 32 長度輸出。這作法一樣有很多解答，最常見的方法大概如下

#include <stdio.h>
int main()
{
     unsigned int x=0x23U;
     unsigned int mask;

     for(mask=0x80000000U;mask; mask>>=1)
         putchar('0'+ ((mask & x)!=0U));
     return 0;
}

另一種方式是直接建表做轉換，建表就是要用到  array，只是一次建小部份的表，不然會太大，如下。

#include <stdio.h>
int main()
{
     unsigned int x=0x23U;
     unsigned int cnt=8;
     const char* table[] = {
         "0000"

,"0001","0010","0011",
         "0100","0101","0110","0111",
         "1000",

"1001","1010","1011",
         "1100","1101","1110","1111"};

     for(cnt=0;cnt<8; ++cnt) {
         printf("%s",table[ (x & 0xf0000000)>>28]);

         x<<=4;
     }
     return 0;
}

寫法差了點，優化空間較大。再來一個題目，假設一個字串，英文字母要由大寫轉小寫的話，可以這麼做

#include <stdio.h>
int main()
{
     int i;
     char src[200], dst[200];
     while(gets(src)){
         

for(i=0;src; ++i)
              if(src>='A' && src<='Z')dst[ i ] = src[ i ]+('a'-'A');
              else dst[ i ] = src[ i ];
         dst[ i ] = 0;
         puts(dst);
     }
     return 0;
}

每次 for loop 要做 if-else ，用 array 去掉 condition，直接做 mapping。

#include <stdio.h>
int main()
{
     int i;
     char src[200], dst[200];
     char mapping[256];

     for(i=0;i<256; ++i) mapping[ i ] = i;
     for(i=

'A'; i<='Z'; ++i) mapping[ i ] = i+('a'-'A');

     while(gets(src)){
         for(i=0;src; ++i)
              dst[ i ] = mapping[ src[ i ] ];
         dst[ i ] = 0;
         puts(dst);
     }
     return 0;
}

好吧，我承認這例子舉的沒很好，正常而言這種用法會拿來配合「部份取代」，或是「移位」。比如說所有英文字母向後移3位，

'A'  --> 'D' , 'B'--> 'E', 'C' ---> 'F', ....., 'X'--->'A', 'Y'---->'B', 'Z'---->'C'，做超簡易的加密。

其他的用法還有很多，這裡就先打住，陣列最好的練習是「高斯消去法求連立方程式解」，這裡就留著不附 code，以後有機會的話再討論。

chiayinwang

感謝您的詳細解說
並讓版上熱絡!

cchh543-md

陣列和sql在程式或資料庫處理，
都有提綱契領，畫龍點睛之妙

smzdtest

陣列在使用時要特別小心，別使用超過一開始定義的空間，例如你定義了10個空間卻使用了15個空間，這種錯誤會造成程式的執行異常。

z50g_18_12_20@G

其實在計算數值出現的次數, 可以使用list, 每個ID都是唯一, 所以在賦予值的時候
如果沒有該ID則會產生一個新的, 不然會覆蓋掉原始的值
這個可以用在array大小不固定的時候

gygy23

建議先了解資料結構，再使用陣列，否則會很亂