Introduction to Data Structures

Author: Pakin Olanraktham

Source	Resources
USACO.guide	Introduction to Data Structures

โครงสร้างข้อมูล (Data Structure) คือ วิธีการจัดเก็บและจัดระเบียบข้อมูล ในหน่วยความจำของคอมพิวเตอร์ เพื่อให้สามารถเข้าถึง จัดการ หรือประมวลผลข้อมูลได้อย่างมีประสิทธิภาพและเหมาะสมกับงานที่ต้องการ

ในภาษา C++ เรามีสิ่งที่เรียกว่า STL หรือ Standard Template Library ซึ่งเป็น Built-in Library ให้เราสามารถใช้กันได้สะดวก โดยสิ่งที่เราต้องเขียนในโค้ดเพื่อที่จะใช้คือ

#include <bits/stdc++.h>

ไว้บรรทัดแรกของโปรแกรม

แล้วโค้ดบรรทัดนั้น ทำหน้าที่อะไร? โค้ดนั้น เปรียบเสมือนการ #include ทุก Library ที่จำเป็นมาให้ แปลว่า เราไม่ต้อง #include <iostream> อีกต่อไปแล้ว ให้ใช้ #include <bits/stdc++.h> เพียงอันเดียวเลย

แล้วถ้าหากเราต้องการใช้ Data Structure ใน STL ล่ะ เราสามารถประกาศได้ด้วยโครงสร้างนี้

vector <int> v;

ซึ่งโค้ดดังกล่าว เป็นการประกาศตัวแปรชื่อ v ซึ่งเป็นโครงสร้าง vector ที่เก็บ int

Static Array

ใน STL เรามี Array ให้ใช้ แต่ปกติไม่นิยมใช้กัน เราเลยจะมีกล่าวถึง Array ที่เราเคยเรียนมาแล้วเพิ่มเติม

int a[1000];

โค้ดนี้ ประกาศ Array ของ int ยาว 1000 แต่เรารู้ว่าการประกาศ Array ภายในฟังก์ชัน เช่น main จะไม่ได้ทำให้แต่ละค่าเป็น 0

ใน STL เรามีฟังก์ชันให้ใช้ คือ memset() ซึ่งมีวิธีการใช้ดังนี้

memset(a, 0, sizeof(a));

ซึ่งจะทำให้ทุกค่าใน a เป็น 0 (ฟังก์ชันนี้ใช้ได้เฉพาะการ set ค่าให้เป็น 0 หากต้องการค่าอื่น สามารถทำได้ด้วยการ Loop ปกติ)

Dynamic Array (Vector)

Vector ในภาษา C++ ทำหน้าที่ได้เหมือน Array ทุกประการ เพียงแต่มีสิ่งที่เพิ่มมา คือความสามารถในการเพิ่มและลดขนาด เราสามารถ push หรือ pop ค่าเข้าไปใน vector ได้ ด้วยเวลา \(\mathcal{O}(1)\)

มีคำสั่งที่ควรรู้ เช่น

.push_back() เป็นการ push ค่าบางอย่าง เข้าไปที่ท้าย vector
.pop_back() เป็นการนำค่าที่อยู่ด้านหลังสุดของ vector ออก แต่หาก vector ว่างอยู่ จะเกิด Error
.empty() เป็นการคืนค่าว่า vector ว่างไหม ซึ่งหากว่างจะคืนค่า true (1) แต่จะคืนค่า false (0) หากมีสมาชิกอยู่
.size() จะคืนค่าขนาดของ vector (จะไม่ได้คืนค่าเป็น int ควรเปลี่ยนเป็น int ก่อนโดย (int) (v.size()))
.back() จะคืนค่าสมาชิกตัวสุดท้ายของ vector แต่หาก vector ว่าง จะเกิด Error

vector <int> v;
for (int i = 0; i < 10; i++) v.push_back(i); // push ค่าตั้งแต่ 0 ถึง 9 เข้าไปใน vector
for (int i = 0; i < 10; i++) cout << v[i] << ' '; // จะส่งออก 0 1 2 3 4 5 6 7 8 9
cout << '\n' << v.size() << '\n'; // จะส่งออก 10
while (!v.empty()) { // เช็คว่า vector ว่างไหม
    cout << v.back() << ' '; // ส่งออกตัวท้ายสุดของ vector
    v.pop_back(); // นำค่าท้ายสุดออก
} // จะส่งออก 9 8 7 6 5 4 3 2 1 0

นอกจากนี้ เราสามารถประกาศ vector ด้วยขนาดหรือค่าที่ต้องการได้ โดย

vector <int> v(100); // จะประกาศ vector v ขนาด 100
vector <int> u(n); // จะประกาศ vector u ขนาด n
vector <int> x{1, 2, 3, 4, 5}; // ประกาศ vector ที่มีสมาชิกคือ 1 2 3 4 5

แล้วถ้าเกิดต้องการประกาศ vector หลายมิติล่ะ

เราสามารถนำ vector <int> ไปใส่ใน <> ของ vector อีกตัวได้ เนื่องจากภายใน <> จะเป็นตัวแปรหรือโครงสร้างข้อมูลชนิดใดก็ได้

vector <vector <int>> m; // ประกาศ 2D vector
vector <vector <int>> q(10, vector <int>(10)); // ประกาศ 2D vector ขนาด 10 x 10

Iterating

หนึ่งในวิธีการลูปไปใน Array คือ

for (int i = 0; i < v.size(); i++) {
    // ...
}

ใน STL เราก็มีสิ่งที่คล้ายกับ pointer ด้วย เรียกว่า iterator ซึ่งจะเป็นการชี้ไปที่สมาชิกตัวหนึ่งในโครงสร้าง STL

เช่น v.begin() จะคืนค่าเป็น iterator ที่ตำแหน่งเริ่มต้นของ vector (index 0) ส่วน v.end() จะคืนค่าเป็น iterator ตำแหน่งที่มากกว่าตัวสุดท้ายของ vector อยู่ 1

for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { // check ว่าเกินตัวสุดท้ายของ vector หรือยัง
    // ...
}

แต่เราสามารถใช้ auto แทนการเขียน vector<int>::iterator ได้

for (auto it = v.begin(); it != v.end(); it++) { // check ว่าเกินตัวสุดท้ายของ vector หรือยัง
    // ...
}

นอกจากนี้ เราสามารถลูปไปในทุกตัวของ vector ได้ โดย

for (auto &e : v) {
    // ...
}

โค้ดดังกล่าว จะลูปทุกค่าใน vector v โดยมีตัวแปรที่ชื่อ e เป็นตัวแทนของสมาชิกใน vector

สังเกตว่า หากเราใช้ auto &e : v เวลาเราเปลี่ยนแปลงค่าใดๆ ของ e ในลูป ค่านั้นใน vector จะเปลี่ยนด้วย แต่หากใช้ auto e : v การเปลี่ยนแปลงค่าของ e จะไม่ส่งผลใดๆ ต่อ vector เช่น

vector <int> x;
for (int i = 1; i <= 5; i++) x.push_back(i); // ให้ vector x มีสมาชิกคือ 1 2 3 4 5
for (auto e : x) e = 1;
for (int i = 0; i < 5; i++) cout << x[i] << ' '; // จะส่งออก 1 2 3 4 5
for (auto &e : x) e = 1;
cout << '\n';
for (int i = 0; i < 5; i++) cout << x[i] << ' '; // จะส่งออก 1 1 1 1 1

บทเรียนนี้ยังไม่สมบูรณ์

หากใครต้องการช่วยเหลือ สามารถส่ง Pull Request มาได้ทาง GitHub