http://pweb.netcom.com/~tjensen/ptr/pointers.htm
其他參考:
- http://c.learncodethehardway.org/book/
- http://cad-lab.github.io/cadlab_data/files/1993_prog_in_c.pdf
- The_C_Book_1991.pdf
前言
本文件旨在向 C 程式語言的初學者介紹指標. 過去幾年, 無論是在 FidoNet 與 UseNet 有關 C 的會議場合, 特別注意到有許多 C 程式語言的初學者, 似乎對於指標的基本用法, 感到有些困難. 因此特別利用較多的範例, 希望以淺顯的說明來解釋指標的用法.
這份文件的第一版本, 如同此一版本, 是被放在公共領域. 當時是由 Bob Stout 將資料放在 PTR-HELP.TXT 的文件檔中, 並納入 SNIPPETS 的收集中加以發行. 之後, 又在原始資料中增添了許多內容並且修正了一些錯誤.
致謝
要感謝許多不為人知的使用者, 將許多問題公佈在 FidoNet 的 C Echo 論壇中, 或是 UseNet comp.lang.c 新聞群組中, 或是在其他網路上的幾個會議區,這些要感謝的人士可能無法一一列出. 其中特別要感謝 Bob Stout 肯將這份資料的第一版本放入他所收集的 SNIPPETS 檔案中.
關於作者:
Teb Jensen 是一位退休的電子工程師, 主要專注於電磁錄音領域中的硬體設計與管理職務. 程式則是自 1968 年以來閒暇時的興趣, 當時正學著如何以打卡的方式讓程式送給電腦主機執行. (那時的主機擁有 64 K 的磁心記憶體)
使用本資料:
這份資料以公共領域授權釋出. 任何人可以採用任何形式, 複製或散佈這份資料. 唯一的要求, 則是若這份資料被用於課程教學, 希望能夠完整呈現, 亦即, 包含所有章節, 包括前言與簡介.
並且任課教師能夠利用下方的電子郵箱通知我一聲. 之所以如此要求, 主要是希望這份資料能夠對其他人有用, 況且我並不要求金錢回報. 只是希望能夠透過使用這份資料的用戶回饋, 多少確認一下這個目標能夠達成.
此外, 並非一定要是課程教學者可以寫信給我. 感謝任何覺得此份資料有用或提供建設性批評的任何人, 都能告訴我一聲, 我將會透過電子郵件回答相關問題.
Ted Jensen tjensen@netcom.com P.O. Box 324 1-415-365-8452 Redwood City, CA 94064 Dec. 1995
簡介
若您想要專精於利用 C 程式語言編寫程式碼, 就必須徹底了解如何使用指標. 然而, C 指標對初學者而言, 經常是一項障礙, 尤其對於從 Fortran, Pascal 或 Basic 程式語言轉進的學習者.
這份資料旨在幫助初學者了解指標. 為了能讓這份資料發揮最大功能, 使用者最好能夠實際執行文章中所列出的各個程式. 因此所有的程式碼都採 ANSI 標準, 以便讓任何符合 ANSI 標準的編譯器都能執行這些程式碼. 內文與程式碼之間, 也特別加以區分開來, 以便使用者可以直接利用複製的方式, 取的各段落的程式碼, 套用到其他系統中進行編譯. 如此才能確實了解這裡所提供的資料.
第一章: 何謂指標?
C 語言初學者必須面對的難題之一, 就是指標的用法.
這份教材的目的, 就是針對初學者簡介指標及其應用.
其實初學者會對指標產生疑惑, 大多源自於在學習 C 語言時, 對於變數的概念經常一知半解.
因此這裡就由 C 變數的一般用法說起.
程式中的變數都必須加以命名, 以便存放數值.
而編譯器與連結器在處理變數時, 就會挪出電腦記憶體中的特定區域, 以存放變數的值
這些特定區域的大小, 取決於變數允許存放值的範圍.
例如, 在 32 位元電腦, 一個整數變數的存放範圍, 需要為 4 位元. 而在舊的 16 位元電腦, 整數存放需要 2 位元.
C 程式中的整數變數存放範圍大小, 在各種機器上不一定相同.
並且 C 程式中的整數變數也不只一種, 在許多 C 程式教科數中,可以發現有整數, 長整數, 短整數等. 這裡則假設使用 32 位元系統, 因此整數需要 4 位元的存放空間.
可以採用下列程式碼,在您所使用的系統中, 查探特定整數型別所需要的記憶體空間:
#include <stdio.h>
int main()
{
printf("size of a short is %d\n", sizeof(short));
printf("size of a int is %d\n", sizeof(int));
printf("size of a long is %d\n", sizeof(long));
}
當我們宣告一個變數時, 亦即告知編譯器兩件事, 變數名稱與變數型別. 例如, 可以透過
1 | int k; |
宣告名稱為 k 的整數型別變數. 當編譯器看到 "int" 的敘述值, 就會在電腦的記憶體中, 保留 4 位元的空間, 以便存放整數變數 k 的值.
此外, 電腦也會設置一個符號表, 註明符號 k 與其在記憶體中用來存放 4 位元資料的相對位址.
因此, 若在變數宣告後, 使用
1 | k = 2; |
2 這個數值, 就會在程式執行時, 被放在保留給 k 變數的記憶體位址中.
在 C 語言中, 整數 k 變數, 可視為一個物件. 其中有兩個值與物件 k 有關, 也就是存放的數值與存放的位址. 有些參考書中將者兩個數值稱為"右值"與"左值". (2 為右值, 而變數位址為左值)
在某些語言中, 左值只能放在指定"等號"的左邊, 而右值則只能放在右邊. 位置放錯, 例如: 2 = k, 就會出錯.
其實, C 語言中有關左值得定義, 根據 K&R II (page 197): [1], 則有些變動.
"物件為儲存區域的名稱, 而左值則為指向該物件的表示式."
這裡先採引用的定義加以說明, 後續將會進一步針對指標加以說明.
接著, 假如程式碼為:
int j, k;
1 2 3 | k = 2; j = 7; <-- line 1 k = j; <-- line 2 |
編譯器會將第一行 (line 1) 的 j 解讀為變數 j 的位址 (也就是左值), 並且將值 7 放到該位址. 在第二行 (line 2), 則會將 j 視為右值 (因為在"指定"運算子的右方), 指的則是存放在 j 記憶體中的 7 這個數值. 因此第二行執行過後, 存放在 j 的 7 這個數值, 就會被放到 k 變數所對應的"左值" (記憶體位址) 中.
在這些範例中, 採用的都是將右值從一個儲存位址, 經由複製將 4 位元的資料複製到另外一個儲存位址. 假如使用 2 位元整數, 則會複製 2 位元資料.
這裡, 就會需要一種變數, 用來存放左值 (記憶體位址). 存放此一變數的值, 隨系統而異, 舊的桌上電腦總共只有 64K 的記憶體, 每存放一個整數位址會佔去 2 位元.
更多位元數的電腦 (例如 64 位元電腦), 則需要更多的位元位址來存放一個整數資料.
實際需要的記憶體大小並不重要, 需要的則是一種方法, 通知編譯器在哪一位址存放哪些資料.
這樣的變數稱為"指標變數" (隨後將說明得更清楚). 在 C 語言中定義指標變數時, 必須在變數名稱前方, 加上一個 * 符號. 而這些指標變數的型別, 隨著要存放在指標位址中的資料型別而定, 例如, 假如宣告:
int *ptr;
ptr 為變數名稱 (與之前的整數變數名稱 k 相同). 而 "*" 符號則告知編譯器, 此一宣告為指標變數, 亦即保留出足夠的記憶體存放位址. 最前方的 int 則表示, 希望此一指標變數用來存放整數. 而此一指標稱為"指向整數". 需要特別注意的是, 當使用 int k; 時並沒有給 k 初始值, 只有在任何符合 ANSI 規範的編譯器中, 會將宣告在函式外的變數通通以 0 初始.
同樣地, ptr 也沒有初始值, 亦即, 還沒有在上述宣告之後, 在保留的位址空間上, 放入任何值. 這裡若宣告是在任何函式之外, 就會被賦予初值, 並且保證不會指向任何 C 物件或函式. 以這種方式初始的指標, 被稱為 "空"指標 (null pointer).
而空指標並不一定會被放入 "0" 值, 因為這取決於特定系統中的設定. 為了在不同系統中的不同編譯器彼此相容, 就會利用巨集 (macro) 來表示空指標. 此巨集以 NULL 命名. 因此, 若以 NULL 設定指標值, 則可以確定在不同機器上, 這些指標變數一定是空指標.
與整數是否為 0 的判斷式 if(k ==0) 相類似, 可以利用 if(ptr == NULL) 判斷是否 ptr 為空指標.
但是, 回到新變數 ptr 的應用, 假設要將整數變數 k 所對應的位址, 存入 ptr, 就必須使用"位址運算子", 寫成:
1 | ptr = &k; |
"位址運算子"的作用是用來取 k 的左值 (位址), 即使這時 k 位於等號右邊, 上述程式會將 k 的值複製到指標 ptr 的儲存空間中. 這時, ptr 稱為"指向" k.
接著再討論另外一個運算子.
也就是所謂的"取值運算子" (dereferencing operator), 就是一個 * 符號. 使用方法如下:
1 | *ptr = 7; |
這行程式會將 7 這個數值,複製到 ptr 變數所指向的位址. 也就是說, 假如 ptr 指向 k (ptr 為 k 存放資料的記憶體位址), 這行程式就會將 k 的值設為 7. 換言之, * 運算子可用來改變 ptr 所指向的值, 而不是指標本身的值. (註:指標本身為位址, 也就是所謂的左變數)
因此, 可以利用:
printf("%d\n",*ptr);
將目前存放在 ptr 所指向位址的整數值, 給印到螢幕.
要釐清上述說明, 可以執行下列程式, 並仔細探討程式碼與其輸出.
------------ Program 1.1 ---------------------------------
/* Program 1.1 from PTRTUT10.TXT 6/10/97 */
#include <stdio.h>
int j, k;
int *ptr;
int main(void)
{
j = 1;
k = 2;
ptr = &k;
printf("\n");
printf("j has the value %d and is stored at %p\n", j, (void *)&j);
printf("k has the value %d and is stored at %p\n", k, (void *)&k);
printf("ptr has the value %p and is stored at %p\n", ptr, (void *)&ptr);
printf("The value of the integer pointed to by ptr is %d\n", *ptr);
return 0;
}
請注意: 我們還沒有談到 C 程式中的 (void *) 表示式. 這裡可以先納入您的測試程式碼中, 隨後將會加以說明.
結論:
1 2 3 4 5 | 1. 變數宣告必須指定名稱與型別. (例如: int k;) 2. 指標變數宣告也是指定名稱與型別. (例如: int *ptr;), 其中的 * 告知編譯器, 該名稱為 ptr 的變數, 為一個指標變數, 而其型別為該指標指向的資料型別 (這裡為整數). 3. 一旦變數已經宣告, 可以透過變數前方的位址運算子, 取得其位址, 例如 &k. 4. 可以由指標中"取值", 亦即, 以 * 指定到指標所參照的值, 例如: *ptr. 5. 變數的左值為被用來存放在記憶體中的位址值, 而變數的右值則式被存放在該位址的數值. |
參考資料:
"The C Programming Language" 2nd Edition B. Kernighan and D. Ritchie Prentice Hall ISBN 0-13-110362-8
第二章: 指標型別與陣列
接著讓我們來看看, 為何需要指定指標指向變數的型別, 例如: int *ptr; 原因之一是, 宣告之後, 可以透過指向, 寫成:
*ptr = 2;
編譯器就會知道要配置多少記憶體給 ptr 變數, 假如 ptr 宣告為指向整數, 電腦就會複製 4 位元的資料, 其它的浮點與雙浮點變數也是相同. 定義指向變數型別的另外一個用途就是編譯器可以解譯程式碼. 例如, 記憶區中存放 10 個連續的整數資料時, 需要 40 位元的記憶體.
假如整數指標 ptr 為這些整數中的第一個變數, 若該整數位於記憶體位址 100. 當程式寫為:
ptr + 1;
因為編譯器知道 ptr 為一個指標變數 (亦即, 其值為一組位址)並且指向某一整數 (目前位址為 100, 即是該整數所在位址), 當 ptr 加上 4 而不是 1 之後, 該指標將會指向下一個整數, 也就是記憶體 104.
相同的概念下, 若 ptr 指向短整數, 則應該加上 2 而不是 1. 對於浮點, 雙浮點或使用者自訂的資料型別 - 結構, 也是類似.
儘管這並非我們常見的"加法", 但是在 C 語言中, 可以透過指標算數進行"加法"運算, 隨後將會再予以說明.
同理, 因為 ++ptr 與 ptr++ 與 ptr + 1 等同 (儘管 ptr 增量的時機點並不一樣).
讓指標以 ++ 增量運算子進行增量, 無論是先加或後加, 由 sizeof(type) 中所得到的位址增量, 其型別均為該物件指向變數的型別 (整數為 4 位元).
由於這 10 個整數位於記憶體中連續區塊上, 指標可以被用於整數資料陣列的處理.
例如:
1 | int my_array[] = {1,23,17,4,-5,100};
|
陣列中帶有 6 個整數. 可以透過 my_array 的索引代表這些整數. 亦即利用 my_array[0] 到 my_array[5] 加以表示, 也可以透過指標加以表示成:
1 2 | int *ptr; ptr = &my_array[0]; /* 將指標指向陣列中的第一個整數*/ |
接著就可以使用陣列索引或取值運算, 列出陣列.
下列程式可以用來展示此一應用:
----------- Program 2.1 -----------------------------------
/* Program 2.1 from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
int my_array[] = {1,23,17,4,-5,100};
int *ptr;
int main(void)
{
int i;
ptr = &my_array[0]; /* point our pointer to the first
element of the array */
printf("\n\n");
for (i = 0; i < 6; i++)
{
printf("my_array[%d] = %d ",i,my_array[i]); /*<-- A */
printf("ptr + %d = %d\n",i, *(ptr + i)); /*<-- B */
}
return 0;
}
編譯執行上列程式就可以仔細觀察 A 行與 B 行程式分別採用兩種方法列出陣列中的同一內容.
也可以清楚看到 B 行程式如何應用"取值"運算, 亦即, 首先在指標增量後, 在新的指標中取值. 將 B 行程式改為
1 | printf("ptr + %d = %d\n",i, *ptr++);
|
之後再執行, 接著改為:
1 | printf("ptr + %d = %d\n",i, *(++ptr));
|
再執行, 執行之前先判定結果, 並與實際執行結果進行比較.
在 C 語言, 可以利用 var_name 來替代 &var_name[0], 因此在程式碼中寫成:
1 | ptr = &my_array[0]; |
或:
1 | ptr = my_array; |
都會得到相同的結果.
因此許多參考書都寫道: 陣列的變數名稱就是指標. 但是比較好的想法則是: 陣列的變數名稱就是陣列中第一元件的位址. 許多初學者 (包含作者本人), 都會將其視為指標.
但是, 可以寫成:
ptr = my_array;
但是卻不能寫成:
my_array = ptr;
原因就是 ptr 為變數, 但是 my_array 卻是常數, 也就是說, my_array 第一元件的位址, 一旦在 my_array[] 完成宣告後, 就不可以改變.
先前曾討論的左值, 中引用 K&R-2 中所言:
"物件為儲存區域的名稱, 而左值則為指向該物件的表示式."
這就衍生出一個有趣的議題. 因為 my_array 為儲存區域的代表名稱, 為何 my_array 在上面的指定敘述程式中, 卻不能用在左值區域?
為了說明這點, 可以將 my_array 視為"不可改變的左值".
上列範例可以將:
1 | ptr = &my_array[0]; |
改為:
1 | ptr = my_array; |
確認兩者會得到相同的結果.
至於 ptr 與 my_array 之間的差異, 有人將陣列變數名稱視為"常數指標". 為了充分了解所謂"常數"的真諦, 重回變數定義時的說明.
當變數宣告時, 用來存值的記憶體就必須加以配置. 這時變數可以透過兩個層面來看.
用在指定運算左邊時, 編譯器會視其為記憶位址, 用來指向右側所設定的值.
若被用在運算右邊時, 變數名稱會被解讀為存在該記憶體中的值.
有了以上的概念, 關注簡單的常數運算:
1 2 | int i, k; i = 2; |
其中 i 為存放 2 常數的變數, 並非直接在資料記憶區塊中指定, 而是直接存入程式記憶區塊.
當 k = i; 程式碼就會到 &i 位址中抓取要複製到 k 的值, 而 i = 2; 只是將 2 放入程式碼, 而沒有取值的運作. 也就是說, k 與 i 都是物件, 但是 2 則非物件.
同理, 由於 my_array 為常數 (為位址值), 一旦編譯器設好用來存值得區域後, my_array[0] 存值得記憶體位址就已經確定, 因此可以使用:
1 | ptr = my_array; |
將此在程式區段中的常數位址設給 ptr, 其中並沒有牽涉到資料區段的取值操作.
這時就可進一步說明第一章程式 1.1. 中 (void *) 的應用. 由於指標可被用來指向各種資料型別. 除了可以指向整數, 也可以指向字元, 之後還會介紹指向結構與指向指標的指標變數.
由於在不同系統中的指標儲值大小會有差別, 並且指標的記憶體空間會隨著指向物件資料型別差異而有所不同.
因此若將長整數指給短整數資料型別變數時, 就會發生問題, 也可以將某一型別的指標變數指定給其他不同型別指標變數時, 產生問題.
為了克服此一問題, C 語言提供 void 這個空的指標資料型別.
假如將某一指標設定為:
void *vptr;
空指標可以視為通用指標. 由於 C 語言不允許整數型別指標與字元型別指標之間的資料交換或比較. 這時就可以透過空指標作為中介, 在特殊情況下在指標型別間進行資料轉換.
在第一章的 1.1 程式中, 就是使用空指標將整數指標轉成能與 %p 資料相符的格式.
下列各章, 也將透過此一概念進行資料轉換.
這裡列出許多技術資料給初學者, 首次閱讀時或許不很容易理解. 因此需要前後執行幾次程式, 看看結果, 並且仔細查驗這兩個例子中的程式碼與產出結果, 才會有所突破.
接下來, 將討論指標, 字元陣列與字串間的關係.
第三章: 指標與字串
字串的研究不僅對進一步理解指標與陣列的關聯有些幫助,也能用來彰顯某些標準 C 字串函數的使用. 最後也可以理解指標如何將資料傳給函式.
就 C 而言, 字串為字元所組成的陣列, 其他的語言則未必如此. 無論是 BASIC, Pascal 或是 Fortran 與其他幾種程式語言, 字串自有其資料類別. C 則不然, 字串之於 C 被表為以 0 位元 (寫為'\0').
這裡要以幾行程式碼作為開端, 來加以說明, 如下:
1 2 3 4 5 6 | char my_string[40]; my_string[0] = 'T'; my_string[1] = 'e'; my_string[2] = 'd': my_string[3] = '\0'; |
或許沒有人會用這種方法來建立字串, 以空字元作為結尾. 根據 C 語言的定義, 字串為一組以空字元結尾的字元陣列. 注意這裡的所謂空字元與 "NULL" 不同. 空字元表為以跳脫序 '\0' 表示的"零"字元. 亦即佔了記憶體中的一個位元, 而 NULL 則為用來起始空指標的巨組程式.
NULL 在 C 編譯器中, 以 #define 在標頭檔案中宣告, 而 nul 則完全無法以 #define 宣告.
由於用上述程式來宣告字串非常累人, 因此 C 允許以多種方法來完成一項工作.
首先, 可以寫成
1 | char my_string[40] = {'T', 'e', 'd', '\0',};
|
但是光打字就有些不方便, 因此也可以寫成:
1 | char my_string[40] = "Ted"; |
若使用的是雙引號, 而不是先前的單引號, 空字元 ('\0') 會自動被加在字串最後面.
上面的例子, 結果都相同. 編譯器會保留連續的 40 位元區塊來存放 Ted\0 這四個字元.
接著看看下列程式:
------------------program 3.1-------------------------------------
/* Program 3.1 from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
char strA[80] = "A string to be used for demonstration purposes";
char strB[80];
int main(void)
{
char *pA; /* a pointer to type character */
char *pB; /* another pointer to type character */
puts(strA); /* show string A */
pA = strA; /* point pA at string A */
puts(pA); /* show what pA is pointing to */
pB = strB; /* point pB at string B */
putchar('\n'); /* move down one line on the screen */
while(*pA != '\0') /* line A (see text) */
{
*pB++ = *pA++; /* line B (see text) */
}
*pB = '\0'; /* line C (see text) */
puts(strB); /* show strB on screen */
return 0;
}
--------- end program 3.1 -------------------------------------
上述程式定義了兩個字元陣列, 各有 80 字元. 由於屬於全域變數, 一開始各字元都填入 '\0'. 然後, strA 前 42 個字元被放入所引用的字串內容.
接著的程式碼, 宣告兩個字元指標並將其字串顯示在螢幕. 將 pA 指標指向 strA, 也就是附註 strA[0] 的位址給變數 pA. 然後利用 puts() 函數顯示 pA 所指向的內容 puts() 函式的宣告為:
1 | int puts(const char *s); |
現在先不用管 const, 傳給 puts() 函數的變數為指標. 其實是指標所對應的值. 而指標的值為其所指向的位址. 因此寫成 puts(strA), 表示輸入變數為 strA[0] 的位址.
同理, 當程式寫 puts(pA); 也是以相同的位址當作輸入, 因為已經透過
pA = strA;
將位址傳給 pA
因此程式執行到 while() 指令中的 A 行時, A 行內容為:
當 pA 所指向的字元並非 nul 字元時 (也就是'\0'), 執行其內容:
而 B 行程式則表示: 將 pA 指向的字元複製給 pB 所指向的字元, 接著增量 pA 後可以指向下一字元, 而 pB 則會指向下一個記憶體空間.
完成最後一個字元複製後, pA 會指向空字元, 也會終止迴圈的執行.
其中空字元並沒有複製, 但由於 C 中的字串一定要以空字元結尾, 所以在 C 行程式中再補上空字元.
執行此一程式時, 當使用者透過除錯器看著 strA, strB, pA 與 pB 一步步執行, 將非常具有教育意義.
It is even more educational if instead of simply defining strB[] as has been done above, initialize it also with something like:
更有意思的是, 若不將 strB[] 按上述方法定義時, 而是將其起始值設為:
1 | strB[80] = |
"12345678901234567890123456789012345678901234567890"
讓其數字個數大於 strA 的長度, 然後一步步看著這些變數設定數值. 大家一定得親自做做看.
接著再回到 puts() 的原型, 運用 "const" 作為某一參數的宣告飾詞時, 主要在告訴使用者, 該函式無法改變其由 s 所指向的字串值, 意即, 程式會將該字串視為常數.
誠然, 上述程式展示了複製字串的一種簡單方式. 一旦確實了解上述程式的用法, 接著將自行編寫可以取代標準 strcpy() 的 C 標準函式, 程式如下:
char *my_strcpy(char dest[], char source[])
{
int i = 0;
while (source[i] != '\0')
{
dest[i] = source[i];
i++;
}
dest[i] = '\0';
return dest;
}
在此一程式中, 同樣運用了指標的傳值.
承上述內容, 若將函式寫成可以接受兩個字元指標變數輸入, 也就是位址, 就可以將上述程式改寫為:
1 2 3 4 5 | int main(void)
{
my_strcpy(strB, strA);
puts(strB);
}
|
雖然與標準 C 的用法有些不同, 採用了下列原型定義:
1 | char *my_strcpy(char *destination, const char *source); |
之所以使用 "const" 飾詞, 主要在確定該函式無法變更指向來源指標的數值. 此點可從上述函式的修改得到印證, 其原型變數, 如 "const" 飾詞所示. 接著在函式中, 增加一行試圖更改該變數由來源指標所指向的值, 意即:
1 | *source = 'X'; |
試著將該字串的第一個字元, 變更為 X. 前面的 const 飾詞就會讓這一行程式產生錯誤, 執行完後就會更加清楚有關 const 變數的使用.
接著, 繼續探討上述程式的內涵, 第一步, 將 ptr++ 解讀為由 ptr 指標傳回值後的增量. 主要與運算子的次序有關. 假如寫成 (ptr)++, 表示增量的部分, 並非指標, 而是該指標所指向值的增量. 也就是說, 在上述程式中, 若對第一個字元 'T' 增量, 其值就會變成 'U'. 使用者可以自行寫程式來印證此一結果.
由於字串只不過就是字元所組合而成的陣列, 並在最後一個字元補上 '\0'. 上面所進行的是用來複製陣列. 這些字元陣列的運算技巧, 也可以應用到整數陣列或浮點數陣列. 但是在這些應用中, 陣列的尾端, 並不會補上 nul 字元, 而可以放進某特定值的內容, 來表示其為終點. 例如, 可以在複製正整數時, 在尾數放入一個負值的整數來標示終點. 或者, 寫一個函式, 可以複製字串以外的陣列及其陣列位址, 就如同下列原型所示:
1 | void int_copy(int *ptrA, int *ptrB, int nbr); |
其中 nbr 為要進行複製的整數值. 試著寫一個可以用來複製整數陣列的 int_copy() 函式, 看看是否能夠正常運作.
如此, 就可以使用函式來處理大陣列. 例如, 有一帶有 5000 個整數的陣列需要處理, 只要將該陣列的位址輸入該函式 (視情形, 可以加上其他相關變數, 如上述程式中的 nbr 變數), 而不需要輸入陣列本身, 意即, 整個陣列值並沒有在堆疊中複製後進行輸入的動作, 而只送出其位址.
此一過程與輸入某一整數給某一函式不同. 輸入整數時, 必須複製該整數, 也就是取得該整數的值, 然後放入某一堆疊當中. 這時, 該函式的處理並不影響原始的整數值, 而若以陣列及指標進行處理, 可以將變數位址輸入, 直接處理原始變數的值.
第四章: 更多關於字串的用法
好的, 在短短的時間裏, 已經介紹了不少東西! 接著再看一次第三章中有關字串複製的部分, 但是採不同的方法. 以下列函式來看:
1 2 3 4 5 6 7 8 9 10 11 | char *my_strcpy(char dest[], char source[])
{
int i = 0;
while (source[i] != '\0')
{
dest[i] = source[i];
i++;
}
dest[i] = '\0';
return dest;
}
|
之前曾說過, 字串就是字元所組成的陣列. 這裡我們利用陣列表示而非指標表示, 來進行資料的實質複製. 結果會與之前相同, 亦即, 採此一方法的字串複製, 其結果依然正確. 這也衍生出接下來要討論的有趣論點.
由於變數透過值進行傳遞, 可經由前述之字元指標或陣列名稱進行, 其間真正傳遞的則是每一陣列中第一個元素的位址. 亦即, 變數數值的傳遞, 可透過字元指標或陣列名稱來代表此一變數. 也可以說, source[i] 其實與 *(p+i) 的用法一樣.
事實上, 這是正確的, 亦即 a[i] 可以利用 *(a+i) 來替代, 而不會產生任何問題. 換言之, 編譯器針對這兩種情形, 會產生相同的編碼. 因此, 指標算術其實與陣列索引編碼相同. 兩種語法會產生相同結果.
但是這並非說, 指標與陣列是相同的東西, 其實不然. 這裡只是說, 利用陣列來進行特定元素辨識, 可以採用兩種不同的語法, 其一為採用陣列索引, 而另一種方法則是利用指標算術, 會得到相同的結果.
接著, 注意最後的表示式, (a+i) 的部分利用簡單的加號 + 與 C 的語法, 表示式子可以交換, 亦即 (a+i) 與 (i+a) 完全相同. 因此可以將 (i+a) 簡化為 (a+i).
但是 *(i+a) 可能來自 i[a]! 綜合上述, 或許會懷疑若:
1 2 | char a[20]; int i; |
寫成
1 | a[3] = 'x'; |
其實與下列表示式, 其實是一樣的.
1 | 3[a] = 'x'; |
試試看! 設定一個字元陣列, 內存為整數或長整數等. 對其第三或第四元素, 以傳統方式, 給定特殊值, 接著將值印出加以確認. 然後如前述, 將陣列表示式反轉過來, 一個好編譯器將會毫無疑問的給出相同的結果, 僅只出於好奇, 別無其他用意.
程式範例:
#include <stdio.h>
// 每一個 C 程式都必須要有一個小寫的 main()函式
int main()
{
// 陣列與指標的應用
char a[20];
int i;
a[3] = 'x';
printf("%c\n",a[3]);
printf("%c\n",3[a]);
printf("%c\n",*(a+3));
printf("%c\n",*(3+a));
return 0;
}
接著, 來看前面給的函數, 寫成:
1 | dest[i] = source[i]; |
由於已知陣列索引與指標算術會得到相同的結果, 因此也可以寫成:
1 | *(dest + i) = *(source + i); |
但是, 需要對每一個值分別加上 i. 加法, 一般而言, 會比索引增量 (例如採用 ++ 運算符號的 i++) 耗費更多時間. 或許對現在最佳化的編譯器來說, 不一定就是如此, 但是採用指標通常比陣列索引來得快些.
另一個可以加速指標運算的方法, 將:
1 | while (*source != '\0') |
簡化為
1 | while (*source) |
兩種情形都會讓括號中為零 (FALSE).
這裡可實驗看看, 以指標的方法來寫程式. 用來處理字串應該不錯. 可以將下列標準函式改寫成自己的版本:
1 2 3 | strlen(); strcat(); strchr(); |
或者其他在系統中的函式.
接下來的章節, 還會再探討字串及其處理. 接下來先討論一下 structures (結構).
第五章: 指標與結構
也許你已經知道, 可以利用結構的形式來宣告帶有不同資料型別的資料區塊. 例如, 人事檔案可能包含下列結構:
1 2 3 4 5 6 | struct tag {
char lname[20]; /* 姓 */
char fname[20]; /* 名 */
int age; /* 年齡 */
float rate; /* 例如: 每小時 100 元 */
};
|
假如在磁片檔案中有許多這樣的資料, 當我們需要一筆筆讀出, 並且分別列出姓名, 以做成資料表格. 其他資料並不需要印出. 具體做法, 可以利用函式呼叫, 透過指向結構的指標作為輸入, 就可以完成處理. 這裡只利用一個結構進行示範, 並且主要在編寫函式, 而非讀檔. 這裡已經假設您知道如何進行讀檔.
複習一下, 我們可以利用點運算子來擷取結構成員, 正如:
--------------- program 5.1 -----------------
/* Program 5.1 from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <string.h>
struct tag {
char lname[20]; /* last name */
char fname[20]; /* first name */
int age; /* age */
float rate; /* e.g. 12.75 per hour */
};
struct tag my_struct; /* declare the structure my_struct */
int main(void)
{
strcpy(my_struct.lname,"Jensen");
strcpy(my_struct.fname,"Ted");
printf("\n%s ",my_struct.fname);
printf("%s\n",my_struct.lname);
return 0;
}
-------------- end of program 5.1 --------------
或許這裏所使用的結構與一般 C 程式所使用的相比還要小, 為了驗證也可以加入:
1 2 3 4 5 6 7 | date_of_hire; (未顯示資料型別) date_of_last_raise; last_percent_increase; emergency_phone; medical_plan; Social_S_Nbr; 等等..... |
假如員工的數量眾多, 應該會採用函式進行資料處理. 例如, 將結構輸入該函式, 就能利用函式印出員工姓名. 但是在最原始的 C (Kernighan & Ritchie, 第一版), 無法輸入結構, 只能輸入指向結構的指標. 在 ANSI C 中, 已經允許利用結構作為函式輸入. 而這裡為了進行更多有關指標的學習, 並不直接採用結構.
總之, 假如輸入整個結構, 就如同必須在函式呼叫時複製結構內容, 在仍然使用堆疊的系統中, 就等同將整個結構資料送入堆疊中. 針對大型結構時, 可能就會造成問題. 若能只輸入指標, 就可使用最少的堆疊空間.
因此這裡主要在談指標, 因此接著來看如何將指向結構的指標變數輸入函式當中.
以上面的情況為例, 建立一個能夠接受指標變數 (指向結構) 的函式, 其中我們只想要擷取該結構的部分成員. 例如, 只要印出範例結構中的人員姓名.
好, 先前我們已經知道如何宣告指向結構的指標變數 tag. 接著就可以利用 tag 結構, 來宣告指標變數:
1 | struct tag *st_ptr; |
並且可以用來指向範例中的結構:
1 | st_ptr = &my_struct; |
接下來, 可以利用指標的分割參照, 來指定特定成員. 但是應該如何利用指標的分割參照來指向結構? 假如要利用指標來設定人員的年紀, 可以寫成:
1 | (*st_ptr).age = 63;
|
仔細看清楚. 此一設定表示, 若將括號中 st_ptr 所指向的內容換成 my_struct, 就會與my_struct.age 相同.
但是, 這樣經常會被用到的表示式, 就被設定為與下列表示式涵義相同:
1 | st_ptr->age = 63; |
了解了之後, 參考下列程式:
------------ program 5.2 ---------------------
/* Program 5.2 from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <string.h>
struct tag{ /* the structure type */
char lname[20]; /* last name */
char fname[20]; /* first name */
int age; /* age */
float rate; /* e.g. 12.75 per hour */
};
struct tag my_struct; /* define the structure */
void show_name(struct tag *p); /* function prototype */
int main(void)
{
struct tag *st_ptr; /* a pointer to a structure */
st_ptr = &my_struct; /* point the pointer to my_struct */
strcpy(my_struct.lname,"Jensen");
strcpy(my_struct.fname,"Ted");
printf("\n%s ",my_struct.fname);
printf("%s\n",my_struct.lname);
my_struct.age = 63;
show_name(st_ptr); /* pass the pointer */
return 0;
}
void show_name(struct tag *p)
{
printf("\n%s ", p->fname); /* p points to a structure */
printf("%s ", p->lname);
printf("%d\n", p->age);
}
-------------------- end of program 5.2 ----------------
這裡要了解不少東西. 讀者必須實際執行一下上面的程式, 並且利用除錯器一步步觀察 my_struct 與 p 在主函式執行流程中, 才能實際了解函式執行的內容.
第六章: 更多關於字串與字串陣列的用法
接著, 再回到字串的用法. 下面的例子, 都以全域的方式運用, 亦即, 在任何函式之外發生作用, 包括主函式.
先前的章節曾經談過:
char my_string[40] = "Ted";
將會配置足夠存放 40 個位元組陣列的空間來存放該變數的值, 並且在最前面的 4 個位元組中放入所設定的字元 (前面三個位元組放入雙引號中的字元, 而最後則放入 '\0')
而實際上, 也可以將 "Ted" 這個字串寫成:
char my_name[] = "Ted";
編譯器屆時就會計算字元個數, 並且預留最後的 null 字元, 以便能將全部四個字元存入記憶體, 並傳回存放字元的陣列名稱, 這裡採用 my_name.
在某些程式中, 也可以寫成:
char *my_name = "Ted";
這種方式, 與先前兩種方法有何不同? 答案是: 當然不同. 採用陣列來存放四個位元組是將資料放在靜態記憶體區塊, 每一個字元的最後都會放入 null 字元. 但是若採用指標的方式, 也是需要相同的四個位元組, 並加上 N 個位元組來存放 my_name 這個指標變數 (N 取決於系統, 但通常至少 2 位元組, 也可能是 4 個以上)
陣列的表示法中, my_name 是 &myname[0] 的縮寫, 也就是第一個陣列元素的位址. 由於該陣列位址在執行期間是固定的, 因此不會改變 (不是變數). 而若採用指標的方式, my_name 則是變數. 因此採用指標是較好的方式, 當然也取決於隨後要如何應用這個變數.
若再進一步觀察採用不同方式宣告後, 在函數內將如何發生變化, 這與處在任何函式外的全域用法有很大的不同.
void my_function_A(char ptr) { char a[] = "ABCDE" . . } void my_function_B(char ptr)
在 my_function_A 的案例中, 陣列 a[] 的值, 就是存放其中的資料. 陣列可視為以 ABCDE 值進行啟始化. 而在 my_function_B 的案例, cp 指標值才代表所存放的資料. 指標的啟始是指向 FGHIJ 字串. 在兩個函式內, 變數定義都是局部, 因此 ABCDE 字串存在指標變數所對應值的堆疊中, 而 FGHIJ 則可能存在任何地方. 在我的系統中, 是存在資料區段中.
此外, 採陣列變數自動起始, 就如同 my_function_A 中所示, 在舊的 K&R C 中是無法使用的, 只能用在 ANSI C 的環境中. 這點在考量程式的可攜或向後相容時就顯得很重要.
只要討論有關指標與陣列的關係與差異時, 就需要更進一步討論多維度陣列. 例如下列陣列:
1 | char multi[5][10]; |
這代表什麼? 讓我們看看.
1 | char multi[5][10]; |
若將有底線的部分視為陣列的變數名稱. 先前的 char 代表資料型別, 而隨後的 [10] 則代表擁有時個字元的陣列. 但是 multi[5] 本身又是一個具有 5 個成員的陣列, 而每一個都帶有 10 個字元的陣列. 亦即, 總共有 5 個陣列各自帶有 10 個字元的陣列.
假設將這個二維的陣列填入資料, 在記憶體中, 可以表示成為五個各自分離的陣列:
1 2 3 4 5 | multi[0] = {'0','1','2','3','4','5','6','7','8','9'}
multi[1] = {'a','b','c','d','e','f','g','h','i','j'}
multi[2] = {'A','B','C','D','E','F','G','H','I','J'}
multi[3] = {'9','8','7','6','5','4','3','2','1','0'}
multi[4] = {'J','I','H','G','F','E','D','C','B','A'}
|
同時, 個別元素可以再表示為:
1 2 3 | multi[0][3] = '3' multi[1][7] = 'h' multi[4][0] = 'J' |
由於陣列在記憶體中是連續的資料, 因此在真實的記憶區段中, 就成為:
1 2 3 | 0123456789abcdefghijABCDEFGHIJ9876543210JIHGFEDCBA ^ |_____ starting at the address &multi[0][0] |
請注意, 這裡並沒有將 multi[0] 寫成"0123456789". 因為若寫成這樣, 電腦會在最 後面補上字串結束用的 '\0', 因為雙引號中間的資料會被當作字串. 這樣, 每一個變數 就會帶有 11 個字元, 而非該有的 10 個字元.
前面的用意在昭示記憶體如何處理二維陣列. 亦即, 以一個二維字元陣列來存放資料, 而不是存成字串陣列.
接著, 編譯器知道陣列中需要多少行, 因此會用 mylti +1 作為 'a' 在第二列之首, 也就是每一列會加上 10, 結合所指的列數來取得正確的資料.
若處理的數值為整數與相同維數的陣列, 在我使用的機器上, 編譯器會加上 10sizeof(int), 而得到 20. 因此第四列第九行的位址, 表示為指標, 將會是 &multi[3][0] 或 (multi + 3). 若希望取得第四列第二個數值, 就可以在此位址上加上 1, 得到下列結果
1 | *(*(multi + 3) + 1) |
再繼續探究, 可知
1 2 3 | *(*(multi + row) + col) 與 multi[row][col] 可得到相同的結果. |
下列程式採用整數數列而非字元陣列來驗證這個結果:
------------------- program 6.1 ----------------------
#include <stdio.h>
#define ROWS 5
#define COLS 10
int multi[ROWS][COLS];
int main(void)
{
int row, col;
for (row = 0; row < ROWS; row++)
{
for (col = 0; col < COLS; col++)
{
multi[row][col] = row*col;
}
}
for (row = 0; row < ROWS; row++)
{
for (col = 0; col < COLS; col++)
{
printf("\n%d ",multi[row][col]);
printf("%d ",*(*(multi + row) + col));
}
}
return 0;
}
----------------- end of program 6.1 ---------------------
由於在陣列程式版本中進行了兩次交互參照取值, 二維陣列的名稱就如同指向陣列的指標. 至於三維陣列則用來處理陣列中陣列所指向的陣列, 因此也等同是指向陣列中陣列的指標. 但這裡的說明將陣列所佔記憶體區段以陣列來加以表示, 因此所處理的記憶體位址為常數而非變數. 亦即所討論的是固定的位址而非變數指標.
上述的取值函式允許從陣列中, 以無需變更位址數值的方式從陣列中取出任何數值 (例如, 以 multi[0][0] 的位址取 multi 符號所對應的值)
CHAPTER 7: More on Multi-Dimensional Arrays
In the previous chapter we noted that given
1 2 3 4 | #define ROWS 5 #define COLS 10 int multi[ROWS][COLS]; |
we can access individual elements of the array multi using either:
1 | multi[row][col] |
or ((multi + row) + col)
To understand more fully what is going on, let us replace
1 | *(multi + row) |
with X as in:
1 | *(X + col) |
Now, from this we see that X is like a pointer since the expression is de-referenced and we know that col is an integer. Here the arithmetic being used is of a special kind called "pointer arithmetic" is being used. That means that, since we are talking about an integer array, the address pointed to by (i.e. value of) X + col + 1 must be greater than the address X + col by and amount equal to sizeof(int).
Since we know the memory layout for 2 dimensional arrays, we can determine that in the expression multi + row as used above, multi + row + 1 must increase by value an amount equal to that needed to "point to" the next row, which in this case would be an amount equal to COLS * sizeof(int).
That says that if the expression ((multi + row) + col) is to be evaluated correctly at run time, the compiler must generate code which takes into consideration the value of COLS, i.e. the 2nd dimension. Because of the equivalence of the two forms of expression, this is true whether we are using the pointer expression as here or the array expression multi[row][col].
Thus, to evaluate either expression, a total of 5 values must be known:
The address of the first element of the array, which is returned by the expression multi, i.e., the name of the array.
The size of the type of the elements of the array, in this case sizeof(int).
The 2nd dimension of the array The specific index value for the first dimension, row in this case. The specific index value for the second dimension, col in this case. Given all of that, consider the problem of designing a function to manipulate the element values of a previously declared array. For example, one which would set all the elements of the array multi to the value 1.
1 2 3 4 5 6 7 8 9 10 11 | void set_value(int m_array[][COLS])
{
int row, col;
for (row = 0; row < ROWS; row++)
{
for (col = 0; col < COLS; col++)
{
m_array[row][col] = 1;
}
}
}
|
And to call this function we would then use:
1 | set_value(multi); |
Now, within the function we have used the values #defined by ROWS and COLS that set the limits on the for loops. But, these #defines are just constants as far as the compiler is concerned, i.e. there is nothing to connect them to the array size within the function. row and col are local variables, of course. The formal parameter definition permits the compiler to determine the characteristics associated with the pointer value that will be passed at run time.
We really don’t need the first dimension and, as will be seen later, there are occasions where we would prefer not to define it within the parameter definition, out of habit or consistency, I have not used it here. But, the second dimension must be used as has been shown in the expression for the parameter. The reason is that we need this in the evaluation of m_array[row][col] as has been described.
While the parameter defines the data type (int in this case) and the automatic variables for row and column are defined in the for loops, only one value can be passed using a single parameter. In this case, that is the value of multi as noted in the call statement, i.e. the address of the first element, often referred to as a pointer to the array. Thus, the only way we have of informing the compiler of the 2nd dimension is by explicitly including it in the parameter definition.
In fact, in general all dimensions of higher order than one are needed when dealing with multi-dimensional arrays. That is if we are talking about 3 dimensional arrays, the 2nd and 3rd dimension must be specified in the parameter definition.
CHAPTER 8: Pointers to Arrays
Pointers, of course, can be "pointed at" any type of data object, including arrays. While that was evident when we discussed program 3.1, it is important to expand on how we do this when it comes to multi-dimensional arrays. To review, in Chapter 2 we stated that given an array of integers we could point an integer pointer at that array using:
1 2 3 | int *ptr;
ptr = &my_array[0]; /* point our pointer at the first
integer in our array */
|
As we stated there, the type of the pointer variable must match the type of the first element of the array. In addition, we can use a pointer as a formal parameter of a function which is designed to manipulate an array. e.g.
Given:
1 2 | int array[3] = {1, 5, 7};
void a_func(int *p);
|
Some programmers might prefer to write the function prototype as:
void a_func(int p[]);
which would tend to inform others who might use this function that the function is designed to manipulate the elements of an array. Of course, in either case, what actually gets passed is the value of a pointer to the first element of the array, independent of which notation is used in the function prototype or definition. Note that if the array notation is used, there is no need to pass the actual dimension of the array since we are not passing the whole array, only the address to the first element.
We now turn to the problem of the 2 dimensional array. As stated in the last chapter, C interprets a 2 dimensional array as an array of one dimensional arrays. That being the case, the first element of a 2 dimensional array of integers is a one dimensional array of integers. And a pointer to a two dimensional array of integers must be a pointer to that data type. One way of accomplishing this is through the use of the keyword "typedef". typedef assigns a new name to a specified data type. For example:
1 | typedef unsigned char byte; |
causes the name byte to mean type unsigned char. Hence
1 | byte b[10]; would be an array of unsigned characters. |
Note that in the typedef declaration, the word byte has replaced that which would normally be the name of our unsigned char. That is, the rule for using typedef is that the new name for the data type is the name used in the definition of the data type. Thus in:
1 | typedef int Array[10]; |
Array becomes a data type for an array of 10 integers. i.e. Array my_arr; declares my_arr as an array of 10 integers and Array arr2d[5]; makes arr2d an array of 5 arrays of 10 integers each.
Also note that Array p1d; makes p1d a pointer to an array of 10 integers. Because p1d points to the same type as arr2d, assigning the address of the two dimensional array arr2d to p1d, the pointer to a one dimensional array of 10 integers is acceptable. i.e. p1d = &arr2d[0]; or p1d = arr2d; are both correct.
Since the data type we use for our pointer is an array of 10 integers we would expect that incrementing p1d by 1 would change its value by 10sizeof(int), which it does. That is, sizeof(p1d) is 20. You can prove this to yourself by writing and running a simple short program.
Now, while using typedef makes things clearer for the reader and easier on the programmer, it is not really necessary. What we need is a way of declaring a pointer like p1d without the need of the typedef keyword. It turns out that this can be done and that
1 | int (*p1d)[10]; |
is the proper declaration, i.e. p1d here is a pointer to an array of 10 integers just as it was under the declaration using the Array type. Note that this is different from
1 | int *p1d[10]; |
which would make p1d the name of an array of 10 pointers to type int.
CHAPTER 9: Pointers and Dynamic Allocation of Memory
There are times when it is convenient to allocate memory at run time using malloc(), calloc(), or other allocation functions. Using this approach permits postponing the decision on the size of the memory block need to store an array, for example, until run time. Or it permits using a section of memory for the storage of an array of integers at one point in time, and then when that memory is no longer needed it can be freed up for other uses, such as the storage of an array of structures.
When memory is allocated, the allocating function (such as malloc(), calloc(), etc.) returns a pointer. The type of this pointer depends on whether you are using an older K&R compiler or the newer ANSI type compiler. With the older compiler the type of the returned pointer is char, with the ANSI compiler it is void.
If you are using an older compiler, and you want to allocate memory for an array of integers you will have to cast the char pointer returned to an integer pointer. For example, to allocate space for 10 integers we might write:
1 2 3 4 5 | int *iptr;
iptr = (int *)malloc(10 * sizeof(int));
if (iptr == NULL)
{ .. ERROR ROUTINE GOES HERE .. }
|
If you are using an ANSI compliant compiler, malloc() returns a void pointer and since a void pointer can be assigned to a pointer variable of any object type, the (int *) cast shown above is not needed. The array dimension can be determined at run time and is not needed at compile time. That is, the 10 above could be a variable read in from a data file or keyboard, or calculated based on some need, at run time.
Because of the equivalence between array and pointer notation, once iptr has been assigned as above, one can use the array notation. For example, one could write:
1 2 3 | int k; for (k = 0; k < 10; k++) iptr[k] = 2; |
to set the values of all elements to 2.
Even with a reasonably good understanding of pointers and arrays, one place the newcomer to C is likely to stumble at first is in the dynamic allocation of multi-dimensional arrays. In general, we would like to be able to access elements of such arrays using array notation, not pointer notation, wherever possible. Depending on the application we may or may not know both dimensions at compile time. This leads to a variety of ways to go about our task.
As we have seen, when dynamically allocating a one dimensional array its dimension can be determined at run time. Now, when using dynamic allocation of higher order arrays, we never need to know the first dimension at compile time. Whether we need to know the higher dimensions depends on how we go about writing the code. Here I will discuss various methods of dynamically allocating room for 2 dimensional arrays of integers.
First we will consider cases where the 2nd dimension is known at compile time.
METHOD 1:
One way of dealing with the problem is through the use of the typedef keyword. To allocate a 2 dimensional array of integers recall that the following two notations result in the same object code being generated:
1 | multi[row][col] = 1; *(*(multi + row) + col) = 1; |
It is also true that the following two notations generate the same code:
1 | multi[row] *(multi + row) |
Since the one on the right must evaluate to a pointer, the array notation on the left must also evaluate to a pointer. In fact multi[0] will return a pointer to the first integer in the first row, multi[1] a pointer to the first integer of the second row, etc. Actually, multi[n] evaluates to a pointer to that array of integers that make up the n-th row of our 2 dimensional array.
That is, multi can be thought of as an array of arrays and multi[n] as a pointer to the n-th array of this array of arrays. Here the word pointer is being used to represent an address value. While such usage is common in the literature, when reading such statements one must be careful to distinguish between the constant address of an array and a variable pointer which is a data object in itself. Consider now:
--------------- Program 9.1 --------------------------------
/* Program 9.1 from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <stdlib.h>
#define COLS 5
typedef int RowArray[COLS];
RowArray *rptr;
int main(void)
{
int nrows = 10;
int row, col;
rptr = malloc(nrows * COLS * sizeof(int));
for (row = 0; row < nrows; row++)
{
for (col = 0; col < COLS; col++)
{
rptr[row][col] = 17;
}
}
return 0;
}
------------- End of Prog. 9.1 --------------------------------
Here I have assumed an ANSI compiler so a cast on the void pointer returned by malloc() is not required. If you are using an older K&R compiler you will have to cast using:
1 | rptr = (RowArray *)malloc(.... etc. |
Using this approach, rptr has all the characteristics of an array name name, (except that rptr is modifiable), and array notation may be used throughout the rest of the program. That also means that if you intend to write a function to modify the array contents, you must use COLS as a part of the formal parameter in that function, just as we did when discussing the passing of two dimensional arrays to a function.
METHOD 2:
In the METHOD 1 above, rptr turned out to be a pointer to type "one dimensional array of COLS integers". It turns out that there is syntax which can be used for this type without the need of typedef. If we write:
1 | int (*xptr)[COLS]; |
the variable xptr will have all the same characteristics as the variable rptr in METHOD 1 above, and we need not use the typedef keyword. Here xptr is a pointer to an array of integers and the size of that array is given by the #defined COLS. The parenthesis placement makes the pointer notation predominate, even though the array notation has higher precedence. i.e. had we written
1 | int *xptr[COLS]; |
we would have defined xptr as an array of pointers holding the number of pointers equal to that #defined by COLS. That is not the same thing at all. However, arrays of pointers have their use in the dynamic allocation of two dimensional arrays, as will be seen in the next 2 methods. METHOD 3:
Consider the case where we do not know the number of elements in each row at compile time, i.e. both the number of rows and number of columns must be determined at run time. One way of doing this would be to create an array of pointers to type int and then allocate space for each row and point these pointers at each row. Consider:
-------------- Program 9.2 ------------------------------------
/* Program 9.2 from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int nrows = 5; /* Both nrows and ncols could be evaluated */
int ncols = 10; /* or read in at run time */
int row;
int **rowptr;
rowptr = malloc(nrows * sizeof(int *));
if (rowptr == NULL)
{
puts("\nFailure to allocate room for row pointers.\n");
exit(0);
}
printf("\n\n\nIndex Pointer(hex) Pointer(dec) Diff.(dec)");
for (row = 0; row < nrows; row++)
{
rowptr[row] = malloc(ncols * sizeof(int));
if (rowptr[row] == NULL)
{
printf("\nFailure to allocate for row[%d]\n",row);
exit(0);
}
printf("\n%d %p %d", row, rowptr[row], rowptr[row]);
if (row > 0)
printf(" %d",(int)(rowptr[row] - rowptr[row-1]));
}
return 0;
}
--------------- End 9.2 ------------------------------------
In the above code rowptr is a pointer to pointer to type int. In this case it points to the first element of an array of pointers to type int. Consider the number of calls to malloc():
1 2 3 4 | To get the array of pointers 1 call
To get space for the rows 5 calls
-----
Total 6 calls
|
If you choose to use this approach note that while you can use the array notation to access individual elements of the array, e.g. rowptr[row][col] = 17;, it does not mean that the data in the "two dimensional array" is contiguous in memory. You can, however, use the array notation just as if it were a continuous block of memory. For example, you can write:
1 | rowptr[row][col] = 176; |
just as if rowptr were the name of a two dimensional array created at compile time. Of course row and col must be within the bounds of the array you have created, just as with an array created at compile time. If you want to have a contiguous block of memory dedicated to the storage of the elements in the array you can do it as follows:
METHOD 4:
In this method we allocate a block of memory to hold the whole array first. We then create an array of pointers to point to each row. Thus even though the array of pointers is being used, the actual array in memory is contiguous. The code looks like this: ----------------- Program 9.3 -----------------------------------
/* Program 9.3 from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int **rptr;
int *aptr;
int *testptr;
int k;
int nrows = 5; /* Both nrows and ncols could be evaluated */
int ncols = 8; /* or read in at run time */
int row, col;
/* we now allocate the memory for the array */
aptr = malloc(nrows * ncols * sizeof(int));
if (aptr == NULL)
{
puts("\nFailure to allocate room for the array");
exit(0);
}
/* next we allocate room for the pointers to the rows */
rptr = malloc(nrows * sizeof(int *));
if (rptr == NULL)
{
puts("\nFailure to allocate room for pointers");
exit(0);
}
/* and now we 'point' the pointers */
for (k = 0; k < nrows; k++)
{
rptr[k] = aptr + (k * ncols);
}
/* Now we illustrate how the row pointers are incremented */
printf("\n\nIllustrating how row pointers are incremented");
printf("\n\nIndex Pointer(hex) Diff.(dec)");
for (row = 0; row < nrows; row++)
{
printf("\n%d %p", row, rptr[row]);
if (row > 0)
printf(" %d",(rptr[row] - rptr[row-1]));
}
printf("\n\nAnd now we print out the array\n");
for (row = 0; row < nrows; row++)
{
for (col = 0; col < ncols; col++)
{
rptr[row][col] = row + col;
printf("%d ", rptr[row][col]);
}
putchar('\n');
}
puts("\n");
/* and here we illustrate that we are, in fact, dealing with
a 2 dimensional array in a contiguous block of memory. */
printf("And now we demonstrate that they are contiguous in memory\n");
testptr = aptr;
for (row = 0; row < nrows; row++)
{
for (col = 0; col < ncols; col++)
{
printf("%d ", *(testptr++));
}
putchar('\n');
}
return 0;
}
------------- End Program 9.3 -----------------
Consider again, the number of calls to malloc() To get room for the array itself 1 call To get room for the array of ptrs 1 call ---- Total 2 calls
Now, each call to malloc() creates additional space overhead since malloc() is generally implemented by the operating system forming a linked list which contains data concerning the size of the block. But, more importantly, with large arrays (several hundred rows) keeping track of what needs to be freed when the time comes can be more cumbersome. This, combined with the contiguousness of the data block that permits initialization to all zeroes using memset() would seem to make the second alternative the preferred one.
As a final example on multidimensional arrays we will illustrate the dynamic allocation of a three dimensional array. This example will illustrate one more thing to watch when doing this kind of allocation. For reasons cited above we will use the approach outlined in alternative two. Consider the following code:
------------------- Program 9.4 -------------------------------------
/* Program 9.4 from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
int X_DIM=16;
int Y_DIM=5;
int Z_DIM=3;
int main(void)
{
char *space;
char ***Arr3D;
int y, z;
ptrdiff_t diff;
/* first we set aside space for the array itself */
space = malloc(X_DIM * Y_DIM * Z_DIM * sizeof(char));
/* next we allocate space of an array of pointers, each
to eventually point to the first element of a
2 dimensional array of pointers to pointers */
Arr3D = malloc(Z_DIM * sizeof(char **));
/* and for each of these we assign a pointer to a newly
allocated array of pointers to a row */
for (z = 0; z < Z_DIM; z++)
{
Arr3D[z] = malloc(Y_DIM * sizeof(char *));
/* and for each space in this array we put a pointer to
the first element of each row in the array space
originally allocated */
for (y = 0; y < Y_DIM; y++)
{
Arr3D[z][y] = space + (z*(X_DIM * Y_DIM) + y*X_DIM);
}
}
/* And, now we check each address in our 3D array to see if
the indexing of the Arr3d pointer leads through in a
continuous manner */
for (z = 0; z < Z_DIM; z++)
{
printf("Location of array %d is %p\n", z, *Arr3D[z]);
for ( y = 0; y < Y_DIM; y++)
{
printf(" Array %d and Row %d starts at %p", z, y, Arr3D[z][y]);
diff = Arr3D[z][y] - space;
printf(" diff = %d ",diff);
printf(" z = %d y = %d\n", z, y);
}
}
return 0;
}
------------------- End of Prog. 9.4 ----------------------------
If you have followed this tutorial up to this point you should have no problem deciphering the above on the basis of the comments alone. There are a couple of points that should be made however. Let's start with the line which reads: Arr3D[z][y] = space + (z(X_DIM * Y_DIM) + yX_DIM);
Note that here space is a character pointer, which is the same type as Arr3D[z][y]. It is important that when adding an integer, such as that obtained by evaluation of the expression (z(X_DIM * Y_DIM) + yX_DIM), to a pointer, the result is a new pointer value. And when assigning pointer values to pointer variables the data types of the value and variable must match.
CHAPTER 10: Pointers to Functions
Up to this point we have been discussing pointers to data objects. C also permits the declaration of pointers to functions. Pointers to functions have a variety of uses and some of them will be discussed here.
Consider the following real problem. You want to write a function that is capable of sorting virtually any collection of data that can be stored in an array. This might be an array of strings, or integers, or floats, or even structures. The sorting algorithm can be the same for all. For example, it could be a simple bubble sort algorithm, or the more complex shell or quick sort algorithm. We'll use a simple bubble sort for demonstration purposes.
Sedgewick [1] has described the bubble sort using C code by setting up a function which when passed a pointer to the array would sort it. If we call that function bubble(), a sort program is described by bubble_1.c, which follows:
/*-------------------- bubble_1.c --------------------*/
/* Program bubble_1.c from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int a[], int N);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int a[], int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (a[j-1] > a[j])
{
t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
}
/---------------------- end bubble_1.c -----------------------/
The bubble sort is one of the simpler sorts. The algorithm scans the array from the second to the last element comparing each element with the one which precedes it. If the one that precedes it is larger than the current element, the two are swapped so the larger one is closer to the end of the array.
On the first pass, this results in the largest element ending up at the end of the array. The array is now limited to all elements except the last and the process repeated. This puts the next largest element at a point preceding the largest element. The process is repeated for a number of times equal to the number of elements minus 1. The end result is a sorted array.
Here our function is designed to sort an array of integers. Thus in line 1 we are comparing integers and in lines 2 through 4 we are using temporary integer storage to store integers. What we want to do now is see if we can convert this code so we can use any data type, i.e. not be restricted to integers.
At the same time we don't want to have to analyze our algorithm and the code associated with it each time we use it. We start by removing the comparison from within the function bubble() so as to make it relatively easy to modify the comparison function without having to re-write portions related to the actual algorithm. This results in bubble_2.c:
/*---------------------- bubble_2.c -------------------------*/
/* Program bubble_2.c from PTRTUT10.HTM 6/13/97 */
/* Separating the comparison function */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int a[], int N);
int compare(int m, int n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int a[], int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare(a[j-1], a[j]))
{
t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
}
int compare(int m, int n)
{
return (m > n);
}
/*--------------------- end of bubble_2.c -----------------------*/
If our goal is to make our sort routine data type independent, one way of doing this is to use pointers to type void to point to the data instead of using the integer data type. As a start in that direction let's modify a few things in the above so that pointers can be used. To begin with, we'll stick with pointers to type integer.
/*----------------------- bubble_3.c -------------------------*/
/* Program bubble_3.c from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int *p, int N);
int compare(int *m, int *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int *p, int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare(&p[j-1], &p[j]))
{
t = p[j-1];
p[j-1] = p[j];
p[j] = t;
}
}
}
}
int compare(int *m, int *n)
{
return (*m > *n);
}
/*------------------ end of bubble3.c -------------------------*/
Note the changes. We are now passing a pointer to an integer (or array of integers) to bubble(). And from within bubble we are passing pointers to the elements of the array that we want to compare to our comparison function. And, of course we are dereferencing these pointer in our compare() function in order to make the actual comparison. Our next step will be to convert the pointers in bubble() to pointers to type void so that that function will become more type insensitive. This is shown in bubble_4.
/*------------------ bubble_4.c ----------------------------*/
/* Program bubble_4.c from PTRTUT10,HTM 6/13/97 */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int *p, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int *p, int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare((void *)&p[j-1], (void *)&p[j]))
{
t = p[j-1];
p[j-1] = p[j];
p[j] = t;
}
}
}
}
int compare(void *m, void *n)
{
int *m1, *n1;
m1 = (int *)m;
n1 = (int *)n;
return (*m1 > *n1);
}
/*------------------ end of bubble_4.c ---------------------*/
Note that, in doing this, in compare() we had to introduce the casting of the void pointer types passed to the actual type being sorted. But, as we'll see later that's okay. And since what is being passed to bubble() is still a pointer to an array of integers, we had to cast these pointers to void pointers when we passed them as parameters in our call to compare().
We now address the problem of what we pass to bubble(). We want to make the first parameter of that function a void pointer also. But, that means that within bubble() we need to do something about the variable t, which is currently an integer. Also, where we use t = p[j-1]; the type of p[j-1] needs to be known in order to know how many bytes to copy to the variable t (or whatever we replace t with).
Currently, in bubble_4.c, knowledge within bubble() as to the type of the data being sorted (and hence the size of each individual element) is obtained from the fact that the first parameter is a pointer to type integer. If we are going to be able to use bubble() to sort any type of data, we need to make that pointer a pointer to type void.
But, in doing so we are going to lose information concerning the size of individual elements within the array. So, in bubble_5.c we will add a separate parameter to handle this size information.
These changes, from bubble4.c to bubble5.c are, perhaps, a bit more extensive than those we have made in the past. So, compare the two modules carefully for differences.
/*---------------------- bubble5.c ---------------------------*/
/* Program bubble_5.c from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <string.h>
long arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(void *p, size_t width, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr, sizeof(long), 10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%ld ", arr[i]);
}
return 0;
}
void bubble(void *p, size_t width, int N)
{
int i, j;
unsigned char buf[4];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare((void *)(bp + width*(j-1)),
(void *)(bp + j*width))) /* 1 */
{
/* t = p[j-1]; */
memcpy(buf, bp + width*(j-1), width);
/* p[j-1] = p[j]; */
memcpy(bp + width*(j-1), bp + j*width , width);
/* p[j] = t; */
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare(void *m, void *n)
{
long *m1, *n1;
m1 = (long *)m;
n1 = (long *)n;
return (*m1 > *n1);
}
/*--------------------- end of bubble5.c ---------------------*/
Note that I have changed the data type of the array from int to long to illustrate the changes needed in the compare() function. Within bubble() I've done away with the variable t (which we would have had to change from type int to type long). I have added a buffer of size 4 unsigned characters, which is the size needed to hold a long (this will change again in future modifications to this code). The unsigned character pointer *bp is used to point to the base of the array to be sorted, i.e. to the first element of that array.
We also had to modify what we passed to compare(), and how we do the swapping of elements that the comparison indicates need swapping. Use of memcpy() and pointer notation instead of array notation work towards this reduction in type sensitivity.
Again, making a careful comparison of bubble5.c with bubble4.c can result in improved understanding of what is happening and why.
We move now to bubble6.c where we use the same function bubble() that we used in bubble5.c to sort strings instead of long integers. Of course we have to change the comparison function since the means by which strings are compared is different from that by which long integers are compared. And,in bubble6.c we have deleted the lines within bubble() that were commented out in bubble5.c.
/*--------------------- bubble6.c ---------------------*/
/* Program bubble_6.c from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <string.h>
#define MAX_BUF 256
char arr2[5][20] = { "Mickey Mouse",
"Donald Duck",
"Minnie Mouse",
"Goofy",
"Ted Jensen" };
void bubble(void *p, int width, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 5; i++)
{
printf("%s\n", arr2[i]);
}
bubble(arr2, 20, 5);
putchar('\n\n');
for (i = 0; i < 5; i++)
{
printf("%s\n", arr2[i]);
}
return 0;
}
void bubble(void *p, int width, int N)
{
int i, j, k;
unsigned char buf[MAX_BUF];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
k = compare((void *)(bp + width*(j-1)), (void *)(bp + j*width));
if (k > 0)
{
memcpy(buf, bp + width*(j-1), width);
memcpy(bp + width*(j-1), bp + j*width , width);
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare(void *m, void *n)
{
char *m1 = m;
char *n1 = n;
return (strcmp(m1,n1));
}
/*------------------- end of bubble6.c ---------------------*/
But, the fact that bubble() was unchanged from that used in bubble5.c indicates that that function is capable of sorting a wide variety of data types. What is left to do is to pass to bubble() the name of the comparison function we want to use so that it can be truly universal. Just as the name of an array is the address of the first element of the array in the data segment, the name of a function decays into the address of that function in the code segment. Thus we need to use a pointer to a function. In this case the comparison function.
Pointers to functions must match the functions pointed to in the number and types of the parameters and the type of the return value. In our case, we declare our function pointer as:
int (fptr)(const void p1, const void *p2);
Note that were we to write:
1 | int *fptr(const void *p1, const void *p2); |
we would have a function prototype for a function which returned a pointer to type int. That is because in C the parenthesis () operator have a higher precedence than the pointer * operator. By putting the parenthesis around the string (*fptr) we indicate that we are declaring a function pointer.
We now modify our declaration of bubble() by adding, as its 4th parameter, a function pointer of the proper type. It's function prototype becomes:
1 2 3 | void bubble(void *p, int width, int N, int(*fptr)(const void *, const void *)); |
When we call the bubble(), we insert the name of the comparison function that we want to use. bubble7.c illustrate how this approach permits the use of the same bubble() function for sorting different types of data.
/*------------------- bubble7.c ------------------*/
/* Program bubble_7.c from PTRTUT10.HTM 6/10/97 */
#include <stdio.h>
#include <string.h>
#define MAX_BUF 256
long arr[10] = { 3,6,1,2,3,8,4,1,7,2};
char arr2[5][20] = { "Mickey Mouse",
"Donald Duck",
"Minnie Mouse",
"Goofy",
"Ted Jensen" };
void bubble(void *p, int width, int N,
int(*fptr)(const void *, const void *));
int compare_string(const void *m, const void *n);
int compare_long(const void *m, const void *n);
int main(void)
{
int i;
puts("\nBefore Sorting:\n");
for (i = 0; i < 10; i++) /* show the long ints */
{
printf("%ld ",arr[i]);
}
puts("\n");
for (i = 0; i < 5; i++) /* show the strings */
{
printf("%s\n", arr2[i]);
}
bubble(arr, 4, 10, compare_long); /* sort the longs */
bubble(arr2, 20, 5, compare_string); /* sort the strings */
puts("\n\nAfter Sorting:\n");
for (i = 0; i < 10; i++) /* show the sorted longs */
{
printf("%d ",arr[i]);
}
puts("\n");
for (i = 0; i < 5; i++) /* show the sorted strings */
{
printf("%s\n", arr2[i]);
}
return 0;
}
void bubble(void *p, int width, int N,
int(*fptr)(const void *, const void *))
{
int i, j, k;
unsigned char buf[MAX_BUF];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
k = fptr((void *)(bp + width*(j-1)), (void *)(bp + j*width));
if (k > 0)
{
memcpy(buf, bp + width*(j-1), width);
memcpy(bp + width*(j-1), bp + j*width , width);
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare_string(const void *m, const void *n)
{
char *m1 = (char *)m;
char *n1 = (char *)n;
return (strcmp(m1,n1));
}
int compare_long(const void *m, const void *n)
{
long *m1, *n1;
m1 = (long *)m;
n1 = (long *)n;
return (*m1 > *n1);
}
/*----------------- end of bubble7.c -----------------*/
References for Chapter 10:
"Algorithms in C" Robert Sedgewick Addison-Wesley ISBN 0-201-51425-7
EPILOG
I have written the preceding material to provide an introduction to pointers for newcomers to C. In C, the more one understands about pointers the greater flexibility one has in the writing of code. The above expands on my first effort at this which was entitled ptr_help.txt and found in an early version of Bob Stout's collection of C code SNIPPETS. The content in this version has been updated from that in PTRTUTOT.ZIP included in SNIP9510.ZIP.
I am always ready to accept constructive criticism on this material, or review requests for the addition of other relevant material. Therefore, if you have questions, comments, criticisms, etc. concerning that which has been presented, I would greatly appreciate your contacting me via email me at tjensen@ix.netcom.com.
Comments
comments powered by Disqus