雙向環狀鏈結串列教學[1]: 新增與印出

雙向環狀鏈結串列教學[2]: 插入節點

雙向環狀鏈結串列教學[3]: 刪除節點

完整程式碼

這裡呈現的程式碼與雙向環狀鏈結串列教學[3]: 刪除節點裡面的完整程式碼相同，此處提供github連結與github gitst連結以給讀者更方便觀看雙向環狀鏈結串列的程式碼

doubly_linked_list/doubly_circular_linked_list.c at main · RuoPuYang/doubly_linked_list

相關連結

• [資料結構] 雙向環狀鏈結串列教學[1]: 新增與印出
• [資料結構] 雙向環狀鏈結串列教學[2]: 插入節點
• [資料結構] 雙向環狀鏈結串列教學[3]: 刪除節點

完整程式碼

刪除結點的函數: delete_node

主函數

首先這邊，我們調用delete_node的函數，首先刪掉第一個結點

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);
    add_node(&head, 41);

    insert_node(&head, 45, 62);
    insert_node(&head, 5, 23);
    insert_node(&head, 128, 57);
    insert_node(&head, 41, 30);

    delete_node(&head, 5);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

在delete_node函數這邊，會先去檢查第一個結點是否就是要刪除的數值，如果是的話，這裡會先把*start設定給第一個結點的下一個結點

這邊之所以要特別把第一個結點的處理與其他結點的處理分開的原因是如果第一個結點被釋放掉的話，需要再特別記錄目前的第一個結點的位置是什麼，如此程式碼在調用head的時候，可以正確地指出目前第一個結點的位置為何

    if(value == current->data) {
        *start = current->next;
        do {
            current = current->next;
        }while(current->next !=ori_start);
        current->next = *start;
        (*start)->prev = current;
        free(ori_start);
        return;
    }

接下來確認要刪除的數值是第一個結點，也就是if(value == current->data)，這裡會先把*start，設定給current->next，也就是讓目前第一個結點的下一個結點，成為新的第一個結點

接著使用do-while的迴圈，走到最後一個結點，而這邊ori_start的設定就是第一個結點，所以確保current會停留在最後一個結點

這時候，由於*start已經是新的第一個結點了，將最後一個結點，也就是current的next，指向*start

current->next = *start;

而新的第一個結點*start的前一個結點，這時候會指向最後一個結點

(*start)->prev = current;

最後釋放舊的第一個結點，完成刪除第一個結點的動作

free(ori_start);

最後將示意圖變成更好讀的樣式

正向的執行結果

23 128 57 41 30 23

反向的執行結果

23 30 41 57 128 23

這個時候，如果在執行刪除第一個結點前後，印出第一個結點的位址

printf("Old first node address: %p\n", head);
delete_node(&head, 5);
printf("New first node address: %p\n", head);

可以看出head指向的位址的改變，注意這邊是使用筆者某一次的編譯結果，根據不同機器環境，不同次的執行結果，所被分配到記憶體位址的執行結果會不盡相同

Old first node address: 0x563ae72472a0
New node address: 0x563ae7247300

刪除數值為128的結點數值

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);
    add_node(&head, 41);

    insert_node(&head, 45, 62);
    insert_node(&head, 5, 23);
    insert_node(&head, 128, 57);
    insert_node(&head, 41, 30);

    delete_node(&head, 5);
    delete_node(&head, 128);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

這時候，在delete_node函數中，由於不是第一個結點，所以執行的程式部分為以下這個區塊

當current的next的數值，如果等同於要刪掉的數值，就會開始執行相關的程式碼

do {
    if(current->next->data == value) {
        temp = current->next;
        current->next = current->next->next;
        current->next->prev = current;
        free(temp);
        return;
    }
    current = current->next;
}while(current != *start);

首先current的下一個結點，會被設定給temp，接著current的下下一個結點，會變成current的下一個結點

current->next = current->next->next;

接著current下一個結點的前一個結點，會變成current，注意這邊由於上一個程式碼的影響，所以current的下一個結點已經變成了數值為57的結點

current->next->prev = current;

最後就是釋放掉欲刪除的結點

free(temp);

正向輸出結果

23 57 41 30 23

反向輸出結果

23 30 41 57 23

刪除數值為30的結點

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);
    add_node(&head, 41);

    insert_node(&head, 45, 62);
    insert_node(&head, 5, 23);
    insert_node(&head, 128, 57);
    insert_node(&head, 41, 30);

    delete_node(&head, 5);
    delete_node(&head, 128);
    delete_node(&head, 30);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

輸出結果

正向輸出結果

23 57 41 23

反向輸出結果

23 41 57 23

相關連結

• [資料結構] 雙向環狀鏈結串列教學[1]: 新增與印出
• [資料結構] 雙向環狀鏈結串列教學[2]: 插入節點
• [資料結構] 雙向環狀鏈結串列教學[4]: 完整程式碼

完整程式碼

插入結點的函數: insert_node

主函數

現在插入第一個結點，插在數值為45的結點之後

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);
    add_node(&head, 41);

    insert_node(&head, 45, 62);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

在insert_node中，如果找不到結點有這個數值，也就是if(insert_after_value == current->data)這個條件式不成立，那麼結點就會不斷的往下走一個，直到結點又走回第一個結點*start，就會離開迴圈

do {
    if(insert_after_value == current->data) {
        Node *new_node = (Node*)malloc(sizeof(Node));
        new_node->data = value;
        new_node->next = current->next;
        current->next->prev = new_node;
        current->next = new_node;
        new_node->prev = current;
        break;
    }
    current = current->next;
}while(current!=*start);

根據目前的鏈結串列，由於找不到數值為45的結點，所以這裡並不會插入數值為45的結點

新增數值為23的結點在數值為5的結點之後

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);
    add_node(&head, 41);

    insert_node(&head, 45, 62);
    insert_node(&head, 5, 23);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

現在新增一個數值為23的結點

Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;

接著目前結點的下一個結點，會變成新結點的下一個結點

new_node->next = current->next;

目前結點的下一個結點的前一個結點，會是新結點

current->next->prev = new_node;

目前結點的下一個結點，會是新結點

current->next = new_node;

新結點的前一個結點，會是目前的結點

new_node->prev = current;

重新整理成橫向的鏈結串列是意圖，整個串列的數值為5 23 128 41

執行結果

正向輸出

5 23 128 41 5

反向輸出

5 41 128 23 5

新增數值為57的結點在數值為128的結點之後

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);
    add_node(&head, 41);

    insert_node(&head, 45, 62);
    insert_node(&head, 5, 23);
    insert_node(&head, 128, 57);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

輸出結果

正向輸出

5 23 128 57 41 5

反向輸出

5 41 57 128 23 5

新增數值為30的結點在數值為41的結點之後

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);
    add_node(&head, 41);

    insert_node(&head, 45, 62);
    insert_node(&head, 5, 23);
    insert_node(&head, 128, 57);
    insert_node(&head, 41, 30);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

輸出結果

正向輸出

5 23 128 57 41 30 5

反向輸出

5 30 41 57 128 23 5

相關連結

• [資料結構] 雙向環狀鏈結串列教學[1]: 新增與印出
• [資料結構] 雙向環狀鏈結串列教學[3]: 刪除節點
• [資料結構] 雙向環狀鏈結串列教學[4]: 完整程式碼

完整程式碼

新增結點的函數: add_node

主函數

int main()
{
    Node *head = NULL;

    add_node(&head, 5);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

這裡我們先建立第一個結點，這是第一個結點，所以這個不管是往前指還是往後指，都會是自己，也就是new_node->next = new_node，new_node->prev = new_node，最後再去確認，如果是新增第一個結點，也就是*start還沒有被真正設定，就讓設定的new_node等同於*start

Node *new_node = (Node*)malloc(sizeof(Node));

new_node->data = value;
new_node->next = new_node;
new_node->prev = new_node;

if(*start == NULL) {
    *start = new_node;
    return;
}

這時候創造完第一個結點後，就可以印出來確認是否創造doubly circular linked list成功

印出串列數值的函數: print_list

這邊的print_list函數，會讓第一個node先印出數值，接著讓指向下一個node，然後進入迴圈，這個迴圈地跳出條件為當node為第一個node的時候就會跳出，要不然就會印出目前的訊息，然後再往下指，跳出後還會再印出目前結點的數值，其實就是要印出第一個結點的數值。

void print_list(Node *node)
{
    Node *first_node = node;
    printf("%d ", node->data);
    node = node->next;

    while(node != NULL) {
        if(node == first_node) break;
        printf("%d ", node->data);
        node = node->next;
    }
    printf("%d\n", node->data);
}

對於只有一個結點的情況，印出數值5之後，由於是第一個結點，所以在迴圈的判斷中就會跳出，跳出迴圈後，接著再印出第一個結點的數值5

輸出結果

5 5

反向印出串列數值的函數: inverse_print_list

其實調用的方法與print_list是一樣的，都是把第一個結點當作參數帶入到函數中，但是這邊將第一個結點命名為last_node，並且往前去走。這邊與print_list的方式一樣，先印出last_node的數值，接著將結點往前移，接著進入迴圈，如果是最後一個結點，就會跳出迴圈，如果不是的話，會印出結點內容，接著就會把結點往前移。

最後跳出迴圈的時候，會再印出最後一個結點的數值。

void inverse_print_list(Node *node)
{
    Node *last_node = node;
    printf("%d ", node->data);
    node = node->prev;

    while(node != NULL) {
        if(node == last_node) break;
        printf("%d ", node->data);
        node = node->prev;
    }
    printf("%d\n", node->data);
}

對於只有一個結點的情況，印出數值5之後，由於是最後一個結點，在迴圈的判斷中就會跳出，跳出迴圈後，會再印出最後一個結點的數值，其實數值就是5

5 5

現在我們新增第二個數值為128的結點

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

新增第二個數值為128的結點後，此時在add_node的函數裡，因為不是屬於第一個結點，所以會執行else裡面的程式碼。

在else裡面的程式碼，其實就是宣告一個current的指標，並將*start設定為current，接下來就開始迭代這個鏈結串列，最後當迴圈走回到第一個結點的時候，就跳出迴圈。

這樣的程式碼就代表，經過迴圈的迭代之後，current會留在第一個結點的前一個結點

void add_node(Node **start, int value)
{
    Node *new_node = (Node*)malloc(sizeof(Node));

    new_node->data = value;
    new_node->next = new_node;
    new_node->prev = new_node;

    if(*start == NULL) {
        *start = new_node;
        return;
    }
    else {
        Node *current;
        current = *start;
        while(current->next != *start) {
            current = current->next;
        }
        current->next = new_node;
        new_node->prev = current;
        new_node->next = *start;
        (*start)->prev = new_node;
    }
}

此時就開始執行添加結點的第一個程式碼，將目前結點的下一個結點，指向new_node

current->next = new_node;

接著將這個數值為128的結點，往前指向數值為5的解點

new_node->prev = current;

新結點的下一個結點，將會指向第一個結點

new_node->next = *start;

第一個結點的前一個結點，會指向新結點

(*start)->prev = new_node;

最後執行程式碼，不管是正向印出，還是反向印出，都可以得到相同的結果

正向印出

5 128 5

反向印出

5 128 5

新增第三個數值為41的結點

int main()
{
    Node *head = NULL;

    add_node(&head, 5);
    add_node(&head, 128);
    add_node(&head, 41);

    print_list(head);

    inverse_print_list(head);

    free_list(head);

    return 0;
}

新增完之後，doubly circular linked list的示意圖會如下

輸出結果為

正向印出

5 128 41 5

反向印出

5 41 128 5

釋放掉記憶體的函數: free_list

最後當所有鏈結串列都建置完成之後，就可以來釋放掉記憶體

這裡首先先設置一個total_node的變數，給予數值為1，接著開始使用迴圈迭代整個串列，以得到整個串列到底有多少結點

在確定有多少個結點之後，在這邊使用一個for迴圈，將current結點設定為第一個結點，並且讓current等同於temp，然後讓current變成下一個結點後，就釋放掉temp結點的記憶體，因為已經知道串列中到底有多少個結點，使用此方法讓迴圈整個走完之後，這樣就可以釋放掉整個雙向環狀鏈結串列的記憶體容量

void free_list(Node *node)
{
    int total_node = 1;
    Node *first = node;
    node = node->next;
    while(node != first) {
        node = node->next;
        total_node++;
    }

    Node *current = first;
    Node *temp;
    int i;

    for(i = 0; i < total_node; i++) {
        temp = current;
        current = current->next;
        free(temp);
    }
}

相關連結

• [資料結構] 雙向環狀鏈結串列教學[2]: 插入節點
• [資料結構] 雙向環狀鏈結串列教學[3]: 刪除節點
• [資料結構] 雙向環狀鏈結串列教學[4]: 完整程式碼

A ‘C’ Test: The 0x10 Best Questions for Would-be Embedded Programmers

中文參考網址

C語言測試 應知道的0x10個基本問題

預處理器(Proprocessor)

• 工程師應知道的0x10個問題(1): 用#defince定義一年的秒數
• 工程師應知道的0x10個問題(2): 用macro寫函數來比大小
• 工程師應知道的0x10個問題(3): #error指令的目的

無窮迴圈(Infinite Loops)

工程師應知道的0x10個問題(4): 無窮迴圈

資料宣告(Data declarations)

工程師應知道的0x10個問題(5): 資料宣告

Static

工程師應知道的0x10個問題(6): Static的用法

Const

工程師應知道的0x10個問題(7): Const的用法

Volatile

工程師應知道的0x10個問題(8): Volatile的用法

位元操作(Bit Manipulation)

工程師應知道的0x10個問題(9): Bit操作

存取固定的記憶體位置(Accessing fixed memory locations)

工程師應知道的0x10個問題(10): 存取固定的記憶體位置

中斷(Interrupts)

工程師應知道的0x10個問題(11): 中斷

程式範例(Code Examples)

• 工程師應知道的0x10個問題(12): 程式範例
• 工程師應知道的0x10個問題(13): 0的一補數

動態記憶體分配(Dynamic Memory Allocation)

工程師應知道的0x10個問題(14): 動態記憶體配置

Typedef

工程師應知道的0x10個問題(15): Typedef

混淆的語法(Obfuscated syntax)

工程師應知道的0x10個問題(16): a++的問題

A ‘C’ Test: The 0x10 Best Questions for Would-be Embedded Programmers

中文參考網址

C語言測試 應知道的0x10個基本問題

原文翻譯

16. C allows some appalling constructs. Is this construct legal, and if so what does this code do?

C語言允許一些可怕的結構。這個結構合法嗎? 如果合法的話這段程式碼會做什麼?

int a = 5, b = 7, c;

c = a+++b;

This question is intended to be a lighthearted end to the quiz, as, believe it or not, this is perfectly legal syntax. The question is how does the compiler treat it? Those poor compiler writers actually debated this issue, and came up with the “maximum munch” rule, which stipulates that the compiler should bite off as big a (legal) chunk as it can. Hence, this code is treated as:

這個問題是為這個測驗的一個愉快的結束。不管你相信或不相信，這是個完全的合法語法。這個問題是編譯器如何處理它? 那些不好的編譯器作者實際上爭論這個問題。根據 “maximum munch”規則，明確說明編譯器應該要盡可能地咬掉最大的一個(合法個)chunk。因此，這個程式碼要被處理為:

注1: 這裡的came up with the “maximum munch” rule，雖然come up with是提出的意思，中文來源這裡是翻成根據，這邊若翻成根據的話整體文義會順很多，所以這裡採用中文來源的譯法

注2: “maximum munch” rule，這裡在中文來源是翻成最處理原則，這邊如果用google搜尋的話，會出現Maximal munch的維基頁面，而google的機器翻譯是翻成最大匹配度

注3: which stipulates that the compiler should bite off as big a (legal) chunk as it can。這邊我直接直譯成譯器應該要盡可能地咬掉最大的一個(合法個)chunk，而中文來源是翻成: 編譯器應當能處理儘可能所有合法的用法。當然事實上這句話的意思有可能是偏盡可能處理的意味在。

對於這段文字如果讀者認為有更好的譯法的話，歡迎留言跟我說

c = a++ + b;

Thus, after this code is executed, a = 6, b = 7 & c = 12;

因此，在這個程式碼執行之後，a = 6, b = 7 & c = 12;

If you knew the answer, or guessed correctly — then well done. If you didn’t know the answer then I would not consider this to be a problem. I find the biggest benefit of this question is that it is very good for stimulating questions on coding styles, the value of code reviews and the benefits of using lint.

如果你知道這個答案，或者是猜對 — 那做得好。如果你不知道這個答案那麼我不會認為這是一個問題。我發現這個問題的最大益處是這是個非常好的激勵問題在於程式風格，程式碼審查的價值以及使用lint的益處。

注1: 文章的lint我想應該是指一種C語言的分析工具，以下文章有對這個工具的簡介
代码的 Lint 是什么意思

最後這段文字其實與這個問題無關，算是原作者對於這16個嵌入式工程師該應知道的問題所做的一個結尾

Well folks, there you have it. That was my version of the C test. I hope you had as much fun doing it as I had writing it. If you think the test is a good test, then by all means use it in your recruitment. Who knows, I may get lucky in a year or two and end up being on the receiving end of my own work.

好的大夥，你已經擁有它了。這是我的版本的C語言測試。我希望你當你在做的時候擁有跟我在寫的時候一樣多的樂趣。如果你認為這個測試是好的測試，那麼當然可以使用它在你的招聘。誰知道呢? 我可能會在一兩年內很幸運但最終我自己工作承受不愉快的事物

注: being on the receiving end有承受不愉快事物的意思，所以Who knows, I may get lucky in a year or two and end up being on the receiving end of my own work.這句話這裡我就翻成: 誰知道呢? 我可能會在一兩年內很幸運但最終我自己工作承受不愉快的事物。這裡我想作者在這裡表達的意思應是日無千日好，花無百日紅的感慨，畢竟專業能力是一部分，職場的問題又是另外一部份
這邊同樣的如果讀者認為有更好的譯法，歡迎留言跟我說

自我實作以及理解

注1: 以下是我的自我實作以及理解的部分，不保證正確而且很有可能描述不清楚或者是有錯誤，讀者若發現有可以更正的地方也歡迎留言告訴我

注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異

這裡我們照著原文宣告a = 6，b = 7，接著讓 c = a+++b。

這裡實際上 a會先與b相加，所以是5+7=12，c的數值是12，b的數值不會變是 7，a跟b加完之後，接著會a++，所以a變成6，其實a++就是後做，先運算完之後再++，所以才會5加完7之後，a自身才++變成6

輸出結果

a: 6, b: 7, c: 12

a++與++a

a++與++a是個經典的問題，如果我們去google的話大都是寫成i++與++的比較

以下有兩篇文章讀者可以參考

C 語言中的 i++ 與++i
What is the difference between ++i and i++?

這裡我們讓 c = a++的話，則c會等於5，接著a++再運算，a變成6

然後接著我們讓c = ++b，++b會先運算，所以b會等於8，而c當然接收8的數值，所以數值為8

輸出結果

a: 6, b: 7, c: 5
a: 6, b: 8, c: 8

接下來我們試試看 a++或++a這類的型態在printf的輸出強況

我們一開始先printf(“a: %d\n”, a++);，這時候a還沒有++，所以輸出的數值為5，接著我們再印一次，這時候a已經++過了，所以數值會變成6

而接著printf(“b: %d\n”, ++b);我們對++b的數值打印出來，這時候b已經++過了，所以數值為8，再印一次b，當然數值也是為8

輸出結果

a: 5
After a++, a: 6
b: 8
After ++b: 8

A ‘C’ Test: The 0x10 Best Questions for Would-be Embedded Programmers

中文參考網址

C語言測試 應知道的0x10個基本問題

原文翻譯

15. Typedef is frequently used in C to declare synonyms for pre-existing data types. It is also possible to use the preprocessor to do something similar. For instance, consider the following code fragment:

Typedef 頻繁的在C語言中使用來對之前存在的資料型態宣告為同義詞。這也是有可能的使用預處理器來做相似的事情。舉例來說，考慮下方的程式碼片段:

#define dPS struct s *

typedef struct s * tPS;

The intent in both cases is to define dPS and tPS to be pointers to structure s. Which method (if any) is preferred and why?

在這兩個案例的目的是去定義 dPS 與 tPS來當指向結構 s 的指標。哪個方法(如果有的話) 是比較偏向的並且解釋為什麼?

This is a very subtle question, and anyone that gets it right (for the right reason) is to be congratulated or condemned (“get a life“ springs to mind). The answer is the typedef is preferred. Consider the declarations:

這是一個非常微妙的問題，而且任何答對這題的人(要有正確的理由)是可以被恭喜或者是譴責(“找點有意思的事“浮現在腦中)。這個答案是 typedef 是比較好的。 思考下面的宣告:

注1: This is a very subtle question, and anyone that gets it right (for the right reason) is to be congratulated or condemned(“get a life“ springs to mind).，這裡的condemn單字有是譴責的意思，而後面的括號 get a life 有找點有意思的的意味，sprins to mind 用google翻譯有湧現到心中的意思。總體來說，在condemned後面加上括號(“get a life“ springs to mind)這裡我感覺作者有點開玩笑的意味在說不要太專注於這類的C語言語法。當然開玩笑歸開玩笑，這裡其實我無法得知這單純是一個開玩笑的語氣還是其實這也算是個有用的語法知識。這裡如果讀者有更好的譯法或者對作者這段話有更好的見解，歡迎留言告訴我。

dPS p1,p2;

tPS p3,p4;

The first expands to

第一個會被擴展成

struct s * p1, p2;

which defines p1 to be a pointer to the structure and p2 to be an actual structure, which is probably not what you wanted. The second example correctly defines p3 & p4 to be pointers.

定義 p1 會變成指向結構的指標而 p2 會變成一個真正的結構，變成可能不是你想要的。第二個範例正確的定義 p3 & p4 成為指標

自我實作以及理解

注1: 以下是我的自我實作以及理解的部分，不保證正確而且很有可能描述不清楚或者是有錯誤，讀者若發現有可以更正的地方也歡迎留言告訴我

注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異

這裡我們先宣告一個 struct s，裡面只有一個成員int a，接著我們也照原文中宣告#define dPS struct s * 與 typedef struct s * tPS;，並在主程式中用 struct s宣告了一個 s_data，並將成員 a 設為 5，接著我們也跟著原文一樣宣告了 dPS p1,p2; 與 tPS p3,p4;

我們來做第一個測試，我們讓p1與p2分別指向 s_data，p1 = &s_data;
p2 = &s_data;，然後編譯

編譯完之後我們發現出現錯誤

Embedded_system_0x10_issues_0x0f_1.c: In function ‘main’:
Embedded_system_0x10_issues_0x0f_1.c:21:10: error: incompatible types when assigning to type ‘struct s’ from type ‘struct s *’
   21 |     p2 = &s_data;
      |          ^

看來 p2 不是指標，接著我們對p2的成員a給予值，然後印出p1的a數值與p2的a數值

我們就可以發現輸出結果為p1的成員a為5，p2的成員a為10。所以當我們宣告成: dPS p1,p2，會如原文所說的擴展成這樣 struct s * p1, p2;，p1還是指標，而p2是一個結構變數

Value of a in p1: 5
Value of a in p2: 10

接著我們將 p3 與 p4 指向s_data，發現都能指成功

接著我們將p3與p4的成員a也都印出來，會發現都是5，tPS p3,p4;這樣宣告確實可以讓p3與p4都是指標

輸出結果

Value of a in p1: 5
Value of a in p2: 10
Value of a in p3: 5
Value of a in p4: 5

A ‘C’ Test: The 0x10 Best Questions for Would-be Embedded Programmers

中文參考網址

C語言測試 應知道的0x10個基本問題

原文翻譯

14. Although not as common as in non-embedded computers, embedded systems still do dynamically allocate memory from the heap. What are the problems with dynamic memory allocation in embedded systems?

雖然在非嵌入式系統上並不常見，嵌入式系統仍然在heap上做動態的配置記憶體。做動態記憶體配置在嵌入式系統上會有什麼問題?

Here, I expect the user to mention memory fragmentation, problems with garbage collection, variable execution time, etc. This topic has been covered extensively in ESP, mainly by Plauger. His explanations are far more insightful than anything I could offer here, so go and read those back issues! Having lulled the candidate into a sense of false security, I then offer up this tidbit:

這裡，我預期使用者描述到記憶體碎片，垃圾回收的問題，變數的執行時間等。這些議題已經被Plauger在ESP雜誌上廣泛的涉及。他的解釋遠是更深刻見解的遠超任何我在這裡可以提供的，所以去並且讀這些議題。緩和應試者進入一個虛假安全的感覺後，接著我會提供這個小題目

注:原文這邊:"I then offer up this tidbit"，因為tidbit有美味小吃或者是小片珍饈的意思，所以這邊我使用中文來源的譯法將tidbit翻成小題目

What does the following code fragment output and why?

以下的程式片段輸出是什麼並且為什麼這樣輸出?

char *ptr;

if ((ptr = (char *)malloc(0)) == NULL) {

puts(“Got a null pointer”);

}

else {

puts(“Got a valid pointer”);

}

This is a fun question. I stumbled across this only recently, when a colleague of mine inadvertently passed a value of 0 to malloc, and got back a valid pointer! After doing some digging, I discovered that the result of malloc(0) is implementation defined, so that the correct answer is ‘it depends’. I use this to start a discussion on what the interviewee thinks is the correct thing for malloc to do. Getting the right answer here is nowhere near as important as the way you approach the problem and the rationale for your decision.

這是個有趣的問題。我在最近偶然發現，當一個我的同事不慎的傳入0的數值進入malloc，然後得到一個有效的指標!在做了一些挖掘之後，我發現這個malloc(0)的結果是實作定義的，所以正確的答案是"要看情況"。我使用這個來開啟一個討論來看應試者怎麼思考malloc所做的正確的事情。這裡得到正確的答案並不比你靠近這個問題以及你決定的原理闡述重要。

注1:I discovered that the result of malloc(0) is implementation defined, so that the correct answer is ‘it depends’.
這裡implementation defined我覺得應該要譯成實作定義的，如果有讀者覺得有更好的譯法歡迎留言告訴我。另外後面的‘it depends’，我查了一下It depends這篇的解說，基本上是要看情況的意思，這裡其實我真的很不懂作者想表達的意思，如果有讀者理解這個作者想表達的意思，歡迎留言告訴我

自我實作以及理解

注1: 以下是我的自我實作以及理解的部分，不保證正確而且很有可能描述不清楚或者是有錯誤，讀者若發現有可以更正的地方也歡迎留言告訴我

注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異

我們照著原文刻出以下的程式碼

輸出結果為確實可以拿到有效的指標

Got a valid pointer

網路上搜尋malloc(0)可以得到不同的討論文章，由於我對這方面真的不了解所以我大約找了三個連結，有興趣的讀者也可以搜尋看看各種不同的答案

以下兩個是用VC的，不是GCC，不過或許兩者的編譯器在處理這個問題上可能有相近之處
1) C語言中關於malloc（0）問題
2) ptr = (char *)malloc(0)
這一篇stack overflow就是純討論，似乎沒有限定在哪一個編譯器
3) What's the point of malloc(0)?

A ‘C’ Test: The 0x10 Best Questions for Would-be Embedded Programmers

中文參考網址

C語言測試 應知道的0x10個基本問題

原文翻譯

13. Comment on the following code fragment?

評論以下的程式碼片段?

unsigned int zero = 0;

unsigned int compzero = 0xFFFF; /*1’s complement of zero */

On machines where an int is not 16 bits, this will be incorrect. It should be coded:

當一個機器不是16位元的，這個會導致錯誤。它應該被寫成這樣:

unsigned int compzero = ~0;

This question really gets to whether the candidate understands the importance of word length on a computer. In my experience, good embedded programmers are critically aware of the underlying hardware and its limitations, whereas computer programmers tend to dismiss the hardware as a necessary annoyance.

這個問題真的可以知道應試者是否了解字組長度在電腦的重要性。在我的經驗中，好的嵌入式程式設計師會嚴謹的知道硬體的細節與它的限制，然後電腦程式設計師傾向忽視硬體並把它視為一個必要的煩擾。

注1: 這裡的the underlying hardware我覺得中文來源翻得蠻好的，因為underlying本身有基本的與潛在的意思在，中文來源翻成硬體的細節我覺得是個好的翻法故在此採用

注2: dismiss the hardware as a necessary annoyance這裡中文來源翻成"然而PC機程式往往把硬體作為一個無法避免的煩惱"，但是dismiss本身有忽視的意思在，所以我這邊會傾向翻成忽視硬體並把硬體視為一個必要的煩惱，這裡如果讀者覺得有更好的譯法，歡迎再留言跟我說

By this stage, candidates are either completely demoralized — or they are on a roll and having a good time. If it is obvious that the candidate isn’t very good, then the test is terminated at this point. However, if the candidate is doing well, then I throw in these supplemental questions. These questions are hard, and I expect that only the very best candidates will do well on them. In posing these questions, I’m looking more at the way the candidate tackles the problems, rather than the answers. Anyway, have fun…

到了這個階段，應試者會完全的沮喪我或者是連連獲勝以及有個好時光。如果明顯的應試者不是非常好，那麼這個測驗將在這裡結束。然而，如果應試者做得好，那麼我將丟出這些追加的問題。這些問題算難，而且我預期只有非常好的應試者會做好它們。提出這些問題後，我更側重的是應試者處理這些問題，而不是答案。不管怎樣，玩得開心…

自我實作以及理解

注1: 以下是我的自我實作以及理解的部分，不保證正確而且很有可能描述不清楚或者是有錯誤，讀者若發現有可以更正的地方也歡迎留言告訴我

注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異

原文中compzero被設為0xFFFF，但是事實上機器有可能不是16位元

unsigned int compzero = 0xFFFF;

像我這邊用的是64位元系統，int為32位元，我們用以下程式碼執行過後可以發現

輸出結果我們可以看到在Ubuntu 64位元的系統上，我們可以發現0的一補數其實是0xffffffff，而不是0xfffff，所以要得到正確的一補數，用~0是個安全的做法

copmzero: ffff
compzero_with_tilde: ffffffff

A ‘C’ Test: The 0x10 Best Questions for Would-be Embedded Programmers

中文參考網址

C語言測試 應知道的0x10個基本問題

原文翻譯

12. What does the following code output and why?

你認為下方的程式碼將會輸出什麼並且為什麼會這樣輸出?

void foo(void)

{

unsigned int a = 6;

int b = -20;

(a+b > 6) ? puts(“> 6”) : puts(“<= 6”);

}

This question tests whether you understand the integer promotion rules in C — an area that I find is very poorly understood by many developers. Anyway, the answer is that this outputs “> 6”. The reason for this is that expressions involving signed and unsigned types have all operands promoted to unsigned types. Thus –20 becomes a very large positive integer and the expression evaluates to greater than 6. This is a very important point in embedded systems where unsigned data types should be used frequently (see reference 2). If you get this one wrong, then you are perilously close to not being hired.

這個問題測試你是否了C語言的解整型提升規則 — 一個我發覺很多開發者都不太了解的領域。不管怎樣，這個答案會輸出“> 6”。這個原因是因為這個有著singed與unsinged型態的表達式所有的運算元被提升為unsigned型態。因此–20變成了一個非常大的正整數並且這個表達式計算出大於6。這是個在嵌入式系統非常重要的點因為unsigned的資料型態應該會被頻繁的使用(看參考2)。如果你答錯了這一題，那麼你已經危險的靠近無法聘僱的邊緣。

注1: integer promotion可以參考以下的維基頁面
整型提升
注2: Reference 2在英文來源裡是以下這個
2. Efficient C Code for Eight-Bit MCUs. ESP November 1988

自我實作以及理解

注1: 以下是我的自我實作以及理解的部分，不保證正確而且很有可能描述不清楚或者是有錯誤，讀者若發現有可以更正的地方也歡迎留言告訴我注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異

注2: 以下皆簡單的使用Ubuntu 20.04虛擬機做測試，並非真實的嵌入式系統，所以Ubuntu 20.04出來的成果可能會與嵌入式系統上的有差異

這裡我們直接照著原文來看結果會是怎樣，是否都被提升為unsigned int

輸出結果真 > 6，所以確實都被提升為正整數

> 6

我們再多測一個項目，這裡我們將a改為整數，設成20，將b改成unsigned int，設成-30

輸出結果為 > 20，代表確實都被設為正整數

> 20