2021q1 Homework1 (quiz1)

contributed by < JimmyZhan070100 >

tags: `linux2021`

2021q1 第 1 週測驗題

作業要求

1.解釋程式運作原理，搭配 Graphviz，比照 Linked List 練習題在 HackMD 筆記上視覺化展現;
- 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator
2.參考 Optimized QuickSort — C Implementation (Non-Recursive) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
3.Linux 核心內部也有 linked list 實作，但是 circulr doubly-linked list，linux-list 仿效 Linux 核心的實作並予以簡化，在 examples/ 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
- 參考資料: The Linux Kernel API - List Management Functions
4.研讀 Ching-Kuang Shene (冼鏡光] 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) CCC 的程式碼中

重要觀念：指標的指標











void remove_list_node(List *list, Node *target)
{
    // The "indirect" pointer points to the *address*
    // of the thing we'll update.
    Node **indirect = &list->head;
    // Walk the list, looking for the thing that 
    // points to the node we want to remove.
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

此處引述你所不知道的C語言: linked list 和非連續記憶體操作
- 透過 **indirect 取得 list->head 的 address 後，便可以快速對 target 進行刪除

註：此段程式並沒有將 target 的記憶體釋放，僅有將它不再串接

解釋：指標的指標顧名思義即為「指向指標的指標」，跟一般的指標一樣都是指向某個數值



int a = 1;
int *ptr = &a;    // 代表 ptr 指向 變數 a 的位址(位址仍是一個數值） 
int **ptr_to_ptr = &ptr;    // 代表 ptr_to_ptr 指向 變數 ptr的位址

第一周 Quiz

Quiz 答案

LLL = (c), left = &((*left)->next)
AAA = (e), &right
BBB = (c), &left
CCC = (b), list_concat(&result, pivot); list_concat(&result, right)

程式運作原理

首先這是一個單向的 linked list ，因為它只有一個 next pointer




typedef struct __node{
    int value;
    struct __node *next;
} node_t;

由於 Quiz 缺少 list_make_node_t 和 list_free(&list) 的實做，在此補上



















node_t *list_make_node_t(node_t *list, int data){
    node_t *temp = malloc(sizeof(node_t));
    if(!temp){
        return list;
    }
    temp->value = data;
    temp->next = list;
    return temp;
}

void list_free(node_t **list){
    node_t *temp;
    while (*list)
    {
        temp = *list;
        *list = (*list)->next;
        free(temp);
    }
}

`list_add_node_t`




void list_add_node_t(node_t **list, node_t *node_t){
    node_t->next = *list;
    *list = node_t;
}

將 list 接在 node_t 的後方，再將 node_t 更新成新的 list head

list_concat







void list_concat(node_t **left, node_t *right){
    while (*left)
    {
        left = &((*left)->next);    
    }
    *left = right;
}

在迴圈內不斷尋訪下一個節點直到找到 NULL 後跳出迴圈，再將 right 接在當前 left 的位置
換言之就是將 right 接在 left 的尾巴

line 6 : l *left = right;

quicksort


























void quicksort(node_t **list)
{
    if(!*list)
        return;
    
    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    node_t *left = NULL, *right = NULL;
    while (p){
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? &right : &left, n);
    }

    quicksort(&left);
    quicksort(&right);

    node_t *result = NULL;
    list_concat(&result, left);
    list_concat(&result, pivot); 
    list_concat(&result, right);
    *list = result;
}

line 6 ~ 9 : 選擇 pivot ，從要排序的串列中選擇一個數字當作比較數值的基準，此處使用 list 的第一個 node 作為 pivot

line 15 : list_add_node_t(n->value > value ? AAA : BBB, n) :

如果 n->value 比較大，則將它與 right 串接
如果 n->value 比較小，則將它與 left 串接

跳出迴圈後就會形成兩條 lists ( left & right )

接著進入遞迴進行排序，最後排序成兩條由小到大的 lists

再藉由 list_concat 將兩串列接起來

由於 pivot 是在 left 與 right 兩串列之間，所以與 result 的串接順序是 :
- 1. left
- 1. pivot
- 1. right
所以 CCC = (b) list_concat(&result, pivot); list_concat(&result, right)

解釋 random 執行多次，輸出結果卻相仿

根據 random 的敘述

The srandom() function sets its argument as the seed for a new sequence of pseudo-random integers to be returned by random(). These sequences are repeatable by calling srandom() with the same seed value. If no seed value is provided, the random() function is automatically seeded with a value of 1.

可以得知當 srandom() 的 argument 可以設定 seed 以產生偽亂數的序列，若沒有給予 seed value ，那麼 random() 將會自動將 seed 設為 1。
由於在程式中，並沒有設定 seed value ，所以 default 狀態下 seed = 1 ，才導致每次的輸出結果都一樣。
為了每次都能夠產生不同的 seed，可以使用 time()

time() returns the time as the number of seconds since the Epoch, 1970-01-01 00:00:00 +0000 (UTC).

根據敘述，我們可以得到從標準計時點（一般是 UTC 1970年1月1日午夜）到目前時間的秒數。




#include <time.h>
#include <stdlib.h>

srandom(time(NULL));

如何印出 `time(NULL)` 的時間

可以發現 time(NULL) 的資料型別為 time_t，繼續尋找他的宣告，可在 time_t.h 找到這段 typedef __time_t time_t;
接著繼續查詢，便可在 types.h 找到下方這段 :
# define __time64_t __time_t
根據 GNU C Library 的解釋 :

These single-time configurations only have a 64-bit time_t and related functions, which can handle dates beyond 2038-01-19 03:14:07 (aka Y2038).

在 Visual Stduio 2019 可找到關於 time_t 和 __time64_t 的敘述 :

在 Visual Studio 2005 之前的 Visual C++ 和 Microsoft C/c + + 版本中， time_t 是 long int (32 位) ，因此無法用於過去3:14:07 年1月19日2038（UTC）的日期。 time_t 現在預設等同於 __time64_t，但定義 _USE_32BIT_TIME_T 會將 time_t 變更為 __time32_t，並強制許多時間函式呼叫接受 32 位元 time_t 的版本。

由此可得知，為了表示更長的時間，編譯器廠商可透過改變資料型態來保存時間 (在此以 Visual Stduio 為例)

那麼該如何印出時間呢？
在 time_t-cpp reference 透過 stdint.h 和 intmax_t 來強制轉型。










#include <stdio.h>
#include <time.h>
#include <stdint.h>
 
int main(void)
{
    time_t epoch = time(NULL);
    printf("%jd seconds \n", (intmax_t)(epoch));
    printf("UTC %s", asctime(gmtime(&epoch)));
}

輸出結果

1614588973 seconds 
UTC Mon Mar  1 08:56:13 2021

2021q1 Homework1 (quiz1)

tags: linux2021

作業要求

重要觀念 ： 指標的指標