2019q1 Homework1 (lab0)

tags: System-Software-2019

contributed by < ultype >

注意看 作業要求，共筆的網址應該以 “publish” (點選「發布」按鈕可得) 的網址，也就是如 https://hackmd.io/s/XXXX 的形式，請留意!

jserv

• Data structure
  • queue.h
  • list_ele_t 為單向 linkedlist單元
  • queue_t 有兩個list_ele_t成員分別指向 linklist 頭和尾的list_ele_t單元 和size大小

/* */
typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

/* Queue structure */
typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

• 第一題
  • 新增一個queue
  • 檢查malloc回傳值是否為null來判斷malloc有無成功
  • 初始化queue

queue_t *q_new() {
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q != NULL) {
        q->size = 0;
        q->head = NULL;
        q->tail = NULL;
    }
    return q;
}

• 第二題
  • 注意傳近來的queue是否為null
  • 新增兩個function listEleNew和char counter 方便新增新單元
  • 檢查listEleNew 回傳值 是否為null
  • 插入元素會遇到兩個狀況
    • cond1 Queue size == 0
      • 頭尾同時指向新元素
    • cond2 Queue size != 0
      • 頭指向新元素
      • 在頭處插入新元素

bool q_insert_head(queue_t *q, char *s) {
/*  What should you do if the q is NULL? */
    if (q == NULL)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    newh = listEleNew(s);
    if (newh == NUL)
        return false;
    /* What if either call to malloc returns NULL? */
    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
    } else {
        newh->next = q->head;
        q->head = newh;
    }
    q->size++;
    return true;
}

list_ele_t *listEleNew(char *s) {
    list_ele_t *newh = NULL;
    if (!s)
        return NULL;  // input string NULL
    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newh)
        return NULL;  // list element malloc fail
    newh->value = (char *) malloc(charCounter(s) * sizeof(char));
    if (newh->value == NULL) {  // malloc new char success
        free(newh);
        newh = NULL;
        // printf("new name success size%d
        // %s\n",charCounter(newh->value),newh->value);
    } else {  // malloc new char array fail
        strcpy(newh->value, s);
        newh->next = NULL;
    }
    return newh;
}

int charCounter(char *s) {
    int count = 0;
    if (s == NULL)
        return 0;
    while (s[count] != '\0') {
        count++;
    }
    return count + 1;
}

• 第三題
  • 同第二題
    • cond1 Queue size == 0
      * 頭尾同時指向新元素
    • cond2 Queue size != 0
      * 尾指向新元素
      * 在尾處插入新元素

bool q_insert_tail(queue_t *q, char *s) {
    /* You need to write the complete code for this function */
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL)
        return false;
    newh = listEleNew(s);
    if (newh == NULL)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* Remember: It should operate in O(1) time */
    if (q->tail == NULL) {  // from zero to one
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;
    return true;
}

• 第四題
  • 注意傳近來的queue是否為null
  • 刪除元素會遇到兩個狀況
    • queue 剩下一個單元
    • queue 剩下多於一個的單元
  • 字串的最後要補上"\0" 不然會出錯

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    list_ele_t *temp;
    int stringsize;

    if (q == NULL || q->size == 0)
        return false;

    /* You need to fix up this code. */
    temp = q->head;
    if (q->head == q->tail) {  // from one to zero
        q->head = NULL;
        q->tail = NULL;
    } else {
        q->head = q->head->next;
    }
    stringsize = charCounter(temp->value);
    if (bufsize > 0) {
        if (bufsize < stringsize) {
            strncpy(sp, temp->value, bufsize);
            sp[bufsize - 1] = '\0';
        } else {
            strcpy(sp, temp->value);
        }
    }
    free(temp->value);
    free(temp);

    q->size--;
    return true;
}

• 第五題
  • 注意傳近來的queue是否為null
  • 發現可重複利用第四題完成第五題

void q_free(queue_t *q) {
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q == NULL)
        return;
    while (q->head != NULL) {
        q_remove_head(q, NULL, 0);
    }
    free(q);
    return;
}

• 第六題
  • 注意傳近來的queue是否為null
  • 回傳queue內size 即可

int q_size(queue_t *q) {
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (q) {
        return q->size;
    }
    return 0;
}

• 第七題
  • 注意傳近來的queue是否為null
  • 觀察反轉後與原本linkedlist是對稱的
    • 先將前面的單元往後搬
    • 被搬動的單元搬到原本tail的後面
    • 被搬動的單元的next指向tail->next
    • a->b->c->d
    • b->c->d->"a"
    • c->d->"b"->a
    • d->"c"->b->a
  • 資料來源 leetcode 大神 （來源遺失）

    void q_reverse(queue_t *q) {
    /* You need to write the code for this function */
    list_ele_t *temp, *curr;
    if (q == NULL)
        return;
    curr = q->head;
    while (curr != q->tail) {
        temp = curr;
        curr = temp->next;
        temp->next = (q->tail)->next;
        (q->tail)->next = temp;
    }

    q->tail = q->head;  // swap head and tail
    q->head = curr;
}

githook 腳本研究

• reference1

• Makefile

  • 執行git hook 腳本

GIT_HOOKS := .git/hooks/applied
$(GIT_HOOKS):
      @scripts/install-git-hooks
      @echo

• script資料夾內
  • install-git-hooks
  • pre-commit.hook
    • 第23行(檢查所有 .c .cpp .h檔)

FILES=`git diff --cached --name-only --diff-filter=ACMR | grep -E "\.(c|cpp|h)$"`

• commit-msg.hook