2110211 data struct

ยินดีต้อนรับสู่ wiki เพื่อติว 2110211 Data Structure (By C++)

• โจทย์ challenge ทำไม่ได้อย่าไปเครียด
• สำหรับเทพ หรือคนที่ต้องการความท้าทายอย่างสุดๆ แนะนำโจทย์ challenge ด้านล่างสุด

ปล. ขอบคุณพื้นที่ ของ ชมรมคอมพิวเตอร์โอลิมปิก โรงเรียนอัสสัมชัญ

โดย TATA201201 Gr.J 96 CP 39

Syllabus Schedule

• วันที่ หัวเรื่อง
• 28 และ 30 พ.ย. Introduction to C++, Intro to STL
• 4 และ 6 พ.ย. Pointer, <vector>, <pair>, basic <map>, Using iterator, sort(), find(),
• 11 และ 13 พ.ย. Composition of data structure, e.g., vector of map.
• 18 และ 20 พ.ย. <deque>, <set>, x 3 / 2 problem
• 25 และ 27 พ.ย. <map> with custom sort, overloading of <, custom sort
• 26 และ 28 พ.ย. Class in C++
• 2 และ 4 ธ.ค. Implementing CP::vector
• 9 และ 11 ธ.ค. Stack, Queue, Implementing CP::deque
• 16 และ 18 ธ.ค. Priority Queue, Binary Heap, Implementing CP::priority_queue
• 24 ธ.ค. Mid-term Exam
• 30 ธ.ค. และ 1 ม.ค. หยุดวันปีใหม่
• 6 และ 8 ม.ค. Hash
• 13 และ 15 ม.ค. Implementing CP::unordered_sort
• 20 และ 22 ม.ค. หยุดกีฬามหาวิทยาลัย
• 27 และ 29 ม.ค. Linked List, Doubly Linked List
• 3 และ 5 ก.พ. Implementing CP::list, Binary Tree
• 10 และ 12 ก.พ. Binary Tree, Binary Search Tree
• 17 และ 19 ก.พ. AVL Tree, implementing CP::map
• 25 ก.พ. Final Exam

Midterm

• โปรดอ่าน
  • หัดอ่าน reference ที่อาจารย์แจก มันมีประโยชน์
  • ใช้เป็นอันเดียว อันอื่นก็น่าจะเป็นได้ไม่ยาก มันเหมือนกันหมดแหละ

STL Containers

vector

• Extendable array
• constructor
  • vector<T> v;
  • vector<T> v(size_t size); // สร้างให้เริ่มต้นมี size ช่อง
  • vector<T> v(iterator begin, iterator end); // สร้างโดยแทรกข้อมูลจาก begin -> end
• Function ที่สำคัญ
  • v.size(); // ขนาดที่ array สามารถจุได้
  • v.push_back(T value); // ต่อท้าย array >> constant time
  • v.pop_back(); // ลบตัวทุดท้ายออก >> constant time
  • v.insert(iterator, T value); // แทรกลงตำแหน่งใดๆตาม iterator >> ใช้เวลาแปรตามตำแหน่ง
    • v.insert(iterator place, iterator begin, iterator end); // แทรกลงตำแหน่ง place โดยเอาข้อมูลจาก begin -> end มาแทรก
  • v.erase(iterator) // ลบข้อมูล
    • v.erase(iterator first, iterator last); // ลบข้อมูลเป็นช่วง
• Iterator
  • vector<T>::iterator it;
  • v.begin();
  • v.end();
  • access ที่ตำแหน่งใดๆ v.begin()+5; มีค่าเหมือน v[5];
• ตัวอย่างการใช้งาน

vector<int> v;
for(int i=0;i<10;i++) v.push_back(i);
v.insert(v.begin(),999);
v.pop_back();
for(size_t i=0;i<v.size();i++) cout << v[i] << " " ;
cout << endl;

pair

• เก็บข้อมูลเป็นคู่อันดับ
• Constructor
  • pair<T1, T2> p(T1 val, T2 val);
  • make_pair(val1, val2);
• Access
  • pair<int,int> v1(15,20);
  • cout << v1.first() << " " << v1.second(); // ได้ข้อมูลตัวแรก 15 และข้อมูลตัวหลัง 20 ตามลำดับ

set

• Constructor
  • set<T> s;
  • set<T> s(iterator begin, iterator end); // กำหนดค่าเริ่มต้นให้ set
• Function ที่ควรรู้
  • s.insert(T x); // แทรก คืนค่าเป็น pait<iterator,bool> บอกว่า แทรกตำแหน่งไหน และได้แทรกรึป่าว (เผื่อมีซ้ำ)
  • s.erase(T x); // ลบ
    • s.erase(iterator) // ลบตัวนั้น
    • s.erase(iterator begin, iterator end); // ลบเป็นช่วง
  • s.find(T x); // ค้นหา
  • s.size(); // หาขนาดของ set
• Iterator
  • set<T>::iterator it;
  • s.begin(); s.end(); // เริ่มต้น สิ้นสุด
  • ++it; ได้ it+5; ไม่ได้
• ตัวอย่างการใช้งาน
  • เก็บข้อมูลที่ไม่ต้องการตัวซ้ำ
  • หาคำที่แตกต่างกัน

map

• Constructor
  • map<KeyType, MappedType> m;
• Function ที่ควรรู้
  • m.insert(make_pair(KeyType Kval, MappedType Mval)); // แทรก
    • แทรกอีกแบบ m[KeyType Kval] = MappedType Mval; // มองเป็นอาเร
  • m.erase(iterator);
    • m.erase(iterator begin, iterator end);
• Iterator
  • map<T,T>::iterator it;
  • m.begin(); m.end(); // ข้อมูลเรียงลำดับ
  • it คืนค่าได้ pointer to pair เรียกใช้งานได้แบบ it->first; it->second;
• ตัวอย่างการใช้งาน
  • การนับคำซ้ำ
• SMS [LINK]

stack

• Last In First Out เข้าหลังออกก่อน
• Constructor
  • stack<T> s;
• Function ที่ควรรู้
  • s.push(T value); // ใส่ลง stack
  • s.pop(); // เอาข้อมูลออกจาก stack โดยไม่อ่าน
  • s.top(); // อ่านข้อมูลบนสุดของ stack
  • s.size(); // จำนวนข้อมูลใน stack
• ประโยชน์
  • เช็ควงเล็บ
  • แปลงนิพจน์ Infix > Postfix
  • คำนวณนิพจน์แบบ Postfix
  • การค้นหาตามแนวลึก Breadth First Search
• Three paren [LINK]

Queue

• First In First Out เข้าก่อนออกก่อน
• Constructor
  • queue<T> q;
• Function ที่ควรรู้
  • q.push(T value); // ใส่ลง queue
  • q.pop(); // เอาข้อมูลออกจาก queue โดยไม่อ่าน
  • q.front(); // อ่านข้อมูลต้น queue
  • q.back(); // อ่านข้อมูลท้าย queue
  • q.size(); // จำนวนข้อมูลใน queue
• ประโยชน์
  • จัดลำดับการทำงาน
  • การค้นหาตามแนวกว้าง Breadth First Search
  • Radix Sort
• Nugget Number (คล้าย *3/2 มั้ง) [LINK]
• Plate [LINK]

Deque

• Double Ended Queue คล้าย Vector + Stack + Queue

Priority Queue

• Default > Max ออกมาก่อนเสมอ
• Constructor
  • priority_queue<T> pq;
• Function ที่ควรรู้
  • pq.push(T value); // ใส่ลง queue
  • pq.pop(); // เอาข้อมูลออกจาก queue โดยไม่อ่าน
  • pq.top(); // อ่านข้อมูลต้น queue
  • pq.size(); // จำนวนข้อมูลใน queue
• ประโยชน์
  • หาตัวที่มากสุด k อันดับ
  • เรียงลำดับข้อมูล
  • Huffman Encoding

Implementing Data Structure

vector

• You can find it in the slide of this course.

Stack

• You can find it in the slide of this course.

Queue

• You can find it in the slide of this course.

priority queue

• -- ยกยอดไป final --

โจทย์ Challenge

• Perket [LINK]
• Numbers [LINK]
• Include [LINK]