基于十字链表存储的稀疏矩阵创建和输出操作的实现pta

稀疏矩阵是其中大多数元素为0的矩阵，我们可以使用十字链表来表示稀疏矩阵，从而节省存储空间。下面是基于十字链表存储的稀疏矩阵创建和输出操作的实现。

首先，我们定义一个节点类，用于表示稀疏矩阵的非零元素节点。该节点类包含四个成员变量：row、col、value和right。其中row和col分别表示该节点所在的行和列的索引值，value表示该节点的数值，right是指向下一个非零元素的指针。

然后，我们创建一个稀疏矩阵类，该类包含一个头节点head、一个保存行头节点的一维数组rows、一个保存列头节点的一维数组cols以及两个整型变量row_num和col_num。头节点head用于表示稀疏矩阵的整体信息，rows和cols数组分别用于保存每一行和每一列的头节点，row_num和col_num分别保存稀疏矩阵的行数和列数。

在创建操作中，我们首先通过读取输入，获取稀疏矩阵的行数row_num和列数col_num。然后，根据row_num和col_num创建rows和cols数组并初始化头节点head。接下来，我们通过遍历输入，获取每个非零元素的行列索引和数值，并创建相应的节点，将其插入到十字链表中。最后，我们根据稀疏矩阵的规模和十字链表的结构，输出稀疏矩阵的元素。

具体的实现过程可以参考以下伪代码：

class Node:
def __init__(self, row, col, value):
self.row = row
self.col = col
self.value = value
self.right = None

class SparseMatrix:
def __init__(self):
self.head = Node(-1, -1, -1)
self.rows = []
self.cols = []
self.row_num = 0
self.col_num = 0

def create_sparse_matrix(self):
self.row_num, self.col_num = input().split()
self.row_num = int(self.row_num)
self.col_num = int(self.col_num)

self.rows = [Node(-1, -1, -1) for _ in range(self.row_num)]
self.cols = [Node(-1, -1, -1) for _ in range(self.col_num)]

self.head.row = self.row_num
self.head.col = self.col_num

for _ in range(self.row_num):
row_data = input().split()
row = int(row_data[0])
col = int(row_data[1])
value = int(row_data[2])
node = Node(row, col, value)

# 插入链表中
self.insert_node(node)

def insert_node(self, node):
# 插入到对应行的链表中
if self.rows[node.row].right is None:
self.rows[node.row].right = node
else:
cur = self.rows[node.row].right
while cur.right is not None and cur.right.col < node.col:
cur = cur.right
node.right = cur.right
cur.right = node

# 插入到对应列的链表中
if self.cols[node.col].right is None:
self.cols[node.col].right = node
else:
cur = self.cols[node.col].right
while cur.right is not None and cur.right.row < node.row:
cur = cur.right
node.right = cur.right
cur.right = node

def output_sparse_matrix(self):
print(self.row_num, self.col_num)
for i in range(self.row_num):
cur = self.rows[i].right
while cur is not None:
print(cur.row, cur.col, cur.value)
cur = cur.right

通过以上代码，我们实现了基于十字链表存储的稀疏矩阵的创建和输出操作。