開源技術教學文件網 如何使用結構 (Struct)

最後修改日期為 JUL 31, 2018

前言

相對於先前介紹的基本型別 (primitive data type),結構 (structure) 是一種複合型別 (derived data type),用來表達由多個屬性組成的型別,而這些屬性可以是基本型別或是另一個複合型別所組成。

在我們先前的程式中,大多都僅使用基本型別,透過結構,我們可以創造新的型別。由於 C 沒有內建的物件導向語法,使用指向結構的指標來模擬 C++ (或 Java 或 C#) 的 this 指標是相當常見的手法。

宣告結構

使用 struct 保留字可以宣告結構,如下例:

struct person_t {
    char *name;
    unsigned age;
};

int main(void)
{
    struct person_t p = { "Michelle", 37 };  
    
    return 0;
}

但這種初始化結構的方式寫死該結構的屬性的位置,若屬性有更動需一併更動相關程式碼,在軟工觀點上不佳。可以改用以下的方法來初始化結構:

struct person_t {
    char *name;
    unsigned age;
};

int main(void)
{
    struct person_t p = { 
        .name = "Michelle", 
        .age = 37
    };  
    
    return 0;
}

透過這種方式,不用寫死結構中各個屬性的相對位置,日後要更動屬性時,可將要修改的部分降低。

此外,可以搭配 typedef 來簡化結構的型別名稱:

/* Forward declaration. */
typedef struct person_t person_t;

struct person_t {
    char *name;
    unsigned age;
};

int main(void)
{
    person_t p = { 
        .name = "Michelle", 
        .age = 37
    };  
    
    return 0;
}

如果想節省命名空間可進一步使用以下方式來宣告結構:

typedef struct {
    char *name;
    unsigned age;
} person_t;

這時候的結構是匿名結構 (anonymous structure),不會占用命名空間。

存取結構內屬性

使用 . (點號) 可存取結構內的屬性,如下例:

#include <assert.h>

typedef struct point_t point_t;

struct point_t {
    double x;
    double y;
};

int main(void)
{
    point_t pt = {
        .x = 3.0,
        .y = 4.0
    };
    
    assert(pt.x == 3);
    assert(pt.y == 4);
    
    return 0;
}

內嵌在結構內的結構

由於結構視為一種型別,我們可以在結構內嵌入另一個結構,如下例:

#include <assert.h>
#include <string.h>

typedef struct person_t person_t;

struct person_t {
    char *name;
    unsigned age;
};

typedef struct employee_t employee_t;

struct employee_t {
    person_t p;
    double salary;
};

int main(void)
{
    employee_t ee = {
        .p = { .name = "Michelle", .age = 37 },
        .salary = 100.0
    };
    
    assert(strcmp(ee.p.name, "Michelle") == 0);
    assert(ee.p.age == 37);
    assert(ee.salary == 100.0);

    return 0;
}

但結構內不能嵌入同一個結構,也就是結構不能遞迴宣告。相對來說,結構內可以放入指向同一結構的指針,在資料結構上常見這種特性。

儲存結構的陣列

由於結構在整體上視為一個新型別,我們可以用陣列來儲存多個結構,如下例:

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

typedef struct point_t point_t;

struct point_t {
    double x;
    double y;
};

int main(void)
{
    point_t pts[] = {
        { .x = 0.0, .y = 0.0 },
        { .x = 1.0, .y = 2.0 },
        { .x = 3.0, .y = 4.0 }
    };

    for (size_t i = 0; i < 3; i++) {
        printf("(%.2f, %.2f)\n", pts[i].x, pts[i].y);
    }

    return 0;
}

宣告指向指標的結構

以下是一個宣告結構指標 (pointer to struct) 的簡單實例:

#include <stdlib.h>

typedef struct point_t point_t;

struct point_t {
    double x;
    double y;
};

int main(void)
{
    point_t *pt = malloc(sizeof(point_t));
    if (!pt)
        return 1;
    
    free(pt);

    return 0;
}

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

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

typedef struct point_t point_t;
typedef point_t * point_p;

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

存取結構指標的屬性

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

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

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

#include <assert.h>
#include <stdlib.h>

typedef struct point_t point_t;

struct point_t {
    double x;
    double y;
};

int main(void)
{
    point_t *pt = malloc(sizeof(point_t));
    if (!pt)
        return 1;
    
    /* 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_t node_t;

struct node_t {
    int data;
    node_t *next;
};

typedef struct stack_t stack_t;

struct stack_t {
    node_t *top;
};

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

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

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

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

typedef struct node_t node_t;

struct node_t {
    int data;
    node_t *next;
};

typedef node_t *stack_t;

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

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

/* Program state. */
bool failed = false;

/* Create a `stack_t` object. */
stack_t *st = malloc(sizeof(stack_t));
if (!st)
    return EXIT_FAILURE;
    
st->top = NULL;

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

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

/* Insert an element. */
{
    // Create a new node.
    node_t *node = malloc(sizeof(node_t));
    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_t *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_t *curr = st->top;
    node_t *temp;
    while (curr) {
        temp = curr;
        curr = curr->next;
        free(temp);
    }
        
    free(st);
}

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

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

電子書籍

如果你覺得這篇 C 語言的技術文章對你有幫助,可以看看以下完整的 C 語言程式設計電子書:

現代 C 語言程式設計

分享本文
Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Yahoo
追蹤本站
Facebook Facebook Twitter