---
# System prepended metadata

title: 程式設計Ⅱ【筆記Ⅰ】
tags: [Programming]

---

# 程式設計Ⅱ【筆記Ⅰ】

* [name=Ivy Lin]
* [筆記Ⅱ](https://hackmd.io/ukBiB1VJTB-T5T4c_uAA3g)
* [筆記ⅠⅠⅠ](https://hackmd.io/JpCPopTTTLyZ91yi279ewA)
* [//筆記Ⅳ](https://hackmd.io/Ts0lnTMpQgGPGw7cvc3X-A)

## 第一週 <*2023.9.12*>

> 利用指標將資料串接形成 ***Linked list*** 結構

### 標準型式  ***singly linked list***

* linked list的結尾用 **NULL** 表示

#### 作法
1. 定義底層資料型態(通常使用 **struct** 搭配 **typedef**)

```clike=
typedef struct t_list{
    //要儲存的資料
    int id;
    char str[10];
    
    //指向LIST結構的指標
    struct t_list* next;
}List; //簡化的名字
```

2. 思考需要被串接的函數內容

```clike=
List* getData(void); //一個List結構的函數，用來取出儲存在結構中的資料)
List* addToLast(List* head, List* np); //在既有的 linked list 加入資料
List* removeFirst(List* head); //在既有的 linked list 移除資料
void showList(List* lst); //顯示list
List* freeList(List* lst); //free list所使用的記憶體
```

3. 讀取資料並串接

> "->" 將輸入的值放到結構指標的某個結構元素中
> "."  結構陣列用此來存取值
> "a->b" 和 "(*a).b" 語法相同
 
```clike=
List* getData(void){
    List* np;
    static int ID; //讓ID的值不消失並存放在getData中
    
    np = (List *)malloc(sizeof(List)); //利用malloc創建一個List的空間
    if(np!=NULL){
        printf("Enter a name: ");
        if (scanf("%9s", np->str)==1) { //利用->將輸入的值存到str中，"==1"是確認使用者確實輸入了可以被讀取的值
            np->id = ID++;
            np->next = NULL;
        } else {
            free(np); //歸還剛剛建構的記憶體空間
            np = NULL; //並重新將np設成NULL
        }
    }
    return np;
}
```


4. 在既有的 linked list 加入或移除資料

> 增加或移除資料的方式依照list函數的操作有所差異
> 通常會使用list的結尾做操作(稱作Quene)

```clike=
//新增、移除資料的函數宣告
List* addToLast(List* head, List* np);
List* removeFirst(List* head);


//函數實作
//新增資料函數 addToLast
List* addToLast(List* head, List* np){ //head指向
    List* ptr = head;
    if(head == NULL)
        head = np; //若head為空，則將head指向np(意即np為第一筆資料)
    else{
        while(ptr->next != NULL) 
            ptr = ptr->next; //利用迴圈走到資料的最後一格
        ptr->next = np; //插入新的資料
    }
    
    return head; //回傳資料開頭
}

//刪除資料函數 removeFirst
List* removeFirst(List* head){
    List* ptr;
    if(head == NULL) return NULL;
    else{
        ptr = head->next; //用ptr記住下一筆資料
        free(head); //free上一筆資料
        
        return ptr; //回傳下一筆資料的位置
    }
}
```

5. 顯示linked list的內容

> 關鍵句: ***lst = lst->next;***

```clike=
void showList(List* lst){
    printf("[");
    while(lst != NULL){
        printf("%d:%s,",lst->id,lst->str);
        lst=lst->next;
    }
    printf("]\n");
}
```

6. 清除整個linked list

> 利用寫好的removeFirst

```clike=
List* freeList(List* lst){
    while(lst != NULL){
        lst = removeFirst(lst);
    }
    return NULL;
}
```

7. main函數(讀取資料)

> 在main的開頭 ***List* head = NULL;***
> 一定要記得設定初值NULL，因為之後呼叫 addToLast 會來當作判斷依據
```clike=
int main(){
    List* head = NULL; //務必要設初始直為NULL
    List* np = NULL;

    while((np = getData()) != NULL) {
        head = addToLast(head, np);
        showList(head);
    }
    
    showList(head);
    head = removeFirst(head); //把第一筆資料移除，並更新head指標
    showList(head);
    head = freeList(head); //清空list
    return 0;
}
```


### 環狀型式  ***Circular Linked List***

* 或是將最後一筆資料接回開頭形成環狀結構

#### 作法
1. 定義底層資料型態(多增加sentinel node來指向第一筆和最後一筆資料)

```clike=
typedef struct t_List {
    int id;
    char str[10];
    struct t_List* next;
} List;
//同原本的linked list

typedef struct {
    List* first;
    List* last;
} Head;
```

2. 思考需要被串接的函數內容

```clike=
List* getData(void); //一個List結構的函數，用來取出儲存在結構中的資料)
Head addToLast(Head head, List* np); //在既有的 linked list 加入資料
Head removeFirst(Head head); //在既有的 linked list 加入資料
void showList(Head head); //顯示list
Head freeList(Head head); //free list所使用的記憶體
```

3. 讀取資料並串接

> 和single list的不同是=>原本np->next是指向NULL
> 環狀list會改成指向自己本身
 
```clike=
List* getData(void)
{
    List* np;
    static int id;
    np = (List *) malloc(sizeof(List));
    if (np!=NULL) {
        printf("Enter a name: ");
        if (scanf("%9s", np->str)==1) {
            np->id = id++;
            np->next = np;  // 這一行不一樣，指向自己而不是NULL
        } else {
            free(np);
            np = NULL;
        }
    }
    return np;
}
```


4. 在既有的 linked list 加入或移除資料

> 若傳入值為NULL，將np設為第一筆資料
> 否則找到最後一筆資料並把np接在後面
> 要維持環狀結構，np->next要指回第一筆資料


```clike=
//函數實作
//新增資料函數 addToLast
Head addToLast(Head head, List* np)
{
  if (head.last == NULL) {
      head.first = np;
      head.last = np;
  } else {
    np->next = head.first;
    (head.last)->next = np;
    head.last = np;
  }
  return head;
}
```

> 若 head.first 是NULL => return head;
> 若 head.first==head.last => 代表只有一筆資料 => free(head.first); **記得要把head.first/last設成NULL**
> 若有超過一筆資料 => 
> 1. 先將last_next 指向first_next
> 2. free(head.first)
> 3. 將head.first指向last_next


```clike=
//刪除資料函數 removeFirst
Head removeFirst(Head head)
{
    if (head.first != NULL)  {
        if (head.first == head.last) {
            free(head.first);
            head.first = head.last = NULL;
        } else {
            (head.last)->next = (head.first)->next;
            free(head.first);
            head.first = (head.last)->next;
        }
    }
    return head;
}
```

5. 顯示linked list的內容

> 關鍵句: ***lst = lst->next;***

```clike=
void showList(Head head)
{
    List* lst = head.first;
    if (lst==NULL) printf("[]\n");
    else {
        printf("[");
        do {
            printf("%d:%s,", lst->id, lst->str);
            lst = lst->next;
        } while (lst != head.first);
        printf("]\n");
    }
}
```

6. 清除整個linked list

> 利用寫好的removeFirst

```clike=
Head freeList(Head head)
{
    while (head.first != NULL) {
        head = removeFirst(head);
    }
    return head;
}
```

7. main函數(讀取資料)

> 注意到 Head head;是一個一般的變數而不是指標
> head 包含的兩個欄位 head.first 和 head.last 都是指向 List 的指標
> 必須手動把兩個指標都設定為 NULL
```clike=
int main(void)
{
    Head head = {NULL, NULL};
    List* np = NULL;

    //head.first = head.last = NULL;
    while((np = getData()) != NULL) {
        head = addToLast(head, np);
        showList(head);
    }
    showList(head);
    head = removeFirst(head);
    showList(head);
    head = freeList(head);
    return 0;
}
```



### 將資料和linked list分開儲存

```clike=
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;
    char str[10];
} Node;

typedef struct t_List {
    Node* data;              // 透過指標，記住資料所在位址
    struct t_List* next;
} List;

Node* createNode(void);      // 用來產生資料
List* cons(Node* nodep, List* lst);   // cons 將資料加在 List 最前面   cons head tail
void showList(List* lst);
void freeList(List* lst);
Node* head(List* lst);       // 取得 List 第一筆資料
List* tail(List* lst);       // 取得扣除第一筆資料之後 剩下的 List

int main(void)
{
    Node* np = NULL;
    List* lst = NULL;

    while((np = createNode()) != NULL) {
        lst = cons(np, lst);  // 不斷用 cons 把新讀取的資料加在既有的 List 前面
        showList(lst);
    }
    showList(lst);

    printf("%d: %s\n", head(lst)->id, head(lst)->str);
    showList(tail(lst));
    freeList(lst);
    return 0;
}

Node* createNode(void)
{
    Node* nodep;
    static int id;

    nodep = (Node *) malloc(sizeof(Node));
    if (nodep!=NULL) {
        printf("Enter a name: ");
        if (scanf("%9s", nodep->str)==1) {
            nodep->id = id++;
        } else {
            free(nodep);
            nodep = NULL;
        }
    }
    return nodep;
}

List* cons(Node* nodep, List* lst)
{
    List* hp;
    if (nodep==NULL) return lst;
    else {
        hp = (List*) malloc(sizeof(List));   // 產生一個 List 結構  並且用指標 hp 記住位址
        hp->data = nodep;                    // 把其中的 data 指標指向 nodep 這筆資料
        hp->next = lst;                      // 把 next 指標指向 既有的 lst
        return hp;                           // 把 hp 所記住的位址傳回去
    }
}

void showList(List *lst)
{
    printf("[");
    while (lst != NULL) {
        printf("%d:%s,", lst->data->id, lst->data->str);
        lst = lst->next;
    }
    printf("]\n");
}

void freeListHelper1(List* lst)
{
    while (lst != NULL) {
        if (lst->data != NULL) {
            free(lst->data);
            lst->data = NULL;
        }
        lst = lst->next;
    }
}

void freeListHelper2(List* lst)
{
    if (lst == NULL) return;
    else {
        freeListHelper2(lst->next);
        free(lst);
    }
}

void freeList(List* lst)
{
    freeListHelper1(lst);   // free 要分成兩步驟， 先把 List 裡面記住的每筆資料清除
    freeListHelper2(lst);   // 再把 List 本身清除
}

Node* head(List *lst)
{
    if (lst != NULL)
        return lst->data;
    else
        return NULL;
}

List* tail(List *lst)
{
    if (lst != NULL)
        return lst->next;
    else
        return NULL;
}
```



## 第二週 <*2023.9.19*>

> 透過參數，傳遞某個指標變數的位址，以便修改函數外部的指標變數的 ***Linked list*** 結構

### 補充寫法(與作業相關)

> [補充資料連結](https://github.com/htchen/i2p-nthu/blob/master/%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88%E4%BA%8C/mid1/2-linked_list_sup.md)

:::info
* 寫法差異:
    主要是更改在傳入變數時，改為傳入指標變數的地址(不須複製一份而是直接更改值)
    
* 實作:
```clike=    
    void insert_increase_list(Node**, int);
```
:::


```clike=
#include <stdio.h>
#include <stdlib.h>
// struct 結構
typedef struct _Node
{
    // 存放的資料
    int data;
    // struct型態 名字為_Node型別的指標
    struct _Node *next;
} Node;

void insert_increase_list(Node **, int);
void show_list(Node *);
void delete_node(Node **, int);

Node *create_node(int x)
{
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = x;
    n->next = NULL;

    return n;
}

void insert_increase_list(Node **hp, int x)
{
    // Node *n = create_node(x);
    if (*hp == NULL)
        *hp = create_node(x);
    else
    {
        Node *q;
        Node *prev = NULL; // 為了記住前一個指標
        q = *hp;
        while (q != NULL && q->data <= x)
        {
            prev = q;
            q = q->next;
        }
        if (prev == NULL) // 插在開頭的情況
        {
            prev = create_node(x);
            prev->next = *hp;
            *hp = prev;
        }
        else // 其他情況(debug時要注意頭尾的狀況是否也不會出錯)
        {
            prev->next = create_node(x);
            prev->next->next = q;
        }
    }
}

void show_list(Node *p)
{
    while (p != NULL)
    {
        printf("{%d,next--}-->", p->data);
        p = p->next;
    }
}

void delete_node(Node **hp, int x)
{
    if (*hp == NULL) // 空list=>不做任何動作
        return;
    else // 有資料的list
    {
        Node *q;
        q = *hp;
        Node *prev = NULL;
        // 若q不是NULL且data不是我要的資料=>繼續找下一個
        while (q != NULL && q->data != x)
        {
            prev = q;
            q = q->next;
        }

        // 如果q=NULL => 完全沒找到要的 => 直接return
        if (q == NULL)
            return;
        // 如果prev=NULL => 資料在到最前端 => *hp設成q->next
        if (prev == NULL)
        {
            *hp = q->next;
            free(q);
        // 若找到了的解法
        else
        {
            prev->next = q->next;
            free(q);
        }
    }
}

int main()
{
    int x;
    Node *head = NULL;

    while (scanf(" %d", &x) == 1)
        insert_increase_list(&head, x);

    show_list(head);

    while (getchar() != '\n')
        ;
    scanf(" %d", &x);
    printf("%d\n", x);

    delete_node(&head, x);
    // printf("k=%d\n", k);
    show_list(head);

    return 0;
}
```

### 兩個星號的練習


```clike=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定義結構=> str紀錄一個動態陣列
typedef struct
{
    int data;
    char *str;
} Node;

// 簡單建構創造新結構的動態陣列方式
Node *create_node()
{
    int x;
    char s[258];
    scanf("%d", &x);
    scanf("%s", s);

    // 動態創造一個結構的記憶體
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = x;
    // 計算輸入的資料長度後在記憶體挖一樣大小的空間(要多一格放'\0')
    n->str = (char *)malloc(sizeof(char) * ((strlen(s) + 1)));
    // 複製s的資料到n->str開出的記憶體空間
    strcpy(n->str, s);

    return n;
}

void show(Node *p)
{
    printf("%p,%d,%s\n", p, p->data, p->str);
}

// 兩顆星的實作處
void swp(Node **a, Node **b)
{
    // 為了能直接改動函數外的值=>傳入指標的位置(雙星=>指標的位置)
    // 創造一個新的結構變數(暫存資料)
    Node *x;
    // 結構變數x(位置)=*a(取得位置的值=>原本資料存放的地址)
    x = *a;
    *a = *b;
    *b = x;

    /*
        **a(指標的位置)  ->  *a(指標)  ->  a(資料)
        **b(指標的位置)  ->  *b(指標)  ->  b(資料)

        利用新的x指標來暫存 *a, 對整個指標交換(重抄地址)

        **a(指標的位置)  ->  *b(指標)  ->  b(資料)
        **b(指標的位置)  ->  *a(指標)  ->  a(資料)

    */
}

int main()
{
    Node *s1, *s2;
    s1 = create_node();
    s2 = create_node();
    // printf("{**s1,%p},{*s1,%p}\n", &s1, s1);
    // printf("{**s2,%p},{*s2,%p}\n", &s2, s2);
    show(s1);
    show(s2);

    swp(&s1, &s2);
    // printf("{**s1,%p},{*s1,%p}\n", &s1, s1);
    // printf("{**s2,%p},{*s2,%p}\n", &s2, s2);
    show(s1);
    show(s2);
}
```


### Linus 指標的優化寫法

:::info
Linus Torvalds on understanding pointers

範例：[https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/](https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/)
:::


* 在找尋資料的過程中，通常會多一個if-else來挑掉不合的狀況

```clike=
//以上面的delete程式碼舉例
void delete_node(Node **hp, int x)
{
    if (*hp == NULL) 
        return;
    else 
    {
        Node *q;
        q = *hp;
        Node *prev = NULL;
        while (q != NULL && q->data != x)
        {
            prev = q;
            q = q->next;
        }
        if (q == NULL)
            return;
        
        
        //這個if-else被視為是不必要的
        if (prev == NULL)
        {
            *hp = q->next;
            free(q);
        else
        {
            prev->next = q->next;
            free(q);
        }
    }
}
```


* 老手的寫法(省掉多餘的if-else)

```clike=
//改寫前面的例子
 void delete_node(Node **hp, int x)
{
    if (*hp == NULL)  return;
    else 
    {
        Node *q;
        //兩個星號的東西=>hp
        //用q來記住hp位置(link list頭)
        q = *hp;
        while(q){ //若q!=NULL(從頭找到尾)
            if (q->data == x){
                //將hp位置設成data的next(接在下一個指標上)
                *hp = q->next; 
                free(q);
                q = (*hp);
            }
            
            //更新資料
            //hp(指標的位址)設為 原本記憶data->next的位址
            hp = &(q->next);
            //q設成hp的值
            q = (*hp);
        }        
    }
}
```


## 第三週 <*2023.9.26*>

> 演算法、約瑟夫斯問題、資料結構

### ***Josephus Problem***

> ***Problem Definition***
> 有 n 個人排成一圈，從 第一個位置開始數，往前每數到第 m 個人，就將那個人從圈子中移除。
> 將被移除的順位列出，就構成所謂的 Josephus Permutation。
> [參考連結](https://en.wikipedia.org/wiki/Josephus_problem)

#### 解法1

> 產生陣列，元素即為每個人的編號
> 逐步模擬移除的過程，移除後將後面陣列元素往前挪


```clike=
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, m, count = 0, pos = 0;
    int *a;
    scanf("%d %d", &n, &m);
    a = (int *)malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++)
        a[i] = i + 1;

    while (n > 1)
    {
        pos += (m - 1);
        pos %= n;

        // a[pos] = -1;
        for (int i = pos + 1; i < n; i++)
            a[i - 1] = a[i];

        --n;
    }
    printf("%d", a[0]);
    return 0;
}
```

:::warning
* 複雜度
    兩層迴圈 => Big-O(n^2)
:::


#### 解法2
> 產生陣列，不搬運，跳過被算過的人

```clike=
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, m, count = 0;
    scanf("%d %d", &n, &m);
    int *a;
    a = (int *)malloc(sizeof(int) * (n + 1));

    for (int i = 0; i < n; i++)
        a[i] = i++;

    int pos = 0, check;
    while (count < n)
    {
        check = 0;
        while (check < (m % n))
        {
            pos += 1;
            pos %= n;
            if (a[pos] != -1)
                check++;
            // printf("{pos,check}={%d,%d}\n", pos, check);
        }
        a[pos] = -1;
        //重點是輸出這行!!!!!
        //(原本的結果會使程式正確運作，但顯示的數值會和正確數值差一格)
        printf("pos=%d\n", (pos + n - 1) % n);
        count++;
    }

    return 0;
}
```


#### 解法3

> 用link list的方式串接資料
> 使用串接資料的方式將要被刪除的元素列印出來

```clike=
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node
{
    int id;
    struct _Node *next;
} Node;

typedef struct
{
    Node *first;
    Node *last;
} Head;

Node *create_Node(int id)
{
    Node *p;
    p = (Node *)malloc(sizeof(Node));
    p->id = id;
    p->next = p;

    return p;
}

Head insert_Node(Head h, Node *p)
{
    if (h.first == NULL)
        h.first = h.last = p;
    else
    {
        p->next = h.first;
        h.first = p;
        (h.last)->next = h.first;
    }

    return h;
}

void show(Head h)
{
    Node *p;
    for (p = h.first; p->next != h.first; p = p->next)
    {
        if (p != NULL)
            printf("%d->", p->id);
    }
    printf("%d->", p->id);
    printf("%d\n", (p->next)->id);
    // printf("%d\n", p->id);
}

Head delete_node(Head h, Node *prev)
{
    Node *p;
    if (h.first != NULL) // 有資料的link list
    {
        // 只有一個資料
        if (h.first == h.last && h.first == prev)
        {
            // 更新head資料為NULL
            h.first = h.last = NULL;
            free(prev);
        }
        // 超過一筆資料
        else
        {
            // 記住要free掉的元素
            p = prev->next;

            // free掉頭的情況
            if (p == h.first)
            {
                // 頭指標改成頭的下一位
                h.first = p->next;
                // 尾指標改成更新過的頭座標
                (h.last)->next = h.first;
            }
            // free掉尾的情況
            else if (p == h.last)
            {
                // 尾指標改為prev(原尾巴的前一個元素)
                h.last = prev;
                // 尾指標的next要改成指向頭指標
                (h.last)->next = h.first;
            }
            // 其餘情況
            else
                // 將prev的next指向下下個元素
                prev->next = p->next;

            free(p);
        }
    }

    return h;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    Head head = {NULL, NULL};
    Node *p;

    int *a;
    a = (int *)malloc(sizeof(int) * n);

    for (int i = n; i > 0; i--)
    {
        p = create_Node(i);
        head = insert_Node(head, p);
    }

    show(head);

    int check, count = 0;
    p = head.last;
    while (count < n)
    {
        check = 0;
        while (check < ((m - 1) % n))
        {
            p = p->next;
            check++;
        }
        // 一樣對輸出的值做改動
        printf("%d->", ((p->next)->id) - 1);
        head = delete_node(head, p);
        count++;
    }

    return 0;
}
```


#### 解法4

> 用link list記住下一個還沒被殺死的元素
> 直接走到新的格子(但沒有free掉被殺死的元素)

```clike=
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node
{
    int id;
    int next;
    int prev;
} Node;

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    Node *a;
    a = (Node *)malloc(sizeof(Node) * n);

    for (int i = 0; i < n; i++)
    {
        a[i].id = i + 1;
        a[i].next = (i + 1) % n;
        a[i].prev = (i - 1) % n;
    }

    int check, count = 0, p, kill;
    p = n - 1;
    while (count < n)
    {
        check = 0;
        while (check < ((m - 1) % n))
        {
            p = a[p].next;
            check++;
        }

        // 一樣對輸出的值做改動
        kill = a[p].next;
        printf("%d->", (a[kill].id) - 1);
        a[p].next = a[kill].next;
        count++;
    }
}
```


#### 解法5(下星期會再詳細的講解)

> 使用遞迴方式來計算數值
> 優點:不用寫複雜的link也不須模擬
> 缺點:過程無法顯示，只能計算出最後剩下的元素

```clike=
#include <stdio.h>

int f(int n, int m){ // index from 1 to n
    //公式本人
    if( n == 1 ) return 1;
    else return ( f(n-1, m) + m-1 ) % n + 1;
}

int main(void) {
    int n = 41, m = 3, i;
    printf("%d\n", f(n,m));
    return 0;
}
```