# 程式設計Ⅱ【筆記Ⅰ】
* [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;
}
```
Sign in with Wallet
Connect another wallet