DTS 07 25/08/09

เรื่อง TREE
ทรีมีความสัมพันธ์ระหว่าง โหนดจะมีความลดหลั่นกันเป็นลำดับชั้น ได้มีการนำรูปแบบทรีไปประยุกต์ในการใช้งานต่างๆ หรือ การมีสายบังคับบัญชา โหนดแต่ละโหนดจะต้องประกอบไปด้วยโหนดแม่

โหนดที่ต่ำกว่าโหนดแม่จะเรียกว่าโหนดลูก

โหนดที่สูงสุดและไม่มีโหนดแม่จะเรียกว่า โหนดราก

โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง

โหนดที่ไม่มีโหนดลูฏจะเรียกว่า โหนดใบ

เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง

นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด ในโครงสร้าง
การเขียนรูปแบบทรีเขียนได้ 4 แบบ
1) แบบที่มีรากอยู่ด้านบน
2) แบบที่มีรากอยู่ด้านล่าง
3) แบบที่มีรากอยู่ด้านซ้าย
4) แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟหรือการเวียนเกิด คือ ทรีที่ประกอบไปด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ จะเรียกว่า Null Tree ถ้ามีโหนดหนึ่งเป็นโหนดราหอีกโหนดจะเป็นทรีย่อย

DTS 06-04/08/09

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

การดำเนินงานพื้นฐานของสแตก
การทำงานต่าง ๆ ของสแตกจะกระทำที่ปลาย
ข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วย
การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวน
การที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้

2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตกpush (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก

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

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

DTS 05-28/07/09

โครงสร้างข้อมูลแบบลิงค์ลิสต์ โครงสร้างข้อมูลแบบลิงค์ลิสต์
จะแบ่งเป็น 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
หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์
ข้อมูลนำเข้าลิสต์
ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน destroy list
หน้าที่ ทำลายลิสต์
ข้อมูลนำเข้า ลิสต์
ผลลัพธ์ ไม่มีลิสต์

การบ้าน
#include <iostream.h>
int main()
{
int index;
for(index=0;index<5;index++)
{
if(index<4)
{
if(index==3)
cout << "Index is 3" << "\n";
else
cout << "Index is less than 3" << "\n";
}
else
cout << "Index is greater than 3" << "\n"; }
return 0;
}