Page 17 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 17
ขั้นต อนว ิธีก ารค ้นหาข้อมูล 15-7
ข้อมูลจ ัดเก็บในร ูปแบบล ิงค์ล ิสต์
23 34 49 54 56
ภาพที่ 15.3 การจ ดั เก็บข ้อมูลแบบลงิ คล์ ิสต์
การค้นหาข้อมูลตามโครงสร้างแบบเชิงเส้นน้ีรูปแบบน้ีจะใกล้เคียงกับการค้นหาในชีวิตประจ�ำวัน เช่น
การค้นหาตั้งแต่รายการแรกจนถึงรายการสุดท้าย หรือการค้นหาแบบประมาณการว่าข้อมูลน่าจะอ ยู่ท่ีตรงไหนแล้วเร่ิม
หาจากต ำ� แหนง่ น น้ั เชน่ หาเบอรโ์ ทรศพั ทข์ องนายส มชาย จากสมดุ โทรศพั ท์ ซ งึ่ จะต อ้ งประมาณวา่ “ส” นา่ จ ะอ ยปู่ ระมาณ
ไหน แล้ ว เ ปิดไ ปท่ีหน้า น้ั น แล้ว ห าน าย สม ช ายต่อไ ป ขั้ นต อน วิธี การ ค้ นห า ข้อ มูลท่ี คร อ บค ลุมใ น
ร ูปแบบน ้ีประกอบด ้วย
- การค ้นหาแ บบบ รูทฟอร์ซ (Bruteforce search)
- การค ้นหาแบบเรียงล �ำดับ (Sequential search)
- การค ้นหาแ บบท วิภาค (Binary search)
- การค ้นหาแบบก ระโดด (Jump search)
- การค้นหาแบบการประมาณค่าในช ่วง (Interpolation search)
- การค ้นหาแ บบฟ ิโบนักซี (Fibonacci search)
2. โครงสรา้ งก ารจัดเกบ็ ข อ้ มูลแ บบไ ม่เชงิ เส้น
โครงสร้างการจัดเก็บข้อมูลประเภทนี้ได้แก่ โครงสร้างแบบต้นไม้ กราฟ ซึ่งการเข้าถึงข้อมูลท่ีต้องการ จะมี
ความซับซ้อนก ว่าร ูปแบบง่าย ตัวอย่างโครงสร้าง เช่น
ข้อมูล : 53, 34, 56, 49, 54
ตัวอย่างโครงสร้างแบบต้นไม้ด ังภาพที่ 15.4
53 56
34 49
54
ภาพที่ 15.4 การจ ดั เกบ็ ข้อมลู โครงสรา้ งแบบต้นไม้
