DTS 05-23-07-2552

สรุป โครงสร้างข้อมูล เรื่อง Linked list และ Stack


การลบข้อมูลใน Linked list
เนื่องจากขั้นตอนของการลบข้อมูลที่ header นั้นจะมีปัญหาที่ยุ่งยากกว่าเมื่อ design ด้วย oop(java)
เราสามารถที่จะแก้ปัญหานี้ได้โดยการใส่ header node ที่ว่าง ๆ ไว้ข้างหน้าของ linked list
เพื่อที่จะทำหน้าที่เป็นชี้ว่าเป็นหัวโหนดโดยที่ไม่ต้องมี pointerคอยชี้ที่ header และเมื่อเราต้องการที่จะเปลี่ยนแปลงข้อมูลใด ๆ บนหัวสามารถที่จะทำได้โดยการแทรก node เข้าไป


กระบวนงาน Search list
หน้าที่ :ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์
ผลลัพธ์ :ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล


กระบวนงาน Traverse
หน้าที่:ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูล นำเข้าลิสต ผลลัพธ์ ขึ้นกับการประมวลผล
เช่นเปลี่ยนแปลงค่าใน nodeรวมฟิลด์ในลิสต์ ,คำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น


กระบวนงาน Retrieve Node
หน้าที่ :หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์


ฟังก์ชั่น EmptyList
หน้าที่ :ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่าเป็นเท็จ ถ้าลิสต์ไม่ว่าง


ฟังก์ชั่น FullList
หน้าที่:ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูล นำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม
เป็นเท็จ ถ้าสามารถมีโหนดอื่น


ฟังก์ชั่น list count
หน้าที่ :นับจำนวนข้อมูลที่อยู่ในลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์


กระบวนงาน destroy list
หน้าที่:ทำลายลิสต์ข้อมูลนำเข้า ลิสต์ผลลัพธ์ ไม่มีลิสต์



stack
คือ โครงสร้างข้อมูลที่สำคัญและมีลักษณะเรียบง่ายซึ่งใช้แถวลำดับเป็นโครงสร้างสำหรับเก็บข้อมูลพื้นฐานได้แก่สแตก เพราะภาษาคอมพิวเตอร์ส่วนมากกำหนดชนิดแถวลำดับไว้ล่วงหน้าและการทำงานของแถวลำดับสะดวกและเรียบง่าย สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแตกหรือ หรือเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก


Popping Stack
หมายถึงการเอาข้อมูลที่อยู่บนสุดในสแตก หรือที่ชี้ด้วยท๊อปออกจากสแตก เรียกว่าการ pop ในการpop นั้นเราจะสามารถ pop ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่


Stack Top
เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก



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