Python数据结构之循环链表
2022/1/30 17:07:43
本文主要是介绍Python数据结构之循环链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
循环链表
- 循环链表的增删改查;
- 循环链表的尾指针的下一个结点指向头指针;
- 优点:
1). 每一个结点都可以遍历全部链表。
2). 而每个循环的时间复杂度都是相同的 O(1)。 - 缺点:
1). 需要多链接一个空间。
代码部分
- 结点类
class Node: def __init__(self, val): self.data = val self.next = None
- 初始化类
def init_linked_list(head_ptr): # 初始化循环链表将链表的ptr指向当前结点,程序结束将最后一个结点的next指针指向头结点 ptr = head_ptr init_data = [10, 42, 16, 72, 88] for i in range(len(init_data)): new_node = Node(init_data[i]) ptr.next = new_node ptr = new_node ptr.next = head_ptr
- 添加单个结点
def add_node(head_ptr, value): # 添加结点数据到链表中 new_node = Node(value) ptr = head_ptr while True: ptr = ptr.next if ptr.next == head_ptr: new_node.next = ptr.next ptr.next = new_node break
- 通过索引下标插入结点
def Insert_node_index(head_ptr, index, value): # 将数据插入到链表中 new_node = Node(value) index_loc = 0 flag = True if head_ptr is not None: if index == 0: flag = False ptr = head_ptr new_node.next = head_ptr while ptr.next != head_ptr: ptr = ptr.next ptr.next = new_node head_ptr = new_node return head_ptr elif index >= 1: ptr = head_ptr flag = False while True: if index_loc == (index - 1): new_node.next = ptr.next ptr.next = new_node break index_loc += 1 ptr = ptr.next if ptr == head_ptr: break return head_ptr if flag: ptr = head_ptr while ptr.next != head_ptr: ptr = ptr.next new_node.next = ptr.next ptr.next = new_node return head_ptr else: head_ptr = new_node return head_ptr
5.通过在某个值前面插入新结点
def Insert_node_value(head_ptr, find_value, new_value): new_node = Node(new_value) if head_ptr.data == find_value: new_node.next = head_ptr ptr = head_ptr while ptr.next != head_ptr: ptr = ptr.next ptr.next = new_node head_ptr = new_node else: ptr = head_ptr while ptr.next.data != find_value: ptr = ptr.next new_node.next = ptr.next ptr.next = new_node return head_ptr
- 通过索引删除结点
def Del_node_index(head_ptr, index): index_loc = 0 ptr = head_ptr while True: if index == 0: head_ptr = head_ptr.next break if (index - 1) == index_loc and index > 0: ptr.next = ptr.next.next break ptr = ptr.next index_loc += 1 return head_ptr
- 通过查找值删除结点
def Del_node_value(head_ptr, find_value): ptr = head_ptr if head_ptr.data == find_value: head_ptr = head_ptr.next while ptr.next.data != find_value: ptr = ptr.next ptr.next = ptr.next.next return head_ptr
- 通过索引查找结点值
def Query_node_index(head_ptr, value): index = 0 ptr = head_ptr while True: if ptr.data == value: break index += 1 ptr = ptr.next if ptr == head_ptr: index = -1 break return index
- 通过结点值查找索引位置
def Query_node_value(head_ptr, index): old_index = 0 find_data = -1 ptr = head_ptr while True: if index == 0: find_data = head_ptr.data break elif index > 0 and index == old_index: find_data = ptr.data ptr = ptr.next old_index += 1 if ptr == head_ptr: break return find_data
- 通过索引修改值
def Reset_index_value(head_ptr, index, new_value): index_loc = 0 ptr = head_ptr ok = False while True: if index == index_loc: ptr.data = new_value ok = True break index_loc += 1 ptr = ptr.next if ptr == head_ptr: break return ok
- 查找旧值修改为新值
def Reset_old_value(head_ptr, old_value, new_value): ptr = head_ptr ok = False while True: if ptr.data == old_value: ptr.data = new_value ok = True break ptr = ptr.next if ptr == head_ptr: break return ok
- 输出数据
def Print(head_ptr): ptr = head_ptr while True: print(ptr.data, end="\t") ptr = ptr.next if ptr == head_ptr: break
- 两个链表的连接
def Mere_list(list_one, list_two): ptr_one = list_one ptr_two = list_two while ptr_one.next != list_one: ptr_one = ptr_one.next ptr_one.next = ptr_two while ptr_two.next != list_two: ptr_two = ptr_two.next ptr_two.next = list_one return list_one
总结: 全部代码部分
class Node: def __init__(self, val): self.data = val self.next = None def init_linked_list(head_ptr): # 初始化循环链表将链表的ptr指向当前结点,程序结束将最后一个结点的next指针指向头结点 ptr = head_ptr init_data = [10, 42, 16, 72, 88] for i in range(len(init_data)): new_node = Node(init_data[i]) ptr.next = new_node ptr = new_node ptr.next = head_ptr def add_node(head_ptr, value): # 添加结点数据到链表中 new_node = Node(value) ptr = head_ptr while True: ptr = ptr.next if ptr.next == head_ptr: new_node.next = ptr.next ptr.next = new_node break def Insert_node_index(head_ptr, index, value): # 将数据插入到链表中 new_node = Node(value) index_loc = 0 flag = True if head_ptr is not None: if index == 0: flag = False ptr = head_ptr new_node.next = head_ptr while ptr.next != head_ptr: ptr = ptr.next ptr.next = new_node head_ptr = new_node return head_ptr elif index >= 1: ptr = head_ptr flag = False while True: if index_loc == (index - 1): new_node.next = ptr.next ptr.next = new_node break index_loc += 1 ptr = ptr.next if ptr == head_ptr: break return head_ptr if flag: ptr = head_ptr while ptr.next != head_ptr: ptr = ptr.next new_node.next = ptr.next ptr.next = new_node return head_ptr else: head_ptr = new_node return head_ptr def Insert_node_value(head_ptr, find_value, new_value): new_node = Node(new_value) if head_ptr.data == find_value: new_node.next = head_ptr ptr = head_ptr while ptr.next != head_ptr: ptr = ptr.next ptr.next = new_node head_ptr = new_node else: ptr = head_ptr while ptr.next.data != find_value: ptr = ptr.next new_node.next = ptr.next ptr.next = new_node return head_ptr def Del_node_index(head_ptr, index): index_loc = 0 ptr = head_ptr while True: if index == 0: head_ptr = head_ptr.next break if (index - 1) == index_loc and index > 0: ptr.next = ptr.next.next break ptr = ptr.next index_loc += 1 return head_ptr def Del_node_value(head_ptr, find_value): ptr = head_ptr if head_ptr.data == find_value: head_ptr = head_ptr.next while ptr.next.data != find_value: ptr = ptr.next ptr.next = ptr.next.next return head_ptr def Query_node_index(head_ptr, value): index = 0 ptr = head_ptr while True: if ptr.data == value: break index += 1 ptr = ptr.next if ptr == head_ptr: index = -1 break return index def Query_node_value(head_ptr, index): old_index = 0 find_data = -1 ptr = head_ptr while True: if index == 0: find_data = head_ptr.data break elif index > 0 and index == old_index: find_data = ptr.data ptr = ptr.next old_index += 1 if ptr == head_ptr: break return find_data def Reset_index_value(head_ptr, index, new_value): index_loc = 0 ptr = head_ptr ok = False while True: if index == index_loc: ptr.data = new_value ok = True break index_loc += 1 ptr = ptr.next if ptr == head_ptr: break return ok def Reset_old_value(head_ptr, old_value, new_value): ptr = head_ptr ok = False while True: if ptr.data == old_value: ptr.data = new_value ok = True break ptr = ptr.next if ptr == head_ptr: break return ok def Print(head_ptr): ptr = head_ptr while True: print(ptr.data, end="\t") ptr = ptr.next if ptr == head_ptr: break def Mere_list(list_one, list_two): ptr_one = list_one ptr_two = list_two while ptr_one.next != list_one: ptr_one = ptr_one.next ptr_one.next = ptr_two while ptr_two.next != list_two: ptr_two = ptr_two.next ptr_two.next = list_one return list_one if __name__ == '__main__': # head = Node(0) # init_linked_list(head) # Print(head) # print() # # head = Insert_node_index(head, 2, 82) # # Print(head) # # print() # # head = Insert_node_value(head, 0, 82) # # Print(head) # # print() # # Print(Del_node_index(head, 4)) # # print() # # Print(Del_node_index(head, 2)) # # print() # # print(Query_node_index(head, 82)) # print(Query_node_value(head, -1)) # Reset_index_value(head, 1, 99) # Print(head) # print(Reset_old_value(head, 42, 55)) # Print(head) head_one = Node(0) init_linked_list(head_one) Print(head_one) print() head_two = Node(1) init_linked_list(head_two) Print(head_two) Mere_list(head_one, head_two) print() Print(head_one)
这篇关于Python数据结构之循环链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python