我想用c语言实现十字链表做矩阵加法
时间: 2023-08-13 11:04:25 浏览: 80
当然可以,以下是用 C 语言实现十字链表做矩阵加法的示例代码:
```
#include <stdio.h>
#include <stdlib.h>
struct MatrixNode {
int row;
int col;
int value;
struct MatrixNode* right;
struct MatrixNode* down;
};
struct CrossMatrix {
int rows;
int cols;
struct MatrixNode** row_heads;
struct MatrixNode** col_heads;
struct MatrixNode* head;
};
struct MatrixNode* create_node(int row, int col, int value) {
struct MatrixNode* node = (struct MatrixNode*)malloc(sizeof(struct MatrixNode));
node->row = row;
node->col = col;
node->value = value;
node->right = NULL;
node->down = NULL;
return node;
}
struct CrossMatrix* create_cross_matrix(int rows, int cols) {
struct CrossMatrix* matrix = (struct CrossMatrix*)malloc(sizeof(struct CrossMatrix));
matrix->rows = rows;
matrix->cols = cols;
matrix->row_heads = (struct MatrixNode**)malloc(rows * sizeof(struct MatrixNode*));
matrix->col_heads = (struct MatrixNode**)malloc(cols * sizeof(struct MatrixNode*));
matrix->head = create_node(-1, -1, 0);
matrix->head->right = matrix->col_heads[0] = create_node(-1, 0, 0);
matrix->head->down = matrix->row_heads[0] = create_node(0, -1, 0);
for (int i = 1; i < rows; i++) {
matrix->row_heads[i] = create_node(i, -1, 0);
matrix->row_heads[i - 1]->down = matrix->row_heads[i];
}
for (int i = 1; i < cols; i++) {
matrix->col_heads[i] = create_node(-1, i, 0);
matrix->col_heads[i - 1]->right = matrix->col_heads[i];
}
return matrix;
}
void insert(struct CrossMatrix* matrix, int row, int col, int value) {
struct MatrixNode* node = create_node(row, col, value);
struct MatrixNode* row_head = matrix->row_heads[row];
struct MatrixNode* col_head = matrix->col_heads[col];
struct MatrixNode* current_node = row_head;
while (current_node->right && current_node->right->col < col) {
current_node = current_node->right;
}
node->right = current_node->right;
current_node->right = node;
current_node = col_head;
while (current_node->down && current_node->down->row < row) {
current_node = current_node->down;
}
node->down = current_node->down;
current_node->down = node;
}
struct CrossMatrix* add(struct CrossMatrix* matrix1, struct CrossMatrix* matrix2) {
if (matrix1->rows != matrix2->rows || matrix1->cols != matrix2->cols) {
printf("Matrices must have the same size\n");
return NULL;
}
struct CrossMatrix* result = create_cross_matrix(matrix1->rows, matrix1->cols);
for (int i = 0; i < matrix1->rows; i++) {
struct MatrixNode* current_node1 = matrix1->row_heads[i]->right;
struct MatrixNode* current_node2 = matrix2->row_heads[i]->right;
while (current_node1 || current_node2) {
if (current_node1 && (!current_node2 || current_node1->col < current_node2->col)) {
insert(result, i, current_node1->col, current_node1->value);
current_node1 = current_node1->right;
}
else if (current_node2 && (!current_node1 || current_node2->col < current_node1->col)) {
insert(result, i, current_node2->col, current_node2->value);
current_node2 = current_node2->right;
}
else {
insert(result, i, current_node1->col, current_node1->value + current_node2->value);
current_node1 = current_node1->right;
current_node2 = current_node2->right;
}
}
}
return result;
}
void print_matrix(struct CrossMatrix* matrix) {
for (int i = 0; i < matrix->rows; i++) {
struct MatrixNode* current_node = matrix->row_heads[i]->right;
for (int j = 0; j < matrix->cols; j++) {
if (current_node && current_node->col == j) {
printf("%d ", current_node->value);
current_node = current_node->right;
}
else {
printf("0 ");
}
}
printf("\n");
}
}
int main() {
struct CrossMatrix* matrix1 = create_cross_matrix(3, 3);
insert(matrix1, 0, 0, 1);
insert(matrix1, 0, 1, 2);
insert(matrix1, 1, 1, 3);
insert(matrix1, 1, 2, 4);
insert(matrix1, 2, 0, 5);
insert(matrix1, 2, 2, 6);
struct CrossMatrix* matrix2 = create_cross_matrix(3, 3);
insert(matrix2, 0, 0, 7);
insert(matrix2, 0, 1, 8);
insert(matrix2, 1, 1, 9);
insert(matrix2, 1, 2, 10);
insert(matrix2, 2, 0, 11);
insert(matrix2, 2, 2, 12);
struct CrossMatrix* result = add(matrix1, matrix2);
print_matrix(result);
return 0;
}
```
这里使用了结构体实现节点和矩阵,定义了`create_node`和`create_cross_matrix`函数用于创建节点和十字链表形式的矩阵。还定义了`insert`和`add`函数用于插入节点和进行矩阵加法。最后,使用`print_matrix`函数打印出矩阵。
阅读全文