使用C中的链接列表创建稀疏矩阵

我有一个任务是创建两个稀疏矩阵（A和B），然后将它们加到第三个稀疏矩阵（C）中。 我已经用向量做了它（接收两个稀疏向量并将它们添加到第三个）所以我决定使用一系列向量来表示矩阵会更容易。 在将来，我可能需要在没有向量的情况下使用实际矩阵（我甚至有一个函数的伪代码将数字插入稀疏矩阵），所以要理解为什么我要问所有这些，即使以下代码有点工作。

因为它是一个矩阵，所以它有两个指针数组，即行数组和列数组。 数组的每个单元格指向相应的行/列。 如下图所示：

作为稀疏矩阵，在有零的情况下，您会看到那些箭头，因为那些带有零的节点不存在。

为了简化这个问题，我更喜欢只处理行数组，如图所示，这些行指向每个新行的头部。 假设每一行都是一个向量C（就像我上面说的，我想用一系列向量表示矩阵）。

这是我构建的所有链表function的代码：

typedef struct List_node { int key; int i,j; struct List_node *next; }List_node; typedef struct List { List_node *head; }List; List *create_list() { List *list = (List*)malloc(sizeof(List)); list->head = NULL; return list; } void insert_first(List_node *x, List *list) { x->next = list->head; list->head = x; } void insert(List_node *x, List_node *y) { x->next = y->next; y->next = x; } List_node *mk_node(int data, int row, int col) { List_node *node = (List_node *)malloc(sizeof(List_node)); node->key = data; node->i = row + 1; node->j = col + 1; return node; } void delete_list(List *list) { List_node *node, *temp; node = list->head; while (node != NULL) { temp = node->next; free(node); node = temp; } free(list); } void print_list(List *list, char name) { List_node *p; p = list->head; printf("\nThe linked list %c consists of: ",name); while (p != NULL) { printf("%d(i = %d) (j = %d) ", p->key, p->i, p->j); p = p->next; } printf("\n"); } 

这是创建向量的代码：

 List *Create_vector (List *A, List *B, int i, int m) { int l,flag = 0; List *C; List_node *node=NULL, *next, *Pointer_A, *Pointer_B; C = create_list(); Pointer_A = A->head; Pointer_B = B->head; for (l = 0; lkey + Pointer_B->key) != 0) { if (flag == 0) { node = mk_node(Pointer_A->key + Pointer_B->key, i,l); insert_first(node, C); flag = 1; } else { next = mk_node(Pointer_A->key + Pointer_B->key, i,l); insert(next, node); node = next; } } Pointer_A = Pointer_A->next; Pointer_B = Pointer_B->next; } return C; } 

这是主要计划：

 void main() { List_node *Row_A, *Row_B, *Row_C; List *A, *B, *C; List_node *node, *next; int data, m,n,l; printf("Enter list row\n"); scanf("%d", &m); Row_A = (List_node*)malloc(sizeof(int)*(m)); Row_B = (List_node*)malloc(sizeof(int)*(m)); Row_C = (List_node*)malloc(sizeof(int)*(m)); printf("Enter list columns\n"); scanf("%d", &n); for (int i=0; i<m; i++) { A = create_list(); B = create_list(); printf("\nInsert first number into A\n"); scanf("%d", &data); node = mk_node(data, i,0); insert_first(node, A); for (l = 1; l<n; l++) { printf("Now insert the rest of the numbers\n"); scanf("%d", &data); next = mk_node(data, i,l); insert(next, node); node = next; } print_list(A,'A'); printf("\nInsert first number into B\n"); scanf("%d", &data); node = mk_node(data,i,0); insert_first(node, B); for (l = 1; l<n; l++) { printf("Now insert the rest of the numbers\n"); scanf("%d", &data); next = mk_node(data, i,l); insert(next, node); node = next; } print_list(B,'B'); C = Create_vector(A,B,i,n); } getchar(); getchar(); } 

希望你能做到这一点。 所以我的问题是：

1. 我不知道如何创建我需要的指针数组，即Row_A，Row_B，Row_C。 意思是，如果每个单元格指向向量的头部 – 如何定义数组？ 作为清单？ 列表节点？ 如何让数组的每个单元格指向每个向量的头部？

2. 每次执行for循环时都会覆盖列表C. 我看到的唯一方法是保持每个向量C并将其放在矩阵中是为了使每个数组单元指向每个向量的头部，这使我们回到问题＃1。 真的吗？ 我怎样才能做到这一点？

非常感谢你。

Answer 1

一些可能让你开始的观察：

• 您可以按照创建动态数组Row_A的方式创建磁头列表，依此类推。 这些头部列表不应该是独立的数据结构。 它们应该是Matrix结构的一部分，就像head是List结构的一部分一样。 head数组的分配应该是其创建函数create_matrix 。

• 每个Matrix存储其自己的磁头列表的事实也是覆盖C的解决方案：而不是一遍又一遍地分配给C->head[i] ，分配给C->head[i] 。 同样适用于A和B 描述矩阵的所有日期都应该封装在一个结构中，以便将所有内容整齐地存储在一起。

• 目前，您将矩阵表示为行列表。 这对于打印和添加矩阵来说很好，但是一旦你进行乘法运算，你还需要列头。 然后，您的节点结构必须准备好有两个指针，如草图所示：一个用于行中的下一个元素（ right说），另一个用于列中的下一个元素（ below ）。

• 你的矩阵并不稀疏。 例如，您添加两个列表（不应该称为create_vector ;选择更具表现力的内容）的代码应该检查与节点关联的索引，以便可以跳过零条目。

• 您应该在结构中存储列表或矩阵的维度。 为了遍历列表，不需要这样做，但它允许快速检查操作是否合法。 例如，您只能添加相同维度的矩阵。

例如：

 typedef struct Matrix Matrix; typedef struct Matrixnode Matrixnode; struct Matrix { int n, m; Matrixnode *row; Matrixnode *col; }; Matrix *create_matrix(int n, int m) { Matrix *mx = malloc(sizeof(*mx)); mx->n = n; mx->m = m; mx->row = malloc(m * sizeof(*m->row)); mx->col = malloc(n * sizeof(*n->col)); return mx; } Matrix *matrix_add(const Matrix *a, const Matrix *b) { assert(a->m == b->m); assert(a->n == b->n); Matrix *c = create_matrix(a->n, a->m); for (int i = 0; i < c->m; i++) { c->row[i] = row_add(a->row[i], b->row[i]); } return c; } 

这是如何制作行向量数组的草图。 （我已经创建了一个col数组，但是没有使用它。当添加矩阵时，你必须注意保持列指针的一致性。）