無病呻吟~~: [C&C++ NOTE][轉] Structure 結構

本文 http://pydoing.blogspot.com/2010/06/c-structure.html

C 語言中的結構為異質的資料結構，這意思是說結構中可以存放不同資料型態的資料體，每個資料體被稱為結構的成員，定義格式如下

宣告定義關鍵字 struct ，接著是結構名稱，然後用大括弧圍起來的成員宣告，須留意結構定義完的右大括弧其後要接分號 ; 。

跟結構有關的運算子如下表

結構成員運算子	.
結構指標運算子	->

宣告為某結構的變數就可以用結構成員運算子存取該成員，而結構指標運算子可以讓指向某結構的指標變數存取其成員，如下例

#include <stdio.h>
 
struct point {
    int x;
    int y;
};
 
int main(void)
{
    struct point a;
    struct point *aPtr = &a;
     
    a.x = 3;
    a.y = 4;
     
    printf("a = (%d, %d)\n", a.x, a.y);  
    printf("*aPtr = (%d, %d)\n", aPtr->x, aPtr->y);
 
    return 0;
}
 
/* 《程式語言：教學誌》的範例程式
    http://pydoing.blogspot.com/
    檔名：structopt.<b style="color:black;background-color:#ffff66">c</b>
    功 能：示範<b  style="color:black;background-color:#a0ffff">結構</b>定義、宣告及<b  style="color:black;background-color:#a0ffff">結構</b>運算子的使用
    作者：張凱慶
    時間：西元2010年4月 */

編譯後執行，如下

第 10 行

10	`struct` `point a;`

宣告變數 a 為 point 結構的變數，第 11 行

11	`struct` `point *aPtr = &a;`

宣告並設定 aPtr 為指向變數 a 的指標，接著第 13 及 14 行

a.x = 3;
a.y = 4;

便是利用結構成員運算子指派初值給變數 a ，最後第 16 及 17 行

printf("a = (%d, %d)\n", a.x, a.y);  
printf("*aPtr = (%d, %d)\n", aPtr->x, aPtr->y);

分別用結構成員運算子及結構指標運算子取出 a 的值並印在螢幕上。

第 13 及 14 行替結構設值可以用以下

13	`struct` `point a = {3, 4};`

來替代，利用大括弧指派初值，大括弧內依序是各個結構成員。

利用關鍵字 typedef 可以替結構建立新型態名稱

#include <stdio.h>
 
struct point {
    int x;
    int y;
};
 
typedef struct point Point;
 
int main(void)
{
    Point a = {3, 4};
     
    printf("a = (%d, %d)\n", a.x, a.y);  
 
    return 0;
}
 
/* 《程式語言：教學誌》的範例程式
    http://pydoing.blogspot.com/
    檔名：structtypedef.<b style="color:black;background-color:#ffff66">c</b>
    功能：示範利用 typedef 建立新型態名稱
    作者：張凱慶
    時間：西元2010年4月 */

編譯後執行，如下

第 8 行

8	`typedef` `struct` `point Point;`

替結構 point 建立 Point 型態名稱，因此往後可以直接使用 Point ，無須 struct point 兩字連用。

typedef 也可以直接寫進結構定義中，第 3 到 8 行可用以下寫法代替

typedef struct point {
    int x;
    int y;
} Point;

結構中的成員也可以是結構，例如

#include <stdio.h>
 
typedef struct point {
    int x;
    int y;
} Point;
 
typedef struct line {
    Point start;
    Point end;
} Line;
 
int main(void)
{
    Line a = {3, 4, 5, 6};
     
    printf("start = (%d, %d)\n", a.start.x, a.start.y);  
    printf("end = (%d, %d)\n", a.end.x, a.end.y);
 
    return 0;
}
 
/* 《程式語言：教學誌》的範例程式
    http://pydoing.blogspot.com/
    檔名：structstruct.<b style="color:black;background-color:#ffff66">c</b>
    功 能：示範在<b  style="color:black;background-color:#a0ffff">結構</b>中使用其他<b  style="color:black;background-color:#a0ffff">結構</b>當作成員
    作者：張凱慶
    時間：西元2010年4月 */

編譯後執行，如下

自我參考的結構

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

如下例定義了一個結構 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://pydoing.blogspot.com/
    檔名：structlist.c
    功能：示範自我參考的結構
    作者：張凱慶
    時間：西元2010年4月 */

編譯後執行，結果如下

第 12 行

12	`List a, b, c, *startPtr;`

我們分別宣告了三個 List 型態的結構，另外一個指向 List 型態的指標。

接下來從第 14 行到第 16 行

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

各自替三個 List 型態結構的成員 name 給值，然後第 18 行

18	`startPtr = &a;`

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

List 型態結構的另一個成員 nextPtr ，便是指向下一筆資料項目的位址。第 19 到第 21 行

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

此例中，我們把 a 當成第一筆資料，也就是資料結構的起始項目， b 是第二筆資料， c 為第三筆資料，因此 a 的 nextPtr 指向 b 的位址，而 b 的 nextPtr 指向 c 。由於 c 為最後一筆資料，我們將 c 的 nextPtr 設為 NULL ， NULL 是 C 語言標準函數庫所定義的一個特別的值，代表無效的指標。

第 23 到第 26 行

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

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

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

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

本文 http://programming.im.ncnu.edu.tw/Chapter13.htm

說明：

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

無病呻吟~~

2011年9月11日星期日

[C&C++ NOTE][轉] Structure 結構

自我參考的結構

用於struct的運算符號

動態空間分配

沒有留言:

張貼留言

2011年9月11日 星期日

[C&C++ NOTE][轉] Structure 結構

自我參考的結構

用於struct的運算符號

動態空間分配

沒有留言:

張貼留言

2011年9月11日星期日