首页计算机计算机基础数据结构 04 第四章 数组.pptx

04 第四章 数组.pptx

页数:36页文件大小:853.4 KB来源: 数据结构ppt课件

本课件为数据结构第四章数组,从数组的抽象数据类型定义与顺序存储入手,说明二维数组的元素地址计算方法,随后讲解对称矩阵、三角矩阵、对角矩阵等特殊矩阵的压缩存储方式,最后重点介绍稀疏矩阵的三元组顺序表表示及其转置与快速转置算法。

第四章数组目录页,列出数组定义与特点、顺序存储与矩阵压缩存储等内容
数组定义与特点页,说明数组是数据元素本身又为线性表的特殊线性表及运算方式
数组行序为主存储示意图,给出以行序为主序时元素地址的计算公式
查看本课件的文字版(共 36 页,供检索与复制)

第1页:第四章数组目录

数组的定义和特点数组的顺序存储结构矩阵的压缩存储本章小结第四章数组课后作业

第2页:数组的定义和特点

数组可以看作是一种特殊的线性表,即线性表数据元素本身又是一个线性表 数组的定义和特点 定义 数组特点 数组结构固定,数组行列数不可变 数据元素同构 数组运算 给定一组下标,存取、修改相应的数据元素 一般不做插入、删除操作( )( )( )( )( )( )( )( )( )数组(Array)

第3页:数组的顺序存储:行序为主

次序约定以行序为主序:BASIC、PASCAL、C数组的顺序存储结构a11a12…….. a1na21a22…….. a2nam1am2…….. amn………………….amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1nLoc(aij)=Loc(a11)+[(i-1)n+(j-1)]*L

第4页:数组的行序与列序存储

次序约定以行序为主序:BASIC、PASCAL、Ca11a12…….. a1na21a22…….. a2nam1am2…….. amn………………….以列序为主序:FORTRAN01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*L数组的顺序存储结构可随机存取任一元素数组的顺序存储结构

第5页:矩阵的压缩存储

矩阵的压缩存储对称矩阵稀疏矩阵三角矩阵对角矩阵

  • 压缩存储的基本思想:
  • 值相同的元素分配一个存储空间;
  • 零元素不分配空间将一个n阶矩阵压缩存储到一个一维数组中,并希望找出n阶矩阵中元素aij与该一维数组元素间的对应关系,即尽可能保持矩阵的随机存取功能。

第6页:对称矩阵的压缩存储

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矩阵的压缩存储压缩存储

第7页:三角矩阵的压缩存储

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) 三角矩阵矩阵的压缩存储压缩存储

第8页:对角矩阵的压缩存储

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)矩阵的压缩存储压缩存储

第9页:稀疏矩阵的压缩存储内容

稀疏矩阵的定义稀疏矩阵的顺序压缩存储三元组表行逻辑链接的顺序表伪地址表示法稀疏矩阵转置稀疏矩阵转置—按M的列序转置稀疏矩阵转置—快速转置稀疏矩阵的链式压缩存储带行指针向量的单链表表示十字链表矩阵的压缩存储——稀疏矩阵

第10页:稀疏矩阵的定义

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的矩阵为稀疏矩阵 压缩存储原则:只存储每个非零元的行、列下标及其值和矩阵的行列维数矩阵的压缩存储——稀疏矩阵稀疏矩阵

第11页:三元组结构定义

typedefstruct{ int i, j;//非零元的行、列下标ElemType e;//非零元的值}Triple;#defineMAXSIZE100//非零元最大个数typedefstruct{Tripledata[MAXSIZE+ 1];//三元组表,data[0]未用int mu, nu, tu;//矩阵行、列数、非零元个数}TSMatrix;三元组结构稀疏矩阵结构i j e 三元组表稀疏矩阵的压缩存储——顺序存储

第12页:三元组表

稀疏矩阵 M 的三元组顺序表表示:矩阵 M 为 6 行 7 列,共 8 个非零元,mu、nu、tu 分别记录行数、列数与非零元个数。

稀疏矩阵 M 的三元组顺序表(mu=6,nu=7,tu=8)
i(行下标)j(列下标)e(非零元值)
1212
139
31-3
3614
4324
5218
6115
64-7

第13页:行逻辑链接的顺序表

行逻辑链接的顺序表——带行链接信息的三元组表增加一个辅助数组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;行逻辑链接的顺序表结构稀疏矩阵的压缩存储——顺序存储

第14页:行逻辑链接表示例

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)

第15页:伪地址表示法

伪地址:本元素在矩阵中(包括零元素在内)按行优先顺序的相对位置672123915-3201424243018361539-7伪地址非零元值矩阵行列维数M.dataaddr e012345678?稀疏矩阵压缩存储后会失去随机存取功能?amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n 伪地址表示法稀疏矩阵的压缩存储——顺序存储稀疏矩阵

第16页:稀疏矩阵转置问题

问题描述:已知一个稀疏矩阵的三元组表,求该矩阵转置矩阵的三元组表 问题分析一般矩阵转置算法:

for(col=0;col<nu;col++)for(row=0;row<mu;row++)T[col][row]=M[row][col];T(n)=O(mu nu)稀疏矩阵转置——基于三元组表

第17页:转置前后的三元组表

稀疏矩阵转置前后对照:M.data 与转置后的 T.data 一一对应,行下标与列下标互换,非零元值保持不变。转置后 T 为 7 行 6 列,仍含 8 个非零元。

矩阵转置前后三元组对照(M 与 T)
M 的 iM 的 jM 的 eT 的 iT 的 jT 的 e
12122112
139319
31-313-3
36146314
43243424
52182518
61151615
64-746-7

第18页:转置的解决思路

解决思路: 将矩阵行、列维数互换,非零元个数不变 将每个三元组中的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稀疏矩阵转置——基于三元组表

第19页:按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的列序转置按矩阵T中三元组表T.data的次序依次在矩阵M的三元组表M.data中找到相应三元组进行转置•为找到M.data中第i列所有非零元素,需对M.data扫描一遍•由于M.data以M行序为主序,所以得到的恰是T.data中应有的顺序稀疏矩阵转置——按M的列序转置

第20页:按列序转置:扫描第一列

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的列序转置

第21页:按列序转置:扫描第二列

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的列序转置

第22页:按列序转置:扫描第三列

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的列序转置

第23页:按列序转置:扫描第四列

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的列序转置

第24页:按列序转置:扫描第五列

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的列序转置

第25页:按列序转置:扫描第六列

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的列序转置

第26页:按列序转置:扫描第七列

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的列序转置

第27页:按列序转置算法

算法描述

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的列序转置

第28页:快速转置思路

按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中位置,稀疏矩阵转置——快速转置

第29页:快速转置的num与cpot

快速转置中的 num 与 cpot 数组:num[col] 统计矩阵 M 中第 col 列非零元个数,cpot[col] 指示第 col 列第一个非零元在 T.data 中的存放位置。

各列非零元个数 num[col] 与起始位置 cpot[col]
col(列号)num[col]cpot[col]
121
223
325
417
508
618
709

cpot 满足 cpot[1]=1、cpot[col]=cpot[col-1]+num[col-1];原文数字存在粘连,表中数值按上述递推关系与三元组分布推算对齐。

第30页:快速转置过程

快速转置结果 T.data:转置后的三元组顺序表按列序(即 T 的行序)存放,T 为 7 行 6 列,共 8 个非零元(mu=7,nu=6,tu=8)。

快速转置得到的 T.data 三元组顺序表
i(行下标)j(列下标)e(非零元值)
13-3
1615
2112
2518
319
3424
46-7
6314

第31页:快速转置算法

算法描述

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)稀疏矩阵转置——快速转置稀疏矩阵

第32页:稀疏矩阵链式存储的原因

引入稀疏矩阵链式存储的原因: 用三元组表存储稀疏矩阵,在单纯的存储和做类似转置之类的运算时可以节约存储空间,且运算速度较快; 但当进行矩阵相加等运算时,稀疏矩阵的非零元位置和个数都会发生变化。使用三元组表必然会引起数组元素的大量移动。稀疏矩阵的压缩存储——链式存储

第33页:带行指针向量的单链表

每行的非零元分别用单链表链接单链表中每个结点存放其所在列及值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];适合于按行进行操作的问题稀疏矩阵的压缩存储——链式存储

第34页:十字链表的结点结构

十字链表每个非零元用含有五个域的结点表示(非零元的所在行、列、值,及同行、同列的下一个非零元)

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];稀疏矩阵的压缩存储——链式存储

第35页:十字链表示例

十字链表每个非零元用含有五个域的结点表示(非零元的所在行、列、值,及同行、同列的下一个非零元)113418225234^^^^^^^M.rheadM.cheadCrossList M;适合于按行及按列进行操作的问题稀疏矩阵的压缩存储——链式存储rowcolvaldownright稀疏矩阵

第36页:第四章本章小结

了解数组的定义和存储方式本章小结掌握特殊矩阵(对称阵,上三角阵,下三角阵,对角阵)的压缩存储方式掌握稀疏矩阵的压缩存储方式,了解相应算法(转置)的实现

顶部目录