最新数据结构课件-第5章-数组、广义表课件PPT.ppt

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

1、数据结构课件-第5章-数组、广义表第5章　数组和广义表5.1数组5.2广义表教学内容2021/8/225.1数组数据结构中的“数组”与高级语言中的“数组”区别：数据结构中的数组是一种线性结构高级语言中的数组是顺序结构；2021/8/23数组顺序存储的特点：数组中的数据元素数目固定，一旦定义，其数据元素的数目不再有增减变化；数组中的数据元素具有相同的数据类型。数组中的每个数据元素都和一组唯一的下标值对应；5.1.2数组的顺序表示与实现已知以下三要素，求数组中任一元素的地址：①开始结点的存放地址（即基地址）

2、②维数和每维的上、下界；③每个数组元素所占用的单元数a1a2a3a4a5a6a7a8a9a100123456789llllllllllLOC(ai)=一维数组5.1.2数组的顺序表示与实现LOC(a1)+（i-1）*l北京林业大学信息学院以行序为主序C,PASCAL5.1.2数组的顺序表示与实现二维数组通常有两种顺序存储方式：以行序为主序以列序为主序5.1.2数组的顺序表示与实现二维数组——以行序为主序存储a11a12……..a1na21a22……..a2nam1am2……..amn………………….Lo

3、c(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…….a21a11a11a12……..a1na21a22……..a2nam1a

4、m2……..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,m

5、3,…,mn下标为i1,i2,i3,…,in的数组元素的存储地址：LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in)*l课前任务检查请以小组为单位，回答并讲解课前任务中的题目！2021/8/2165.1.3矩阵的压缩存储2021/8/2171.什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.什么样的矩阵能够压缩？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。3.什么叫

6、稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）5.1.3矩阵的压缩存储北京林业大学信息学院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.对称矩阵a0,0a1,

7、0a1,1a2,0a2,1aijan-1,n-1…...…...01234kn(n+1)/2-1按行序为主序：ajiaijba0,0a0,1….……..A0,n-1a1,0a1,1……..…….A1,n-1an-1,0an-1,1……..An-1,n-1………………….1.对称矩阵对称矩阵typedefintElemtype;typedefstructsp_Matrix{Elemtype*data;}sp_Matrix;定义一个压缩矩阵结构voidInitMatrix(sp_Matrix*M）{M->d

8、ata=(Elemtype*)malloc(sizeof(Elemtype)*(N*(N+1/2)));}初始化对称矩阵的压缩矩阵2021/8/2211.对称矩阵对称矩阵voidAssignMatrix(sp_Matrix*M,Elemtypee,inti,intj){if(i>=j)M->data[i*(i+1)/2+j]=e;elseM->data[j*(j+1)/2+i]=e;}指定缩矩阵结构中的元素voidPrintMatrix(s