- 1、本文档共17页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
云大数据结构课程教学课件多维数组和广义表
数据结构 第五章 多维数组和广义表 * 数据结构 * 多维数组和广义表为非线性结构,其逻辑特征为:一个元素可能有多个直接前趋和多个直接后继。 5.1 多 维 数 组 对多维树组的看法: 观点一:多维数组是向量的推广。n维数组中每个元素都属于n个向量,最多可以有n个直接前趋和n个直接后继。 观点二:多维数组是线性表的推广。n维数组可以看成是元素为n-1维数组组成的线性表。 观点一和观点二是统一的。 对于数组,通常只有两种操作: (1) 给定一组下标,存取相应的数据元素; (2) 给定一组下标,修改相应数据元素中的某一个或几个数据项的值。 即对于数组,通常只进行读、写操作,不进行元素的插入和删除操作。因此,一般采用顺序存储结构表示数组。 由于内存存储单元是一维结构,而数组是个多维结构,用一维内存来存 * 数据结构 * 储多维数组,则必须按某种次序将数组元素排成一个线性序列,按照这个线性序列的顺序将元素存放在内存中 两种顺序存储方法: (1) 行优先顺序(row major order) (c,pascal语言采用) 特点:在顺序放置数组元素时,元素的下标是从右往左开始排列的。 (以二维数组为例) (2) 列优先顺序(column major order) (fortran语言采用) 特点:在顺序放置数组元素时,元素的下标是从左往右开始排列的。 (以二维数组为例) a11 a12 …... a1n a21 a22…… a2n … … an1an2 ann 第1行 第2行 第n行 a11 a21 …... an1 a12 a22…… an2 … … a1na2n ann 第1列 第2列 第n列 * 数据结构 * 顺序存储的数组是一个随机存取结构,即只要知道开始元素的存储起址,维数和每一维的上、下界及单个元素所占单元数,便可将数组元素的存储地址表示为其下标的线性函数。 (以二维数组为例,且数组采用行优先顺序) LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d d为单个元素 所占单元数 开始元素的 存储起址 n为列数 c语言中因数组下标从0开始,因此上面的式子应改为: LOC(aij)=LOC(a00)+(i*n+j)*d 5.2 矩阵的压缩存储 在高级语言中,矩阵通常采用二维数组来存储,这样存储一是可以随机访问元素,再一个可以较方便地实现矩阵的运算。 然而,在工程问题中,往往会遇到一些高阶矩阵,这些高阶矩阵中有许多值相同的元素或是零的元素,为了节省存储空间,对这样一些矩阵通 * 数据结构 * 常不是直接用二维数组进行存储,而是对其进行压缩存储,即多个值相同的元素只分配一个存储空间,值为0的元素不分配空间。 采用压缩存储的矩阵分为两类:特殊矩阵和稀疏矩阵。 5.2.1 特 殊 矩 阵 特殊矩阵指的是非零元素或零元素的分布有一定规律的矩阵。对特殊矩阵常采用一维数组存储。 需解决的问题:如何将二维数组元素下标转换成一维数组元素下标。 1.对称矩阵 已知n阶方阵A,若其元素满足如下性质: aij=aji 0=i,j=n-1 则称A为对称矩阵。 显然,对于对称矩阵只需存储上三角或下三角矩阵元素即可,这样可节省将近一半的存储空间。下面以存储下三角矩阵为例具体说明。 需存储元素的个为n(n+1)/2,该数决定了一维数组s的大小。 * 数据结构 * 将二维数组元素下标转换成一维数组元素下标,即确定aij与s[k]的对应关系。 若i=j 则 k=i*(i+1)/2+j 若 ij 则 k=j*(j+1)/2+i (这是由对称性质决定的) 根据转换公式,可以得到aij的存储起址,对其进行访问。 注意:进行压缩存储后,没有改变原采用二维数组存储时能进行随机访问的特性。 2.三角矩阵 三角矩阵以主对角线划分,可分为上三角矩阵和下三角矩阵。前者的特点是:下三角中所有元素均为常数,后者的特点是:上三角中所有元素均为常数。 对于三角矩阵
文档评论(0)