data stucture第一章

data stucture第一章

三月 12, 2025

Algorithm定義

須滿足下列五個criteria(標準要求)

  • Input(至少提供>=0個輸入資料)
  • Output(至少提供>=1個輸出結果)
  • Definiteness明確性(每個指令敘述必須是clear且unambiguous)
  • Finiteness有限性(Algorithm在執行有限steps後必須能夠終止)(program不具有限性)
  • Effectiveness有效性(每個指令敘述夠基本，即可被人用紙、筆追蹤/執行)
    會考哪一個不是定義:
    ex correctness?

Recursion

  • Direct Recursion直接(包含self-calling)
  • Indirect recursion間接ex: A->B->C->A
  • Tail recursion 尾端遞迴 (是Direct recursion的一種，即recursion call之下一個可執行敘述為return/end)
    ex return n*rec();//非尾端遞迴
    return rec();//為尾端遞迴

Recursion vs. Iteration(Non-Recursion)

  • 任何問題的解決必存在這兩種形式的演算法
  • 遞迴->非遞迴(有標準SOP)
  • 非遞迴->遞迴(無)

解題關鍵:記住數學上Recursion definition

輾轉相除法

gcd(A,B)=B,if(A %B)=0
gcd(A,B)=gcd(B,A %B),otherwise

Ackerman Function A(m,n)

很難算

快速冪!!!O(log(n))

數學rec:
x^n=1* x^(n/2)x^(n/2),if n=even
x^n=x x^(n/2)*x^(n/2),if n=odd
台大解:

1
2
3
4
5
6
7
int exp(int x,int n){
    int f;
    if(n%2==0)f=1;
    else f=x;
    if(n<2) return f;
    return f*exp(x*x,n/2);
}

自己寫比較好懂:

1
2
3
4
5
int exp(int x,int n){
    if(n==1) return x;
    if(n%2) return x*exp(x*x,n/2);
    return exp(x*x,n/2);
}

Hanoi河內塔

遞迴核心概念:把問題縮小
以這題為例 先拿n-1個disk然後再拿最後第n個
設有A,B,C柱
step1. n-1 disk到B柱
step2. 第n個disk放到C柱
step3. n-1 disk放到C柱
用程式實現:

1
2
3
4
Hanoi(n,from,to,Aux) // (最後面的是暫存)
step1. Hanoi(n-1,from,Aux,to); //先移動n-1個盤子
step2. move disk n from "from" to "to"
step3. Hanoi(n-1,Aux,to,from); //再把n-1個盤子移動到to

遞迴:T(n)=T(n-1)+1+T(n-1)從左至右就是step1~3
O(n)=2^n-1

觀念:
perm(a,b,c)=’a’+perm(b,c)+’b’+perm(a,c)+’c’+perm(a,b)
輪流作為head後面接剩下資料之perm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>

using namespace std;
void perm(char s[],int i,int n){
    for(int j=1;j<=n;j++){
        cout<<s[j]<<' ';
    }
    cout<<'\n';
    int j,temp;
    if(i==n){
        for(j=1;j<=n;j++){
            cout<<s[j];
        }
        cout<<'\n';
    }else{
        for(j=i;j<=n;j++){
            swap(s[i],s[j]);
            perm(s,i+1,n);
            swap(s[i],s[j]);
        }
    }
}
int main()
{
    char s[100];
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    perm(s,1,n);
    return 0;
}

缺點是資料並不會依輸入的字典序排列

BST的插入，與遍歷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>

using namespace std;
int temp;
struct node{
    int data;
    node* left;
    node* right;
};
node*first=new node;


node* findx(node* nod,int x){
    if(nod == nullptr ||(nod->right==nullptr&&nod->left==nullptr)) return nod;
    if(nod->data>x){
        if(nod->left!=nullptr&&nod->left->data!=x)return findx(nod->left,x);

    }else{
        if(nod->right!=nullptr&&nod->right->data!=x)return findx(nod->right,x);
    }
    return nod;

}

void insertx(int x){

    if(first->data==0){
        first->data=x;
        return;
    }
    node* parent=findx(first,x);
    node* ins=new node;
    if(parent->data<x) parent->right=ins;
    else parent->left=ins;
    ins->data=x;
    ins->left=nullptr;
    ins->right=nullptr;
}
void inord(node* nod){

    if(nod==nullptr)return;
    if(nod->left!=nullptr) inord(nod->left);
    cout<<nod->data<<' ';
    if(nod->right!=nullptr) inord(nod->right);
}
void post(node*nod){
    if(nod==nullptr)return;
    if(nod->left!=nullptr) post(nod->left);
    if(nod->right!=nullptr) post(nod->right);
    cout<<nod->data<<' ';
}
void pre(node*nod){
    if(nod==nullptr)return;
    cout<<nod->data<<' ';
    if(nod->left!=nullptr) pre(nod->left);
    if(nod->right!=nullptr) pre(nod->right);
}
int main()
{
    first->data=0;
    first->left=nullptr;
    first->right=nullptr;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>temp;
        insertx(temp);

    }
    inord(first);
    cout<<'\n';
    post(first);
    cout<<'\n';
    pre(first);
    return 0;
}