สรุปเนื้อหาที่ออกสอบ
- โครงสร้างข้อมูลแบบทรี
- โครงสร้างข้อมูลแบบกราฟ
- การเรียงลำดับข้อมูล
- การค้นหาข้อมูล
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ
ชั้น (Hierarchical Relationship)ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่าง ๆ อย่างแพร่หลาย
ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูลเช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ
โครงสร้างสารบัญหนังสือ เป็นต้น
1. การท่องไปแบบพรีออร์เดอร์
(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธีNLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์
(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LNRมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
กราฟที่มีการเปลี่ยนแปลงตลอดเวลา
อาจจะใช้วิธีแอดจาเซนซีลิสต์(Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธีจัดเก็บกราฟด้วยการเก็บโหนดและ
พอยน์เตอร์ แต่ต่างกันตรงที่ จะใช้ ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
การท่องไปในกราฟ
1. การค้นหาแบบกว้าง (Breadth-first Search)
กำหนดจุดเริ่มต้น ถ้าให้เริ่มต้นที่จุด A การค้นหาจะเริ่มต้นที่โหนดประชิดของ A จนครบทุกจำนวนของโหนดประชิด
จากภาพที่ปรากฏต่อไปนี้ โหนด N1 โหนด N2 ไปเรื่อย ๆจนจบที่โหนด Nk การค้นหาแบบกว้างจะค้นหาต่อที่โหนด
ประชิดของ N1 ซึ่งเป็นโหนด ประชิดแรกของโหนด Aแบบแผนการค้นหา จะเป็นแบบเดียวกับโหนด A หลังจากเสร็จ
สิ้นการค้นหาจะดำเนินการค้นหาต่อที่ โหนด N2 จนสุดท้ายจบที่ โหนด Nk ในหารค้นหาแบบกว้างจะใช้คิวเก็บลำดับ
Sorting
- การเรียงลำดับ
- วิธีการเรียงลำดับ
- การเรียงลำดับแบบเลือก (selection sort)
- การเรียงลำดับแบบฟอง (bubble Sort)
- การเรียงลำดับแบบเร็ว (quick sort)
- การเรียงลำดับแบบแทรก (insertion sort)
- การเรียงลำดับแบบฐาน (radix sort)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น