补充内容-数组

1 补充内容数组 数据结构 2 数组定义及多维数组稀疏矩阵的三元组表示 主要内容 3 数组定义数组的逻辑结构 基本特点 操作等数组的存储 第一节数组定义及多维数组 4 inta 10 inta n m a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 5 1 数组的定义 数组 Array 是n n 1 个相同类型数据元素a0 a1 an 1构成的有限序列 集合中的每个元素都是由一个值和一组下标组成 A i A j i A j i k 6 2 数组的特点 数组中的数据元素数目固定 数组中的数据元素具有相同的数据类型 数组中的每一个数据元素都和一组唯一的下标值对应 7 数组与线性表的比较线性表的顺序存储结构常借助一维数组来描述 数组是线性表的推广 3 数组与线性表 8 一维数组是定长线性表 二维数组a m n m个长度为n的线性表 每行为线性表的一个元素 构成的线性表 此时的线性表中的元素本身也是一个线性表 9 二维数组a m n n个长度为m的线性表 每一列为线性表的一个元素 构成的线性表 此时的线性表中的元素本身也是一个线性表 10 数组是一个具有固定格式和数量的数据有序集 每一个数据元素有唯一的一组下标来标识 因此 在数组上不能做插入 删除数据元素的操作 通常在各种高级语言中数组一旦被定义 每一维的大小及上下界都不能改变 我们着重研究二维和三维数组 因为它们的应用是广泛的 尤其是二维数组 区别于线性表的操作 11 4 数组的基本操作 随机存 给定一组下标 存一个数据元素到该组下标对应的内存单元中 随机取 从给定的一组下标所对应的内存单元中取一个数据元素 数组列表 列出数组中的每个数据元素 矩阵运算 矩阵运算一般包括矩阵加 矩阵减 矩阵乘和矩阵求逆 针对二维数组 12 5 数组的存储结构 一维数组的存储二维数组的存储 13 一维数组的存储 对于一维数组 因为元素之间的关系是线性的 所以一维数组就顺序地存放在一组连续的存储单元中 设有数组a的每个元素占有k个存储单元 则数组a中第i个元素ai 0 i n 1 的存储首地址为 Loc ai Loc a0 i k 0 i n 1 14 1000a0a1a2 an 1一维数组的存储表示 15 二维数组可有两种存储方式 一种以行序为主序的存储方式 一种是以列序为主序的存储方式 在许多高级语言 如C语言 PASLAL语言中 都是以行序为主序的存储结构 二维数组的存储 16 行序为主序 对一个如图所示的m行n列的二维数组Am n 以行序为主序存储时 二维数组的线性排列次序为 1 1 11 10 1 1 11 10 1 0 01 00 n m m m n n a a a a a a a a a L L L L 17 其中 二维数组中任一数据元素的存储首址为 其中n为列数 Loc aij Loc a00 i n j kK为每个数据元素占用的存储单元 18 列序为主序 以列序为主序存储时 二维数组的线性排列次序为 19 其中 二维数组中任一数据元素的存储首址为 其中m为行数 Loc aij Loc a00 j m i kK为每个数据元素占用的存储单元 20 数组元素的存储位置是其下标的线性函数 一旦确定了数组各维的长度 数组元素的存储位置就是常数 因而计算各个元素存储位置的时间相等 所以存储数组中任一元素的时间也相等 称具有这一特点的存储结构为随机存储结构 随机存储结构 21 稀疏矩阵三元组表示三元组顺序表 第二节稀疏矩阵的三元组表示 22 1 稀疏矩阵 稀疏矩阵 对一个m n的矩阵 若矩阵中非零元素的个数远远小于矩阵元素个数 即矩阵中大多数元素的值为零 而只有少数的非零元素 这些非零元素在矩阵中的分布又没有一定的规律 则称其为稀疏矩阵 23 稀疏矩阵 24 2 三元组表示 三元组的定义三元组顺序表的结构描述 25 三元组的定义 三元组 用来描述稀疏矩阵中非零元素的值及其分布规律 它是由非零元素的值以及非零元素在矩阵中的行下标和列下标组成 形式为 i j d 26 这样稀疏矩阵中的每一个非零元素需由一个三元组唯一确定 如图所对应的三元组有 0 2 11 0 4 17 1 1 25 3 0 19 4 3 37 5 6 50 27 28 3 三元组顺序表 稀疏矩阵的每一个非零元素由一个三元组惟一确定 稀疏矩阵的所有元素构成三元组线性表 将稀疏矩阵中的三元组线性表用顺序存储结构表示 就构成了三元组顺序表 29 三元组的结构描述 typedefstruct inti 行号 intj 行号 elemtyped 非零元素值 TupNode 三元组类型 30 typedefstruct introws 行数intcols 列数intnums 非零元素个数