网站建设工作成果怎么写,临海网站开发公司,seo刷网站,网站页面设计内容第五部分、数组和广义表详解 数组和广义表#xff0c;都用于存储逻辑关系为“一对一”的数据。
数组存储结构#xff0c;99% 的编程语言都包含的存储结构#xff0c;用于存储不可再分的单一数据#xff1b;而广义表不同#xff0c;它还可以存储子广义表。
本章重点从矩阵… 第五部分、数组和广义表详解 数组和广义表都用于存储逻辑关系为“一对一”的数据。
数组存储结构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 i0; im1;i) { for (int j0; jn2; j) { C[i][j]0; for (int k0; kn1; 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 行第一个元素的位置 小于第 n1 行第一个元素的位置如果是矩阵的最后一行 小于矩阵中非 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 的列数矩阵 B 的行数 n 不是很大的情况下算法的时间复杂度相当于O(m*p)比普通算法要快很多。 十、十字链表实现矩阵加法附带C语言实现代码
矩阵之间能够进行加法运算的前提条件是各矩阵的行数和列数必须相等。 在行数和列数都相等的情况下矩阵相加的结果就是矩阵中对应位置的值相加所组成的矩阵例如 图 1 矩阵相加
1、十字链表法
之前所介绍的都是采用顺序存储结构存储三元组在类似于矩阵的加法运算中矩阵中的数据元素变化较大这里的变化主要为非0元素变为00变为非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例如三元组为ijk所在行的具体位置
如果 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.mum; M.nun; M.tut; if(!(M.rhead(OLink*)malloc((m1)*sizeof(OLink)))||!(M.chead(OLink*)malloc((n1)*sizeof(OLink)))) { printf(初始化矩阵失败); exit(0); //初始化矩阵的行列链表 } for(i1;im;i) { M.rhead[i]NULL; //初始化行 } for(j1;jn;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-ii; p-jj; p-ee; //初始化p if(NULLM.rhead[i]||M.rhead[i]-jj) { p-rightM.rhead[i]; M.rhead[i]p; } else { for(qM.rhead[i];(q-right)q-right-jj;qq-right); p-rightq-right; q-rightp; } if(NULLM.chead[j]||M.chead[j]-ii) { p-downM.chead[j]; M.chead[j]p; } else { for (qM.chead[j];(q-down) q-down-ii;qq-down); p-downq-down; q-downp; } } 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 种情况还可以细分为以下几种场景
当 paNULL 时表明当前行列没有非 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、完整代码演示 #includestdio.h #includestdlib.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); //实现 NM 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() 函数实现 NM 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 元素的个数。
