数据结构数组幻灯片.ppt

《数据结构数组幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构数组幻灯片.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数组第1页，共42页，编辑于2022年，星期六定义：定义：相同类型的数据元素的集合。相同类型的数据元素的集合。一维数组的一维数组的示例：示例：35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9一维数组一维数组2.4.1 数组的定义数组的定义第2页，共42页，编辑于2022年，星期六数组的定义和初始化数组的定义和初始化main()int a13=3,5,7,*elem;for(int i=0;i 3;i+)printf(“%d”,a1i,“n”);/静态数组静态数组 elem=a1;for(int i=0;i 0 a,i=0 a+i*la2.

2、4.1 数组的定义数组的定义第4页，共42页，编辑于2022年，星期六二维数组：二维数组：类似于线性表，一个二维数组的逻辑结构可形类似于线性表，一个二维数组的逻辑结构可形式地表示为：式地表示为：2_Array=(D,R)D=aij(i=0,1,m-1,j=0,1,n-1),aij是同类型数据元素的集是同类型数据元素的集合。合。R=ROW,COL是数据元素上关系的集合。是数据元素上关系的集合。2.4.1 数组的定义数组的定义a11 a12 a13 a1na21 a22 a23 a2nam1 am2 am3 amn ai,j-1 aij ai,j+1 ai-1,j ai+1,j Am,n=第5页，

3、共42页，编辑于2022年，星期六a aij ij受行列两个关系的约束：第受行列两个关系的约束：第受行列两个关系的约束：第受行列两个关系的约束：第i i行的行向量，第行的行向量，第行的行向量，第行的行向量，第j j列的列向列的列向列的列向列的列向量。量。量。量。ROW=|0 i m-1,0 j n-2每一行上的列关系。每一行上的列关系。aij ij的行前趋的行前趋的行前趋的行前趋a ai,j-1i,j-1，a aij ij的行后继的行后继的行后继的行后继a a i,j+1COL=|0 i m-2,0 j n-1每一列上的行关每一列上的行关系。系。a aij ij的列前趋的列前趋的列前趋的列前趋

4、a ai-1,ji-1,j，aij ij的列后继的列后继a i+1,j2.4.1 数组的定义数组的定义第6页，共42页，编辑于2022年，星期六行行优先存放优先存放(例：例：pascal、C语言语言)：设数组开始存放位置设数组开始存放位置 LOC(0,0)=a,每个元素占用每个元素占用 l 个存储个存储单元单元 LOC(i,j)=a+(i n+j)l2.4.2 数组的顺序存储结构数组的顺序存储结构约定存放次序：约定存放次序：因为计算机的存储单元是一维的，数组可以是多维的，因为计算机的存储单元是一维的，数组可以是多维的，所以必须约定存放次序。所以必须约定存放次序。第7页，共42页，编辑于2022

5、年，星期六n n列列优先存放优先存放(例：例：Fortran Fortran语言语言)：设数组开始存放位置设数组开始存放位置 LOC(0,0)=a,每个元素占用每个元素占用 l 个个存储单元存储单元 LOC(i,j)=a+(j m+i)l2.4.2 数组的顺序存储结构数组的顺序存储结构第8页，共42页，编辑于2022年，星期六三维数组：三维数组：各维元素个数为各维元素个数为 m1,m2,m3下标为下标为 i1,i2,i3的数组元素的存储地址：的数组元素的存储地址：(按页按页/行行/列存放列存放)LOC(i1,i2,i3)=a+(i1 m2 m3+i2 m3+i3)*l 前前i1页总页总元素个数

6、元素个数第第i1页的页的前前i2行总行总元素个数元素个数2.4.2 数组的顺序存储结构数组的顺序存储结构第第i1页的页的第第i2行行i3列列前前元素个元素个数数第9页，共42页，编辑于2022年，星期六下标为下标为 i1,i2,i3的数组元素的存储地址：的数组元素的存储地址：(按列按列/行行/页存放页存放)LOC(i1,i2,i3)=a+(i3 m1 m2+i2 m1+i1)*l 前前i3列总列总元素个数元素个数第第i3列的列的前前i2行总行总元素个数元素个数2.4.2 数组的顺序存储结构数组的顺序存储结构第第i3列的列的第第i2行行i1页页前前元素个元素个数数第10页，共42页，编辑于202

7、2年，星期六 n 维数组：维数组：各维元素个数为各维元素个数为m1,m2,m3,mn 下标为下标为 i1,i2,i3,in 的数组元素的存储地址：的数组元素的存储地址：LOC(i1,i2,in)=a+(i1 m2 m3 mn+i2 m3 m4 mn+in-1 mn+in)l 2.4.2 数组的顺序存储结构数组的顺序存储结构第11页，共42页，编辑于2022年，星期六 二维数组二维数组 三维数组三维数组 行向量行向量 下标下标 i1 页向量页向量 下标下标 i1 列向量列向量 下标下标 i2 行向量行向量 下标下标 i2 列向量列向量 下标下标 i3第12页，共42页，编辑于2022年，星期六特

8、殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵：特殊矩阵：是指非零元素的分布有一定规律是指非零元素的分布有一定规律/大量零元素的矩阵。大量零元素的矩阵。压缩存储：压缩存储：针对阶数很高的特殊矩阵。为节省针对阶数很高的特殊矩阵。为节省存储空间，可以不存储零元素或对称元素。存储空间，可以不存储零元素或对称元素。对称矩阵对称矩阵 三对角矩阵三对角矩阵2.4.2 数组的顺序存储结构数组的顺序存储结构第13页，共42页，编辑于2022年，星期六对称矩阵的压缩存储对称矩阵的压缩存储设有一个设有一个 n n 的对称矩阵的对称矩阵 A。在矩阵中，在矩阵中，aij=aji2.4.2 数组的顺序存储结构数组的顺序存储

9、结构第14页，共42页，编辑于2022年，星期六 为节约存储空间，只存对角线及对角线以为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的上的元素，或者只存对角线及对角线以下的元素。前者称为元素。前者称为上三角矩阵上三角矩阵，后者称为，后者称为下三下三角矩阵角矩阵。把它们按行存放于一个一维数组把它们按行存放于一个一维数组 B 中，称中，称之为对称矩阵之为对称矩阵 A 的压缩存储方式。的压缩存储方式。数组数组 B 共有共有 n+(n-1)+1=n(n+1)/2个元素。个元素。2.4.2 数组的顺序存储结构数组的顺序存储结构第15页，共42页，编辑于2022年，星期六上三角矩

10、阵下三角矩阵第16页，共42页，编辑于2022年，星期六下三角矩阵B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1 0 1 2 3 4 5 6 7 8 n(n+1)/2-1若若 i j,数组元素数组元素Aij在数组在数组B中的存放位置为中的存放位置为 1+2+i+j=(i+1)i/2+j前前i行元素总数行元素总数 第第i行第行第j个元素前元素个数个元素前元素个数第17页，共42页，编辑于2022年，星期六 若若ij，数组元素，数组元素 Aij 在矩阵的上三角部分在矩阵的上三角部分,在在数组数组 B 中没有存放，可以找它的对称元素：中没有存放，可以找它的

11、对称元素：Aji：=j(j+1)/2+i 若已知某矩阵元素位于数组若已知某矩阵元素位于数组B的第的第k个位置，可寻找满足个位置，可寻找满足i(i+1)/2 k (i+1)(i+2)/2的的 i(行号行号),j=k-i (i+1)/2 (列号列号)例例:当当 k=8,3 4/2=6 k j，数组元素，数组元素Aij在矩阵的下三角部分，在矩阵的下三角部分，在数组在数组 B 中没有存放。因此，找它的对称元素中没有存放。因此，找它的对称元素Aji。Aji在数组在数组 B 的第的第(2 n-j-1)j/2+i 的位的位置中找到。置中找到。2.4.2 数组的顺序存储结构数组的顺序存储结构第20页，共42页

12、，编辑于2022年，星期六三对角矩阵的压缩存储三对角矩阵的压缩存储B a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 102.4.2 数组的顺序存储结构数组的顺序存储结构第21页，共42页，编辑于2022年，星期六 三对角矩阵中除主对角线及在主对角线上三对角矩阵中除主对角线及在主对角线上 下最临近下最临近的两条对角线上的元素外，所有其它元素均为的两条对角线上的元素外，所有其它元素均为0。总共。总共有有3n-2个非零元素。个非零元素。将三对角矩阵将三对角矩阵A中三条对角线上的元素按行存放在中三条对角线上的元素

13、按行存放在一维数组一维数组 B 中，且中，且a00存放于存放于B0。在三条对角线上的元素在三条对角线上的元素aij 满足满足 0 i n-1,i-1 j i+1 在一维数组在一维数组 B 中中 Aij 在第在第 i 行，它前面有行，它前面有 3i-1 个个非零元素非零元素,在本行中第在本行中第 j 列前面有列前面有 j-i+1 个，所以元素个，所以元素 Aij 在在 B 中位置为中位置为 k=2 i+j。2.4.2 数组的顺序存储结构数组的顺序存储结构第22页，共42页，编辑于2022年，星期六2.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)n 非零元素个数远远少于矩阵元素个数且非零

14、元素个数远远少于矩阵元素个数且分布无规律可循。分布无规律可循。在上图中在上图中,矩阵矩阵A是是6*7的矩阵的矩阵,它有它有42个元素个元素,但只有但只有8个非零个非零元素。元素。n 简单的压缩存储会失去随机存取功能，还要存储辅助信息简单的压缩存储会失去随机存取功能，还要存储辅助信息 存储非零元素时，存储元素的行列号存储非零元素时，存储元素的行列号n 存储方式：存储方式：顺序存储：顺序存储：不改变矩阵的稀疏程度不改变矩阵的稀疏程度(存取、修改、转置存取、修改、转置)链式存储：链式存储：改变矩阵的稀疏程度改变矩阵的稀疏程度(相加、相乘相加、相乘)第23页，共42页，编辑于2022年，星期六稀疏矩阵

15、的抽象数据类型稀疏矩阵的抽象数据类型(三元组顺序表）三元组顺序表）#define MAXSIZE 12500typedef structint i,j;/非零元素行号非零元素行号/列号列号ElemType e;/非零元素的值非零元素的值Triple;/三元组三元组typedef structTriple dataMAXSIZE;int mu,nu,tu;/矩阵行数、列数、非零元个数矩阵行数、列数、非零元个数TSMatrix;/稀疏矩阵类定义稀疏矩阵类定义 2.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)第24页，共42页，编辑于2022年，星期六2.4.3 稀疏矩阵稀疏矩阵(Spar

16、se Matrix)稀疏矩阵稀疏矩阵A7 6第25页，共42页，编辑于2022年，星期六转置矩阵转置矩阵B6 7=AT7 62.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)第26页，共42页，编辑于2022年，星期六用三元组表表示的稀疏矩阵及其转置用三元组表表示的稀疏矩阵及其转置2.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)如果只简单交换行列下标，所得如果只简单交换行列下标，所得B是按列优先存储是按列优先存储第27页，共42页，编辑于2022年，星期六稀疏矩阵转置算法思想稀疏矩阵转置算法思想 显然，一个稀疏矩阵的转置仍然是一个稀显然，一个稀疏矩阵的转置仍然是一个稀疏矩阵。

17、疏矩阵。(1)将矩阵的行列值交换将矩阵的行列值交换(2)将每一个三元组的将每一个三元组的i和和j相互调换相互调换(3)重排三元组之间的次序重排三元组之间的次序 可以有两种处理方法：可以有两种处理方法：2.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)第28页，共42页，编辑于2022年，星期六方法一：方法一：按照按照A(m n)的的列列序来进行转置序来进行转置,设矩阵列数为设矩阵列数为nu，对矩阵三元组表扫描对矩阵三元组表扫描nu次。第次。第k次检测列号为次检测列号为k的项。的项。第第k次扫描找寻所有列号为次扫描找寻所有列号为k的项，将其行号变列号、的项，将其行号变列号、列号变行号，顺

18、次存于转置矩阵三元组表。列号变行号，顺次存于转置矩阵三元组表。2.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)按按A的列下标转置，所得的列下标转置，所得B是按行优先存放是按行优先存放第29页，共42页，编辑于2022年，星期六稀疏矩阵的转置稀疏矩阵的转置Status TransposeSMatrix(TSMatrix&A,TSMatrix&B)B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;/转置矩阵的列数转置矩阵的列数,行数和非零元素个数行数和非零元素个数if(B.tu)q=0;/矩阵矩阵B的指针的指针for(col=0;col=A.nu-1;+col)for(p=0;

19、p=A.tu-1;+p)/矩阵矩阵A的指针的指针 if(A.datap.j=col)B.dataq.i=A.datap.j;B.dataq.j=A.datap.i;B.dataq.e=A.datap.e;+q;return 1;/TransposeSMatrix2.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)特点：以特点：以B矩阵的三元组为中心，在矩阵的三元组为中心，在A矩阵的三元组中通盘查找合适的结点矩阵的三元组中通盘查找合适的结点置入置入B中。中。第30页，共42页，编辑于2022年，星期六 该算法主要工作是在该算法主要工作是在p col的两重循环中做的，所的两重循环中做的，所以

20、时间复杂度是以时间复杂度是O(nu tu)。一般矩阵的转置算法是在一般矩阵的转置算法是在nu mu的两重循环中的两重循环中做的，时间复杂度是做的，时间复杂度是O(nu mu)。当稀疏矩阵的非零元个数当稀疏矩阵的非零元个数tu=nu mu时，其时间复时，其时间复杂度杂度:O(nu tu)=O(nu nu mu)=O(nu2 mu)大大高于一大大高于一般矩阵的时间复杂度，所以该算法仅适用于般矩阵的时间复杂度，所以该算法仅适用于tunu mu的稀疏矩阵。的稀疏矩阵。2.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)用三元组节省了存储空间，但增加了执行时间用三元组节省了存储空间，但增加了执行时

21、间第31页，共42页，编辑于2022年，星期六方法二：快速转置运算方法二：快速转置运算(带辅助向量的三元组带辅助向量的三元组)n预先确定预先确定A的每一列第一个非零元在的每一列第一个非零元在B中应有的位置，中应有的位置，则在转置时就可直接放到则在转置时就可直接放到B中去，所以在转置前，应先中去，所以在转置前，应先求得求得A的的每一列中非零元的个数每一列中非零元的个数和每一列的和每一列的第一个非零第一个非零元在元在B中的位置中的位置。只需对只需对A A扫描一遍。扫描一遍。n需要两个辅助数组需要两个辅助数组num和和pos。num表示表示A中第中第col列非列非零元素的个数。零元素的个数。pos表

22、示表示A中第中第col列第一个非零元素在列第一个非零元素在B中的位置。显然有：中的位置。显然有：pos0=0 poscol=poscol-1+numcol-12.4.3 稀疏矩阵稀疏矩阵(Sparse Matrix)第32页，共42页，编辑于2022年，星期六矩阵矩阵A A的辅助数组的值的辅助数组的值Col012356numcol111221poscol012357转置矩阵转置矩阵第33页，共42页，编辑于2022年，星期六Status FastTransposeSMatrix(TSMatrix&A,TSMatrix&B)B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;if(B.t

23、u)for(col=0;col=A.nu-1;+col)numcol=0;/初始化初始化num for(t=0;t=A.tu-1;+t)+numA.datat.j;/求求A中每列非零元个数中每列非零元个数 pos0=0;for(col=1;col=A.nu-1;+col)poscol=poscol-1+numcol-1;/求第求第col列中第一个非零元在列中第一个非零元在B中的序号中的序号 for(p=0;pj=pb-j 且且pa-v+pb-v0,则则pa-v=pa-v+pb-v。2)pa-j=pb-j 且且pa-v+pb-v=0,则则需需要要在在A矩矩阵阵链链表表中中删删除除pa所所指指的的

24、结结点点。这这时时，需需改改变变i行行链链表表中中前前一一结结点点的的right域域值值，以以及及j列列表中前一结点的表中前一结点的down域值。域值。3)pa-jj 且且 pa-j0,则则 pa指指 针针 移移 动动 指指 向向 下下 一一 个个 非非 零零 元元 结结 点点。(pa-j=0指向表头指向表头)4)pa-jpb-j或或pa-j=0,则在则在A矩阵链表中插入矩阵链表中插入pb所指结点。所指结点。算法时间复杂度算法时间复杂度O(tuA+tuB)2.4.4 数组的链式存储结构数组的链式存储结构例：用十字链表实现稀疏矩阵相加运算例：用十字链表实现稀疏矩阵相加运算第42页，共42页，编辑于2022年，星期六