C 語言程式設計教學:結構和指標

PUBLISHED ON AUG 16, 2018 — PROGRAMMING

    由於結構視為一種型別,我們也可以宣告指向結構的指標 (pointer to struct),以及對其動態配置記憶體。熟悉結構指標是相當重要的,因為 C 語言的資料結構和物件導向就是此語法特性為基礎繼續延伸。

    宣告指向指標的結構

    以下是一個宣告結構指標的簡單實例:

    #include <stdlib.h>
    
    typedef struct point Point;
    
    struct point {
        double x;
        double y;
    };
    
    int main(void)
    {
        Point *pt = malloc(sizeof(Point));
        if (!pt) {
            return EXIT_FAILURE;
        }
        
        free(pt);
    
        return 0;
    }
    

    由於我們從 heap 動態配置記憶體,在程式尾段要記得將記憶體釋放掉。

    有些 C 語言教材會將型別名稱進一步簡化,如下例:

    typedef struct point Point;
    typedef Point * Point_p;
    

    這不是硬性規定,僅為個人風格;筆者目前沒有採用這種方式,因為有時會忘了該型別其實是指標;如果要這樣做,建議在尾端加上 _pPtr 等可以辨識的型別名稱。

    存取結構指標的屬性

    存取結構指標內的屬性有兩種方式:

    • 解指標 (dereference)
    • 使用 -> (箭號)

    第二種方式在語法上比較簡潔,故較受歡迎,可以當做一種語法糖。在我們這個例子中,我們兩種方法都使用,供讀者參考:

    #include <assert.h>
    #include <stdlib.h>
    
    typedef struct point Point;
    
    struct point {
        double x;
        double y;
    };
    
    int main(void)
    {
        Point *pt = malloc(sizeof(Point));
        if (!pt) {
            return EXIT_FAILURE;
        }
        
        // Init x and y with dereference.
        (*pt).x = 0.0;
        (*pt).y = 0.0;
        
        // Access fields of pt with dereference.
        assert((*pt).x == 0.0);
        assert((*pt).y == 0.0);
        
        // Mutate x and y with `->`
        pt->x = 3.0;
        pt->y = 4.0;
        
        // Access fields of pt with `->`
        assert(pt->x == 3.0);
        assert(pt->y == 4.0);
        
        free(pt);
    
        return 0;
    }
    

    案例:無函式的堆疊操作

    本節不是必需的,若覺得沒有需求或過於艱難可先略過不讀。

    我們一般在練習資料結構和演算法時,我們都會將程式碼包在函式 (或方法) 中,因為我們心中假定這些資料結構和演算法是可重覆利用的程式碼區塊,事實上也是如此。但初學者一開始時可以嘗試直接將資料結構或演算法的步驟直接寫在主程式中,在某些情境下這樣做反而會比較簡單,日後在改寫成函式時也可以了解兩者的差異。如果已經熟悉 C 核心語法的讀者,倒不需要刻意這樣做。

    由於整個程式碼略長,我們將完整的程式碼在這裡展示,有需要的讀者可自行前往觀看。接下來,我們會分段說明。

    堆疊 (stack) 是一種先進後出 (FILO, 即 first-in, last-out) 的線性 (linear) 資料結構,可以想成是一個桶子,先放進去的東西會放置在下面,後放進去的東西會放置在上方。

    典型的 C 資料結構會採取以下的方式來宣告堆疊型別:

    typedef struct node Node;
    
    struct node {
        int data;
        Node *next;
    };
    
    typedef struct stack Stack;
    
    struct stack {
        Node *top;
    };
    

    Node 型別是用來儲存資料的盒子,而 Stack 型別會將 Node 型別包在裡面,日後用函式寫資料結構時,Node 型別不會外露。

    在我們這個例子中,我們採用單向連結串列 (singly-linked list) 將堆疊串起來,如果讀者一開始不知道這是什麼意思也無妨,這只是描述某種串連節點的方式的術語。

    由這個例子可以發現,雖然結構不能內嵌同一結構,但可內嵌指向同一結構的指標。

    有些 C 語言教材會採用以下策略:

    typedef struct node Node;
    
    struct node {
        int data;
        Node *next;
    };
    
    typedef Node * Stack;
    

    這樣的做法就是將指向 Node 的指標外露,在這個例子是可行的;然而,在許多資料結構,會用到超過一項的屬性,這個方法就行不通。讀者可以自行練習用這種方法改寫本範例。

    首先,我們建立堆疊物件 st

    // Program state.
    bool failed = false;
    
    // Create a Stack object.
    Stack *st = malloc(sizeof(Stack));
    if (!st) {
        return EXIT_FAILURE;
    }
        
    st->top = NULL;
    

    同樣也是用 malloc 搭配 sizeof 即可配置記憶體。至於 failed 僅是用來表示整個程式運作狀態的旗標,和堆疊操作無關。

    接著,建立並插入第一個節點:

    // Insert an element.
    {
        // Create a new node.
        Node *node = malloc(sizeof(Node));
        if (!node) {
            perror("Failed to allocate a node");
            failed = true;
            goto STACK_FREE;
        }
            
        node->data = 9;
        node->next = NULL;
            
        // Point st->top to node.
        st->top = node;
    }
    

    在這段程式碼中,我們刻意將整段程式碼包在一個區塊中,這是為了減少命名空間的汙染;簡單地說,變數 node 的名稱在這個區塊結束後就無效,不會影響到後續的程式碼。

    其實配置記憶體的動作是有可能失敗的,所以要考慮失敗時的處理方法。在本程式中,我們在配置記憶體失敗時,就將先前已配置的記憶體釋放掉,並以失敗狀態結束本程式。在這個例子中,我們優雅地用 goto 來減少重覆的程式碼,讀者可追蹤本例完整的程式碼即知其使用方式。

    接著,我們檢查堆疊頂端的資料:

    // Peek top element.
    if (st->top->data != 9) {
        perror("It should be 9");
        failed = true;
        goto STACK_FREE;
    }
    

    我們以撰寫測試程式的精神撰寫此段程式碼,當程式不符預期時就進行結束程式相關的動作。

    我們中間有略過一些程式碼。接著來看從堆疊中取出節點的方法:

    // Pop top element.
    do {
        Node *curr = st->top;
        if (!curr) {
            break;
        }
        
        // Update st->top.
        st->top = curr->next;
            
        if (curr->data != 5) {
            perror("It should be 5");
            failed = true;
            goto STACK_FREE;
        }
            
        free(curr);
    } while (0);
    

    我們在這裡用單次執行的 do ... while 區塊包住程式碼,因為在 st->topNULL 時可以利用 break 直接結束這段程式碼。

    在取出該節點後,我們要更新 st->top 所指的節點。另外,取出的節點之後沒有指標會指到,故需在此處即釋放其記憶體。

    最後,我們展示釋放堆疊物件的程式碼:

    STACK_FREE:
    {
        Node *curr = st->top;
        Node *temp;
        while (curr) {
            temp = curr;
            curr = curr->next;
            free(temp);
        }
            
        free(st);
    }
    

    如果我們先前提過的,釋放記憶體要由內而外。我們先將內側的節點逐一釋放,最後將外部的堆疊物件釋放掉。

    透過本節的範例,我們不僅可以學會指標函式的使用方式,也可以使用一個替代性的方法來練習資料結構和演算法。然而,從本程式可觀察到,隨著程式變長,不免開始出現一些重覆的程式碼,這也是為什麼我們要用函式 (或方法) 包覆程式以減少重覆的程式碼。本節的方法僅止於早期程式短小時的練習,之後還是要用函式和模組等手法組織程式碼。

    comments powered by Disqus