DTS10-25/08/2009

สรุปเรื่อง Treeทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น เช่น แผนผังองค์ประกอบของหน่วยงานต่างๆ เป็นต้น
โหนดมีความสัมพันธ์กับโหนดในระดับต่ำลงมา หนึ่งระดับได้หลายๆ โหนด เรียกว่าโหนดว่า โหนดแม่ (Parent or Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (Root Node)
โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไมมีโหนดลูกเรียกว่า โหนดใบ (Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch)
นิยามที่เกี่ยวข้องกับทรี
1.ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือเซตของทรีที่แยกจากัน (Disjoint Trees)
2.ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่างๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา ไปทางซ้าย เป็นต้น
3.ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5.กำลัง (Degree) หมายถึง จำนวนทรีย่อยของโหนดนั้นๆ
6.ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้นๆ
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลักจะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก การแทนที่ทรี แต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน วิธีการแทนที่ง่ายที่สุด คือ ทำให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์ที่เท่ากัน โดย
1.โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด
2.แทนทรีด้วยไบนารีทรี โดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
- ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
- ลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไป โหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยเตอร์ในลิงค์ฟิลด์มีค่าเป็น Null
โครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูดไม่เกินสองหรือแต่ละโหนดมีจำนวนทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)
ไบนารีทรีที่ทุกๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกัน
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
1.ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่นๆ
2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3.จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุกๆ โหนดในทรี
โหนดแม่ (แทนด้วย N)
ทรีย่อยทางซ้าย (แทนด้วย L)
ทรียอ่ยทางขวา (แทนด้วย R)
วิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN วิธีที่นิยมใช้ คือ การท่องจากซ้ายไปขวา 3 แบบแรก คือ NLR LNR และ LRN
ลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ
1.)การท่องไปแบบพรีออร์เดอร์ (Preorder Traversal)
ในวิธี NLR มีชั้นตอนการเดิน
1.เยือนโหนดราก
2.ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
3.ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2.)การท่องไปแบบอินออร์เดอร์ (Inorder Traversal)
ในวิธี LNR มีขั้นตอนการเดิน
1.ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
2.เยือนโหนดราก
3.ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3.)การท่องไปแบบโพสออร์เดอร์ (Postorder Traversal)
ในวิธี LRN มีขั้นตอนการเดิน
1.ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
2.ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
3.เยือนโหนดราก

DTS09-11/08/2009

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

DTS07-04/08/2009

สรุปเรื่อง Stackสแตก (Stack) เป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์ มีคุณสมบัติ คือ การเพิ่มหรือลบข้อมูลในสแตก ลักษณะสำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมาจากสแตกเป็นลำดับแรกสุด เช่น การหยิบ CD, การหยิบจาน เป็นต้น
กระบวนการที่สำคัญ 3 กระบวนการ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก ต้องดูด้วยว่าสามารถใส่ข้อมูลลงไปได้หรือไม่ ถ้าสแตกเต็มก็ไม่สามารถเพิ่มข้อมูลได้
2.Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก การ Pop ถ้าไม่มีสมาชิกในสแตก จะทำให้เกิดความผิดพลาดที่เรียกว่า Stack Underflow
3.Stack Top การคัดลอกข้อมูลบนสุดของสแตก แต่ไม่ได้เอาข้อมูลออก
การแทนที่ข้อมูลของสแตก
การแทนที่ทำได้ 2 วิธี
1.การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบด้วย 2 ส่วน คือ
(1)Head Node ประกอบไปด้วย top pointer และจำนวนสมาชิกในสแตก
(2)Data Node ประกอบไปด้วย ข้อมูลและพอยเตอร์
2.การแทนที่ข้อมูลของสแตกแบบอะเรย์
การดำเนินการเกี่ยวกับสแตก ของทั้งแบบลิงค์ลิสต์และแบบอะเรย์ ได้แก่
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 คือ การลบข้อมูลทั้งหมดที่อยู่ในสแตก
ขั้นตอนในการคำนวณ
1.อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละตัวอักษร
2.ถ้าเป็นตัวถูกดำเนินการให้ทำการ push ตัวถูกดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
3.ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่า โดยตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่ 1 ตามลำดับ
4.ทำการคำนวณตัวถูกดำเนินการตัวที่ 1 ด้วยตัวถูกดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
5.ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก
6.ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่

DTS05-28/07/2009

โครงสร้างข้อมูลแบบลิงค์ลิสต์
โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 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
6. กระบวนงาน Retrieve Node
7. ฟังก์ชั่น EmptyList
9. ฟังก์ชั่น list count
10. กระบวนงาน destroy list

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

DTS06-28/07/2009

#include

int main () {
int a,b,c;

cout<<"Please enter to Born(HB) DDMMYYYY:";
cin>>a>>b>>c;


while (b <=12&&b!=0){
cout << a;


switch (b){
case 1:cout<<" January "; break;
case 2:cout<<" February "; break;
case 3:cout<<" March "; break;
case 4:cout<<" April "; break;
case 5:cout<<" May "; break;
case 6:cout<<" June "; break;
case 7:cout<<" July "; break;
case 8:cout<<" August "; break;
case 9:cout<<" September "; break;
case 10:cout<<" October "; break;
case 11:cout<<" November "; break;
case 12:cout<<" December "; break;

b++;

}
cout << c;
cout <<"\nPlease enter to Born(HB) DDMMYYYY:";
cin >>a>>b>>c;
}
cout <<"Gooy Bye";

return 0;
}