数据结构数组与广义表.ppt
《数据结构数组与广义表.ppt》由会员分享,可在线阅读,更多相关《数据结构数组与广义表.ppt(46页珍藏版)》请在课桌文档上搜索。
1、第五章 数组和广义表,1,第五章 数组和广义表,本章前讨论的线性结构数据元素都是非结构的原子类型,元素值不可再分。本章讨论了两种数据结构数组和广义表。作为线性表的扩展,表中的数据元素也是一种数据结构。数组这种数据结构可以看成是线性表的推广。广义表是另一种推广形式的线性表,是一种灵活的数据结构,在许多方面有广泛的应用。,2,知识结构图,数组与广义表,数 组,广义表,类型定义,表示方法,稀疏矩阵,特殊矩阵,存储结构,逻辑结构,应用,压缩存储,各种运算,3,5.1 数组,数组是n(n1)个相同数据类型的数据元素a0,a1,a2,.,an-1构成的占用一块地址连续的内存单元的有限序列。,数组中任意一个
2、元素可以用该元素在数组中的位置来表示,数组元素的位置通常称作数组的下标。,4,5.1.1 数组的概念及其与线性表的关系,由定义知,n维数组中有b1b2 bn个数据元素,每个数据元素都受到n维关系的约束。直观的n维数组 以二维数组为例讨论。将二维数组看成是一个定长的线性表,其每个元素又是一个定长的线性表。设二维数组A=(aij)mn,则 A=(1,2,p)(p=m或n)其中每个数据元素j是一个列向量(线性表):j=(a1j,a2j,amj)1jn或是一个行向量:i=(ai1,ai2,ain)1im如图5-1所示。,5,6,n维数组的特点,每个数据元素都受着n个关系的约束;在每个关系中,元素(0=
3、ji=bi-2)都有一个直接后继;数据元素都必须属于同一数据类型;n=1时,退化为定长的线性表;n维数组可以看成是线性表的推广。数组一旦被定义,则维数已定,对于数组的操作只有存取元素和修改元素。(一旦建立了数组,数组中的元素个数和元素之间的关系就不再发生变动)数组是多维的结构,而存储空间是一个一维的结构。(存储时需要一个次序约定),7,5.1.2 数组的顺序存储结构,数组的实现机制,8,行向量 下标 i 页向量 下标 i列向量 下标 j 行向量 下标 j 列向量 下标 k二维数组 三维数组,9,数组的顺序表示-小结,n维数组的特点:数据元素同属于一种数据类型;数组一旦被定义,则维数和各维长度不
4、能改变;数组操作只有引用型操作,没有加工型操作;数组是多维结构,但存储空间是一维结构。数组顺序表示的特点存储单元地址连续(需要一段连续空间)存储规则(以行(列)为主序)决定元素实际存储位置随机存取存储密度最大(100%),10,5.2 矩阵的压缩存储,在科学与工程计算问题中,矩阵是一种常用的数学对象,在高级语言编程时,通常将一个矩阵描述为一个二维数组。这样,可以对其元素进行随机存取,各种矩阵运算也非常简单。对于高阶矩阵,若其中非零元素呈某种规律分布或者矩阵中有大量的零元素,若仍然用常规方法存储,可能存储重复的非零元素或零元素,将造成存储空间的大量浪费。对这类矩阵进行压缩存储:多个相同的非零元素
5、只分配一个存储空间;零元素不分配空间。,11,5.2.1 特殊矩阵的压缩存储,1.对称矩阵n阶矩阵A中元素满足性质aij=aji(1i,jn)。,(即aij=aji,1=i,j=n),LTA0.n(n+1)/2-1,k=0 1 2 n(n+1)/2-1,12,13,k的含义:按行优先,是第k个(从0开始),i=3,j=2,k=4,公式的推导(下三角)i=3,j=2则前面有一个i-1行的完整三角形,共有元素(1+i-1)(i-1)/2=i(i-1)/2个另外,同一行,前面还有j-1个元素所以,k=i(i-1)/2+j-1,14/50,2、三角矩阵,以主对角线划分,n阶三角矩阵有n阶上三角矩阵和n
6、阶下三角矩阵两种。n阶上三角矩阵的下三角(不包括主对角线)中的元素均为0(或常数)。n阶下三角矩阵正好相反,它的主对角线上方均为0(或常数)。注:在大多数情况下,n阶三角矩阵常数为零。,下三角矩阵元素ai j保存在向量sa中时的下标值k与(i,j)之间的对应关系是:,15,5.2.2 稀疏矩阵的压缩存储,稀疏矩阵:设m行n列的矩阵含t个非零元素,则=t/(m*n)称为稀疏因子,通常认为 0.05 的矩阵为稀疏矩阵。,(1)、稀疏矩阵矩阵中非零元素的个数远远小于矩阵元素个数。(2)、稠密矩阵 一个不稀疏的矩阵。(3)、稀疏矩阵压缩存储方法 只存储稀疏矩阵中的非零元素,实现方法是:将每个非零元素用
7、一个三元组(i,j,aij)来表示,则每个稀疏矩阵可用一个三元组线性表来表示。,16,1、三元组顺序表稀疏矩阵和对应的三元组线性表,若把稀疏矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵的三元组顺序表。,17,三元组表表示的稀疏矩阵转置,18,18,稀疏矩阵的转置 Tij=Mji,19,稀疏矩阵用三元组表示的转置,行数和列数交换i、j的值相互交换重排三元组之间的次序,20,用三元组表示,求稀疏矩阵M的转置矩阵T,M,T,1.行数和列数交换,总个数不变:T.m=M.n;T.n=M.m;T.t=M.t;2.让q定位T中的第一条记录:q=1;,6 5 6,21,M,T,3.让col取M的每一列
8、:for(col=1;col=M.n;col+)4.让p扫描三元组M的每一条记录:for(p=1;p=M.t;p+),6 5 6,col=1,22,M,T,6 5 6,col=1,5.如果p指向的记录的j下标与col相等:if(M.datap.j=col),23,M,T,6 5 6,col=1,6.把M中的记录p复制到T中的记录q:T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.v=M.datap.v;7.让q下移:q+;,1 3-3,24,M,T,6 5 6,col=2,1 3-3,2 1 12,2 5 18,25,M,T,6 5 6,col=
9、3,1 3-3,2 1 12,2 5 18,3 1 9,3 4 24,26,M,T,6 5 6,col=6,1 3-3,2 1 12,2 5 18,3 1 9,3 4 24,6 3 14,27,(1)稀疏矩阵的转置:“按需查找”法,简单算法的分析稀疏矩阵转置算法复杂度=O(n*t)比较一般矩阵的转置算法:其复杂度=O(m*n)如果t和m*n一个数量级,则稀疏矩阵转置算法复杂度=O(m*n2)所以此算法只适用于tm*n时,for(col=1;col=nu;col+)for(row=1;row=mu;row+)Tcolrow=Mrowcol;,28,算法的实现附设两个辅助向量num 和cpot。n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数组 广义
链接地址:https://www.desk33.com/p-229782.html