请设计两个函数,一个根据读入的“行号 列号 元素值”三元组构建十字链表表示的稀疏矩阵,另一个从矩阵中查询指定行列上元素的值。
时间: 2024-09-26 18:11:38 浏览: 52
在Python中,我们可以创建一个稀疏矩阵的数据结构,如十字链表,来存储非零元素及其位置。这里我将为您设计两个函数:
```python
class Node:
def __init__(self, row, col, value):
self.row = row
self.col = col
self.value = value
self.next_row = None
self.next_col = None
class SparseMatrix:
def __init__(self):
self.head = None
def insert(self, row, col, value):
if not self.head:
self.head = Node(row, col, value)
else:
current = self.head
while True:
if row == current.row and abs(col - current.col) == 1:
current.value += value
break
elif row > current.row:
if not current.next_row:
next_node = Node(row, col, value)
current.next_row = next_node
break
else:
current = current.next_row
else:
if not current.next_col:
next_node = Node(row, col, value)
current.next_col = next_node
break
else:
current = current.next_col
def query_value(self, row, col):
if not self.head:
return 0
current = self.head
while current:
if row == current.row and col == current.col:
return current.value
elif row > current.row or (row == current.row and col < current.col):
current = current.next_row
else:
current = current.next_col
return 0
# 使用示例
matrix = SparseMatrix()
matrix.insert(0, 0, 1)
matrix.insert(1, 0, 2)
matrix.insert(1, 1, 3)
print(matrix.query_value(0, 0)) # 输出:1
print(matrix.query_value(1, 0))
阅读全文