DTS 08-25/08/2552

เรื่อง Tree
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์
ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ
ชั้น (Hierarchical Relationship)
ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน
ต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดง
ความสัมพันธ์ระหว่างข้อมูล
แต่ละโหนดจะมีความสัมพันธ์กับโหนดใน
ระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนด
เรียกโหนดดังกล่าวว่า โหนดแม่
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ
เรียกว่า โหนดลูก
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่
เรียกว่า โหนดราก
โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน
เรียกว่า โหนดพี่น้อง
กว่า โหนดพี่น้อง (Siblings)
โหนดที่ไม่มีโหนดลูก เรียกว่า
โหนดใบ
เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง
โหนดสองโหนด
เรียกว่า กิ่ง
การแทนทรีด้วยโหนดขนาดเท่ากันค่อนข้าง
ใช้เนื้อที่จำนวนมาก เนื่องจากแต่ละโหนดมี
จำนวนโหนดลูกไม่เท่ากันหรือบางโหนดไม่มี
โหนดลูกเลย
ถ้าเป็นทรีที่แต่ละโหนดมีจำนวน
โหนดลูกที่แตกต่างกันมาก จะเป็นการสิ้นเปลือง
เนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์
แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัดเนื้อที่ใน
การจัดเก็บได้มาก เรียกโครงสร้างทรี
ที่แต่ละโหนดมีจำนวนโหนดลูกไม่เกินสอง
หรือแต่ละโหนดมีจำนวน
ทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)

DTS 07-11/08/2552

เรื่อง Queue
คิว (Queue) เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือ
ลิเนียร์ลิสต์ซึ่งการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่ง
เรียกว่าส่วนท้ายหรือเรียร์ (rear) และการนำข้อมูลออกจะ
กระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า หรือฟรอนต์
(front)
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อน
ออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
การทำงานของคิว
การใส่สมาชิกตัวใหม่ลงในคิว
เรียกว่า Enqueue ซึ่งมีรูปแบบคือ
enqueue (queue, newElement)
หมายถึง การใส่ข้อมูล
newElement ลงไปที่ส่วนเรียร์
การแทนที่ข้อมูลของคิว
สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การดำเนินการเกี่ยวกับคิว
การดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queue 6. Empty Queue
2. Enqueue 7. Full Queue
3. Dequeue 8. Queue Count
4. Queue Front 9. Destroy Queue
5. Queue Rear

DTS 06-10/08/2009

เรื่อง Stack
สแตก (Stack)

เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack) ลักษณะที่สำคัญของสแตกคือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)

การดำเนินงานพื้นฐานของสแตก
การทำงานต่าง ๆ ของสแตกจะกระทำที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วยการทำงานของสแตกจะประกอบด้วย
กระบวนการ 3 กระบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้ push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s ในการเพิ่มข้อมูลลงในสแตก จะต้องทำการตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม่สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตกเช่น ต้องการนำข้อมูลออกจากสแตก s
ไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนำข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย
แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflowเพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก

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


การดำเนินการเกี่ยวกับสแตก
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack 5. Empty Stack
2. Push Stack 6. Full Stack
3. Pop Stack 7. Stack Count
4. Stack Top 8. Destroy Stack

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 เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก

การประยุกต์ใช้สแตก
การประยุกต์ใช้สแตก จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
การคำนวณนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2