สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Searching
การค้นหาข้อมูลแบ่งตามลักษณะการจัดเก็บได้ 2 อย่างคือ
1. การค้นหาข้อมูลภายใน (Internal Search)
2. การค้นหาข้อมูลภายนอก (External Search)
แบ่งตามลักษณะการค้นหาได้ 2 อย่างคือ
1. การค้นหาข้อมูลตามลำดับ (Linear Search)
ซึ่งการค้นหาแบบนี้มีเทคนิค 2 อย่างคือ
1.1 Unsorted Linear Search เป็นการค้นหาข้อมูลแบบเรียงลำดับทีละตัว เริ่มตั้งแต่ข้อมูลตัวแรก ไปเรื่อย ๆ จนกระทั่งพบข้อมูลที่ต้องการ หรือจนหมดทุกตัว
Algorithm
1. กำหนดให้ ตัวนับเริ่มต้นเป็นตัวแรกของข้อมูล
2. เปรียบเทียบข้อมูล ถ้า - พบข้อมูล ทำข้อ 5 - ไม่พบข้อมูล ทำข้อ 3
3. เพิ่มค่า ตัวนับ
4. ทำซ้ำข้อ 2
5. จบ
1.2 Sorted Linear Search เป็นการค้นหาข้อมูลแบบเรียงลำดับทีละตัว เริ่มตั้งแต่ข้อมูลตัวแรก ไปเรื่อย ๆ จนกระทั่งพบข้อมูลที่ต้องการ หรือจนค่าของข้อมูลตัวถัดไปมีค่ามากกว่า ซึ่งมีเงื่อนไขว่า ข้อมูลนั้นต้องมีการจัดเรียงแล้วเท่านั้น
Algorithm
1. กำหนดให้ ตัวนับเริ่มต้นเป็นตัวแรกของข้อมูล
2. เปรียบเทียบข้อมูล ถ้า -พบข้อมูล ทำข้อ 5 -ค่าของข้อมูลที่ต้องการค้นหา < ค่าของข้อมูลที่ตำแหน่ง ตัวนับ ทำข้อ 5
3. เพิ่มค่า ตัวนับ
4. ทำซ้ำข้อ 2
5. จบ
2. การค้นหาข้อมูลทวิภาค (Binary Search)
2.1 Binary Search in Array เป็นการค้นหาข้อมูลแบบทวิภาค โดยอาศัยการแบ่งข้อมูลที่มีอยู่ออกเป็นส่วน ๆ ซึ่งต้องหาค่ากลางของข้อมูลแล้วทำการเปรียบเทียบข้อมูลจากค่ากลางนั้น และข้อมูลต้องมีการจัดเรียงแล้วเท่านั้น
Algorithm
1. หาตำแหน่งกึ่งกลางโดย ได้จาก (Lo+Hi)/2
2. เปรียบเทียบ ถ้า
2.1 พบข้อมูล ทำข้อ 4
2.2 ข้อมูลมีค่าน้อยกว่าค่ากลางให้ ค่ากลางทางซ้าย
2.3 ข้อมูลมีค่ามากกว่าค่ากลางให้ ค่ากลางทางขวา
3. ทำซ้ำข้อ 2 จนกระทั่ง ตำแหน่ง Hi=Lo
4. จบ
2.2 Binary Search Tree เป็นการค้นหาข้อมูลแบบทวิภาค ซึ่งข้อมูลจัดอยู่ในรูปแบบของ Tree ที่เป็นลักษณะของ Binary Tree
Algorithm
1. สร้าง Binary Tree
2. เปรียบเทียบ กับ Node ที่อยู่ขณะนั้น ถ้า
2.1 ถ้าพบ ทำข้อ 4
2.2 ถ้า ค่าที่ต้องการค้นหา > Node ที่อยู่ขณะนั้น ให้หา Node ทางขวา
2.3 ถ้า ค่าที่ต้องการค้นหา < Node ที่อยู่ขณะนั้น ให้หา Node ทางซ้าย
3. ทำซ้ำข้อ 2 จน Node ไม่มี Child
4. จบ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น