内容纲要

数组

数组概念及特性:

  • 数组是存储结构,是语言内建的数据类型。它可以成为多种数据结构的存储表示。它的操作只有按下标“读/写”。
  • 数组又是逻辑结构,用于问题的解决。可以有查找、定位、插入、删除等操作。
  • 一维数组的数组元素为不可再分割的单元素时,是线性结构;但它的数组元素是数组时,是多维数组,是非线性结构。

一维数组:(通常被称为向量vector)数组是相同类型的数据元素的集合,而一维数组的每个数组元素是一个序对,由下标(index)和值(value)组成。设每个数组元素占据相等的l 个存储单元,第0 号元素的存储地址为a,则第i 号数组元素的存储地址LOC(i),当i=0, LOC(i) =a;当i>0, LOC(i) =LOC( [i -1])+l = a+i*l;

多维数组:多维数组属于数组套数组,可以看做是一维数组的推广。多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界,因此它比其他复杂的非线性结构简单。

二维数组顺序存储:

行优先存放(以行为主序):Loc (a[i][j]) = a+(im+j )l(m为列数)

列优先存放(以列为主序):Loc(a[i][j]) = a+(jn+i)l(n为行数)

矩阵

特殊矩阵:指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵,为节省存储空间,对可以不存储的元素,如零元素或对称元素,不再存储。有对称矩阵、三对角矩阵、w 对角矩阵。

对称矩阵

对称矩阵:设有一个n*n 的矩阵A。如果在矩阵中,aij = aji,则此矩阵是对称矩阵。若只保存对称矩阵的对角线和对角线以上(下) 的元素,则称此为对称矩阵的压缩存储。

三角矩阵

上三角矩阵:若只存对角线及对角线以上的元素。

  • 压缩到一维数组中共有数组sa 共有n+(n-1)+······+1 = n*(n+1)/2 个元素。
  • 若i<j,属于上三角矩阵存储。数组元素a[i][j]在数组sa中没有存放,他的对称元素位置为:A[j][i] = j *( j +1 ) / 2 + i(下标从1开始减一)

下三角矩阵:若只存对角线或对角线以下的元素。

  • 压缩到一维数组中共有数组sa 共有n+(n-1)+······+1 = n*(n+1)/2 个元素。
  • 若i≥j,属于下三角矩阵存储。数组元素a[i][j]在数组sa中的存放位置为:1 + 2 + ······ + i + j = (i + 1)* i / 2 + j(下标从1开始减一)

已知某矩阵元素位于一维数组的第k 个位置,可寻找满足i (i + 1) / 2≤ k < (i + 1)(i + 2) / 2的i, 此即为该元素的行号。j = k – i (i + 1) / 2此即为该元素的列号。

三对角矩阵:矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外,所有其它元素均为0。总共有3n-2个非零元素。

将三对角矩阵A中三条对角线上的元素按行存放在一维数组中,且a00存放于a[0]。在三条对角线上的元素aij 中满足0 <= i <= n-1 , i-1 <= j <= i+1;在一维数组中A[i][j] 在第i 行,它前面有3i-1非零 元素, 在本行中第j 列前面有j-i+1 个,所以元素A[i][j] 在一维数组中位置为k = 2i + j。

稀疏矩阵

稀疏矩阵:设矩阵A 中有s 个非零元素,若s 远远小于矩阵元素的总数(即s << m×n),则称A 为稀疏矩阵。

  • 设矩阵A 中有s 个非零元素。令e = s/(m*n),称e为矩阵的稀疏因子。通常认为e≤0.05 时称之为稀疏矩阵。
  • 在存储稀疏矩阵时,为节省存储空间,应只存储非零元素。但通常非零元素的分布没有规律,故在存储非零元素时,必须记下它所在的行和列的位置( i, j )。
  • 每一个三元组(i, j, aij) 唯一确定了矩阵A的一个非零元素。因此,稀疏矩阵可由表示非零元素的一系列三元组及其行列数唯一确定。

三元顺序表

  • 把稀疏矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵的三元组顺序表。
  • 在三元组顺序表中,行为主序,所有非零元素的三元组按行号递增的顺序排列;行号相等的按列号递增的顺序排序。
  • 三元组顺序表中三元组的个数记忆在变量tu 中,此即矩阵中的非零元素个数。稀疏矩阵的行数和列数分别记忆在mu 和nu中。

行逻辑链接的顺序表:为了便于随机存取任意一行的非零元素,则需知道每一行的第一个非零元素在三元组表中的位置。为此,可将指示“行”信息的辅助数组rpos固定在稀疏矩阵的存储结构中。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。

十字链表

十字链表:一个结点除了数据域(i,j,e)之外,还应该用两个方向的指针(right:用于链接同一行中的下一个元素; down:用于链接同一列中的下一个元素),分别指向行和列。整个矩阵构成了一个十字交叉的链表,因此称十字链表。每一行和每一列的头指针,用两个一维指针数组来存放。

十字链表

广义表

广义表:广义表是线性表的推广,是n ≥ 0个元素的有限序列,记作LS = ( α1,α2,····,αn )。αi 或为原子项(原子,一般用小写字母表示),或为广义表(子表,一般用大写字母表示)。n 为广义表的长度。

原子:是作为结构上不可分割的成分,它可以是一个数或一个结构。

表头与表尾:LS不为空时,称α1为表头(head),称其余元素组成的子表( α2, α3,······,αn ) 为表尾(tail)。

任何一个非空广义表其表头可能是原子或广义表,而其表尾必定为广义表。

操作取表头,表尾,实例如下:

取表头表尾

结构特点:

  • 广义表中的数据元素有相对次序。
  • 广义表的长度定义为最外层包含元素个数。
  • 广义表的深度定义为所含括弧的重数:“原子”的深度为0 ; “空表”的深度为1。
  • 广义表可以共享
  • 广义表可以是一个递归的表。递归表的深度是无穷值,长度是有限值。

广义表的存储结构:由于广义表LS=(α1,α2,α3,…αn)中的数据元素可以具有不同的结构(或是原子,或是广义表),因此,难以用顺序存储结构表示,通常采用链式存储结构来表示。

广义表的存储结构

最后修改日期:2020年7月12日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。