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

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

1.มีการพัฒนาบุคลิกภาพของตนให้ดีขึ้นฝีกเช่นการให้แต่งการสุภาพเรียบเร้อย
2.รู้จักวางแผนการทำงานและการทำงานเป็นกลุ่มเช่นการทำงานโครงการ
3.มีความอดทนต่ออุปสรรคต่างๆและรู้จักการแก้ไขปัญหาเฉพาะหน้า
4.มีการเรียนรู้กระบวนการคิดอย่างเป็นระบบ ระเบียบมากขึ้นและได้เรียนรู้งานจากการทำงานจริง
5.สามารถนำความรู้ที่ได้เรียนมาไปประยุกต์ใช้ในชีวิตประจำวัน และการทำงานและได้พัฒนาประสิทธิภาพของตัวเองให้ดีขึ้นและ
6.ทำให้รู้จักตนเองมากขึ้น

DTS 10/09-09-2552

Sorting

การเก็บข้อมูลเราก็ต้องจัดเก็บให้เป็นระเบียบ และง่ายในกระบวนการค้นหาข้อมูลเพื่อนำมาใช้ใหม่เช่นการจัดเรียงหมวดหมู่ของหนังสือในห้องสมุด ต้องมีการจัดการกับรายละเอียดของหนังสือต่างๆ ให้เป็นแฟ้มข้อมูลที่เรียงลำดับตามตัวอักษร เป็นต้น และในการประกอบการต่างๆ ที่เกี่ยวข้องกับการใช้งานด้านคอมพิวเตอร์ ก็มีการจัดเรียงลำดับของข้อมูล โดยวิธีใดวิธีหนึ่งแล้วแต่กำหนดทำไมเราจึงต้องศึกษาการเรียงลำดับข้อมูล (Sorting) เพื่อช่วยในการออกแบบอัลกอรึทึม ? เพราะการเรียงลำดับข้อมูล เป็นงานพื้นฐานที่ใช้ในโปรแกรมประยุกต์ต่างๆ ช่วยทำให้การเรียกใช้งานข้อมูลนั้นๆ มีความสะดวก รวดเร็ว ในการค้นหา มากกว่าการเรียกใช้ข้อมูลที่ไม่มีการลำดับ และทำให้เกิดเทคนิคใหม่ๆที่น่าสนใจและสำคัญอันได้แก่ partial order , recursion , merge , lists , การจัดเก็บ binary tree ในอาร์เรย์ เป็นต้น


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

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


Sorting Algorithms

Bubble Sortหลักของการเรียงแบบนี้คือ จะเปรียบเทียบและแลกเปลี่ยนข้อมูล 2 ค่าที่อยู่ติดกันในลักษณะที่เรากำหนด เช่น จากน้อยไปหามากหรือมากไปหาน้อย
Quick Sortการเรียงลำดับในลักษณะนี้ เป็นการปรับปรุงมาจากการเรียงลำดับแบบ Bubble เพื่อให้การเรียงลำดับเร็วขึ้น วีธีนี้เหมาะกับการเรียงข้อมูลที่มีจำนวนมาก หรือมีขนาดใหญ่ และเป็นวิธีการเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาน้อยที่สุด
Insertion SortInsertion Sort การเรียงลำดับที่ง่ายไม่ซับซ้อน เป็นการนำข้อมูลใหม่เพิ่มเข้าไปในชุดข้อมูลที่มีการเรียงลำดับอยู่แล้ว โดยข้อมูลใหม่ที่นำเข้ามาจะแทรกอยู่ในตำแหน่งทางขวาของชุดข้อมูลเดิม และยังคงทำให้ข้อมูลทั้งหมดมีการเรียงลำดับ

DTS 09/02-09-2552

กราฟ (Graph)
เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงาน
ที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน
นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์ (Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges) กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด
ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Graphs)
และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟนั้นว่า กราฟแบบมีทิศทาง
(Directed Graphs)บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถ
เขียนชื่อเอ็จกำกับไว้ก็ได้
การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ ระหว่างโหนดไม่มีรูปแบบที่ตายตัวการลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนดได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใด ๆ สามารถวนเข้าหาตัวมันเองได้
โดยทั่ว ๆ ไปการเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes) หรือวงกลม (circles)ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้นหรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนดถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้อง
มีหัวลูกศรกำกับทิศทางของความสัมพันธ์ด้วย
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนด
หรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node) หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
การแทนกราฟในหน่วยความจำ
ในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการจัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมา
การแทนกราฟในหน่วยความจำด้วยวิธีเก็บเอ็จทั้งหมดใน แถวลำดับ 2 มิติ จะค่อนข้างเปลืองเนื้อที่ เนื่องจากมีบางเอ็จที่เก็บซ้ำอาจหลีกเลี่ยงปัญหานี้ได้โดยใช้แถวลำดับ 2 มิติเก็บโหนดและ พอยเตอร์ชี้ไปยงตำแหน่งของโหนดต่าง ๆ ที่สัมพันธ์ด้วย และใช้ แถวลำดับ 1 มิติเก็บโหนดต่าง ๆ ที่มีความสัมพันธ์กับโหนด
ในแถวลำดับ 2 มิติที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
การจัดเก็บกราฟด้วยวิธีเก็บโหนดและพอยน์เตอร์นี้ยุ่งยาก ในการจัดการเพิ่มขึ้นเนื่องจากต้องเก็บโหนด
และพอยน์เตอร์ในแถวลำดับ 2 มิติ และต้องจัดเก็บโหนดที่สัมพันธ์ด้วยในแถวลำดับ 1 มิติ อย่างไรก็ตามทั้งสองวิธีไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลง ตลอดเวลา ควรใช้ในกราฟที่ไม่มีการเปลี่ยนแปลงตลอดการใช้งานเพราะถ้ามีการเปลี่ยนแปลงส่วนใดส่วนหนึ่งของกราฟจะกระทบกับส่วนอื่น ๆ ที่อยู่ในระดับที่ต่ำกว่าด้วยเสมอ
กราฟที่มีการเปลี่ยนแปลงตลอดเวลาอาจจะใช้วิธีแอดจาเซนซีลิสต์ (Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธีจัดเก็บกราฟด้วยการเก็บโหนดและพอยน์เตอร์ แต่ต่างกันตรงที่ จะใช้ ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียวแต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal) วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
2. การท่องแบบลึก (Depth First Traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดย
กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น
ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน
โหนดอื่น ๆ ต่อไปจนครบทุกโหนด

DTS 08/26-08-2552

ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship)
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือ เซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน
3. ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน
โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละ
โหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึง จำนวนทรีย่อยของโหนด นั้น ๆ
6. ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1 และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลักจะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ จำนวน ลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูก การแทนที่ทรี ซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน ทำให้ยากต่อการปฏิบัติการ วิธีการแทนที่ที่ง่ายที่สุด คือ ทำให้แต่ละโหนดมี จำนวนลิงค์ฟิลด์เท่ากัน โดยอาจใช้วิธีการต่อไปนี้
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด การแทนที่ทรีด้วยวิธีนี้ จะให้จำนวนฟิลด์ใน
แต่ละโหนดเท่ากันโดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูกของโหนดที่มีลูกมากที่สุด โหนดใดไม่มีโหลดลูกก็ให้ค่าพอยเตอร์ในลิงค์ฟิลด์นั้นมีค่าเป็น Null และให้ลิงค์ฟิลด์แรกเก็บค่าพอยเตอร์ชี้ไปยังโหนด ลูกลำดับที่หนึ่ง ลิงค์ฟิลด์ที่สองเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูกลำดับที่สอง และลิงค์ฟิลด์อื่นเก็บ
ค่าพายเตอร์ของโหนดลูกลำดับ ถัดไปเรื่อย ๆ
การแทนทรีด้วยโหนดขนาดเท่ากันค่อนข้างใช้เนื้อที่จำนวนมาก เนื่องจากแต่ละโหนดมีจำนวนโหนดลูกไม่เท่ากันหรือบางโหนดไม่มีโหนดลูกเลยถ้าเป็นทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่างกันมาก จะเป็นการสิ้นเปลืองเนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
2. แทนทรีด้วยไบนารีทรี
เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือกำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้นโดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
-ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
-ลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไปโหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ในลิงค์ฟิลด์มีค่าเป็น Null
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลง ดังต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบ
ความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆ โหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N) ทรีย่อยทางซ้าย (แทนด้วย L)หรือทรีย่อยทางขวา (แทนด้วย R)
มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ
NLR LNR LRN NRL RNL และ RLN
วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN
1. การท่องไปแบบพรีออร์เดอร์ (Preorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี
NLR
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR
3. การท่องไปแบบโพสออร์เดอร์ (Postorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LRN
เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ (Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรือ อาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression) นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้
- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree) เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของ
โหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน ปฏิบัติการในไบนารีเซิร์ชทรี ปฏิบัติการ
เพิ่มโหนดเข้าหรือดึงโหนดออกจากไบนารีเซิร์ชทรีค่อนข้างยุ่งยากกว่าปฏิบัติการในโครงสร้างอื่น ๆ เนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้วต้องคำนึงถึงความเป็นไบนารีเซิร์ชทรีของทรีนั้นด้วยซึ่งมีปฏิบัติการดังต่อไปนี้
(1) การเพิ่มโหนดในไบนารีเซิร์ชทรี
(2) การดึงโหนดในไบนารีเซิร์ชทรี
วิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้
ก. กรณีโหนดที่จะดึงออกเป็นโหนดใบการดึงโหนดใบออกในกรณีนี้ทำได้ง่ายที่สุดโดยการดึงโหนดนั้นออกได้ทันที เนื่องจากไม่กระทบกับโหนดอื่นมากนัก วิธีการก็คือให้ค่าในลิงค์ฟิลด์ของโหนดแม่ซึ่งเก็บที่อยู่
ของโหนดที่ต้องการดึงออกให้มีค่าเป็น Null
ข. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง วิธีการดึง
โหนดนี้ออกสามารถใช้วิธีการเดียวกับการดึงโหนดออกจากลิงค์ลิสต์ โดยให้โหนดแม่ของโหนดที่จะดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวาต้องเลือกโหนดมาแทนโหนดที่ถูกดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือทรีย่อยทางขวาก็ได้
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น

DTS 07/05-07-2552

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

DTS 06/29-07-2552

Stack เป็นโครางสร้งข้อมูลที่มีข้อมูลแบบลิเนียร์ลิสต์ที่มีคุณสมบัติ การเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ปลายข้างเดียวเรียกว่าtop ของสแตก และสแตกสามารถทำได้2แบบคือ
1.การแทนข้อมูลแบบลิงค์ลิสต์
2.การแทนข้อมูลของสแตกแบบอะเรย์
การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์รูปแบบนิพจน์ทางคณิตศาสตร์• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+

การคำนวณนิพจน์ทางคณิตศาสตร์ จะสามารถทำได้ 3 วิธี
1.นิพจย์ Infin
2.นิพจย์postfix
3.นิพจย์prefix

DTS 05/22-07-2552

Linked List จะมีคำสั่งในกระบวนการทำงานของแต่ะคำสั่งที่แต่ต่างกันไป เช่น กระบวนการการทำงานแบบ Traverse มีหน้าที่คือการท่องไปในลิสต์และจะทำการประมวลข้อมูล ผลลัพธ์ที่ได้ขึ้นอยู่กับการประมวลผล เช่นการแปลงค่าใน node การคำนวณค่าเฉลี่ยของฟิลด์ และยังมีฟังก์ชัน EmptyList เพื่อทดสอบว่าลิสต์ว่างหรือไม่ กระบวนการทำงาน Retrieve Node ใช้หาตำแหน่งในลิสต์การทำงานของLinked List คือกระบวนการ Destroy list คือการหยุดการทำงานของลิสต์Linked List แบบซ้อนเป็นลิงค์ลิสต์สมาชิกตัวสุดท้ายที่ชี้ไปที่สมาชิกตัวแรกของลิงค์ลิสต์จะเป็นการทำงานแบบวงกลม
เรื่อง"Stack"
เป้นโครงสร้างข้อมูลแบบลิเนียนลิสต์ ลักษณะที่สำคัญของสแตกคือข้อมูลที่ถูกใส่หลังสุดจะถูกนำออกมาแสดงก่อนข้อมูลที่เข้าไปก่อน เรียกขั้นตอนนีว่า LOFO ( Last in First Out ) จะมีการทำงานอยู่ 3 ขั้นตอน
1.การใส่ข้อมูลลงในสแตกหรือ Push
2.การนำข้อมูลออกจากส่วนบนสุดของสแตกหรือ Pop เมื่อนำข้อมูลออกจากสแตกแล้วจะเกิดภาวะสแตกว่าง stack empty และถ้าไม่มีข้อมูลอยู่ในสแตก
3.การคัดลอกข้อมูลที่อยู่บนสุดของสแตกไว้แต่ไม่ได้เป็นกการนำข้อมูลออกจากสแตก


ประวัติ นักศึกษา แบบ stdio.h and iostream.h

แบบ stdio.h

#include
struct student
{
char name[45];
char lastname[45];
int id;
}data;
void main()
{
printf("student data\n");
printf("name:");
scanf("%s",&data.name);
printf("lastname:");
scanf("%s",&data.lastname);
printf("id:");
scanf("%d",&data.id);
{
printf("\n\n\nDisplay data of studen\n");
printf("name:%s\n",data.name);
printf("lastname:%s\n",data.lastname);
printf("id:%d\n",data.id);
}
}

แบบ iostream.h

#include
struct student
{
char name[45];
char lastname[45];
int id;
}data;
void main()
{
printf("student data\n");
printf("name:");
scanf("%s",&data.name);
printf("lastname:");
scanf("%s",&data.lastname);
printf("id:");
scanf("%d",&data.id);
{
printf("\n\n\n\nDisplay data of studen\n");
printf("name:%s\n",data.name);
printf("lastname:%s\n",data.lastname);
printf("id:%d\n",data.id);
}
}



จงยกตัวอย่าง Stack ที่ใช้ในชีวิตประจำวันของนักศึกษา

Print

1.ใส่กระดาษ
2.สั่งพิมพ์
3.กระดาษออก

ลูกชิ้นปิ้ง

1เสี่บลูกชิ้นลุกที่1-4
2ปิ้ง
3กินลูกที่4321ตามลำดับ

ลูกชิ้นที่บนจะเป็นลูกสุดท้ายที่เสี่บเป็นลูกที่4
ลูกที่อยู่ด้านล้างเป็นลูกแรกจะเป็นลูกที่1

DTS 04/15-07-2552

สรุปเรื่อง set and string
ตอนท้าย ได้รูว่าอะเรย์ของสตริงมีจำนวนมาก ก็ทำให้ทำให้เป็นอะเรย์ของสตริงเพื่อจะได้เขียนโปรแกรมได้สะดวก และอะเรย์ของสตริงที่ยาวไม่เท่ากันทำได้ก็ต่อเมื่อกำหนดค่าเริ่มต้นเท่านั้นอะเรย์ที่ยาวเท่ากันจะถือว่าเป็นอะเรย์ที่แท้จริงสามาตรได้ทั้งเมื่อกำหนกเป็นตัวแปรจะแตกต่างจากความยาวไม่เท่ากันคือแบบความยาวไม่เท่ากันจะเติมท้ายด้วยnull characterให้เพียงตัวเดียว แบบความยาวเท่ากันจะเติมครบทุกช่อง การกำหนดการเกี่ยวกับสตริงคือ ฟังก์ชั่นstrlen(str)ให้หาความยาวของสตริง ฟังก์ชั่นstrcpy(str1,str2) ให้คัดลอกข้อมูลจากอันหนึ่งไปยังอีกอันหนึ่ง
เรื่อง Linked List ได้รู้ถึงการสร้างลิงค์ลิสต์ และการทำงานของลิงค์ลิสต์ว่าทำงานแบไหนและข้อมูลของอิลิเมนต์โดยมีพอยเตอร์เป็นตัวเชื่อมแต่ละอิลิเมนท์เรียกว่าNodeแบ่งได้เป็น2ส่วนคือData จะเก็บข้อมูลของอิลิเมนท์ และLink Field จะทำหน้าที่เก็บตำแหน่งของโนดต่อไปในลิสต์
โครงสร้างขอ้มูลแบบลิงค์ลิสต์จะแบ่งออเป็น2ส่วนคือ
1.Head Structure มี3ส่วน
-จำนวนโนดในลิสต์ Count
-พอยเตอร์ที่ที่ชี้ไปยังโนดเพื่อเข้าถึง Pos
-พอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์ Head
2.Data Node Stucture จะประกอบด้วยข้อมูล Data และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
กระบวนงานและฟังก์ชั่นที่ใช้ในการดำเนินงานพื้นฐานมีดังนี้
1.กระบวนงาน Create List
2.กระบวนงาน Insert Node
3.กระบวนงาน Delete Node
4.กระบวนงาน Search list

DTS 03/01-07-2552

Pointer

ตัวแปร pointer เป็นตัวแปรที่ทำหน้าที่เก็บตำแหน่งที่อยู่ของตัวแปร สามารถอ้างอิงกลับไปกลับมาได้ มีขนาด 2 ไบต์เท่ากันหมด ไม่ว่าจะเป็น char,int,floatหรืออื่นๆ

ในการประกาศตัวแปร pointer จะต้องนำหน้าด้วยเครื่องหมาย * เช่น int*x // เป็นตัวแปร pointer

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

** ในกรณีที่ตัวแปรใดมีเครื่องหมาย & นำหน้าจะไม่สามารถนำมาคำนวณได้

ตัวอย่าง
int *ptr,count // เป็นการประกาศตัวแปร ptr เป็นตัวแปร pointer และประกาศตัวแปร count
count = 100 // เป็นการกำหนดค่าให้กับ count มีค่าเท่ากับ 100
ptr = &count // เป็นการกำหนดค่าให้กับ ptr มีค่าเท่ากับตำแหน่งที่อยู่ของ count

String

string หมายถึงอักขระที่มีความยาวมากกว่า 1 ตัวแรงต่อกันเป็นข้อความ โดยข้อมูลชนิดขด้อความต้องเขียนอยู่ภายในเครื่องหมาย " " (Double quote)
หรือพูดง่าย ๆ ก็คือ String เป็น Array ของ อักขระนั่นเอง ตัวอย่างเช่น
char name[20];
หมายถึง string ที่เก็บข้อความได้ 19 ตัวอักษร ตามปกติแล้วจุดสิ้นสุดของ string จะเป็น \0
มีฟังก์ชั่นที่เกี่ยวข้องกับ String ดังนี้
getchar(); // ใช้สำหรับรับข้อมูลชนิดอักขระเข้ามาจากคีย์บอร์ด โดยรับครั้งละ 1 อักขระเท่านั้น
gets(); // จะใช้รับข้อมูลชนิดข้อความเข้ามาทางคีย์บอร์ด
putchar(); // คือการแสดงผลอักขระออกทางหน้าจอ
puts(); // ใช้ในการแสดงข้อความออกจากหน้าจอ

(set)

เป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย

แบบฝึกหัด

1.ให้นักศึกษากำหนดค่าของArray1มิติ และ Array2มิติ

ตอบ arrray1มิติ int num[10]={2,4,6,8,10,12,14,16,18,20};
arrray2มิติint a[2][3] = {{1,2,3},{4,5,6}}

2.ให้นักศึกษาหาค่าของ A[2], A[6] จากค่า A={2,8,16,24,9,7,3,8}

ตอบ A[2], A[6] = 16,3

3.จากค่าของ int a[2][3] = {{6,5,4},{3,2,1}};ให้นักศึกษา หาค่าของ a[1][0] และ a[0][2]

ตอบ a[1][0] = 3- a[0][2] = 4

4.ให้นักศึกษากำหนด Structure ที่มีค่าของข้อมูลอย่างน้อย 6 Records

ตอบ #include "stdio.h"
struct time
{
int day
;int month
;int year;
};
struct Account
{
char id[20];
char acct_type[30];
char acct_name[30];
char name[30];
float balance;
struct time date;
}details;
void input_data()
{
printf("Savings Bank\n");
printf("id = ");
scanf("%s",&details.id);
printf("Bank_Name : ");
scanf("%s",&details.acct_name);
printf("Name : ");
scanf("%s",&details.name);
printf("Balance : ");
scanf("%f",&details.balance);
printf("Day-Month-Year : ");
scanf("%d-%d-%d",&details.date.day,&details.date.month,&details.date.year);
}
void show_data()
{
printf("Information Account\n");
printf("Your ID : %s\n",details.id);
printf("Your Bank_Name : %s\n",details.acct_name);
printf("Your Name : %s\n",details.name);
printf("Your Balance : %f\n",details.balance);
printf("Date : %d-%d-%d",details.date.day,details.date.month,details.date.year);
}
main()
{
input_data();
show_data();
return(0);
}

5.ให้นักศึกษาบอกความแตกต่างของการกำหนดตัวแปรชนิด Array กับตัวแปร Pointer ในสภาพของการกำหนดที่อยู่ของข้อมูล

ตอบ การกำหนดที่อยู่ของ array จะเป็นการกำหนดแบบแยกประเภท เช่น int, char, float จะไม่รวมอยู่ด้วยกันการกำหนดที่อยู่ของ pointer จะเป็นการใส่ข้อมูลลงไปใน address และจะมีการประกาศค่าก่อนที่จะใช้งาน

Structure

#include"stdio.h"
struct student
{
char name[60];
char lastname[60];
int id;
int age;
char address [80];
int day;
int month;
int year;
}date;
void main()
{
printf("student data\n");
printf(" name:");
scanf("%s",&date.name);
printf(" lastname:");
scanf("%s",&date.lastname);
printf(" id:");
scanf("%d",&date.id);
printf(" age:");
scanf("%d",&date.age);
printf(" address:");
scanf("%s",&date.address);
printf("date is (dd/mm/yy): ");
scanf("%d/%d/%d",&date.day,&date.month,&date.year);
{
printf("Display Data of student \n");
printf("Name : %s\n",date.name);
printf("Lastname : %s\n",date.lastname);
printf("ID : %d\n",date.id);
printf("Age : % d\n",date.age);
printf("address : %s\n",date.address);
printf("birthday : %d/%d/%d \n",date.day,date.month,date.year);
}
}

DTS 02/24-06-2552

สรุปบทเรียน อะเรย์และเรคคอร์ด

อาร์เรย์ คือ กลุ่มตัวแปรชนิดเดียวกันที่ใช้ชื่อเดียวกัน อาร์เรย์จะมีตัวห้อยหรือ subscript เป็นตัวระบุจำนวนสมาชิก อาร์เรย์จะแบ่งออกเป็น
1.อาร์เรย์มิติเดียว คือจะเก็บข้อมูลในแถวเดียวไม่ว่าจะเป็นแนวนอน หรือ แนวตั้ง รูปแบบของอาร์เรย์มิติเดียว
= ชนิดของตัวแปร ชื่อของตัวแปร ขนาดของตัวแปรอาร์เรย์ เช่น int num [5]

2.อาร์เรย์หลายมิติ จะมี 2 มิติ หรือ 3 มิติ จะแตกต่างจากอาร์เรย์มิติเดียวตรงที่ตัวห้อย คือ ตัวห้อยของอาร์เรย์จะมีขนาดของแถวและขนาดของคอลัมม์มาเป็นตัวบอกจำนวนสมาชิกด้วย รูปแบบของอาร์เรย์มิติหลายมิติ
= ชนิดของตัวแปร ชื่อของตัวแปร ขนาดของแถว ขนาดของคอลัมม์ เช่น int num [2][3]
* กรณีถ้ามีการกำหนดค่าให้กับตัวแปรชนิด character ขนาดของอาร์เรย์ก็จะมีขนาดเพิ่มขึ้นจากเดิมมาหนึ่งค่า เพื่อเก็บ "\0" จะทำหน้าที่บอกการสิ้นสุดของสายอักษร

Structure
คือ โครงสร้างข้อมูลที่มีประเภทข้อมูลแตกต่างชนิดกันได้ สมาชิกอาจเป็น จำนวนเต็ม ทศนิยม พอยเตอร์ ก็ได้
เมื่อต้องการอ้างถึงตัวแปรในโครงสร้างของ structure จะใช้ . มาเป็นตัวอ้าง เช่น personal.name

DTS 01/24-06-2552

1. ความหมายของโครงสร้างข้อมูล

ข้อมูล (Data) คือ ข้อเท็จจริงต่าง ๆ ซึ่งอาจจะเป็นตัวเลขหรือไม่เป็นตัวเลขก็ได้
โครงสร้าง (Structure) คือ ความสัมพันธ์ของสมาชิกในกลุ่ม


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


2. ประเภทของโครงสร้างข้อมูล

โครงสร้างข้อมูลในภาษาคอมพิวเตอร์ที่ใช้กัน
อยู่ในปัจจุบัน แบ่งออกเป็น 2 ประเภท คือ
1. โครงสร้างข้อมูลทางกายภาพ
(Physical Data Structure)
2. ประเภทของโครงสร้างข้อมูล
2. โครงสร้างข้อมูลทางตรรกะ


2.1 โครงสร้างข้อมูลทางกายภาพ
เป็นโครงสร้างข้อมูลที่ใช้โดยทั่วไปในภาษาคอมพิวเตอร์
แบ่งออกเป็น 2 ประเภทตามลักษณะข้อมูล คือ
(Logical Data Structure)



1. ข้อมูลเบื้องต้น (Primitive Data Types)
ได้แก่ จำนวนเต็ม (Integer) จำนวนจริง
(Real) และตัวอักขระ (Character

2. ข้อมูลโครงสร้าง (Structured Data Types)
ได้แก่ แถวลำดับ (Array) ระเบียนข้อมูล
(Record) และ แฟ้มข้อมูล (File)


2.2 โครงสร้างข้อมูลทางตรรกะ
เป็นโครงสร้างข้อมูลที่เกิดจากการจินตนาการของผู้ใช้
เพื่อใช้ในการแก้ปัญหาในโปรแกรมที่สร้างขึ้น
แบ่งเป็น 2 ประเภท คือ
1. โครงสร้างข้อมูลแบบเชิงเส้น (Linear Data Structures)
ความสัมพันธ์ของข้อมูลจะเรียงต่อเนื่องกัน เช่น ลิสต์ (List)
สแตก (Stack) คิว (Queue) สตริง (String) เป็นต้น


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


3. การแทนที่ข้อมูลในหน่วยความจำหลัก
ในการเขียนโปรแกรมคอมพิวเตอร์ จะมีการแทนที่
ข้อมูลในหน่วยความจำหลักอยู่ 2 วิธี คือ
1. การแทนที่ข้อมูลแบบ สแตติก
(Static Memory Representation)
2. การแทนที่ข้อมูลแบบไดนามิก
(Dynamic Memory Representation)

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

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


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


4. ขั้นตอนวิธี (Algorithm)
เป็นวิธีการแก้ปัญหาต่างๆ อย่างมีระบบ
มีลำดับขั้นตอนตั้งแต่ต้นจนกระทั่งได้ผล
ลัพธ์ สามารถเขียนได้หลายแบบ การ
เลือกใช้ต้องเลือกใช้ขั้นตอนวิธีที่
เหมาะสม กระชับและรัดกุม

ประวิติ

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

ชื่อ นายชายธวัช มีสุข (ชายน้อย)

MR.CHAITAWAT MEESUK (CHAINOI)

รหัส50152792077

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

Facult of Management Science Curriculum Business computer

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

Suan Dusit Rajabhat University

e-mail : jaochainoi_meesukjung1122@hotmail.com

jaochainoi_businesscomputre50@hotmail.com

Tel : 084-339-3393

DTS -01-/24/06/2552