DTS 11-16-09-2552

สรุปเนื้อหาบทเรียน "Data Structure"

เรื่อง Searching

การค้นหาข้อมูล searching แบ่งเป็น 2 ประเภท

1.การค้นหาข้อมูลแบบภายใน

2.การค้นหาข้อมูลแบบภายนอก

การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ (Linear)

ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ มีวิธีโดยการนำข้อมูลที่ต้องการหามาเปรียบเทียบกับข้อมูลในแถวลำดับ ถ้าค่าข้อมูลที่ต้องการหาไม่ตรงกับค่าข้อมูลในแถวลำดับก็ทำการค้นหาไปเรื่อยๆ จนเจอค่าข้อมูลที่ต้องการจึงจะหยุดการค้นหา หรือจะหยุดการค้นหาก็ต่อเมื่อไม่พบค่าข้อมูล

การค้นหาแบบเซนทินัล (Sentinel)

มีลักษณะเช่นเดียวกับการค้นหาแบบเชิงเส้น แต่การค้นหานั้นเป็นการเปรียบเทียบค่าน้อยกว่าการค้นหาแบบเชิงเส้น มีวิธีโดยการเพิ่มพื้นที่ที่เก็บข้อมูลอีก 1 ที่ แล้วนำข้อมูลที่ต้องการค้นหาไปใส่ไว้ที่ต้น หรือท้ายอาเรย์ แล้วทำการตรวจสอบ ถ้าตำแหน่งที่พบเท่ากับ n-1 แสดงว่าหาข้อมูลไม่พบ นอกนั้นถือว่าพบข้อมูลที่ต้องการค้นหา

การค้นหาแบบไบนารี (Binary Search)

จะใช้กับข้อมูลที่เรียงลำดับแล้วเท่านั้น โดยแบ่งข้อมูลออกเป็น 2 ส่วน การค้นหาเป็นวิธีค้นหาที่ไปยังค่ากลางเพื่อตรวจสอบหรือเปรียบเทียบว่าใช่ข้อมูลที่ต้องค้นหาหรือไม่ และจะละทิ้งข้อมูลส่วนหน้าหรือส่วนหลังขึ้นอยู่กับว่าข้อมูลที่ต้องการค้นหามีค่ามากกว่า หรือน้อยกว่าข้อมูลค่ากลาง

DTS 10-09-09-2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Graph (ต่อ) และ Sorting

การท่องไปในกราฟ

1.การค้นหาแบบกว้าง จะมีการกำหนดจุดเริ่มต้น แล้วท่องไปยังโหนดประชิดของจุดเริ่มต้นไปเรื่อยๆจนครบทุกโหนด

- การค้นหาแบบกว้าง ในกราฟไม่มีทิศทาง โหนดที่พบมีได้หลายรายการแล้วแต่ลำดับของโหนดประชิดที่ได้จัดเรียงไว้

- การค้นหาแบบกว้าง ในกราฟมีทิศทาง การค้นหาโหนดทำได้ง่ายขึ้น โดยใช้คิวเก็บลำดับของโหนดประชิด และใช้ตารางเก็บค่าโหนดประชิด

2.การค้นหาแบบลึก ต้องมีการกำหนดจุดเริ่มต้นสำหรับเยี่ยมเป็นจุดแรก มีหลักการคล้ายกับแบบลำดับของทรี

กราฟมีน้ำหนัก คือ กราฟที่ทุกเอดจ์มีค่าน้ำหนักกำกับ ค่าน้ำหนักนี้อาจหมายถึงระยะทาง เวลา เป็นต้น ใช้แก้ปัญหา ดังนี้

1.การสร้างต้นไม้ทอดข้ามน้อยที่สุด มีขั้นตอนดังต่อไปนี้

- เรียงเอดจ์ตามน้ำหนัก

- สร้างป่าที่มีแต่ต้นไม้ว่าง

- เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุด และไม่เคยถูกเลือก ถ้าค่าซ้ำกันให้เลือกมา 1 เส้น

- พิจารณาเอดจ์ที่จะเลือกมาประกอบเป็นต้นไม้ทอดข้าม แต่ห้ามเกิดวงรอบ ถ้าเกิดตัดทิ้ง

- ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ

2.การหาเส้นทางที่สั้นที่สุด

ข้อกำหนด

เซต S เก็บโหนดที่ผ่านได้และมีระยะทางจากจุดเริ่มต้นสั้นสุด

ให้ W แทนโหนดนอกเซต

ให้ D แทนระยะทาง

ขั้นตอนการทำงาน

- เซต S คือจุดเริ่มต้น

- คำนวณหาระยะทางจากโหนดเริ่มต้นไปยังทุกโหนด โดยยอมให้โหนดในเซต S เป็นทางผ่าน

*** ถ้าโหนดในเซต S ที่เป็นทางผ่านมีมากกว่า 1 ให้เลือกระยะทางที่สั้นที่สุดไปใส่ใน D

- เลือกโหนด W ที่ห่างจากจุดเริ่มต้นน้อยที่สุดไปไว้ใน S

Sorting

การเรียงลำดับ ช่วยในการค้นหาข้อมูลหรือสิ่งของต่างๆมีความง่ายมากยิ่งขึ้น ทำให้เป็นระเบียบแบบแผน เกิดประสิทธิภาพในการทำงาน

การเรียลำดับอย่างมีประสิทธิภาพต้องคำนึงถึง

- เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม

- เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงาน

- จำนวนเนื้อที่ในหน่วยความจำ

วิธีการเรียงลำดับ

วิธีการเรียงลำดับสามารถแบ่งออกได้ 2 วิธี

1.การเรียงลำดับแบบภายใน เป็นการเรียงลำดับข้อมูลที่อยู่ในหน่วยความจำหลัก เวลาที่ใช้จะคำนึงถึงเวลาที่ใช้เปรียบเทียบและเลื่อนข้อมูล

2.การเรียงลำดับแบบภายนอก เป็นการเรียงลำดับข้อมูลที่อยู่ในหน่วยความจำสำรอง เวลาที่ใช้จะคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูล

การเรียงลำดับแบบเลือก

เป็นวิธีที่ง่าย แต่เสียเวลาในการจัดเรียงนาน โดยจะทำการเลือกข้อมูลมาเก็บไว้ตามตำแหน่งที่กำหนด คือ กำหนดให้เรียงข้อมูลจากค่าน้อยไปหาค่ามาก ก็จะทำการเลือกข้อมูลตัวที่มีค่าน้อยที่สุดมาอยู่ที่ตำแหน่งแรกสุด และค่าที่อยู่ตำแหน่งแรกก็จะมาอยู่แทนที่ค่าน้อยสุด แล้วทำการเลือกไปเรื่อยๆ จนครบทุกค่า ค่าที่ได้ก็จะเรียงจากน้อยไปหามาก

การเรียงลำดับแบบฟอง

เป็นการเรียงลำดับโดยเปรียบเทียบข้อมูลที่อยู่ติดกัน โดยจะทำการเปรียบเทียบคู่ไหนก่อนก็ได้ คือ ถ้าข้อมูลอยู่ในตำแหน่งที่ไม่ถูกต้องก็จะทำการสลับตำแหน่งกัน การเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมากนัก นิยมใช้เนื่องจากเข้าใจง่าย

การเรียงลำดับแบบเร็ว

เป็นวิธีที่ใช้เวลาน้อย เหมาะกับข้อมูลที่มีจำนวนมาก โดยจะเลือกข้อมูลมาหนึ่งค่ามาเป็นค่าหลัก ถ้าเป็นการเรียงจากค่าน้อยไปหาค่ามาก แล้วให้ตำแหน่งที่ 1 เป็นค่าหลัก ทำการเปรียบเทียบจากตำแหน่งท้ายไปเรื่อยๆ จนเจอค่าที่น้อยกว่าค่าหลัก แล้วทำการสลับตำแหน่งกัน หลังจากสลับตำแหน่งให้นำค่าหลักเปรียบเทียบกับข้อมูลตำแหน่งที่ 2,3 จนพบข้อมูลที่มีค่ามากกว่าค่าหลักแล้วทำการสลับตำแหน่งกัน ทำลักษณะนี้เรื่อยๆจนข้อมูลเรียงถูกต้อง

การเรียงลำดับแบบแทรก

เป็นวิธีที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต โดยทำการเปรียบเทียบข้อมูลในเซต กับข้อมูลที่ต้องการแทรก ถ้าเรียงจากค่าน้อยไปหาค่ามาก จะต้องให้ข้อมูลที่มีค่าน้อยอยู่ก่อนหน้าข้อมูลที่มีค่ามาก

การเรียงลำดับแบบฐาน

เป็นวิธีที่พิจารณาเลขที่ละหลัก โดยจะพิจารณาเลขหลักหน่วยก่อน แล้วทำการจัดเรียงข้อมูลทีละตัวตามกลุ่มหมายเลข จากนั้นนำข้อมูลที่จัดเรียงในหลักหน่วยมาจัดเรียงในหลักสิยต่อไปเรื่อยๆจนครบทุกหลัก ก็จะได้ข้อมูลที่ต้องการ การเรียงลำดับแบบฐานไม่ซับซ้อน แต่ใช้เนื้อที่ในหน่วยความจำมาก

DTS 09-02-09-2552

สรุปเนื้อหาบทเรียน "Data Structure"

เรื่อง Tree (ต่อ) และ Graph

เอ็กซ์เพรสชั่นทรี
เป็นการนำนิพจน์มาเก็บยังโครงสร้างทรี โดยแต่ละโหนดจะเก็บตัวดำเนินการ (Operator) และตัวถูกดำเนินการ (Operand) ซึ่งตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ ส่วนตัวดำเนินการจะเก็บอยู่ที่โหนดกิ่ง แต่ต้องคำนึงถึงความสำคัญของเครื่องหมายตามลำดับด้วย คือ
-ฟังก์ชั่น
-วงเล็บ
-ยกกำลัง
-เครื่องหมายหน้าเลขจำนวน
-คูณ หาร
-บวก ลบ

***ถ้ามีความสำคัญในระดับเดียวกันให้ทำจากซ้ายไปขวา

ไบนารีเซิร์ซทรี
ค่าของโหนดรากจะมีค่ามากกว่าโหนดย่อยทางด้านซ้าย และมีค่าน้อยกว่าหรือเท่ากับโหนดย่อยทางด้านขวา

การเพิ่มโหนดในไบนารีเซิร์ซทรี ถ้าทรีว่างโหนดที่เพิ่มจะเป็นโหนดราก ถ้าทรีไม่ว่างต้องทำการตรวจสอบโหนดใหม่ว่ามีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก

***ถ้ามีค่ามากกว่าหรือเท่ากันจะนำโหนดที่เพิ่มไปเพิ่มยังทรีย่อยด้านขวา แต่ถ้ามีค่าน้อยกว่าจะนำไปเพิ่มที่ทรีย่อยด้านซ้าย

การดึงโหนดในไบนารีเซิร์ซทรี ต้องทำการค้นหาตำแหน่งที่ต้องการดึงก่อนว่าอยู่ตำแหน่งใดแล้วต้องรู้ด้วยว่าโหนดแม่ของโหนดนั้นคือโหนดไหน จึงจะสามารถทำการดึงได้ แต่เมื่อดึงโหนดออกแล้ว ทรีนั้นต้องคงสภาพเนไบนารีเซิร์ซทรีเหมือนเดิม

วิธีการดึงโหนดออก แยกได้ 3 วิธี

1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลยเพราะไม่มีผลกระทบต่อโหนดอื่นๆ แล้วเป็นวิธีที่ง่ายที่สุด

2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน

3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออก

***ถ้าเลือกทรีย่อยด้านซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดมาแทน แต่ถ้าเลือกทรีย่อยด้านขวาต้องเลือกโหนดที่มีค่น้อยที่สุดมาแทน

Graph

เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น ประกอบด้วยกลุ่มของสิ่งสองสิ่ง คือ

1.โหนด แทนด้วย N

2.เส้นเชื่อมระหว่างโหนด แทนด้วย E

*** กราฟที่มีเส้นเชื่อมระหว่างโหนดที่ไม่มีลำดับ จะเรียกกราฟนั้นว่า กราฟแบบไม่มีทิศทาง

ส่วนกราฟที่มีเส้นเชื่อมระหว่างโหนดที่มีลำดับ จะเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง หรือเรียกว่า ไดกราฟ

ในการเขียนกราฟสิ่งที่สนใจจะถูกแทนด้วยจุด หรือ วงกลม ที่มีชื่อข้อมูลกำกับ ส่วนเอ็จจะแทนด้วยเส้นหรือเส้นโค้ง

กราฟแบบมีทิศทางเส้นเอ็จต้องมีลูกศรกำกับแสดงลำดับการเชื่อมต่อ โดยมีโหนดเริ่มต้นและโหนดสิ้นสุด

กราฟแบบไม่มีทิศทาง เอ็จจะเชื่อมต่อกันแบบไม่สำคัญ คือสามารถเชื่อมต่อไปยังโหนดใดก็ได้ ไม่มีโหนดใดเป็นโหนดแรก และไม่มีโหนดใดเป็นโหนดสิ้นสุด

การแทนกราฟในหน่วยความจำ

สิ่งที่ต้องการจัดเก็บก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด วิธีที่ง่ายคือ การเก็บเอ็จในแถวลำดับ 2 มิติ แต่จะเป็นการเปลืองเนื้อที่เพราะบางเอ็จมีการเก็บซ้ำ แต่สามารถแก้ปัญหานี้ได้โดยมิติแรกเก็บโหนดต่างๆ แล้วใช้พอยเตอร์ชี้ไปยังความสัมพันธ์กับโหนดในมิติ 2 แต่เป็นวิธีที่ยุ่งยาก ไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา

กราฟที่มีการเปลี่ยนแปลงตลอดเวลา อาจใช้วิธีแอดจาเซนซีลิสต์ คือการใช้ลิงค์ลิสต์ เพื่อความสะดวกในการเปลี่ยนแปลง

นอกจากนี้ยังมีวิธีแทนกราฟในความจำหลักอีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้กันมากที่สุดคือ การแทนด้วยแอดจาเซนซีเมทริกซ์ โดยที่ถ้ากราฟ L มีทั้งหมด nโหนด แอดจาเซนซีเมทริกซ์เป็นเมทริกซ์จัตุรัสขนาด n*n วิธีนี้สามารถหาจำนวนเส้นทางได้ว่ามีกี่จำนวนเส้นทาง

การท่องไปในกราฟ

เป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย การท่องไปในกราฟมี 2 แบบ คือ

1.การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือนหรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียงจนกระทั่งครบทุกโหนด

2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ