|
羅德興老師的教學歷程檔案 - 112-2 資料結構 (2024年) - Unit 6 鏈結串列 (Linked Lisk) |
|
|
|
|
Unit 6 鏈結串列 (Linked Lisk)Unit 6 鏈結串列 (Linked Lisk) 1.  2.  想想如何在鏈結串列中加入新節點  範例 6-1一、Single Linked List [download]# This is list0.py by 0000000XXX (學號) YYYYYY(姓名) on 2020/05/15 # This is 展示 linked list (連結串列)的實作 # 程式的前兩行務必註明：學號、姓名、題號、及用途 class ListNode: def __init__(self, data): # initialize this object # store data self.data = data # store the reference (next item) self.next = None return def has_value(self, value): # method to compare the value with the node data if self.data == value: return True else: return False class SingleLinkedList: def __init__(self): # initialize this object self.head = None self.tail = None return def add_list_item(self, item): # make sure item is a proper node if not isinstance(item, ListNode): item = ListNode(item) if self.head is None: self.head = item else: self.tail.next = item self.tail = item return def list_length(self): #returns the number of list items count = 0 current_node = self.head while current_node is not None: count = count + 1 # jump to the linked node current_node = current_node.next return count def output_list(self): # outputs the list (the value of the node, actually) current_node = self.head results = [] while current_node is not None: results.append(current_node.data) # jump to the linked node current_node = current_node.next print(results) return def remove_value(self, value): #remove the first item in the list with this value previous_node = None current_node = self.head while current_node is not None: if current_node.data == value: previous_node.next = current_node.next return previous_node = current_node current_node = current_node.next return import datetime # 引入時間日期模組 today = datetime.date.today() print ("Hello, 現在是", today) print ("我是 學號 0000000XXX YYYYYY(姓名) 在學習 data structure- linked list 實作 \n\n") node1 = ListNode(99) #print(type(node1)) # <class '__main__.ListNode'> list1 = SingleLinkedList() print("\n 目前的 list 000:") list1.output_list() list1.add_list_item(node1) print("\n 加入 node，目前的 list:") list1.output_list() list1.add_list_item('ABCD') print("\n 加入 node，目前的 list:") list1.output_list() list1.add_list_item(15) print("\n 加入 node，目前的 list:") list1.output_list() list1.add_list_item(17) print("\n 加入 node，目前的 list:") list1.output_list() list1.remove_value(15) print("\n 移除 node 值為 15 的，目前的 list:") list1.output_list() list1.remove_value('20') print("\n 目前的 list:") list1.output_list() ''' 作業1:就你的理解，在每行程式 加上 註解 # 作業2:在執行部分，改變並加入別的數值與文字 作業3:定義一個函式 移除 list 的特定節點 def remove_list_item_by_id(self, id): 作業4:定義一個函式 搜尋 list 的內容 def unordered_search(self, value): 作業5:定義一個函式 反轉 list 的內容 def reverse(self): ''' # 作業5:定義一個函式 反轉 list 的內容 def reverse(self): # 可參考 def reverse(self): # reverse the order of the list previous_node = None current_node = self.head next_node = current_node.next while next_node is not None: current_node.next = previous_node previous_node = current_node current_node = next_node next_node = next_node.next current_node.next = previous_node self.head = current_node return 範例 6-2 ''' This is ds-ex6-list.ipynb by 羅老師 on 2023/05/08 以 指標 實作 單向鏈結串列 (SingleLinkedList) 想想 IPO ...... 想想 演算法 資料來源：https://lovedrinkcafe.com/python-single-linked-list/ [1]1 --> [2]2 --> [3]3 --> [4]5 [index]: means the index of the node And the following number/string of [index] is the data of the Node ''' import os class Node: def __init__(self ,data=None, next=None): self.data = data self.next = next class SingleLinkedList: def __init__(self): self.head = None self.tail = None def append(self, data): new_node = Node(data) if self.head == None: self.head = new_node self.tail = new_node else: self.tail.next = new_node self.tail = self.tail.next #重寫 def delete(self): if self.head == None: return print("This list is empty") else: if len(self) == 1: self.head = None else: current_node = self.head while current_node.next != None: self.tail = current_node current_node = current_node.next self.tail.next = None def insert(self, index , data): ''' To insert the data to the specific index ''' if self.head == None: print("You can only insert the data to a not empty list") if not 1 <= index <= len(self): print("{} is not in range".format(index)) elif index == 1: new_node = Node(data) new_node.next = self.head self.head = new_node else: cur_idx = 1 new_node = Node(data) current_node = self.head while cur_idx+1 != index: current_node = current_node.next cur_idx += 1 new_node.next = current_node.next current_node.next = new_node def delete_node_by_index(self, index): ''' To delete the specific node ''' def reverse(self): # reverse the order of the list print ('待完成的作業 6-2') def __len__(self): length = 0 current_node = self.head while current_node != None: length += 1 current_node = current_node.next return length def __str__(self): current_node = self.head chain = [] index = 1 while current_node != None: chain.append("["+str(index)+"]"+str(current_node.data)) index += 1 current_node = current_node.next return " --> ".join(chain) def main(): l = SingleLinkedList() while True: os.system('cls' if os.name == 'nt' else 'clear') # print(__doc__) print('本程式 以 指標 實作 單向鏈結串列 (SingleLinkedList)') print(l) print("這個鏈結串列的長度為："+ str(len(l))) print("-"*20) opt = input("1. 加入資料\n2. 刪除資料\n3. 插入資料\n4. 刪除特定資料\n5. 反轉串列\n0. 結束程式\n 請輸入要使用的功能：") if opt == "1": data = input("請輸入要加入的資料：") l.append(data) print(l) elif opt == "2": l.delete() print(l) elif opt == "3": index = input("請輸入要插入的資料的index：") data = input("請輸入要插入的資料：") l.insert(int(index), data) print(l) elif opt == "4": print ('待完成的作業 6-1') index = int(input("請輸入要刪除的資料的index：")) l.delete_node_by_index(int(index)) print(l) elif opt == "5": l.reverse() print(l) elif opt == "0": print("The Final result is: {}".format(l)) return False else: print("請輸入合法指令") if __name__ == '__main__': main()
作業2:在執行部分，改變並加入別的數值與文字 作業3:定義一個函式 移除 list 的特定節點 def remove_list_item_by_id(self, id): 作業4:定義一個函式 搜尋 list 的內容 def unordered_search(self, value): 作業5:定義一個函式 反轉 list 的內容 def reverse(self): ''' # 作業5:定義一個函式 反轉 list 的內容 def reverse(self):
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
| 中華科技大學數位化學習歷程 - 意見反應 |  |
