Tata: Created page with "ยินดีต้อนรับสู่ wiki เพื่อติว 2110211 Data Structure (By C++)
* '''โจทย์ challenge ทำไม่ได้อย..."

2019-03-07T17:20:20Z

Created page with "ยินดีต้อนรับสู่ wiki เพื่อติว 2110211 Data Structure (By C++) <br> * '''โจทย์ challenge ทำไม่ได้อย..."

New page

ยินดีต้อนรับสู่ wiki เพื่อติว 2110211 Data Structure (By C++) <br>
* '''โจทย์ challenge ทำไม่ได้อย่าไปเครียด'''
* '''สำหรับเทพ หรือคนที่ต้องการความท้าทายอย่างสุดๆ''' แนะนำโจทย์ challenge ด้านล่างสุด
ปล. ขอบคุณพื้นที่ ของ ชมรมคอมพิวเตอร์โอลิมปิก โรงเรียนอัสสัมชัญ<br><br>
'''โดย 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];
* ตัวอย่างการใช้งาน
<pre>
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;
</pre>

=== 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 [[http://www.programming.in.th/task/rev2_problem.php?pid=1027 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 [[http://www.programming.in.th/task/rev2_problem.php?pid=1121 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 มั้ง) [[http://www.programming.in.th/task/rev2_problem.php?pid=1003 LINK]]
* Plate [[http://www.programming.in.th/task/rev2_problem.php?pid=1004 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

== Operator Overloading ==

=== Overload operator< ===

=== compare class ===

=== compare function ===

== 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 [[http://www.programming.in.th/task/rev2_problem.php?pid=0019 LINK]]
* Numbers [[http://www.programming.in.th/task/rev2_problem.php?pid=0032 LINK]]
* Include [[http://www.programming.in.th/task/rev2_problem.php?pid=1057 LINK]]

2110211 data struct - Revision history

Tata: Created page with "ยินดีต้อนรับสู่ wiki เพื่อติว 2110211 Data Structure (By C++) * '''โจทย์ challenge ทำไม่ได้อย..."

Tata: Created page with "ยินดีต้อนรับสู่ wiki เพื่อติว 2110211 Data Structure (By C++)
* '''โจทย์ challenge ทำไม่ได้อย..."