2019q1 Homework1 (lab0)

# 2019q1 Homework1 (lab0) contributed by < `york56` > ###### tags: `System-Software-2019` `GUTS` ## Preparation ### Installation of Lubuntu 18.04 Done. Yet to documentate the installation process. ### Environment ``` $ uname -a # username, all Linux york-X450JF 4.15.0-45-generic #48-Ubuntu SMP Tue Jan 29 16:28:13 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux $ gcc --version gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0 ``` ### git, github(ssh key), commit message format Done. Done. Done. ### TODO: installation of input method for Mandarin ### TODO: WiFi driver and Bluetooth driver ### Study Linked lists https://people.engr.ncsu.edu/efg/210/s99/Notes/LinkedList.1.html * linked list a list consisting of items in which each item knows the location of the next item. * node(element) an item in a linked list. Each node contains a piece of list data and the location of the next node (item). * link (of a node) the location of the next node. * head node first node in a linked list * head pointer * points to the head node * The last node has a reference to **null**. * null meams: adj.無效的；無價值的；【數】零的 / **n.【數】零** / vt.使無效 ## Try to read queue.h I can't understand this: ```c= /* Linked list element (You shouldn't need to change this) */ typedef struct ELE { /* Pointer to array holding string. This array needs to be explicitly allocated and freed */ char *value; struct ELE *next; } list_ele_t; /* Queue structure */ typedef struct { list_ele_t *head; /* Linked list of elements */ /* You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail */ } queue_t; ``` ### Try to understand `type struct` Now I understood the it by this. [[C,C++] typedef struct 用法說明 - 李山姆的部落格 - 痞客邦](http://groangao.pixnet.net/blog/post/24474489-%5Bc%2Cc%2B%2B%5D-typedef-struct-%E7%94%A8%E6%B3%95%E8%AA%AA%E6%98%8E) ### Try to understand `char *value` Now I understood the it by this. [C語言: 超好懂的指標，初學者請進～](https://kopu.chat/2017/05/15/c%E8%AA%9E%E8%A8%80-%E8%B6%85%E5%A5%BD%E6%87%82%E7%9A%84%E6%8C%87%E6%A8%99%EF%BC%8C%E5%88%9D%E5%AD%B8%E8%80%85%E8%AB%8B%E9%80%B2%EF%BD%9E/) ### Try to understand 【`This array needs to be explicitly allocated and freed`】 #### Allocateed Being in a status where the memory for the datum is prepared. #### Being freed? ??? ??? ??? ??? ??? ### Try to interpret the fist few lines of `queue.h` ```c= /* This is a node/element inside a linked-list. */ struct ELE{ char *value; // Delare a pointer variable call 'value', which points to sth belonging to type-char struct ELE *next; // Delare a pointer variable call 'next', which points to sth belonging to ELE, a type-struct thing defined by us // It points toward the next element, not this node itself!!! }; typedef struct ELE list_ele_t; // Define the struct (called ELE) as a kind of type called "list_ele_t" /* A queue is a linked-list containing elements. */ typedef struct { list_ele_t *head; // head is a pointer pointing to sth belonging to list_ele_t } queue_t; ``` ### Why not use `list_ele_t` instead of `struct ELE` , since we have already typedefined it, resulting ```c= typedef struct ELE { char *value; list_ele_t *next; } list_ele_t; ``` . ### Why there is no need to write: ```c= typedef struct some_kind_of_name { bla bla bla } queue_t; ``` in the second part, but has the need to writ: ```c= typedef struct ELE { bla bla bla } list_ele_t; ``` in the first part. ## Try to complete the declare of queue structure According to Prof. Jserv, it is ```c= typedef struct { list_ele_t *head; // the head pointer list_ele_t *tail; // the tail pointer int size; } queue_t; ``` . I can't understand it. I thought a queue is something like: ![](https://i.imgur.com/pat4OPu.png =250x) . So it should be something like: ```c= typedef struct { list_ele_t{}; // as head list_ele_t{} // as body . . . list_ele_t{}; // as body list_ele_t{}; // as tail int size; } queue_t; ``` , but after reading https://www.interviewbit.com/courses/programming/topics/linked-lists/ ![](https://i.imgur.com/bISJNsl.png) I realize we merely have to hold two pointers in hands (one pointing to the beginning element and the other to the ending element), letting every element floating elsewhere. Also it seems like we have to calculate the size of the queue in advance and store it. ### How to get the nth node? If the queue_t data only has head pointer, tail pointer, and queue size, how to get the nth element? Count along the queue? ## Try to complete the function `q_new` It seems like ```c= queue_t *q_new(); ``` is enough to the task >Create empty queue. >Return NULL if could not allocate space. , but I don't know why. QwQ QwQ QwQ I interpret the code as: >define a pointer `q_new` pointing toward something of type-queue_t. > I thought we should declare a queue_t variable and let the pointer inside point to a null. ```c= queue_t an_empty_queue{ list_ele_t *head = &null; list_ele_t *tail = &null; int size = 0; } ``` ### Don't know how to let a pointer point to a null ## Try to complete the function `q_free` `void q_free(queue_t *q)` is enough?? ## Try to complete q_insert_head >Attempt to insert element at head of queue. >Return true if successful. >Return false if q is NULL or could not allocate space. >Argument s points to the string to be stored. >The function must explicitly allocate space and copy the string into it. I have no idea. I refer to < `DyclexiaS` >. https://hackmd.io/s/Byjnik5F7 The conditions causing failures include: 1. No queue, which means q (a pointer) is NULL. (??? Can an element have a NULL info part and a not-NULL link part?) 2. No new element. 3. ??? ```c= bool q_insert_head(queue_t *q, char *s) { if (q == NULL) return false; list_ele_t *newh; /* What should you do if the q is NULL? */ newh = malloc(sizeof(list_ele_t)); if (newh == NULL) return false; /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ newh->value = strdup(s); if (newh->value == NULL) { free(newh); return false; } if (q->head == NULL) q->tail = newh; newh->next = q->head; q->head = newh; ++q->q_size; return true; } ``` ### What is the 8th line `newh = malloc(sizeof(list_ele_t))` 去開記憶體，開給 list_ele_t 這種 datatype。然後把開出來的記憶體的address指派給newh 我不懂的的是我以為list_ele_t的大小是固定的，為什麼要一直重算？去要記憶體，如果發生`newh == NULL`，也就是要不到，就回傳false。 ```c= typedef struct ELE { char *value; struct ELE *next; } list_ele_t; ``` 而且我以為list_ele_t的宣告不論怎樣都會被執行，newh有機會是NULL嗎？ #### `sizeof()` This operator gives the byte size of the inputted operator. https://www.geeksforgeeks.org/sizeof-operator-c/ #### `malloc()` The C library function `void *malloc(size_t size)` allocates the requested memory and returns a pointer to it. https://en.cppreference.com/w/c/memory/malloc #### 動態配置 https://openhome.cc/Gossip/CGossip/MallocFree.html ### allocate space for the string and copy it ```c= /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ newh->value = strdup(s); // value是個pointer // char *value if (newh->value == NULL){ free(newh); return false; } if (q->head == NULL) q->tail = newh; newh->next = q->head; q->head = newh; ++q->q_size; return true; ``` 再造一個 pointer ( 其指向 s 這個 pointer 指向的 char ) 並 assign 給 value (其為 newh 這個 pointer 指向的 struct 裡面的 pointer )，但這個 assigning 也有可能失敗。(會什麼會失敗啊???) 失敗了的話就把 newh 清掉然後回傳 false 。 #### `->` ![](https://i.imgur.com/uksn8sE.png) http://squall.cs.ntou.edu.tw/cprog/content/12%20struct%20and%20other%20datatypes_bw.pdf #### `char * strdup(const char *str1);` Returns a pointer to a null-terminated byte string, which is a duplicate of the string pointed to by str1. The returned pointer must be passed to [free](https://en.cppreference.com/w/c/memory/free "c/memory/free") to avoid a memory leak. ##### `char * strdup(const char *str1);`的輸入如果是NULL會發生什麼？ ##### a null-terminated byte string In computer programming, a null-terminated string is a character string stored as an array containing the characters and terminated with a null character. https://en.wikipedia.org/wiki/Null-terminated_string ##### 什麼是 Memory Leak ? ??? #### `void free( void* ptr );` Deallocates the space previously allocated by [malloc()](https://en.cppreference.com/w/c/memory/malloc "c/memory/malloc"), [calloc()](https://en.cppreference.com/w/c/memory/calloc "c/memory/calloc"), aligned_alloc, (since C11) or [realloc()](https://en.cppreference.com/w/c/memory/realloc "c/memory/realloc"). If `ptr` is a null pointer, the function does nothing. ##### null pointer ??? ??? ### 檢查完各種例外，真的要把新的頭放進去了喔但如果放之前是空的，頭尾都要這個指向新加進去的元素。 ```c= if (q->head == NULL) q->tail = newh; ``` 如上，假如 head 裡面沒東西(所以是空的 queue )就讓把 newh 指派給 tail 。然後等一下把 newh 也指派給 head ，這樣頭尾都指向同一個 element ，所以就從空的長大成有一個元素的，合理。無論 head 是不是 NULL 我們都要做以下。 ```c= newh->next = q->head; q->head = newh; ++q->q_size; return true; ``` 讓 newh 的 next 指向原本的第一個 element ，也就是把 q 裡面的 head 指派給 newh (我們要加進去的 element 的 pointer ) 的 next 。我們都是靠 q 來知道頭尾在哪裡的，讓 q 的 head 指向整顆 newh 。把 q 裡面的 q_size 加一。這樣我們應該就完成了。 ### 但是回頭一看我又不懂了為什麼以下是分兩步 ```c list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); ``` 不是一步 ```c list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.