vvgigg
commented
1 year ago Chapter : 5 - item : 2 - รู้จักกับ Doubly Linked List
ให้เขียนคลาสของ Doubly Linked List ซึ่งมีเมท็อดดังนี้
- init สร้าง Head ขึ้นมาเพื่อบอกว่าจุดเริ่มต้นของ Linked List คือตรงไหน
- str คืนค่าเป็นสตริงซึ่งบอกว่า Linked List เราตั้งแต่หัวไปจนท้ายมีตัวอะไรบ้าง
- reverse คืนค่าเป็นสตริงซึ่งบอกว่า Linked List เราตั้งแต่ท้ายไปจนหัวมีตัวอะไรบ้าง
- isEmpty เช็คว่า Linked List ของเราว่างหรือป่าว คืนค่าเป็น True / False
- append add Item เข้า Linked List จากด้านหลัง ไม่คืนค่า
- addHead add Item เข้า Linked List จากด้านหน้า ไม่คืนค่า
- search ค้นหา Item ที่ต้องการใน Linked List คืนค่าเป็น Found / Not Found
- index ค้นหา Item ที่ต้องการใน Linked List ว่าอยู่ที่ Index ไหน คืนค่าเป็น Index (0,1,2,3,4,.....) ถ้าหากไม่มีคืนค่าเป็น -1
- size คืนค่าเป็นขนาดของ Linked List
- pop นำ Item Index ที่ pos ออกจาก Linked List คืนค่าเป็น Success / Out of Range
- insert เป็นการนำ Item ไปแทรกใน Linked List ตามตำแหน่ง pos ไม่มีการคืนค่า
ถ้าน้องยังไม่ค่อยเข้าใจการทำงานของ insert ให้น้องลองกับ List บน Python ได้ เช่น
- มี arr = [ 0 , 1 , 2 , 3 ] แล้วเรา arr.insert(0,"T") จะได้ผลลัพธ์คือ [ "T", 0 , 1 , 2 , 3 ]
- มี arr = [ 0 , 1 , 2 , 3 ] แล้วเรา arr.insert(999,"T") จะได้ผลลัพธ์คือ [ 0 , 1 , 2 , 3 , "T" ]
- มี arr = [ 0 , 1 , 2 , 3 ] แล้วเรา arr.insert(-2,"T") จะได้ผลลัพธ์คือ [ 0 , 1 , "T" , 2 , 3 ]
- มี arr = [ 0 , 1 , 2 , 3 ] แล้วเรา arr.insert(-10,"T") จะได้ผลลัพธ์คือ [ "T", 0 , 1 , 2 , 3 ]
โดยรูปแบบ Input มีดังนี้
- append -> AP
- addHead -> AH
- search -> SE
- index -> ID
- size -> SI
- pop -> PO
- insert -> IS
โดยให้เพิ่มเติมจากส่วน #Code Here ของโปรแกรมต่อไปนี้ เพื่อให้สามารถแสดงผลได้ตามที่โจทย์กำหนด **** ห้ามใช้ List ในการทำ Linked List เด็ดขาดถ้าหากพบจะถูกลดเป็น 0 คะแนน ****
class Node: def init(self, value): self.value = value self.next = None self.previous = None
class LinkedList: def init(self): self.head = None self.tail = None
def __str__(self):
if self.isEmpty():
return "Empty"
cur, s = self.head, str(self.head.value) + " "
while cur.next != None:
s += str(cur.next.value) + " "
cur = cur.next
return s
def reverse(self):
if self.isEmpty():
return "Empty"
cur, s = self.tail, str(self.tail.value) + " "
while cur.previous != None:
s += str(cur.previous.value) + " "
cur = cur.previous
return s
def isEmpty(self):
return self.head == None
def append(self, item):
#Code Here
def addHead(self, item):
#Code Here
def insert(self, pos, item):
#Code Here
def search(self, item):
#Code Here
def index(self, item):
#Code Here
def size(self):
#Code Here
def pop(self, pos):
#Code HereL = LinkedList() inp = input('Enter Input : ').split(',') for i in inp: if i[:2] == "AP": L.append(i[3:]) elif i[:2] == "AH": L.addHead(i[3:]) elif i[:2] == "SE": print("{0} {1} in {2}".format(L.search(i[3:]), i[3:], L)) elif i[:2] == "SI": print("Linked List size = {0} : {1}".format(L.size(), L)) elif i[:2] == "ID": print("Index ({0}) = {1} : {2}".format(i[3:], L.index(i[3:]), L)) elif i[:2] == "PO": before = "{}".format(L) k = L.pop(int(i[3:])) print(("{0} | {1}-> {2}".format(k, before, L)) if k == "Success" else ("{0} | {1}".format(k, L))) elif i[:2] == "IS": data = i[3:].split() L.insert(int(data[0]), data[1]) print("Linked List :", L) print("Linked List Reverse :", L.reverse())
จงเขียนฟังก์ชั่นสำหรับการ Merge LinkList 2 ตัวเข้าด้วยกันโดยห้ามสร้าง Class LinkList จะมีแต่ Class Node ซึ่งเก็บค่า value ของตัวเองและ Node ถัดไป โดยมีฟังก์ชั่นดังนี้
Chapter : 5 - item : 1 - Locomotive-(101)
