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

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

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

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

การบ้าน iostream.h & stdio.h

เขียนโปรแกรมโดยใช้ stdio.h

#include
main()
{
char name [20];
char number [20];
char brand [20];
float price [20];
printf ("---------Buy Telephone---------\n");
printf ("name\n");
scanf("%s",&name);
printf ("number\n");
scanf ("%s",&number);
printf ("brand\n");
scanf ("%s",&brand);
printf ("price\n");
scanf ("%f",&price);
print ("---------Thank You---------");
}


เขียนโปรแกรมโดยใช้ iostream.h

#include
main ()
{
char name [20];
char number [20];
float brand [20];
char price [20];
cout <<"---------Buy Telephone---------\n";
cout <<"name:";
cin >>name;
cout <<"\nnumber:";
cin >> number;
cout << "\nbrand:";
cin >>brand;
cout <<"\nprice:";
cin >>price;
cout<< "---------Thank You---------";
}

DTS-05-22-07-2552

สรุปเนื้อหา "Data Structure"
เรื่อง Stack

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

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


การดำเนินงานของสแตก
การทำงานของสแตกจะประกอบด้วย 3 กระบวนการที่สำคัญ คือ

1. Push คือ การนำข้อมูลไปใส่ในสแตก เช่น สแตก s ต้อใส่ข้อมูล i ในสแตก จะได้ push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s
2. Pop คือ การนำข้อมูลออกมาจากส่วนบนสุดของสแตก เช่น ต้องการนำข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร i จะได้ i = pop(s)
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก

การแทนที่ข้อมูลของสแตก

การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ

1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วน คือ

1. Head Node จะประกอบไปด้วย 2 ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป

การดำเนินงานเกี่ยวกับสแตก

การดำเนินงานเกี่ยวกับสแตกได้แก่

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-04-15-07-2552

สรุปเนื้อหา "Data Structuer "
เรื่อง Linked List

ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^


โหนด (Note)



โครงสร้างแบบ Linked list แบ่งได้หลายแบบตามวิธีการชี้ไปยังโหนดต่างๆ ดังนี้

1. Singly Linked list


2. Doubly Linked list


3. Multi-Linked list

ลักษณะของ Singly Linked list
หากทราบถึงโหนดแรกของ Linked list จะสามารถเข้าถึงข้อมูลทั้งหมดใน Linked list ได้ เนื่องจากแต่ละโหนดจะมีพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป ดังนั้น Linked list ต้องมี external พอยน์เตอร์ที่ชี้ไปยังโหนดแรกของ Linked list จากรูปใช้พอยน์เตอร์ H (Head)

Linked list ประกอบไปด้วย node ซึ่งมีข้อมูลของแต่ละ node อยู่ประกอบไปด้วย ข้อมูลและตัวที่บ่งชี้ถึงโหนดต่อไป หากเป็นโหนดสุดท้ายจะมีค่าเป็น null ในภาษา java เราสามารถอ้างถึง reference ได้โดย object จึงสามารถที่จะสร้าง linked list ได้เช่นกันเหมือนกับภาษา C หรืออื่นๆ

Circular Linked list
ในปกติ Linked list เมื่อถึงโหนดสุดท้าย ค่าในฟิลด์ LINK หรือ โหนดถัดไปจะมีค่าเป็น NULL ซึ่งเราสามารถใช้ประโยชน์ได้โดยการเปลี่ยนให้ ค่า NULL ในฟิลด์ LINK เป็นตำแหน่งของโหนดแรกในลิสต์ หรือชี้ไปที่ต้นลิสต์ใหม่นั่นเอง ซึ่งเราจะเรียก Linked list แบบนี้ว่า Circular Linked listCircular Linked list ใช้ประโยชน์เมื่อต้องการให้ข้อมูลมีลักษณะเป็นวนรอบหรือลูป โดยแต่ละขั้นตอนจะมีการทำงานภายในลูป จะมีการย้ายตำแหน่งของพอยน์เตอร์ไปยังโหนดถัดไปใน Linked list ในลักษณะแบบวงกลม

Doubly Linked list

Doubly linked list ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึงสามารถทำการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไปข้างหน้า และอ่านไปทางข้างหลัง

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

DTS-03-01-07-2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Pointer , set and string

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

การประกาศชนิดของตัวเเปรพอยน์เตอร์รูปแบบจะเป็น
type *variable-name

ต้องมีระบุตัวดำเนินการ เพื่อบอกว่าตัวแปรดังกล่าวเป็นตัวแปรแบบตัวชี้โดยตัวดำเนินการที่ใช้คือ
1. เครื่องหมาย
เป็นเครื่องหมายที่ใช้เมื่อต้องการให้เอาค่าตำแหน่งที่อยู่ของตัวแปรที่เก็บไว้ในหน่วยความจำออกมาใช้
เช่น m = &count;

เป็นการนำตำแหน่งในหน่วยความจำของตัวแปร count ใส่ลงไปในตัวแปร (แบบพอยท์เตอร์)
m ซึ่งตำแหน่งที่ว่านี้เป็นตำแหน่งของตัวแปรนั้น ๆ ภายในของคอมพิวเตอร์

2. เครื่องหมาย
ซึ่งจะมีการใช้งานอยู่ 2 ลักษณะ
- ใช้ในการประกาศ parameter
เช่น void swap(int*p,int*q)
{
............................
}

- ใช้เป็น dereferencing operator จะใช้เมื่อต้องการนำค่าที่อยู่ในตำแหน่งที่ตัวแปรพอยน์เตอร์นั้นชี้อยู่ออกมาแสดง



set and string

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

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

โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character
เช่นchar a[]={'H','E','L','L','O','\0'};char a[]="hello";

เช่น "UNIVERSITY!" จะเป็นข้อมูลแบบสตริงยาว 10 อักขระ

สตริงกับอะแรย์สตริงคือ อะเรย์ของอักขระ เช่น char a[5]อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระหรือ เป็นสตริงขนาด 5 อักขระก็ได้

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

VDO ส่วนตัว

การบ้าน data structure

#include
#include
main()
{
struct car{
int day;int month;
int year;char name[20];
char last_name[20];
char brand[10];
char color[20];
float price;
}car1;

printf ("day=");
scanf ("%d",&car1.day);
printf ("month=");
scanf ("%d",&car1.month);
printf ("year=");
scanf ("%d",&car1.year);
printf ("name=");
scanf ("%s",&car1.name);
printf ("last_name=");
scanf ("%s",&car1.last_name);
printf ("brand=");
scanf ("%s",&car1.brand);
printf ("color=");
scanf ("%s",&car1.color);
printf ("price=");
scanf ("%f",&car1.price);

printf ("display data of car1\n");
printf ("Day=%d mont=%d year=%d\n",car1.day,car1.month,car1.year);
printf ("name=%s\n",car1.name);
printf ("last_name=%s\n",car1.last_name);
printf ("brand=%s\n",car1.brand);
printf ("color=%s\n",car1.color);
printf ("price=%f\n",car1.price);
}

DTS-02-24-06-2552

สรุปเนื้อหา"Data Structure"

เรื่อง อาร์เรย์(Array)

อาร์เรย์ คือ แถวหรือลำดับของข้อมูลชนิดเดียวกันที่มีจำนวนหลายตัวนำมาเก็บในตัวแปรชื่อเดียวกัน แต่ต่างกันที่บอกลำดับ ซึ่งเรียกว่าตัวห้อย(subscript)

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

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

ประเภทของอาร์เรย์แบ่งได้เป็น 2 ประเภท คือ

อาร์เรย์มิติเดียว(One dimension)

อาร์เรย์หลายมิติ(Multi dimension)

อาร์เรย์มิติเดียว(One dimension)

คือตัวเเปรอาร์เรย์ที่ใช้เก็บข้อมูลเป็นกลุ่ม มีลักษณะตำแหน่งที่ตั้งเป็นลักษณะแถวเดียว(วางตามแนวนอน) หรือคอลัมน์เดียว(วางตามแนวตั้ง)

#ชนิดของตัวแปร ชื่อของตัวแปร ขนาดของตัวแปรอาร์เรย์ เช่น int num [5]

รูปแบบการประกาศตัวแปรอาร์เรย์มิติเดียว

Data-type : ชนิดของตัวแปร

array-name : ชื่อของตัวแปร

Size : ขนาดของตัวแปรอาร์เรย์

อาร์เรย์หลายมิติ(Multi dimension)

คือ อาร์เรย์ตั้งแต่ 2 มิติเป็นต้นไป ใช้เก็บข้อมูลเป็นกลุ่มที่ข้อมูลนั้นใช้ตัวแปรชื่อเดียวกันแต่ต่างกันที่ตัวห้อย

(subscript) ซึ่งจะบอกลำดับความแตกต่างของตัวแปรว่าอยู่ในแถวใด ในคอลัมน์ที่เท่าไหร่ ลำดับใดในแถว

#ชนิดของตัวแปร ชื่อของตัวแปร ขนาดของแถว ขนาดของคอลัมม์ เช่น int num [2][3]

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

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

ประวัติส่วนตัว

ชื่อ-สกุล : นางสาวสสิพร สำราญรัตน์

Name : Miss.Sasiphon Samsansat

ชื่อเล่น : จิจ๊ะ

Nickname : Jija

รหัสนักศึกษา : 50152792015

เบอร์โทรศัพท์ : 084-6639700

วันเกิด : 29 ธันวาคม 2531

อายุ : 20 ปี

ภูมิลำเนาเดิม : ชุมพร

คติประจำใจ : ชีวิตไม่สิ้นก็ดิ้นกันไป

E-mail jijajeedz@hotmail.com

ปัจจุบันศึกษาอยู่ที่มหาวิทยาลัยราชภัฏสวนดุสิต

คณะวิทยาการจัดการ

สาขาบริหารธุรกิจ

แขนงคอมพิวเตอร์ธุรกิจ

กรุงเทพมหานคร