DTS 09/25-08-2552

สรุปเรื่อง Tree
ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น เช่น แผนผังองค์ประกอบของหน่วยงานต่างๆ เป็นต้น
โหนดมีความสัมพันธ์กับโหนดในระดับต่ำลงมา หนึ่งระดับได้หลายๆ โหนด เรียกว่าโหนดว่า โหนดแม่ (Parent or Mother Node)
โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)
โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (Root Node)
โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)
โหนดที่ไมมีโหนดลูกเรียกว่า โหนดใบ (Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch)
นิยามของทรี
1.)นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง
การเขียนรูปแบบทรี เขียนได้ 4 แบบ คือ
1.แบบที่มีรากอยู่ด้านบน
2.แบบที่มีรากอยู่ด้านล่าง
3.แบบที่มีรากอยู่ด้านซ้าย
4.แบบที่มีรากอยู่ด้านขวา
2.)นิยามทรีด้วยรูปแบบรีเครอร์ซีฟ
ทรี ประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ถ้าว่างไม่มีโหนดใดๆ เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็น ทรีย่อย (Sub Tree)
นิยามที่เกี่ยวข้องกับทรี
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.เยือนโหนดราก

DTS 08/11-08-2552

สรุปเรื่อง Queue
คิว (Queue) เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ การเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่ง เรียกว่าส่วนท้ายหรือเรียร์ (rear) และการนำข้อมูลออกจะทำอีกข้างหนึ่ง เรียกว่า ส่วนหน้า หรือฟรอนต์ (front)
ลักษณะการทำงานของคิว
เป็นลักษณะของการเข้าก่อนออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
การทำงานของคิว
- การใส่สมาชิกตัวใหม่ลงในคิว เรียกว่า Enqueue
- การนำสมาชิกออกจากคิว เรียกว่า Dequeue
- การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง เรียกว่า Queue Front
- การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดง เรียกว่า Queue Rear
การแทนที่ข้อมูลของคิว
มี 2 วิธี
1.การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
ประกอบไปด้วย 2 ส่วน คือ
(1)Head Node ประกอบไปด้วย 3 ส่วน คือ พอยเตอร์ 2 ตัว คือ Front และ rear กับจำนวนสมาชิกในคิว
(2)Data Node ประกอบไปด้วยข้อมูลและพอยเตอร์ที่ชี้ไปยังข้อมูลถัดไป
2.การแทนที่ข้อมูลของคิวแบบอะเรย์
การนำข้อมูลเข้าจะต้องดูว่าคิวเต็มหรือว่างไหม ถ้านำข้อมูลเข้าไปจะทำให้เกิดความผิดพลาดขึ้น overflow
การนำข้อมูลออกจากคิว จะไม่สามารถทำได้ถ้านำข้อมูลออกแล้วทำให้คิวว่าง จะทำให้เกิดความผิดพลาดขึ้น underflow
กรณีคิวเป็นแบบวงกลม คิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อยๆ จะนกระทั้ง rear มีค่าน้อยกว่า front อยู่หนึ่งค่า คือ rear = front - 1
การดำเนินการเกี่ยวกับคิว
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 การลบข้อมูลทั้งหมดที่อยู่ในคิว
การประยุกต์ใช้คิว
คิวถูกประยุกต์ใช้มากในการจำลองระบบงานธุรกิจ เช่น การให้บริการลูกค้า คือ ต้องวิเคราะห์จำนวนลูกค้าในคิว เพื่อให้ลูกค้าเสียเวลาน้อยที่สุด ในด้านคอมพิวเตอร์ ได้นำคิวเข้ามาใช้ คือ ในระบบปฏิบัติการ ในเรื่องของคิวของงานที่เข้ามาทำงาน จัดให้งานที่เข้ามาได้ทำงานคามลำดับความสำคัญ

DTS 07/04-08-2552

สรุปเรื่อง 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 คือ การลบข้อมูลทั้งหมดที่อยู่ในสแตก
การประยุกต์ใช้สแตก
จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ ที่ขั้นตอนแรกต้องเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษา การคำนวณนิพจน์ทางคณิตศาสตร์และรีเคอร์ชั่น เป็นต้น
การทำงานของโปรแกรมที่มีโปรแกรมย่อย
สแตกจะเข้ามาช่วยในการทำงาน คือ แต่ละจุดจะเก็บเลขที่คำสั่งถัดไปที่เครื่องต้องทำงานไว้ในสแตก หลังจากเสร็จสิ้นโปรแกรมย่อยแล้วจะทำการ pop ค่าเลขที่คำสั่เพื่อกลับไปทำงานต่อในโปรแกรมย่อย
การคำนวณนิพจน์ทางคณิตศาสตร์ มี 3 รูปแบบ
1.นิพจน์ Infix operator จะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว เช่น A+B-C
2.นิพจน์ Postfix จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 แล้วตามด้วย operator เช่น AB+C/DE*-
3.นิพจน์ Prefix จะต้องเขียน operator ก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2 เช่น -+A*BC/DE
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix
1.อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2.ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3.ถ้าเป็นตัวดำเนินการจะนำค่าลำดับความสำคัญของตัวดำเนินการที่อ่านเข้ามาเปรียบเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้องกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4.ตัวดำเนินการที่เป็นวงเล็บปิด ")" จะไม่ push ลงในสแตก แต่มีผลให้ตัวดำเนินการอื่นๆ ถูก pop ออกจากสแตกนำไปเรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ "(" จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5.เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์ Postfix
การคำนวณค่า Postfix ที่แปลงมา ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตกช่วย
ขั้นตอนในการคำนวณ
1.อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละตัวอักษร
2.ถ้าเป็นตัวถูกดำเนินการให้ทำการ push ตัวถูกดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
3.ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่า โดยตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่ 1 ตามลำดับ
4.ทำการคำนวณตัวถูกดำเนินการตัวที่ 1 ด้วยตัวถูกดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
5.ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก
6.ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่

DTS 06/28-07-2552

#include<iostream.h>
#include<conio.h>
void main()
{
int n,i;
float a,min;
clrscr();
cout<<"number : ";
cin>>n; cout<<"number1 : ";
cin>>a;
min=a;
for(i=2;i<=n;i++)
{
cout<<"number"<<i<<": ";
cin>>a;
if(min>a)
{
min=a;
}
}
cout<<"number less than : ";
cout<<min;
getch();
}