用 Link list 建造 Queue for C
===
工欲善其事,必先利其器,首先要有:
1. Pointer 指標的觀念
2. Struct 結構的觀念
3. Dynamic memory allocation 的使用
4. 用 link list 製作 queue
---
## 關於指標的使用
\*Q 在宣告中出現與程式碼中出現，有兩種不同的功能
在宣告時，用了 int \*Q 表示宣告指標變數
\*Q 從指標指向的位址內容，或是修改指標指向的記憶體位址的內容
Q 存放指向 mem 位址的數值
&Q Q 這個 mem 位址的數值
怎麼驗證記憶體位址，使用16進位的方式，進出變數內容，可以很明顯地看出差異
%x 資料以16進位的方式呈現
```clike=
int a;
int *x;
a = 15;
printf("&a %x x %x \n", &a, x);
x = &a;
*x = 11;
printf("&a %x a %d *x %d x %x &x %x", &a, a, *x, x, &x);
```
Output 的結果為
```
&a b4f80c54 x 0
&a b4f80c54 a 11 *x 11 x b4f80c54 &x b4f80c58
```
可以看出來 &a 印出的是 a 這個變數的記憶體位址，在程式中，把 a 的位址給了 x 指標，透過 \*x 更改指向的 mem 位址的內容，也就是對 a 的內容做修改。
更多的指標
char * 意思是指向的資料有正負號 8 bits 的 pointer
unsigned long * 無號 32 bits 的 pointer
void * 就是無型別
```
char *ptr8;
unsigned long *ptr32;
void *ptrx
ptr32 = ptr8; 這是type錯誤
ptrx = ptr8; 頂多是warning
*ptr8 = 100; 在ptr8指向的記憶體位址填入100得值
*ptrx = 100; error不知道指向的記憶體位址的目的地，空間有多大
```
---
## 關於結構的使用
使用的方法，格式是
```clike=
struct 結構名稱{
資料型態 資料變數名稱;
資料型態 資料變數名稱;
...
}
```
使用自己定義資料結構時，可以使用這種方式
```clike=
struct node Node1;
```
建立一個 link list ，我們需要內容跟連結，所以使用方法如下
```clike
struct node{
int val;
struct node *link
}
```
其中 \*link 的 `*` 不可省略。
原因是 `struct node link` 就變成遞迴定義，也就是自己呼叫自己這種結構，問題會發生在 compiler 無法判斷這個 `struct node` 會呼叫多少次，無從得知 `struct node` 的大小。
而我們可以使用 `.` 這種運算子，取出 struct 中的元素。延續上面的宣告，我們可以這樣建立對應的 struct 變數
```clike
struct node Node1, Node2, Node3;
Node1.val = 100;
Node2.val = 50;
Node1.link = &Node2;
Node2.link = &Node3;
```
依此類推，想透過 Node1 間接在 Node3 裡面存放資料
```clike
Node1.link.link.val = 500;
```
Node1 透過 link 連接到 Node2 ，再透過 Node2 的 link 連結到 Node3 ，再針對 Node3 中的 val 填值。
這樣使用會發生問題，因為 struct 的 `.` 運算，左邊必須是 struct ，不能是 pointer 。
所以要使用上面的存值方法，必須修改成這樣。
```clike
(* (* Node1.link).link).val = 500;
```
透過上面的使用， struct 裡面有 pointer to struct ，如果透過 pointer 的方式存取 struct 的成員，就必須對指標的觀念清楚，小心謹慎地使用 \* 和 () 來達成方法。
因為 struct 成員包含指向結構的指標(define a pointer to struct in a struct)，是一種很常見的事情，但是上面的使用方式，不方便也不直覺，所以C語言定義了 `->` 運算符號。 `->` 符號的左邊是一個 pointer to struct ，右邊是該 struct 中要使用的成員。當 struct 為透過指標存取結構時，必須使用 `->` 。
`->` 為第一優先權且為左結合，上面的例子可以變成這樣。
```clike
Node1.link->link->val = 500;
```
Typedef 的介紹
替一個已知的資料型態取另外的名稱(別名)，也就是 int 可以用 int32 來取代 int ，用 int32 來設定 int 的資料型態
```clike
typedef int int32;
int32 x = 3;
```
Typedef struct
```clike
typedef struct node{
float time;
struct node *link;
}Q_node;
```
可以拆解成兩部份
1. 建立 struct 為 node 這個資料結構
```clike
struct node{
float time;
struct node *link;
};
```
2. 替 struct node 這個資料結構取別一個新名字稱作 Q_node
```clike
typedef struct node Q_node;
```
使用別名同時又宣告該結構的變數供程式使用
```clike
typedef struct node{
float time;
struct node *link;
}Q_node, arrival_time;
```
實際上可分解成下面三個動作
```clike
typedef struct node{
float time;
struct node *link;
};
typedef struct node Q_node;
Q_node arrival_time;
```
延伸用法(少了 struct 的名稱)
```clike
typedef struct{
float time;
struct node *link;
}Q_node, arrival_time;
```
也就是宣告了一種結構他的變數名稱為 arrival_time ，而這種結構的別名是 Q_node
其運行的方式類似下面的方法
```clike
struct{ //實際程式中宣告 struct 沒有名稱會發生問題
float time;
struct node *link;
};
typedef struct node Q_node;
Q_node arrival_time;
```
在運行的過程中嘗試做鏈結串列會發生問題。
```clike=
Q_node *node1 = (Q_node *) malloc(sizeof(Q_node));
Q_node *node2 = (Q_node *) malloc(sizeof(Q_node));
node1->time = 5;
node1->link = node2;
```
會發生型態不相容的問題
Q_node* 無法對應到 struct 中的 struct node *
```clike=
typedef struct node{
float time;
struct node *link;
}Q_node;
```
需要給予 struct 名稱宣告鏈結時才能被對應。
---
## 動態記憶體分配
程式在執行時才獲得的記憶體空間，由於這種記憶體空間的配置方式使用 Heap(堆疊) 方式來達成，也有人將這塊記憶體空間稱謂 Heap ，在程式結束時，針對資料的釋放，採用後進先出的方式釋放資源。
首先程式要先告訴電腦需要多少空間， C 語言使用 malloc() ，實現動態記憶體分配。
有分配就會有歸還， C 語言使用 free() 歸還程式執行時， malloc() 所分配的記憶體空間。
void *malloc(size_t size);
void free(void *ptr);
實際使用的方法
```
資料結構 *指標;
指標 = (資料型態 *) malloc (所需要的記憶體空間，他的bytes數);
```
malloc() 成功時，會回傳的是 void * 所指向的記憶體位址，若失敗則會回傳 NULL 。
所以前面要有一個 Datatype * 去轉換成對應的指標型態，我們稱為轉型(casting or type casting)，將程式獲得的記憶體位址存入宣告的指標變數。
```clike=
Datatype *ptr;
ptr = (Datatype *) malloc (sizeof(指標資料結構的大小)*(空間大小));
```
```
free(void 釋放分配出去的記憶體空間，他對應的記憶體位址);
```
```clike=
free(ptr);
```
[更多 C memory alloction function 的介紹](https://openhome.cc/Gossip/CGossip/MallocFree.html)
在 C++ 裡面動態配置記憶體空間，則是使用 new 跟 delete
```
資料型態* 指標;
指標 = new 資料型態[所需要的記憶體空間，他的bytes數];
delete [] 指標;
```
```clike=
Datatype* ptr;
ptr = new Datatype[所需要的記憶體空間，他的bytes數];
delete [] ptr;
```
ex:
```clike=
User* userArray;
userArray = new User[5];
delete [] userArray;
```
[關於 C++ new 更多的介紹](http://www.cplusplus.com/reference/new/operator%20new[]/)
[關於 C++ delete 更多的介紹](http://www.cplusplus.com/reference/new/operator%20delete[]/)
---
## Linked list
建立 single linked list
```c=
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
產生 linked list
```c=
static node_t *list_make_node_t(node_t *list, int val) {
node_t *tmp = list;
node_t *n = malloc(sizeof(node_t));
n->value = val;
n->next = NULL;
if (!list)
return n;
while (tmp->next)
tmp = tmp->next;
tmp->next = n;
return list;
}
```
釋放 linked list
```c=
static void list_free(node_t **list) {
node_t *pNode;
while (*list) {
pNode = *list;
*list = ((*list)->next);
free(pNode);
}
}
```
將 node 加入 linked list 中
```c=
static inline void list_add_node_t(node_t **list, node_t *node_t) {
node_t->next = *list;
*list = node_t;
}
```
將兩個 linked list 合併
```c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next);
*left = right;
}
```
---
## 用簡單的 linked list 製造 FIFO queue
首先要有 linked list 的 struct
```clike=
typedef struct node{
float time;
struct node *link;
}Q_node;
```
接著宣告可以存放 node 的 queue
```clike=
typedef struct queue{
int size;
Q_node *head, *tail;
}Queue;
```
一開始一定要執行的初始化
```clike=
void initQueue(Queue *q){
q->size = 0;
q->head = q->tail = NULL;
}
```
判斷宣告出來的 queue 是否為不存在，或是確認資料沒有被放進 queue 裡面
```clike=
int queueIsEmpty(Queue *q){
return q->head == NULL;
}
```
將資料放入 node，將 node 加入 queue 中
```clike=
void addQueue(Queue *q, float arrival_time){
Q_node *temp = (Q_node *)malloc(sizeof(Q_node));
temp->time = arrival_time;
temp->link = NULL;
if(q->head == NULL)
q->head = temp;
else
q->tail->link = temp;
q->tail = temp;
q->size++;
}
```
取出 node 中的資料，並把該 node 從 queue 中移除
```clike=
float deleteQueue(Queue *q){
Q_node *temp = q->head;
float retval = temp->time;
q->head = (q->head)->link;
if(q->head == NULL)
q->tail = NULL;
q->size--;
free(temp);
return retval;
}
```
----
## 沒用的冷知識-指標宣告的表示方式
### Typical C programmer
**int \*p**
It explains "\*p is what is the int" emphasizing **syntax**.
ex.
int \*p1
It means "\*p1 is what is the int".
### Typical C++ programmer
**int\* p**
It explains "p is a pointer to an int" emphasizing **type**.
ex.
int\* p1
It means "p1 is a pointer points to an integer".
簡單的說：
int \*p; 表示 \*p 是一個 int。(C style)
int* p; 表示 p 是一個指向 int 的指標，p 的類型是 int*。(C++ style)
結論：不論你用 C 或 C++ 的方式宣告指標變數，編譯器都能看懂程式碼中的指標宣告，唯一的差別只是大部分人不會注意到的意義。
[參考來源](http://www.stroustrup.com/bs_faq2.html#whitespace)
---
###### tags: `C` `Queue`
Sign in with Wallet
Connect another wallet