数据结构与算法教程，数据结构C语言版教程！（第五部分、数组和广义表详解）五

发布时间：2024年01月23日

?第五部分、数组和广义表详解

数组和广义表，都用于存储逻辑关系为“一对一”的数据。

数组存储结构，99% 的编程语言都包含的存储结构，用于存储不可再分的单一数据；而广义表不同，它还可以存储子广义表。

本章重点从矩阵的角度讨论二维数组的存储，同时讲解广义表的存储结构以及有关其广度和深度的算法实现。

九、行逻辑链接的顺序表实现矩阵乘法（附带C语言完整代码）

矩阵相乘的前提条件是：乘号前的矩阵的列数要和乘号后的矩阵的行数相等。且矩阵的乘法运算没有交换律，即 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 元素值）的情况。下面介绍使用行逻辑链接的顺序表计算矩阵乘积的方法。

1、行逻辑链接的顺序表解决矩阵乘积算法

对矩阵的乘积进行深度剖析，矩阵 A 和矩阵 B 相乘的运算过程是这样的：

首先，找到矩阵 A 中第一行的非 0 元素，分别是 A11?= 3和 A14?= 5；（由于行逻辑链接的顺序表中存储的都是非 0 元素，查找的过程就需要使用记录每行第一个非 0 元素的首地址的数组来完成）
用 3 去和 B 中对应的第一行中的非 0 元素相乘，矩阵 B 中第一行非 0 元素是 B12?= 2，所以 3*2 = 6 ，因为 6 是 A11?和 B12?相乘的结果，所以暂时存放在 C12?中；用 5 去和 B 中对应的第 4 行的非 0 元素相乘，由于矩阵 B 中第 4 行没有非 0 元素，所以，第一行的计算结束；
以此类推。

2、攻克问题难点

现在，解决问题的关键在于，如何知道顺序表中存放的非0元素是哪一行的呢？

解决方案：由于使用的是行逻辑链接的顺序表，所以，已经知道了每一个矩阵中的每一行有多少个非0元素，而且第一行的第一个非0元素的位置一定是1。

所以，第 n 行的非0元素的位置范围是：大于或等于第 n 行第一个元素的位置，小于第 n+1 行第一个元素的位置（如果是矩阵的最后一行，小于矩阵中非 0 元素的个数 + 1）。

3、具体实现代码

#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)

4、总结

当稀疏矩阵 $A_{mn}$ ?和稀疏矩阵 $B_{np}$ ?采用行逻辑链接的顺序表做乘法运算时，在矩阵 A 的列数（矩阵 B 的行数） n 不是很大的情况下，算法的时间复杂度相当于O(m*p)，比普通算法要快很多。???????

十、十字链表实现矩阵加法（附带C语言实现代码）

矩阵之间能够进行加法运算的前提条件是：各矩阵的行数和列数必须相等。

在行数和列数都相等的情况下，矩阵相加的结果就是矩阵中对应位置的值相加所组成的矩阵，例如：

图 1 矩阵相加

1、十字链表法

之前所介绍的都是采用顺序存储结构存储三元组，在类似于矩阵的加法运算中，矩阵中的数据元素变化较大（这里的变化主要为：非0元素变为0，0变为非0元素），就需要考虑采用另一种结构——链式存储结构来存储三元组。

采用链式存储结构存储稀疏矩阵三元组的方法，称为“十字链表法”。

2、十字链表法表示矩阵

例如，用十字链表法表示矩阵 A ，为：??

图 2 矩阵用十字链表法表示

由此可见，采用十字链表表示矩阵时，矩阵的每一行和每一个列都可以看作是一个单独的链表，而之所以能够表示矩阵，是因为行链表和列链表都分别存储在各自的数组中

图 2 中：存储行链表的数组称为?rhead 数组；存储列链表的数组称为?chead 数组。

3、十字链表中的结点

从图2中的十字链表表示矩阵的例子可以看到，十字链表中的结点由 5 部分组成：

图 3 十字链表中的结点

指针域A存储的是矩阵中结点所在列的下一个结点的地址（称为?“down域”）；
指针域B存储的是矩阵中该结点所在行的下一个结点的地址（称为?“right域”）；

用结构体自定义表示为：

typedef struct OLNode

{

????????int i,j,e; //矩阵三元组 i 代表行 j 代表列 e 代表当前位置的数据

????????struct OLNode *right,*down; //指针域右指针下指针

}OLNode,*OLink;

4、十字链表的结构

使用十字链表表示一个完整的矩阵，在了解矩阵中各结点的结构外，还需要存储矩阵的行数、列数以及非 0 元素的个数，另外，还需要将各结点链接成的链表存储在数组中。

所以，采用结构体自定义十字链表的结构，为：

typedef struct

{

???????? OLink *rhead,*chead; //存放各行和列链表头指针的数组

???????? int mu,nu,tu; //矩阵的行数,列数和非零元的个数

}CrossList;

5、十字链表存储矩阵三元组

由于三元组存储的是该数据元素的行标、列标和数值，所以，通过行标和列标，就能在十字链表中唯一确定一个位置。

判断方法为：在同一行中通过列标来判断位置；在同一列中通过行标来判断位置。

首先判断该数据元素 A（例如三元组为：（i，j，k））所在行的具体位置：

如果 A 的列标 j 值比该行第一个非 0 元素 B 的 j 值小，说明该数据元素在元素 B 的左侧，这时 A 就成为了该行第一个非0元素（也适用于当该行没有非 0 元素的情况，可以一并讨论）
如果 A 的列标 j 比该行第一个非 0 元素 B 的 j 值大，说明 A 在 B 的右侧，这时，就需要遍历该行链表，找到插入位置的前一个结点，进行插入。

对应行链表的位置确定之后，判断数据元素 A 在对应列的位置：

如果 A 的行标比该列第一个非 0 元素 B 的行标 i 值还小，说明 A 在 B 的上边，这时 A 就成了该列第一个非 0 元素。（也适用于该列没有非 0 元素的情况）
反之，说明 A 在 B 的下边，这时就需要遍历该列链表，找到要插入位置的上一个数据元素，进行插入。

实现代码：

//创建系数矩阵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;

}

6、十字链表解决矩阵相加问题

在解决 “将矩阵 B 加到矩阵 A ” 的问题时，由于采用的是十字链表法存储矩阵的三元组，所以在相加的过程中，针对矩阵 B 中每一个非 0 元素，需要判断在矩阵 A 中相对应的位置，有三种情况：

提取到的 B 中的三元组在 A 相应位置上没有非 0 元素，此时直接加到矩阵 A 该行链表的对应位置上；
提取到的 B 中三元组在 A 相应位置上有非 0 元素，且相加不为 0 ，此时只需要更改 A 中对应位置上的三元组的值即可；
提取到的 B 中三元组在 A 响应位置上有非 0 元素，但相加为 0 ，此时需要删除矩阵 A 中对应结点。

提示：算法中，只需要逐个提取矩阵 B 中的非 0 元素，然后判断矩阵 A 中对应位置上是否有非 0 元素，根据不同的情况，相应作出处理。

设指针 pa 和 pb 分别表示矩阵 A 和矩阵 B 中同一行中的结点（ pb 和 pa 都是从两矩阵的第一行的第一个非0元素开始遍历），以上 3 种情况还可以细分为以下几种场景：

当 pa==NULL 时，表明当前行（列）没有非 0 元素，此时可以直接将 pb 结点添加到当前行（列）中；
当 pa 结点的列值 j <?pb 结点的列值 j 时，表明 pb 结点的位置相对靠后，此时需要从 pa 结点处向后查找，找到第一个比 pb 结点列值 j 大的结点，将 pb 插入到该结点前面；
当 pb 结点的列值 j >?pb 结点的列值 j 时，和第 2 种情况类似，将 pb 结点插入到 pa 结点的前面；
当 pa 的列值 j ==?pb 的列值 j，且两结点的值相加结果不为 0 ，只需要更改 pa 指向的结点的值即可；
当 pa 的列值 j ==?pb 的列值 j ，但是两结点的值相加结果为 0 ，就需要从矩阵 A 的十字链表中删除 pa 指向的结点。

实现代码：

//实现 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;

}

7、完整代码演示

#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

8、总结

使用十字链表法解决稀疏矩阵的压缩存储的同时，在解决矩阵相加的问题中，对于某个单独的结点来说，算法的时间复杂度为一个常数（全部为选择结构），算法的整体的时间复杂度取决于两矩阵中非 0 元素的个数。

文章来源:https://blog.csdn.net/sinat_41942180/article/details/135175982
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！