資料結構 上

IDE Code

WEEK_2：正課
9.30實習題_Insertion_Sort
9.30實習題_binary_search
9.30加分題_交集法_DFS

WEEK_3：
10.7實習題_非連續子序列之兩數最大和（Struct & Sort）
10.7延伸題_最大非連續子序列和（DP）
10.7加分題_奇數魔方陣

I/O Stream（課外補充）

I/O 優化（加速輸入輸出 遇TLE可用）

    //取消強制flush
    cin.tie(0);
    
    //取消 iostream 與 stdio 的同步使用
    ios_base::sync_with_stdio(false);
    
    //不使用 cout << endl 
    cout << "\n";

StringStream（好工具）

getline 搭配 stringstream

輸出

四捨五入cout << fixed << setprecision(10); 或是更高精度 (int)10*位數+0.5
寬度 cout << setw(n) << setfill( c ) <<;

參考資料：
https://cp.wiwiho.me/

Swap

Define

#define swap(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

Call by address (Call by pointer)

void swap(int *x,int *y){
    int tmp=*x;
    *x=*y;
    *y=tmp;
}

Call by reference

void swap(int &x,int &y){
    int tmp=x;
    x=y;
    y=tmp;
}

Auto

根據使用型態變化

變數宣告

  // int x = 1;
  auto x = 1;    
  
  // double y = sin(1.3);
  auto y = sin(1.3);

陣列宣告

    // initializer_list<int>
    auto A = { 1, 2 };

    // initializer_list<int>
    auto B = { 3 };

函式宣告

// int my_fun();
auto my_fun(){    
    int value = 3;
    return value;
}

參考資料：
https://blog.gtwang.org/programming/cpp-auto-variable-tutorial/
https://docs.microsoft.com/zh-tw/cpp/cpp/auto-cpp?view=msvc-160

For Loop

使用於任何陣列。
for( auto y : x ){…}
y = x.begin() → x.end()。

    int x[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    //float[]、vector<double>，任何陣列。

Call by value

    for( auto y : x ){ 
        y++;
    }
    //int x[10] = {1,2,3,4,5,6,7,8,9,10};

Call by reference

可以修改陣列

    for( auto &y : x ){ 
        y++;
    }
    //int x[10] = {2,3,4,5,6,7,8,9,10,11};

參考資料：
https://docs.microsoft.com/zh-tw/cpp/cpp/range-based-for-statement-cpp?view=msvc-160

Dynamic Memory Allocation

    int *i;
    float *pi;
    
    i=(int*)malloc(sizeof(int));//動態記憶體配置
    *i=1024;
    
    pi=(float*)malloc(sizeof(float));//動態記憶體配置
    *pi=3.1415;
    
    printf("i=%d,pi=%d",*i,*pi);
    
    free(i);
    free(pi);

Selection sort

從未排序中，選擇最小的放進數列中

//n為list大小

    for(i=0;i<n;i++){    //i之前已排好
        for(j=i+1;j<n;j++){    //i之後選擇最小的丟到前面去
            if(list[i]>list[j]){
                swap(&list[i],&list[j]);
            }
        }
    }
    
    for(i=0;i<n;i++){
        printf("%d,",list[i]);
    }

參考資料：
https://medium.com/appworks-school/初學者學演算法-排序法入門-選擇排序與插入排序法-23d4bc7085ff

Insertion Sort

插入已排列的數列
題目：http://140.121.198.41:20211/contest/5/problem/2

    for(i=1;i<n;i++){    //輪到i去插入
        int tmp = list[i];          // tmp = 正處理的值
        j=i-1;
        while( j>-1 && tmp<list[j] ){
            itst[j+1]=list[j];    // 向右移
            j--;
        }
        list[j+1]=tmp;            // 插入新值
    }

參考資料：
http://notepad.yehyeh.net/Content/Algorithm/Sort/Insertion/1.php

Bubble Sort

Merge Sort

Quick Sort

Binary_search

只適用於「已排序」的數列
題目：http://140.121.198.41:20211/contest/5/problem/1

Main

    int mid,L,R,target;
    scanf("%d",&target);
    L=0,R=n-1;

Recursion

int binary_search(int L,int R,int list[],int target,int mid){

    if(L<=R){    //終止條件
        mid=(L+R)/2;
        if(target==list[mid]){
            return mid;
        }
        else if(target<list[mid]){
            binary_search(L,mid-1,list,target,mid);
        }
        else{
            binary_search(mid+1,R,list,target,mid);
        }
    }
    
    return -1;
}

Non-Recursion

int binary_search(int L,int R,int list[],int target,int mid){
    while(L<=R){
        mid=(L+R)/2;
        if(target==list[mid])
            return mid;
        else if(target<list[mid])
            R=mid-1;
        else
            L=mid+1;
    }
    return -1;
}

Binary search tree

參考資料：
https://www.gushiciku.cn/dc_tw/101530793
https://blog.techbridge.cc/2016/09/24/binary-search-introduction/

加分題_交集法（DFS）

題目：http://140.121.198.41:20211/contest/5/problem/a1

作法：
1 1 1 1 0 0 0 0 0 0
1 1 1 1 0 1 0 0 0 0
1 1 1 1 0 1 0 1 1 0 >>解答1 回復上一動
1 1 1 1 0 1 0 0 1 1 >>解答2 回復上一動
1 1 1 1 0 0 1 0 0 0
1 1 1 1 0 0 1 0 1 1 >>解答3 回復上一動
1 1 1 1 0 0 0 1 0 0
1 1 1 1 0 0 0 0 1 0
1 1 1 1 0 0 0 0 0 1
…

DFS

//input:n=10,inp[0..2]=4,1,2 
//Output：0 1 1 1 0 0 0 0 1 0
//index=走訪位置，ans[]=答案，m為inp的序號

void DFS(int index,int m){

    if(m==inp_size){//等於最後一個
        for(int j=0;j<n;j++){   //check有重複出現的位置。
            ans[j]=ans[j]&tmp[j]; //位元運算
        }
    }
    
    else{   
        while(index<n){ 
            if(check(index,inp[m])){  //判斷可不可以放進去。
                for(int j=0;j<inp[m];j++){  //放入方塊。
                    tmp[index+j]=1;
                }
                DFS(index+inp[m],m+1);    //進到下一層，左子樹。
                for(int j=0;j<inp[m];j++){  //回復上一動，回節點。
                    tmp[index+j]=0;
                }
            }
            index++;
        }
    }
    
}

Check

bool check(int index,int m){
    if((index==0||tmp[index-1]==0)&&(tmp[index+m]==0)&&((index+m)<=n)){
       return true; 
    }
    else{
        return false;
    }
}

Main

int main() {
   
   cin >> n;    //陣列大小
   inp_size=0;
   while(cin >> inp[inp_size]){    //輸入input
       inp_size++;
   }
   
   for(int j=0;j<n;j++){    //設為0
       tmp[j]=0,ans[j]=1;
   }
   
   DFS(0,0);
   
   for(int j=0;j<n;j++){
       printf("%d ",ans[j]);
   }
   
   return 0;
}

Abstraction

透過語意、規範，隱藏實作過程來簡化程式。

Data Abstraction

透過資料型態（規範），來包裝各種元素。

• Array

    int list[5]={0,1,2,3,4};    //儲存單一型態

• Structure

struct student{    //儲存多數型態
    char lastName;
    int studentId;
    char grade; 
}

Abstraction Data Type（ADT）

以規範好的行為，去操作資料形態中的物件。

    stack<int> Stack;
    
    Stack.push(...)
    Stack.pop
    cout << Stack.top();

    Bool IsZero(int x){
        x==0?true:false
    }
    Bool Equal(int x,int y){
        x==y?true:false
    }

Performance Analysis

Space Complexity

float rsum(float list[ ], int n){
    if(n)return rsum(list, n-1) + list[n-1];
    return list[0];
}

Total
= float list[ ] + int n + return addres
= 4 + 4 + 4 = 12n

Time Complexity

1. assignment
2. for loop (n+1)
3. return
4. conditional

float sum(float list[ ], int n){
    float tempsum= 0;     count++;    /* for assignment */
    int i;
    for (i= 0; i< n; i++){
        count++;                      /* for the "for" loop */
        tempsum+= list[i];   count++; /* for assignment */
    }
    count++;                         /* last execution of "for" */
    count++;                         /* for return */ 
    return tempsum;
}

Asymptotic Notation（O, Ω, Θ）

• Big O

  f(n) ≤ cg(n) for all n, n≥n₀
  

• Omega Ω

  f(n) ≥ cg(n) for all n, n≥n0
  

• Theta Θ

  c₁ g(n) ≤ f(n) ≤ c₂ g(n) for all n, n≥n₀
  

Fibonacci

Recursion

int fibonacci(int n) {
  
        if(n<2){
            return n;
        }
        
        if(n>=2){
            return fibonacci(n-1)+fibonacci(n-2);
        }
}

Non-Recursion（DP）

int fibonacci(long long int n) {

    for(int m=0;m<=n;m++){
        
        if(m>=2){
            c=a;
            a=b;
            b=c+b;
        }
        else if(m<2){
            a=0;
            b=1;
        }
            
    }
  
    if(n<2&&n!=0){
        return n;
    }
    else if(n>=2){
        return b;
    }
    
}

非連續子序列之兩數最大和（Struct & Sort）

Struct

    struct list {
        int value;
        int index;
    };

Sort compare

bool compare(list &s1, list &s2){
    return s1.value > s2.value;
}

Main

int main() {

    int n,m;
    list L[100000];    //struct
    
    /*---------------輸入---------------*/
    std::cin >> n;
    for(m=0;m<n;m++){
        std::cin >> L[m].value;
        L[m].index=m;
    }
    int sub_len=m;    //list長度
    
    /*-------------搜尋比對-------------*/
    if(sub_len==3){    //spical case：子序列長度=1
        std::cout << L[0].value+L[2].value;
    }
    else{   
        std::sort(L,L+sub_len,compare);    //找出前四大的數
        
        int tmp,max = -INT16_MAX;
        for(m=0;m<4;m++){    //比對是否相鄰
            for(int i=m+1;i<4;i++){
                if(abs(L[m].index-L[i].index)>1){    //比對是否相鄰
                    tmp=L[m].value+L[i].value;    //找出最大和
                    if(tmp>max){
                        max=tmp;
                    }
                }
            }
        }
        
        std::cout << max;
    }
    
   return 0;
}

參考資料：範例八 https://shengyu7697.github.io/std-sort/

課外延伸題_最大非連續子序列和（DP）

DP（Dynamic programming）

int sub_max(int* list){
    
    if(sub_len==3){
        return list[0]+list[2];
    }
    
    int temp[10005]; 
    for(int m=0;m<sub_len;m++){
        temp[m]=list[m];
    }
    
    temp[0]=list[0];
    temp[1]=list[1]>list[0]?list[1]:list[0];
    
    for(int i = 2;i<sub_len;i++){
        temp[i]=max(max(temp[i],temp[i-1]),temp[i-2]+list[i]);
    }
    
    return temp[sub_len-1];
}

Main

int main() {

    int n,m;
    int list[10005];
    
    cin >> n;
    
    for(m=0;m<n;m++){
        cin >> list[m];
    }
    sub_len=m;//list大小,global變數
    
    cout << sub_max(list);
    
   return 0;
}

加分題_奇數魔方陣

題目：http://140.121.198.41:20211/contest/6/problem/a1

int main(void) { 
    
    int square[row][column] = {0}; 
    
    int N,K;
    int r,c;    //r=row_index,c=column_index
    int r2,c2;  //儲存上一步
    cin >> N;   //space
    
    r=1;    //first_step
    c=N/2+1;    
    square[r][c]=1;
    
    for(K=2;K<=N*N;K++){
        
        r--;    //下一步
        c++;
        
        if (r < 1)r=N;    //邊界
        if (c > N)c=1;
        
        if(square[r][c]){   //重複出現
            r=r2+1;   //回到上一步
            c=c2;      
            if(r>N)r=1;   //邊界
        }
        
        c2=c;   //儲存
        r2=r;
        square[r][c]=K; //放入K
    }
    return 0; 
} 

參考資料：
https://openhome.cc/Gossip/AlgorithmGossip/OddArray.htm

Struct

typedef

Union