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

สิ่งที่ได้รับจากการเรียนวิชาเตรียมฝึกประสบการณ์วิชาชีพ

1. ด้านการตรงต่อเวลา : ในการดำรงชีวิตในปัจจุบันเราจะต้องเป็นคนที่ตรงต่อเวลา มีความรับผิดชอบในหน้าที่ที่เราควรทำ เพื่อที่จะได้ไม่ทำให้ผู้อื่นต้องมารอคอยหรือมาเดือดร้อนเพราะเรา

2. ด้านการมีระเบียบวินัย : ความมีระเบียบวินัยในตัวเองนั้นเป็นสิ่งที่สำคัญ คนเราต้องมีระเบียบอยู่ในกฎเกณฑ์ เราควรรู้ว่าอะไรควรทำ อะไรไม่ควรทำ ถ้าเราทำได้ดังนี้เราก็จะอยู่ร่วมกันได้อย่างสงบสุข ไม่ว่าจะเป็นสังคมเล็กหรือสังคมใหญ่ก็ต้องการการมีระเบียบวินัยด้วยกันทั้งนั้น

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

4. ด้านการทำงานร่วมกับผู้อื่น : ทำให้เรารู้รักสามัคคีซึ่งกันและกันมากยิ่งขึ้น รู้จักแบ่งปันซึ่งกันและกัน และทำให้เราได้รู้จักเพื่อนใหม่ๆตลอดเวลา ซึ่งสิ่งเหล่านี้เราสามารถนำไปใช้ได้ในชีวิตประจำวัน ทั้งในด้านของการศึกษา และการทำงาน รวมถึงการดำรงชีวิตในปัจจุบันนี้อีกด้วย

5. ด้านบุคลิกภาพ : ในการเข้าเรียนวิชาเตรียมฝึกประสบการณ์วิชาชีพทุกครั้ง เราจะต้องเรียบร้อยตั้งแต่ศีรษะจรดปลายเท้า เริ่มจากการแต่งกายให้เรียบร้อยและถูกต้องตามระเบียบของทางมหาวิทยาลัย ส่วนผมก็จะต้องเกล้าและติดเน็ตให้เป็นระเบียบ ส่วนรองเท้าก็ต้องเป็นสีดำห้ามมีลวดลาย ซึ่งทั้งหมดนี้ทำให้เรามีบุคลิกภาพที่ดีขึ้น ซึ่งเป็นผลดีต่อตัวเราเอง จะทำให้คนทั่วไปมองเราในทางบวก และอีกประการหนึ่งที่สำคัญคือเวลาไปสมัครงานจะทำให้เราดูดี สง่าผ่าเผย เป็นที่น่าเชื่อถือแก่บุคคลที่ได้พบเห็น

***********************************************************************

DST-11-16-09-2552

สรุปการเรียน "data structure"

เรื่อง Searching



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



วัตถุประสงค์ของการค้นหาโดยทั่วไป ได้แก่

• เพื่อดูรายละเอียดเฉพาะข้อมูลส่วนที่ต้องการ


• ดึงข้อมูลตัวที่ค้นหาออกจากโครงสร้าง


• เปลี่ยนแปลงแก้ไขรายละเอียดบางอย่างของข้อมูลที่ค้นพบ และ/หรือเพิ่มข้อมูลตัวที่ค้นหา

การค้นหาข้อมูลแบ่งเป็น 2 ประเภท

1. การค้นหาข้อมูลแบบภายใน(Intemal Searching)


2. การค้นหาข้อมูลแบบภายนอก(Extemal Searching)

1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear) เป็นวิธีที่ใช้กับข้อมูลทียังไม่ได้เรียงลำดับ

หลักการ

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

2. การค้นหาแบบเซนตินัล(Sentinel) เป็นวิธีที่ค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่มีประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนามาจากอัลกอริ่มแบบเชิงเส้น

หลักการ

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

3. การค้นหาแบบไบนารี(Binary Searching) ใช้กับข้อมูลที่ถูกจัดเรียงแล้วเท่านั้น

หลักการของการค้นหา คือ ข้อมุลถูกแบ่งออกเป็น 2 ส่วนแล้วนำค่ากลางของข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา

1.หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้นตำแหน่งตัวเเทนข้อมุล

2.นำผลการเปรียบเทียบกรณีที่หาไม่พบมาใช้ในการค้นหารอบต่อไป

*********************************************************************************

DST-10-09-09-2552

สรุปการเรียน "data structure"
เรื่อง Sorting

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


วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภท คือ
(1)การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อน ข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภายนอก(external sorting) เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูล จากหน่วยความจำหลักและหน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้ในการเรียง ลำดับข้อมูลแบบภายใน


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


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


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


การเรียงลำดับแบบฐาน (radix sort)เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก
1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน2. การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่ม ๆตามลำดับการเข้ามา
3. ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อย ๆ จนหมดทุกกลุ่ม
4. ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณา จัดเรียงในหลักสิบต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ

*********************************************************************************

DTS-09-02-09-2552

สรุปเนื้อหา "data structure"

เรื่อง กราฟ (Graph)



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


นิยามของกราฟ
กราฟเป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบด้วยลุ่มของสิ่งสองสิ่ง คือ

1. โหนด(Nodes) หรือ เวอร์เทกซ์(Vertexes)
2. เส้นเชื่อมระหว่างโหนด เรียก เอ็จ(Edges)

กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง(Undirected Graphs) และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง(Directed Graphs) บางครั้งเรียกว่า "ไดกราฟ"(Digraph)

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

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

กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จโดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง(Empty Graph) นั่นคือ ไม่มีโหนดใดเป็นโหนดแรก(First Node) หรือไม่มีโหนดเริ่มต้นและไม่มีโหนดใดเป็นโหนดส้นสุด โหนดสองโหนดในกราฟแบบไม่มีทิศทางถือว่าเป็นโหนดที่ใกล้กัน(Adjacent)

กราฟแบบมีทิศทางเป็นเซตจำกัดของโหนดและเอ็จ

รูปแบบต่างๆของกราฟแบบมีทิศทางเหมือนกับรูปแบบของกราฟไม่มีทิศทางต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำหนดด้วยเท่านั้น

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

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

การจัดเก็บกราฟด้วยวิธีเก็บโหนดและพอยเตอร์นี้ยุ่งยาก ในการจัดเก็บเพิ่มขึ้นเนื่องจากต้องเก็บโหนดและพอยเตอร์ในแถวลำดับ 2 มิติ และต้องจัดเก็บโหนดที่สัมพันธ์ด้วยในแถวลำดับ

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

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

วิธีแทนกราฟในความจำหลักอีกวิธีหนึ่งซึ่งเป็นที่นิยมใช้กันมากที่สุด คือ การแทนด้วยแอดจาเซนซีเมทริกซ์(Adjacency Matrix)

การท่องไปในกราฟ

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

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

*********************************************************************************

DTS-08-26-08-2552

สรุปเนื้อหา "data structure"
เรื่อง ทรี(Tree)

ทรี(Tree) เป็นโครงสร้างข้อมูลที่มีความสัมพันธ์ระหว่างโหนด จะมีความสัมพันธ์ลดหลุ่นกันเป็นลำดับชั้น (Hierarchical Relationship) ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่งข้อมูล แต่ละโหนดจะมีความสัมพันธ์กับโหนดในระดับได้หลายๆโหนดเรียกโหนดดังกล่าวว่า "โหนดแม่"(Parent or Mother Node)
โหนดที่อยู่ตำกว่าโหนดแมอยู่ระดับหนึ่งเรียกว่า "โหนดลูก"(Child or Son Node)
โหนดที่อยุ่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า "โหนดราก"(Root Node)
โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า "โหนดพี่น้อง"(Siblings)
โหนดที่ไม่มีโหนดลูกเรียกว่า "โหนดใบ"(Leave Node)
เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด "กิ่ง"(Branch)

นิยยามของทรี

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

นิยามที่เกี่ยวข้องกับทรี

1. ฟอร์เรสต์(Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือเซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรีที่มีแบบแผน(Ordered Tree) หมายถึง ทรีที่โหนดต่างๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา ไปทางซ้าย เป็นต้น
3. ทรีคล้าย(Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน(Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ มีข้อมูลที่เหมือนกัน
5. กำลัง(Degree) หมายถึง จำนวนทรีย่อยของโหนดนั้นๆ
6. ระดับของโหนด(Level of node) คือ ระยะทางในแนวดิ่งของโหนดนั้นๆ ที่อยู่ห่างจากโหนดราก และโหนดเส้นทางตามแนวดิ่งของโหนดใดๆ ซึ่งห่างจากโหนดรากเรียกว่า ความสูง(Height) หรือความลึก(Depth)

การแทนที่ทรีในหน่วยความจำหลัก

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

วิธีการแทนที่ที่ง่ายที่สุด คือ ทำให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์เทากัน

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

ไบนารีทรีทุกๆโหนดมีทรีทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบและโหนดใบทุกโหนดจะต้องอยู่ในระดับเดียวกัน เรียกว่า ไบนารีทรีแบบสมบูรณ์(Complete binary tree) สามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณได้

การแปลงทรีทั่วไปให้เป็นไบนารีทรี

ขั้นตอนการแปลงทั่วๆไปให้เป็นไบนารีทรี มีดังนี้

1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่นๆ
2. ให้เชื่อมความสัมพันธ์ะหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา

การท่องไปในไบนารีทรี

ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี(Treversing Binary Tree) เพื่อเข้าไปเยือนทุกๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุกๆโหนดๆละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร

1.การท่องไปแบบพรีออร์เดอร์(Preorder Traversal) เป็นการเดินทางไปเยือนโหนดต่างๆในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้

• เยือนโหนดราก
• ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
• ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่างๆในทรีด้วยวิธี LNR มีขั้นตอนการเดินดังต่อไปนี้

• ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
• เยือนโหนดราก
• ทองไปในทรีย่อยทางขวาแบบอินออร์เดอร์

3.การท่องไปแบบโพสออร์เดอร์(Postorder Traversal) เป็นการเดินทางเขาไปเยือนโหนดต่างๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้

• ท่องไปในย่อยทางซ้ายแบบโพสออร์เดอร์
• ท่องไปในทรีย่อยทางขวาแบบโพสออร์เดอร์
• เยือนโหนดราก

*********************************************************************************

DTS-07-05-08-2552

สรุปเนื้อหา "data structure"
เรื่อง คิว(Queue)


คิว(Queue) เป็นโครงสร้างข้อมูลเชิงเส้นที่นิยามการเพิ่มหรือการลบข้อมูลว่าจะทำที่ปลายลิสต์คนละด้าน ปลายลิสต์ด้านที่เป็นทางเข้าจะเรียกว่าส่วนท้ายหรือเรียร์(rear) ปลายลิสต์ด้านที่เป็นทางออกจะเรียกว่าส่วนหน้าหรือฟรอนต์(front) ข้อมูลที่เข้ามาในคิวก่อนจะออกจากคิวก่อนตามลำดับการเข้ามา จึงเรียกคุณลักษณะแบบนี้ว่า "เข้าก่อนออกก่อน" หรือ First In First Out (FIFO)


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

1. การสร้างคิวด้วยแถวลำดับ
2. การเพิ่มข้อมูลให้กับคิว
3. การนำเข้าข้อมูลจากคิว

ข้อจำกัดของคิว

โครงสร้างคิวยังไม่มีประสิทธิภาพเท่าที่ควร เนื่องจากเมื่อมีการเพิ่มข้อมูลจนเต็มและมีการลบข้อมูลบางจำนวนออกจากโครงสร้างคิวแล้ว ตัวแปร rear ยังมีค่าเท่าเดิม ไม่สามารถเปลี่ยนไปยังต้นแถวลำดับได้จนกว่าจะมีการลบข้อมูลทุกจำนวนออกจากคิว ทำให้เสียพื้นที่ส่วนต้นของโครงส้รางคิวในตำแหน่งที่ตัวแปร front ผ่านมาแล้ว จากสาเหตุนี้ทำให้มีการพัฒนาโครงสร้างคิวใหม่ ให้รับข้อมูลเพิ่มในพื้นที่ส่วนต้นแถวลำดับที่ว่าง ด้วยการนำส่วนปลายของโครงสร้างคิว ทั้ง 2 ด้านมาบรรจบกันในลักษณะวงกลม เรียกว่า คิววงกลม(Circular Queue)

คิววงกลม คือ คิวที่เมื่อเก็บข้อมูลถึงปลายลิสต์แล้วยอมให้เก็บข้อมูลใหม่เพิ่มที่ส่วนต้นลิสต์ได้ถ้าพื้นที่ส่วนต้นของลิสต์ว่าง

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

1. การสร้างคิววงกลมด้วยแถวลำดับ
2. การเพิ่ข้อมูลให้กับคิววงกลม
3. การนำข้อมูลออกคิววงกลม

การจัดการคิวด้วยรายการโยง

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

1. การประกาศโครงสร้างข้อมูลคิววงกลม
2. การเพิ่มข้อมูลลงในคิววงกลม
3. การนำข้อมูลออกจากคิวงวกลม
4. การแสดงข้อมูลในคิววงกลม

*********************************************************************************

DTS-06-29-07-2552

สรุปบทเรียน "data structure"
เรื่อง stack

การใช้สแตกเพื่อแปลงรูปนิพจน์ทางคณิตศาสตร์

• นิพจน์ Infix คือ นิพจน์ที่เครืองหมายดำเนินการ(Operator) อยู่ระหว่างตัวดำเนินการ(Operands) เช่น a+b-c
• นิพจน์ Perfix คือ นิพจน์ที่เครื่องหมายดำเนินการ(Operator) อยู่หน้าตัวดำเนินการ(Operands) เช่น +-ab
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ(Operator) อยู่หลังตัวดำเนินการ(Operands) เช่น ab*/

ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix

1.อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว

2.ถ้าเป็นตัวถูกดำเนินการจะย้ายไปเป็นตัวอักษรในนิพจน์ Postfix

3.ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัวดำเนินารที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก

-ถ้ามีความสำคัญมากจะถูก push ลงในสแตก

-ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix

4.ตัวดำเนินการที่เป็น ")" จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่นๆถูก pop ออกจากสแตก นำไปเรียงต่อกันในนิพจน์ Prostfix จนกว่าจะเจอ ")" จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ

5.เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อใน Prostfix

*********************************************************************************