ทรี (Tree)
เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่างโหนดจะมีความสัมพันธ์
ลดหลั่นกันเป็นลำดับชั้น(Hierarchical Relationship)
แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา
หนึ่งระดับได้หลายๆโหนดเรียกโหนดดังกล่าวว่า โหนดแม่
(Parent orMother Node) โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ
เรียกว่า โหนดลูก(Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่าโหนดราก(Root Node)
-โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node) เส้นเชื่อมแสดง
ความสัมพันธ์ระหว่าง โหนดสองโหนดเรียกว่า กิ่ง (Branch)
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด
(loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกัน
ทางเดียว เท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด
โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่านัลทรี (Null Tree) และถ้ามี
โหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย
(Sub Tree) T1, T2, T3,…,Tk
โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest)หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดราก
ของทรีออกหรือ เซตของทรีที่แยกจากกัน(Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree)หมายถึง ทรีที่โหนดต่าง ๆ
ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย เป็นต้น
3. ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มี
รูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือทรีที่เหมือนกันโดยสมบูรณ์
โดยต้องเป็นทรีที่ คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมี
ข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ
-การแทนทรีด้วย โหนดขนาดเท่ากันค่อนข้างใช้เนื้อที่จำนวนมาก
เนื่องจากแต่ละโหนดมีจำนวนโหนดลูกไม่เท่ากันหรือบาง
โหนดไม่มีโหนดลูกเลยถ้าเป็นทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่าง
กันมากจะเป็นการสิ้นเปลืองเนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
-โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัด
เนื้อที่ ในการจัดเก็บได้มาก เรียกโครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูก
ไม่เกินสอง หรือแต่ละโหนดมีจำนวนทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี
(Binary Tree) มีวิธีการท่องเข้าไปในทรี 6 วิธี
คือ NLR LNR LRN NRL RNL และ RLN
แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา
3 แบบแรกเท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการเป็นนิยามแบบ
รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธีNLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง
ๆในทรีด้วยวิธี LNRมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก
DTS:08-28-08-2552
วันศุกร์ที่ 28 สิงหาคม พ.ศ. 2552
เรื่อง Queue
เรื่อง Queue
คิว (Queue) เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ซึ่งการเพิ่ม
ข้อมูล จะกระทำที่ปลายข้างหนึ่งซึ่ง เรียกว่าส่วนท้ายหรือเรียร์ (rear)
และการนำข้อมูล ออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า
ส่วนหน้าหรือฟรอนต์(front)
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือที่
เรียกว่าFIFO (First In First Out)
การทำงานของคิวการใส่สมาชิกตัวใหม่ลงในคิว
เรียกว่าEnqueueซึ่งมีรูปแบบคือenqueu(queue,newElement)
หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์ของคิว
การนำสมาชิกออกจากคิว เรียกว่าDequeue ซึ่งมีรูปแบบคือdequeue
(queue, element) หมายถึง การนำออกจากส่วนหน้าของคิวและให้
ข้อมูลนั้นกับ element
-การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะเรียกว่า Queue Front
แต่จะไม่ทำการเอาข้อมูลออกจากคิว
-การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะ เรียกว่าQueue Rear
แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว
การแทนที่ข้อมูลของคิวสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วน คือ
1. Head Nodeจะประกอบไปด้วย 3 ส่วนคือพอยเตอร์จำนวน 2 ตัว
คือ Front และ rear กับจำนวนสมาชิในคิว
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับคิว ได้แก่
1.Create Queue คือ จัดสรรหน่วยความจำให้แก่ Head Node และให้ค่า pointer
ทั้ง 2 ตัวมีค่าเป็น null และจำนวนสมาชิกเป็น
2. Enqueue คือ การเพิ่มข้อมูลเข้าไปในคิว
3. Dequeue คือ การนำข้อมูลออกจากคิว
4. Queue Front คือ เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5. Queue Rear คือ เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty Queue คือเป็นการตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue คือ เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Count คือ เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9. Destroy Queue คือ เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว
DTS:07-28-08-2552
คิว (Queue) เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ซึ่งการเพิ่ม
ข้อมูล จะกระทำที่ปลายข้างหนึ่งซึ่ง เรียกว่าส่วนท้ายหรือเรียร์ (rear)
และการนำข้อมูล ออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า
ส่วนหน้าหรือฟรอนต์(front)
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือที่
เรียกว่าFIFO (First In First Out)
การทำงานของคิวการใส่สมาชิกตัวใหม่ลงในคิว
เรียกว่าEnqueueซึ่งมีรูปแบบคือenqueu(queue,newElement)
หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์ของคิว
การนำสมาชิกออกจากคิว เรียกว่าDequeue ซึ่งมีรูปแบบคือdequeue
(queue, element) หมายถึง การนำออกจากส่วนหน้าของคิวและให้
ข้อมูลนั้นกับ element
-การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะเรียกว่า Queue Front
แต่จะไม่ทำการเอาข้อมูลออกจากคิว
-การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะ เรียกว่าQueue Rear
แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว
การแทนที่ข้อมูลของคิวสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วน คือ
1. Head Nodeจะประกอบไปด้วย 3 ส่วนคือพอยเตอร์จำนวน 2 ตัว
คือ Front และ rear กับจำนวนสมาชิในคิว
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับคิว ได้แก่
1.Create Queue คือ จัดสรรหน่วยความจำให้แก่ Head Node และให้ค่า pointer
ทั้ง 2 ตัวมีค่าเป็น null และจำนวนสมาชิกเป็น
2. Enqueue คือ การเพิ่มข้อมูลเข้าไปในคิว
3. Dequeue คือ การนำข้อมูลออกจากคิว
4. Queue Front คือ เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5. Queue Rear คือ เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty Queue คือเป็นการตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue คือ เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Count คือ เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9. Destroy Queue คือ เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว
DTS:07-28-08-2552
เรื่อง stack
สแตก เ ป็นโครงสร้างข้อมูลที่เป็นแบบลิเนียร์ลิสต์ มีคุณสมบัติ
ที่ว่า การเพิ่มหรือลบข้อมูลในสแตก
ลักษณะที่สำคัญของสแตก คือ
ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลับดับแรกสุด
เรียกว่า LIFO ( Last In First Out)
การทำงานของสแตกประกอบไปด้วย 3 กระบวนที่สำคัญ คือ
1. Push คือ การนำข้อมูลใส่ลงไปในสแตก
เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้ push (s,i )
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก
เช่น ต้องการนำข้อมูลออกจากสแตก sไปไว้ที่ตัวแปร i
จะได้ i = pop (s)
การแทนที่ข้อมูลของสแตก
สามารถทำได้ 2 วิธี
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมุลของสแตกแบบอะเรย์
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stact จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง
Head ของสแตกกลับมา
2. Push Stact การเพิ่มข้อมูลลงไปในสแตก
3. Pop stact การนำข้อมูลบนสุดออกจากสแตก
4. stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก
5. Empty stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
9. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การประยุกต์ใช้สแตก
จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสาร
อันดับแรกสุดไว้ใช้หลังสุด
เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรย่อยการคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
DTS:06-28-08-2552
ที่ว่า การเพิ่มหรือลบข้อมูลในสแตก
ลักษณะที่สำคัญของสแตก คือ
ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลับดับแรกสุด
เรียกว่า LIFO ( Last In First Out)
การทำงานของสแตกประกอบไปด้วย 3 กระบวนที่สำคัญ คือ
1. Push คือ การนำข้อมูลใส่ลงไปในสแตก
เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้ push (s,i )
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก
เช่น ต้องการนำข้อมูลออกจากสแตก sไปไว้ที่ตัวแปร i
จะได้ i = pop (s)
การแทนที่ข้อมูลของสแตก
สามารถทำได้ 2 วิธี
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมุลของสแตกแบบอะเรย์
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stact จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง
Head ของสแตกกลับมา
2. Push Stact การเพิ่มข้อมูลลงไปในสแตก
3. Pop stact การนำข้อมูลบนสุดออกจากสแตก
4. stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก
5. Empty stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
9. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การประยุกต์ใช้สแตก
จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสาร
อันดับแรกสุดไว้ใช้หลังสุด
เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรย่อยการคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
DTS:06-28-08-2552
วันอังคารที่ 4 สิงหาคม พ.ศ. 2552
สมัครสมาชิก:
บทความ (Atom)