使用双向链表（链表的链表）从（行、列、值）的元组列表构建电子表格

Question

我希望得到像使用二维数组从（行、列、值）的元组列表构建电子表格的结果。没有 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]]

我期待的结果是一个链接列表的链接列表，它只存储 Cell 的值在行和列的位置。

就像第 1 列第 1 行的图像一样，存储的值是 3.

Answer 1

首先是一些评论：

• 当您允许调用者设置/获取任何值时，在您的 Node 类上创建 getter 和 setter 是没有用的。在那种情况下，只需让调用者直接访问属性即可。

• 如果目标是为每个行/列组合创建一个节点实例，即使该节点中没有数据，那么使用链表确实没有任何好处，你最好使用嵌套（标准) 列表。当您不为没有数据的地方创建节点时，使用链表可能会变得更有趣。这允许有效地表示非常 sparse 的电子表格，比如当只有几个值，但位于 825812 行和 9422 列和 16840 列时。所以我建议只为包含数据的单元格创建节点。你仍然会以正确的顺序存储它们。

• 关于数据结构还有很多其他选择，但是为列创建单独的列表并不是一个好主意。

• 我会建议一个顶级链表数据结构，其中实例继承自

  Node

  ：这将是一个哨兵（虚拟）节点。此链表中的每个新节点都将是具有另一个链表（嵌套）值的节点实例。这个嵌套链表将代表一行，其中的每个节点代表一个单元格（它的值是一个

  Cell

  实例）。此外，这个嵌套链表将是

  Node

  的一个实例，代表一个哨兵节点。

• 您可以添加一个方法，将链表结构转换为更常见的列表列表结构（在未使用的单元格处带有

  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)

Answer 2

self.row_count = max(lCells, key=lambda x: x.row).row + 1
    self.col_count = max(lCells, key=lambda x: x.col).col + 1
    print(self.row_count, "<ROW Col>", self.col_count)
    # self.row_heads = [Node(None, row, 0) for row in range(self.row_count)]
    # self.col_heads = [Node(None, 0, col) for col in range(self.col_count)]
    self.row_heads = [None for _ in range(self.row_count)]
    self.col_heads = [None for _ in range(self.col_count)]

    for cell in lCells:
        row = cell.row
        col = cell.col
        val = cell.val

        # Search for the column in the linked list for the corresponding row
        current_node = self.row_heads[row]
        while current_node is not None and current_node.col != col:
            current_node = current_node.right

        # If the column is not found, create a new node for it
        if current_node is None:
            new_node = Node(val, row, col)

            # Link the new node to the right of the previous node (or the row head, if the row is empty)
            if self.row_heads[row] is None:
                self.row_heads[row] = new_node
            else:
                current_node = self.row_heads[row]
                while current_node.right is not None:
                    current_node = current_node.right
                current_node.right = new_node

            # Link the new node to the bottom of the previous node (or the column head, if the column is empty)
            if self.col_heads[col] is None:
                self.col_heads[col] = new_node
            else:
                current_node = self.col_heads[col]
                while current_node.bottom is not None:
                    current_node = current_node.bottom
                current_node.bottom = new_node
            # # Increment the number of columns
            # self.col_count += 1
        # If the column is found, just update the value of the existing node
        else:
            current_node.value = val