DTS 11-08/09/2009

ทบทวนบทเรียน ครั้งที่ 9

เรื่อง Graph(ต่อจากครั้งที่เเล้ว)เเละเรื่อง Sorting

Graph การท่องไปในกราฟ1.เเบบกว้าง โดยเลือกโหนดที่เป็นจุดเริ่มต้น เเละหาโหนดที่ใกล้สุดเยือนจนครบเหมือนคิว ที่ทีละระดับ เข้าก่อนออกก่อน2.เเบบลึก คล้ายกับการท่องไปในทรี โดยมีโหนดเเรกถัดไปให้ลึกที่สุดก่อนเเล้วค่อยย้อนกลับมาตามเเนวเดิมไปโหนดต่อไปเหมือนกับสแตก

Sorting

Sorting คือการเรียงลำดับจัดเเบบเเผนเพื่อให้ค้นหาข้อมูลได้อย่างมีประสิทธิภาพ

วิธีการเรียง มี2ประเภท

1.ภายใน ข้อมูลทั้งหมดต้องอยู๋ในความจำหลัก เท่านั้น และจะคำนึกถึงเวลาใช้ในการเปรียบเทียบเเละการเลี่อนข้อมูล

2.ภายนอก ข้อมูลจะเก็บในความจำสำรอง ใช้เวลาในการถ่ายเทข้อมูลมาก

การเรียงเเบบเลือกทำการเลือก

ข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละตัวโดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับมาการเเทนที่ โดยการเปรียบเทียบเเย้วย้ายที่สลับตำเเหน่งกันปกติ เป็นวิธีที่ง่ายที่สุดเเต่มีข้อเสียในการจัดเรียงที่ค่อนข้างนานเหมือนการเปรียบเทียบถ้าจำนวนสมาชิกทั้งหมดเท่ากับ x การเปรียบเทียบก็เท่ากับ X-1 เลยทีเดียว

การเรียงเเบบฟอง

เป็นการเทียบข้อมูลในตำแหน่งที่ติดกันจะมีการเปรียบเทียบข้อมูลในเเถวลำดับ ช่องเเรก กับช่องถัดไป ถ้าช่องหลังมีข้อมูลใหญ่กว่า ก็จะสลับที่กับช่องเเรก เเละต่อไปก็เปรียบช่อง2 - 3 ถ้าช่อง3มากกว่าช่อง2ก็จะสลับที่ เท่ากับว่า เราจะสลับถ้าข้อมูลที่มากกว่าไว้ทางซ้ายมือ เเละเหรียบเทียบไปเรื่อยๆจนครบ และเเถวที่ได้ถูกเรียงไว้เเล้ว ก็จะถูกวางไว้ตำเเหน่งนั้นตลอด เเละเป็นคำตอบในที่สุด วิธีนี้เป็นรูปแบบที่นิยมใช้กันมาก

DTS 10-01/09/2009

ทบทวนบทเรียนครั้งที่ 8

เรื่อง กราฟ

กราฟคือ โครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure)

ความเเตกต่างกับโครงสร้างทรี คือ โดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูป และการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex(โหนด) และ edge(เส้นเชื่อม) กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้

ศัพท์ที่เกี่ยวข้อง

1.เวอร์เทก (Vertex) หมายถึง โหนด

2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด

3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด

4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกันตัวอย่างของ

กราฟในชีวิตประจำวัน เช่น

1.กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง

2.ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น

การเเทนที่กราฟในหน่วยความจำ

1.เเบบอะเรย์ 2 มิติ คือ จะมีมิติที่1 เก็บค่าโหนดต่างๆ มิติที่2 จะเก็บโหนดที่เเสดงความสัมพันธ์กับโหนดที่1 จะค่อนข้างเปลี้องเนื้อที่เเละมีความซ้ำซ้อนกัน จึงไม่เป็นที่นิยม

2.มีการเก็บโดยใช้พอยเตอร์เเละโหนด เเต่ก็ยังเป็นอะเรย์ 2 มิติ อยู่และต้องจัดเก็บโหนดที่สัมพันธ์ด้วยในแถวลำดับ1 มิติ เเต่มีความยุ่งยากเเละซับซ้อน ไม่เหมาะกับกราฟที่มีการเปลี่ยนเเปลงตลอดเวลา

3.วิธีแอดจาเซนซีลิสต์(Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธีที่2 แต่ต่างกันตรงที่ จะใช้ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข

DTS 09-24/08/2009

ทบทวนบทเรียนครั้งที่ 7

เรื่อง ทรี(Tree)

ทรี เป็นโครงสร้างข้อมูลไม่เชิงเส้น โดยจะมีการเรียงข้อมูลลดหลั่งลงเป็นลำดับๆไปส่วนมากจะใช้ให้เห็นถึงความสำคัญข้อมูลว่าอันไหนสำคัญกว่าเเละอันไหนรองๆลงมา

ชื่อเรียกของโหนด

-จะมีการเีรียงข้อมูลโดยข้อมูลที่อยู่ในระดับสูงสุดจะเรียกว่า โหนดราก

-รองลงมาจะเป็นโหนดเเม่

-ข้อมูลที่ออกมาจากโหนดเเม่ คือ โหนดลูก

-โหนดที่มีเเม่เป็นโหนดเดียวกัน เรียกว่าโหนดพี่น้อง-โหนดที่ไม่มีลูกคือ โหนดใบ

-เส้นที่ลากเเสดงความสัมพันธ์คือ กิ่ง

นิยามของทรี

1.เป็นนิยามเเบบกราฟ-ทรีคือ กราฟที่จะไม่มีวงจรปิดจำนวนโหนดทั้งหมด เท่ากับZ กิ่งของโหนดก็จะเท่ากับ Z-1 เสมอ

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ-ทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด ถ้าเป็นโหนดว่างคือนัลทรี เเละโหนดที่ออกมาจากโหนดราก คือ ทรีย่อย

นิยามที่เกี่ยวกับทรี

1. ฟอร์เรสต์ (Forest)คือ กลุ่มของทรีที่มีโหนดรากเเละย่อยๆออกมา

2. ทรีที่มีแบบแผน (Ordered Tree)คือ ทรีที่โหนดมีความสัมพันธ์ที่แน่นอนหรือมีเเบบเเผนนั้นเอง

3. ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนเเต่ข้อมูลไม่เหมือนกัน

4. ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ ทั้งข้อมูลทั้งโครงสร้าง

5. กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด

6. ระดับของโหนด (Level of Node) คือการเเบ่งระดับของทรีเป็นชั้นๆเช่นโหนดรากคือระดับ1 โหนดเเม่ระดับ 2 เป็นต้น

การเเทนที่ในหน่วยความจำมี 2 แบบ

1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด การแทนที่ทรีด้วยวิธีนี้ จะให้จำนวนฟิลด์ในแต่ละโหนดเท่ากันโดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูกของโหนดที่มีลูกมากที่สุด

2.เเบบไบนารีทรี คือเเต่ละโหนดจะมีลิงค์เเค่2ลิงค์เท่านั้นมีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLNN คือ เยือนโหนดรากL คือ ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์R คือ ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์

DTS 08-11/08/2009

ทบทวนบทเรียน ครั้งที่ 6
เรื่อง คิว (Queue)

คิว เป็นโครงสร้างคล้ายกับ Stack เเต่ต่างตรงที่ว่าคิว เข้าก่อนออกก่อน เหมือนการเรียงคิวซื้อของ นั้นเองเเต่ถ้าเป็นสเเตกจะเป็นเข้าก่อนออกที่หลัง โดยคิวจะมีโครงสร้างงการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่งเรียกว่าส่วนท้ายหรือเรียร์ (rear) และการนำข้อมูลออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า หรือฟรอนต์(front)

การทำงานของคิวโดยพื้นฐาน

1.การใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueue

2.การนำสมาชิกออกจากคิว เรียกว่าDequeue

3.การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะเรียกว่า Queue Frontแต่จะไม่ทำการเอาข้อมูลออกจากคิว

4.การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะ เรียกว่าQueue Rear แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว

ตัวดำเนินการเกี่ยวกับคิว มีลักษณะคล้ายของสแตกมาก ดังนี้

1. Create Queue คือการ สร้างคิว มีผลคือได้คิวว่าง

2. Enqueue คือการเพิ่มสมาชิกลงไป

3. Dequeue คือการนำสมาชิกออกมา

4. Queue Front คือการนำส่วนของฟรอนด์ ออกมาเเสดงโดยไม่เอาข้อมูลออกมา

5. Queue Rear คือการนำข้อมูลส่วนเรียร์มาเเสดงเเต่ไม่เอาเข้ามูลเข้ามา

6. Empty Queueคือการตรวจสอบว่าคิวว่างหรือไม่ ถ้าเราเห้นว่าคิวว่างเเล้วยังจะลบข้อมูลอีกก็จะเกิดข้อผิดพลาดที่เรียกว่า underflow

7. Full Queue คือการตรวจสอบว่าคิวเต็มหรือไม่ ถ้าตรวจสอบเเล้วคิวเต็มเเล้วเรายังจะเพิ่มข้อมูลเ้ข้าไป คิวจะเกิดข้อผิดพลาดที่เรียกว่าoverflow

8. Queue Count คือการนับจำนวนสมาชิกในคิว9. Destroy Queueคือการล้างคิวทั้งหมด เหมือนลบทิ้งไป โดยจะได้คิวว่างมาเป็นผลลัพย์

DTS 07-04/08/2009

ทบทวนบทเรียนครั้งที่ 5

เรื่อง Stack

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

การดำเนินงานของสเเตกมี3เเบบ(โดยพื้นฐาน)
1. การpush เป็นการใส่ข้อมูลลงสเเตกโดยถ้าสเเตกยังไม่เต็มก็ใส่ลงไปได้
2. การ pop เป็นการนำข้อมูลออกมาจากสเเตกโดยจะpopข้อมูลที่อยู่บนสุดเป็นเงื่อนไขที่ สำคัญมากแต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก.

การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack -เป็นการดำเนินการสร้างสแตก
2. Push Stack -เป็นการใส่ข้อมูลลงสเเตกโดยถ้าสเเตกยังไม่เต็มก็ใส่ลงไปได้
3. Pop Stack -เป็นการนำข้อมูลออกมาจากสเเตกโดยจะpopข้อมูลที่อยู่บนสุดเป็นเงื่อนไขที่สำคัญมากแต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow
4. Stack Top -เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก
5. Empty Stack -เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้มีความผิดพลาดในการนำข้อมูลออกจาก สแตกที่เรียกว่า Stack Underflow
6. Full Stack -เป็นการตรวจสอบว่าสแตกเต็มหรือไม่จะได้ไม่ผิดพลาดที่เรียกว่าStack Overflow
7. Stack Count -การนับจำนวนสมาชิก(ข้อมูล)ในสเเตก
8. Destroy Stack -การลบข้อมูลทั้งหมดในสเเตกจนกลายเป็นสเเตกว่าง

รวมทั้งมีการคำนวณนิพจน์ทางคณิตศาสตร์
--การคำนวณนี้จะเป็นการที่เราต้องเเปลงค่า Infix เป็น Postfixมีหลักการทำอยู่โดยเราต้องเปรียบเทียบตัวดำเนินการก่อนที่จะรับเข้าเป็นPostfixส่วนตัวถูกดำเนินการสามารถเข้าPostfix ได้ทันที
--การเเปลงกับจาก Postfix เป็น Infix เป็นการ
1. อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละตัวอักษร
2. ถ้าเป็นตัวถูกดำเนินการให้ทำการpushตัวถูกดำเนินการนั้นลงในสแตกแล้วกลับไปอ่านอักษรตัวใหม่เข้ามา3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่าโดยตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่1
4. ทำการคำนวณ ตัวถูกดำเนินการตัวที่ 1ด้วยตัวถูก ดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
5. ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก
6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่

DTS05-28/07/2009

เรื่อง Linked ListLinked List
เป็นการจัดเก็บชุดข้อมูลมีพอยเตอร์เป็นตัวเชื่อมโยงต่อเนื่องกันไปตามลำดับซึ่งในลิงค์ลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่า
โหนด (Node) ในหนึ่งโหนดจะประกอบด้วย1.ส่วนของข้อมูลที่ต้อง
การจัดเก็บ เรียกว่าส่วน (Data)2.ส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนด
ถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์**หากโหนดแรกไม่มีข้อมูลหรือไม่มีข้อมูลในโหนดที่อยู่ถัดไป
ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL เขียนแทนด้วย
เครื่องหมาย กากบาทโครงสร้างข้อมูลแบบลิงค์ลิสต์ประกอบด้วย 2 ส่วน1.Head Structure แบ่งเป็น 3ส่วน-count เป็นการนับจำนวนข้อมูลที่มีอยู่ในลิสต์นั้น-pos พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง-head พอยเตอร์ที่ชี้ไปยังโหนดแรกของลิสต์2.Data Node Structure จะประกอบด้วย ข้อมูลและพอยเตอร์
ที่ชี้ไปโหนดถัดไปการเพิ่มข้อมูลลงไปในลิงค์ลิสต์นั้น จากที่ Head Structure
ในส่วนของ count จะมีค่าเป็น 0 นั้นหมายถึงในลิสต์นั้นยังไม่มี
ข้อมูลใดเลย ส่วน head จะมีเครื่องหมายกากบาท นั้นหมายถึง
ในลิสต์นั้นไม่มีการเชื่อมโยงไปยังข้อมูลแรก แต่ถ้าต้องการเพิ่ม
ข้อมูลลงไปในลิสต์ Data Node ในส่วนของข้อมูล (Data)จะมี
ค่าเก็บอยู่ แล้ว count ก็จะเปลี่ยนค่าจาก 0 เป็น 1 คือ การบ่งบอก
ถึงจำนวนข้อมูลที่มีอยู่ในลิสต์นั้น แล้ว head ก็จะชี้ไปยัง
ข้อมูล (Data) ตัวแรกของลิสต์ ส่วนพอยเตอร์ที่ชี้ไปโหนดถัดไป
จะเป็นเครื่องหมายกากบาทแทน
การลบข้อมูลในลิงค์ลิสต์ ถ้าต้องการลบข้อมูลตัวใดในลิสต์
สามารถลบได้เลย แต่ต้องเปลี่ยน head เพื่อชี้ไปยังข้อมูลตัวแรก
ของลิสต์กรณีที่ลบข้อมูลตัวแรกออก แล้ว link คือ เมื่อลบข้อมูล
ตัวใดออกควรชี้ link ถัดไปให้ถูกต้องด้วย