เรื่อง Linked List และ เรื่อง Stack
กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน(ต่อจากสัปดาห์ที่แล้ว)
-กระบวนงาน Traverse
หน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์
ผลลัพธ์ ขึ้นกับการประมวลผล เช่นเปลี่ยนแปลงค่าในnode,รวมฟิลด์ในลิสต์
-กระบวนงาน Retrieve Node
หน้าที่ หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์
ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์
-ฟังก์ชั่น EmptyList
หน้าที่ ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์
ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่างเป็นเท็จ ถ้าลิสต์ไม่ว่าง
-ฟังก์ชั่น FullList
หน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์
ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็มเป็นเท็จ ถ้าสามารถมีโหนดอื่น
-ฟังก์ชั่น list count
หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ข้อมูลนำเข้าลิสต์
ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
-กระบวนงาน destroy list
หน้าที่ ทำลายลิสต์
ข้อมูลนำเข้า ลิสต์
ผลลัพธ์ ไม่มีลิสต์
Exam.
Algorithm destroyList (ref pList )
Pre pList is a pointer to a valid list head structure
Post All data and head structure deleted
Return null head pointer
1. Loop (pList->count not zero)
1 dltPtr = pList->head
2 pList->head = dltPtr->link
3 pList->count = pList->count-1
4 release (dltPrt)
2. release (pList)
3. Return null pointer
End destroyList
Linked List แบบซับซ้อน
1. Circular Linked List เป็นลิงค์ลิสต์ที่สมาชิกตัวสุดท้ายมีตัวชี้ (list) ชี้ไปที่สมาชิกตัวแรกของลิงค์ลิสต์ จะมีการทำงานไปในทิศทางเดียวเท่านั้นคือเป็นแบบวงกลม
2. Double Linked List เป็นลิงค์ลิสต์ที่มีทิศทางการทำงานแบบ 2 ทิศทางในลิงค์ลิสต์แบบ 2ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูลก่อนหน้า (backward pointer)และตัวชี้ข้อมูลถัดไป(forward pointer)
เรื่อง 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) แต่ถ้าไม่มีสมาชิกในสแตกแล้วทำการ popสแตกจะทำให้เกิดความผิดพลาดที่เรียกว่า Stack Underflow
3.Stack Topเป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก
ไม่มีความคิดเห็น:
แสดงความคิดเห็น