ลูกแรดเตรียมพร้อมล่าเหยื่อ
สรุป สิ่งที่ได้เรียนรู้จากการเรียนวิชา เตรียมฝึกประสบการณ์วิชาชีพ
ได้เรียนรู้ในการใช่ชีวิต อย่างมีคุณธรรมละจริยธรรม การทำงานอย่างเป็นระบบ การทำงานเป้นกลุ่ม รู้ถึงองค์ประกอบของเงินส่วนบุคคลและการบริหารเงินในความหมายที่ลึกซึ่งยิ่งขึ้น บุคลิกที่ดีเป็นอย่าง ราควรทำตัวอย่างไรให้เหมาะสมกับสถานที่ ที่เราไป เวลาทำงาน หรือ ไปเข้าร่วมสังคม เราจะแต่งตัวหรือ พูดจาอย่างไร ได้รู้ถึงแนวทางแห่งความสำเร็จ ด้วยเรื่องที่ว่า"การศึก,การพยายามมองไกลตัว,เป้นตัวของตัวเอง" รู้ถึงการเปลียนแปลงในเทคโนโลยีในอนาคต ว่าจะมีการเปลียนแปลง ในเรื่องใดและอย่างไร และรู้ถึงความสำคัญของเทคโนโลยีนั้นอีกด้วย ได้รู้เกียบกับ วัฒนาธรรม ในชาติต่างๆ ที่ถ้าเราต้องการที่จะทำธุรกิจๆ กันประเทศต่าง เราต้องปรับตัวตามเขาไปด้วยในปรเทศนั้น อีกด้วย เพือเพิ่มโอกาสประสบความสำเร็จในการประกอบธุรกิจมากสิ่งขึ้น การเรียนวิชาเตรียมฝึกประสบการณ์วิชาชีพนี้ช่วยให้ผมได้รู้อะไรมากมายในเรื่องของการปรับตัวต่างๆ และการทำตัวให้เหมาะสม ในเรื่องต่างๆอีกด้วยครับ
DTS11-15/09/2009
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 ส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
สรุป 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 ส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
DTS10-15/09/2009
เรื่องตารางแฮช
คือการเข้าถึงข้อมูลโดยตรง กำหนดให้ 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. การสร้างฟังก์ชั่นแฮชแบบสองท่า
คือการเข้าถึงข้อมูลโดยตรง กำหนดให้ 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. การสร้างฟังก์ชั่นแฮชแบบสองท่า
DTS09-15/09/2009
เรื่อง sorting
คือการเรียงลำดับ เป็นการจัดให้เป็นระเบียบอย่างมีแบบแผน ซึ่งจะสามารถหาข้อมูลได้ง่ายขึ้น ราดเร็วขึ้น เช่น การค้นหาหมายเลขในสมุดโทรศัพท์ ซึ่งมีการเรียงลำดับตามชื่อ-นามสกุลของเจ้าของโทรศัพท์ จะสามารถหาหมายเลขโทรศัพท์ได้เร็วขึ้น
วิธีการเรียงลำดับ
1. การเรียงลำดับแบบภายใน การเรียงลำดับทั้งหมดต้องอยู่ในหน่วยความจำหลัก
2. การเรียงลำดับแบบภายนอก เป็นการเรียงลำดับขอ้มูลจะเก็บไว้ในหน่วยความจำสำรอง
การเรียงลำดับแบบเลือก ทำการเลือกข้อมูลมาเก็บไว้ในตำแหน่ง ข้อมูลนั้นควรจะอยู่ที่ละตัว โดยการค้นหาข้อมูลั้นจะเรียงจากน้อยไปหามาก
การเรียงลำดับแบบฟอง เป็นการเปรียบเทียบข้อมูลที่ในตำแหน่งอยู่ติดกัน ถ้าข้อมูลทั้งสองไม่อยู่ในตำแหน่งที่ถูกต้องให้สลับตำแหน่ง ข้อมูลมีการเรียงลำดับจากน้อยไปมาก
การเรียงลำดับแบบเร็ว ใช้เวลาน้อย เหมาะกับข้อมูลที่มีจำนวนมากต้องการความรวดเร็วในการทำงาน และกำหนดค่าหนึ่งเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ โดยแบ่งข้อมูลออกเป็นสองส่วน ส่วนแรกอยู่ตอนหน้าของข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่ง
การเรียงลำดับแบบแทรก เป็นการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงกันอยู่แล้ว ทำให้เซตใหม่ได้มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับจะเริ่มจากการเปรียบเทียบในตำแหน่งที่1และ2 หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้าย และต้องจัดข้อมูลที่มีค่าน้อยในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้าเรียงจากมากไปน้อยจะจัดให้ข้อมูลที่มีค่ามากอยูในตำแหน่งก่อน
การเรียงลำดับแบบฐาน เป็นการพิจารณาข้อมูลทีละหลัก โดยเริ่มจากข้อมูลที่มีค่าน้อยที่สุดก่อน นั้นคือข้อมูลที่เป็นจำนวนเต็มในหลักหน่วยก่อน และจัดเรียงเข้ามาทีละตัวแล้วนำไปเก็บไว้เป็นกลุ่ม ในรอบต่อไปนำข้อมูลทั้งหมดมาจัดเรียงในหลักหน่วยก่อนแล้วจึงไปทำหลักสิบตอไป
คือการเรียงลำดับ เป็นการจัดให้เป็นระเบียบอย่างมีแบบแผน ซึ่งจะสามารถหาข้อมูลได้ง่ายขึ้น ราดเร็วขึ้น เช่น การค้นหาหมายเลขในสมุดโทรศัพท์ ซึ่งมีการเรียงลำดับตามชื่อ-นามสกุลของเจ้าของโทรศัพท์ จะสามารถหาหมายเลขโทรศัพท์ได้เร็วขึ้น
วิธีการเรียงลำดับ
1. การเรียงลำดับแบบภายใน การเรียงลำดับทั้งหมดต้องอยู่ในหน่วยความจำหลัก
2. การเรียงลำดับแบบภายนอก เป็นการเรียงลำดับขอ้มูลจะเก็บไว้ในหน่วยความจำสำรอง
การเรียงลำดับแบบเลือก ทำการเลือกข้อมูลมาเก็บไว้ในตำแหน่ง ข้อมูลนั้นควรจะอยู่ที่ละตัว โดยการค้นหาข้อมูลั้นจะเรียงจากน้อยไปหามาก
การเรียงลำดับแบบฟอง เป็นการเปรียบเทียบข้อมูลที่ในตำแหน่งอยู่ติดกัน ถ้าข้อมูลทั้งสองไม่อยู่ในตำแหน่งที่ถูกต้องให้สลับตำแหน่ง ข้อมูลมีการเรียงลำดับจากน้อยไปมาก
การเรียงลำดับแบบเร็ว ใช้เวลาน้อย เหมาะกับข้อมูลที่มีจำนวนมากต้องการความรวดเร็วในการทำงาน และกำหนดค่าหนึ่งเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ โดยแบ่งข้อมูลออกเป็นสองส่วน ส่วนแรกอยู่ตอนหน้าของข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่ง
การเรียงลำดับแบบแทรก เป็นการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงกันอยู่แล้ว ทำให้เซตใหม่ได้มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับจะเริ่มจากการเปรียบเทียบในตำแหน่งที่1และ2 หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้าย และต้องจัดข้อมูลที่มีค่าน้อยในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้าเรียงจากมากไปน้อยจะจัดให้ข้อมูลที่มีค่ามากอยูในตำแหน่งก่อน
การเรียงลำดับแบบฐาน เป็นการพิจารณาข้อมูลทีละหลัก โดยเริ่มจากข้อมูลที่มีค่าน้อยที่สุดก่อน นั้นคือข้อมูลที่เป็นจำนวนเต็มในหลักหน่วยก่อน และจัดเรียงเข้ามาทีละตัวแล้วนำไปเก็บไว้เป็นกลุ่ม ในรอบต่อไปนำข้อมูลทั้งหมดมาจัดเรียงในหลักหน่วยก่อนแล้วจึงไปทำหลักสิบตอไป
DTS08-08/09/2009
เรื่องกราฟ
กราฟ (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
กราฟ (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
DTS07-25/08/2009
เรื่อง TREE
ทรีมีความสัมพันธ์ระหว่าง โหนดจะมีความลดหลั่นกันเป็นลำดับชั้น ได้มีการนำรูปแบบทรีไปประยุกต์ในการใช้งานต่างๆ หรือ การมีสายบังคับบัญชา โหนดแต่ละโหนดจะต้องประกอบไปด้วยโหนดแม่
โหนดที่ต่ำกว่าโหนดแม่จะเรียกว่าโหนดลูก
โหนดที่สูงสุดและไม่มีโหนดแม่จะเรียกว่า โหนดราก
โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง
โหนดที่ไม่มีโหนดลูฏจะเรียกว่า โหนดใบ
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด ในโครงสร้าง
การเขียนรูปแบบทรีเขียนได้ 4 แบบ
1) แบบที่มีรากอยู่ด้านบน
2) แบบที่มีรากอยู่ด้านล่าง
3) แบบที่มีรากอยู่ด้านซ้าย
4) แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟหรือการเวียนเกิด คือ ทรีที่ประกอบไปด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ จะเรียกว่า Null Tree ถ้ามีโหนดหนึ่งเป็นโหนดราหอีกโหนดจะเป็นทรีย่อย
ทรีมีความสัมพันธ์ระหว่าง โหนดจะมีความลดหลั่นกันเป็นลำดับชั้น ได้มีการนำรูปแบบทรีไปประยุกต์ในการใช้งานต่างๆ หรือ การมีสายบังคับบัญชา โหนดแต่ละโหนดจะต้องประกอบไปด้วยโหนดแม่
โหนดที่ต่ำกว่าโหนดแม่จะเรียกว่าโหนดลูก
โหนดที่สูงสุดและไม่มีโหนดแม่จะเรียกว่า โหนดราก
โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง
โหนดที่ไม่มีโหนดลูฏจะเรียกว่า โหนดใบ
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด ในโครงสร้าง
การเขียนรูปแบบทรีเขียนได้ 4 แบบ
1) แบบที่มีรากอยู่ด้านบน
2) แบบที่มีรากอยู่ด้านล่าง
3) แบบที่มีรากอยู่ด้านซ้าย
4) แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟหรือการเวียนเกิด คือ ทรีที่ประกอบไปด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ จะเรียกว่า Null Tree ถ้ามีโหนดหนึ่งเป็นโหนดราหอีกโหนดจะเป็นทรีย่อย
DTS06-04/08/2009
สรุปบทเรียน
สแตก(stack)
ความรู้พื้นฐานเกี่ยวกับสแตก
โครงสร้างข้อมูลที่สำคัญและมีลักษณะเรียบง่ายซึ่งใช้แถวลำดับเป็นโครงสร้างสำหรับเก็บข้อมูลพื้นฐานได้แก่สแตก เพราะภาษาคอมพิวเตอร์ส่วนมากกำหนดชนิดแถวลำดับไว้ล่วงหน้าและการทำงานของแถวลำดับสะดวกและเรียบง่าย
สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแตกหรือ หรือเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก
ตัวอย่างการทำงานแบบโครงสร้างข้อมูลแบบสแตกที่สามารถเห็นได้ในชีวิตประจำวันทั่วไปได้แก่ การวางจานซ้อนกันต้องวางจานลงบนกล่องเก็บจานจากล่างสุดที่ละใบ และสามารถใส่ได้จนเต็มกล่อง และเมื่อมีการวางจานจนเต็มกล่องแล้วจะไม่สามารถวางจานซ้อนได้อีกเพราะกล่องมีสภาพเต็ม แต่เมื่อเราจะหยิบจานไปใช้ เราต้องหยิบใบบนสุด ซึ่งเป็นจานที่ถูกวางเก็บเป็นอันดับสุดท้ายออกได้เป็นใบแรก และสามารถหยิบออกที่ละใบจากบนสุดเสมอ ส่วนจานที่ถูกวางเก็บเป็นใบแรก จะนำไปใช้ได้ก็ต่อเมื่อนำจานที่วางทับมันอยู่ออกไปใช้เสียก่อน และจะหยิบออกไปใช้เป็นใบสุดท้ายดังรูปข้างล่าง
ส่วนประกอบของสแตก
การนำสแตกไปใช้งานนั้นไม่ว่าจะเป็นโครงสร้างสแตกแบบแถวลำดับ(array)หรือ แบบลิงค์ลิสต์ (link list) เราจะมีตัวแปรตัวหนึ่งที่ใช้เป็นตัวชี้สแตก(stack pointer ) เพื่อเป็นตัวชี้ข้อมูลที่อยู่บนสุดของสแตก ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย ดังนั้นโครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือ
ตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )
สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น นอกจากนี้ยังต้องมีตัวกำหนดค่าสูงสุดของสแตก ( Max Stack ) ซึ่งจะเป็นตัวบอกว่าสแตกนี้สามารถเก็บ จำนวนข้อมูลได้มากที่สุดเท่าไร เปรียบเทียบส่วนประกอบของสแตกได้กับการให้ สแตกเป็นกระป๋องเก็บลูกเทนนิส ส่วน Stack Elements หรือสมาชิกของสแตก คือ ลูกเทนนิส ส่วนตัวชี้สแตกเป็นตัวบอกว่าขณะนี้มีลูกเทนนิสอยู่ในกระป๋องกี่ลูก ส่วน Max Stack เป็นตัวบอกว่า กระป๋องนี้เก็บลูกเทนนิสได้มากที่สุดเท่าไร
การจัดการ กับสแตก
ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (pushing stack) และ การดึงข้อมูลออกจากสแตก (poping stack)
1. การเพิ่มข้อมูลในสแตก (pushing stack) เป็นการนำข้อมูลเข้าสู่สแตก ซึ่งการกระทำเช่นนี้ เราเรียกว่า push ซึ่งโดยปกติก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ในสแตกก่อน ว่ามีที่เหลือว่างให้เก็บข้อมูลได้อีกหรือไม่
ในการเพิ่มข้อมูลในสแตก (pushing) สามารถทำได้โดยให้ทับบนข้อมูลสุดท้ายในสแตก และจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าสแตกจะเต็ม ความหมายของคำว่า สแตกเต็ม คือท๊อปของ สแตกชี้ที่บนสุดของสแตก เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่ หมายถึงสามารถบรรจุสมาชิกในสแตกได้ N ตัว หากเป็นสแตกว่าง ค่าของท๊อปจะเป็นศูนย์ แต่หากสแตกเต็ม ค่าท๊อปจะเป็น N นั้นแสดงว่าเมื่อท๊อปชี้ที่ N หรือค่าของท๊อป เท่ากับ N ก็จะไม่สามารถ push ข้อมูลลง สแตกได้
นิยาม Push (S,x)
ถ้าให้ S เป็นสแตก และ x เป็นข้อมูลที่ต้องการใส่ในสแตก หรือดึงออกสแตก กระบวนการ push (S, x ) หมายถึง การ push ข้อมูล x ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า ท๊อปมีค่าเป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า ของท๊อปจะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push
2. การดึงข้อมูลจากสแตก (Popping Stack) หมายถึงการเอาข้อมูลที่อยู่บนสุดในสแตก หรือที่ชี้ด้วย ท๊อปออกจากสแตก เรียกว่าการ pop ในการpop นั้นเราจะสามารถ pop ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่
นิยาม pop(S)
ถ้าให้ S เป็นสแตก การ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้น คำสั่ง x = pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกออกมา และใส่ค่าไว้ที่ x หรือการเซตค่า x ให้เท่ากับข้อมูลที่ดึงจากสแตก
ปัญหาที่เกิดขึ้นกับสแตก คือขอผิดพลาดที่เกิดขึ้นซึ่งมีผลมาจากการจัดการสแตกมีดังนี้
สแตกเต็ม (Full Stack)
สแตกว่าง (Empty Stack)
สแตกเต็ม (Full Stack)
การ push สแตกทุกครั้งจะมีการตรวจสอบที่ว่างในสแตกว่ามีที่ว่างเหลือหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ push สแตกได้ ในกรณีเช่นนี้เราเรียกว่าเกิดสถานะล้นเต็ม (Stack Overflow) โดย การตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของ สแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูล อีก
2. สแตกว่าง (Empty Stack)
นิยาม empty(S) ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่างหรือสแตกเต็ม
การ pop สแตกทุกครั้งจะมีการตรวจสอบข้อมูลในสแตกว่ามีข้อมูลในสแตกหรือไม่ ถ้าไม่มีข้อมูลในสแตก เหลืออยู่ เราก็ไม่สามารถทำการ pop สแตกได้ ในกรณีเช่นนี้เรียกว่าเกิดสถานะ สแตกจม (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่า สแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้
สแตก(stack)
ความรู้พื้นฐานเกี่ยวกับสแตก
โครงสร้างข้อมูลที่สำคัญและมีลักษณะเรียบง่ายซึ่งใช้แถวลำดับเป็นโครงสร้างสำหรับเก็บข้อมูลพื้นฐานได้แก่สแตก เพราะภาษาคอมพิวเตอร์ส่วนมากกำหนดชนิดแถวลำดับไว้ล่วงหน้าและการทำงานของแถวลำดับสะดวกและเรียบง่าย
สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแตกหรือ หรือเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก
ตัวอย่างการทำงานแบบโครงสร้างข้อมูลแบบสแตกที่สามารถเห็นได้ในชีวิตประจำวันทั่วไปได้แก่ การวางจานซ้อนกันต้องวางจานลงบนกล่องเก็บจานจากล่างสุดที่ละใบ และสามารถใส่ได้จนเต็มกล่อง และเมื่อมีการวางจานจนเต็มกล่องแล้วจะไม่สามารถวางจานซ้อนได้อีกเพราะกล่องมีสภาพเต็ม แต่เมื่อเราจะหยิบจานไปใช้ เราต้องหยิบใบบนสุด ซึ่งเป็นจานที่ถูกวางเก็บเป็นอันดับสุดท้ายออกได้เป็นใบแรก และสามารถหยิบออกที่ละใบจากบนสุดเสมอ ส่วนจานที่ถูกวางเก็บเป็นใบแรก จะนำไปใช้ได้ก็ต่อเมื่อนำจานที่วางทับมันอยู่ออกไปใช้เสียก่อน และจะหยิบออกไปใช้เป็นใบสุดท้ายดังรูปข้างล่าง
ส่วนประกอบของสแตก
การนำสแตกไปใช้งานนั้นไม่ว่าจะเป็นโครงสร้างสแตกแบบแถวลำดับ(array)หรือ แบบลิงค์ลิสต์ (link list) เราจะมีตัวแปรตัวหนึ่งที่ใช้เป็นตัวชี้สแตก(stack pointer ) เพื่อเป็นตัวชี้ข้อมูลที่อยู่บนสุดของสแตก ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย ดังนั้นโครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือ
ตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )
สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น นอกจากนี้ยังต้องมีตัวกำหนดค่าสูงสุดของสแตก ( Max Stack ) ซึ่งจะเป็นตัวบอกว่าสแตกนี้สามารถเก็บ จำนวนข้อมูลได้มากที่สุดเท่าไร เปรียบเทียบส่วนประกอบของสแตกได้กับการให้ สแตกเป็นกระป๋องเก็บลูกเทนนิส ส่วน Stack Elements หรือสมาชิกของสแตก คือ ลูกเทนนิส ส่วนตัวชี้สแตกเป็นตัวบอกว่าขณะนี้มีลูกเทนนิสอยู่ในกระป๋องกี่ลูก ส่วน Max Stack เป็นตัวบอกว่า กระป๋องนี้เก็บลูกเทนนิสได้มากที่สุดเท่าไร
การจัดการ กับสแตก
ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (pushing stack) และ การดึงข้อมูลออกจากสแตก (poping stack)
1. การเพิ่มข้อมูลในสแตก (pushing stack) เป็นการนำข้อมูลเข้าสู่สแตก ซึ่งการกระทำเช่นนี้ เราเรียกว่า push ซึ่งโดยปกติก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ในสแตกก่อน ว่ามีที่เหลือว่างให้เก็บข้อมูลได้อีกหรือไม่
ในการเพิ่มข้อมูลในสแตก (pushing) สามารถทำได้โดยให้ทับบนข้อมูลสุดท้ายในสแตก และจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าสแตกจะเต็ม ความหมายของคำว่า สแตกเต็ม คือท๊อปของ สแตกชี้ที่บนสุดของสแตก เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่ หมายถึงสามารถบรรจุสมาชิกในสแตกได้ N ตัว หากเป็นสแตกว่าง ค่าของท๊อปจะเป็นศูนย์ แต่หากสแตกเต็ม ค่าท๊อปจะเป็น N นั้นแสดงว่าเมื่อท๊อปชี้ที่ N หรือค่าของท๊อป เท่ากับ N ก็จะไม่สามารถ push ข้อมูลลง สแตกได้
นิยาม Push (S,x)
ถ้าให้ S เป็นสแตก และ x เป็นข้อมูลที่ต้องการใส่ในสแตก หรือดึงออกสแตก กระบวนการ push (S, x ) หมายถึง การ push ข้อมูล x ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า ท๊อปมีค่าเป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า ของท๊อปจะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push
2. การดึงข้อมูลจากสแตก (Popping Stack) หมายถึงการเอาข้อมูลที่อยู่บนสุดในสแตก หรือที่ชี้ด้วย ท๊อปออกจากสแตก เรียกว่าการ pop ในการpop นั้นเราจะสามารถ pop ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่
นิยาม pop(S)
ถ้าให้ S เป็นสแตก การ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้น คำสั่ง x = pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกออกมา และใส่ค่าไว้ที่ x หรือการเซตค่า x ให้เท่ากับข้อมูลที่ดึงจากสแตก
ปัญหาที่เกิดขึ้นกับสแตก คือขอผิดพลาดที่เกิดขึ้นซึ่งมีผลมาจากการจัดการสแตกมีดังนี้
สแตกเต็ม (Full Stack)
สแตกว่าง (Empty Stack)
สแตกเต็ม (Full Stack)
การ push สแตกทุกครั้งจะมีการตรวจสอบที่ว่างในสแตกว่ามีที่ว่างเหลือหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ push สแตกได้ ในกรณีเช่นนี้เราเรียกว่าเกิดสถานะล้นเต็ม (Stack Overflow) โดย การตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของ สแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูล อีก
2. สแตกว่าง (Empty Stack)
นิยาม empty(S) ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่างหรือสแตกเต็ม
การ pop สแตกทุกครั้งจะมีการตรวจสอบข้อมูลในสแตกว่ามีข้อมูลในสแตกหรือไม่ ถ้าไม่มีข้อมูลในสแตก เหลืออยู่ เราก็ไม่สามารถทำการ pop สแตกได้ ในกรณีเช่นนี้เรียกว่าเกิดสถานะ สแตกจม (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่า สแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้
DTS05-28/07/2009
เรื่อง Linked List
Linked 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 ถัดไปให้ถูกต้องด้วย
Linked 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 ถัดไปให้ถูกต้องด้วย
DTS04-21/07/2009
เรื่อง Set and String
โครงสร้างข้อมูลแบบเซ็ต
เป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มี ความสัมพันธ์กัน ในภาษาซี จะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้
ตัวดำเนินการของเซ็ต (Set operators) ประกอบด้วย
- set intersection
- set union
- set difference เป็นต้น
สมมติว่า ต้องการจัดตารางเรียน 4 วิชา ได้แก่ Math, English,Physics และ Chemistryให้กับผู้ลงทะเบียนเรียน
วิธีการแก้ปัญหาเบื้องต้น
- จะต้องกำหนดเซ็ตของผู้เรียนที่ลงทะเบียนเรียนในแต่ละวิชา
- นำเซ็ตดังกล่าวที่ได้มาทำการ intersection กัน หากมีเซ็ตใดที่ทำการ intersect กันแล้วมีข้อมูลสมาชิกในเซ็ตที่ซ้ำกันอยู่ จะไม่สามารถจัดให้วิชาดังกล่าวอยู่ในวันเวลาเดียวกันได้
โครงสร้างข้อมูลแบบสตริง
สตริง (String) หรือ สตริงของอักขระ (CharacterString) เป็นข้อมูลที่ประกอบไปด้วยตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง
การประยุกต์ใช้คอมพิวเตอร์ที่เกี่ยวกับข้อมูลที่เป็นสตริงมีการนำไปใช้สร้างโปรแกรมประเภทบรรณาธิการข้อความ(text editor) หรือโปรแกรมประเภทประมวลผลคำ (word processing) ซึ่งมีการทำงานที่อำนวยความสะดวกหลายอย่างเช่น การตรวจสอบข้อความ การจัดแนวข้อความในแต่ละย่อหน้า และการค้นหาคำ เป็นต้น
สตริงกับอะเรย์
สตริง คือ อะเรย์ของอักขระเช่น char a[6] อาจจะเป็นอะเรย์ขนาด 6 ช่อง อักขระ หรือเป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character เช่น
char a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};
char a[ ]=“HELLO”;
การกำหนดสตริง
การกำหนดสตริงทำได้หลายแบบ คือ
1. กำหนดเป็นสตริงที่มีค่าคงตัว (String Constants)
2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์
อะเรย์ของสตริง
ถ้าหากมีสตริงจำนวนมาก ก็ควรจะทำให้เป็นอะเรย์ของสตริง เพื่อที่จะเขียนโปรแกรมได้สะดวก การสร้างอะเรย์ของสตริง สามารถสร้างได้ทั้งแบบที่ให้ค่าเริ่มต้นและแบบที่กำหนดเป็นตัวแปร
การกำหนดตัวแปร country จะแตกต่างกับการกำหนดตัวแปรอะเรย์เพราะเป็นการกำหนดตัวแปรพอยเตอร์ขึ้น 4 ตัว โดยให้แต่ละตัวชี้ไปยังค่าคงตัวสตริงทั้ง4 ตัว โดยที่contry[0] จะชี้ไปที่ข้อมูลแรก contry[1]จะชี้ข้อมูลที่สอง contry[2] จะชี้ข้อมูลที่สาม และcontry[3] จะชี้ข้อมูลตัวสุดท้ายในการเขียนค่าเริ่มต้น คือ ค่าคงตัวสตริง เขียนไว้ในเครื่องหมายวงเล็บปีกกา และข้อมูลในเครื่องหมายคำพูด คือ ค่าคงตัวสตริง
ฟังก์ชัน puts ( ) ใช้ในการพิมพ์สตริงออกทางจอภาพ โดยการผ่านค่าแอดเดรสของสตริงไปให้เท่านั้นข้อสังเกตการกำหนดอะเรย์ของสตริงในลักษณะอย่างนี้ ไม่ใช่อะเรย์ที่แท้จริงตามหลักการของอะเรย์ เนื่องจากขนาดของช่องในอะเรย์ไม่เท่ากันแต่อนุโลมให้ถือว่าเป็นอะเรย์
อะเรย์ของสตริงที่ยาวเท่ากันอะเรย์ในลักษณะนี้จะถือว่าเป็นอะเรย์ที่แท้จริงและสามารถกำหนดได้ทั้งเมื่อมีการให้ค่าเริ่มต้น และเมื่อกำหนดเป็นตัวแปร โดยดำเนินการตามแบบการกำหนดอะเรย์ 2 มิติ เช่น
char fruit [3][7]={“Apple”, “Orange”, “Mango”};
กำหนดตัวแปร fruit เป็นแบบ 3 แถว 7 คอลัมน์ ในแต่ละช่องจะเก็บข้อมูลแบบอักขระอะเรย์ของสตริงที่ยาวเท่ากัน อะเรย์ในลักษณะนี้จะถือว่าเป็นอะเรย์ที่แท้จริง และสามารถกำหนดได้ทั้งเมื่อมีการให้ค่าเริ่มต้นและเมื่อกำหนดเป็นตัวแปร โดยดำเนินการตามแบบการกำหนดอะเรย์ 2 มิติ
สิ่งที่ได้รับจากการเรียน : ได้ทราบถึงการนำ Set และ String สามารถนำมาใช้กับ อะเรย์ ได้
โครงสร้างข้อมูลแบบเซ็ต
เป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มี ความสัมพันธ์กัน ในภาษาซี จะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้
ตัวดำเนินการของเซ็ต (Set operators) ประกอบด้วย
- set intersection
- set union
- set difference เป็นต้น
สมมติว่า ต้องการจัดตารางเรียน 4 วิชา ได้แก่ Math, English,Physics และ Chemistryให้กับผู้ลงทะเบียนเรียน
วิธีการแก้ปัญหาเบื้องต้น
- จะต้องกำหนดเซ็ตของผู้เรียนที่ลงทะเบียนเรียนในแต่ละวิชา
- นำเซ็ตดังกล่าวที่ได้มาทำการ intersection กัน หากมีเซ็ตใดที่ทำการ intersect กันแล้วมีข้อมูลสมาชิกในเซ็ตที่ซ้ำกันอยู่ จะไม่สามารถจัดให้วิชาดังกล่าวอยู่ในวันเวลาเดียวกันได้
โครงสร้างข้อมูลแบบสตริง
สตริง (String) หรือ สตริงของอักขระ (CharacterString) เป็นข้อมูลที่ประกอบไปด้วยตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง
การประยุกต์ใช้คอมพิวเตอร์ที่เกี่ยวกับข้อมูลที่เป็นสตริงมีการนำไปใช้สร้างโปรแกรมประเภทบรรณาธิการข้อความ(text editor) หรือโปรแกรมประเภทประมวลผลคำ (word processing) ซึ่งมีการทำงานที่อำนวยความสะดวกหลายอย่างเช่น การตรวจสอบข้อความ การจัดแนวข้อความในแต่ละย่อหน้า และการค้นหาคำ เป็นต้น
สตริงกับอะเรย์
สตริง คือ อะเรย์ของอักขระเช่น char a[6] อาจจะเป็นอะเรย์ขนาด 6 ช่อง อักขระ หรือเป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character เช่น
char a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};
char a[ ]=“HELLO”;
การกำหนดสตริง
การกำหนดสตริงทำได้หลายแบบ คือ
1. กำหนดเป็นสตริงที่มีค่าคงตัว (String Constants)
2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์
อะเรย์ของสตริง
ถ้าหากมีสตริงจำนวนมาก ก็ควรจะทำให้เป็นอะเรย์ของสตริง เพื่อที่จะเขียนโปรแกรมได้สะดวก การสร้างอะเรย์ของสตริง สามารถสร้างได้ทั้งแบบที่ให้ค่าเริ่มต้นและแบบที่กำหนดเป็นตัวแปร
การกำหนดตัวแปร country จะแตกต่างกับการกำหนดตัวแปรอะเรย์เพราะเป็นการกำหนดตัวแปรพอยเตอร์ขึ้น 4 ตัว โดยให้แต่ละตัวชี้ไปยังค่าคงตัวสตริงทั้ง4 ตัว โดยที่contry[0] จะชี้ไปที่ข้อมูลแรก contry[1]จะชี้ข้อมูลที่สอง contry[2] จะชี้ข้อมูลที่สาม และcontry[3] จะชี้ข้อมูลตัวสุดท้ายในการเขียนค่าเริ่มต้น คือ ค่าคงตัวสตริง เขียนไว้ในเครื่องหมายวงเล็บปีกกา และข้อมูลในเครื่องหมายคำพูด คือ ค่าคงตัวสตริง
ฟังก์ชัน puts ( ) ใช้ในการพิมพ์สตริงออกทางจอภาพ โดยการผ่านค่าแอดเดรสของสตริงไปให้เท่านั้นข้อสังเกตการกำหนดอะเรย์ของสตริงในลักษณะอย่างนี้ ไม่ใช่อะเรย์ที่แท้จริงตามหลักการของอะเรย์ เนื่องจากขนาดของช่องในอะเรย์ไม่เท่ากันแต่อนุโลมให้ถือว่าเป็นอะเรย์
อะเรย์ของสตริงที่ยาวเท่ากันอะเรย์ในลักษณะนี้จะถือว่าเป็นอะเรย์ที่แท้จริงและสามารถกำหนดได้ทั้งเมื่อมีการให้ค่าเริ่มต้น และเมื่อกำหนดเป็นตัวแปร โดยดำเนินการตามแบบการกำหนดอะเรย์ 2 มิติ เช่น
char fruit [3][7]={“Apple”, “Orange”, “Mango”};
กำหนดตัวแปร fruit เป็นแบบ 3 แถว 7 คอลัมน์ ในแต่ละช่องจะเก็บข้อมูลแบบอักขระอะเรย์ของสตริงที่ยาวเท่ากัน อะเรย์ในลักษณะนี้จะถือว่าเป็นอะเรย์ที่แท้จริง และสามารถกำหนดได้ทั้งเมื่อมีการให้ค่าเริ่มต้นและเมื่อกำหนดเป็นตัวแปร โดยดำเนินการตามแบบการกำหนดอะเรย์ 2 มิติ
สิ่งที่ได้รับจากการเรียน : ได้ทราบถึงการนำ Set และ String สามารถนำมาใช้กับ อะเรย์ ได้
DTS03-30/06/2009
สรุปบทเรียน Array and Record
อาร์เรย์หมายถึงการจัดชุดของข้อมูลที่เป็นชนิดเดียวกันที่กำหนดโดยรูปแบบของช่องตาราง
ที่จัดเก็บจะต้องเท่ากันทุกช่องโดยทั่วไปอาร์เรย์จะมี 1 มิติ 2 มิติ และหลายมิติ
อาร์เรย์ 1 มิติ
เป็นตัวแปรที่เก็บข้อมูลเพียงแถวเดียวหรือชั้นเดียวเช่น
ในการคำนวณหาสมาชิกของอาร์เรย์ 1 มิติทำได้ดังนี้
จำนวนสมาชิกของอาร์เรย์ = (u-l)+1
u คือค่าสูงสุด หรือ Upper bound
l คือค่าต่ำสุด หรือ Lower bound
ส่วน 2 มิติสามารถหาได้ดังนี้
จำนวนสมาชิก = M x N
รูปแบบของการประกาศตัวแปรอาร์เรย์มิติเดียว
type array-name[n];
type คือ ชนิดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น เช่น int,float,char เป็นต้น
array-name คือ ชื่อของตัวแปรอาร์เรย์ที่ต้องตั้งให้สื่อและเข้ากับชนิดของตัวแปร
และจะต้องไม่ไปตรงกับคำสงวนของภาษาซีด้วย
n คือขนาดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น
เช่น int num[3];
การกำหนดข้อมูลให้กับตัวแปรอาร์เรย์
เราสามารถกำหนดไปพร้อมกับการประสร้างตัวแปรได้เลย เช่น
type array-name = {value-1,value-2,....value-n};
value-1,value-2 คือข้อมูลที่กำหนดให้ตัวแปรและต้องเป็นชนิดเดียวกับตัวแปรนั้น ๆ ด้วย เช่น
int number[3] = {23,-123,43};
char name[5] = "BENZ";
อาร์เรย์ 2 มิติ
มีลักษณะการกำหนดตำแหน่งแบบแถวและคอลัมน์
รูปแบบของการประกาศตัวแปรอาร์เรย์ 2 มิติ
type array-name[n][m];
type คือ ชนิดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น เช่น int,float,char เป็นต้น
array-name คือ ชื่อของตัวแปรอาร์เรย์ที่ต้องตั้งให้สื่อและเข้ากับชนิดของตัวแปร
และจะต้องไม่ไปตรงกับคำสงวนของภาษาซีด้วย
n คือ จำนวนแถวของตัวแปรอาร์เรย์
m คือ จำนวนคอลัมน์ของตัวแปรอาร์เรย์
เช่น int num[3][5];
Structure โครงสร้างข้อมูล
หมายถึง การที่นำข้อมูลที่มีความเกี่ยวข้องกัน เช่น ข้อมูลของนักศึกษาที่อาจประกอบด้วย
ชื่อ,นามสกุล,อายุ,เพศ,ชั้นเรียน มารวมกันและจัดทำเป็นโครงสร้างข้อมูล ดังภาพ
แต่ในการเรียนใช้งานจริง ๆ เราจะต้องสร้างตัวแปรชนิดโครงสร้างขึ้นมาใช้งานจริง ๆ
ไม่สามารถใช้โครงสร้าง student ได้
การประกาศตัวแปรชนิดโครงสร้าง
struct name {
type var-1;
type var-2;
.....
type var-n;
} struct-variable;
struct คือ คำที่ใช้กำหนดโครงสร้างข้อมูล
(ต้องมีเสมอ)
name คือ ชื่อของโครงสร้างข้อมูลที่จะสร้างขึ้น
type var-1,type var-2 คือชื่อตัวแปร
ในกลุ่มโครงสร้างข้อมูล
struct-variable คือชื่อของตัวแปรชนิดโครงสร้าง
ที่ต้องการสร้างขึ้นจะมีลักษณะโครงสร้างภายใน
เหมือนกับโครงสร้างข้อมูลที่กำหนด
** กรณีประกาศตัวแปรโครงสร้างหลายตัวใช้คอมม่าขั้นหรือประกาศอีกแบบ เช่น
struct struct-name variable;
ตัวอย่าง
struct student student1;
*** เราสามารถประกาศ Structure หนึ่งเป็นสมาชิกของอีก Structure ก็ได้
แต่ต้องประกาศตัวที่จะนำไปใส่ไปไว้อีก Structure ก่อน
การอ้างถึงสมาชิกในตัวแปรชนิดโครงสร้าง
struct-name.variable-name
struct-name คือ ชื่อของตัวแปรชนิดโครงสร้าง (ไม่ใช่ชื่อโครงสร้าง)
. คือเครื่องหมายขั้นระหว่างชื่อตัวแปรชนิดโครงสร้างกับตัวแปรที่เป็นสมาชิก
variable-name คือชื่อของตัวแปรที่เป็นสมาชิก
การกำหนดข้อมูลให้ตัวแปรชนิดโครงสร้าง
เราสามารถกำหนดได้เหมือนตัวแปรทั่วไปแต่ต้องอ้างอิงถึงสมาชิกให้ถูกต้อง เช่น
student1.age = 15;
student1.sex = 'M';
กรณีถ้าเป็นอาร์เรย์ของตัวแปรชนิดโครงสร้างสามารถเขียนได้ดังนี้
student1[0].age = 15;
student1[1].sex = 'M';
อาร์เรย์หมายถึงการจัดชุดของข้อมูลที่เป็นชนิดเดียวกันที่กำหนดโดยรูปแบบของช่องตาราง
ที่จัดเก็บจะต้องเท่ากันทุกช่องโดยทั่วไปอาร์เรย์จะมี 1 มิติ 2 มิติ และหลายมิติ
อาร์เรย์ 1 มิติ
เป็นตัวแปรที่เก็บข้อมูลเพียงแถวเดียวหรือชั้นเดียวเช่น
ในการคำนวณหาสมาชิกของอาร์เรย์ 1 มิติทำได้ดังนี้
จำนวนสมาชิกของอาร์เรย์ = (u-l)+1
u คือค่าสูงสุด หรือ Upper bound
l คือค่าต่ำสุด หรือ Lower bound
ส่วน 2 มิติสามารถหาได้ดังนี้
จำนวนสมาชิก = M x N
รูปแบบของการประกาศตัวแปรอาร์เรย์มิติเดียว
type array-name[n];
type คือ ชนิดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น เช่น int,float,char เป็นต้น
array-name คือ ชื่อของตัวแปรอาร์เรย์ที่ต้องตั้งให้สื่อและเข้ากับชนิดของตัวแปร
และจะต้องไม่ไปตรงกับคำสงวนของภาษาซีด้วย
n คือขนาดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น
เช่น int num[3];
การกำหนดข้อมูลให้กับตัวแปรอาร์เรย์
เราสามารถกำหนดไปพร้อมกับการประสร้างตัวแปรได้เลย เช่น
type array-name = {value-1,value-2,....value-n};
value-1,value-2 คือข้อมูลที่กำหนดให้ตัวแปรและต้องเป็นชนิดเดียวกับตัวแปรนั้น ๆ ด้วย เช่น
int number[3] = {23,-123,43};
char name[5] = "BENZ";
อาร์เรย์ 2 มิติ
มีลักษณะการกำหนดตำแหน่งแบบแถวและคอลัมน์
รูปแบบของการประกาศตัวแปรอาร์เรย์ 2 มิติ
type array-name[n][m];
type คือ ชนิดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น เช่น int,float,char เป็นต้น
array-name คือ ชื่อของตัวแปรอาร์เรย์ที่ต้องตั้งให้สื่อและเข้ากับชนิดของตัวแปร
และจะต้องไม่ไปตรงกับคำสงวนของภาษาซีด้วย
n คือ จำนวนแถวของตัวแปรอาร์เรย์
m คือ จำนวนคอลัมน์ของตัวแปรอาร์เรย์
เช่น int num[3][5];
Structure โครงสร้างข้อมูล
หมายถึง การที่นำข้อมูลที่มีความเกี่ยวข้องกัน เช่น ข้อมูลของนักศึกษาที่อาจประกอบด้วย
ชื่อ,นามสกุล,อายุ,เพศ,ชั้นเรียน มารวมกันและจัดทำเป็นโครงสร้างข้อมูล ดังภาพ
แต่ในการเรียนใช้งานจริง ๆ เราจะต้องสร้างตัวแปรชนิดโครงสร้างขึ้นมาใช้งานจริง ๆ
ไม่สามารถใช้โครงสร้าง student ได้
การประกาศตัวแปรชนิดโครงสร้าง
struct name {
type var-1;
type var-2;
.....
type var-n;
} struct-variable;
struct คือ คำที่ใช้กำหนดโครงสร้างข้อมูล
(ต้องมีเสมอ)
name คือ ชื่อของโครงสร้างข้อมูลที่จะสร้างขึ้น
type var-1,type var-2 คือชื่อตัวแปร
ในกลุ่มโครงสร้างข้อมูล
struct-variable คือชื่อของตัวแปรชนิดโครงสร้าง
ที่ต้องการสร้างขึ้นจะมีลักษณะโครงสร้างภายใน
เหมือนกับโครงสร้างข้อมูลที่กำหนด
** กรณีประกาศตัวแปรโครงสร้างหลายตัวใช้คอมม่าขั้นหรือประกาศอีกแบบ เช่น
struct struct-name variable;
ตัวอย่าง
struct student student1;
*** เราสามารถประกาศ Structure หนึ่งเป็นสมาชิกของอีก Structure ก็ได้
แต่ต้องประกาศตัวที่จะนำไปใส่ไปไว้อีก Structure ก่อน
การอ้างถึงสมาชิกในตัวแปรชนิดโครงสร้าง
struct-name.variable-name
struct-name คือ ชื่อของตัวแปรชนิดโครงสร้าง (ไม่ใช่ชื่อโครงสร้าง)
. คือเครื่องหมายขั้นระหว่างชื่อตัวแปรชนิดโครงสร้างกับตัวแปรที่เป็นสมาชิก
variable-name คือชื่อของตัวแปรที่เป็นสมาชิก
การกำหนดข้อมูลให้ตัวแปรชนิดโครงสร้าง
เราสามารถกำหนดได้เหมือนตัวแปรทั่วไปแต่ต้องอ้างอิงถึงสมาชิกให้ถูกต้อง เช่น
student1.age = 15;
student1.sex = 'M';
กรณีถ้าเป็นอาร์เรย์ของตัวแปรชนิดโครงสร้างสามารถเขียนได้ดังนี้
student1[0].age = 15;
student1[1].sex = 'M';
RECORD DTS02 - 23/6/2552
สรุปบทเรียนที่ได้รับ
เรียน ความหมายของโครงสร้างข้อมูล ได้รู้ว่า โครงสร้างข้อมูลมี 2 ประเภท
1.โครงสร้างข้อมูลทางกายภาพ
2.โครงสร้างข้อมูลทางตรรกะ
โครงสร้างข้อมูลทางกายภาพ ได้แก่ แถวลำดับ(เป็นการเก็บข้อมูลเดียวกันเท่านั้น) ระเบียนข้อมูล (เป้นการเก้บข้อมูลมากกว่า 1 ชนิด ใน Key เดียวกัน) และ แฟ้ม ข้อมูล
โครงสร้างข้อมูลทางตรรกะ มี 2 ประเภท
1. โครงสร้างข้อมูลแบบชิงเส้น (จะมีรูปแบบที่สัมพันธ์ และต่อเนื่องกัน)
2. โครงสร้างข้อมูลแบบไม่เชิงเส้น (มีความสัมพันธ์ในหลายทิศทาง หรือ หลากหลายนั้นเอง)
การแทนข้อมูลในหน่วยความจำหลัก มี 2 ประเภท
1 การแทนที่ข้อมูลแบบสแตติก
( เป็นการแทนที่ข้อมูลที่ต้องจองก่อน และไม่สามารถ ลด หรือเพิ่ม ในภายหลังได้)
2.การแทนข้อมูลแบบไดนามิก
(เป็นการแทนที่ข้อมูลโดยไม่ต้องจอง และสามารถ เพื่มหรือลด ในภายหลังได้)
ขั้นตอนวิธี
คือการแก้ไขปัญหาอย่างมีระบบ สามารถเขียนได้หลายแบบ กระชับและเหมาะสม
ขั้นตอนมี 7 ข้อ
พูดโดยรวมแล้ว ให้มีความถูกต้อง มีความรวดเร็วในการทำงาน มีความยืดหยุ่นในการทำงานและ
ง่ายต่อการเข้าใจ พัตนาง่าย หรือพูดอีกอย่างคือ ทำให้ดีที่สุดในทุกๆทางที่จะทำได้
เรื่อง สัญลักษณ์ ในการเขียนผังงาน(ตัวดำเนินงานในรูปลักษณ์ของผังงาน)
เรื่องนิพจน์(เรื่อง เครื่องหมาย > < = )
เรื่อง ภาษาขะนตอนวิธี
1.ตัวแปรต้องเป้น อักษร อักษรผสม และตัวเลข
2.การกำหนดตัวแปร ใช้เครื่องหมาย
3.นิพจน์ การคำนวนตามลำดับขั้นตอน
4.ข้อความไปยังขั้นตอน ใช้รูปแบบ คือ
Goto เลขที่ชั้นตอน
5.เรื่องเงือนไข
แบบทางเลือกเดียว
if (condition) then statement 1
แบบสองทางเลือก
if (condition) then statement 1
else statement 2
6. การวนซํา
7.คำอธิบาย บอกถึงรายละเอียดต่างๆของขั้นตอนทำงาน
มีการทดสอบ หลัง ช.ม
ทดสอบว่า รู้ จักความหมายของตัวแปร
ทดลอบ ว่ารู้จักการวนวซซํา หรือไม่
for(I=1,I<10,I++);
วนกลับทั้งหมด 10 ครั้ง Iจะมีค่า=10 ในแต่ละรอบ I จะบวก 1
การบ้าน
#include<stdio.h>
#include<string.h>
#include
#include
void main()
{
struct movie {
char name[50];
char produced[30];
char costume_designer[15];
char actor[30];
char actor01[30];
char actor02[30];
int in_theaters;
char month[10];
int year;
};
struct movie data;
strcpy(data.name,"Harry Potter and the Half the blood prince");
strcpy(data.produced,"David Yates");
strcpy(data.costume_designer,"JANY TEMIME");
strcpy(data.actor,"Hugh Jackman");
strcpy(data.actor01,"Liev Schreiber");
strcpy(data.actor02,"Danny Huston");
data.in_theaters=16;
strcpy(data.month,"Jaly");
data.year=2006;
printf(" Movie is new\n\n");
printf(" ******************************************\n\n");
printf(" %s\n",data.name);
printf(" Produced: %s\n",data.produced);
printf(" Costume Designer: %s\n",data.costume_designer);
printf(" Actor: %s,%s,%s\n",data.actor,data.actor01,data.actor02);
printf(" In Theaters: %d/%s/%d\n\n",
data.in_theaters,data.month,data.year);
printf(" ******************************************");
}
เรียน ความหมายของโครงสร้างข้อมูล ได้รู้ว่า โครงสร้างข้อมูลมี 2 ประเภท
1.โครงสร้างข้อมูลทางกายภาพ
2.โครงสร้างข้อมูลทางตรรกะ
โครงสร้างข้อมูลทางกายภาพ ได้แก่ แถวลำดับ(เป็นการเก็บข้อมูลเดียวกันเท่านั้น) ระเบียนข้อมูล (เป้นการเก้บข้อมูลมากกว่า 1 ชนิด ใน Key เดียวกัน) และ แฟ้ม ข้อมูล
โครงสร้างข้อมูลทางตรรกะ มี 2 ประเภท
1. โครงสร้างข้อมูลแบบชิงเส้น (จะมีรูปแบบที่สัมพันธ์ และต่อเนื่องกัน)
2. โครงสร้างข้อมูลแบบไม่เชิงเส้น (มีความสัมพันธ์ในหลายทิศทาง หรือ หลากหลายนั้นเอง)
การแทนข้อมูลในหน่วยความจำหลัก มี 2 ประเภท
1 การแทนที่ข้อมูลแบบสแตติก
( เป็นการแทนที่ข้อมูลที่ต้องจองก่อน และไม่สามารถ ลด หรือเพิ่ม ในภายหลังได้)
2.การแทนข้อมูลแบบไดนามิก
(เป็นการแทนที่ข้อมูลโดยไม่ต้องจอง และสามารถ เพื่มหรือลด ในภายหลังได้)
ขั้นตอนวิธี
คือการแก้ไขปัญหาอย่างมีระบบ สามารถเขียนได้หลายแบบ กระชับและเหมาะสม
ขั้นตอนมี 7 ข้อ
พูดโดยรวมแล้ว ให้มีความถูกต้อง มีความรวดเร็วในการทำงาน มีความยืดหยุ่นในการทำงานและ
ง่ายต่อการเข้าใจ พัตนาง่าย หรือพูดอีกอย่างคือ ทำให้ดีที่สุดในทุกๆทางที่จะทำได้
เรื่อง สัญลักษณ์ ในการเขียนผังงาน(ตัวดำเนินงานในรูปลักษณ์ของผังงาน)
เรื่องนิพจน์(เรื่อง เครื่องหมาย > < = )
เรื่อง ภาษาขะนตอนวิธี
1.ตัวแปรต้องเป้น อักษร อักษรผสม และตัวเลข
2.การกำหนดตัวแปร ใช้เครื่องหมาย
3.นิพจน์ การคำนวนตามลำดับขั้นตอน
4.ข้อความไปยังขั้นตอน ใช้รูปแบบ คือ
Goto เลขที่ชั้นตอน
5.เรื่องเงือนไข
แบบทางเลือกเดียว
if (condition) then statement 1
แบบสองทางเลือก
if (condition) then statement 1
else statement 2
6. การวนซํา
7.คำอธิบาย บอกถึงรายละเอียดต่างๆของขั้นตอนทำงาน
มีการทดสอบ หลัง ช.ม
ทดสอบว่า รู้ จักความหมายของตัวแปร
ทดลอบ ว่ารู้จักการวนวซซํา หรือไม่
for(I=1,I<10,I++);
วนกลับทั้งหมด 10 ครั้ง Iจะมีค่า=10 ในแต่ละรอบ I จะบวก 1
การบ้าน
#include<stdio.h>
#include<string.h>
#include
#include
void main()
{
struct movie {
char name[50];
char produced[30];
char costume_designer[15];
char actor[30];
char actor01[30];
char actor02[30];
int in_theaters;
char month[10];
int year;
};
struct movie data;
strcpy(data.name,"Harry Potter and the Half the blood prince");
strcpy(data.produced,"David Yates");
strcpy(data.costume_designer,"JANY TEMIME");
strcpy(data.actor,"Hugh Jackman");
strcpy(data.actor01,"Liev Schreiber");
strcpy(data.actor02,"Danny Huston");
data.in_theaters=16;
strcpy(data.month,"Jaly");
data.year=2006;
printf(" Movie is new\n\n");
printf(" ******************************************\n\n");
printf(" %s\n",data.name);
printf(" Produced: %s\n",data.produced);
printf(" Costume Designer: %s\n",data.costume_designer);
printf(" Actor: %s,%s,%s\n",data.actor,data.actor01,data.actor02);
printf(" In Theaters: %d/%s/%d\n\n",
data.in_theaters,data.month,data.year);
printf(" ******************************************");
}
ประวัติ
นาย พชร ภูววัฒนา รหัสประจำตัว 50132792078
Mr. Pachara Phuwawatthana
ชื่อเล่น M
หลักสูตร การบริหารธุรกิจ (คอมพิวเตอร์ธุรกิจ) คณะ วิทยาการจัดการ
มหาวิทยาลัยราชภัฏสวนดุสิต
E-mail = u50132792078@gmail.com
Mr. Pachara Phuwawatthana
ชื่อเล่น M
หลักสูตร การบริหารธุรกิจ (คอมพิวเตอร์ธุรกิจ) คณะ วิทยาการจัดการ
มหาวิทยาลัยราชภัฏสวนดุสิต
E-mail = u50132792078@gmail.com
