DTS 09-24/08/2009

เรื่อง ทรี (Tree)

ทรี (Tree) เป็นโครงสร้างข้อมูลไม่เชิงเส้น โดยจะมีการเรียงข้อมูลลดหลั่งลงเป็นลำดับๆไปส่วนมากจะใช้ให้เห็นถึงความสำคัญข้อมูลว่าอันไหนสำคัญกว่าเเละอันไหนรองๆลงมา

ชื่อเรียกของโหนด

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

นิยามของทรี

1.เป็นนิยามเเบบกราฟ

-ทรีคือ กราฟที่จะไม่มีวงจรปิดจำนวนโหนดทั้งหมด เท่ากับZ กิ่งของโหนดก็จะเท่ากับ Z-1 เสมอ

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ

-ทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด ถ้าเป็นโหนดว่างคือนัลทรี เเละโหนดที่ออกมาจากโหนดราก คือ ทรีย่อย

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

1. ฟอร์เรสต์ (Forest) คือ กลุ่มของทรีที่มีโหนดรากเเละย่อยๆออกมา

2. ทรีที่มีแบบแผน (Ordered Tree) คือ ทรีที่โหนดมีความสัมพันธ์ที่แน่นอนหรือมีเเบบเเผนนั้นเอง

3. ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนเเต่ข้อมูลไม่เหมือนกัน

4. ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ ทั้งข้อมูลทั้งโครงสร้าง

5. กำลัง (Degree) คือ จำนวนทรีย่อยของโหนด

6. ระดับของโหนด (Level of Node) คือ การเเบ่งระดับของทรีเป็นชั้นๆเช่นโหนดรากคือระดับ1โหนดเเม่ระดับ 2 เป็นต้น

การเเทนที่ในหน่วยความจำมี 2 แบบ คือ

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

2.เเบบไบนารีทรี คือเเต่ละโหนดจะมีลิงค์เเค่2ลิงค์เท่านั้น

DTS 08-11/08/2009

เรื่อง คิว (Queue)

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



การทำงานของคิว
การใส่สมาชิกตัวใหม่ลงในคิว เรียกว่า Enqueue ซึ่งมีรูปแบบคือ enqueue (queue, newElement) หมายถึง การใส่ข้อมูล newElement ลงไปที่ส่วนเรียร์ของคิว

การนำสมาชิกออกจากคิว เรียกว่า Dequeue ซึ่งมีรูปแบบคือ dequeue (queue, element) หมายถึง การนำออกจากส่วนหน้าของคิวและให้ ข้อมูลนั้นกับ element

การทำงานของคิวโดยพื้นฐาน
1. การใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า E
2. การนำสมาชิกออกจากคิว เรียกว่าDequeue
3. การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะเรียกว่า Queue Frontแต่จะไม่ทำการเอาข้อมูลออกจากคิว
4. การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะ เรียกว่าQueue Rear แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว




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

DTS 06-04/08/2009

Lecture 4 : เรื่อง Stack

สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (TopOf 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เพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป

การแทนที่ข้อมูลของสแตก :
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ

1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 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

3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก

4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก

5. Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่ เรียกว่า " Stack Underflow "

6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า " Stack Overflow "

7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก

8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก

2. การแทนที่ข้อมูลของสแตกแบบอะเรย์

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

การประยุกต์ใช้สแตก :
การประยุกต์ใช้สแตก จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)

ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ :
Postfix ..
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์ Postfix

DTS 05-28/07/2009

Lecture 7 : เรื่อง Linked List

ลิงค์ลิสต์ (Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่าง ๆ โดยมีพอยเตอร์เป็นตัวเชื่อมต่อแต่ละอิลิเมนท์ เรียกว่าโนด (Node) ซึ่งในแต่ละโนดจะประกอบไปด้วย 2 ส่วน คือData จะเก็บข้อมูลของอิลิเมนท์ และส่วนที่สอง คือ Link Field จะทำหน้าที่เก็บตำแหน่งของโนดต่อไปในลิสต์

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

ในลิงค์ลิสต์จะมีตัวแปรสำหรับชี้ตำแหน่งลิสต์ (List pointer variable) ซึ่งเป็นที่เก็บตำแหน่งเริ่มต้นของลิสต์ ซึ่งก็คือ : โหนดแรกของลิสต์นั่นเอง ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหนดแรกของลิสต์จะเป็น Null

โครงสร้างข้อมูลแบบลิงค์ลิสต์ : จะแบ่งเป็น 2 ส่วน คือ

1. Head Structure จะประกอบไปด้วย 3 ส่วน ได้แก่

- จำนวนโหนดในลิสต์ (Count)

-พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง (Pos)

-พอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์ (Head)

2. Data Node Structure จะประกอบไปด้วยข้อมูล(Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน :

1. กระบวนงาน Create List

หน้าที่ : สร้างลิสต์ว่าง
ผลลัพธ์ : ลิสต์ว่าง

2. กระบวนงาน Insert Node

หน้าที่ : เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการ
ข้อมูลนำเข้า : ลิสต์ ข้อมูล และตำแหน่ง
ผลลัพธ์ : ลิสต์ที่มีการเปลี่ยนแปลง

3. กระบวนงาน Delete Node

หน้าที่ : ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ

ข้อมูลนำเข้า : ข้อมูลและตำแหน่ง
ผลลัพธ์ : ลิสต์ที่มีการเปลี่ยนแปลง

4. กระบวนงาน Search list

หน้าที่ : ค้นหาข้อมูลในลิสต์ที่ต้องการ
ข้อมูล : นำเข้าลิสต์
ผลลัพธ์ : ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล

5. กระบวนงาน Traverse

หน้าที่ : ท่องไปในลิสต์เพื่อเข้าถึงและ
ประมวลผล : ข้อมูลนำเข้าลิสต์
ผลลัพธ์ : ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node ,

รวมฟิลด์ในลิสต์ ,คำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น

6. กระบวนงาน Retrieve Node

หน้าที่ : หาตำแหน่งข้อมูลจากลิสต์
ข้อมูล : นำเข้าลิสต์
ผลลัพธ์ : ตำแหน่งข้อมูลที่อยู่ในลิสต์

7. ฟังก์ชั่น EmptyList

หน้าที่ : ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์
ผลลัพธ์ : เป็นจริง ถ้าลิสต์ว่าง
เป็นเท็จ : ถ้าลิสต์ไม่ว่าง

8. ฟังก์ชั่น FullList

หน้าที่ : ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูล
นำเข้า : ลิสต์
ผลลัพธ์ : เป็นจริง ถ้าหน่วยความจำเต็ม
เป็นเท็จ : ถ้าสามารถมีโหนดอื่น

9. ฟังก์ชั่น list count

หน้าที่ : นับจำนวนข้อมูลที่อยู่ในลิสต์
ข้อมูลนำ : เข้าลิสต์
ผลลัพธ์ : จำนวนข้อมูลที่อยู่ในลิสต์

Algorithm listCount (val pList )
Pre pList is a pointer to a valid list head structure
Return count for number of node in list
1. Return (pList->count)
End listCount

10. กระบวนงาน destroy list

หน้าที่ : ทำลายลิสต์
ข้อมูลนำเข้า : ลิสต์
ผลลัพธ์ : ไม่มีลิสต์

Linked List แบบซับซ้อน :

1. Circular Linked List เป็นลิงค์ลิสต์ที่สมาชิกตัวสุดท้ายมีตัวชี้ (list) ชี้ไปที่สมาชิกตัวแรกของลิงค์ลิสต์ จะมีการทำงานไปในทิศทางเดียวเท่านั้นคือเป็นแบบวงกลม

2. Double Linked List เป็นลิงค์ลิสต์ที่มีทิศทางการทำงานแบบ 2 ทิศทาง ในลิงค์ลิสต์แบบ 2 ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูล
ก่อนหน้า (backward pointer)

และตัวชี้ข้อมูลถัดไป (forward pointer)