C語言 資料結構DataStructure

以struct作為存資料的節點，以指標作為資料的連結

由於無法預期資料數，因此需透過malloc向系統要求記憶體空間。不用之後可透過free返還記憶體。使用malloc/free需引用 <stdlib.h>

函式原型
void *malloc(size_t size);
void free(void *ptr);

malloc 參數size代表要求的記憶體大小，回傳值為要到的記憶體位址，如果無法得到的記憶體會回傳NULL。

每次呼叫malloc後應該檢查回傳值是否為NULL

一個結構節點如何取得記憶體
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node)); //取一塊與struct相同size的記憶體，將其由void*，轉型為struct node *，透過ptr指標來操作節點。

17.2 assert
assert是一個函式，後面接一個條件，若條件不為真，程式就會停止執行。使用assert需要include <assert.h>

17.3 鏈結序列
利用struct宣告鏈結序列中的節點，節點包含兩部分，一個欄位儲存資料，一個欄位儲存鏈結序列中的下一個節點位置。方法如下，
struct listnode{
int data; //節點資料
struct listnode *next; //指向下一個節點
};

連結的第一個節點稱為head，鏈結最後一個節點的next指向NULL，表示鏈結序列的結束。


逐一檢視鏈結序列的節點(遍歷 traverse)
ptr = head;
while(ptr != NULL){
process *ptr;
ptr = ptr->next;
}

or


for(ptr = head; ptr != NULL; ptr = ptr->next)
process *ptr;


保留上一個節點作法
ptr = head;
while(ptr != NULL){
process *ptr;
previous = ptr; //先利用previous紀錄節點位置
ptr = ptr->next; //將節點指向下一個

}


把新節點加到兩個舊節點的方法
current->next = last->next;
last->next= current;


17.3.2 遞迴處理

鏈結序列可用遞迴定義
NULL是鏈結序列
一個節點加上該節點指向的鏈結序列，也是鏈結序列



17.4 二元樹
一個節點有兩個指標，分別指向兩個節點
NULL是二元樹
一個節點加上該節點指向的左二元樹及右二元樹，也是一個二元樹

17.4.1 節點
如何宣告一個二元樹中的節點?
struct treenode{
int data;
struct treenode *left;
struct treenode *right;
};

typedef struct treenode Treenode;

17.4.2 二元搜尋樹
定義
NULL是一個二元樹
一個節點如果
左右子樹都是二元搜尋樹
所有左子樹節點的資料都不大於該節點的資料
所有右子樹節點的資料都不小於該節點的資料
那麼這個節點加上左右子樹也是一個二元搜尋樹


17.4.3 二元樹遍歷
前序 preoder  根, 左子樹, 右子樹
中序 inorder 左子樹, 根, 右子樹
後序 postorder 左子樹, 右子樹, 根