数组和广义表,都用于存储逻辑关系为“一对一”的数据。
数组存储结构,99% 的编程语言都包含的存储结构,用于存储不可再分的单一数据;而广义表不同,它还可以存储子广义表。
本章重点从矩阵的角度讨论二维数组的存储,同时讲解广义表的存储结构以及有关其广度和深度的算法实现。
矩阵相乘的前提条件是:乘号前的矩阵的列数要和乘号后的矩阵的行数相等。且矩阵的乘法运算没有交换律,即 A*B 和 B*A 是不一样的。
例如,矩阵 A:
矩阵 B:
由于矩阵 A 的列数和矩阵 B 的行数相等,可以进行 A*B 运算(不能进行 B*A 运算)。计算方法是:用矩阵A的第 i 行和矩阵B中的每一列 j 对应的数值做乘法运算,乘积一一相加,所得结果即为矩阵 C 中第 i 行第 j 列的值。
得到的乘积矩阵 C 为:
例如:C12?= 6 是因为:A11*B12?+ A12*B22?+ A13*B32?+ A14*B42,即 3*2 + 0*0 + 0*4 + 5*0 = 6 ,因为这是 A 的第 1 行和 B 的第 2 列的乘积和,所以结果放在 C 的第 1 行第 2 列的位置。
例如,A是 m1*n1 矩阵,B是 m2*n2 矩阵(前提必须是 n1 == m2 ):
int C[MAX][MAX];
for (int i=0; i<m1;i++) {
????????for (int j=0; j<n2; j++) {
????????????????C[i][j]=0;
????????????????for (int k=0; k<n1; k++) {
????????????????????????C[i][j]+=A[i][k]*B[k][j];
????????????????}
????????}
}
普通算法的时间复杂度为。
在稀疏矩阵做乘法运算时,由于本身矩阵中含有的非 0 元素少,普通算法会出现很多 0*0 或者 k*0 或者 0*k ( k 代表非 0 元素值)的情况。下面介绍使用行逻辑链接的顺序表计算矩阵乘积的方法。
对矩阵的乘积进行深度剖析,矩阵 A 和矩阵 B 相乘的运算过程是这样的:
现在,解决问题的关键在于,如何知道顺序表中存放的非0元素是哪一行的呢?
解决方案:由于使用的是行逻辑链接的顺序表,所以,已经知道了每一个矩阵中的每一行有多少个非0元素,而且第一行的第一个非0元素的位置一定是1。
所以,第 n 行的非0元素的位置范围是:大于或等于第 n 行第一个元素的位置, 小于第 n+1 行第一个元素的位置(如果是矩阵的最后一行, 小于矩阵中非 0 元素的个数 + 1)。
#include <stdio.h>
#define MAXSIZE 1200#define MAXRC 100
#define ElemType int
typedef struct { ???
????????int i, j;//行,列 ???
????????ElemType e;//元素值
}Triple;
typedef struct
{ ???
????????Triple? data[MAXSIZE + 1]; ???
????????int rpos[MAXRC + 1];//每行第一个非零元素在data数组中的位置 ???
????????int mu, nu, tu;//行数,列数,元素个数
}RLSMatrix;
RLSMatrix MultSMatrix(RLSMatrix A, RLSMatrix B, RLSMatrix C)
{
????????//如果矩阵A的列数与矩阵B的行数不等,则不能做矩阵乘运算 ???
????????if (A.nu != B.mu) ???????
????????????????return C; ???
????????C.mu = A.mu; ???
????????C.nu = B.nu; ???
????????C.tu = 0; ???
????????//如果其中任意矩阵的元素个数为零,做乘法元素没有意义,全是0 ???
????????if (A.tu * B.tu == 0) ???????
????????????????return C; ???
????????else ???
????????{ ???????
????????????????int arow; ???????
????????????????int ccol; ???????
????????????????//遍历矩阵A的每一行 ???????
????????????????for (arow = 1; arow <= A.mu; arow++) ??????
????????????????{ ????????
????????????????????????//创建一个临时存储乘积结果的数组,且初始化为0,遍历每次都需要清空 ????????????????????????int ctemp[MAXRC + 1]; ???????????
????????????????????????for (int i = 0; i < MAXRC + 1; i++) { ???????????????
????????????????????????????????ctemp[i] = 0; ???????????
????????????????????????} ???????????
????????????????????????C.rpos[arow] = C.tu + 1; ???????????
????????????????????????//根据行数,在三元组表中找到该行所有的非0元素的位置 ???????????
????????????????????????int tp; ???????????
????????????????????????if (arow < A.mu) ???????????????
????????????????????????????????tp = A.rpos[arow + 1];//获取矩阵A的下一行第一个非零元素在data数组中位置 ???????????
????????????????????????else ???????????????
????????????????????????????????tp = A.tu + 1;//若当前行是最后一行,则取最后一个元素+1 ???????????
????????????????????????int p; ???????????
????????????????????????int brow; ???????????
????????????????????????//遍历当前行的所有的非0元素 ???????????
????????????????????????for (p = A.rpos[arow]; p < tp; p++) ???????????
????????????????????????{ ???????????????
????????????????????????????????brow = A.data[p].j;//取该非0元素的列数,便于去B中找对应的做乘积的非0元素 ???????????????
????????????????????????????????int t; ???????????????
????????????????????????????????// 判断如果对于A中非0元素,找到矩阵B中做乘法的那一行中的所有的非0元素 ???????????????
????????????????????????????????if (brow < B.mu) ???????????????????
????????????????????????????????????????t = B.rpos[brow + 1]; ???????????????
????????????????????????????????else ???????????????????
????????????????????????????????????????t = B.tu + 1; ???????????????
????????????????????????????????int q; ???????????????
????????????????????????????????//遍历找到的对应的非0元素,开始做乘积运算 ???????????????
????????????????????????????????for (q = B.rpos[brow]; q < t; q++) ?????
????????????????????????????????{ ???????????????????
????????????????????????????????????????//得到的乘积结果,每次和ctemp数组中相应位置的数值做加和运算?
????????????????????????????????????????ccol = B.data[q].j; ???????????????????
????????????????????????????????????????ctemp[ccol] += A.data[p].e * B.data[q].e; ???????????????
????????????????????????????????} ???????????
????????????????????????} ???????????
????????????????????????//矩阵C的行数等于矩阵A的行数,列数等于矩阵B的列数,所以,得到的ctemp存储的结果,也会在C的列数的范围内 ???????????
????????????????????????for (ccol = 1; ccol <= C.nu; ccol++) ???????????
????????????????????????{ ???????????????
????????????????????????????????//由于结果可以是0,而0不需要存储,所以在这里需要判断 ???????????????
????????????????????????????????if (ctemp[ccol]) ???????????????
????????????????????????????????{ ???????????????????
????????????????????????????????????????//不为0,则记录矩阵中非0元素的个数的变量tu要+1;且该值不能超过存放三元素数组的空间大小 ???????????????????
????????????????????????????????????????if (++C.tu > MAXSIZE) ???????????????????????
????????????????????????????????????????????????return C; ???????????????????
????????????????????????????????????????else { ???????????????????????
????????????????????????????????????????????????C.data[C.tu].e = ctemp[ccol]; ???????????????????????
????????????????????????????????????????????????C.data[C.tu].i = arow; ???????????????????????
????????????????????????????????????????????????C.data[C.tu].j = ccol; ???????????????????
????????????????????????????????????????} ???????????????
????????????????????????????????} ???????????
????????????????????????} ???????
????????????????} ???????
????????????????return C; ???
????????}
}
int main(int argc, char* argv[])
{ ???
????????RLSMatrix M, N, T; ???
????????M.tu = 4; ???
????????M.mu = 3; ???
????????M.nu = 4; ???
????????M.rpos[1] = 1; ???
????????M.rpos[2] = 3; ???
????????M.rpos[3] = 4; ???
????????M.data[1].e = 3; ???
????????M.data[1].i = 1; ???
????????M.data[1].j = 1; ???
????????M.data[2].e = 5; ???
????????M.data[2].i = 1; ???
????????M.data[2].j = 4; ???
????????M.data[3].e = -1; ???
????????M.data[3].i = 2; ???
????????M.data[3].j = 2; ???
????????M.data[4].e = 2; ???
????????M.data[4].i = 3; ???
????????M.data[4].j = 1; ???
????????N.tu = 4; ???
????????N.mu = 4; ???
????????N.nu = 2; ???
????????N.rpos[1] = 1; ???
????????N.rpos[2] = 2; ???
????????N.rpos[3] = 3; ???
????????N.rpos[4] = 5; ???
????????N.data[1].e = 2; ???
????????N.data[1].i = 1; ???
????????N.data[1].j = 2; ???
????????N.data[2].e = 1; ???
????????N.data[2].i = 2; ???
????????N.data[2].j = 1; ???
????????N.data[3].e = -2; ???
????????N.data[3].i = 3; ???
????????N.data[3].j = 1; ???
????????N.data[4].e = 4; ???
????????N.data[4].i = 3; ???
????????N.data[4].j = 2; ???
????????T = MultSMatrix(M, N, T); ???????
????????for (int i = 1; i <= T.tu; i++) { ???????
????????????????printf("(%d,%d,%d)\n", T.data[i].i, T.data[i].j, T.data[i].e); ???
????????} ???
????????return 0;
}
??????
输出结果:
(1,2,6)
(2,1,-1)
(3,2,4)
当稀疏矩阵 ?和稀疏矩阵?采用行逻辑链接的顺序表做乘法运算时,在矩阵 A 的列数(矩阵 B 的行数) n 不是很大的情况下,算法的时间复杂度相当于O(m*p)
,比普通算法要快很多。???????
矩阵之间能够进行加法运算的前提条件是:各矩阵的行数和列数必须相等。
在行数和列数都相等的情况下,矩阵相加的结果就是矩阵中对应位置的值相加所组成的矩阵,例如:
图 1 矩阵相加
之前所介绍的都是采用顺序存储结构存储三元组,在类似于矩阵的加法运算中,矩阵中的数据元素变化较大(这里的变化主要为:非0元素变为0,0变为非0元素),就需要考虑采用另一种结构——链式存储结构来存储三元组。
采用链式存储结构存储稀疏矩阵三元组的方法,称为“十字链表法”。
例如,用十字链表法表示矩阵 A ,为:??
图 2 矩阵用十字链表法表示
由此可见,采用十字链表表示矩阵时,矩阵的每一行和每一个列都可以看作是一个单独的链表,而之所以能够表示矩阵,是因为行链表和列链表都分别存储在各自的数组中
图 2 中:存储行链表的数组称为?rhead 数组;存储列链表的数组称为?chead 数组。
从图2中的十字链表表示矩阵的例子可以看到,十字链表中的结点由 5 部分组成:
图 3 十字链表中的结点
指针域A存储的是矩阵中结点所在列的下一个结点的地址(称为?“down域”);
指针域B存储的是矩阵中该结点所在行的下一个结点的地址(称为?“right域”);
用结构体自定义表示为:
typedef struct OLNode
{
????????int i,j,e; //矩阵三元组 i 代表行 j 代表列 e 代表当前位置的数据
????????struct OLNode *right,*down; //指针域 右指针 下指针
}OLNode,*OLink;
使用十字链表表示一个完整的矩阵,在了解矩阵中各结点的结构外,还需要存储矩阵的行数、列数以及非 0 元素的个数,另外,还需要将各结点链接成的链表存储在数组中。
所以,采用结构体自定义十字链表的结构,为:
typedef struct
{
???????? OLink *rhead,*chead; //存放各行和列链表头指针的数组
???????? int mu,nu,tu; //矩阵的行数,列数和非零元的个数
}CrossList;
由于三元组存储的是该数据元素的行标、列标和数值,所以,通过行标和列标,就能在十字链表中唯一确定一个位置。
判断方法为:在同一行中通过列标来判断位置;在同一列中通过行标来判断位置。
首先判断该数据元素 A(例如三元组为:(i,j,k))所在行的具体位置:
对应行链表的位置确定之后,判断数据元素 A 在对应列的位置:
实现代码:
//创建系数矩阵M,采用十字链表存储表示
CrossList CreateMatrix_OL(CrossList M)
{
????????int m,n,t;
????????int i,j,e;
????????OLNode *p,*q;//定义辅助变量
????????scanf("%d%d%d",&m,&n,&t); //输入矩阵的行列及非零元的数量
????????//初始化矩阵的行列及非零元的数量
????????M.mu=m;
????????M.nu=n;
????????M.tu=t;
????????if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink)))||!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink))))
????????{
????????????????printf("初始化矩阵失败");
????????????????exit(0); //初始化矩阵的行列链表
????????}
????????for(i=1;i<=m;i++)
????????{
????????????????M.rhead[i]=NULL; //初始化行
????????}
????????for(j=1;j<=n;j++)
????????{
????????????????M.chead[j]=NULL; //初始化列
????????}
????????for(scanf("%d%d%d",&i,&j,&e);0!=i;scanf("%d%d%d",&i,&j,&e)) //输入三元组 直到行为0结束
????????{
????????????????if(!(p=(OLNode*)malloc(sizeof(OLNode))))
????????????????{
????????????????????????printf("初始化三元组失败");
????????????????????????exit(0); //动态生成p
????????????????}
????????????????p->i=i;
????????????????p->j=j;
????????????????p->e=e; //初始化p
????????????????if(NULL==M.rhead[i]||M.rhead[i]->j>j)
????????????????{
????????????????????????p->right=M.rhead[i];
????????????????????????M.rhead[i]=p;
????????????????}
????????????????else
????????????????{
????????????????????????for(q=M.rhead[i];(q->right)&&q->right->j<j;q=q->right);
????????????????????????p->right=q->right;
????????????????????????q->right=p;
????????????????}
????????if(NULL==M.chead[j]||M.chead[j]->i>i)
????????{
????????????????p->down=M.chead[j];
????????????????M.chead[j]=p;
????????}
????????else
????????{
????????????????for (q=M.chead[j];(q->down)&& q->down->i<i;q=q->down);
????????????????????????p->down=q->down;
????????????????????????q->down=p;
????????????????}
????????}
????????return M;
}
在解决 “将矩阵 B 加到矩阵 A ” 的问题时,由于采用的是十字链表法存储矩阵的三元组,所以在相加的过程中,针对矩阵 B 中每一个非 0 元素,需要判断在矩阵 A 中相对应的位置,有三种情况:
提示:算法中,只需要逐个提取矩阵 B 中的非 0 元素,然后判断矩阵 A 中对应位置上是否有非 0 元素,根据不同的情况,相应作出处理。
设指针 pa 和 pb 分别表示矩阵 A 和矩阵 B 中同一行中的结点( pb 和 pa 都是从两矩阵的第一行的第一个非0元素开始遍历),以上 3 种情况还可以细分为以下几种场景:
实现代码:
//实现 N 和 M 两个矩阵相加
CrossList AddSMatrix(CrossList M, CrossList N) {
????????OLink p, q;
????????int k = 1;
????????//遍历 N 矩阵中的每一列
????????for (; k <= N.mu; k++) {
????????????????p = N.rhead[k];
????????????????//提取当前列中的每个非 0 元素,调用 insertToMatrix() 函数将其添加到 M 矩阵中
????????????????while (p)
????????????????{
????????????????????????q = (OLink)malloc(sizeof(OLNode));
????????????????????????q->i = p->i;
????????????????????????q->j = p->j;
????????????????????????q->e = p->e;
????????????????????????q->down = NULL;
????????????????????????q->right = NULL;
????????????????????????//将 q 结点添加到 M 矩阵中
????????????????????????M = insertToMatrix(M, q);
????????????????????????p = p->right;
????????????????}
????????}
????????return M;
}
//实现将指定 p 结点添加到 M 矩阵中
CrossList insertToMatrix(CrossList M, OLink p) {
????????int i = p->i, j = p->j;
????????//de标记是否需要删除结点(1 表示删除结点,0表示不删除),pl标记是否需要添加结点(1表示不添加结点,0表示添加)
????????int de = 0, pl = 0;
????????//从行的角度将 p 结点链接到 M 矩阵的适当位置
????????//第 1 种场景,如果当前行没有非 0 元素,直接将 p 结点链接到对应的行。
????????if (M.rhead[i] == NULL)
????????{
????????????????M.rhead[i] = p;
????????????????M.tu++;
????????}
????????//当前行有非 0 元素
????????else
????????{
????????????????OLink q = M.rhead[i];
????????????????OLink pre = q;
????????????????//解决第 2 种情况
????????????????while (q && (q->j < p->j))//用两个指针找到该元素块应该插到那个位置
????????????????{
????????????????????????pre = q;
????????????????????????q = q->right;
????????????????}
????????????????//解决第4、5 种情况
????????????????if (q != NULL && (q->j == p->j))
????????????????{
????????????????????????q->e += p->e;
????????????????????????if (q->e == 0)
????????????????????????{
????????????????????????????????if (pre == q)
????????????????????????????????????????M.rhead[i] = q->right;
????????????????????????????????else
???????????????????????????????????????? pre->right = q->right;
????????????????????????????????M.tu--;
????????????????????????????????//需要删除结点,但不是现在删除,而是等到处理完列链表之后再删除
????????????????????????????????de = 1;
????????????????????????}
????????????????????????else
????????????????????????????????//不需要添加新的结点
????????????????????????????????pl = 1;
????????????????}
????????????????//对需要添加新结点的情况(第 2 和第 3 种情况)
????????????????if (de == 0 && pl == 0)
????????????????{
????????????????????????//直接将 p 添加到行链表头
????????????????????????if (pre == q)
????????????????????????{
????????????????????????????????M.rhead[i] = p;
????????????????????????????????p->right = q;
????????????????????????}
????????????????????????else
????????????????????????{
????????????????????????????????//将 p 添加到 pre 之后
????????????????????????????????pre->right = p; p->right = q;
????????????????????????}
????????????????????????M.tu++;
????????????????}
????????}
????????//从列的角度实现将 p 添加到 M 矩阵中
????????//解决第 1 种情况
????????if (M.chead[j] == NULL)
???????????????? M.chead[j] = p;//列的插入与行类似
????????else {
????????????????OLink q = M.chead[j];
????????????????OLink pre = q;
????????????????//解决第 2 种情况
????????????????while (q && (q->i < p->i))
????????????????{
????????????????????????pre = q;
????????????????????????q = q->down;
????????????????}
????????????????//当需要删除结点时,将 q 结点从列链表中摘除,然后释放 q 和 p
????????????????if (de == 1)
????????????????{
????????????????????????if (q != NULL)
????????????????????????{
????????????????????????????????if (pre == q)
????????????????????????????????????????M.chead[j] = q->down;
????????????????????????????????else
????????????????????????????????????????pre->down = q->down;
????????????????????????????????free(q);
????????????????????????????????free(p);//如果AB对应元素相加为0,将这个元素从链表中删除后再free掉
????????????????????????????????return M;
????????????????????????}
????????????????}
????????????????//当需要添加结点时(第 1、2、3种情况),将新结点链接到对应的列链表中
????????????????if (pl == 0)
????????????????{
????????????????????????if (pre == q)
????????????????????????{
????????????????????????????????M.chead[j] = p;
????????????????????????????????p->down = q;
????????????????????????}
????????????????????????else
????????????????????????{
????????????????????????????????pre->down = p;
????????????????????????????????p->down = q;
????????????????????????}
????????????????}
????????}
????????return M;
}
#include<stdio.h>
#include<stdlib.h>
typedef struct OLNode
{
????????int i, j, e; //矩阵三元组i代表行 j代表列 e代表当前位置的数据
????????struct OLNode* right, * down; //指针域 右指针 下指针
}OLNode, * OLink;
typedef struct
{
????????OLink* rhead, * chead; //行和列链表头指针
????????int mu, nu, tu; //矩阵的行数,列数和非零元的个数
}CrossList;
CrossList CreateMatrix_OL(CrossList M);
//实现 N+M
CrossList AddSMatrix(CrossList M, CrossList N);
//将 q 结点添加到 M 矩阵中
CrossList insertToMatrix(CrossList M, OLink q);
//输出 M 矩阵每一列中的非 0 元素
void displayL(CrossList M);
//输出 M 矩阵每一行中的非 0 元素
void displayR(CrossList M);
int main()
{
????????CrossList M, N;
????????M.rhead = NULL;
????????M.chead = NULL;
????????N.rhead = NULL;
????????N.chead = NULL;
????????printf("输入测试矩阵M:\n");
????????M = CreateMatrix_OL(M);
????????printf("输入测试矩阵N:\n");
????????N = CreateMatrix_OL(N);
????????//调用 addSMatrix() 函数实现 N+M
????????M = AddSMatrix(M, N);
????????printf("矩阵相加的结果为:\n");
????????displayR(M);
????????//displayL(M);
????????return 0;
}
//创建系数矩阵M,采用十字链表存储表示
CrossList CreateMatrix_OL(CrossList M)
{
????????int m, n, t;
????????int i, j, e;
????????OLNode* p, * q;//定义辅助变量
????????scanf("%d%d%d", &m, &n, &t);//输入矩阵的行列及非零元的数量
????????//初始化矩阵的行列及非零元的数量
????????M.mu = m;
????????M.nu = n;
????????M.tu = t;
????????if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink))))
????????{
????????????????printf("初始化矩阵失败");
????????????????exit(0); //初始化矩阵的行列链表
????????}
????????for (i = 1; i <= m; i++)
????????{
????????????????M.rhead[i] = NULL; //初始化行
????????}
????????for (j = 1; j <= n; j++)
????????{
????????????????M.chead[j] = NULL; //初始化列
????????}
????????for (scanf("%d%d%d", &i, &j, &e); 0 != i; scanf("%d%d%d", &i, &j, &e)) //输入三元组 直到行为0结束
????????{
????????????????if (!(p = (OLNode*)malloc(sizeof(OLNode))))
????????????????{
????????????????????????printf("初始化三元组失败");
????????????????????????exit(0); //动态生成p
????????????????}
????????????????p->i = i;
????????????????p->j = j;
????????????????p->e = e; //初始化p
????????????????if (NULL == M.rhead[i] || M.rhead[i]->j > j)
????????????????{
????????????????????????p->right = M.rhead[i];
????????????????????????M.rhead[i] = p;
????????????????}
????????????????else
????????????????{
????????????????????????for (q = M.rhead[i]; (q->right) && q->right->j < j; q = q->right);
????????????????????????p->right = q->right;
????????????????????????q->right = p;
????????????????}
????????????????if (NULL == M.chead[j] || M.chead[j]->i > i)
????????????????{
????????????????????????p->down = M.chead[j];
????????????????????????M.chead[j] = p;
????????????????}
????????????????else
????????????????{
????????????????????????for (q = M.chead[j]; (q->down) && q->down->i < i; q = q->down);
????????????????????????p->down = q->down;
????????????????????????q->down = p;
????????????????}
????????}
????????return M;
}
//实现 N 和 M 两个矩阵相加
CrossList AddSMatrix(CrossList M, CrossList N) {
????????OLink p, q;
????????int k = 1;
????????//遍历 N 矩阵中的每一列
????????for (; k <= N.mu; k++) {
????????????????p = N.rhead[k];
????????????????//提取当前列中的每个非 0 元素,调用 insertToMatrix() 函数将其添加到 M 矩阵中
????????????????while (p)
????????????????{
????????????????????????q = (OLink)malloc(sizeof(OLNode));
????????????????????????q->i = p->i;
????????????????????????q->j = p->j;
????????????????????????q->e = p->e;
????????????????????????q->down = NULL;
????????????????????????q->right = NULL;
????????????????????????//将 q 结点添加到 M 矩阵中
????????????????????????M = insertToMatrix(M, q);
????????????????????????p = p->right;
????????????????}
????????}
????????return M;
}
//实现将指定 p 结点添加到 M 矩阵中
CrossList insertToMatrix(CrossList M, OLink p) {
????????int i = p->i, j = p->j;
????????//de标记是否需要删除结点(1 表示删除结点,0表示不删除),pl标记是否需要添加结点(1表示不添加结点,0表示添加)
????????int de = 0, pl = 0;
????????//从行的角度将 p 结点链接到 M 矩阵的适当位置
????????//第 1 种场景,如果当前行没有非 0 元素,直接将 p 结点链接到对应的行。
????????if (M.rhead[i] == NULL)
????????{
????????????????M.rhead[i] = p;
????????????????M.tu++;
????????}
????????//当前行有非 0 元素
????????else
????????{
????????????????OLink q = M.rhead[i];
????????????????OLink pre = q;
????????????????//解决第 2 种情况
????????????????while (q && (q->j < p->j))//用两个指针找到该元素块应该插到那个位置
????????????????{
????????????????????????pre = q;
????????????????????????q = q->right;
????????????????}
????????????????//解决第4、5 种情况
????????????????if (q != NULL && (q->j == p->j))
????????????????{
????????????????????????q->e += p->e;
????????????????????????if (q->e == 0)
????????????????????????{
????????????????????????????????if (pre == q)
????????????????????????????????????????M.rhead[i] = q->right;
????????????????????????????????else
????????????????????????????????????????pre->right = q->right;
????????????????????????????????M.tu--;
????????????????????????????????//需要删除结点,但不是现在删除,而是等到处理完列链表之后再删除
????????????????????????????????de = 1;
????????????????????????}
????????????????????????else
????????????????????????????????//不需要添加新的结点
????????????????????????????????pl = 1;
????????????????}
????????????????//对需要添加新结点的情况(第 2 和第 3 种情况)
????????????????if (de == 0 && pl == 0)
????????????????{
????????????????????????//直接将 p 添加到行链表头
????????????????????????if (pre == q)
????????????????????????{
????????????????????????????????M.rhead[i] = p;
????????????????????????????????p->right = q;
????????????????????????}
????????????????????????else
????????????????????????{
????????????????????????????????//将 p 添加到 pre 之后
????????????????????????????????pre->right = p;
????????????????????????????????p->right = q;
????????????????????????}
????????????????????????M.tu++;
????????????????}
????????}
????????//从列的角度实现将 p 添加到 M 矩阵中
????????//解决第 1 种情况
????????if (M.chead[j] == NULL)
????????????????M.chead[j] = p;//列的插入与行类似
????????else {
????????????????OLink q = M.chead[j];
????????????????OLink pre = q;
????????????????//解决第 2 种情况
????????????????while (q && (q->i < p->i))
????????????????{
????????????????????????pre = q;
????????????????????????q = q->down;
????????????????}
????????????????//当需要删除结点时,将 q 结点从列链表中摘除,然后释放 q 和 p
????????????????if (de == 1)
????????????????{
????????????????????????if (q != NULL)
????????????????????????{
????????????????????????????????if (pre == q)
????????????????????????????????????????M.chead[j] = q->down;
????????????????????????????????else
????????????????????????????????????????pre->down = q->down;
????????????????????????????????free(q);
????????????????????????????????free(p);//如果AB对应元素相加为0,将这个元素从链表中删除后再free掉
????????????????????????????????return M;
????????????????????????}
????????????????}
????????????????//当需要添加结点时(第 1、2、3种情况),将新结点链接到对应的列链表中
????????????????if (pl == 0)
????????????????{
????????????????????????if (pre == q)
????????????????????????{
????????????????????????????????M.chead[j] = p;
????????????????????????????????p->down = q;
????????????????????????}
????????????????????????else
????????????????????????{
????????????????????????????????pre->down = p;
????????????????????????????????p->down = q;
????????????????????????}
????????????????}
????????}
????????return M;
}
void displayL(CrossList M) {
????????int i;
????????printf("---------------------\ni\tj\te\n---------------------\n");
????????for (i = 1; i <= M.nu; i++)
????????{
????????????????if (NULL != M.chead[i])
????????????????{
????????????????????????OLink p = M.chead[i];
????????????????????????while (NULL != p)
????????????????????????{
????????????????????????????????printf("%d\t%d\t%d\n", p->i, p->j, p->e);
????????????????????????????????p = p->down;
????????????????????????}
????????????????}
????????}
}
void displayR(CrossList M) {
????????int i;
????????printf("---------------------\ni\tj\te\n---------------------\n");
????????for (i = 1; i <= M.mu; i++)
????????{
????????????????if (NULL != M.rhead[i])
????????????????{
????????????????????????OLink p = M.rhead[i];
????????????????????????while (NULL != p)
????????????????????????{
????????????????????????????????printf("%d\t%d\t%d\n", p->i, p->j, p->e);
????????????????????????????????p = p->right;
????????????????????????}
????????????????}
????????}
}
运行结果:
输入测试矩阵M:
3 3 3
1 2 1
2 1 1
3 3 1
0 0 0
输入测试矩阵N:
3 3 4
1 2 -1
1 3 1
2 3 1
3 1 1
0 0 0
矩阵相加的结果为:
---------------------
i?????? j?????? e
---------------------
1?????? 3?????? 1
2?????? 1?????? 1
2?????? 3?????? 1
3?????? 1?????? 1
3?????? 3?????? 1
使用十字链表法解决稀疏矩阵的压缩存储的同时,在解决矩阵相加的问题中,对于某个单独的结点来说,算法的时间复杂度为一个常数(全部为选择结构),算法的整体的时间复杂度取决于两矩阵中非 0 元素的个数。