数据结构数组和广义表.ppt
《数据结构数组和广义表.ppt》由会员分享,可在线阅读,更多相关《数据结构数组和广义表.ppt(46页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、关于数据结构数组与关于数据结构数组与广义表广义表第一张,PPT共四十六页,创作于2022年6月第五章第五章 数组和广义表数组和广义表l本章前讨论的线性结构数据元素都是非结构的本章前讨论的线性结构数据元素都是非结构的原子原子类型类型,元素值不可再分。本章讨论了两种数据,元素值不可再分。本章讨论了两种数据结构结构数组和广义表。作为线性表的扩展,表中数组和广义表。作为线性表的扩展,表中的数据元素也是一种数据结构。的数据元素也是一种数据结构。l数组数组这种数据结构可以看成这种数据结构可以看成是线性表的推广是线性表的推广。l广义表广义表是另一种推广形式的线性表,是一种灵活的是另一种推广形式的线性表,是一
2、种灵活的数据结构,在许多方面有广泛的应用。数据结构,在许多方面有广泛的应用。第二张,PPT共四十六页,创作于2022年6月2知识结构图知识结构图数组与广义表数组与广义表 数数 组组广义表广义表类类型型定定义义表表示示方方法法稀稀疏疏矩矩阵阵特特殊殊矩矩阵阵存存储储结结构构逻逻辑辑结结构构 应应用用压压缩缩存存储储各各种种运运算算第三张,PPT共四十六页,创作于2022年6月35.1 数组数组数组数组是是n(n1)个相同数据类型的数据元素个相同数据类型的数据元素a0,a1,a2,.,an-1构成的构成的占用一块地址连续的内存单元的有限序列。占用一块地址连续的内存单元的有限序列。数组中任意一个元素
3、可以用该元素在数组中的位置来表示,数组元数组中任意一个元素可以用该元素在数组中的位置来表示,数组元素的位置通常称作素的位置通常称作数组的下标数组的下标。第四张,PPT共四十六页,创作于2022年6月45.1.1 数组的概念及其与线性表的关系数组的概念及其与线性表的关系 由定义知由定义知,n维数组中有维数组中有b1 b2 bn个数据元素个数据元素,每个数据元素都受每个数据元素都受到到n维关系的约束维关系的约束。直观的直观的n维数组维数组 以二维数组为例讨论。以二维数组为例讨论。将二维数组看成是一个定长的线性表,其每个将二维数组看成是一个定长的线性表,其每个元素又是一个定长的线性表元素又是一个定长
4、的线性表。设二维数组设二维数组A=(aij)m n,则,则 A=(1,2,p)(p=m或或n)其中每个数据元素其中每个数据元素j是一个列向量是一个列向量(线性表线性表):j=(a1j,a2j,amj)1jn或或是一个行向量是一个行向量:i=(ai1,ai2,ain)1 i m如图如图5-1所示。所示。第五张,PPT共四十六页,创作于2022年6月5 a11 a12 a1n a21 a22 a2n am1 am2 amnA=A=a11 a12 a1na21 a22 a2nam1 am2 amna11 a21 am1a12 a22 am2a1n a2n amnA=图图5-1 二维数组图二维数组图例
5、形式例形式(a)矩阵矩阵表示形式表示形式(b)行行向量的一维数组形式向量的一维数组形式(c)列向量的一维数组形式列向量的一维数组形式第六张,PPT共四十六页,创作于2022年6月6n维数组的特点维数组的特点l每个数据元素都受着每个数据元素都受着n n个关系的约束;个关系的约束;l在每个关系中,元素在每个关系中,元素 (0=j(0=ji i=b=bi i-2)-2)都有一个直接后继都有一个直接后继;l数据元素都必须属于同一数据类型数据元素都必须属于同一数据类型;ln=1n=1时,退化为定长的线性表;时,退化为定长的线性表;ln n维数组可以看成是线性表的推广。维数组可以看成是线性表的推广。l数组
6、一旦被定义,则维数已定,对于数组的操作只有存取元素和修数组一旦被定义,则维数已定,对于数组的操作只有存取元素和修改元素。改元素。(一旦建立了数组,数组中的元素个数和元素之间的关系就不再一旦建立了数组,数组中的元素个数和元素之间的关系就不再发生变动发生变动)l数组是多维的结构,而存储空间是一个一维的结构。(存储时需要一个次数组是多维的结构,而存储空间是一个一维的结构。(存储时需要一个次序约定)序约定)第七张,PPT共四十六页,创作于2022年6月75.1.2 数组的顺序存储结构数组的顺序存储结构数组的实现机制数组的实现机制a的内存单元地址的内存单元地址每个元素所需的字节个数每个元素所需的字节个数
7、第八张,PPT共四十六页,创作于2022年6月8行向量行向量行向量行向量 下标下标下标下标 i i 页向量页向量页向量页向量 下标下标下标下标 i i列向量列向量列向量列向量 下标下标下标下标 j j 行向量行向量行向量行向量 下标下标下标下标 j j 列向量列向量列向量列向量 下标下标下标下标 k k二维数组二维数组二维数组二维数组 三维数组三维数组三维数组三维数组第九张,PPT共四十六页,创作于2022年6月9数组的顺序表示数组的顺序表示-小结小结ln维数组的特点维数组的特点:l数据元素同属于一种数据类型;数据元素同属于一种数据类型;l数组一旦被定义,则维数和各维长度不能改变;数组一旦被定
8、义,则维数和各维长度不能改变;l数组操作只有引用型操作,没有加工型操作;数组操作只有引用型操作,没有加工型操作;l数组是多维结构,但存储空间是一维结构。数组是多维结构,但存储空间是一维结构。l数组顺序表示的特点数组顺序表示的特点l存储单元地址连续(需要一段连续空间)存储单元地址连续(需要一段连续空间)l存储规则(以行(列)为主序)决定元素实际存储位置存储规则(以行(列)为主序)决定元素实际存储位置l随机存取随机存取l存储密度最大(存储密度最大(100%100%)第十张,PPT共四十六页,创作于2022年6月105.2 矩阵的压缩存储矩阵的压缩存储 在科学与工程计算问题中,矩阵是一种常用的数学对
9、象,在科学与工程计算问题中,矩阵是一种常用的数学对象,在高级语言编程时,通常将一个矩阵描述为一个二维数组。在高级语言编程时,通常将一个矩阵描述为一个二维数组。这样,可以对其元素进行随机存取,各种矩阵运算也非常简这样,可以对其元素进行随机存取,各种矩阵运算也非常简单。单。对于对于高阶矩阵高阶矩阵,若其中,若其中非零元素呈某种规律分布非零元素呈某种规律分布或者或者矩阵中有大量的零元素矩阵中有大量的零元素,若仍然用常规方法存储,可能存,若仍然用常规方法存储,可能存储重复的非零元素或零元素,将造成存储空间的大量浪费。储重复的非零元素或零元素,将造成存储空间的大量浪费。对这类矩阵进行压缩存储:对这类矩阵
10、进行压缩存储:多个相同的非零元素只分配一个存储空间多个相同的非零元素只分配一个存储空间;零元素不分配空间。零元素不分配空间。第十一张,PPT共四十六页,创作于2022年6月115.2.1 5.2.1 特殊矩阵的压缩存储特殊矩阵的压缩存储l1.对称矩阵对称矩阵n阶矩阵阶矩阵A中元素满足性质中元素满足性质aij=aji(1i,jn)。(即aij=aji,1=i,j=n)a11a21a22aijannLTA0.n(n+1)/2-1k=0 1 2 n(n+1)/2-1第十二张,PPT共四十六页,创作于2022年6月12lk的含义:按行优先,是第k个(从0开始)156752896830790415268
11、37904i=3j=2k=4l公式的推导(下三角)li=3,j=2l则前面有一个i-1行的完整三角形,共有元素 (1+i-1)(i-1)/2=i(i-1)/2个l另外,同一行,前面还有j-1个元素l所以,k=i(i-1)/2+j-1第十三张,PPT共四十六页,创作于2022年6月132 2、三角矩阵、三角矩阵 以主对角线划分,以主对角线划分,n阶三角矩阵有阶三角矩阵有n阶上三角矩阵和阶上三角矩阵和n阶下三角矩阵两种。阶下三角矩阵两种。n阶上三角矩阵的下三角(不包括主对角线)中的元素均为阶上三角矩阵的下三角(不包括主对角线)中的元素均为0(或常数)。(或常数)。n阶下三角矩阶下三角矩阵正好相反,
12、它的主对角线上方均为阵正好相反,它的主对角线上方均为0(或常数)。(或常数)。注:在大多数情况下,注:在大多数情况下,n阶三角矩阵常数为零。阶三角矩阵常数为零。第十四张,PPT共四十六页,创作于2022年6月14 下三角矩阵元素下三角矩阵元素ai j保存保存在向量在向量sa中时的中时的下标值下标值k与(与(i,j)之间的对应关系之间的对应关系是:是:i(i-1)/2+j 当当ij时时n(n+1)/2 当当ij 时时K=1i,jn (5-5)第十五张,PPT共四十六页,创作于2022年6月155.2.2 稀疏矩阵的压缩存储稀疏矩阵的压缩存储l稀稀疏疏矩矩阵阵:设设m行行n列列的的矩矩阵阵含含t个
13、个非非零零元元素素,则则=t/(m*n)称称为为稀稀疏疏因因子子,通常认为通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。(1)、稀疏矩阵、稀疏矩阵矩阵中非零元素的个数远远小于矩阵元素个数。矩阵中非零元素的个数远远小于矩阵元素个数。(2)、稠密矩阵、稠密矩阵 一个不稀疏的矩阵。一个不稀疏的矩阵。(3)、稀疏矩阵压缩存储方法、稀疏矩阵压缩存储方法 只存储稀疏矩阵中的非零元素,只存储稀疏矩阵中的非零元素,实现方法是实现方法是:将每个非零元将每个非零元素用一个素用一个三元组(三元组(i,j,aij)来表示,则每个稀疏矩阵可用一个来表示,则每个稀疏矩阵可用一个三元组线性表三元组线性表三元组线性
14、表三元组线性表来表示。来表示。第十六张,PPT共四十六页,创作于2022年6月161、三元组顺序表、三元组顺序表稀疏矩阵和对应的三元组线性表稀疏矩阵和对应的三元组线性表 若把稀疏矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵的三元组顺序表。若把稀疏矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵的三元组顺序表。第十七张,PPT共四十六页,创作于2022年6月17三元组表表示的稀疏矩阵转置三元组表表示的稀疏矩阵转置18稀疏矩阵的转置 Tij=Mji 0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 24 0 0 0 0 18 0 0 0 0 0 0-3
15、 0 012 0 0 0 18 9 0 0 24 0 0 0 0 0 0 0 18 0 0 0 0 0 14 0 0566121213931-336144324521865613-32112251831934246314第十八张,PPT共四十六页,创作于2022年6月18稀疏矩阵用三元组表示的转置l行数和列数交换li、j的值相互交换l重排三元组之间的次序566121213931-336144324521865613-32112251831934246314656211231913-3631434242518第十九张,PPT共四十六页,创作于2022年6月19用三元组表示,求稀疏矩阵M的转置矩阵
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数组 广义
限制150内