时间戳

首页 > 解决方案 > 在 Python 中列出的链接中的 searchDelete

python-3.x - 在 Python 中列出的链接中的 searchDelete

问题描述

陷入问题编号。

  1. insertAfterSearch（搜索一条数据，如果找到，则在搜索到的节点之后插入新数据CLUE：2个参数）
  2. searchDelete（搜索数据，如果找到则删除节点，CLUE：1 参数）有人可以帮我解决这个问题。
class Node:
    def __init__(self, data):
        self.nodeValue = data
        self.nodeLink = None
        
class LinkedList:
    def __init__(self):
        self.startNode = None
        

        
    def traverseList(self):
        if self.startNode is None:
            print("List is empty")
        else:
            currentNode = self.startNode
            while currentNode is not None:
                print(currentNode.nodeValue, end = " ")
                currentNode = currentNode.nodeLink
            print("End of Link")
    
    def insertAtEnd(self, data):
        newNode = Node(data)
        if self.startNode is None:
            self.startNode = newNode
        else:
            currentNode = self.startNode
            while currentNode.nodeLink is not None:
                currentNode = currentNode.nodeLink
            currentNode.nodeLink = newNode
    
        
    def searchValue(self, searchData):
        if self.startNode is None:
            print("List is empty")
        else:
            currentNode = self.startNode
            nodeNumber = 1
            while currentNode is not None:
                if currentNode.nodeValue == searchData:
                    print("Found the Data", searchData, "at Node", nodeNumber)
                    return
                else:
                    currentNode = currentNode.nodeLink
                    nodeNumber += 1
            print("Data not found")
            
    def generateLinkedList(self):
        numOfInput = int(input("How many nodes do you want to create: "))
        if numOfInput == 0:
            return
        for currentInput in range(numOfInput):
            print("Node #", currentInput+1, ": ", end ="")
            inValue = int(input("Enter the value for the node: "))
            self.insertAtEnd(inValue)
    
        
        
sampleList = LinkedList()
sampleList.generateLinkedList()
sampleList.traverseList()
sampleList.searchValue(3)

https://pastebin.com/b1wGZeMJ

标签： python-3.x

解决方案

我将通过给节点一个方法（如果它们在对象内部，我们称之为函数）来检查它是否具有搜索值来实现这一点。

class Node:
    def __init__(self, data):
        self.nodeValue = data
        self.nodeLink = None

    def find_value(self, value):
        if self.nodeValue == value:
            return self

        elif self.nodeLink == None:
            return None

        else:
            return self.nodeLink.find_value(value)

这样你就可以让第一个对象找到你的值，它会继续传递它，直到它找到那个值，并且对象被递回链到前面，所以对你来说，它看起来就像头只会给你回答。有了这个，我们就可以插入和删除对象。

搜索后插入

要插入一个对象，您需要获取找到的对象（父）链接（子）并保存它。然后将父母链接指向您的新对象，并将对象链接指向孩子。为此，我将在 Node 中定义一个方法来执行此操作：

def insert_link(self, value):
    new_child = Node(value)
    old_child = self.nodeLink

    self.nodeLink = new_child
    new_child.nodeLink = old_child

请注意此方法还如何为您创建新对象。现在我还在 Node 和 List-Object 中分别定义了一个 print_node 和一个 print_list 函数：

节点：

def print_node(self):
    print(self.nodeValue, end = " -> ")

    if self.nodeLink is None:
        print(None)
        return

    self.nodeLink.print_node()

列表：

def print_list(self):
    self.startNode.print_node()

现在我们可以测试插入：

def main():
    sampleList = LinkedList()
    sampleList.generateLinkedList()
    sampleList.print_list()
    sampleList.insertAfterSearch(3, 6)
    sampleList.print_list()

if __name__ == '__main__':
    main()

在终端：

$ python3 linked_list.py 
How many nodes do you want to create: 1
Node # 1 : Enter the value for the node: 3
3 -> None
3 -> 6 -> None

搜索和删除

为此，我们需要找到一个节点并将其父节点链接设置为子节点。然后应该删除该节点。我还将使用节点递归地执行此操作。为此，我们将添加一个“自毁”方法（因为它很酷）：

def self_destruct(self, parent, value):

    if not self.nodeValue == value:

        if self.nodeLink is None:
            print("Value not found")
            return None

        found_node = self.nodeLink.self_destruct(self, value)
        return found_node

在链表中，我们将首先测试头部是否会被删除。如果是这样，我们只需要重新分配头部。如果不是头部，我们需要开始自毁搜索：

def deleteSearch(self, key):

    if self.startNode.nodeValue == key:
        found = self.startNode
        self.startNode = found.nodeLink


    else:
        found = self.startNode.self_destruct(None, key)

    if found is None:
        print("Could not find object")
    else:
        del found # Not really needed because garbage collector, but I don't trust that sourcery.

新主线：

def main():
    sampleList = LinkedList()
    sampleList.generateLinkedList()
    sampleList.print_list()
    sampleList.deleteSearch(3)
    sampleList.print_list()

会产生：

$ python3 linked_list.py 
How many nodes do you want to create: 5
Node # 1 : Enter the value for the node: 1
Node # 2 : Enter the value for the node: 5
Node # 3 : Enter the value for the node: 3
Node # 4 : Enter the value for the node: 2
Node # 5 : Enter the value for the node: 7
1 -> 5 -> 3 -> 2 -> 7 -> None
1 -> 5 -> 2 -> 7 -> None

并且删除起始节点也可以：

$ python3 linked_list.py 
How many nodes do you want to create: 4
Node # 1 : Enter the value for the node: 3
Node # 2 : Enter the value for the node: 7
Node # 3 : Enter the value for the node: 8
Node # 4 : Enter the value for the node: 9
3 -> 7 -> 8 -> 9 -> None
7 -> 8 -> 9 -> None

因为您是新来的，所以我想指出，如果一个答案解决了您的解决方案，您应该确认该答案，因为它为回答者提供了更多的声誉，并且让其他人更容易找到正确的答案。

推荐阅读