DTS 11-16/09/52

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

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

การค้นหาข้อมูล (Searching)
การค้นหา คือการใช้วิธีการค้นหากับโครงสร้างข้อมูล เพื่อดูว่าข้อมูลตัว
ที่ต้องการถูกเก็บอยู่ในโครงสร้างแล้วหรือยัง

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

การค้นหาแบ่งเป็น 2 ประเภท ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับการเรียงลำดับ
การค้นหาข้อมูลแบบภายใน (Internal Searching)
การค้นหาข้อมูลแบบภายนอก (External Searching)

1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear)
เป็นวิธีที่ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ
หลักการ คือ ให้นำข้อมูลที่จะหามาเปรียบเทียบกับข้อมูลตัว
แรกในแถวลำดับถ้าไม่เท่ากันให้เปรียบเทียบกับข้อมูลตัวถัดไปถ้าเท่ากัน
ให้หยุดการค้นหา
2. การค้นหาแบบเซนทินัล (Sentinel)เป็นวิธีที่การค้นหาแบบเดียวกับ
วิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า
พัฒนามาจากอัลกอริทึมแบบเชิงเส้น
หลักการ
1) เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก 1 ที่
2) นำข้อมูลที่จะใช้ค้นหาข้อมูลใน Array ไปฝากที่ต้นหรือ ท้ายArray
3) ตรวจสอบผลลัพธ์จากการหาโดยตรวจสอบจากตำแหน่งที่พบ ถ้าตำแหน่ง
ที่พบมีค่าเท่ากับ n-1แสดงว่าหาไม่พบ
3. การค้นหาแบบไบนารี (Binary Search)ใช้กับข้อมูลที่ ถูกจัดเรียงแล้ว
เท่านั้นหลักการของการค้นหาคือ ข้อมูลถูกแบ่งออกเป็นสองส่วนแล้วนำ
ค่ากลาง ข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
1) หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้นตำแหน่งตัวแทน
ข้อมูลหาได้จากสูตร
mid = (low+high)/2
mid คือ ตำแหน่งกลาง ,
low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ
2) นำผลการเปรียบเทียบกรณีที่หาไม่พบมาใช้ในการค้นหารอบต่อไป
ถ้าข้อมูลมีการเรียงจากน้อยไปหามาก เมื่อเปรียบเทียบแล้วคีย์มีค่ามากกว่า
ค่ากลาง แสดงว่าต้องทำการค้นหาข้อมูลในครึ่งหลังต่อไป จากนั้นนำข้อมูล
ครึ่งหลังมาหา ค่ากลางต่อ ทำอย่างนี้ไปเรื่อย ๆ จนกว่าจะได้ข้อมูลที่ต้องการ

DTS 10-09/09/52

กราฟ และ sorting
กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น
(Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูล
ทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษ แบบหนี่งขอ'กราฟโดย
ทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ
เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด กราฟมีลักษณะ
เป็นเซ็ตของ จุด (Point) และเซ็ตของเส้น (Line) ซึ่งแต่ละเส้นทำหน้า
ที่เชื่อมต่อจุดเข้าด้วยกัน แต่ละจุดเรียกว่าโหนด (Node) ของกราฟ
และเส้นเรียกว่าเอจ (Edge) บางครั้งเอจจะ เรียกว่าอาร์ค (Arc) และ
โหนดเรียกว่าเวอร์ทิค (Vertice) โดยกำหนดให้กราฟ G มีเซ็ต
ของโหนดเป็น VG และเซ็ตของเอจเป็น EG

การวิ่งตามเส้นทางในกราฟ
แอปพลิเคชั่นที่เขียนขึ้นมาเมื่อใช้งานกราฟส่วนใหญ่ต้องเข้าไปเรียกใช้
งานในแต่ละ โหนด เช่น การพิมพ์รายการกิจกรรมในระบบการบริหารจัด
การโครงการ การแสดงผล ระยะทางระหว่างเมือง เทคนิคพื้นฐานการวิ่ง
ตามเส้นทางในกราฟ (Graph Traversal) ที่จะกล่าวถึง คือ การวิ่งตาม
แนวกว้างก่อน (Breadth – first) และการวิ่งตามแนวลึกก่อน (Depth – first)
การวิ่งตามเส้นทางมีสิ่งที่ต้องระวัง คือ การวิ่งไปถึงแต่ละโหนดควรมี
เพียงครั้งเดียว การวิ่งซ้ำโหนดเดิมทำให้การทำงานและผลที่ได้เกิดขึ้นซ้ำ
จากการวิ่งย้อน ตามเส้นทางที่เคยผ่านมาแล้ว และมีหลายเส้นทางที่เชื่อม
ต่อระหว่างสองโหนด การเขียน อัลกอริทึมการวิ่งตามเส้นทางในกราฟจะใช้
เครื่องหมายหรือตัวมาร์ก (Mark) บอกให้ทราบว่า มีการวิ่งมายังโหนดนี้แล้ว
โดยก่อนหน้านี้จะถูกมาร์กว่ายังไม่วิ่งมา หรือเปลี่ยนมาใช้ตัวมาร์ก กับเอจ
แทน ดังนั้น เอจที่ผ่านไปแล้วจะไม่ถูกรวมกับเอจอื่น ๆ ที่เหลือ เครื่องหมาย
หรือตัวมาร์ก จะใช้เป็นมาร์กบิต (Mark Bit) เก็บไว้ในแต่ละโหนดหรือเอจ

การวิ่งตามแนวกว้างก่อน
การวิ่งตามเส้นทางในกราฟตามแนวกว้างก่อน (Breath – first Traversal)
หรือการค้นหา ตามแนวกว้างก่อน (Breath – first Traversal) เริ่มด้วยการ
เลือก มาหนึ่งโหนดเป็นตำแหน่ง เริ่มต้นและทำเครื่องหมายว่าวิ่งผ่านมา
แล้ว จากนั้นวิ่งไปยังโหนดทุกโหนดที่ติดกับโหนด นี้และยังไม่วิ่งผ่าน
และทำ เครื่องหมาย ทำเช่นนี้จะกระทั่งวิ่งผ่านทุก ๆ โหนดที่มีอยู่ในกราฟ
การวิ่งตาม แนวกว้างในกราฟจากรูปที่ 10.13 ผลจากการวิ่งไปยังแต่ละ
โหนดจะมีลำดับเป็น 1,2,3,4,5,6,7,8 หรือมีลำดับเป็น 1,3,2,6,5,4,7,8 ก็ได้
ขึ้นอยู่กับการเลือกโหนดที่ จะวิ่งผ่าน ทางด้านซ้ายหรือขวาก่อน
อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้าง ก่อนจะใช้โครงสร้าง
ข้อมูลคิวเพื่อเก็บโหนดที่วิ่งผ่านไปแล้วในแต่ละระดับของ กราฟ แต่ละ
โหนดที่เก็บในคิวจะใช้ สำหรับวิ่งไปยังโหนดติดกันที่ยังไม่ได้วิ่งไป
ทำจนวิ่งผ่านทุกโหนดในกราฟและสิ้นสุดลงเมื่อ คิวว่าง อัลกอริทึมการ
วิ่งตาม เส้นทางในแนวกว้างก่อน

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

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

(2) การเรียงลำดับแบบภายนอก(external sorting)
เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ
เรียงลำดับ ข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการเรียงลำดับต้อง
คำนึงถึงเวลาที่เสียไป ระหว่างการถ่ายเทข้อมูลจากหน่วยความจำหลัก
และหน่วยความจำสำรองนอกเหนือ จากเวลาที่ใช้ในการเรียงลำดับข้อมูล
แบบภายในการเรียงลำดับแบบเลือก (selection sort) ทำการเลือกข้อมูลมา
เก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละตัว โดยทำการค้นหา ข้อมูลนั้น
ในแต่ละรอบแบบเรียงลำดับการเรียงลำดับแบบเลือกเป็นวิธีที่ง่าย แต่เสีย
เวลาในการจัดเรียงนาน โดยจะทำการเลือกข้อมูลมาเก็บไว้ตามตำแหน่ง
ที่กำหนด คือ กำหนดให้เรียงข้อมูลจากค่าน้อยไปหาค่ามาก ก็จะทำการ
เลือกข้อมูลตัวที่มีค่าน้อยที่สุดมา อยู่ที่ตำแหน่งแรกสุด และค่าที่อยู่
ตำแหน่งแรกก็จะมาอยู่แทนที่ค่าน้อยสุด แล้วทำการ เลือกไปเรื่อยๆ
จนครบทุกค่า ค่าที่ได้ก็จะเรียงจากน้อยไปหามาก

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

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

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

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

DTS 09-02/09/52

สรุป
เอ็กซ์เพรสชั่นทรีเป็นการนำนิพจน์มาเก็บยังโครงสร้างทรี โดยแต่ละโหนดจะเก็บตัวดำเนินการ (Operator) และตัวถูกดำเนินการ (Operand) ซึ่งตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบ ส่วนตัวดำเนินการจะเก็บอยู่ที่โหนดกิ่ง แต่ต้องคำนึงถึงความสำคัญของเครื่องหมายตามลำดับด้วย คือ-ฟังก์ชั่น-วงเล็บ-ยกกำลัง-เครื่องหมายหน้าเลขจำนวน-คูณ หาร-บวก ลบ***ถ้ามีความสำคัญในระดับเดียวกันให้ทำจากซ้ายไปขวาไบนารีเซิร์ซทรีค่าของโหนดรากจะมีค่ามากกว่าโหนดย่อยทางด้านซ้าย และมีค่าน้อยกว่าหรือเท่ากับโหนดย่อยทางด้านขวาการเพิ่มโหนดในไบนารีเซิร์ซทรี ถ้าทรีว่างโหนดที่เพิ่มจะเป็นโหนดราก ถ้าทรีไม่ว่างต้องทำการตรวจสอบโหนดใหม่ว่ามีค่ามากกว่าหรือน้อยกว่าค่าที่โหนดราก
***ถ้ามีค่ามากกว่าหรือเท่ากันจะนำโหนดที่เพิ่มไปเพิ่มยังทรีย่อยด้านขวา แต่ถ้ามีค่าน้อยกว่าจะนำไปเพิ่มที่ทรีย่อยด้านซ้าย
การดึงโหนดในไบนารีเซิร์ซทรี ต้องทำการค้นหาตำแหน่งที่ต้องการดึงก่อนว่าอยู่ตำแหน่งใดแล้วต้องรู้ด้วยว่าโหนดแม่ของโหนดนั้นคือโหนดไหน จึงจะสามารถทำการดึงได้ แต่เมื่อดึงโหนดออกแล้ว ทรีนั้นต้องคงสภาพเนไบนารีเซิร์ซทรีเหมือนเดิม
วิธีการดึงโหนดออก แยกได้ 3 วิธี
1. กรณีโหนดที่จะดึงออกเป็นโหนดใบ สามารถดึงได้เลยเพราะไม่มีผลกระทบต่อโหนดอื่นๆ แล้วเป็นวิธีที่ง่ายที่สุด
2. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยด้านซ้ายหรือทรีย่อยด้านขวาเพียงด้านใดด้านหนึ่ง สามารถทำได้เหมือนวิธีแรก เพียงให้โหนดแม่ของโหนดที่ต้องการดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
3. กรณีโหนดที่ต้องการดึงออกมีทั้งทรีย่อยด้านซ้ายและทรีย่อยด้านขวา ต้องทำการเลือกว่าจะนำทรีย่อยด้านใดมาแทนโหนดที่ถูกดึงออก
***ถ้าเลือกทรีย่อยด้านซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดมาแทน แต่ถ้าเลือกทรีย่อยด้านขวาต้องเลือกโหนดที่มีค่น้อยที่สุดมาแทน
Graph
เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น ประกอบด้วยกลุ่มของสิ่งสองสิ่ง คือ
1.โหนด แทนด้วย N
2.เส้นเชื่อมระหว่างโหนด แทนด้วย E
*** กราฟที่มีเส้นเชื่อมระหว่างโหนดที่ไม่มีลำดับ จะเรียกกราฟนั้นว่า กราฟแบบไม่มีทิศทาง
ส่วนกราฟที่มีเส้นเชื่อมระหว่างโหนดที่มีลำดับ จะเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง หรือเรียกว่า ไดกราฟ
ในการเขียนกราฟสิ่งที่สนใจจะถูกแทนด้วยจุด หรือ วงกลม ที่มีชื่อข้อมูลกำกับ ส่วนเอ็จจะแทนด้วยเส้นหรือเส้นโค้ง
กราฟแบบมีทิศทางเส้นเอ็จต้องมีลูกศรกำกับแสดงลำดับการเชื่อมต่อ โดยมีโหนดเริ่มต้นและโหนดสิ้นสุด
กราฟแบบไม่มีทิศทาง เอ็จจะเชื่อมต่อกันแบบไม่สำคัญ คือสามารถเชื่อมต่อไปยังโหนดใดก็ได้ ไม่มีโหนด
ใดเป็นโหนดแรก และไม่มีโหนดใดเป็นโหนดสิ้นสุด
การแทนกราฟในหน่วยความจำ
สิ่งที่ต้องการจัดเก็บก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด วิธีที่ง่ายคือ การเก็บเอ็จในแถวลำดับ 2 มิติ แต่จะเป็นการเปลืองเนื้อที่เพราะบางเอ็จมีการเก็บซ้ำ แต่สามารถแก้ปัญหานี้ได้โดยมิติแรกเก็บโหนดต่างๆ แล้วใช้พอยเตอร์ชี้ไปยังความสัมพันธ์กับโหนดในมิติ 2 แต่เป็นวิธีที่ยุ่งยาก ไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา กราฟที่มีการเปลี่ยนแปลงตลอดเวลา อาจใช้วิธีแอดจาเซนซีลิสต์ คือการใช้
ลิงค์ลิสต์ เพื่อความสะดวกในการเปลี่ยนแปลง นอกจากนี้ยังมีวิธีแทนกราฟในความจำหลักอีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้กันมากที่สุดคือ การแทนด้วยแอดจาเซนซีเมทริกซ์ โดยที่ถ้ากราฟ L มีทั้งหมด nโหนด แอดจาเซนซีเมทริกซ์เป็นเมทริกซ์จัตุรัสขนาด n*n วิธีนี้สามารถหาจำนวนเส้นทางได้ว่ามีกี่จำนวนเส้นทาง
การท่องไปในกราฟ
เป็นการไปเยือนโหนดในกราฟ ซึ่งแต่ละโหนดจะถูกเยือนเพียงครั้งเดียว แต่กราฟนั้นมาหลายเส้นทางเมื่อเยือนแล้วต้องทำเครื่องหมายว่าได้เยือนเรียบร้อย การท่องไปในกราฟมี 2 แบบ คือ
1.การท่องแบบกว้าง เป็นการกำหนดโหนดที่จะเยือนหรือโหนดเริ่มต้นแล้วทำการเยือนไปยังโหนดที่ใกล้เคียงจนกระทั่งครบทุกโหนด
2.การท่องแบบลึก โดยกำหนดเริ่มต้นที่โหนดแรกแล้วเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี แล้วย้อนกลับมาเพื่อเยือนโหนดอื่นๆ

DTS 08-26/08/52

สรุป ทรี
โครงสร้างข้อมูลแบบทรี เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น ได้มีการนำรูปแบบทรีไปประยุกต์ใช้งานต่างๆอย่างแพร่หลาย
ทรี หรือโครงสร้างข้อมูลแบบต้นไม้ ประกอบด้วยโหนด (node) ซึ่งเป็นส่วนที่เก็บข้อมูล ในทรีหนึ่งทรีจะประกอบไปด้วยรูทโหนด (root node) เพียงหนึ่งโหนด แล้วรูทโหนดสามารถแตกโหนดออกเป็นโหนดย่อยๆ ได้อีกหลายโหนดเรียกว่าโหนดลูก (Child node) เมื่อมีโหนดลูกแล้ว โหนดลูกก็ยังสามารถแสดงเป็นโหนด
พ่อแม่ (Parent Node) โดยการแตกโหนดออกเป็นโหนดย่อยๆได้อีก
Binary TreeBinary Tree
มีลักษณะเหมือนกับ Tree ปกติแต่มีคุณสมบัติพิเศษ คือ “แต่ละโหนดจะมีโหนดลูกได้ไม่เกิน 2 โหนด” หรือพูดอีกนัยหนึ่งก็คือ แต่ละโหนดใน binary tree จะมีดีกรีได้ไม่เกิน2
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆไป1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และดหนดลูกอื่นๆ2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในทรีเพื่อเข้าไปเยือนทุกๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแผน สามารถเยือนโหนดทุกๆโหนดๆละนึ่งครั้ง
1.การท่องไปแบบพรีออร์เดอร์ การเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี NLR
1. เยือนดหนดราก
2. ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
3. ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์ เป็นการเดินไปเยือนโหนดต่างๆในทรีด้วยวิธี LNR
1.ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2.เยือนโหนดราก
3.ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3.การท่องไปแบบโพสออร์เดอร์ เป็นการเดินไปเยือนโหนดต่างๆ ในทรีด้วยวิธี LRN
1.ท่องไปในทรีย่อยซ้ายแบบโพสออร์เดอร์
2.ท่องไปในทรีย่อยขวาแบบโพสออร์เดอร์
3.เยือนโหนดราก

DTS 07-05/08/52

สรุป เรื่อง Queue
คิวเป็นโครงสร้างข้อมูลแบบลำดับ (Sequential) ลักษณะของคิวเราสามารถพบได้ในชีวิตประจำวัน เช่น การเข้าแถวตามคิวเพื่อรอรับบริการต่างๆ ลำดับการสั่งพิมพ์งาน เป็นต้น ซึ่งจะเห็นได้ว่าลักษณะของการทำงานจะเป็นแบบใครมาเข้าคิวก่อน จะได้รับบริการก่อน เรียกได้ว่าเป็นลักษณะการทำงานแบบ FIFO (First In , First Out) ลักษณะของคิว จะมีปลายสองข้าง ซึ่งข้างหนึ่งจะเป็นช่องทางสำหรับข้อมูลเข้าที่เรียกว่า REAR และอีกข้างหนึ่งซึ่งจะเป็นช่องทางสำหรับข้อมูลออก เรียกว่า FRONT
การสร้างคิว (Queue) คิวที่อยู่ในคอมพิวเตอร์สามารถจัดเก็บได้หลายลักษณะ แต่โดยทั่วไปแล้วจะใช้การจัดเก็บแบบลิงค์ลิสท์เดี่ยวหรือจัดเก็บโดยใช้อาร์เรย์ ก่อนที่จะทำการสร้างคิวจะต้องทำความเข้าใจถึงโครงสร้างของคิว ซึ่งประกอบไปด้วย ตัวคิว ซึ่งในที่นี้ขอแทนด้วยอาร์เรย์ และจะต้องมีตัวชี้อีก 2 ตัว ได้แก่ ตัวชี้ F (Front Pointer) ชี้ไปที่สมาชิกตัวแรก และตัวชี้ R (Rear Pointer) ชี้ไปที่สมาชิกตัวสุดท้ายของคิว โดยที่เวลาข้อมูลจะเข้าสู่คิวจะเข้าทาง R ส่วนเวลาที่ข้อมูลจะออกจากคิวจะออกทาง
ในการทำงานกับคิวที่ต้องมีการนำข้อมูลเข้าและออกนั้น จะต้องมีการตรวจสอบว่าคิวว่างหรือไม่ เมื่อต้องการนำข้อมูลเข้า เพราะหากคิวเต็มก็จะไม่สามารถทำการนำข้อมูลเข้าได้ เช่นเดียวกัน เมื่อต้องการนำข้อมูลออกก็ต้องตรวจสอบด้วยเช่นกัน ว่าในคิวมีข้อมูลอยู่หรือไม่ หากคิวไม่มีข้อมูลก็จะไม่สามารถนำข้อมูลออกได้เช่นกัน การInsertion เป็นการนำข้อมูลเข้าสู่คิว โดยการที่จะนำข้อมูลเข้าสู่คิวนั้นจะแบ่งออกเป็น 2 กรณี คือ
1. การนำข้อมูลเข้าไปในคิวว่าง โดยจะต้องดำเนินการให้พอยน์เตอร์ทั้ง 2 คือ F และ R ชี้ไปยังช่องแรกหรือตำแหน่งที่จะเก็บข้อมูลแรก
2. การนำข้อมูลเข้าไปในคิวต่อจากข้อมูลเดิม จะต้องจัดการให้พอยน์เตอร์ R ชี้ไปยังช่องหรือตำแหน่งของข้อมูลที่นำเข้าไป ส่วนพอยน์เตอร์ F ยังคงชี้ไปยังช่องหรือตำแหน่งของข้อมูลที่นำเข้าไปเป็นข้อมูลแรก
การ Deletion
เป็นการนำข้อมูลที่เก็บอยู่ในคิวออกจากคิว โดยการเมื่อทำการ Deletion ข้อมูลนั้นออกจากคิวแล้ว จะต้องมีการจัดการให้ตัวชี้คิว F ชี้ไปยังช่องหรือตำแหน่งต่อจากข้อมูลที่จะได้ทำการ Deletion ไปแล้ว ส่วนพอยน์เตอร์ R ชี้ไปยังช่องข้อมูลสุดท้ายเหมือนเดิมการ Deletion ข้อมูลนี้จะทำการนำข้อมูลในส่วนของข้อมูลตัวแรกสุดที่เข้าสู่คิวออกไปทำงานตามต้องการ แต่การ Deletion ข้อมูลนี้จะไม่สามารถ Deletion ข้อมูลออกจากคิวที่ว่างเปล่าหรือไม่มีข้อมูลได้ (F = 0) ถ้าเกิดกรณีเช่นนี้จะเกิด Error ที่เรียกว่า Underflow ขึ้น ฉะนั้นก่อนที่จะทำการ Deletion ควรที่จะต้องมีการตรวจสอบว่าคิวว่างหรือไม่ เพื่อไม่ให้เกิด Error นี้ขึ้น
การประยุกต์ใช้งานคิวในการจำลองแบบการจำลองแบบ (Simulation) หมายถึง การใช้ระบบหนึ่งเพื่อเลียนแบบพฤติกรรมของอีกระบบหนึ่ง ใช้งานเมื่อการทดลองด้วยระบบจริงๆ มีค่าใช้จ่ายสูง หรือเสี่ยงต่ออันตราย การจำลองแบบของคอมพิวเตอร์ จะใช้ขั้นตอนการทำงานของโปรแกรม เพื่อการเลียนแบบพฤติกรรมของระบบที่เราต้องการศึกษาการจำลองแบบของระบบแบ่งกันใช้เวลาระบบคอมพิวเตอร์ที่มีการทำงานแบบแบ่งกันใช้เวลา เป็นระบบที่มีผู้ใช้เครื่องคอมพิวเตอร์พร้อมกันในเวลาเดียวกัน โดยระบบมีหน่วยผลกลาง (ซีพียู) และหน่วยความจำหลักเพียงอย่างละ 1 เท่านั้น ผู้ใช้หลายๆ คนนี้ จะต้องมีการใช้หน่วยความจำหลักและหน่วยประมวลผลกลางร่วมกัน ซึ่งอนุญาติให้ผู้ใช้แต่ละคนประมวลผลโปรแกรม (ใช้ทรัพยากรของระบบ) ในเวลาหนึ่งๆ แล้วก็จะให้ผู้ใช้คนต่อไปใช้จนกว่าจะวนกลับมายังผู้ใช้คนแรกอีก วิธีการประมวลผลร่วมกันระหว่างผู้ใช้หลายๆ คน เราเรียกว่า ระบบแบ่งกันใช้เวลา (Time sharing) ซึ่งลักษณะการใช้ซีพียูจะเป็นไปตามลำดับคือ “มาก่อนได้ก่อน” (first – come – first – serve) และมีลำดับการทำงานดังนี้1. เมื่อโปรแกรมขอใช้เวลาซีพียู โปรแกรมนั้นจะถูกนำไปต่อท้ายคิวประมวลผล2. โปรแกรมที่อยู่ต้นคิวจะถูกส่งไปทำงาน และยังคงอยู่ที่ต้นคิวจนกว่าจะใช้ซีพียูเสร็จ3. เมื่อรันโปรแกรมทำงานเสร็จตามเวลาการขอใช้ซีพียู ก็จะถูกนำออกจากคิว และจะไม่ถูกนำกลับมาอีก จนกว่าจะมีการขอใช้ซีพียูครั้งใหม่ (จึงจะกลับไปที่ข้อ 1. อีก)การจำลองแบบสนามบินการเขียนโปรแกรมเพื่อจำลองแบบของสนามบิน จะใช้โครงสร้างข้อมูลแบบคิว แทนคิวของเครื่องบินที่จะรอขึ้นหรือรอลง แต่คอนข้างเป็นโปรแกรมที่ซับซ้อน ดังสภาพความเป็นจริงที่ว่า สนามบินมีขนาดเล็กแต่มีเครื่องบินขึ้นลงจำนวนมาก มีทางวิ่ง (runway) เพียงทางเดียว ดังนั้น ณ เวลาใด ๆ เครื่องบิน จะต้องขึ้นหรือลงอย่างใดอย่างหนึ่งเท่านั้น และเพียงเครื่องเดียวด้วย ในเวลาที่เครื่องบินซึ่งพร้อมจะขึ้นหรือลงมาถึงสนามบิน สนามบินนั้นอาจจะว่างหรือมีเครื่องบินอื่นกำลังขึ้นหรือลงอยู่ก็ได้ และอาจจะมีเครื่องบินหลายลำที่รอขึ้นและรอลง จึงมีคิว 2 คิวเกิดขึ้น คือ คิวขึ้น (takeoff) และคิวลง ( landing) ในการรอนั้นบนพื้นจะดีกว่าบนอากาศ ดังนั้นจึงให้เครื่องบินขึ้นได้ก็ต่อเมื่อไม่มีเครื่องบินลง หลักจากได้รับสัญญาณร้องขอจากเครื่องบินลำใหม่เพื่อจะลงหรือขึ้น โปรแกรมการจำลองแบบจะให้บริการเครื่องบินที่อยู่ในตำแหน่งหัวคิวของคิวลงก่อน และถ้าคิวลงว่าง จึงอนุญาตให้เครื่องบินในคิวขึ้นขึ้นได้ โปรแกรมจำลองแบบนี้สามารถจะทำงานได้ตลอดเวลา