DTS : 11-16/09/2552

Summary B4 Final

ทรี (Tree)

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

การท่องไปในไบนารีทรี

วิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบ สามารถเยือนโหนดได้โหนดละหนึ่งครั้ง วิธีการท่องเข้าไปในทรีมี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่ที่นิยมใช้กันคือ 3 วิธีแรก ซึ่งขั้นตอนการท่องไปแต่ละแบบ มีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
- เยือนโหนดราก
- ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
- ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้
- ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
- เยือนโหนดราก

- ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
- ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
- ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
- เยือนโหนดราก

ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุกๆโหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน

กราฟ (Graph)

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

การท่องไปในกราฟ
1. การค้นหาแบบกว้าง(Breadth-first Search) ในกราฟแบบไม่มีทิศทาง รายชื่อโหนดที่พบจากการค้นหา มีได้หลายรายการขึ้นกับลำดับการเรียงโหนดประชิด ในกราฟแบบมีทิศทาง การค้นหาโหนดทำได้ง่ายขึ้นถ้าใช้คิวเก็บลำดับของโหนดประชิดที่ต้องเยี่ยมต่อไป
2. การค้นหาแบบลึก (Depth-first Search)

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

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

การค้นหาข้อมูล (Searching)

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

วิธีการค้นหาข้อมูล
1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear) เป็นวิธีที่ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ วิธีการ คือ นำข้อมูลที่จะหามาเปรียบเทียบกับข้อมูลลูกค้าแรกในแถวลำดับ ถ้าไม่เท่ากันให้เปรียบเทียบข้อมูลถัดไป ถ้าเท่ากันให้หยุดค้นหา
2. การค้นหาแบบเซนทินัล(Sentinel) เป็นวิธีที่การค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า วิธีการ คือ

- เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก 1 ที่
- นำข้อมูลที่จะใช้ค้นหาข้อมูลใน Array ไปฝากที่ต้นหรือ ท้าย Array
- ตรวจสอบผลลัพธ์จากการหา โดยตรวจสอบจากตำแหน่งที่พบ ถ้าตำแหน่งที่พบมีค่าเท่ากับ n-1แสดงว่าหาไม่พบ นอกนั้นถือว่าพบข้อมูลที่ค้าหา
3. การค้นหาแบบไบนารี(Binary Search) การค้นหาแบบไบนารีใช้กับข้อมูลที่ถูกจัดเรียงแล้วเท่านั้น วิธีการ คือ ข้อมูลถูกแบ่งออกเป็นสองส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา

- หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้นตำแหน่งตัวแทน หาได้จากสูตร

mid = (low+high)/2
mid คือ ตำแหน่งกลาง ,low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ

- นำผลการเปรียบเทียบ กรณีที่หาไม่พบมาใช้ในการค้นหารอบต่อไป

DTS : 10-09/09/2552

Sorting

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

วิธีการเรียงลำดับ
1. การเรียงลำดับแบบภายใน(Internal sorting) การเรียงข้อมูลทั้งหมดให้อยู่ในหน่วยความจำหลัก เวลาที่ใช้ในการเรียงจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบ และเลื่อนข้อมูลภายในหน่วยความจำหลัก
2. การเรียงลำดับแบบภายนอก(External sorting) การเรียงข้อมูลในหน่วยความจำสำรอง เวลาที่ใช้ในการเรียงต้องคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูลในหน่วยความจำหลัก

การเรียงลำดับแบบเลือก(Selection sorting)
ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ข้อมูลควรจะอยู่ทีละตัว โดยการค้นหาข้อมูลแต่ละรอบแบบเรียงลำดับจากน้อยไปหามาก
1) รอบแรกจะค้นหาข้อมูลที่น้อยที่สุดมาเก็บในตำแหน่งที่ 1
2) รอบสองนำตัวเลขที่มีค่าน้อยรองลงมาเก็บในตำแหน่งที่สอง
3) ทำเช่นนี้ไปเรื่อยๆจนครบทุกค่า การเรียงลำดับแบบเลือกเป็นวิธีที่ง่ายที่สุด แต่มีข้อเสียในการใช้เวลาจัดเรียงนาน เพราะแต่ละรอบต้องเปรียบเทียบข้อมูลทุกตัว ถ้ามีข้อมูล n ตัว ต้องเปรียบเทียบทั้งหมด n-1 รอบ และจำนวนครั้งในการเปรียบเทียบมีดังนี้
รอบที่ 1 มีการเปรียบเทียบ n-1 ครั้ง
รอบที่ 2 มีการเปรียบเทียบ n-2 ครั้ง
....
รอบที่ n-1 มีการเปรียบเทียบ 1 ครั้ง

การเรียงลำดับแบบฟอง(Bubble sort)
เป็นวิธีเรียงลำดับที่มีการเปรียบเทียบข้อมูลที่มีตำแหน่งติดกัน
1. ถ้าข้องมูลทั้งสองอยู่ตำแหน่งที่ไม่ถูกต้อง ให้สลับกันตำแหน่งกัน
2. ถ้ามีการเรียงลำดับข้อมูลจากน้อยไปมาก ให้นำข้อมูลที่มีค่าน้อยอยู่ก่อนข้อมูลที่มีค่ามาก ถ้าเรียงลำดับข้อมูลจากมากไปน้อย ให้นำข้อมูลที่มีค่ามากอยู่ก่อนที่มีค่าน้อย การเรียงลำดับข้อมูลแบบฟองเป็นวิธีการที่ไม่ซับซ้อน เป็นวิธีการที่นิยมใช้กันมากเพราะเป็นรูปแบบที่เข้าใจง่าย แต่มีประสิทธิภาพค่อนข้างต่ำ

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

การเรียงลำดับแบบแทรก(Insertion sort) เป็นการเรียงลำดับที่เพิ่มสมาชิกใหม่เข้าไปในเซ็ต ที่มีการเรียงลำดับข้อมูลอยู่แล้ว แล้วทำให้เซ็ตใหม่มีการเรียงลำดับด้วย
1. เริ่มเปรียบเทียบข้อมูลตำแหน่งที่ 1 และ 2 หรือข้อมูลตำแหน่งสุดท้ายกับรองสุดท้าย
2. ถ้าเป็นการเรียงข้อมูลจากค่าน้อยไปมาก จัดเรียงข้อมูลที่มีค่าน้อยอยู่ก่อนข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงข้อมูลจากมากไปน้อย จัดเรียงข้อมูลที่มีค่ามากอยู่ก่อนข้อมูลที่มีค่าน้อย

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

DTS : 09-02/09/2552

Grapt

กราฟ(Grapt)เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น กราฟนำไปใช้แก้ปัญหาข้อมมูลที่ค่อนข้างซับซ้อน เช่น การวางข่ายคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น

นิยามของกราฟ

1) โหนด(Node) หรือเวอร์เทกซ์(Vertexes)

2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ(Edges)

กราฟที่มีเอ็จเชื่อมโหนดสองโหนด ถ้าเอ็จไม่มีลำดับ เรียกว่า กราฟแบบไม่มีทิศทาง(Undirected Grapts) ถ้ากราฟเป็นเอ้จที่มีลำดับ เรียกว่า กราฟแบบมีทิศทาง(Directed Grapts) ถ้าต้องการอ้างชื่อเอ็จ สามารถเขียนชื่อเอ็จกำกับไว้ได้

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

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

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

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

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

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

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

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

2. การท่องแบบลึก(Depts First Traversal) การทำงานคล้ายกับการท่องทีละลำดับของทรี โดยกำหนดโหนดเริ่มต้นโหนดแรก และเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี จากนั้นย้อนกลับมาแนววิถีเดิม จนกระทั่งสามารถดำเนินการต่อเข้าสู่วิถีอื่น เพื่อเยือนโหนดอื่นจนครบ