创建使用链表在C稀疏矩阵 [英] Creating a sparse matrix using linked lists in C
问题描述
我有一个任务是创建两个稀疏矩阵（A和B），然后将其添加成第三稀疏矩阵（C）。我已经用向量（接收到两个稀疏向量和将它们添加到三分之一）做到了，所以我决定这将是更容易使用了一系列的载体重新present矩阵。在将来，我可能需要做没有载体，但与实际的基质（我甚至有插入数字变成稀疏矩阵功能的psuedo- code），所以不要理解的为什么我问了这一切，即使下面的code 有些工作
I have an assignment which is to create two sparse matrices (A and B) and then adding them up into a third sparse matrix (C). I have already done it with vectors (receiving two sparse vectors and adding them into a third) so I decided it would be easier to use a series of vectors to represent a matrix. In the future, I may need to do it without vectors but with an actual matrix (I even have a psuedo-code of a function that inserts a number into a sparse matrix), so do understand why I'm asking all of this, even though the following code somewhat works.
由于它是一个矩阵，它有两个数组的指针是该行阵列和列阵列。阵列的每个单元被指向各个行/列。这是因为下面的图片：
Because it is a matrix, it has two arrays of pointers that are the row array and column array. each cell of the array is pointing to the respective line/column. It is as in the picture below:
作为一个稀疏矩阵，那里有零，你看那些箭头那些与他们零节点不存在。
Being a sparse matrix, where there are zeroes, you see those arrows as those nodes that have zeroes with them do not exist.
要simplfy这个问题，我preFER只解决行，其中，为图像中看到的，都指向每个新行头的数组。假设每一行向量C（就像我上面说的，我要重新present了一系列向量的矩阵）。
To simplfy the problem, I prefer to only address the array of rows, which, as seen in the image, are pointing to the heads of each new row. Assume each line is a vector C (like I said above, I want to represent the matrix with a series of vectors).
这是所有的链接列表功能，我建的code：
This is the code of all of the linked list functions I built:
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");
}
这是创建矢量code：
This is the code that creates the vectors:
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; l<m; l++)
{
if ((Pointer_A->key + 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();
}
希望你走到这一步。所以我的问题是：
Hopefully you got this far. So my problems are:
-
我不知道如何创建一个我需要的三分球，这是Row_A，Row_B，Row_C的数组。也就是说，如果每个小区都指向到一个向量的头 - 我怎么定义数组？由于名单？清单节点？怎样使数组中的每一个细胞，使其指向每个向量的头上？
I'm not sure how to create the array of pointers that I need, which are Row_A, Row_B, Row_C. Meaning, if each cell is pointing into the head of a vector - how do I define the arrays? As list? List node? How do I make every cell of the array to point to each vector's head?
C组名单被重写每一个for循环执行时间。我看到，可以保持每个向量C，并把它在一个矩阵的唯一方法就是让每一个阵单元指向每个向量的头，这使我们又回到问题＃1。真的吗？我怎样才能做到这一点？
List C is overriden every time the for loop is executed. The only way I see that can keep each vector C and put it in a matrix is to make each array cell point to each vector's head, which brings us back to problem #1. Is that true? How can I do this?
非常感谢你。
推荐答案
一些观察，可能让你开始：
Some observations that may get you started:
-
您创建的负责人名单只是你
Row_A等创建动态数组的方式。元首这些清单不应该是独立的数据结构。他们应该是矩阵结构的一部分，就像头是列表<的一部分/ code>结构。头阵列的分配应该是它的创造者功能的一部分create_matrix。
You create list of heads just the way you create your dynamic arrays
Row_Aand so on. These lists of heads should not be standalone data structures. They should be part of aMatrixstruct, just asheadis part of yourListstruct. The allocation of the head array should be part of its creator functioncreate_matrix.
这是每个矩阵存储自己的头上名单，这一事实也解决覆盖 C ：而不是分配给 C 遍地，分配给 C-＆GT;头[I] 。同样，对于 A 和 B 。描述矩阵中所有日期应该在一个结构进行封装，使一切都整齐地存放在一起。
The fact that each Matrix stores its own list of heads is also the solution to overwriting C: Instead to assign to C over and over, assign to C->head[i]. Likewise for A and B. All date that describes the matrix should be encapsulated in one struct, so that everything is stored neatly together.
目前你重新present您的矩阵行的列表。这很好打印和矩阵加法，但一旦你到乘法，还需要列标题。然后，您的节点结构必须ppared有两个指针所示的草图$ P $：一为下一个元素的行中（右键，说的），一个用于列中的下一个元素（以下 ）。
At the moment you represent your matrix as a list of rows. That's fine for printing and for matrix addition, but once you get to multiplication, you will also need column heads. Your node structure must then be prepared to have two pointers as illustrated in the sketch: One for the next element in the row (right, say) and one for the next element in the columns (below).
您矩阵是不疏。例如，您的code以添加两个列表（这不应该叫 create_vector ;选择一些更EX pressive）应检查与相关指数节点，以便零条目可以跳过。
Your matrices are not sparse. For example, your code to add two lists (which shouldn't be called create_vector; chose something more expressive) should check the index associated with the nodes so that zero entries can be skipped.
您应该存储在结构列表或矩阵的维数。这不是必要的，以遍历列表，但它允许快速检查操作是否合法。例如，您只能添加同一维度的矩阵。
You should store the dimension of a list or matrix in the struct. This is not needed in order to traverse the list, but it allows to check quickly whether an operation is legal. For example, you can only add matrices of the same dimension.
例如：
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;
}
这是一个如何让行向量阵列的草图。 （我创建了一个山坳阵列，但不要使用它。当加入矩阵，你得把保持柱指针一致的，太照顾。）
This is a rough sketch of how you can make the row vectors arrays. (I've created a col array, but don't use it. When adding matrices, you'd have to take care of keeping the column pointers consistent, too.)
这篇关于创建使用链表在C稀疏矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
