DTS_8 26/08/2552

สรุปผลเรียนเรื่อง ทรี (Tree)

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

ความสัมพันธ์ของโหนดใน Tree

แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้
หลายๆ โหนด เรียกโหนดดังกล่าวว่า โหนดแม่ (Parent or Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ เรียกว่า โหนดลูก(Child Node)
โหนดทีอยู่ในระดับสูงสุดและไม่มีโหนดแม่ เรียกว่า โหนดราก(Root Node)
โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า โหนดพี่น้อง(Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ(Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด เรียกว่า กิ่ง(Branch)

นิยามของทรี(Tree)

ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด(loop)ในโครงสร้าง โหนดสอง
โหนดใดๆ ในทรีต้องมีทางติดต่อกัน ทางเดียวเท่านั้น และทรีที่มี N โหนด
ต้องมีกิ่งทั้งหมด N-1เส้น
ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ว่าง ไม่มีโหนดใดๆ เรียกว่า
นัลทรี(Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่ง
เป็นทรีย่อย (Sub Tree)

นิยามที่เกี่ยวกับทรี (Tree)

1.ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดราก
ของทรีออก หรือ เซตของทรีที่แยกออกจากกัน(Disjoint Trees)
2.ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่างๆในทรีนั้น
มีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา ไปทางซ้าย เป็นต้น
3.ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มี
รูปร่างของทรีเหมือนกัน โดยไม่คำนึ่งถึงข้อมูลทีอยู่ในแต่ละโหนด
4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์
โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูล เหมือนกัน
5.กำลัง (Degree) หมายถึง จำนวนทรีย่อยของในโหนดนั้นๆ
6.ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนด
นั้นๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่
ระดับ 1และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือยาวเท่ากับ 1 หน่วย
ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยัง
โหนดใดบวกด้วย 1และจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ
ซึ่งห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)

การแทนที่ทรีในหน่วยความจำหลัก

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

การแปลงทรีทั่วไปให้เป็นไบนารีทรี

1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโตแล้วลบความสัมพนธ์ ระหว่างโหนด
แม่และโหนดลูกอื่นๆ
2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา

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

1.การท่องไปแบบพีออร์เดอร์(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่างๆใสทรีด้วยวิธี NLR มีขั้นตอนการเดิน
ดังต่อไปนี้
1.1เยื่อนโหนดราก
1.2ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
1.3ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.การท่องไปอบบอินออร์เดอร์(Inorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่างๆ
ในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้
2.1ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2.2เยื่อนโหนดราก
2.3ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3.การท่องโพสออร์เดอร์(Postorder Traversal) เป็นการเดินเข้าไปเยื่อนโหนดต่างๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
3.1ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
3.2ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
3.3เยือนโหนดราก

DTS_7 5/08/2552

สรุปผลเรียนเรื่อง คิว (queue)

คิวเป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์การเพิ่มข้อมูล
จะทำการเพิ่มจากส่วนท้ายซึ่งเิรียกว่าเรียร์ (rear) และทำการนำข้อมูล
ออกอีกด้านหนึ่งซึ่งเรียกว่าส่วนหน้าหรือฟรอนต์ (front) ลักษณะการทำงาน
ของคิวจะเรียกว่าเข้าก่อนออกก่อนหรือ FIFO (First in First out)

การทำงานของคิว (queue)ประกอบด้วย
1.การใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueue และการนำข้อมูลออกจากคิวเรียกว่า Dequeue
2.การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงเรียกว่า Queue Front แต่จะไม่ทำการนำข้อมูลออกจากคิว และการนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงเรียกว่า Queue Rear และจะไม่เพิ่มข้อมูลไปในคิวเช่นกัน

การแทนที่ข้อมูลของคิว (queue)
1.การแทนที่ข้อมูลแบบลิงค์ลิสตจะประกอบไปด้วย2ส่วนคือ
1.1Head Node จะประกอบไปด้วย3ส่วนคือ พอยเตอร์จำนวน2ตัวคือFront และ Rear กับจำนวนสมาชิกในคิว
1.2Data Node จะประกอบไปด้วยข้อมูล Data และพอยเตอร์ที่่ชี้ไปยังข้อมูลตัวถัดไป
2.การแทนที่ข้อมูลแบบอาร์เรย์

การดำเนินการเกี่ยวกับคิวได้แก่
1.Create Queueเป็นการจัดสรรหน่วยความจำให้แก่ Head Node และค่า Pointer ทั้งสองตัวมีค่าเป็น null และค่าสมาชิกเป็น 0
2.Enqueue เป็นการเพิ่มข้อมูลเข้าไปในคิว
3.Dequeue เป็นการนำข้อมูลออกจากคิว
4.Queue Front เป็นการนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง
5.Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6.Empty เป็นการตรวจสอบว่าคิวว่างหรือไม่
7.Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8.Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9.Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว

# การนำข้อมูลเข้าสู่คิว จะไม่นำเข้าในขณะที่คิวเต็มหรือไม่มีที่ว่าง
ถ้าพยายามนำข้อมูลเข้าจะเกิดการผิดพลาดที่เรียกว่า overflow

# การนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างได้
ถ้าพยายามจะเอาออกจะเกิดการผิดพลาดที่เรียกว่า underflow

DTS_6 29/07/2552

สรุปบทเรียนเรื่อง Stack ต่อ

การแทนที่ข้อมูลของ Stack สามารถทำได้ 2 วิธี คือ
1) การแทนที่แบบลิงค์ลิสต์
2) การแทนที่แบบอะเรย์

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node
2. Data Node

การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก
โดยไม่มีการลบข้อมูลออกจากสแตก
5. Empty Stackเป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6. Full Stackเป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่ เรียกว่า Stack Overflow
7. Stack Countเป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stackเป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก

การคำนวณนิพจน์ทางคณิตศาสตร์
สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
สำหรับ opertor คือ +-*/ operand คือ ABCหรือตัวแปรอื่นๆ

ตัวอย่างการเขียนนิพจน์ทางคณิตศาสตร์ทั้ง3แบบคือ
1.แบบ infix คือ A+B-C
2.แบบ postfix คือ AB+C-
3.แบบ prefix คือ +AB-C