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 และจะมีการประกาศค่าก่อนที่จะใช้งาน