我希望得到一个结果，就像在构建一个电子表格从元组(行，列，值)的列表使用2D数组。没有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或具有行，列，值的Cell来帮助实现电子表格。
lCell = [[9, 9, 20] [2, 5, 7] [3, 1, 6] [8, 5, -6.7], [1, 1, 3]]
我期望的结果是一个链表的链表，它只存储Cell在row和col.位置的值
就像在col1行1处的图像一样，存储的值是3。
预期输出
先说几句:
-
当你允许调用者设置/获取任何值时，在你的Node类上创建getter和setter是没有用的。在这种情况下，只需让调用者直接访问属性。
-
如果目标是为每个row/col组合创建一个Node实例，即使该节点中没有数据，那么使用链表确实没有任何好处，您最好使用嵌套(标准)列表。当不为没有数据的地方创建节点时，使用链表可能会变得更有趣。这允许有效地表示非常稀疏的电子表格，比如只有几个值，但位于第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)
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