C 速查手冊

自我參考的結構

結構 (structure) 中不能有與自己相同識別字 (identifier) 名稱的結構,但可以有指向相同識別字名稱結構的指標 (pointer) ,這是說 C 語言可以簡單的利用結構與指標把資料連接起來,形成複雜的資料結構 (data structure) 。

如下例定義了一個結構 list ,其中有一個成員宣告為指向 list 的指標

#include <stdio.h>

struct list {
    char *name;
    struct list *nextPtr;
};

typedef struct list List;

int main(void)
{
    List a, b, c, *startPtr;
    
    a.name = "John";
    b.name = "Mary";
    c.name = "Tony";
    
    startPtr = &a;
    a.nextPtr = &b;
    b.nextPtr = &c;
    c.nextPtr = NULL;
    
    while (startPtr != NULL) {
        printf("%s\n", startPtr->name);
        startPtr = startPtr->nextPtr;
    }

    return 0;
}

/* 《程式語言教學誌》的範例程式
    http://kaiching.org/
    檔名:structlist.c
    功能:示範自我參考的結構
    作者:張凱慶 */

編譯後執行,結果如下

$ gcc structlist.c
$ a.out
John
Mary
Tony
$

宣告 List 變數的地方

List a, b, c, *startPtr;

這裡分別宣告了三個 List 型態的結構變數,另外一個指向 List 型態的指標變數。

下面替三個 List 變數設定成員值

a.name = "John";
    b.name = "Mary";
    c.name = "Tony";

底下繼續將 a 的位址指派給額外宣告的指標 startPtr

startPtr = &a;

這是說將 a 作為此資料結構的起始點,同時利用額外的指標進行操作。因為從指標可以輕易的取所指向結構的成員,指標也可以當成控制變數,因而使用指標得以容易遊走在資料結構中。

List 型態結構的另一個成員 nextPtr ,便是指向下一筆資料項目的位址。接下來

a.nextPtr = &b;
b.nextPtr = &c;
c.nextPtr = NULL;

此例中把 a 當成第一筆資料,也就是資料結構的起始項目, b 是第二筆資料, c 為第三筆資料,因此 anextPtr 指向 b 的位址,而 bnextPtr 指向 c 。由於 c 為最後一筆資料,因此將 cnextPtr 設為 NULLNULL 是 C 語言標準程式庫 (standard library) 所定義的一個特別的值,代表無效的指標。

最後的 while 迴圈

while (startPtr != NULL) {
    printf("%s\n", startPtr->name);
    startPtr = startPtr->nextPtr;
}

最後使用了一個迴圈 (loop) ,這個迴圈的結束條件為 startPtr 等於 NULL 。此迴圈的任務為印出指標所指向結構的 name 成員,然後把 startPtr 重新指派給所指向結構的 nextPtr 成員。

由於 startPtr 最初的值為 a 的位址,所以第一次進入迴圈會印出 aname 成員,同時 anextPtr 成員的值會重新指派給 startPtr 。我們之前是將 anextPtr 設定成 b 的位址,所以第二次進入迴圈時, startPtr 指向的是 b ,之後的動作皆可類推。

這樣的資料結構稱之為鍵結串列 (linked list) ,所有的資料可以分開儲存在不同非連續的記憶體位址。須留意一點,這裡用一個簡單的方式說明 C 語言的結構與指標的一般應用,而非建立實際可有效運用的資料結構。

複雜的資料結構還需要用標準程式庫中的 malloc() 向作業系統借記憶體空間,不需要使用後還得用 free() 將借來的記憶體空間還給作業系統,真正大型的 C 程式就需要大量的運用 malloc()free() 及其他記憶體相關的函數做記憶體管理。

回 C 速查手冊首頁