0

作为我的 A-Level 课程的一部分，我必须编写一个程序来创建一个能够添加和删除节点的链表。

不幸的是，我的考试委员会规定这必须以特定的非正统方式完成。他们希望节点是具有存储在标准列表中的两个属性（数据和指针）的对象。

以这种方式完成非常重要，因为考试委员会不接受任何其他方法:(

这是我必须使用的节点的构造方法

class ListNode:
    def __init__(self) :
        self.data = int()
        self.pointer = -1

我花了很长时间尝试各种事情来让它正常工作，但我似乎无法让它保持指针正确。

有人可以帮我解决一个工作问题，任何帮助都非常感谢。

编辑：正如我建议的那样，我发布了我目前最好的尝试。

到目前为止，我已经完成了初始化并添加了（我认为），但我需要删除方面的帮助。我还认为我可能需要调整我的添加代码才能删除工作。虽然我完全不知道如何在被删除后保持指针指向正确的节点。

初始化：

def initialiselist():
    List = [Node() for i in range(10)]
    startpointer = nullpointer
    freelistptr = 0

    for index in range(9):
        List[index].pointer = index + 1
    List[9].pointer = nullpointer

    for i in List:
        print(i.data, i.pointer)
    return List, startpointer, freelistptr

添加节点：

def insertnode(List, startpointer, freelistptr, newdata):
    if startpointer == -1:                      #If list is empty
        List[freelistptr].data = newdata
        startpointer = freelistptr
        freelistptr = List[startpointer].pointer
        List[startpointer].pointer = -1
        return(List,startpointer,freelistptr)

    for i in List:
        if i.data == newdata:        
            print("You cannot have duplicate data")
            return(List,startpointer,freelistptr)

    if freelistptr == -1:
        print("The list is full")
        return(List,startpointer,freelistptr)

    elif freelistptr != -1:         #If Lis is not empty
        List[freelistptr].data = newdata

        if List[startpointer].data > newdata:             #If the new data is less than the startpointer 
            temp = List[freelistptr].pointer
            List[freelistptr].pointer = startpointer                    
            startpointer = freelistptr                                  
            freelistptr = temp
            return(List,startpointer,freelistptr)

        else:                                               #If the new data is greater than the startpointer

            if List[startpointer].pointer == -1:                            
                List[startpointer].pointer = freelistptr                
                temp = freelistptr                                      
                freelistptr = List[freelistptr].pointer             
                List[temp].pointer = -1
                return(List,startpointer,freelistptr)

            nextnodeptr = List[startpointer].pointer                        
            previousnodeptr = startpointer
            newnodeptr = freelistptr
            temp2 = List[freelistptr].pointer

            while True:
                if List[nextnodeptr].pointer == -1:
                    if List[nextnodeptr].data > newdata:
                        List[newnodeptr].pointer = nextnodeptr
                        List[previousnodeptr].pointer = newnodeptr
                        break
                    elif List[nextnodeptr].data < newdata:
                        List[nextnodeptr].pointer = newnodeptr
                        temp2 = List[freelistptr].pointer
                        List[newnodeptr].pointer = -1
                        break
                if List[nextnodeptr].data > newdata:
                    temp2 = List[freelistptr].pointer
                    List[newnodeptr].pointer = nextnodeptr
                    List[previousnodeptr].pointer = newnodeptr
                    break   
                else:
                    previousnodeptr = nextnodeptr
                    nextnodeptr = List[nextnodeptr].pointer

            freelistptr = temp2   
            return (List,startpointer,freelistptr)

我知道这只是一堵完整的文字墙，但我不习惯在这里发帖，所以很抱歉。

我的问题是如何删除节点？

4

1 回答 1

0

如果我正确理解“非正统”要求，节点的底层结构应该是标准列表。这意味着您的节点类应该是list没有任何自身属性的子类。

以下是我将如何处理这个问题：

class ListNode(list):

    @property
    def pointer(self): return (self[1:] or [None])[0]
    @pointer.setter
    def pointer(self,node): self[:] = [self.data,node]

    @property
    def data(self): return self[0] if self else None
    @data.setter
    def data(self,value): self[:1] = [value]

    def addNode(self,node): # to end of chain
        if self.pointer: self.pointer.addNode(node)
        else:            self.pointer = node

    def append(self,value):
        self.addNode(ListNode([value]))

    def insertNode(self,node): # before this node
        if self.pointer: node.addNode(self.pointer)        
        self.data,node.data       = node.data,self.data
        self.pointer,node.pointer = node,self.pointer

    def find(self,value):
        if self.data == value: return self
        if self.pointer: return self.pointer.find(value)

    def deleteNode(self,node): # needs to start from a previous node
        if self.pointer is node: self.pointer = node.pointer
        else:                    self.pointer.deleteNode(node)

    def __repr__(self):
        return f"{self.data}" + (f" --> {self.pointer}" if self.pointer else "")

请注意，一旦使用 setter 和 getter 定义了数据和指针属性，其余方法就不需要知道底层存储结构实际上是什么

用法：

head  = ListNode([0])
head.append(1)
head.append(2)
head.append(3)

print(head)
# 0 --> 1 --> 2 --> 3

node2 = head.find(2)
node4 = ListNode([4])
node2.insertNode(node4)

print(head)
# 0 --> 1 --> 4 --> 2 --> 3

node2 = head.find(2)
head.deleteNode(node2)

print(head)
# 0 --> 1 --> 4 --> 3
于 2020-04-16T19:34:01.157 回答