วันพุธที่ 30 กันยายน พ.ศ. 2552

DTS 06-28/07/2009

#include
#include
int main ()
{
long int num;
cout<<"************* Count Back to one *************"<<'\n'<<'\n';
cout<<"Please enter number (0 to STOP):";
cin>>num;
while(num!=0){
while (num>0) {
cout<>'\n';
num--;
}
cout<<"Please enter intiger(0 to STOP):";
cin>>num;
}
clrscr();
cout<<"---------------Good Bye--------------";
return 0;
}

วันอาทิตย์ที่ 13 กันยายน พ.ศ. 2552

DTS10-01/09/2009

สรุป Tree(ต่อ)
เอ็กซ์เพรสชันทรี (Expression Tree)การนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์
ลำดับขั้นตอนการคำนวณความสำคัญของเครื่องหมายมีดังนี้
-ฟังก์ชัน
-วงเล็บ
-ยกกำลัง
-เครื่องหมายหน้าเลขจำนวน(unary)
-คูณ หรือ หาร
-บวก หรือ ลบ
-ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
สรุป กราฟ (Graph)
กราฟ (Graph) โครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น นำไปใช้แก้ปัญหาที่ค่อนข้างซ้บซ้นอ
เช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
นิยามของกราฟ
กราฟ เป็นโครสร้างข้อมูบแบบไม่ใช่เชิงเส้น ที่ประกอบ
1.โหนด (Nodes) หรือเวอร์เทกซ์ (Vertexes)
2.เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
-กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า กราฟแบบไม่มีทิศทาง
-ถ้ากราฟมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟว่า กราฟแบบมีทิศทาง บางครั้งเรียกว่า ไดกราฟ
-การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ระหว่างโหนดไม่มีรูปแบบที่ตายตัว
-เขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ของสิ่งที่สนใจแทนโหนดด้วยจุด (pointes) หรือวงกลม (circles) ที่มีชื่อหรือข้อมูลกำกับ
ลักษณะของกราฟ
-กราฟที่มีลักษณะต่อเนื่อง (Connected) เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใดๆ ไปยังโหนดอื่นเสมอ
-กราฟที่มีลักษณะเป็นวิถี (Path) มีเส้นเชื่อมไปยังโหนดต่างๆ อย่างเป็นลำดับ โดยแต่ละโหนดจะเป็นโหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป
-กราฟที่เป็นวัฎจักร (Cycle) ต้องมีอย่างน้อย 3 โหนด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก
-กราฟที่มีลักษณะไม่ต่อเนื่อง (Disconnected) ไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลยกราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)รูปแบบของกราฟแบบมีทิศทางเหมือนกับรูปแบบของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟแบนี้จะทิศทางกำกับด้วยเท่านั้น

DTS09-25/08/2009

สรุปเรื่อง 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.เยือนโหนดราก