数据结构课件-第5章-数组、广义表.pptx

《数据结构课件-第5章-数组、广义表.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Page12021/7/30DataStructure第五章数组、广义表10086510第5章　数组和广义表5.1数组5.2广义表教学内容Page22021/7/305.1数组Page32021/7/30数据结构中的“数组”与高级语言中的“数组”区别：数据结构中的数组是一种线性结构高级语言中的数组是顺序结构；5.1.1数组的定义一维数组A=(a0,a1,a2,…,an)是线性表,元素之间的顺序关系由下标来体现,并且具有相同类型,每一个元素都是原子类型.二维数组a00a01a0n-1a10a11…a1na20a21…a2nAm×n=::::am-10am-11…am-1n-1二维数组可看成一个定

2、长线性表，每一个元素也是一个定长线性表。Page52021/7/30多维数组d(d≥3)维数组，看作一个由d-1维数组作为数据元素的线性表；数组是一种较复杂的线性表结构，由简单的数据结构即线性表辗转合成而得。三维数组5.1.1数组的定义5.1.1数组的定义数组特点数组结构固定数据元素同构数组基本操作(1)InitArray(&A,n,bound1,boundn)//构造数组A(2)DestroyArray(&A)//销毁数组A(3)Value(A,&e,index1,…,indexn)//取数组元素值(4)Assign(A,&e,index1,…,indexn)//给数组元素赋值数组顺序存储

3、的特点：数组中的数据元素数目固定，一旦定义，其数据元素的数目不再有增减变化；数组中的数据元素具有相同的数据类型。数组中的每个数据元素都和一组唯一的下标值对应；5.1.2数组的顺序表示与实现已知以下三要素，求数组中任一元素的地址：①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数北京林业大学信息学院a1a2a3a4a5a6a7a8a9a100123456789llllllllllLOC(ai)=一维数组5.1.2数组的顺序表示与实现LOC(a1)+（i-1）*l以行序为主序C,PASCAL5.1.2数组的顺序表示与实现二维数组通常有两种顺序存储方式：以行序为主序

4、以列序为主序5.1.2数组的顺序表示与实现二维数组——以行序为主序存储a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1nLoc(a11)+[(i-1)n+(j-1)]*L以列序为主序FORTRAN二维数组通常有两种顺序存储方式：以行序为主序以列序为主序5.1.2数组的顺序表示与实现二维数组——以列序为主序存储按列序为主序存放01m-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…

5、….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=5.1.2数组的顺序表示与实现Loc(a11)+[(j-1)m+(i-1)]*L二维数组A[m][n]按行优先LOC(i,j)=a+(i*n+j)*l按列优先LOC(i,j)=a+(j*m+i)*l三维数组各维元素个数为m1,m2,m3下标为i1,i2,i3的数组元素的存储地址：（按页/行/列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l前i1页总元素个数第i1页的前i2行总元素个数n维数组各维元素个数为m1,m2,m3,…,mn下标

6、为i1,i2,i3,…,in的数组元素的存储地址：LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in)*l课前任务检查请以小组为单位，回答并讲解课前任务中的题目！Page162021/7/30Page172021/7/305.1.3矩阵的压缩存储北京林业大学信息学院1.什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.什么样的矩阵能够压缩？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。3.什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）5.1.3矩阵的压

7、缩存储5.1.3矩阵的压缩存储1.对称矩阵a0,0a0,1….……..A0,n-1a1,0a1,1……..…….A1,n-1an-1,0an-1,1……..An-1,n-1………………….ajiaij[特点]在nn的矩阵a中，满足如下性质：aij=aji(1i,jn)[存储方法]只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。5.1.3矩阵的压缩存储1.对