結構(struct)

說明：

指能夠結合多個彼此相關的變數在一個名稱之下，且可以包含數個不同資料型態的變數。換句話說，結構是一種使用者自定的型態，它可將不同的資料型態串在一起。舉例而言：「學生個人資料表」，裡頭有姓名(字串型態)、年齡(整數型態)、生日(日期型態)…等等。

格式：

struct 結構型態

{

欄項資料型態欄項變數名稱；

　　　：　　　　　：

} 變數Ⅰ，變數Ⅱ……;

示意圖：

範例：

struct Student_PersonalData {
    char name[4];
    int age;
    char address[30];
} SP_Data;

應用範例：

#include <stdio.h>
#include <string.h>
void main() {
    struct Student_Perosnal_Data {
        char name[10];
        int age;
        char address[50];
        char interest[11];
    } stu;
    strcpy(stu.name,"張三");
    stu.age = 25;
    strcpy(stu.address, "南投縣埔里鎮大學路一號");
    strcpy(stu.interest, "basketball");
    printf("The student's name is: %s\n", stu.name);
    printf("The student's age is: %d\n", stu.age);
    printf("The student's address is: %s\n", stu.address);
    printf("The student's interest is: %s\n", stu.interest);
}

上述的struct Student_PersonalData一經定義以後,就可以比照C的內建資料型別來宣告和處理。

struct內也可以其他的struct

struct Student_Detail {
    int age;
    char *name;
    char *address;
};
struct Student_Data {
    int stuid;
    struct Student_Detail detail;
};
void main() {
    struct Student_Data x;
    x.stuid = 100;
    x.detail.age = 20;
    x.detail.name = "Johnson Lee";
    x.detail.address = "Nation Chi Nan University";
}

用於struct的運算符號

在如下的結構定義裡,next前面的*不可省略,否則就遞迴定義了,Compiler將無法決定struct list的大小。

struct list {
    int data;
    struct list *next; // a pointer to struct list
};

struct list listOne, listTwo, listThree;

listOne.next = &listTwo;
listTwo.next = &listThree;
// 以下想要由listOne設定到listThree的data
listOne.next.next.data = 0; // 這不合法, 因為.的左邊必須是struct,不可以是pointer
(*(*listOne.next).next).data = 0; // 這樣寫才對

你會發現上面的例子中, 如果struct裡面有pointer to struct, 而我們想要用該pointer來存取結構成員時, 就必須很小心的用*和()來表達。由於結構成員包括指向結構的指標(define a pointer to struct in a struct), 是很常見的事情, 這樣的(*(*listOne.next).next).data語法既難寫又難懂, 因此C語言定義了->運算符號。此符號的左邊是一個pointer to struct, 右邊則是該pointer指到的結構成員。->為第一優先權左結合, 因此

(*(*listOne.next).next).data = 0; //這樣寫才對
listOne.next->next->data = 0; // 這樣寫更漂亮

動態空間分配

所謂動態空間分配指的是,在執行期間由程式向作業系統或程式庫要求後才分配的空間,這塊記憶體區域稱為Heap(堆積)。C語言的動態空間分配主要透過malloc和free兩函數來處理。這兩個函數的宣告如下:

void *malloc(size_t size);
void free(void *ptr);

透過malloc()所分配出來的空間必須由使用者呼叫free()才能歸還給系統。初學者常犯的錯誤之一,就是忘了用free()歸還空間,這會造成程式佔用太多記憶體,此現象稱為memory leakage。相反的,如果空間已用free()歸還了,卻還試著去使用那塊記憶體,則會發生Segmentation Fault (core dumped)的錯誤。

Linked Stack

typedef struct items {
    int data;
    struct items *link;
} ITEM;

typedef struct stack {
    ITEM *top;
} STACK;

void initStack(STACK *s) {
    s->top = NULL;
}

void pushStack(STACK *s, int y) {
    ITEM *x; // x will point to the new ITEM
    x = (ITEM *) malloc(sizeof(ITEM)); // allocate memory for the new ITEM
    x->data = y; // store data
    x->link = s->top; // x->link points to where s->top points
    s->top = x; // stack's top points to x
}

int popStack(STACK *s) {
    ITEM * x = s->top;
	int d = x->data;
    s->top = s->top->link;
    free(x);
    return d;
}
int stackIsEmpty(STACK *s) {
    return s->top == NULL;
}
void main() {
    STACK s;
    int i;
    initStack(&s);
    for (i = 1; i < 10; i++) {
        pushStack(&s, i);
    }
    while (!stackIsEmpty(&s)) {
        printf("%d\n", popStack(&s));
    }
}

Linked Queue

typedef struct items {
    int data;
    struct items *link; // points to next element
} ITEM;

typedef struct queue {
    int size;
    ITEM *front, *rear;
} QUEUE;

void initQueue(QUEUE *q) {
    q->size = 0;
    q->front = q->rear = NULL;
}
int queueIsEmpty(QUEUE *q) {
    return q->front == NULL;
}
int queueLength(QUEUE *q) {
    return q->size;
}
void addQueue(QUEUE *q, int y) {
    ITEM * x = (ITEM *) malloc(sizeof(ITEM));
    x->data = y;
	x->link = NULL;
    if (q->front == NULL)
        q->front = x;
    else
        q->rear->link = x;
    q->rear = x;
    q->size++;
}
int deleteQueue(QUEUE *q) {
    ITEM * x = q->front;
    int rel = x->data;
    q->front = x->link;
    if (q->front == NULL)
        q->rear = NULL;
    q->size--;
    free(x);
    return rel;
}
void main() {
    QUEUE q;
    int i;
    initQueue(&q);
    for (i = 1; i < 10; i++) {
        addQueue(&q, i);
    }
    while (!queueIsEmpty(&q)) {
        printf("%d\n", deleteQueue(&q));
    }
}

以下範例定義了矩陣結構,並透過動態空間分配的方式來做矩陣的加法和乘法

/**
 * Author: Shiuh-Sheng Yu
 * Department of Information  Management
 * National Chi Nan University
 * Subject: 矩陣相加與相乘
 * Toolkit: gcc
 * Modified Date:2002/08/20
 */
#include <stdio.h>
// 以巨集(macro)定義矩陣元素和動態分配空間的對應關係
// 所謂巨集指的是經由preprocessor(前置處理器)取代原始檔內的字串
#define M(x,i,j) *(x->data + i*x->col + j)

// 定義MATRIX為 struct matrix *
// 也就是說MATRIX之型態為 a pointer to struct matrix
// 至於struct則是C語言讓使用者 "自訂型態" 的關鍵字
typedef struct matrix {
    int row, col;
    double* data;
} *MATRIX;

/**
 * 由檔案讀入一個矩陣
 */
MATRIX readMatrix(FILE* f) {
    int x, y, i, j;
    char keyword[256];
    MATRIX m;
    /* read in keyword "matrix" */
    fscanf(f, "%255s", keyword);
    if (strcmp(keyword,"matrix")!=0) {
        printf("keyword error: %s",keyword);
        return NULL;
    }
    // 動態分配一塊struct matrix大小的空間
    m =  (MATRIX) malloc(sizeof(struct matrix));
    /* read in matrix dimension to x y */
    fscanf(f,"%d", &x);
    fscanf(f,"%d", &y);
    m->row = x;
    m->col = y;
    m->data = (double*)malloc(x * y * sizeof(double));
    /* read in x*y double and store them to m->data */
    for (i = 0; i < x; i++) {
        for (j = 0; j < y; j++) {
            fscanf(f,"%lf",m->data + i*y + j);
        }
    }
    return m;
}

/**
 * 印出矩陣的內容 
 */
void printMatrix(MATRIX x) {
    int i, j;
    for (i = 0; i < x->row; i++) {
        for ( j= 0; j < x->col; j++) {
            printf("%lf", M(x,i,j));
        }
        printf("\n");
    }
}
/**
 * 矩陣相加
 * 傳回一新矩陣為x,y之和
 */
MATRIX addMatrix(MATRIX x, MATRIX y) {
    int i, j;
    MATRIX m;
    // 檢查兩矩陣的大小是否能相加
    if ((x->row != y->row) || (x->col != y->col)) {
        printf("Matrix dimension mismatch.\n");
        return NULL;
    }
    // 產生新矩陣所需的記憶體空間
    m = (MATRIX) malloc(sizeof(struct matrix));
    m->row = x->row;
    m->col = x->col;
    //產生存放資料所需的空間
    m->data = (double*)malloc(m->row * m->col * sizeof(double));
    // 進行矩陣的加法運算
    for (i =  0; i < m->row; i++) {
        for (j =  0; j < m->col; j++) {
            M(m,i,j) =  M(x,i,j) + M(y,i,j); // 使用macro
        }
    }
    return m;
}
MATRIX multiplyMatrix(MATRIX x, MATRIX y) {
    /* 自己練習看看吧 */

}
/**
 * 將動態分配矩陣的空間還給系統
 */
void freeMatrix(MATRIX x) {
    free(x->data);
    free(x);
}

int main() {
    char buf[100];
    MATRIX a, b, c;
    // 持續讀入運算符號
    // stdin定義於stdio.h, 代表standard input. 在沒有透過作業系統重新指定
    // 的情形下, 一般為鍵盤
    for (; fscanf(stdin,"%99s",buf) != EOF;) {
        if (buf[0] == '+') {
            if ((a = readMatrix(stdin)) == NULL) {
                break; // 有錯誤則跳離開最接近的迴圈或switch敘述(此處為for迴圈)
            }
            printMatrix(a);
            if ((b = readMatrix(stdin)) == NULL) {
                break;
            }
            printf("+\n");
            printMatrix(b);
            printf("=\n");
            if ((c = addMatrix(a, b)) == NULL) {
                break;
            }
            printMatrix(c);
            printf("\n");
            freeMatrix(a); // 釋放動態分配的矩陣空間
            freeMatrix(b);
            freeMatrix(c);
        } else if (buf[0]=='*') {
            /* 練習看看吧 */
        } else {
            printf("Operator error\n");
            break;
        }
    }
}