《数据结构第5章_数组和广义表》由会员分享，可在线阅读，更多相关《数据结构第5章_数组和广义表（67页珍藏版）》请在金锄头文库上搜索。
1、,Page 1,2018/9/10,第五章 数组和广义表,Page 2,2018/9/10,本章的基本内容是：数组的逻辑结构特征 数组的存储方式及寻址方法 特殊矩阵和稀疏矩阵的压缩存储方法 广义表的基本概念和存储结构,Page 3,2018/9/10,学习目标 理解多维数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主”的存储表示中的地址计算方法。 掌握特殊矩阵的存储压缩表示方法。 理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。 重点和难点 重点是学习数组类型的定义及其存储表示。 知识点 数组的类型定义、数
2、组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。,Page 4,2018/9/10,线性表具有相同类型的数据元素的有限序列。,限制插入、删除位置,线性表具有相同类型的数据元素的有限序列。,限制元素类型为字符,串零个或多个字符组成的有限序列 。,Page 5,2018/9/10,线性表具有相同类型的数据元素的有限序列。,将元素的类型进行扩充,Page 6,2018/9/10,5.1 数组的定义,数组是线性表的推广 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。,Page 7,2018/9/10,数组的抽象数据类型定义,ADT Array 数据对象
3、：ji=0,., bi-1, i=1,2,n Daj1,j2,.jn|n(0)为数组的维数，bi为数组第i维的长度， ji为数组元素的第i维下标， aj1,j2,.jn ElemSet 数据关系：RR1, R2, ., Rn Ri | 0jkbk-1, 1kn 且ki, 0jibi-2, aj1,，ji, ,jn, aj1,，ji+1, ,jn D, i=2,.,n ,Page 8,2018/9/10,基本操作,InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法，则构造相应的数组A。DestroyArray(&A) 初始条件：数组 A
4、已经存在。 操作结果：销毁数组 A。Value(A, &e, index1, ., indexn) 初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A, e, index1, ., indexn) 初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若下标不超界，则将 e 的值赋给A中指定下标的元素。 ADT Array,Page 9,2018/9/10,关于数组的基本操作,在数组中插入（或）一个元素有意义吗？,将元素 x 插入 到数组中第1行第2列。,删除数组
5、中 第1行第2列元素。,Page 10,2018/9/10, 存取：给定一组下标，读出对应的数组元素； 修改：给定一组下标，存储或修改与其相对应的数组元素。存取和修改操作本质上只对应一种操作寻址,数组应该采用何种方式存储？,数组没有插入和删除操作，所以，不用预留空间，适合采用顺序存储。,关于数组的基本操作,Page 11,2018/9/10,数组的存储结构与寻址一维数组,设一维数组的下标的范围为闭区间l，h，每个数组元素占用 c 个存储单元，则其任一元素 ai 的存储地址可由下式确定： Loc(ai)Loc(al)(il)c,5.2 数组的顺序表示和实现,Page 12,2018/9/10,常
6、用的映射方法有两种： 按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。 按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。,数组的存储结构与寻址二维数组,Page 13,2018/9/10,l2,h2,l1,h1,(a) 二维数组,aij前面的元素个数 =阴影部分的面积 =整行数每行元素个数+本行中aij前面的元素个数 =(i -l1)(h2 -l21)(j -l2),按行优先存储的寻址,Page 14,2018/9/10,假设有60行70列的二维数组a160, 170以行序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第3
7、2行第58列的元素a32,58的存储地址为（ ）。（无第0行第0列元素） ） 16902 B）16904 ）14454 ）答案A, B, C均不对,Page 15,2018/9/10,第l1行,第l1+1行,(i -l1)(h2 -l21)(j -l2)个元素,Loc(aij)Loc(al1l2)(il1)(h2l21)(jl2)c,按行优先存储的寻址,按列优先存储的寻址方法与此类似。,Page 16,2018/9/10,Loc(aijk ) = Loc(a000) +( im2m3 + jm3 + k )c,n（n2）维数组一般也采用按行优先和按列优先两种存储方法。请自行推导任一元素存储地址
8、的计算方法。,数组的存储结构与寻址多维数组,Page 17,2018/9/10,5.3 矩阵的压缩存储,压缩存储 为多个值相同的矩阵元只分配一个存储空间； 对零元不分配空间。,Page 18,2018/9/10,特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律。 稀疏矩阵：矩阵中有很多零元素。,压缩存储的基本思想是： 为多个值相同的元素只分配一个存储空间； 对零元素不分配存储空间。,特殊矩阵和稀疏矩阵,Page 19,2018/9/10,特殊矩阵的压缩存储对称矩阵,3 6 4 7 8 6 2 8 4 2 4 8 1 6 9 7 4 6 0 5 8 2 9 5 7,A,对称矩阵特点：a
9、ij=aji,如何压缩存储？,只存储下三角部分的元素。,5.3.1 特殊矩阵,Page 20,2018/9/10,(a) 下三角矩阵 (b) 存储说明 (c) 计算方法,aij在一维数组中的序号 =阴影部分的面积 = i(i+1)/2+ j+1 一维数组下标从0开始 aij在一维数组中的下标 k= i(i+1)/2+ j,0i n-1,0 j n-1,aij,对称矩阵的压缩存储,Page 21,2018/9/10,对于下三角中的元素aij（ij），在数组SA中的下标k与i、j的关系为：ki(i1)/2j 。 上三角中的元素aij（ij），因为aijaji，则访问和它对应的元素aji即可，即：k
10、j(j1)/2i 。,对称矩阵的压缩存储,Page 22,2018/9/10,特殊矩阵的压缩存储三角矩阵,3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8 2 9 5 7,(a) 下三角矩阵,3 4 8 1 0 c 2 9 4 6 c c 5 7 c c c 0 8 c c c c 7,(b) 上三角矩阵,如何压缩存储？,只存储上三角（或下三角）部分的元素。,Page 23,2018/9/10,矩阵中任一元素aij在数组中的下标k与i、j的对应关系：,下三角矩阵的压缩存储,Page 24,2018/9/10,矩阵中任一元素aij在数组中的下标k与i、j的对应关
11、系：,上三角矩阵的压缩存储,Page 25,2018/9/10,特殊矩阵的压缩存储对角矩阵,对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。,a00 a01 0 0 0 a10 a11 a12 0 0 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 a43 a44,A=,Page 26,2018/9/10,按行 存储,元素aij在一维数组中的序号 =2 + 3(i1)+( ji + 2) =2i+ j+1一维数组下标从0开始 元素aij在一维数组中的下标 =2i+ j,(b) 寻址的计算方
12、法,对角矩阵的压缩存储,k=(m-1)i+j+(m-1)/2-1 下标,Page 27,2018/9/10,如何只存储非零元素？,注意：稀疏矩阵中的非零元素的分布没有规律。,5.3.2 稀疏矩阵,稀疏矩阵,Page 28,2018/9/10,5.3.2 稀疏矩阵,稀疏矩阵 非零元较零元少，且分布没有一定规律的矩阵。 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值。,矩阵维数 （6,7）非零元 (1,2,12) (1,3,9) (3,1,-3) (3,6,14),(4,3,24) (5,2,18) (6,1,15) (6,4,-7),如何存储三元组表？,Page 29,2018/9
13、/10,压缩存储稀疏矩阵(三元组顺序表),以顺序存储结构来表示三元组。 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 12500 /假设非零元个数的最大值为12500 typedef struct int i,j; /该非零元的行下标和列下标 ElemType e; Triple; typedef struct Triple dataMAXSIZE+1; /非零元三元组表，data0未用 int mu,nu,tu; /矩阵的行数、列数和非零元个数 TSMatrix ;,行序,Page 30,2018/9/10,6 7 8,1 2 12,1 3 9,3 1 -3,3 6 14,
14、4 3 24,5 2 18,6 1 15,6 4 -7,data,i j e,0 1 2 3 4 5 6 7 8,data0.i,data0.j,data0.e分别存放矩阵行列维数和非零元个数,是否对应惟一的稀疏矩阵？,Page 31,2018/9/10,求转置矩阵,问题描述 已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。 解决思路 将矩阵行、列维数互换； 将每个三元组中的i和j相互调换； 重排三元组次序。,Page 32,2018/9/10,?,Page 33,2018/9/10,方法一：按矩阵的列序转置 按T.data中三元组次序依次在M.data中找到相应的三元组进行转置。,7 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,col=1,col=2,Page 34,2018/9/10,1. 设置转置后矩阵T的行数、列数和非零元个数； 2. 在T中设置初始存储位置q； 3. for (col=最小列号; col=最大列号; col+)3.1 在M中查找列号为col的三元组；3.2 交换其行号和列号，存入T中q位置；3.3 +q；,
