動態配置記憶空間

Q : 輸入兩個正整數，以遞迴方式計算最大公因數並輸出

上一篇 "換個方式看公因數" 的程式仍然有個問題，主程式 main() 以一個靜態陣列 int data[1000] 來存放使用者輸入的數字，若使用者輸入了超過 1000 個數字，程式就沒辦法處理。又或使用者只輸入 3 個數字，那麼 997 個多餘的空間就浪費了。要改善這個問題，就要使用動態空間配置。

char bool int long float double 都是 C++ 的基本資料型態，以他們宣告出來的變數即佔有對應的記憶空間，用來在程式中存放資料。int data[1000] 以靜態的方式宣告了名為 data 的陣列變數，共有 1000 個存放 int 資料的空間，靜態資料空間伴隨程式而存在，除非程式結束，否則空間不會釋放。

若改用指標的方式宣告，就能做到動態空間配置，例如

int* data;
.
.
data = new int[20];
.
.
delete [] data;

上面程式先宣告了一個名為 data 的 int 指標變數(尚未產生資料空間)，直到中間以 new 指令才動態配置了 20 個 int 記憶空間，最後使用完畢以 delete 指令釋放記憶空間。而在程式中，以陣列的方式即可存取 data 的元素，例如 data[18]=100;

用上述的方法改寫上一篇的主程式 main() ，就能實現動態配置記憶空間，以避免輸入資料過多或空間浪費的問題，程式修改如下

#include <iostream>

int common_divisor(int a, int b) //遞迴函式1
{
   if(a%b==0) //如果a/b餘0，b就是公因數
      return b;
   else if(a>b)
      return common_divisor(a-b,b); //a值較大，把a減掉b繼續測試
   else
      return common_divisor(b,a); //b值較大，交換位置重新測試
}

int common_divisor(int d[], int n) //遞迴函式2
{
   if(n==1)
     return d[0];
   if(n==2)
     return common_divisor(d[0],d[1]);
   if(n>2)
     return common_divisor(common_divisor(d,n/2),
                                     common_divisor(&d[n/2],n-n/2) );

   return 0; //n小於1才會發生
}

int main()
{
   int d;
   int datacount=0;
   int *dataptr=0; //用來存放所有輸入資料的記憶空間指標

   std::cout << "請輸入n個正整數，輸入完成請按 Ctrl-Z" << std::endl;
   while ( std::cin >> d )
   {
      if (dataptr!=0) //已經存在舊資料
      {
         int *newptr= new int[datacount+1]; //動態配置比原來多一個單位的記憶空間
         for(int i=0; i<datacount; i++)
                newptr[i]=dataptr[i]; //把舊資料複製到新的位置

         delete [] dataptr; //釋放舊的記憶空間
         dataptr=newptr; //資料指標指向新的位置
      } else
         dataptr=new int[datacount+1]; //沒有舊資料，直接動態配置記憶空間

        dataptr[datacount]=d; //把輸入的資料放進最後一個位置
        datacount++; //資料計數變數+1
    }
    std::cout << "最大公因數=" << common_divisor(dataptr, datacount);
    return 0;
}

基本資料型態本身不具備"主動"的方法，完全靠外在的程式碼去處理必要的程序，雖然看起來很傻沒有技巧，但總算仍可以完成任務~