python-3.x 使用双向链表(链表的链表)从(行,列,值)的元组列表构建电子表格

s4n0splo  于 2023-04-13  发布在  Python
关注(0)|答案(1)|浏览(97)

我希望得到一个像Build a spreadsheet from a list of tuples of (row, column, value) using 2D array. no numpy一样的结果,但它不是2d列表,而是一个链表的链表。
目前我还不知道如何建立一个链表的链表。

class Cell:
    def __init__(self, row: int, col: int, val: float):
        # a cell object has the row, column and value
        self.row = row
        self.col = col
        self.val = val

    def __str__(self) -> str:
        """
        Convert cell to a string for printing.
        """

        return "(" + str(self.row) + "," + str(self.col) + "," + "{:.2f}".format(self.val) + ")"
class Node:
    """
    A basic type in linked list
    """

    def __init__(self, value=None):
        self.m_value = value
        self.m_next = None
        self.m_prev = None

    def get_value(self):
        return self.m_value

    def get_next(self):
        return self.m_next

    def get_prev(self):
        return self.m_prev

    def set_value(self, value):
        self.m_value = value

    def set_next(self, next):
        self.m_next = next

    def set_prev(self, prev):
        self.m_prev = prev
class LinkedListSpreadsheet(BaseSpreadsheet):
    def __init__(self):
        self.rows = LinkedList()
        self.cols = LinkedList()
        self.length = 0

    def buildSpreadsheet(self, lCells: [Cell]):
        """
        Construct the data structure to store nodes.
        @param lCells: list of cells to be stored
        """
        pass

我需要帮助,以实现电子表格完成def buildSpreadsheet(self, lCells: [Cell]) lCell或细胞,其中有行,列,值。
所以lCell = [[9, 9, 20] [2, 5, 7] [3, 1, 6] [8, 5, -6.7], [1, 1, 3]]
我期望的结果是一个链表的链表,它只存储行和列位置的单元格的值。
与列1行1处的图像一样,存储的瓦尔是3。
expected output

6g8kf2rb

6g8kf2rb1#

首先是一些评论:

  • 当你允许调用者设置/获取任何值时,在Node类上创建getter和setter是没有用的。在这种情况下,只需让调用者直接访问属性。
  • 如果目标是为每个row/col组合创建一个Node示例,即使该节点中没有数据,那么使用链表实际上没有任何好处,使用嵌套的(标准)列表。当您不为没有数据的地方创建节点时,使用链表可能会变得更有趣。这允许有效地表示非常稀疏的电子表格,比如只有几个值,但是位于行825812和列9422和16840。所以我建议只为有数据的单元格创建节点。你仍然可以按照正确的顺序存储它们。
  • 关于数据结构,还有许多其他选择,但是为列创建单独的列表并不是一个好主意。
  • 我建议使用一个顶级链表数据结构,示例继承自Node:这将是一个sentinel(伪)节点。这个链表中的每个新节点都将是节点示例,其值为另一个链表(嵌套)。这个嵌套链表将表示一行,其中的每个节点表示一个单元格(其值为Cell示例)。此外,这个嵌套链表将是Node的示例,表示一个sentinel节点。
  • 您可以添加一个方法,将链表结构转换为更常见的列表结构(在未使用的单元格处使用None),这样您就可以更容易地测试实现。

这可能不是你希望的那样,但是我不能让自己创建一个链表,每个没有数据的坐标都有一个节点示例。这感觉很糟糕:

class Cell:
    def __init__(self, row: int, col: int, val: float):
        self.row = row
        self.col = col
        self.val = val

    def __repr__(self) -> str:
        return f"Cell({self.row},{self.col},{self.val})"

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = self.prev = None

    def insertAfter(self, value):
        other = Node(value)
        other.next = self.next
        if other.next:
            other.next.prev = other
        self.next = other
        other.prev = self

    def __str__(self) -> str:
        return f"Node(value:{self.value})"

class LinkedList(Node):
    def __init__(self, sentinelvalue=None):
        super().__init__()
        self.value = sentinelvalue

    def __iter__(self):
        node = self.next  # Skip dummy node
        while node:
            yield node.value
            node = node.next

    def nodes(self):
        node = self  # Include dummy node
        while node:
            yield node
            node = node.next
    
    def __repr__(self):
        return f"LinkedList={super().__str__()})"
    

class LinkedListRow(LinkedList):
    def __init__(self, cell):
        super().__init__(Cell(cell.row, -1, -1))
        self.set(cell)  # A row always has at least one cell with data

    def find(self, col):
        return next(node for node in self.nodes() if not node.next or node.next.value.col > col)
    
    def set(self, cell):
        node = self.find(cell.col)
        if node.value.col == cell.col:
            node.value = cell
        else:
            node.insertAfter(cell)
        
    def __repr__(self):
        return f"Row={super().__str__()})"
    
    def asList(self):
        lst = []
        for value in self:
            lst.extend([None] * (value.col - len(lst)))
            lst.append(value)
        return lst

class LinkedListSpreadsheet(LinkedList):
    def __init__(self):
        super().__init__(LinkedListRow(Cell(-1, -1, -1)))
        
    def find(self, row):
        return next(rowlist for rowlist in self.nodes() if not rowlist.next or rowlist.next.value.value.row > row)
    
    def set(self, cell):
        node = self.find(cell.row)
        if node.value.value.row == cell.row:
            node.value.set(cell)
        else:
            node.insertAfter(LinkedListRow(cell))

    def __repr__(self):
        return f"Spreadsheet={super().__str__()})"

    def asList(self):
        matrix = []
        for rowlist in self:
            matrix.extend(([] for _ in range(rowlist.value.row - len(matrix))))
            matrix.append(rowlist.asList())
        # pad the inner lists so they have equal length
        maxcols = max(map(len, matrix))
        for row in matrix:
            row.extend([None] * (maxcols - len(row)))
        return matrix

演示运行:

sheet = LinkedListSpreadsheet()
sheet.set(Cell(1, 10, 3))
sheet.set(Cell(1, 3, 9))
sheet.set(Cell(1, 2, 18))
sheet.set(Cell(1, 0, -10))
sheet.set(Cell(4, 5, 55))
for row in sheet.asList():
    print(row)

相关问题