指標與動態記憶體配置介紹
本來是先寫了這一段文章，
但是陰錯陽差地弄丟了，
所以又寫了另外的兩段文章：
-
指標介紹
-
動態記憶體配置與釋放
我也沒力氣整理了，
應該是大同小異，
但是有些觀念和範例說明的確還是互有千秋，
您就自己看看囉!
話說
C 語言介紹到這裡其實指標大家早已經在使用了，
例如:
int x[20];
scanf("%d",&x[10]);
x 雖說是一個陣列，
但是在 C 語言中其實是一個指標常數，
在使用 scnaf() 函式時要求在變數前加一個 &
符號其實是在取得變數 x[10] 的位址 (指標)。
記憶體位址
C 語言中指標 (或稱指標常數) 就是是記憶體位址，
指標變數就是存放記憶體位址的變數，
記憶體位址是什麼東東呢?
我們知道電腦裡 CPU 是在做算術、
邏輯運算、和控制流程的工作，
記憶體是在暫時儲存資料的，
記憶體的基本單元是二進位的位元 (bit)，
但是一個二進位位元只能表達 0 和 1 兩種狀態，
實在太少了，
因此我們通常將八個位元組合起來一起使用，
稱為位元組 (byte)，
一般你在買 PC 的時候會說記憶體有多少 Mega 的單位就是位元組，
現在 32MB 的記憶體大約只要 NT1000 元，
1995 年的時候差不多是 1MB 1000元，
(科技在進步喔!
請加緊腳步跟上來)。
在 CPU裡 頭替每一個記憶體位元組指定一個序號，
以便用來存取該位元組內存放的資料，
序號就好像我們家的門牌號碼讓郵差可以分辨哪些信放進哪一個信箱一樣，
所以我們稱這個序號為記憶體位址。
指標變數
這種變數內存放的資料是記憶體的位址，
CPU 可以隨時存取其資料，
例如：
這三個敘述個別定義了一個指標變數，
變數的名稱是 addr, fPtr 及 dPtrScore。
一般來說記憶體的位址是個很單純的二進位數字，
其位元長度則隨作業系統而定，
一般 32 位元的作業系統下位址是 32 位元，
16 位元的作業系統下位址可以是 16 位元或是 32 位元，
位址有多少個位元代表 CP U能夠存取到多少個記憶體，
16 位元的話就是 2 的 16 次方 (65536) 個位元組，
才 64K byte，
現在隨便一台電腦都有 1G byte 的記憶體，
CPU 如果只能存取 64K byte 的話，
未免也太遜了。
Visual C++ 編譯器產生的執行檔使用 32 位元的記憶體位址。
當然你可以用 sizeof(addr) 或是 sizeof(int *)
來看到究竟這種變數使用多少個位元的記憶體來存放位址。
CPU 對於指標變數能夠做什麼事?
CPU 對於一般的變數能夠做兩件事：
存及取 (寫入及讀出)，
例如:
int x;
x = 1; // 寫入變數 x
printf("%d",x); // 讀出變數 x
對於指標變數而言當然也可以做這樣子兩個動作，
但是 CPU 要寫入的資料必須是某一個記憶體的位址，
例如：
int x;
int *xptr;
xptr = &x; // 將變數 x 的位址寫入變數 xptr
printf("%d",xptr); // 讀出變數 xptr 內存放的資料
取址運算子 &
C 程式中怎樣取得一個記憶體的位址呢?
最基本的方式就是利用取址運算子作用在一個變數上，
例如：
&x 及 &y 分別可以取得變數 x
所使用的二個位元組記憶體中第一個位元組的位址及變數 y
所使用的四個位元組記憶體中第一個位元組的位址。
注意：
-
程式在還沒有執行起來的時候 (還沒載入的時候)，
根本不知道其中的變數會放在記憶體內的什麼地方，
每一次執行的時候放的位置也不一定一樣。
-
比較簡單的個人電腦作業系統 (例如 DOS) 使用 memory-mapped IO
時，
很多輸入輸出界面的資料區都有固定的位址，
例如：通訊界面 RS232，
視訊 VGA 界面…，
在 C 程式中可以直使用這些位址，
例如：
int FAR *x;
x= 0XA8000000;
取值運算子 * (dereference operator, indirection operator)
看了以上那麼多關於指標的基本介紹，
究竟指標、位址、指標變數內存放的這些資料有什麼用啊?
一個程式要處理的資料大體上不外乎字元、整數、浮點數，
根本不需要處理記憶體的位址呀?
C 語言提供處理記憶體位址的能力是希望程式設計者寫出來的程式能夠更有彈性 (flexible)。
到底是什麼彈性呢?
讓我們舉幾個例子來說：
-
有時候我們會說 "請到系辦找助教幫你處理"，
這句話很有彈性，
我沒有指明是哪一個助教，
你到系辦找任何一個助教應該都可以。
-
你不認得路而隨便找一個人問路時，
他可能告訴你 "請到那邊路口再找一個人問，
他可以清楚地指給你看"，
這句話也很有彈性，
沒有指明是什麼樣子的人，
應該是任何人在路口的都可以。
-
你去打工送貨時也許會得到這樣的指示：
"請你每天在你的工作分派信箱中拿送貨單，
然後按單上地址送貨"，
這句話也很有彈性，
沒有跟你說任何一個地址，
而告訴你說去指定的地方拿送貨單，
這個地址可能在基隆市，
可能在八堵、汐止、台北、甚至高雄，
如果你的指示是 "請每天將貨物送基隆市北寧路二號"
那麼這個指示就很沒有彈性，
你再聰明乖巧幹練遇見這樣子的指示也做不出什麼偉大的事來。
-
在電腦中 CPU 也是這個樣子的，
如果你的程式有下面這樣子的敘述的話：
double x;
double product;
...
product = 1;
while (x>0)
{
product *= x;
x = x-1;
}
你知道 CPU 在執行的時候會做計算
f(x) = x * (x-1) * (x-2) *… 的動作，
你也知道對任何一個數字而言，
要求出 f(x) 之值只要把該數字存入變數 x
中 CPU 做完上面敘述後可以在變數 product 中找到 f(x) 的值，
這樣子的一段程式彈性夠不夠呢?
假如我希望利用同樣的一段函式把變數 dIncome
內的值做一個 f(dIncome) 的計算的話，
我們勢必要拷貝 dIncome 變數內的資料到變數 x 內存放，
也就是說變數 x 會變成一個大雜燴，
什麼有的沒有的都要存放在此變數內才能進行某些特定的運算，
如此變數的名稱無法表達其內資料的意義了。
下面這一段程式運用 C 程式的 * 運算子讓前面這一段程式增加一些彈性：
double dIncome;
double *dPtrData;
…
product = 1;
dPtrData = &dIncome; // 將 dIncome 變數之位址存入 dPtrData 指標變數中
while (*dPtrData>0)
{
product *= *dPtrData;
*dPtrData = *dPtrData-1;
}
CPU 在執行 *dPtrData 時牽涉到兩個變數的讀取，
首先讀取 dPtrData 變數的資料，
這是一個記憶體的位址，
而後 CPU 再根據這個位址去讀取存放在該位址的資料
(實際上也就是 dIncome 變數內的資料)，
由於 dPtrData 變數宣告為 double 型態之指標，
CPU 會把其內的位址所指示的記憶體位置當作一個 double 型態的變數
(8 個位元組) 來存取資料。
現在如果希望該段程式能夠處理另一個 double 型態變數 dScale 內的資料的話，
只需要在前面加入dPtrData = &dScale 即可。
這樣子好像前面工讀的例子一樣地有彈性，
老闆只要更改你工作分派信箱內的資料，
你就可以做很多不同的工作了。
C 程式可以分很多的模組來製作，
個別模組由不同的人來製作，
剛才這一段程式除了可以處理自己模組內的變數，
也可以處理別的模組裡的變數，
只要該變數的型態是 double 就可以了，
程式在撰寫的時候，
很明顯地我們對想要處理的資料做了一種一般化的處理，
我們並不是假設要處理的資料存放在某一個特定的變數裡，
而是假想說要處理的資料位於任何一個型態為 double 的變數內。
這個情況就好像你擬定一個推銷的策略時，
不會是只針對某一個特定的人，
而會做最起碼的一般化，
至少針對某一個特殊族群是有用的。
-
上面這樣子的程式應用特別適合用在函式的參數表示上，
一個可以重覆使用的函式通常是將相同的處理程序應用在不同的資料上，
例如 scanf() 標準輸入函式，
這個函式需要由鍵盤界面讀入使用者鍵入的字元，
然後轉換為正確的格式置於指定的變數內，
這些指定的變數是隨不同的程式而不同的，
製作 scnaf() 函式的人在製作此函式時壓根兒就不曉得這些變數叫什麼名字，
放在記憶體的什麼地方，
因此他當然不能把使用者鍵入的資料存到一個 "特定" 的變數內，
那該怎麼辦呢?
設計 scanf() 函式的人利用類似下面程式的方式來寫入指定的變數
int scanf(const char *fmt, int *iPtr)
{
…
*iPtr = some value from keyboard
}
在撰寫程式時只知道 iPtr 這個指標變數，
而不知道真正要放到哪一個變數內。
注意：
當然由上面這個例子中大家也可以看到萬一呼叫 scanf()
函式的人沒有把正確的指標傳進來的話，
scanf() 也就一定沒有辦法把資料傳回去了，
如下例：
大家應該知道是怎麼錯的吧!
-
再舉一個函式指標應用的例子：
在電腦中單一資料本身對於 CPU 並沒有特殊的意義，
資料的意義是相對的，
需要透過比對才能顯示它的意義，
就好像 1 美元本身沒有太大意義，
可是如果有告訴你 7 美元可以看一場電影，
5 美元可以買一磅牛肉，
1 美元可以換 33 元台幣，
那就不一樣了，
數字 10 之所以為 10 是因為和 '1' '0'
這兩個形狀比對成功所以我們才認得它是 10。
資料在電腦中需要藉由排序來建立資料間的組織，
以加快比對與搜尋的速度，
C 語言中提供一個 qsort() 的函式讓你對大量的資料運用快速排序法 (quick sort)
來排出它們的順序，
但是在製作 qsort() 函式時會遇見一個嚴重的問題，
就是
如果是整數的話可以將大的數字放前面，
也可以將小的數字放前面，
如果是字元的話可以用 ASCII 內碼的排列順序來排序，
如果是中文的話呢?
如果每一筆資料有部分是數字，
有部分是英文字串，
還有部分是中文，
那該以哪些欄位來排順序呢?
嚴格來說只有設計及使用該資料格式的人才知道如何排序比較有用，
那麼撰寫 qsort() 函式的人該怎麼辦呢?
利用函式指標變數
撰寫 qsort() 函式的人藉由函式指標，
間接地呼叫一個他不知道究竟做了什麼事的函式來比較資料的大小順序，
他只要知道這個函式需要傳入兩個資料位址，
該函式在比較資料完畢之後如果第一個資料比第二個資料大的話會傳回正數，
等於的話會傳回 0，
小於的話會傳回負數就可以了，
在 qsort() 函式內當需要比對兩筆資料時會以類似下面的程式碼來處理：
qsort(……, int (*pfnCompare)(void *, void *))
{
int iResult;
…
if ((iResult=*pfnCompare(&data1,&data2))>0)
…
else if (iResult == 0)
…
else
…
}
厲害吧!
寫 qsort()
函式的人只要訂下這個比較大小函式的規格後就可以利用函式指標變數
pfnCompare 放心地寫他自己的 qsort() 了。
如果你要使用 qsort() 函式將一個整數陣列
int a[100]; 內的資料由大到小排列的話，
你需要寫一個比較兩個整數的函式，
如下：
int compareInt(const void* number1, const void* number2)
{
if (*(int*)number1 > *(int*)number2)
return 1;
else if (*(int*)number1 == *(int*)number2)
return 0;
else
return -1;
}
此函式必須依照 qsort() 函式的要求宣告為
int xxx(const void *, const void *);
的型態，
為什麼兩個引數是宣告為 void 型態的指標呢?
為什麼不宣告為 int * 或是 double * 呢?
這個原因容易，
因為寫 qsort() 函式的人根本不知道 qsort()
函式所要排序的是什麼樣子的資料，
只得宣告為 void * 型態。
在 compareInt() 函式內因為我們確知傳入的指標所指到的資料是整數型態，
因此我們在指標變數 number1 及 number2 之前加上 (int *) 的型態轉換運算子，
((int *) number1) 還是一個指標而且其位址值沒有任何改變，
但是編譯器會把這樣子的指標視為指向整數變數的指標，
再加上一個取內容運算子 * 後，
*((int *)number1) 就可以取到第一個整數變數內的整數資料了。
定義此函式之後，
我們就可以以下列程式呼叫 qsort() 函式來排序了
qsort(a,100,sizeof(int),compareInt)
抽象地存取資料或程式碼的方式
由上節的討論可以得知，
C 語言中指標最主要的目的就是提供程式設計者一種間接存取資料或程式碼的抽象方式，
使得程式碼的彈性大增。
動態的記憶體配置
在很多高階語言
(BASIC, FORTRAN, COBOL…)
中程式語言系統刻意地不讓程式設計者感覺到記憶體的使用狀況，
程式設計者在使用變數時或是在呼叫函式時事實上都有使用一些記憶體，
但是程式語言希望設計程式的人專注於資料的掌握與處理，
不要分心去管低階記憶體的使用，
在這種情形下，
程式設計者需要替使用程式的人設想所要處理資料量的多寡，
事先準備好所需要使用的變數，
例如：
一個處理申請入學學生資料的程式，
在程式設計時必須決定要處理多少學生，
以下面的程式碼設計足夠的變數來存放所有學生資料：
#define NUMBER_OF_STUDENTS 50
char cName [NUMBER_OF_STUDENTS][10]; // 姓名
char cId [NUMBER_OF_STUDENTS][10]; // 身份証字號
char cAddress[NUMBER_OF_STUDENTS][50]; // 住址
char cTelNo [NUMBER_OF_STUDENTS][10]; // 電話號碼
int iScore[NUMBER_OF_STUDENTS; // 測試成績
萬一學生人數超過 50 人的話，
就必須要修改程式才能夠處理，
這樣子的程式彈性太小，
可是如果要突破這個限制的話，
光光有陣列變數是不夠的，
陣列變數必須在設計程式的時候就決定元素的個數，
必須要有能夠在程式執行的時候決定使用多少記憶體的機制，
這個機制就是動態的記憶體配置，
在程式執行的時候向作業系統多要求一塊記憶體來存放資料，
這多要求的記憶體位於哪裡完全由作業系統決定，
程式在設計的時候根不知道，
那麼如何來使用這些記憶體存放資料呢? 這
個答案就是指標變數了，
和前面幾節描描述的一致，
指標變數藉由兩次記憶體的存取，
就是有這個能耐來處理一般化未知變數內的資料：
如何宣告
char (*cName)[10];
char (*cID)[10];
char (*cAddress)[50];
char(*cTelNo)[10];
int *iScore;
以上我們定義了五個指標變數，
分別準備用來存放
char[10], char[10], char[50], char[10], 及 int
型態變數的位址。
如何配置
那麼如何在程式執行時動態地取得適當大小的記憶體呢?
如下面的程式：
#include <stdlib.h>
#include <stdio.h>
int numberOfStudents;
printf("Please enter the number of students:");
scanf("%d",&numberOfStudents);
cName = (char(*)[10]) malloc(numberOfStudents*sizeof(char[10]));
if (cName == NULL)
printf("Memory allocation error!\n"), exit(1);
…
iScore = (int *) malloc (numberOfStudent*sizeof(int));
if (iScore == 0)
printf("Memory allocation error!\n"), exit(1);
如果系統在使用者執行的時候有足夠多的資源的話，
malloc() 函式會傳回一個 (void *) 型態且不為 0 的指標，
若為 0 則代表配置失敗，
可能是系統目前執行的程式太多，
也可能是使用者輸入的人數太多，
這個指標變數型態為 void *，
和我們宣告的指標變數型態不一樣，
直接設定的話編譯器會給我們一個型態不合的警告訊息，
因此我們加上一個指標型態的轉換運算子 (char (*)[10])，
這個運算子實際上不會去改變存入的位址，
只是為了讓編譯器確定程式設計者知道要存入值的型態和變數的型態是一致的。
注意：
char *cName[10] 和 char (*cName)[10] 是不一樣的，
如果你看一下運算子的優先順序表，
你就會知道陣列的 [] 運算子的優先順序要比指標的 * 運算元要高，
前者和 char* (cName[10]) 是等效的，
那麼前者宣告的是什麼樣子的 cName 變數呢?
是
10-elements ARRAY OF POINTER to char
也就是一個十個元素的陣列，
每一個元素存放的是指向字元變數的指標，
後者則是
POINTER to a 10-element ARRAY of char
也就是一個指標變數，
其內容可以是一個 10 個字元元素陣列第一個元素的起始的位址。
如何使用
最後一個問題是配置完畢後如何使用?
如果你按照前面的宣告方式，
那麼使用起來就簡單了，
例如：
將學生的身份字號及成績清除
for (i=0; i<numberOfStudents; i++)
{
iScore[i] = 0;
for (j=0; j<10; j++)
cId[i][j] = ' ';
}
夠簡單吧!
跟陣列的使用方法一模一樣。
當然也可以不用陣列的用法而用指標的取內容運算子 * 來做：
for (i=0; i<numberOfStudents; i++)
{
*(iScore+i) = 0;
for (j=0; j<10; j++)
*(*(cId + i)+j) = ' ';
}
這和使用陣列 [] 的存取是完全等效的，
編譯器其實把前者翻譯成為後者來處理，
但是很明顯地使用陣列 [] 來存取清楚得多，
後者我們還必須瞭解指標變數的運算特性。
如何釋放配置的記憶體
透過 malloc() 函式取得的記憶體，
使用完畢後一定要在程式內以 free() 函式釋放掉，
例如：
free(iScore):
free(cId);
free(cName);
free(cAddress);
free(cTelNo);
由上面的討論，
大家應該可以瞭解動態地記憶體配置可以使程式的彈性大大提高，
這也是 C 語言中為什麼要使用指標變數的一個很大的原因。
指標 (位址) 的 +/- 運算
C 語言中的 +/- 運算共分為四種：
(同理++和--亦分為此四種)
-
int 型態的 + - 法
-
long 型態的 + - 法
-
double 型態的 + - 法
-
指標型態的 + - 法
指標變數的加減法和一般數值變數的加減法完全不同，
例如：
int *x;
int y[10];
x= &(y[0]); // x設定為變數 y[0] 的位址
假設 sizeof(int) 為 4， 假設 y[0] 的位址為 0xA000， 那麼變數 x 的內容就是 0xA000， 下列運算式運算後
變數 x 的內容是 0xA001 呢還是 0xA004? 答案是後者!!
這個 + 號顯然和整數之加號不一樣，
再看看下面：
double y[10];
double *x=y;
x = x + 1; // (或是 x++)
假設 y[0] 的位址是 0xA000，
指標變數 x 初始化之後的內容當然也是 0xA000，
x=x+1 之後變數 x 的內容則是 0xA008，
驚訝嗎?
其實 C 編譯器一發現 + 號兩側其中一個運算元是指標變數時
(只能有一個是指摽變數)，
立刻採用指標的加法來運算，
在上面兩個例子中雖然加完後變數 x 內的位址資料不同，
但是還真湊巧，
個別都是變數 y[1] 的記憶體位址 (&y[1])，
這樣子不知道你是不是已經猜到，
所謂指標的加減法其實是將指標由目前所指向的記憶體位址移到連續排列的下一個或是前一個同樣型態的變數上，
以其數值來說運算規則如下：
x=x+1 (或是 x++)
若 x 為一指標變數，則 x 之值為原來之值加上 sizeof(*x)
x=x-1 (或是 x--)
則 x 之值為原來之值減上 sizeof(*x)
若是 x 及 y 為相同型態的指標變數，
則 x-y 之數值為
((int)x-(int)y)/sizeof(*x)
若 x,y 為不同型態的指標變數則 x-y 未定義，
x 與 y 同為指標變數時，x+y 亦無定義。
指標與陣列
在 C 語言中指標與陣列在存取上是完全等效的，
陣列的存取 x[3] 相當於 *(x+3)，
反之亦同，
y[3][i] 相當於 *(*(y+3)+i)，
反之亦同，
一般說來以陣列的語法存取資料內容較為直觀，
比較容易了解，
再看看下面幾個等效的寫法：
int x[20];
*(x+3)
*(3+x)
x[3]
3[x]
或是
int y[5][6];
y[3][i]
*(y[3]+i)
*(i+y[3])
*(*(y+3)+i)
i[3[y]]
i[y[3]]
i[*(3+y)]
…
嚴格來說， 這麼多寫法中只有一個或兩個是我們設計程式時該用的， 其它都是給你參考參考，了解一下背後的概念，好玩而已， 製作程式時要選用意義最明顯、最直接的寫法。
注意：
指標變數與陣列變數的宣告則有極大的差異，
特別是陣列宣告通常有替儲存資料的變數配置記憶體。
指標與 C 語言中函式的參數傳遞
C 語言中因為有指標的設計，
因此在函式傳遞參數時一律使用傳值的方法，
若是遇見函式內只需要某一參數的數值時當然就沒有問題，
只要將變數的內容拷貝到函數的參數變數內即可，
若是遇見函式需要藉由參數傳某一數值回呼叫函式，
或是不希望浪費時間拷貝變數內資料的話，
只要將變數的位址藉由傳值的機制傳入函式，
函式內部即可利用此位址直接存取呼叫端函式內的變數。
一般程式語言中為什麼需要有指標這種設計
-
動態配置記憶體
-
製作資料結構 (維持資料間的關係)
-
有彈性地間接存取程式碼及資料
-
變數可以不受定義區塊的使用限制，
生命期不見得與函式相同，
而可以由程式設計者自行在函式間傳遞。
以上四點使得 PASCAL 或是 C 語言中都有指標的設計，
JAVA 語言中亦有類似的 reference(參考)之設計。
指標不一定要用位址來製作，
但是 C/C++ 語言中為了效率的考量，
直接以位址做為指標，
程式設計者用得好的話可使效率大大提昇，
用得不好的話，
指標是 C 程式設計者的夢魘，
除了程式中有許多不易控制的 Bug 之外，
程式的可讀性也大大降低，
C/C++ 語言中以位址做為指標，
還有額外的功能，
就是很方便做 memory-mapped I/O 的設計，
同時不同函式可以共享大的資料區段而不需拷貝整段資料。
以位址做為指標的壞處 (容易犯的錯誤)
-
wild pointer：
由於某一個指標的錯誤內容可能導致另外一記憶體區段內資料的錯誤，
如果該區段亦包括指標變數，
那麼會引發完全無法控制的連鎖反應，
程式的除錯變得異常困難。
-
memory leakage：
未釋放的動態配置記憶體，
必須記錄在變數內，
萬一該變數不慎被覆寫，
就永遠無法再使用該段記憶體了。
此時指標就好像一把鑰匙，
萬一掉了就回不了家了。
-
dangling reference：
此種現象也是指標的內容不正確，
導致的效果和 wild pointer 一樣，
產生的原因則比較明確，
-
在函式結束後還以指標存取堆疊上的區域變數，
-
以指標 (或是複製的指標) 存取已經用 free() 函式釋放了的記憶體區段。
藉由指標來製作資料結構
C 語言中指標結合陣列的宣告相當隱晦，容易錯誤
