สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Linked List และ Stack
Linked List (ต่อ)
Search list จะทำหน้าที่ค้นหาข้อมูลในลิสต์ตามที่ต้องการ
Traverse การท่องเข้าไปในลิสต์ คือ การท่องไปในทุกโหนดของลิงค์ลิสต์ เข้าถึงโครงสร้างทีละโครงสร้างที่อยู่ในลิสต์นั้น
**สมมติว่ามีลิงค์ลิสต์ H อยู่แล้ว ถ้าจะหาว่า X อยู่ในลิสต์นี้หรือไม่ เราจะสามารถรู้ได้โดยการค้นหาแบบลำดับ (sequential search) ตามลำดับ
Retrieve Node คือ การหาตำแหน่งข้อมูลในลิสต์ ว่าข้อมูลที่ต้องการนั้นอยู่ตำแหน่งที่เท่าไหร่ในลิสต์นั้น
EmptyList คือ ลิงค์ลิสต์ที่ไม่มี node อยุ่ภายใน หรือเป็นการทดสอบว่าลิสต์ว่างหรือไม่
List count คือ การนับจำนวนข้อมูลที่มีอยู่ในลิสต์ทั้งหมด ซึ่งสามารถดูค่าของจำนวนข้อมูลได้จาก Count
Destroy list คือ การทำลายลิสต์ทิ้ง โดยการลบข้อมูลในลิสต์ออกจนหมด
Linked List แบบซับซ้อน
1.Circular Linked Listหมายถึง ลิงค์ลิสต์ที่โหนดสุดท้ายสามารถวกกลับมาที่โหนดแรกได้
ใช้ประโยชน์เมื่อต้องการให้ข้อมูลมีลักษณะเป็นวนรอบหรือลูป โดยแต่ละขั้นตอนการทำงานภายในลูป จะมีการย้ายตำแหน่งของพอยน์เตอร์ไปยังโหนดถัดไป
2.Double Linked List หมายถึง ลิงค์ลิสต์ที่ทุกโหนดสามารถวกกลับมาที่โหนดก่อนหน้าของตนเองได้ ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึงสามารถทำการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไปข้างหน้า และอ่านไปทางข้างหลัง
Stack
สแตกเป็นลิเนียร์ลิสต์ที่มีคุณสมบัติที่ว่าเมื่อทำการเพิ่มข้อมูล หรือลบข้อมูลในสแตกจะกระทำที่ ปลายข้างเดียวกัน ปลายข้างนั้นเรียกว่า ท๊อปของสแตก (TOP OF STACK) ซึ่งมีคุณสมบัติเป็น ไลโฟลิสต์ (LIFO List) หรือพูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ทีหลังสุดจะ ออกลิสต์ก่อน ตัวอย่างของสแตกที่เห็นง่าย ๆ และมักจะถูกอ้างเป็นตัวอย่างบ่อยครั้งที่สุด คือจาน ที่ตั้งซ้อนกัน เมื่อจะใช้จานก็ต้องหยิบจากใบบนสุด และถ้าจะนำจานมาไว้ก็ต้องวางทับไว้บนสุด เช่นกัน
การดำเนินงานพื้นฐานของสแตก ประกอบด้วยกระบวนการ 3 กระบวนการ
1.Push การนำข้อมูลใส่ลงไปในสแตก ซึ่งโดยปกติก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ในสแตกก่อน ว่ามีที่เหลือว่างให้เก็บข้อมูลได้อีกหรือไม่ การเพิ่มข้อมูลในสแตก สามารถทำได้โดยให้ทับบนข้อมูลสุดท้ายในสแตก และจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าสแตกจะเต็มถ้าสแตกเต็มหรือ(Stack Overflow) จะไม่สามารถเพิ่มข้อมูลลงไปได้อีก
2.Pop การเอาข้อมูลที่อยู่บนสุดในสแตกออก ในการpop นั้นเราจะสามารถ pop ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่
**กรณีที่ในสแตกไม่มีข้อมูลอยู่จะทำให้เกิดข้อผิดพลาด เรียกว่า (Stack Underflow) หรือสแตกจม
3.Stack Top เป็นการคัดลอกข้อมูลในสแตก แต่ข้อมูลที่ถูกคัดลอกนั้นไม่ได้ถูกลบออกจากสแตก
**ตัวอย่างของสแตก = การว่างเก้าอี้ซ่อนกัน คือ เก้าอี้ตัวแรกจะถูกว่างไว้ข้างล่างสุดเมื่อต้องการใช้ก็ต้องดึงตัวที่อยู่บนสุดก่อนแล้วจึงจะใช้ตัวแรกที่ว่างอยู่ข้างล่างได้
การวางเหรียญซ่อนกัน คือ การวางเหรียญนั้นเหรียญแรกจะวางอยู่ล่างสุดแล้วเรียงต่อไปเรื่อยๆ การยิบเหรียญลงมาจึงต้องหยิบจากเหรียญบนสุดก่อนถึงจะหยิบเหรียญแรกได้
ไม่มีความคิดเห็น:
แสดงความคิดเห็น