Python教程

Python数据结构之循环链表

本文主要是介绍Python数据结构之循环链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

循环链表

  1. 循环链表的增删改查;
  2. 循环链表的尾指针的下一个结点指向头指针;
  3. 优点:
    1). 每一个结点都可以遍历全部链表。
    2). 而每个循环的时间复杂度都是相同的 O(1)。
  4. 缺点:
    1). 需要多链接一个空间。

代码部分

  1. 结点类
class Node:
    def __init__(self, val):
        self.data = val
        self.next = None
  1. 初始化类
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
  1. 添加单个结点
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
  1. 通过索引下标插入结点
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
  1. 通过索引删除结点
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
  1. 通过查找值删除结点
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
  1. 通过索引查找结点值
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
  1. 通过结点值查找索引位置
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

  1. 通过索引修改值
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
  1. 查找旧值修改为新值
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
  1. 输出数据
def Print(head_ptr):
    ptr = head_ptr
    while True:
        print(ptr.data, end="\t")
        ptr = ptr.next
        if ptr == head_ptr:
            break
  1. 两个链表的连接
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数据结构之循环链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!