ลูกแรดเตรียมพร้อมล่าเหยื่อ

สิ่งที่ได้รับจากการฝึกประสบการณ์วิชาชีพ คือ ในการทำงานเป็นทีม สมาชิกในทีมจะต้องมีสามัคคีกัน และต้องสามารถช่วยแบ่งเบาภาระหน้าที่ในการทำงานของทีมได้ ต้องไม่เห็นแก่ประโยชน์ของตนเพียงคนเดียว การมีน้ำใจให้แก่เพื่อนๆไม่ว่าจะเป็นเพื่อนห้องเดียวกันหรือเพื่อนต่างห้องกัน

ในการทำงานแต่ละครั้งต้องมีอุปสรรคเข้ามาเกี่ยวข้องอยู่เสมอ ไม่ว่าจะเป็นเรื่องของการติดต่อสื่อสารที่เข้าใจไม่ตรงกันระหว่างผู้รับสารและผู้สื่อสาร ฯลฯ

DTS11-15/09/09

SUMMARY B4 FINAL

สรุป TREE

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

โหนดแต่ละโหนดจะต้องประกอบไปด้วยโหนดแม่

โหนดที่ต่ำกว่าโหนดแม่จะเรียกว่าโหนดลูก

โหนดที่สูงสุดและไม่มีโหนดแม่จะเรียกว่า โหนดราก

โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง

โหนดที่ไม่มีโหนดลูฏจะเรียกว่า โหนดใบ

เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง

นิยามของทรี

1. นิยามทรีด้วยนิยามของกราฟ คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด ในโครงสร้าง การเขียนรูปแบบทรีเขียนได้ 4 แบบ
1) แบบที่มีรากอยู่ด้านบน
2) แบบที่มีรากอยู่ด้านล่าง
3) แบบที่มีรากอยู่ด้านซ้าย
4) แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟหรือการเวียนเกิด คือ ทรีที่ประกอบไปด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ จะเรียกว่า Null Tree ถ้ามีโหนดหนึ่งเป็นโหนดราหอีกโหนดจะเป็นทรีย่อย
----------------------------------------------------------------------------
สรุป GRAPE

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

นิยมนำไปใช้แก้ปัญหาหลัก ๆ 2 ปัญหา คือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด(Minimum Spanning Trees :MST)
1. เรียงลำดับเอดจ์ ตามน้ำหนัก
2. สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนด และไม่มีเส้นเชื่อม
3. เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลย ถ้ามีน้ำหนักซ้ำกันหลายค่าให้สุ่มมา 1 เส้น
4. พิจารณาเอดจ์ที่จะเลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบ ให้ตัดทิ้งนอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5. ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่หมดให้ไปทำข้อ 3
6. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา
7. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (5,7) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
8. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (1,4) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
9. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(3,5) นำมาเชื่อมต่อต้นไม่ในป่า เนื่องจากเป็นเอดจ์สุดท้าย
2. การหาเส้นทางที่สั้นที่สุด(Shortest path)
2.1 เริ่มต้นให้เซต S มีเพียงโหนดเดียว คือโหนดที่เป็นจุดเริ่มต้น
2.2 คำนวณหาระยะทางจาก โหนดที่เป็นจุดเริ่มต้น ไปยังโหนดทุกโหนดในกราฟ โดยยอมให้ใช้โหนด
ในเซต S เป็นทางผ่านได้ ถ้ามีมากกว่า 1 ทาง ให้เลือกทางที่สั้นที่สุด นำไปใส่ใน D ของแต่ละโหนด
2.3 เลือกโหนด W ที่ห่างจากโหนดเริ่มต้นน้อยที่สุดไปไว้ใน S การคำนวณหาระยะทางสั้นที่สุด จาก โหนดต้นทางคือโหนด 1 ไปยังโหนดใด ๆ
------------------------------------------------------------------------
สรุปเรื่อง sorting

วิธีการเรียงลำดับ
1. การเรียงลำดับแบบภายใน การเรียงลำดับทั้งหมดต้องอยู่ในหน่วยความจำหลัก
2. การเรียงลำดับแบบภายนอก เป็นการเรียงลำดับขอ้มูลจะเก็บไว้ในหน่วยความจำสำรอง

การเรียงลำดับแบบเลือก ทำการเลือกข้อมูลมาเก็บไว้ในตำแหน่ง ข้อมูลนั้นควรจะอยู่ที่ละตัว โดยการค้นหาข้อมูลั้นจะเรียงจากน้อยไปหามาก

การเรียงลำดับแบบฟอง เป็นการเปรียบเทียบข้อมูลที่ในตำแหน่งอยู่ติดกัน ถ้าข้อมูลทั้งสองไม่อยู่ในตำแหน่งที่ถูกต้องให้สลับตำแหน่ง ข้อมูลมีการเรียงลำดับจากน้อยไปมาก

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

การเรียงลำดับแบบแทรก เป็นการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงกันอยู่แล้ว ทำให้เซตใหม่ได้มีสมาชิกทุกตัวเรียงลำดับด้วย

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

การเรียงลำดับแบบฐาน เป็นการพิจารณาข้อมูลทีละหลัก โดยเริ่มจากข้อมูลที่มีค่าน้อยที่สุดก่อน นั้นคือข้อมูลที่เป็นจำนวนเต็มในหลักหน่วยก่อน และจัดเรียงเข้ามาทีละตัวแล้วนำไปเก็บไว้เป็นกลุ่ม ในรอบต่อไปนำข้อมูลทั้งหมดมาจัดเรียงในหลักหน่วยก่อนแล้วจึงไปทำหลักสิบตอไป
-------------------------------------------------------------------
สรุป searching

การค้นหาข้อมูล คือ การใช้วิธีการค้นหาโครงสร้างข้อมูล เพื่อดุซ่าข้อมูลตัวที่ต้องการถูฏเก็บอยู่ในโครงสร้างแล้วหรือยัง

การค้นหา สามารถแบ่งได้ 2 ประเภท ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับกสนเรียงลำดับ
การค้นหาข้อมูลภายนอก(INTERNAL SEARCHING)
การค้นหาข้อมูลภายใน(EXTERNAL SEARCHING)

1. การค้นหาเชิงเส้นหรือการค้นหาแบบลำดับ(LINEAR)เป็นวิธีที่ใช้กับข้อมูลที่ไม่เรียงลำดับ
2. การค้นหาแบบเซนทินัล (SENTINEL) เป็นวิธิที่การค้นหาแบบเดียวกับการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนามาจากอัลกอริทึ่มแบบเชิงเส้น
3. การค้นหาแบบไบนารี(BINARY SEARCH) ใช้กับข้อมูลที่จัดเรียงแล้วเท่านั้น หลักการต้องมีการแบ่งข้อมูลออกเป็น 2 ส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา

DTS 10-15/09/09

เรื่องตารางแฮช
คือการเข้าถึงข้อมูลโดยตรง กำหนดให้ k เป็นคีย์ถูกจัดเก็บอยู่ใน ช่อง k ด้วยการทำแฮช ด้วยพื้นฐานการจัดเก็บในช่องที่h(k) โดยฟังก์ชั่น h เพื่อคำนวณหาช่องของคีย์โดยการจับคู่กับดอกภพสัมพันธ์ U ในตาราง T

การชนกับของข้อมูล
การแทรกในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ถูกสร้างจากฟังก์ชั้น อย่างไรก็ตามการเกิดการชนกันยังคงมีอย่างน้อย 1 ครั้ง

วิธีการสร้างฟังก์ชั่นแฮช
1. วิธีการหาร คือ การจับคู่คีย์ K ในช่องของ m โดยนำเศษที่เหลือของ k จากการหารด้วย m ด้วยฟังก์ชั่นคือ h(k) = mod m.
2. วิธีการคูณ ปรกอบด้วย 2 ขั้นตอน
ขั้นที่ 1 คูณด้วย k ด้วยค่าคงที่ h(k) = *m(kA mod 1)
เมื่อ " kA mod 1" หมายถึง เศษส่วนของ kA, นั้นคือ , kA-*kA
ประโยชน์ของวิธีนี้คือ ค่าของm จะไม่วิกฤติ และสามารถดำเนินการในครื่องคอมพิวเตอร์ส่วนมากได้
3. วิธีทั่วไป คือ Open Addressing ฟังก์ชั่นแฮช คือ h:V{0,1,.....m-1}-->{0,1,...,m-1}

เทคนิคลำดับของการตรวจสอบ
1. การตรวจสอบเชิงเสน
2. การตรวจสอบด้วยสมการกำลังสอง
3. การสร้างฟังก์ชั่นแฮชแบบสองท่า

DTS 09-15/09/09

เรื่อง sorting
คือการเรียงลำดับ เป็นการจัดให้เป็นระเบียบอย่างมีแบบแผน ซึ่งจะสามารถหาข้อมูลได้ง่ายขึ้น ราดเร็วขึ้น เช่น การค้นหาหมายเลขในสมุดโทรศัพท์ ซึ่งมีการเรียงลำดับตามชื่อ-นามสกุลของเจ้าของโทรศัพท์ จะสามารถหาหมายเลขโทรศัพท์ได้เร็วขึ้น

วิธีการเรียงลำดับ
1. การเรียงลำดับแบบภายใน การเรียงลำดับทั้งหมดต้องอยู่ในหน่วยความจำหลัก
2. การเรียงลำดับแบบภายนอก เป็นการเรียงลำดับขอ้มูลจะเก็บไว้ในหน่วยความจำสำรอง

การเรียงลำดับแบบเลือก ทำการเลือกข้อมูลมาเก็บไว้ในตำแหน่ง ข้อมูลนั้นควรจะอยู่ที่ละตัว โดยการค้นหาข้อมูลั้นจะเรียงจากน้อยไปหามาก

การเรียงลำดับแบบฟอง เป็นการเปรียบเทียบข้อมูลที่ในตำแหน่งอยู่ติดกัน ถ้าข้อมูลทั้งสองไม่อยู่ในตำแหน่งที่ถูกต้องให้สลับตำแหน่ง ข้อมูลมีการเรียงลำดับจากน้อยไปมาก

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

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

การเรียงลำดับแบบฐาน เป็นการพิจารณาข้อมูลทีละหลัก โดยเริ่มจากข้อมูลที่มีค่าน้อยที่สุดก่อน นั้นคือข้อมูลที่เป็นจำนวนเต็มในหลักหน่วยก่อน และจัดเรียงเข้ามาทีละตัวแล้วนำไปเก็บไว้เป็นกลุ่ม ในรอบต่อไปนำข้อมูลทั้งหมดมาจัดเรียงในหลักหน่วยก่อนแล้วจึงไปทำหลักสิบตอไป

DTS 08-08/09/09

เรื่องกราฟ

กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด

นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Graphs)และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง(Directed Graphs)
บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้

โดยทั่ว ๆ ไปการเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes) หรือวงกลม (circles)ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้นหรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนดถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้องมีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย

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

สำหรับเทคนิคการท่องไป ในกราฟมี 2 แบบดังนี้

1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ

2. การท่องแบบลึก (Depth First Traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม
แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่ง
สามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด

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

1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด(Minimum Spanning Trees :MST)
1. เรียงลำดับเอดจ์ ตามน้ำหนัก
2. สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนด และไม่มีเส้นเชื่อม
3. เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลย ถ้ามีน้ำหนักซ้ำกันหลายค่าให้สุ่มมา 1 เส้น
4. พิจารณาเอดจ์ที่จะเลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบ ให้ตัดทิ้งนอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5. ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่หมดให้ไปทำข้อ 3
6. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา
7. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (5,7) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
8. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (1,4) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
9. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(3,5) นำมาเชื่อมต่อต้นไม่ในป่า เนื่องจากเป็นเอดจ์สุดท้าย

2. การหาเส้นทางที่สั้นที่สุด(Shortest path)
2.1 เริ่มต้นให้เซต S มีเพียงโหนดเดียว คือโหนดที่เป็นจุดเริ่มต้น
2.2 คำนวณหาระยะทางจาก โหนดที่เป็นจุดเริ่มต้น ไปยังโหนดทุกโหนดในกราฟ โดยยอมให้ใช้โหนด ในเซต S เป็นทางผ่านได้ ถ้ามีมากกว่า 1 ทาง ให้เลือกทางที่สั้นที่สุด นำไปใส่ใน D ของแต่ละโหนด
2.3 เลือกโหนด W ที่ห่างจากโหนดเริ่มต้นน้อยที่สุดไปไว้ใน S

การคำนวณหาระยะทางสั้นที่สุด จากโหนดต้นทางคือโหนด 1
ไปยังโหนดใด ๆ มีวิธีคำนวณดังนี้
1) เริ่มต้นโหนดที่เป็นจุดเริ่มต้น คือ โหนด 1 ไปไว้ที่เซต Sจากนั้นนำค่าน้ำหนักบนเอดจ์ (1,2) เอดจ์ (1,4) เอดจ์ (1,5)และ เอดจ์ (1,6) ไปเขียนในตารางสำหรับ โหนด 3 ไม่ได้ เชื่อมต่อกับโหนดที่ 1 ดังนั้นจึงใช้ค่าอินฟินีตี้ (Infinity) แทน แสดงในตารางที่ปรากฏในบรรทัดIter= Initial

2) เลือก W ที่มีระยะทางสั้นที่สุด คือ โหนด 2 ไปไว้ที่เซต Sคำนวณ ระยะทางใหม่ ระยะทางสั้นที่สุด จากโหนด 1 ไปโหนดอื่น ๆ เท่าเดิม ยกเว้นโหนด 3 ซึ่งขณะนี้มีวิถีกับโหนด 1 ดังนี้ (1,2,3) ระยะทางที่ได้มาจากน้ำหนักบนเอจน์เป็น (1,2) และ เอดจ์ (2,3)รวมกันคือ 70 จึงเขียนค่า 70 แทนค่าอินฟินีตีเดิม

3) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 5 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่าถึงแม้จะมี
โหนด 5 อยู่ในวิถีเส้นทางใหม่ แต่ระยะทางจากวิถีเดิมสั้นกว่า จึงคงค่าเดิมไว้ดังแสดงในตาราง

4) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 4 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่า มีวิถีจากโหนด 1 ไปโหนด3 รวม 2 วิถีดังนี้
วิถีที่ 1 คือ (1,2 และ3) มีค่าน้ำหนัก = 30+40 =70
วิถีที่ 2 คือ (1,4 และ3) มีค่าน้ำหนัก = 50+10 =60
เลือกน้ำหนักจากวิถีที่สั้นที่สุด คือ 60 ไปเขียนแทนค่าเดิม

5) เลือก W ที่มีระยะทางสั้นที่สุดคือโหนด 3 ไปไว้ที่เซต Sคำนวณหาระยะทางใหม่ปรากฏว่า มีวิถีจากโหนด 1 ไปโหนด3

DTS 07 25/08/09

เรื่อง TREE
ทรีมีความสัมพันธ์ระหว่าง โหนดจะมีความลดหลั่นกันเป็นลำดับชั้น ได้มีการนำรูปแบบทรีไปประยุกต์ในการใช้งานต่างๆ หรือ การมีสายบังคับบัญชา โหนดแต่ละโหนดจะต้องประกอบไปด้วยโหนดแม่

โหนดที่ต่ำกว่าโหนดแม่จะเรียกว่าโหนดลูก

โหนดที่สูงสุดและไม่มีโหนดแม่จะเรียกว่า โหนดราก

โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง

โหนดที่ไม่มีโหนดลูฏจะเรียกว่า โหนดใบ

เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง

นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด ในโครงสร้าง
การเขียนรูปแบบทรีเขียนได้ 4 แบบ
1) แบบที่มีรากอยู่ด้านบน
2) แบบที่มีรากอยู่ด้านล่าง
3) แบบที่มีรากอยู่ด้านซ้าย
4) แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟหรือการเวียนเกิด คือ ทรีที่ประกอบไปด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ จะเรียกว่า Null Tree ถ้ามีโหนดหนึ่งเป็นโหนดราหอีกโหนดจะเป็นทรีย่อย

DTS 06-04/08/09

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

การดำเนินงานพื้นฐานของสแตก
การทำงานต่าง ๆ ของสแตกจะกระทำที่ปลาย
ข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วย
การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวน
การที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้

2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตกpush (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก

3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก

การดำเนินการเกี่ยวกับสแตก ได้แก่
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เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก

DTS 05-28/07/09

โครงสร้างข้อมูลแบบลิงค์ลิสต์ โครงสร้างข้อมูลแบบลิงค์ลิสต์
จะแบ่งเป็น 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 หน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผล
ข้อมูลนำเข้าลิสต์
ผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต์ ,คำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Node หน้าที่ หาตำแหน่งข้อมูลจากลิส
ต์ ข้อมูลนำเข้าลิสต์
ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์
7. ฟังก์ชั่น EmptyList
หน้าที่ ทดสอบว่าลิสต์ว่าง
ข้อมูลนำเข้าลิสต์
ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่าง
เป็นเท็จ ถ้าลิสต์ไม่ว่าง
8. ฟังก์ชั่น FullList
หน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่
ข้อมูลนำเข้าลิสต์
ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม
เป็นเท็จ ถ้าสามารถมีโหนดอื่น
9. ฟังก์ชั่น list count
หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์
ข้อมูลนำเข้าลิสต์
ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน destroy list
หน้าที่ ทำลายลิสต์
ข้อมูลนำเข้า ลิสต์
ผลลัพธ์ ไม่มีลิสต์

การบ้าน
#include <iostream.h>
int main()
{
int index;
for(index=0;index<5;index++)
{
if(index<4)
{
if(index==3)
cout << "Index is 3" << "\n";
else
cout << "Index is less than 3" << "\n";
}
else
cout << "Index is greater than 3" << "\n"; }
return 0;
}

DTS 04 14/07/09

โครงร้างข้อมูลแบบเซต
ในโครงสร้างข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน การดำเนินการจะมีแบบ A^B ตัวที่ซ้ำกัน , AUB รวมกัน(กระจัดกระจาย) , A-B หรือ B-A ตัวที่อยู่ในA แต่ไม่อยู่ในB และโครงสร้างของสตริง จะเป็นข้อความคล้ายๆกับ notepad เป็นโปรแกรมประเภทประมวลผลคำ เช่น ภาษา HTML หรือ การเปลี่ยนแท็ปของ Hi5ฯลฯ

โครงสร้างข้อมูลแบบสตริง
อะเรย์ของสตริงที่ยาวไม่เท่ากัน ทำได้เฉพาะเมื่อมีการกำหนดค่าเริ่มต้นเท่านั้น เช่น ฟังก์ชั่น puts()ใช้ในการเพิ่มสตริงออกทางจอภาพ โดยการผ่านค่าแอดเดรสของสตริงไปให้เท่านั้น อะเรย์ของสตริงที่ยาวเท่ากัน จะถือว่าเป็นอะเรย์ที่แท้จริง และสามารถกำหนดได้ทั้งเมื่อมีการให้ค่าเริ่มต้น เมื่อกำหนดเป็นตัวแปร โดยดำเนินการตามแบบกำหนดเป็นอะเรย์ 2 มิติ

การกำหนดตัวแปรจะมีความแตกต่างจากการกำหนดตัวแปรแบบความยาวไม่เท่ากัน คือในแบบความยาวไม่เท่ากันตัวท้ายของสตริงจะต้องเติม null charactor(\0)เพียงตัวเดียวแต่ใบแบบความยาวเท่ากัน จะเติม null charactor(\0) ให้ครบทุกช่อง

DTS 03 30/06/52

อาร์เรย์ เป็นแบบหนึ่งของโครงสร้างที่เรียกว่า Linear List ซึ่งมีจำนวนรายการ ( Element) จำกัด และข้อมูลที่เก็บอยู่ในอาร์เรย์แต่ละช่องจะต้องเป็นข้อมูลชนิดเดียวกัน อยู่ภายใต้ตัวแปรชื่อเดียวกัน โดยขนาดของแต่ละช่องต้องเท่ากันหมด การอ้างถึงข้อมูลในแต่ละช่องของของอาร์เรย์ ต้องอาศัยตัวห้อย Subscript เช่น กำหนดให้ Array A มีขนาด 100 รายการ A[5] จะหมายถึง ค่าของอาร์เรย์ตำแหน่งที่ 5 ในอาร์เรย์นั้น ซึ่ง Subscript ก็คือ เลข 5 จำนวน Subscript ที่ต้องการใช้เวลาเรียกใช้ค่าใน Array เรียกว่า มิติ ไดเมนชั่น ( Dimention) ของ Array นั้น

การสร้าง Array ขึ้นมาใช้งานนั้น ต้องคำนึงถึง
1. ชื่อของ Array
2. ขนาดของ Array แต่ละช่อง และมิติของ Array
3. ค่าสูงสุด ( Upper Bound) และค่าต่ำสุด (Lower Bound) ในแต่ละมิติ

ARRAY 1 มิติ คือ Array ที่มีลักษณะเป็นตารางแถวเดียว Array 1 มิติ จะมีลักษณะโดยทั่วไปดังนี้
A(L:U)
A: ชื่อของArray
L: ค่าต่ำสุด (Lower Bound )
U: ค่าสูงสุด (Upper Bound )

หมายเหตุ ในภาษาซี ช่องแรกของอาร์เรย์จะเริ่มจาก 0


ค่า subscript ที่ใช้อ้างอิงถึงสมาชิก จะต้องมีค่ามากกว่า หรือเท่ากับขอบเขตล่าง และน้อยกว่าหรือเท่ากับขอบเขตบน
lower bound ≤ subscript ≤ upper bound
ขนาดของ index แต่ละตัว ของ Array หาได้จาก
ขนาดของ subscript = upper bound – lower bound + 1

อาร์เรย์ 2 มิติ
อาร์เรย์ 2 มิติ คือ อาร์เรย์ที่มีลักษณะที่เป็นตารางที่มี 2 ด้าน คือ ทางด้านแนวนอน ( ROW) และแนวตั้ง ( COLUMN) มีจำนวนช่องเท่ากับ จำนวนช่องทางด้านแนวนอน ( ROW) คูณกับจำนวนช่องทางด้านแนวตั้ง ( COLUMN) การอ้างถึง Array 2 มิติ ต้องใช้ Subscript 2 ตัว คือ ROW และ COLUMN การกำหนดอาร์เรย์ 2 มิติทำได้โดย

สิ่งที่ฉันปรารถนา

นางสาว กนกวรรณ เหลืองเลิศวัฒน

VDO แนะนำตัว

RECORD DTS 02 23/06/2552

การเรียนครั้งนี้ได้รู้ถึงโครงสร้างของข้อมูลทั้งกายภาพและทางตรรกะ และแต่ในโครงสร้างแต่ละตัวนั้นมีความสำคัญในการใช้ และมีการแก้ปัญหาอย่างมีระบบ มีลำดับขั้นตอนที่แสดงถึงผลลัพธ์ โดยต้องกระชับและรัดกุม
ประเภทตามลักษณะข้อมูล
1. ข้อมูลเบื้องต้น Primitive Data Types
ได้แก่ จำนวนเต็ม จำนวนจริง และตัวอักขระ
2. ข้อมูลโครงสร้าง Structured Data Types
ได้แ่ก่ แถวลำดับ ระเบียนข้อมูล และแฟ้มข้อมูล เป็นต้น
2. โครงสร้างข้อมูลทางตรรกะ
-เป็นโครงสร้างข้อมูลที่เกิดจากจินตนาการของผู้ใช้เพื่อใช้ในการแก้ปัญหาในโปรแกรมที่สร้างขึ้น

แบ่งเป็น 2 ประเภท
1. โครงสร้างข้อมูลเชิงเส้น Linear Data Structures
ความสัมพันธ์ของข้อมูลจะเรียงต่อเนื่องกัน เช่น ลิสต์ สแตก คิว สตริง
2. โครงสร้างข้อมูลทางตรรกะ Non-Linear Data Structures
ข้อมูลแต่ละตัวสามารถมีความสัมพันธ์กับข้อมูลอื่นได้หลายตัว
ได้แก่ ทรี และกราฟ

การบ้าน

#include <stdio.h>
#include <string.h>

void main(){

struct addr{

char name[30];

char surname[30];

char soi[20];

char street[40];

char city[20];

char language[20];

char bank[10];

long int post;
};
struct addr kanokwan;

strcpy(kanokwan.name,"Kanokwan");

strcpy(kanokwan.surname,"Luanglertwatana");

strcpy(kanokwan.street,"Wutthakat");

strcpy(kanokwan.city,"Bangkok");

strcpy(kanokwan.bank,"Kbank");

strcpy(kanokwan.soi,"Chaiwut");

strcpy(kanokwan.language,"Thai");

kanokwan.post=10150;

printf("******profile******\n\n");

printf(" Name:%s\n\n",kanokwan.name);

printf(" Surname:%s\n\n",kanokwan.surname);

printf(" Bank:%s\n\n",kanokwan.bank);

printf(" street : %s\n\n",kanokwan.street);

printf(" city : %s\n\n",kanokwan.city);

printf(" soi : %s\n\n",kanokwan.soi);

printf(" post :%d\n\n",kanokwan.post);

printf(" language :%s\n\n",kanokwan.language);

}

ประวัติ

นางสาวกนกวรรณ เหลืองเลิศวัฒน

ชื่อเล่น จู

รหัสนักศึกษา 50132792062

Miss. Kanokwan Luanglertwatana

หลักสูตร บริหารธุรกิจ(คอมพิวเตอร์ธุรกิจ) คณะวิทยาการจัดการ

มหาวิทยาลัยราชภัฎสวนดุสิต

E-mail : U50132792062@gmail.com

Tel. 0876966608