python中的非正统链表

2024-09-26 18:09:46 发布

您现在位置:Python中文网/ 问答频道 /正文

作为我的A级cirriculum的一部分,我需要一个程序来创建一个能够添加和删除节点的链表

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

这样做是非常重要的,因为考试委员会不接受任何其他方法:(

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

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)    

我知道这只是一个完整的文字墙,但我不习惯张贴在这里,所以我很抱歉

我的问题是如何删除节点


Tags: infordatareturnif节点islist
1条回答
网友
1楼 · 发布于 2024-09-26 18:09:46

如果我正确理解了“非正统”需求,那么节点的底层结构应该是一个标准列表。这意味着您的节点类应该是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

相关问题 更多 >

    热门问题