# 計算機程式設計 Quiz 2
## Problem 1
### Description
用動態二維陣列實作，判斷陣列內數字是否都只出現一次。第一輸入有兩個整數 m, n，表示陣列的高度與寬度，接下來是這個陣列的值，值的範圍介於 1 ~ m * n。
#### Sample Input

3 3
1 2 3
4 5 6
7 8 9

3 3
1 2 1
4 5 6
7 8 9

#### Sample Output

yes

no

### Solution
#### main.c

#include <stdio.h>
#include <stdlib.h>

int main() {
    int m, n, e;
    scanf("%d %d", &m, &n);
    char** arr = (char**)malloc(sizeof(char*) * m);
    for (int i = 0; i < m; i++) {
        arr[i] = (char*)malloc(sizeof(char) * n);
        arr[i][n] = 0;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &e);
            if (arr[(e - 1) / n][(e - 1) % n]) {
                printf("no\n");
                return 0;
            } else {
                arr[(e - 1) / n][(e - 1) % n] = 1;
            }
        }
    }
    printf("yes\n");
    return 0;
}

## Problem 2
### Description
輸入字串，將字串轉成整數，需用 recursion，最後需要換行。
#### Sample Input

12345678

#### Sample Output

12345678

### Solution
#### main.c

#include <stdio.h>
#include <string.h>
#include "function.h"

int main(){
    char str[20];
    scanf("%s", str);
    int n = strlen(str);
    printf("%d\n", str2int(str, n));
    return 0;
}

#### function.h

int str2int(char* str, int len) {
    if (len == 1) return str[0] - '0';
    return str[len - 1] - '0' + str2int(str, len - 1) * 10;
}

## Problem 3
### Description
實作 `initialize()`、`insertion()`、`reverse_list()`，其中 `insertion()` 是需要插入在 linked list 的開頭而非結尾。
#### Sample Input

5
1 2 3 4 5

#### Sample Output

1 2 3 4 5

### Solution
#### main.c

#include <stdio.h>
#include <stdlib.h>
#include "function.h"


int main(){
    linked_list_t my_list;
    initialize(&my_list);    
    int data, input_size;
    /* when you add a node, you add it at the head */
    
    scanf("%d\n", &input_size);
    for(int i=0; i < input_size; ++i) {
        scanf("%d", &data);
        insertion(&my_list, data);
    }
    
    reverse_list(&my_list); 
    output_list(&my_list);  

    return 0;
}

void output_list(linked_list_t *ptr_list){
    node_t *ptr_node = ptr_list->head;
    char is_first = 1;
    while(ptr_node){
        if(is_first){
            printf("%d", ptr_node->data);
            is_first = 0;
        } else{
            printf(" %d", ptr_node->data);
        }
        ptr_node = ptr_node->next;
        
    }
    printf("\n");
}

#### function.h

#include <stdlib.h>

struct node{
    int data;
    struct node *next;
};
typedef struct node node_t;

typedef struct linked_list{
    node_t *head;
} linked_list_t;

void initialize(linked_list_t* L) {
    L->head = NULL;
}

void output_list(linked_list_t*);

void insertion(linked_list_t* L, int data) {
    node_t* new_node = (node_t*) malloc(sizeof(node_t));
    new_node->data = data;
    new_node->next = NULL;
    if (!L->head) L->head = new_node;
    else {
        new_node->next = L->head;
        L->head = new_node;
    }
}

void reverse_list(linked_list_t* L) {
    node_t* prev = NULL;
    node_t* curr = L->head;
    node_t* next = L->head->next;
    while (curr) {
        curr->next = prev;
        prev = curr;
        curr = next;
        if (next) next = next->next;
    }
    L->head = prev;
}

## Problem 4
### Description
`initialize()`、`insertion()`可以從 Problem 3 複製，實作 `reverse_output()`，不可以在 `reverse_output()` 裡面呼叫 `reverse_output()` 之外的 function，可以使用全域變數。
#### Sample Input

5
1 2 3 4 5

#### Sample Output

1_2_3_4_5

### Solution
#### main.c

#include <stdio.h>
#include <stdlib.h>
#include "function.h"


int main(){
    linked_list_t my_list;
    initialize(&my_list);    
    int data, input_size;
    /* when you add a node, you add it at the head */
    
    scanf("%d\n", &input_size);
    for(int i=0; i < input_size; ++i) {
        scanf("%d", &data);
        insertion(&my_list, data);
    }
    
    reverse_output(my_list.head);  

    return 0;
}

#### function.h

#include <stdio.h>
#include <stdlib.h>

int len = 0;

struct node{
    int data;
    struct node *next;
};
typedef struct node node_t;

typedef struct linked_list{
    node_t *head;
} linked_list_t;

void initialize(linked_list_t* L) {
    L->head = NULL;
}

void insertion(linked_list_t* L, int data) {
    node_t* new_node = (node_t*) malloc(sizeof(node_t));
    new_node->data = data;
    new_node->next = NULL;
    if (!L->head) L->head = new_node;
    else {
        new_node->next = L->head;
        L->head = new_node;
    }
}

void reverse_output(node_t* curr) {
    if (!curr->next) {
        printf("%d", curr->data);
        if (!len) printf("\n");
        return;
    }
    len++;
    reverse_output(curr->next);
    len--;
    printf("_%d", curr->data);
    if (!len) printf("\n");
}