数组
稀疏矩阵
结构定义
1
2
3
4
5
6
7
8
9
10
11
12
13
/*稀疏矩阵三元组表的类型定义*/
typedef struct {
int row, col; /*该非零元素的行下标和列下标*/
ElementType e; /*该非零元素的值*/
} Triple;
typedef struct {
int m, n, len; /*矩阵的行数、列数和非零元素的个数*/
Triple data[MAXSIZE + 1]; /* 非零元素的三元组表。data[0]未用*/
} TSMatrix;
十字链表
结构定义
1
2
3
4
5
6
7
8
9
10
11
12typedef struct OLNode {
int row, col; /*非零元素的行和列下标*/
int value;
struct OLNode *right; /*非零元素所在行表、列表的后继链域*/
struct OLNode *down;
} OLNode, *OLink;
typedef struct {
OLink *row_head; /*行、列链表的头指针向量*/
OLink *col_head;
int m, n, len; /*稀疏矩阵的行数、列数、非零元素的个数*/
} CrossList;创建十字链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46void CreateCrossList(CrossList *M, OLNode nodes[], int m, int n, int len) {
OLNode *p, *q;
int i, j, k, e;
M->m = m;
M->n = n;
M->len = len;
//创建行头数组并初始化
M->row_head = (OLink*)malloc((m+1)*sizeof(OLink));
for (i = 1; i <= m; ++i) M->row_head[i] = NULL;
//创建列头数组并初始化
M->col_head = (OLink*)malloc((n+1)*sizeof(OLink));
for (i = 1; i <= n; ++i) M->col_head[i] = NULL;
//根据nodes数组里的每一个数据
for (k = 0; k < len; ++k) {
//生成新结点并填入数据
p = (OLNode *)malloc(sizeof(OLNode));
p->row = i = nodes[k].row;
p->col = j = nodes[k].col;
p->value = e = nodes[k].value;
p->right = p->down = NULL;
//将新节点插入到行链表中
if (M->row_head[i] == NULL) //如果行链表为空。
M->row_head[i] = p;
else {
//寻找行表中的插入位置:工作指针q指向插入位置的前一个结点,然后插入
for (q = M->row_head[i]; q->right != NULL && q->right->col < j; q = q->right);
p->right = q->right;
q->right = p;
}
//将新节点插入到列链表中,方法类似于插入到行链表中
if (M->col_head[j] == NULL) //如果行链表为空。
M->col_head[j] = p;
else {
//寻找行表中的插入位置:工作指针q指向插入位置的前一个结点,然后插入
for (q = M->col_head[j]; q->down != NULL && q->down->row < i; q = q->down);
p->down = q->down;
q->down = p;
}
}
}