数据结构4数组课件.ppt

第4章 数组; 数组是我们最常用的一种数据结构，各种计算机语言均有此类型。例如：顺序表、顺序栈、循环队列等。 １．数组的定义： 数组：是ｎ（ｎ＞１）个相同数据类型的数据元素a0,a1…an-1,构成的占用一块连续的内存单元的有限序列。; 数组与线性表: 相同之处:由若干个相同数据类型的数据元素组成. 不同之处: 1.存储单元连续与否 2.数据元素在逻辑意义上可分与否 3.操作不同。;２. 数组的逻辑结构;但是: 1)可将Amxn看成由m个行向量组成的向量,即 Amn={ (a00,a01,……a0n-1),(a10,a11,……a1n-1),……(am-10, am-11,……am-1n-1) };３．数组抽象数据类型： 数据集合： 　　数组的数据集合可表示为a0,a1…an-1,每个数据元素的类型为抽象数据类型:DataType．（限定顺序存储） 数据关系:线性关系. 操作集合： 各种高级程序设计语言的操作各不相同，必备的操作有： （1）求数组元素个数 （2）随机取 （3）随机存 （4）矩阵运算; 一般数组: (以二维数组为例) 多采用顺序存储: (1).按行优先顺序存储 假设：Am×n= ; L:为每个元素所占存储单元. Pascal和C语言中数组存储为此方式.;推广:假设:A[c1--d1][c2--d2];特殊矩阵：指有一定量的零元素（或相同元素），并且其分布（非零元素的位置）有一定的规律。 采用压缩顺序存储方式:只存非零元素,节省空间. 1.下三角矩阵:;非零元素aij存储地址: Loc(aij)=Loc(a00)+[i*(i+1)/2+j]*L （0≤j ≤i ≤ n-1）;;2.对称矩阵;K;例：三对角阵 An×n =;以上数组存储方式与顺序存储线性表类似 数组元素的存储位置是其下标的线性函数。;稀疏因子：设在m*n的矩阵中，有t个非零元素，令;　 含有大量零元素的矩阵,且无规律。仅存非零元素,可省空间,避免大量无意义运算,提高运算效率.; A的三元组顺序表表示: (0,0,3) (0,4,7) (1,2,-1) (2,0,-1) (2,1,-2) (4,3,2);2. 链接存储结构:;0 1 2 3 4;(3). 三元组十字链表:;为了方便算法中对矩阵的行方向和列方向的有哪些信誉好的足球投注网站。 采用动态存储结构:每个非零元素用一个结点由五个数据域组成:三个数值,两个指针. 三个数值：i，j，value.表示非零元素的行号、列号和元素值。 两个指针：Down：向下指针 Right：向右指针;链表头结点;4;转置运算：设稀疏矩阵A以三元组表顺序存储结构存放。 三元组顺序表结构定义如下：;md;例：将稀疏矩阵A进行转置;转置算法：;算法分析： 上述算法的时间复杂度为：O(sa.nd×sa.td) 关键在于非零元素个数。 当： sa.td m ×n 时，才适合用三元组表 当： sa.td ≈ m ×n 时, 不适合用三元组表 ; 一般数组, 按行、列存放，计算公式。 特殊矩阵：计算公式。(上下三角阵,对称阵,带状阵) 稀疏矩阵：表示方法： 顺序存储：三元组表 链接存储：三元组表的(单)链表, 行指针数组结构的三元组链表, 三元组十字链表 十字链表;作业补充题： 1. 二维数组A的元素由6个字符组成，行下标以0 ~ 8；列下标从1 ~ 10；问： （1）A至少需占多少字节？ （2）A的第8 列和第5行共占多少字节？ （3）若A按行存放，元素A[8,5]的起始行地址与当A按列存放时的哪一个元素的起始地址一致? ;