DTH ครั้งที่8-25/08/2552

สรุปบทเรียนเรื่อง Tree
ทรีเป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น
แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆ โหนดเรียกโหนดดังกล่าวว่า โหนดแม่(Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (Root Node)โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน
เรียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง
โหนดสองโหนดเรียกว่า กิ่ง (Branch)
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น
การเขียนรูปแบบทรี อาจเขียนได้ 4 แบบได้แก่
1) แบบที่มีรากอยู่ด้านบน
2) แบบที่มีรากอยู่ด้านล่าง
3) แบบที่มีรากอยู่ด้านซ้าย
4) แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่านัลทรี
และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์
2. ทรีที่มีแบบแผน
3. ทรีคล้าย
4. ทรีเหมือน
5. กำลัง
6. ระดับของโหนด
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลักจะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือจำนวน ลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูกการแทนที่ทรี ซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน ทำให้ยากต่อการปฏิบัติการ วิธีการแทนที่ที่ง่ายที่สุดคือ ทำให้แต่ละโหนดมี จำนวนลิงค์ฟิลด์เท่ากัน
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด การแทนที่ทรีด้วยวิธีนี้ จะให้จำนวนฟิลด์ในแต่ละโหนดเท่ากันโดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูกของโหนดที่มีลูกมากที่สุด โหนดใดไม่มีโหลดลูกก็ให้ค่าพอยเตอร์ในลิงค์ฟิลด์นั้นมีค่าเป็น Nullและให้ลิงค์ฟิลด์แรกเก็บค่าพอยเตอร์ชี้ไปยังโหนด ลูกลำดับที่หนึ่ง ลิงค์ฟิลด์ที่สองเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูก
ลำดับที่สอง และลิงค์ฟิลด์อื่นเก็บค่าพอยเตอร์ของโหนดลูก
2. แทนทรีด้วยไบนารีทรีเป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือกำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้นโดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็น
ไบนารีทรี มีลำดับขั้นตอนการแปลง ดังต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบ
ความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี
มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLRLNR LRN NRL RNL และ RLNแต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRNคือ
1. การท่องไปแบบพรีออร์เดอร์
2.การท่องไปแบบอินออร์เดอร์
3. การท่องไปแบบโพสออร์เดอร์

DTH ครั้งที่7-11/08/2552

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

DTH ครั้งที่6-04/08/2552

สแตก(Stach)
เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตกจะกระทำที่ปลายข้างเดียวกัน ซึ่งเรียนว่า Top ของสแตกและลักษณะที่สำคัญของสแตกคือ ข้อมูลที่ได้หลังสุด จะถูกนำออกมาจากสแตกเป็นลำดับสุกแรกสุด เรียกคุณสมบัตินี้ว่า Lifo
การทำงานของสแตกประกอบด้วยกระบวนการ 3 กระบวนการคือ
1.Push คือการนำข้อมูลใส่ลงในสแตก
2.Pop คือการนำข้อมูลออกจากส่วนบนสุดของสแตก
3.Stach Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก
การแทนที่ข้อมูลของสแตกสามารถทำได้2วิธีคือ
1.การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2.การแทนที่ข้อมูลของสแตกแบบอะเรย์
การดำเนินการเกี่ยวกับสแตก
1.Create Stack เป็นการจัดสรรหน่วยความจำลห้แ่ Head Node และส่งค่าตำแหน่งที่ชีไปยัง Head ของสแตก
2.Push Stack เป็นการเพิ่มข้อมูลลงไปในสแตก
3.Pop Stack เป็นการนำข้อมูลบนสุดของสแตกออกจากสแตก
4.Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกโดยไม่มีการลบข้อมูลออกจากสแตก
5.Empty Stack เป็นการตรวจสอบการว่างของสแตก
6.Full Stack เป็นการตรวจสอบว่าสแตกต็มหรือไม่
7.Stack Count เป็นการนับจำนวนสมาชิกที่อยู่ในสแตก
8.Destrog Stack เป็นการลบข้อมูลทั้งหมอที่อยู่ในสแตก
การคำนวนนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเรื่องหมาย สำหรับการคำนวณด้วย โดยไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบคือ
1.นิพจน์ Infix นิพจน์รูปแบบนี้ operator จะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ2ตัว
2.นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวดำเนินการตัวที่1และ2ก่อน แล้วตามด้วย operator
3.นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operator ก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่1และ2