- โครงสร้างข้อมูลแบบลิงค์ลิสต
- กระบวนงานและฟังกชั่นที่ใช้ดำเนินงานพื้นฐาน
- การสร้างลิงค์ลิสต
- ลิงค์ลิสต์แบบซับซ้อน
จุดประสงค์การเรียนรู้
1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบลิงค์ลิสต
2. เพื่อให้ทราบกระบวนการทำงานและฟังกชั่นที่ ใช้ดำเนินงานพื้นฐานของลิงค์ลิสต
3. เพื่อให้นักศึกษาทราบวิธีการสร้างลิงค์ลิสต
4. เพื่อให้นักศึกษาทราบการทางานของลิงค์ลิสต แบบซับซ้อน
ลิงค์ลิสต (Linked List) เป็นวิธีการเก็บ ข้อมูลอย่างต่อเนื่องของอิลิเม้นต์ต่าง ๆ โดยมีพอยเตอร์เป็นตัวเชื่อมต่อแต่ละอิลิเม้นท์ เรียกว่าโนด (Nodeซึ่งในแต่ละโนดจะประกอบไปด้วย 2 ส่วน คือ Dataจะเก็บข้อมูลของอิลิเม้นท์ และส่วนที่สอง คือ Link Field จะทำหน้าที่เก็บ ตำแหน่งของโนดต่อไปในลิสต
ในส่วนของdataอาจจะเป็นรายการเดียวหรือเป็นเรคคอร์ดก็ได้ในส่วนของ linkจะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไปใน โหนดสุดท้ายจะเก็บคา Null ซึ่งไม่ได้ชี้ไปยังตำแหน่งใด ๆ เป็นตัวบอกการ สิ้นสุดของลิสต
ในลิงค์ลิสตจะมีตัวแปรสำหรับชี้ ตำแหน่งลิสต (List pointer variable)ซึ่งเป็นที่เก็บตำแหน่งเริ่มต้นของลิสต ซึ่งก็ คือ
โหนดแรกของลิสตนั้นเอง ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหนดแรกของลิสตจะเป็น Null
โครงสร้างข้อมูลแบบลิงค์ลิสต
โครงสร้างข้อมูลแบบลิงค์ลิสตจะแบ่งเป็น 2 ส่วน คือ
1. Head Structure จะประกอบไปด้วย 3 ส่วน ได้แก่ จำนวนโหนดในลิสต (Count)พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง(Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อูมลแรกของลิสต (Head)
2. Data Node Structure จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
กระบวนงานและฟังกชั่นทใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create List
หน้าที่ สร้างลิสตว่าง
ผลลัพธ์ ลิสตว่าง
Algorithm CreateList
Pre Nothing
Post Head node allocated or error returned
Return Head node pointer or null if memory overflow
1. if (memory available)
1 allocate (Pnew)
2 pNew->head = null pointer
3 pNew->count = 0
2. else
1 pNew = null poiter
3. return pNew
End CreateList
2.กระบวนงาน Insert Nodeหน้าที่เพิ่มข้อมูลลงไปในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าลิสต ข้อมูล และตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง
Algorithm insertNode
val pPre
val dataIn
Pre pList is a pointer to a valid list head structurepPre is a pointer todata’s logical predecessordataIn contains data to be inserted
Post data have been insert in sequence
Return true if successful, false if memory overflow
Allocate (pNew)
If (memory overflow)
1 return false
pNew->data = dataIn
3. If (pPre null)
1 pNew->link = pList->head
2 pList->head = pNew
5. else
1 pNew->link = pPre->link
2 pPre->link = pNew
6. pList->count = pList->count +1
7. Return true
End insertNode
3. กระบวนงาน Delete Node หน้าที่ลบสมาชิกในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าข้อมูลและตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง
Algorithm deleteNode
val pPre
val pLoc
ref dataOut
Pre pList is a pointer to a valid list head structure
pPre is a pointer to predecessor node
pLoc is a pointer to node to be deleted
dataOut is address to pass deleted data to
calling module
Post data have been delete and return to caller
1. dataOut = pLoc->data
2. if (pPre null)
1 pList->head = pLoc->link
3. Else
1 pPre->link = pLoc->link
4. pList->count = pList->count - 1
5. Release (pLoc)
6. Return
End deleteNode
4. กระบวนงาน Search listหน้าที่ค้นหาข้อมูลในลิสตที่ต้องการข้อมูลนำเข้าลิสตผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล
Algorithm searchList (val pList
val pPre
ref pLoc
val target
Pre pList is a pointer to a valid list head structure
pPre is a pointer to receive predecessor
pLoc is a pointer to receive current node
target is the key being sought
Post pLoc points to first node with equal or greater key or null if target >
key of last node
pPre points to largest node smaller than key or null if target< ppre =" null" ploc =" pList-">head
loop (pLoc not null AND target > pLoc->data.key)
1 pPre = pLoc
2 pLoc = pLoc->link
If (pLoc null)
1 found = false
else
1 if (target equal pLoc->data.key)
1 found = true
2 else
1 found = false
Return found
Return searchList
5.กระบวนงาน Traverse หน้าที่ ท่องไปในลิสตเพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสตผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต , คำนวณค่าเฉลยของฟิลด์ เป็นต้น
Algorithm traverse
ref dataPtr
Pre pList is a pointer to a valid list head structure
fromWhere is 0 to start at the first element
dataPtr is address of a pointer to data
Post address placed in dataPtr and return true or if end of list, return
false
Return true if next element located, false if end of list
1. if (fromWhere is 0)
1 if (pList->count is zero)
1 success = false
2 else
1 pList->pos = pList->head
2 dataPtr = address (pList->pos->data)
3 success = true
2. else
1 if (pList->pos->link null)
1 success = false
2 else
1 pList->pos = pList->pos->link
2 dataPtr = address (pList->pos->data)
3 success = true
3. return success
End traverse
6.กระบวนงาน Retrieve Nodeหน้าที่ หาตำแหน่งข้อมูลจากลิสตข้อมูลนำเข้าลิสตผลลัพธ ตำแหน่งข้อมูลที่อยู่ในลิสต
Algorithm retrieveNode
ref dataOut
pList is a pointer to a valid list head structure
key is a target of data to be retrieved
dataOut contains address for retrieved data
Post data placed at location specified in dataOut or error returned if
not found
Return true if successful, false if data not found
found = searchList (pList, pPre, pLoc, key)
1 dataOut=pLoc->data
return found
End retrieveNode
7. ฟังกชั่น EmptyListหน้าที่ ทดสอบว่าลิสตว่างข้อมูลนำเข้า ลิสตผลลัพธ์เป็นจริงถ้าลิสตว่างเป็นเท็จ ถ้าลิสตไม่ว่าง
Algorithm emptyList
Pre pList is a pointer to a valid list head structure
Return true if list empty, false if list contains data
1. Return (pList->count equal to zero)
End emptyList
7. ฟังกชั่น EmptyList
หน้าที่ ทดสอบว่าลิสตว่างข้อมูลนำเข้า ลิสต
ผลลัพธ์ เป็นจริง ถ้าลิสตว่าง
เป็นเท็จ ถ้าลิสตไม่ว่าง
Algorithm emptyList
Pre pList is a pointer to a valid list head structure
Return true if list empty, false if list contains data
1. Return (pList->count equal to zero)
End emptyList
8. ฟังกชั่น FullList
หน้าที่ ทดสอบว่าลิสตเต็มหรือไม่ข้อมูลนำเข้าลิสต
ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็มเป็นเท็จ ถ้าสามารถมีโหนดอื่น
Algorithm fullList (val pList
Pre pList is a pointer to a valid list head
structure
Return false if another, true if memory full
1. allocate (pNew)
2. if (allocation successful)
1 release (pNew)
2 return false
3. return true
End fullList
9. ฟังกชั่น list count
หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสตข้อมูลนำเข้าลิสต
ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต
Algorithm listCount
Pre pList is a pointer to a valid list head structure
Return count for number of node in list
1. Return (pList->count)
End listCount
10. กระบวนงาน destroy list
หน้าที่ ข้อมูลนำเข้า ลิสต
ผลลัพธ
Algorithm destroyList
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
program buildLinkList
1. print (Welcome to exploring linked list)
2. pList=createList
3. option = menu()
4. loop (option not quit)
1 if (option add)
1 getData (dataIn)
2 addNode (pList, dataIn)
2 elseif (option delete)
1 print (Enter key of data to be delete)
2 read (deleteKey)
3 removeNode (pList,deleteKey)
3 else
1 printList (pList)
4 option=menu ()
5. destroyList (pList)
6. Print (Exploration complete)
End buildLinkedList
Algorithm menu
Pre Noting
Post Valid choice
1. print (……….Menu………)
2. print (A: Add new data)
3. print (D: Delete data)
4. print (P: Print List)
5. print (Q: Quit)
6. valid = false
7. loop (valid false)
1 print (Enter your choice: )
2 read (choice)
3 if (choice equal ‘A’ or ‘D’ or ‘P’ or ‘Q’)
1 valid=true
4 else
1 print (Invalid choice. Choices are
8. return choice
End menu
Algorithm addNode
val dataIn
Pre pList is a pointer to the head of the list
dataIn are data to be inserted into list
Post data have been inserted into list in key
sequence
1. found = searchList (pList, pPre, pLoc, dataIn.key)
2. if (found)
1 print (error : Data already in list. Not added)
3. else
1 success = insertNode (pList, pPre, dataIn)
4. if (success false)
1 print (error : Out of memory)
2 abort algorithm
5. Return
End addNode
Algorithm removeNode
val key
Pre pList is a pointer to the head of the list
key is the key to be located and deleted
Post the node has been delted or a warning message
printed if not found
found = searchList (pList, pPre, pLoc, key)
if (found)
1 deleteNode (pList, pPre, pLoc, deleteData)
else
1 print (error : Key not in list)
return
End removeNode
Algorithm printList (val pList
Pre pList is a valid linked list
Post All keys have been printed
1. if emptyList (pList))
1 print (No data in list)
2. else
1 print (***Begin Data Print ***)
2 count = 0
3 moreData = traverse (pList, count, dataPtr)
4 Loop (moreData true)
1 count=count+1
2 print (count, dataPtr->key)
3 moreData = traverse (pList,
count, dataPtr)
5 Print (*** End of Data Print ***)
3. return
End printList
Linked List แบบซับซ้อน1. Circular Linked Listเป็นลิงคลิสตที่สมาชิก ตัวสุดท้ายมีตัวชี้ (list)ชี้ไปที่สมาชิกตัวแรกของ ลิงคลิสต จะมีการทำงานไปในทิศทางเดียวเท่านั้นคือเป็นแบบวงกลม
2.Double Linked List เป็นลิงค์ลิสตที่มีทิศทางการทำงานแบบ 2 ทิศทางในลิงค์ลิสตแบบ 2ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูลก่อนหน้า (backward pointer) และต้วชี้ข้อมูลถัดไป (forward pointer)
กระบวนงาน Insert Node
Algorithm insertDbl (val pList
val dataIn
Pre pList is a pointer to a valid double linked list
dataIn contains the data to be inserted
Post The data have been inserted in sequence
Return 0 : failed-memory overflow
1 : successful
2 : failed-duplicate key presented
1. if (full list)
1 return (0)
2. found = searchList (pList, pPre, pSucc, dataIn.key)
if (found false)
1 allocate (pNew)
2 pNew->data = dataIn
3 pNew->back=pPre
4 pNew->fore=pPre->fore
5 if (pPre->fore null)
1 pList->rear=pNew
6 else
1 pSucc->back=pNew
7 pPre->fore=pNew
8 pList->count=pList->count+1
9 return (1)
4. Return (2)
End insertDbl
กระบวนงาน Delete Node
Algorithm deleteDbl
val pDlt
Pre pList is a pointer to a valid double linked list
pDlt is a pointer to the node to be deleted
Post node deleted
1. if (pDlt null)
1 abort (impossible condition in delete double) 2. pList->count=pList->count-1
3. pPred = pDlt->back
4. pSucc = pDlt->fore
. pPred->fore=pSucc
4. If (pSucc not null)
1 pSucc->back=pPred
7. Recycle (pDlt)
8. Return
End deleteDbl
แบบฝึกหัด
1. อธิบายโครงสร้างการทำงานของลิสกเชื่อมโยง
2. ท่านสามารถลบ โหนดจากลิสกที่มีการ เชื่อมโยงออกจากกันได้หรือไม่กรณีที่ใช้ตัวชี้เป็นตัวดำเนินการเชื่อมโยงอธิบายหลักการ
ดำเนินการ
3. ใหอธิบายหลักการทำงานของ Circular LinkedList
ไม่มีความคิดเห็น:
แสดงความคิดเห็น