补充内容-数组.ppt

补充内容数组 主要内容 数组定义及多维数组 稀疏矩阵的三元组表示 数组定义 数组的逻辑结构，基本特点，操作等 数组的存储 1. 数组的定义 数组（Array）是n(n1)个相同类型数据元素a0,a1,…,…,an-1构成的有限序列，集合中的每个元素都是由一个值和一组下标组成。 2.数组的特点 数组中的数据元素数目固定。 数组中的数据元素具有相同的数据类型。 数组中的每一个数据元素都和一组唯一的下标值对应。 数组与线性表的比较 线性表的顺序存储结构常借助一维数组来描述。 数组是线性表的推广。 一维数组是定长线性表， 二维数组a[m][n]: m个长度为n的线性表(每行为线性表的一个元素)构成的线性表。 此时的线性表中的元素本身也是一个线性表。 二维数组a[m][n]: n个长度为m的线性表(每一列为线性表的一个元素)构成的线性表。 此时的线性表中的元素本身也是一个线性表。 4. 数组的基本操作 随机存。给定一组下标，存一个数据元素到该组下标对应的内存单元中。 随机取。从给定的一组下标所对应的内存单元中取一个数据元素。 数组列表。列出数组中的每个数据元素。 矩阵运算。矩阵运算一般包括矩阵加、矩阵减、矩阵乘和矩阵求逆。（针对二维数组） 5.数组的存储结构 一维数组的存储 二维数组的存储 一维数组的存储 对于一维数组，因为元素之间的关系是线性的，所以一维数组就顺序地存放在一组连续的存储单元中。 设有数组a的每个元素占有k个存储单元，则数组a中第i个元素ai(0≤i≤n-1)的存储首地址为： Loc(ai)=Loc(a0)+i*k (0≤i≤n-1) 1000 a0 a1 a2 ┇ ┇ an-1 一维数组的存储表示 二维数组可有两种存储方式：一种以行序为主序的存储方式，一种是以列序为主序的存储方式。 在许多高级语言（如C语言，PASLAL语言中）都是以行序为主序的存储结构。 行序为主序 对一个如图所示的m行n列的二维数组Am×n，以行序为主序存储时，二维数组的线性排列次序为： 列序为主序 以列序为主序存储时，二维数组的线性排列次序为： 数组元素的存储位置是其下标的线性函数， 一旦确定了数组各维的长度，数组元素的存 储位置就是常数，因而计算各个元素存储位 置的时间相等，所以存储数组中任一元素的 时间也相等。称具有这一特点的存储结构为 随机存储结构。 稀疏矩阵 三元组表示 三元组顺序表 1.稀疏矩阵 稀疏矩阵：对一个m×n的矩阵，若矩阵中非零元素的个数远远小于矩阵元素个数，即矩阵中大多数元素的值为零，而只有少数的非零元素，这些非零元素在矩阵中的分布又没有一定的规律，则称其为稀疏矩阵。 2. 三元组表示 三元组的定义 三元组顺序表的结构描述 ⑴三元组的定义 三元组：用来描述稀疏矩阵中非零元素的值及其分布规律，它是由非零元素的值以及非零元素在矩阵中的行下标和列下标组成，形式为：(i,j,d)。 3. 三元组顺序表 稀疏矩阵的每一个非零元素由一个三元组惟一确定，稀疏矩阵的所有元素构成三元组线性表。 将稀疏矩阵中的三元组线性表用顺序存储结构表示，就构成了三元组顺序表。 三元组的结构描述 typedef struct { int i; /*行号*/ int j; /*行号*/ elemtype d; /*非零元素值*/ }TupNode; /*三元组类型*/ typedef struct { int rows;//行数 int cols;//列数 int nums