2023q1 Homework1 (lab0)

contributed by < POCHUN-CHEN >

Helpful Git skill

I have created a note to document how to use Git.
Git基本功能教學

why we should use "pointer to pointer" (indirect pointer)

This can avoid using an additional conditional statement at the beginning of the data.

Worse & better code comparision

Worse code

void remove_list_node(List *list, Node *target)
{
    Node *prev = NULL;
    Node *current = list->head;
    // Walk the list
    while (current != target) {
        prev = current;
        current = current->next;
    }
    // Remove the target by updating the head or the previous node.
    if (!prev)
        list->head = target->next;
    else
        prev->next = target->next;
}

Better code

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;
}

Discussing

In the program I wrote for the first time, I used this code *indirect = (*indirect)->next;. I think this can reduce the use of pointer once and make the program more fast.

Q: why can't we replace
indirect = &(*indirect)->next; in line 9 by
*indirect = (*indirect)->next;?

A: head will be changed!

See the below flow diagram:

Wrong way

Wrong way: *indirect = (*indirect)->next;

Correct way

Correct way: indirect = &(*indirect)->next;

List structure for linked list

This is the structure diagram that I initially thought of when I first tried to understand the linked list structure.
Below diagram is an example of a singly linked list.

I have a question, why can't we put a Node_head structure in the first List_of_head ? As shown in the following figure.

This allows for more efficient use of the Node_head for memory space.

Anwser: 自 Head 開始，鏈結 list 各節點，個別節點皆嵌入 list_head 結構體，不過 Head 是個特例，無法藉由 container_of 巨集來找到對應的節點，因為後者並未嵌入到任何結構體之中，其存在是為了找到 list 整體。

Linked list `container_of` structure

List structure

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

Element structure with char value

typedef struct {
    char *value;
    struct list_head list;
} element_t;

Note:

typedef define a type struct{...} to a new name element_t.

Flow chart:

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Notes:

Head is a special case without Node. It just use to serch for the list.
In element_t structure, we can know the value address through counting the type size to get it. This is why we should use "container_of".

References:

Instructions of functions in "queue.c"

Write in English more proficiently!

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

Homework Request:

[q_new] Create an empty queue

Use INIT_LIST_HEADin librarylist.h to initialize prev & next.

Instructions:

Use malloc(sizeof())to allocate memorynew, and check the allocated memory new action is succesful or not.
If this condition is right, use INIT_LIST_HEADto initialize the struct list_head and return new.

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

If this condition is wrong , return Null.

Source Code

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struc list_head));
    if(new){
        INIT_LIST_HEAD(new);
        return new;
    }
    return NULL;
}

[q_free] Free all storage used by queue

Instructions:

Check l exist.
Declare node to run through whole list.
Use list_del to pick up each del and use q_release_element to delete it.

Source Code (Version 1: Dereferenced a NULL or invalid pointerAborted)

/* Free all storage used by queue */
void q_free(struct list_head *l) {
   if (!l)
        return;
    
    struct list_head *curr = l->next;
    
    while (curr != l)
    {
        element_t *del = list_entry(curr, element_t, list);
        if (!del)
            return;
        list_del(&del->list);
        free(del);
        curr = curr->next;
    }
    
    free(l); 
}

Source Code (Version 2: Dereferenced a NULL or invalid pointerAborted)

/* Free all storage used by queue */
void q_free(struct list_head *l) {
   if (!l)
        return;
    
    struct list_head *curr = l->next;
    
    while (curr != l)
    {
        element_t *del = list_entry(curr, element_t, list);
        if (!del)
            return;
        list_del(&del->list);
        q_release_element(del);
        curr = curr->next;
    }
    
    free(l); 
}

Debug:

Use function q_release_element(), instead of free(). Because there are not element just has itself, there are value.
We didn't need to check element_t *del is exist. It must exist when we allocate memeory before.

static inline void q_release_element(element_t *e)
{
    test_free(e->value);
    test_free(e);
}

curr = curr->next; must before list_del(&del->list) & q_release_element(del), or curr will pointer a cutted list node del. It will pointer NULL, after we delete del.

Source Code (Version 3)

/* Free all storage used by queue */
void q_free(struct list_head *l) {
   if (!l)
        return;

    struct list_head *curr = l->next;

    while (curr != l) {
        element_t *del = list_entry(curr, element_t, list);
        // if (!del)
        //     return;
        curr = curr->next;
        list_del(&del->list);
        // free(del);
        q_release_element(del);
    }

    free(l);
}

[q_insert_head] Insert an element at head of queue

Use list_addin librarylist.h to add a node next to head.

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

Instructions:

Use malloc(sizeof())to allocate memorynew, and check the allocated memory new action is succesful or not.
Allocate memory to new->value in element_t.
Copy value from s to new->value
Use list_add() to add a node next to head.

Debug:

If we want to storage 'l' long string, we need to use 'l+1' char to storage and put '\0' after each string.
strncpy(new->value, s, strlen(s)); we don't need to add one char memory size in the third input.

Source Code

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    int sl = strlen(s);
    new->value = malloc(
        (sl + 1) *
        sizeof(char));  // notice there are (strlen(s)+1) size need to allocate.
    if (!new->value) {
        free(new);
        return false;
    }
    strncpy(new->value, s, sl);
    *(new->value + sl) = '\0';  // add '\0' after string.
    list_add(&new->list, head);
    return true;
}

[q_insert_tail] Insert an element at tail of queue

This function is similar to q_insert_head.
The only different part is list_add(&new->list,head) and list_add_tail(&new->list, head).

!!Segmentation fault occurred. You dereferenced a NULL or invalid pointer!!

Sol:
We need to check, if memory is fail allocation, free fail allocation memory.

if (!new->value) {
        free(new);
        return false;
    }

Source Code

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    int sl = strlen(s);
    new->value = malloc(
        (sl + 1) *
        sizeof(char));  // notice there are (strlen(s)+1) size need to allocate.
    if (!new->value) {
        free(new);
        return false;
    }
    strncpy(new->value, s, sl);
    *(new->value + sl) = '\0';  // add '\0' after string.
    list_add_tail(&new->list, head);
    return true;
}

[q_remove_head] Remove an element from head of queue

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}

We need to check head is exist and not empty.

/* list_empty() - Check if list head has no nodes attached */
static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

/**
 * list_entry() - Get the entry for this node
 * @node: pointer to list node
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 *
 * Return: @type pointer of entry containing node
 */
#define list_entry(node, type, member) container_of(node, type, member)

Instructions:

bufsize-1

*(removed->value + bufsize-1) = '\0';

Debug:
*(sp + bufsize-1) = '\0';

removed->value just exist in function q_remove_head. This is not helpful for modifying parameters.

Source Code (version 1)

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *removed = list_entry(head->next, element_t, list);
    if (!removed)
        return NULL;
    list_del(&removed->list);

    if (bufsize) {
        strncpy(sp, removed->value, bufsize - 1);
    }
    *(removed->value + bufsize - 1) = '\0';
    return removed;
}

Source Code (version 2)

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *removed = list_entry(head->next, element_t, list);
    if (!removed)
        return NULL;
    list_del(&removed->list);

    if (bufsize) {
        strncpy(sp, removed->value, bufsize - 1);
    }
    *(sp + bufsize - 1) = '\0';
    return removed;
}

[q_remove_tail] Remove an element from tail of queue

Instructions:

Source Code (Version 1)

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
     if (!head || list_empty(head))
        return NULL;
    element_t *removed = list_entry(head->prev, element_t, list);
    if (!removed)
        return NULL;
    list_del(&removed->list);

    if (bufsize) {
        strncpy(sp, removed->value, bufsize - 1);
    }
    *(removed->value + bufsize - 1) = '\0';
    return removed;
}

Source Code (Version 2)

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *removed = list_entry(head->prev, element_t, list);
    if (!removed)
        return NULL;
    list_del(&removed->list);

    if (bufsize) {
        strncpy(sp, removed->value, bufsize - 1);
    }
    *(sp + bufsize - 1) = '\0';
    return removed;
}

[q_size] Return number of elements in queue

/* list_for_each - Iterate over list nodes*/
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

Instructions:

Check head is exist
Structure a node
Declarate size = 0, and iterate plus it by list_for_each

Discussing:
Why can't we use queue_contex_t *entry to get q_size?

queue_contex_t *entry = list_entry(head, queue_contex_t, q);
return entry->size;

Source Code

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    struct list_head *node;
    int size = 0;
    list_for_each (node, head)
        size++;
    return size;
}

[q_delete_mid] Delete the middle node in queue

Instructions:

Check there are not just a head
Construct two list_head，rabbit、turtle。
Check rabbit->next、rabbit->next->next is not head
Move rabbit two steps， and turtle one steps. It decides when rabbit arrived head, turtle will stand in the middle of list.
Use list_del（turtle） to delete turtle.

Discussing:

If list monents is odd, there is a middle node from 1.
If list monents is even, there is a middle node from 0.
e.g.

n = 6
(6+1)/2=3.5 -> 4
n = 5
(5+1)/2=3 -> 3

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing.

Source Code (Version 1)

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/de lete-the-middle-node-of-a-linked-list/
    if (!head->next)
        return false;
    struct list_head *rabbit = head->next, *turtle = head->next;

    while (rabbit->next != head && rabbit->next->next != head) {
        rabbit = rabbit->next->next;
        turtle = turtle->next;
    }
    turtle = turtle->next;
    list_del(turtle);

    return true;
}

Update imformation is contributed by < Risheng1128 >

while (rabbit != head && rabbit->next != head)

Source Code

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/de lete-the-middle-node-of-a-linked-list/
    if (!head->next)
        return false;
    struct list_head *rabbit = head->next, *turtle = head->next;

    while (rabbit != head && rabbit->next != head) {
        rabbit = rabbit->next->next;
        turtle = turtle->next;
    }
    list_del(turtle);

    return true;
}

[q_delete_dup] Delete all nodes that have duplicate string

Source Code

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    
    return true;
}

[q_swap] Swap every two adjacent nodes

Instructions:

Check head exist.
Declare list_head structure curr, first, second. curr will make the list move next two steps each generation. first and second will chanege each other.

Source Code (Version 1: Ifinity loop)

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;

    struct list_head *curr = head->next, *first = NULL, *second = NULL;

    while (curr != head && curr->next != head) {
        first = curr;
        second = first->next;
        first->next = second->next;
        first->prev = second;
        second->next = first;
        second->prev =curr->prev;
        curr = curr->next->next;
    }
}

Source Code (Version 2: Ifinity loop)

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;

    struct list_head *first = head->next;

    while (first != head && first->next != head) {
        struct list_head *second = first->next;
        first->next = second->next;
        second->prev =first->prev;
        first->prev->next = second;
        second->next->prev = first;
        first->prev = second;
        second->next = first;
        first = first->next;
    }

Debug:
I didn't change the pointers first->prev->next & second->next->prev.

Source Code (Version 3)

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;

    struct list_head *first = head->next;

    while (first != head && first->next != head) {
        struct list_head *second = first->next;
        list_del_init(first);
        list_add(first, second);
        first = first->next;
    }

Better code thinking.
Reference guide line[q_swap] in 2022q1 Homework1 (lab0) 。

I don't need to use three list_head
It will be better declare second in while loop.
Use list_del_init, list_add(first, second).

[q_reverse] Reverse elements in queue

Instructions:

Check head exist.
Delcare *prev 、 *cuur 、 *next .

Tips:

If we want to do the code in the function at lease once, we can use pointer to pointer to NULL. After doing the code in the function the pointer which pointers to NULL will get meaning, we can compare it in the function condition.

Source Code

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *prev = head->prev, *curr = head, *next = NULL;

    while (next != head) {
        next = curr->next;
        curr->next = prev;
        curr->prev = next;
        prev = curr;
        curr = next;
    }
}

[q_reverseK] Reverse the nodes of the list k at a time

Discussing:

Why we can't uselist_del_init(curr) and list_add(curr,&list), but can use list_move(curr, &list) ?
Why we can't use list_add_tail(&list,curr) and list_move_tail(&list, curr), but can use list_splice_tail(&list, curr) ?
Is list_move_tail(&list, curr) better than change pointers' destinations?

Source Code (Version 1)

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;

    struct list_head *curr = head->next, *list = NULL;
    
    while (curr != head) {

        struct list_head *next = NULL;

        for (int i = 0; i < k; i++){
            
            next = curr->next;
            
            if (next == head){
                list_add(list,curr);
                return;
            }
                
            list_del_init(curr);
            list_add_tail(curr,list);
            curr = next;
        }
        q_reverse(list);
        list_add(list,curr);
        free(list);
    }
}

Source Code (Version 2)

// https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;

    struct list_head *curr = head->next;
    
    while (curr != head){
        
        struct list_head list;
        INIT_LIST_HEAD(&list);

        for (int i = 0; i < k; i++){
            
            struct list_head *next = curr->next;
            
            if (next == head){
                //list_add(&list,curr);
                q_reverse(&list);
                list_splice_tail(&list, curr);
                return;
            }
                
            // list_del_init(curr);
            // list_add(curr,&list);
            list_move(curr, &list);
            curr = next;
        }
        //q_reverse(&list);
        // list_add_tail(&list,curr);
        // list_move_tail(&list, curr);
        list_splice_tail(&list, curr);

        //free(&list);
    }
}

[q_sort] Sort elements of queue in ascending order

Instructions:

q_sort has a same concept as Merge Two Sorted Lists.

Reference Source code quick-sort.c in sysprog21/linux-list programs 。

Check linked list in head has more than two entry and not empty. If not return it.
Use INIT_LIST_HEAD to initialize two list structure we made.
Use list_first_entry to get first entry to set it as pivot.
Delete the pivot from linked list (use list_del)
Compare through all list (list_for_each_entry_safe). Use strncmp to compare item->value to pivot->value, and seperate them to each list_less and list_greater.
Call q_sort to regress list_less & list_greater.
Add pivot to list
Splice list_less before pivot in list.
Splice list_greater after pivot in list.

Debug

cmprint() error: implicit declaration of function ‘cmpint’
Sol: use strcmp() to replace cmprint()

list_for_each_entry_safe(item, is, head, list) {
        if (cmpint(&item->value, &pivot->value) < 0)
            list_move_tail(&item->list, &list_less);
        else
            list_move_tail(&item->list, &list_greater);
    }

or declarate function cmprint()

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

Source Code

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    struct list_head list_less, list_greater;
    element_t *pivot;
    element_t *item = NULL, *is = NULL;

    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    pivot = list_first_entry(head, element_t, list);
    list_del(&pivot->list);

    list_for_each_entry_safe (item, is, head, list) {
        if (strcmp(item->value, pivot->value) < 0)
            list_move_tail(&item->list, &list_less);
        else
            list_move_tail(&item->list, &list_greater);
    }

    q_sort(&list_less);
    q_sort(&list_greater);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}

[q_descend] Remove every node which has a node with a strictly greater value anywhere to the right side of it

Source Code

/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    return 0;
}

[q_merge] Merge all the queues into one sorted queue, which is in ascending order

Merge k Sorted Lists is developed by Merge Two Sorted Lists. There is a concept that I don't really understand.
q_sort has a same concept as Merge Two Sorted Lists.

Instructions:

Check head is exist and not empty.
list_for_each_entry is a function which iterates over list entries. In queue_contex_t struct, it like a 2D list. list_head *q is a one component list, and list_head chain is a group list made by many component lists.
Cut the circular linked list to doubly linked list.
Use function mergeTwoLists to merge two lists.
list_entry is a function which gets the entry for the node.
Restructure doubly linked list to circular linked list.
Return q_size of (group_list->q).

Hint:

include <stdint.h> ,when we use uintptr_t.
Function features
- mergeTwoLists : Put two lists together, and sequence them.
- mergesort_list : Seperate lists.
Adjust function mergeTwoLists() below.











struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    c *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (L1->val < L2->val) ? &L1: &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

In line 4, *node = (*node)->next has different data types. *node is struct ListNode* , and (*node)->next is struct linked_head*. Change struct ListNode* to struct linked_head*, and use list_entry()to assigment element_t *L1_entry.

Compare node = (L1_entry->value < L2_entry->value) ? &L1 : &L2 & node = strcmp(L1_entry->value, L2_entry->value) < 0 ? &L1 : &L2. Why strcmp() doesn't cause "ERROR: Not sorted in ascending order (It might because of unsorted queues are merged or there're some flaws in 'q_merge')" or "ERROR: Removed value c != expected value r"?

Source Code

Function mergeTwoLists()

/* Merge the two lists in a one sorted list. */
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        element_t *L1_entry = list_entry(L1, element_t, list);
        element_t *L2_entry = list_entry(L2, element_t, list);
        node = (L1_entry->value < L2_entry->value) ? &L1 : &L2;
        
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

Function q_merge()

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;

    queue_contex_t *entry = list_entry(head, queue_contex_t, chain);
    queue_contex_t *c_next = entry->chain.next;
    struct list_head *q_head = c_next->q;

    while (c_next != head)
    {
        // struct list_head *q_curr = q_head->next;
        
        // while (q_curr->next != q_head)
        // {
        //     struct list_head *q_next = q_curr->next;
        //     list_move_tail(q_curr,entry->q);
        //     q_curr = q_next;
        // }
        list_splice_tail(q_head,entry->q);
        c_next = c_next->chain.next;
    }
    q_sort(q_head);
    int size = q_size(q_head);
    return size;

    
    
    
    return 0;
}

Q & A

Experiment:

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int n = 5;
    for (int i = 0; i <= n; i++) {
        printf("%d\n", i);
    }
    return 0;
}

Output:

That means i++ is be done after once cycle of for function done.

In 案例探討: LeetCode 21. Merge Two Sorted Lists case, why we use struct in Line 1 ? It should be a function.

struct ListNode *mergeTwoLists(struct ListNode *L1,
                               struct ListNode *L2) { 
    struct ListNode *head;
    struct ListNode **ptr = &head;
    for (; L1 && L2; ptr = &(*ptr)->next) {
        if (L1->val < L2->val) {
            *ptr = L1;
            L1 = L1->next;
        } else {
            *ptr = L2;
            L2 = L2->next;
        }
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

在非遞迴的實作中，原始的迭代版 merge sort 如下：





























void mergesort_iter(node_t **list) {
    node_t *head = *list;
    if (!head || !head->next)
        return;

    node_t *result = NULL;
    node_t *stack[1000];
    int top = 0;
    stack[top] = head;

    while (top >= 0) {
        node_t *left = stack[top--];

        if (left) {
            node_t *slow = left;
            node_t *fast;

            for (fast = left->next; fast && fast->next; fast = fast->next->next)
                slow = slow->next;
            node_t *right = slow->next;
            slow->next = NULL;

            stack[++top] = left;
            stack[++top] = right;
        } else
            result = mergeTwoLists(result, stack[top--]);
    }
    *list = result;
}

第12行程式碼意義為何？

2023q1 Homework1 (lab0)

Helpful Git skill

why we should use "pointer to pointer" (indirect pointer)

Discussing

List structure for linked list

Linked list container_of structure

Note:

Flow chart:

Notes:

References:

Instructions of functions in "queue.c"

[q_new] Create an empty queue

Instructions:

[q_free] Free all storage used by queue

Instructions:

[q_insert_head] Insert an element at head of queue

Instructions:

[q_insert_tail] Insert an element at tail of queue

[q_remove_head] Remove an element from head of queue

Instructions:

[q_remove_tail] Remove an element from tail of queue

Instructions:

[q_size] Return number of elements in queue

Instructions:

[q_delete_mid] Delete the middle node in queue

Instructions:

Discussing:

[q_delete_dup] Delete all nodes that have duplicate string

[q_swap] Swap every two adjacent nodes

Instructions:

[q_reverse] Reverse elements in queue

Instructions:

Tips:

[q_reverseK] Reverse the nodes of the list k at a time

[q_sort] Sort elements of queue in ascending order

Instructions:

Debug

[q_descend] Remove every node which has a node with a strictly greater value anywhere to the right side of it

[q_merge] Merge all the queues into one sorted queue, which is in ascending order

Instructions:

Hint:

Q & A

Read more

會議邀請人員

Servo Lab 碩士口試注意事項

3D 列印交接工作

量測結果python畫圖

Linked list `container_of` structure