西北工业大学noj_西工大noj

【十字链表为存储结构实现矩阵相加】

**
用十字链表为存储结构实现矩阵相加 B = B + A

#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>

typedef struct OLNode										//十字链表存储单元
{
    int row, col;
    int data;
    struct OLNode *right, *down;
} OLNode, *OLink;
typedef struct CrossList									//十字链表
{
    OLink *row_head, *col_head;
    int m, n, len;
} CrossList;

void CreatCrossList(CrossList* M, int m, int n, int len)
//创建以十字链表为存储结构的稀疏矩阵
{
    M->m = m, M->n = n, M->len = len;						//读入行列数和非零元素个数
    
    M->row_head = (OLink*)malloc(sizeof(OLink) * (m + 1));	//给头指针向量分配空间
    if(M->row_head == NULL) return;							//判断是否为空指针
    M->col_head = (OLink*)malloc(sizeof(OLink) * (n + 1));
    if(M->col_head == NULL) return;
    
    for(int i = 0; i <= m; i++)								//初始化头指针向量为空
        M->row_head[i] = NULL;
    for(int i = 0; i <= n; i++)
        M->col_head[i] = NULL;
        
    int i, j, e;											//开始读入数据
    for(int k = 0; k < M->len; k++)
    {
        scanf("%d %d %d", &i, &j, &e);
        OLink p = (OLink)malloc(sizeof(OLNode));			//创建一个结点
        if(p == NULL) return;
        p->row = i, p->col = j, p->data = e;				//将数据赋给创建的结点
        p->right = p->down =NULL;							//初始化指针
        
        //横向分配存储位置
        OLink q;
        if(M->row_head[i] == NULL)							//该行头指针为空
            M->row_head[i] = p;
        else if(M->row_head[i]->col > j)					//该行第一个结点列数大于该结点
        {
            p->right = M->row_head[i];
            M->row_head[i] = p;
        }
        else												//该行第一个结点列数小于该结点
        {
            for(q = M->row_head[i]; q->right && 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 if(M->col_head[j]->row > i)
        {
            p->down = M->col_head[j]->down;
            M->col_head[j] = p;
        }
        else
        {
            for(q = M->col_head[j]; q->down && q->down->row < i; q = q->down);
            p->down = q->down;
            q->down = p;
        }
    }
}

void Insert(CrossList *M, OLink q)
//单个非零元素插入十字链表矩阵中
//借用创建十字链表矩阵的思想，只是多了可能会在相同位置的情况，且若相加后为零，还可能删除结点
{
    int i = q->row, j = q->col;						//i，j存放非零元素的行列数
    OLink p;
    
    if(M->row_head[i] == NULL)						//该行没有元素，直接插入
            M->row_head[i] = q;
    else if(M->row_head[i]->col > j)				//该行第一个元素列坐标大于该元素列坐标
    {	
        q->right = M->row_head[i];
        M->row_head[i] = q;
    }
    else if(M->row_head[i]->col == j)				//该行第一个元素和该元素在同一个位置
    {
        M->row_head[i]->data = M->row_head[i]->data + q->data;
        if(M->row_head[i]->data == 0)				//相加后等于零，删除结点
            M->row_head[i] = M->row_head[i]->right;
    }
    else											//该行第一个元素列坐标小于该元素列坐标
    {
        for(p = M->row_head[i]; p->right && p->right->col < j; p = p->right);//空循环
        if(p->right == NULL)						//该行所有元素列坐标都小于该元素
            p->right = q;
        else if(p->right->col > j)					//该元素列坐标大小介于该行两个元素之间
        {
            q->right = p->right;
            p->right = q;
        }
        else										//该元素列坐标大小等于该行某个个元素（不为第一个元素）
        {
            p->right->data = p->right->data + q->data;
            if(p->right->data == 0)					//相加等于零，删除结点
                    p->right = p->right->right;
        }
    }
}
void AddCrossList(CrossList* A, CrossList* B)
{
    OLink p = (OLNode*)malloc(sizeof(OLNode));
    for(int k = 1; k <= A->m; k++)
    {
        p = A->row_head[k];
        while(p)
        {
            OLink q =(OLNode*)malloc(sizeof(OLNode));
            //重新分配结点，目的是不改变原来的A十字链表矩阵
            q->data = p->data;
            q->row = p->row;
            q->col = p->col;
            q->right = q->down = NULL;
            Insert(B, q);						//一行一行逐个逐个插入到B十字链表矩阵中去
            p = p->right;
        }
    }
}

void Print(CrossList *M)						//打印B的稀疏矩阵（三元组形式）
{
    OLink p = (OLNode*)malloc(sizeof(OLNode));
    for(int k = 1; k <= M->len; k++)			//一行一行地扫描打印
    {
        p = M->row_head[k];
        while(p)
        {
            printf("%d %d %d\n", p->row, p->col, p->data);
            p = p->right;
        }
    }
}

int main()
{
    int m, n, len1, len2;
    scanf("%d %d %d %d", &m, &n, &len1, &len2);		//读入矩阵行列数，非零元个数
    CrossList *A, *B;
    A = (CrossList*)malloc(sizeof(CrossList));		//创建十字链表矩阵
    B = (CrossList*)malloc(sizeof(CrossList));
    CreatCrossList(A, m, n, len1);
    CreatCrossList(B, m, n, len2);
    AddCrossList(A, B);								//矩阵相加
    Print(B);										//输出相加后的矩阵
    return 0;
}

[题目介绍](https://img-blog.csdnimg.cn/d84c53b2607a4926ade0c2c925659223.png#pic_center)

测试数据：
3 4 3 2
1 1 1 
1 3 1
2 2 2
1 2 1
2 2 3

正确输出：
1 1 1
1 2 1
1 3 1
2 2 5

## 西北工业大学数据结构noj

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177