页数:36页文件大小:853.4 KB来源: 数据结构ppt课件
本课件为数据结构第四章数组,从数组的抽象数据类型定义与顺序存储入手,说明二维数组的元素地址计算方法,随后讲解对称矩阵、三角矩阵、对角矩阵等特殊矩阵的压缩存储方式,最后重点介绍稀疏矩阵的三元组顺序表表示及其转置与快速转置算法。
数组的定义和特点数组的顺序存储结构矩阵的压缩存储本章小结第四章数组课后作业
数组可以看作是一种特殊的线性表,即线性表数据元素本身又是一个线性表 数组的定义和特点 定义 数组特点 数组结构固定,数组行列数不可变 数据元素同构 数组运算 给定一组下标,存取、修改相应的数据元素 一般不做插入、删除操作( )( )( )( )( )( )( )( )( )数组(Array)
次序约定以行序为主序:BASIC、PASCAL、C数组的顺序存储结构a11a12…….. a1na21a22…….. a2nam1am2…….. amn………………….amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1nLoc(aij)=Loc(a11)+[(i-1)n+(j-1)]*L
次序约定以行序为主序:BASIC、PASCAL、Ca11a12…….. a1na21a22…….. a2nam1am2…….. amn………………….以列序为主序:FORTRAN01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*L数组的顺序存储结构可随机存取任一元素数组的顺序存储结构
矩阵的压缩存储对称矩阵稀疏矩阵三角矩阵对角矩阵
a11a12….… …..a1na21a22…….. …….a2nan1an2……..ann………………….Loc(a11)+[ ]*L(i j)Loc(aij)=Loc(a11)+[( +(i-1)]*Lj(j-1)2(i<j)0…...a11a21a22a31a32an1ann…...按行序为主序:…...a33 对称矩阵Loc(aij)=n(n+1)/2-1+(j-1)i(i-1)2矩阵的压缩存储压缩存储
a110 0……..0a21a220……..0an1an2an3……..ann………………….0…...a11a21a22a31a32an1ann…...k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1按行序为主序:…...a33Loc(aij)=Loc(a11)+[( +(j-1)]*Li(i-1)2(i j)aij=0(i<j) 三角矩阵矩阵的压缩存储压缩存储
a11a120…………… .0a21a22a230……………000…an-1,n-2an-1,n-1an-1,n00… …an,n-1ann0a32a33a340………0……………………………Loc(aij)=a11a12a21a22a23ann-1ann…...按行序为主序:a32…...(|i-j|≤1)aij=0其它 对角矩阵?特殊矩阵压缩存储后会失去随机存取功能?0[4+(n-2)*3]-1Loc(a11)+[ ]*L2(i-1)+(j-1)矩阵的压缩存储压缩存储
稀疏矩阵的定义稀疏矩阵的顺序压缩存储三元组表行逻辑链接的顺序表伪地址表示法稀疏矩阵转置稀疏矩阵转置—按M的列序转置稀疏矩阵转置—快速转置稀疏矩阵的链式压缩存储带行指针向量的单链表表示十字链表矩阵的压缩存储——稀疏矩阵
M由{(1,2,12), (1,3,9), (3,1,-3),(3,6,14), (4,3,24),(5,2,18),(6,1,15), (6,4,-7)}和矩阵维数(6,7)唯一确定 定义:非零元较零元少,且分布没有一定规律的矩阵假设m行n列的矩阵含t个非零元素稀疏因子通常认为 0.05的矩阵为稀疏矩阵 压缩存储原则:只存储每个非零元的行、列下标及其值和矩阵的行列维数矩阵的压缩存储——稀疏矩阵稀疏矩阵
typedefstruct{ int i, j;//非零元的行、列下标ElemType e;//非零元的值}Triple;#defineMAXSIZE100//非零元最大个数typedefstruct{Tripledata[MAXSIZE+ 1];//三元组表,data[0]未用int mu, nu, tu;//矩阵行、列数、非零元个数}TSMatrix;三元组结构稀疏矩阵结构i j e 三元组表稀疏矩阵的压缩存储——顺序存储稀疏矩阵 M 的三元组顺序表表示:矩阵 M 为 6 行 7 列,共 8 个非零元,mu、nu、tu 分别记录行数、列数与非零元个数。
| i(行下标) | j(列下标) | e(非零元值) |
|---|---|---|
| 1 | 2 | 12 |
| 1 | 3 | 9 |
| 3 | 1 | -3 |
| 3 | 6 | 14 |
| 4 | 3 | 24 |
| 5 | 2 | 18 |
| 6 | 1 | 15 |
| 6 | 4 | -7 |
行逻辑链接的顺序表——带行链接信息的三元组表增加一个辅助数组rpos[MaxRC+1](MaxRC为行数)其物理意义是第i行第一个非零元在三元组表中的位置(下标),显然有:rpos[1]=1rpos[i]=rpos[i-1]+第i-1行非零元个数(i 2)
typedefstruct{Triple data[MaxSize+1];//非零元三元组表intrpos[MaxRC+1];//每行第一个非零元的位置int mu, nu, tu;//矩阵的行、列数,非零元个数}RLSMatrix;行逻辑链接的顺序表结构稀疏矩阵的压缩存储——顺序存储rpos[MaxRC+1]:第i行第一个非零元在三元组表中的位置rpos[1]=1rpos[i]=rpos[i-1]+第i-1行非零元个数(i 2)1 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7M.datai j e0123456780123456M.rops133567 行逻辑链接的顺序表rpos[0]不用或存矩阵行数6678稀疏矩阵的压缩存储——顺序存储找M(3,5)
伪地址:本元素在矩阵中(包括零元素在内)按行优先顺序的相对位置672123915-3201424243018361539-7伪地址非零元值矩阵行列维数M.dataaddr e012345678?稀疏矩阵压缩存储后会失去随机存取功能?amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n 伪地址表示法稀疏矩阵的压缩存储——顺序存储稀疏矩阵
问题描述:已知一个稀疏矩阵的三元组表,求该矩阵转置矩阵的三元组表 问题分析一般矩阵转置算法:
for(col=0;col<nu;col++)for(row=0;row<mu;row++)T[col][row]=M[row][col];T(n)=O(mu nu)稀疏矩阵转置——基于三元组表稀疏矩阵转置前后对照:M.data 与转置后的 T.data 一一对应,行下标与列下标互换,非零元值保持不变。转置后 T 为 7 行 6 列,仍含 8 个非零元。
| M 的 i | M 的 j | M 的 e | T 的 i | T 的 j | T 的 e |
|---|---|---|---|---|---|
| 1 | 2 | 12 | 2 | 1 | 12 |
| 1 | 3 | 9 | 3 | 1 | 9 |
| 3 | 1 | -3 | 1 | 3 | -3 |
| 3 | 6 | 14 | 6 | 3 | 14 |
| 4 | 3 | 24 | 3 | 4 | 24 |
| 5 | 2 | 18 | 2 | 5 | 18 |
| 6 | 1 | 15 | 1 | 6 | 15 |
| 6 | 4 | -7 | 4 | 6 | -7 |
解决思路: 将矩阵行、列维数互换,非零元个数不变 将每个三元组中的i和j相互调换,非零元值不变 重排次序,使T.data中元素以T的行(M的列)为主序M.data6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678T.data34 24i j e01234567876813-316 1521 1225 1831 946-763 14稀疏矩阵转置——基于三元组表
M.data6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678T.data34 24i j e01234567876813-316 1521 1225 1831 946-763 14 方法一:按M的列序转置按矩阵T中三元组表T.data的次序依次在矩阵M的三元组表M.data中找到相应三元组进行转置•为找到M.data中第i列所有非零元素,需对M.data扫描一遍•由于M.data以M行序为主序,所以得到的恰是T.data中应有的顺序稀疏矩阵转置——按M的列序转置
6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678M.datai j e012345678T.datakppppppppkkcol=176813-316 15稀疏矩阵转置——按M的列序转置
6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678M.datai j e012345678T.datappppppppkcol=276813-316 1521 1225 18kk稀疏矩阵转置——按M的列序转置
6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678M.datai j e012345678T.datappppppppcol=376813-316 1521 1225 18k31 934 24kk稀疏矩阵转置——按M的列序转置
6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678M.datai j e012345678T.datappppppppcol=476813-316 1521 1225 1831 934 24k46-7k稀疏矩阵转置——按M的列序转置
6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678M.datai j e012345678T.datappppppppcol=576813-316 1521 1225 1831 934 2446-7k稀疏矩阵转置——按M的列序转置
6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678M.datai j e012345678T.datappppppppcol=676813-316 1521 1225 1831 934 2446-7k63 14k稀疏矩阵转置——按M的列序转置
6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678M.datai j e012345678T.datappppppppcol=776813-316 1521 1225 1831 934 2446-763 14k算法结束稀疏矩阵转置——按M的列序转置
算法描述
StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){ int col, p, k;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for()for()if( ){T.data[k]. i =M.data[p].j;T.data[k]. j=M.data[p].i;T.data[k]. e=M.data[p].e;k++;}returnOK;}returnERROR;}设置矩阵信息有非零元,转置k为T.data表下标col=1;col<=M.nu;col++p=1;p<=M.tu;p++M.data[p].j==colT(n)=O(M.nu×M.tu)若M.tu与M.mu×M.nu同数量级则T(n)=O(M.mu×M.nu2)k=1;查找M每一列的非零元扫描M的所有非零元稀疏矩阵转置——按M的列序转置按M.data中三元组次序转置,结果放入T.data中恰当位置6781 2 121 3 93 1-33 6 144 3 245 2 186 1 156 4-7i j e012345678M.datai j e012345678T.datapppppppp13-316 1521 1225 1831 934 2446-763 14768需要预先确定M中每一列第一个非零元在T.data中位置,稀疏矩阵转置——快速转置
快速转置中的 num 与 cpot 数组:num[col] 统计矩阵 M 中第 col 列非零元个数,cpot[col] 指示第 col 列第一个非零元在 T.data 中的存放位置。
| col(列号) | num[col] | cpot[col] |
|---|---|---|
| 1 | 2 | 1 |
| 2 | 2 | 3 |
| 3 | 2 | 5 |
| 4 | 1 | 7 |
| 5 | 0 | 8 |
| 6 | 1 | 8 |
| 7 | 0 | 9 |
cpot 满足 cpot[1]=1、cpot[col]=cpot[col-1]+num[col-1];原文数字存在粘连,表中数值按上述递推关系与三元组分布推算对齐。
快速转置结果 T.data:转置后的三元组顺序表按列序(即 T 的行序)存放,T 为 7 行 6 列,共 8 个非零元(mu=7,nu=6,tu=8)。
| i(行下标) | j(列下标) | e(非零元值) |
|---|---|---|
| 1 | 3 | -3 |
| 1 | 6 | 15 |
| 2 | 1 | 12 |
| 2 | 5 | 18 |
| 3 | 1 | 9 |
| 3 | 4 | 24 |
| 4 | 6 | -7 |
| 6 | 3 | 14 |
算法描述
Statusfast_transpos ( TSMatrixM, TSMatrix&T){ int col,p,k , num[N],cpot[N];returnOK;}设置矩阵信息T.mu =M.nu;T.nu =M.mu;T.tu =M.tu;num[]清零for(col=1;col<=M.nu;col++)设置num[]for(p=1;p<=M.tu;p++)设置cpot[]cpot[0]=0; cpot[1]=1;for(col=2;col<=M.nu;col++)cpot[col]=cpot[col-1]+num[col-1];转置for(p=1;p<=M.tu;p++){}col=M.data[p].j;k=cpot[col];T.data[k].i=M.data[p].j; T.data[k].j=M.data[p].i;T.data[k].e=M.data[p].e;cpot[col]++;if(T.tu ){}num[col]=0;num[M.data[p].j]++;T(n)=O(M.nu+M.tu)若M.tu与M.mu×M.nu同数量级则T(n)=O(M.mu×M.nu)稀疏矩阵转置——快速转置稀疏矩阵引入稀疏矩阵链式存储的原因: 用三元组表存储稀疏矩阵,在单纯的存储和做类似转置之类的运算时可以节约存储空间,且运算速度较快; 但当进行矩阵相加等运算时,稀疏矩阵的非零元位置和个数都会发生变化。使用三元组表必然会引起数组元素的大量移动。稀疏矩阵的压缩存储——链式存储
每行的非零元分别用单链表链接单链表中每个结点存放其所在列及值rhead^4 2^1 35 7^3-1^1-12-2^
typedef struct RLNode{ intj;ElemTypee;structRLNode *right;}RLNode,*RLink; 带行指针向量的单链表表示单链表结点结构typedef struct{ RLink *rhead;intmu,nu,tu;}RowList;数组结构RowListM;M.rheadM.mu=5M.nu=5M.tu=6RLinkrhead[M];适合于按行进行操作的问题稀疏矩阵的压缩存储——链式存储十字链表每个非零元用含有五个域的结点表示(非零元的所在行、列、值,及同行、同列的下一个非零元)
typedefstruct OLNode{int row, col;//非零元所在行、列ElemType val;//非零元的值struct OLNode *right, *down;//同行、同列的下一个非零元}OLNode,* OLink;typedefstruct{OLink*rhead,*chead;//行、列链表头指针一维数组int mu, nu, tu;//行、列数及非零元个数}CrossList;结点结构十字链表结构rowcolvaldownrightOLinkrhead[M], chead[N];稀疏矩阵的压缩存储——链式存储十字链表每个非零元用含有五个域的结点表示(非零元的所在行、列、值,及同行、同列的下一个非零元)113418225234^^^^^^^M.rheadM.cheadCrossList M;适合于按行及按列进行操作的问题稀疏矩阵的压缩存储——链式存储rowcolvaldownright稀疏矩阵
了解数组的定义和存储方式本章小结掌握特殊矩阵(对称阵,上三角阵,下三角阵,对角阵)的压缩存储方式掌握稀疏矩阵的压缩存储方式,了解相应算法(转置)的实现
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}