# 2020q3 Homework1 (lab0)
contributed by < `ptzling310` >
## Struct at queue.h
### list_ele_t
定義一個 structure: list_ele_t 為 Link-list
含有
1. vlaue: 指向某個 char 的 pointer
2. next: 指向某個 struct ELE(list_ele_t) 的 pointer
```c=
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
```
```graphviz
digraph structs {
node [shape=record];
struct1 [label="{ list_ele_t |{ <value>value | <next>next }}"];
NULL1[label="...",shape=plaintext]
NULL2[label="...",shape=plaintext]
struct1:value -> NULL1
struct1:next -> NULL2
}
```
### queue_t
Queue的結構
含有
1. head: 指向某個 list_ele_t 的 pointer, 為 queue 之第一個 list
2. tail: 指向某個 list_ele_t 的 pointer, 為 queue 之最後一個 list
3. size: 紀錄 queue 有的 list 數量
```c=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
```graphviz
digraph structs {
node [shape=record];
struct3 [label="{ queue_t |{ <head>value | size | <tail>tail }}"];
NULL1[label="...",shape=plaintext]
NULL2[label="...",shape=plaintext]
struct3:head -> NULL1
struct3:tail -> NULL2
}
```
## Function at queue.c
### *q_new()
去建立一個 empty 的 queue
若有空間 --> 回傳位址
無空間 --> 回傳 NULL
```c=
queue_t *q_new()
{
//配置一個空間,該空間 address 紀錄在 q
queue_t *q = malloc(sizeof(queue_t));
//無法配置空間
if(!q){
return NULL;
}
//設定該 queue 之資料
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_insert_head
在queue的尾插入一個char
插入成功-->回傳true
插入失敗--> 表示queue為NULL,回傳flase
```c=
bool q_insert_head(queue_t *q, char *s)
{
//queue:NULL
if(!q)
return false;
//queue: 有東西
//*newh: 指向新增的 list_ele_t
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
//確定 malloc 成功
if(!newh)
return false;
//把資料放入list
newh->next = NULL;
//s: 存要希望存入的 value 的位址,造再給這些 char 一個空間,再連到存到 value
//而為了儲存長度 l 的字串，需要至少 l + 1 個 char 元素，並在最後設定為 \0 字元
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if(!newh->value){
free(newh);
return false;
}
memset(newh->value,'\0',strlen(s)+1);
strncpy(newh->value,s,strlen(s));
//把list放入queue的head
//設定head
newh->next = q->head;
q->head = newh;
//若插入的是第一個list,則設定tail
if(!q->tail){
q->tail = newh;
q->head = newh;
} else{
q->tail->next=newh;
q->tail=newh;
}
// 更新q->size
q->size+=1;
return true;
}
```
### q_insert_tail
在 queue 的尾插入一個 lsit
插入成功-->回傳 true
插入失敗--> 表示 queue 為 NULL, 回傳 flase
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if(!q)
return false;
//新增一個 list
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if(!newh)
return false;
//設定 struct 內所需之值
newh->next=NULL;
newh->value = malloc(sizeof(char)*strlen(s)+1);
if(!newh->vlaue){
free(newh);
return false;
}
memset(newh->value,'\0',strlen(s)+1);
strncpy(newh->value,s,strlen(s));
//insert
if(!q->tail){
q->head = newh;
q->tail = newh;
} else{
q->tail->next = newh;
q->tail = newh;
}
q->size +=1;
return true;
}
```
### q_remove_head
在佇列開頭 (head) 移除 (remove) 給定的元素。
移除成功-->回傳true
移除失敗-->表示 queue 為 NULL 或 empty ,回傳 flase
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
//不用 remove head 的情況
if(!q || !q->head)
return false;
list_ele_t *tmp; //要記得free
tmp = q->head;
q->head = q->head->next;
if(sp!=NULL){
memset(sp,0,bufsize);
if(tmp->value){
strncpy(sp,tmp->value,bufsize-1);
}
}
free(tmp->value);
free(tmp);
q->size -= 1;
return true;
}
```
### list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
```c=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
//do not need to merge
if(!l1)
return l2;
if(!l2)
return l1;
//head指向依 NULL
list_ele_t *head = NULL;
//tmp指向一 pointer: head, 並且記錄 head 的 addre
list_ele_t **tmp = &head;
while(l1 && l2){
if(strcmp(l1->value,l2->value) < 0){ //l1<l2
//將l1指派給tmp,所以tmp會存l1的位址
*tmp = l1;
l1 = l1->next;
} else{
*tmp* = l2;
l2 = l2->next;
}
tmp = &((*tmp)->next);
}
if(l1)
*tmp = l1;
if(l2)
*tmp =l2;
return head;
}
```
### list_ele_t *merge_sort(list_ele_t *head)
```c=
list_ele_t *merge_sor(list_ele_t *head)
{
//do not need to sort
if(!head || !head->next){
return head;
}
//split
list_ele_t *h1 = head;
list_ele_t *h2 = head->next;
while(h2 && h2->next){
h1 = h1->next;
h2 = h2->next->next;
}
h2 = h1->next;
h1->next = NULL;
h1 = head;
//sort each list
lsit_ele_t *list1 = merge_sort(h1);
list_ele_t *list2 = merge_sort(h2);
//merge two list into one
return merge(list1,list2);
}
```
### void q_sort(queue_t *q*)
```c=
void q_sort(queue_t *q*)
{
//q不存在或沒有指向的list, 則不用排序
if(!q || !q->head){
return;
}
//把queue所指的list丟去排序
q->head = merge_sort(q->head);
//排序完成,要再更新q->tail
while(q->tail->next){
q->tail=q->tail->next;
}
}
```
:::danger
思考： merge_sort 的成本高，如果 linked list 的 element 若數量不多，是不是就不要採用 merge_sort
:::
## 語法
### strcmp()
- 目的:
在 `q_sort()` 中,要求list依遞增方式排序, 又所存之值為string, 而非int, 所以須利用此語法達成字串排序
- 說明:
```c
int strcmp(const char *str1, const char *str2)
```
str1: 指向第一個要比較的字串
str2: 指向第二個要比較的字串
- 字串的大小
依照 ASCII 來比較大小
- 返回值
str1 > str2 : return value > 0
str1 = str2 : return value = 0
str1 < str2 : return value < 0
- 舉例
```c=
#include <stdio.h>
#include <string.h>
int main ()
{
char str1[15];
char str2[15];
int return_value;
strcpy(str1, "abcdef");
strcpy(str2, "ABCDEF");
return_value = strcmp(str1, str2);
if(return_value > 0)
{
printf("str1 is less than str2");
}
else if(return_value < 0)
{
printf("str2 is less than str1");
}
else
{
printf("str1 is equal to str2");
}
return(0);
}
```
結果
```
str1 is less than str2
```
- 參考來源
[strcmp() - C語言庫函數](http://tw.gitbook.net/c_standard_library/c_function_strcmp.html)
### strcpy()、strncpy()：字串複製
- 目的：為了在 insert 以及 remove 中處理要插入(或移除)的字串，需要先配置額外空間，將字串複製到新創造出的空間上。
- 說明:
```c
char *strcpy( char *dest, const char *src );
char *strncpy( char *dest, const char *src, size_t count );
```
src：字串來源
dest：將來源自串複製到此
- 舉例_strcpy()
```c=
#include <stdio.h>
#include <string.h>
int main()
{
char src[40];
char dest[100];
//先把dest先都填入'\0'
memset(dest, '\0', sizeof(dest));
//將"This is gitbook.net"複製到src
strcpy(src, "This is gitbook.net");
//將src複製到dest
strcpy(dest, src);
printf("Final copied string : %s", dest);
return(0);
}
```
結果
```
Final copied string : This is gitbook.net
```
- 舉例_strncpy()
```c=
char src[40];
char dest[12];
//把dest 都先填入\0
memset(dest, '\0', sizeof(dest));
//將字串複製到src內
strcpy(src, "This is tutorialspoint.com");
//複製src的前10個字元到dest
strncpy(dest, src, 10);
printf("Final copied string : %s\n", dest);
```
結果
```
Final copied string : This is tu
```
- 討論
1. 使用 `strcpy()` ，是依據 `/0` 作為結束的判斷，並且 `/0` 也會被複製。
2. 使用 `strcpy()` 可能會有 buffer overflow的問題，也就是 scr 複製到 dest 的長度太長。所以 dest 會占用到別的變數的記憶體空間、回傳 Segmentation Violation。 所以利用 `strncpy()` 來控制要複製幾個字元。
3. 若 `len(src) < n` (例：8 < 10)，則會把不足的地方補上 `/0` ；若`len(src) > n` 則==不會==補 `/0` ，必須自己補上！ 所以大多都再 `strncpy()` 前先把 dest 的值全部填 `/0` 。
### 問題
1. strcpy()與```'\0'```的關係
2. 每次 alloc 一個 struct 後,都對結構內所有資料設值(容易忘記把 next 設 NULL --> 錯誤迴圈)
3. 字串比大小
### 時間表
用來記錄做事進度
- [x] 2020/9/13：完成q_new, q_free_, q_size
- [x] 2020/9/14：完成 q_insert_head, q_insert_tail, q_remove_head, q_reverse
- [x] 2020/9/16：完成q_sort~~並修改註解~~
- [x] 2020/9/17：完成 lab0 中所用之語法、程式註解
- [ ] 2020/9：Valgrind記憶體分析
- [ ] 2020/9：Dude, is my code constant time?
:::danger
因為之前沒有看懂 github 上對於 commit 的要求，所以變成再完成作業後才一次將 code 更新到github 上...
:::
:::info
(☍﹏⁰。) 覺得這個自己寫的不太好，之後補上詳細解釋，以免自己以後回來看某些地方又看不懂
:::
:::info
commit 寫錯的話
$ git commit --amend
commit 中要告知 function 時的用途、連帶影響的 function
也可以加上 TODO
:::
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet