Max Coding blog

基礎資料結構(Data Structure)-C++

C++ Data structure
2021/08/28

array 陣列

陣列一個基礎的資料結構，為一種靜態的資料結構(static data structure)，在使用前須要先宣告大小。 

1
2
3
4
int main(){
    int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    return 0;
}
陣列可以使用索引(index)來提取或儲存資料。 
1
2
3
4
5
6
7
8
9
10
int main(){
    int arr[10];
    for(int i = 0;i < 10;i++)
        arr[i] = i*10;
    for(int i = 0;i < 10;i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}
前面的指標中可以動態分配記憶體，而陣列的記憶體也可以動態分配，叫做動態陣列，當我們使用完陣列之後將會把記憶體歸還，而此時這些記憶體的值將不可預測，有可能改變，也有可能不變。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int main(){
    int * arr = new int[10];//動態配置記憶體
    for(int i = 0;i < 10;i++)
        arr[i] = i;
    for(int i = 0;i < 10;i++)
        cout << arr[i] << " ";
    delete [] arr;//將記憶體歸還
    cout << '\n' << "==============" << endl;
    for(int i = 0;i < 10;i++)
        cout << arr[i] << " ";

    return 0;
}
## vector（向量） vector是一種動態資料結構(dynamic data structure)，不需要事先宣告大小，運用上非常方便。 1. 首先運用vector前要先引入一個標頭檔(header file)#include<vector>，接著進行宣告。 
1
2
3
4
5
6
7
8
#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> vec;

    return 0;
}
2. push_back() 將值加到vector的尾端，pop_back() 將vector尾部的值刪去，vector有自動擴大空間的機制，所以當push_back的時候如果空間不夠裝，vector會自動安排記憶體，但這麼做時間複雜度很高，所以通常在使用前會先預設一些記憶體位置給vector，我們會使用reserve()這個函式。 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> vec;
    vec.reserve(128);
    for(int i = 0;i < 10;i++)
        vec.push_back(i);
    for(int i = 0;i < vec.size();i++)
        cout << vec[i] << " ";//ouput = 0 1 2 3 4 5 6 7 8 9

    return 0;
}
3. vector有許多成員函式，使我們在使用vector時可以更方便、更快速，接著要使用insert將資料插入vector的某一個位置 syntax :vec.insert(const_iterator position, const value_type& val) 
1
2
3
4
5
6
7
8
9
10
11
int main(){
    vector<int> vec;
    vec.reserve(128);
    for(int i = 0;i < 10;i++)
        vec.push_back(i);
    vec.insert(vec.begin()+3,1000);
    for(int i = 0;i < vec.size();i++)
        cout << vec[i] << " ";//output = 0 1 2 1000 3 4 5 6 7 8 9

    return 0;
}
4. 還有一個函式能幫助我們進行刪除特定位置的資料 syntax :vec.erase (const_iterator position); 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> vec;
    vec.reserve(128);
    for(int i = 0;i < 10;i++)
        vec.push_back(i);
    vec.erase(vec.begin()+1);
    vec.erase(vec.begin()+3,vec.begin()+6);
    for(int i = 0;i < vec.size();i++)
        cout << vec[i] << " ";//output = 0 2 3 7 8 9

    return 0;
}
5. 在C++11時有新的函式emplace_back()、emplace()、emplace_front，emplace相關函式可以減少記憶體拷貝和移動，也就是避免產生臨時變數。 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> vec;
    for(int i = 0;i < 10;i++)
        vec.emplace_back(i);
    vec.emplace(vec.begin()+5,2021);
    for(int i = 0;i < vec.size();i++)
        cout << vec[i] << " ";

    return 0;
}
6. 其他vector的使用，搭配pair。 
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
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main(){
    vector<pair<int,char>> vec;
    for(int i = 0;i < 10;i++)
        vec.emplace_back(make_pair(i,65+i));

    for(int i = 0;i < vec.size();i++)
        cout << vec[i].first << " " << vec[i].second << endl;
    /*ouput:
        0 A
        1 B
        2 C
        3 D
        4 E
        5 F
        6 G
        7 H
        8 I
        9 J
        */
    return 0;
}
## queue（佇列） 須加標頭檔#include<queue> 1. queue就像是在排隊一樣，所以有一個概念就是 FIFO(First In First Out)，了解觀念後我們可以開始進行使用它，首先加入資料和刪除資料可以使用push()、pop()，接著queue有成員函式幫助queue的使用，back()：得到尾巴的值，front()：得到頭的值 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <queue>
using namespace std;
int main(){
    queue<int> q;
    for(int i = 0;i < 10;i++)
        q.push(i);
    for(int i = 0;i < 10;i++){
        cout << q.front() << " ";
        q.pop();
    }

    return 0;
}
2. queue也有emplace() 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <queue>
using namespace std;
int main(){
    queue<int> q;
    q.emplace(1);
    q.emplace(10);
    q.emplace(100);
    auto l = q.size();
    for(int i = 0;i < l;i++){
        cout << q.front() << endl;
        q.pop();
    }

    return 0;
}
## stack（堆疊） 1. stack就像是堆盤子一樣，一個一個往上堆，而stack的概念就和queue相反，stack的概念是LIFO(Last In First Out)，觀念了解後就可以來使用它了，stack的資料放入和移除的方式也是使用push() and pop()，接著我們可以使用top()來提取stack最上方的元素。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <stack>
using namespace std;
int main(){
    stack<int> s;
    for(int i = 0;i < 10;i++)
        s.push(i);
    auto l = s.size();
    for(auto i = 0;i < l;i++){
        cout << s.top() << " ";
        s.pop();
    }

    return 0;
}
2. stack也可以使用emplace，使用方式與queue極為相似，這裡就不演示了。 ## set（集合） 此處的set可與數學裡的集相互呼應，接著要介紹使用方式，要將資料加入set可用insert()，若要移除則可以使用erase()，還有一個成員函式叫count()，可以運用此函式來判斷一個數是否在此集合裡，回傳值為布林值。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <set>
using namespace std;
int main(){
    set<int> my_set;
    my_set.insert(100);
    my_set.insert(200);
    my_set.insert(300);

    my_set.erase(100);
    cout << my_set.count(100) << endl;//不存在輸出0
    cout << my_set.count(200) << endl;//存在輸出1

    return 0;
}
## map map就像是python的dict，map就像一個對照表，一個key對上一個value，可以用中括號[]來得到對應的值，map也可以使用count()檢查某個值是否有對應值。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <map>
using namespace std;
int main(){
    map<int,string> m;
    m[1] = "one";
    m[2] = "two";
    m[3] = "three";
    m[4] = "four";
    cout << m.count(1) << endl;//存在輸出1
    cout << m.count(5) << endl;//存在輸出0

    cout << m[2] << endl;//output = two
    cout << m[3] << endl;//output = three

    return 0;
}

by 中和高中 吳振榮
CATALOG
  1. 1. array 陣列
    1. 1.0.0.1. by 中和高中 吳振榮
Total : 31
2023
2021
C++ OOP CSS web dev HTML Linux Pytorch Machine Learning TensorFlow2 Python Scikit Learn TensorFlow1 Math theorem algorithm Data structure Transfer Learning APCS TensorFlow