数据结构----数组

数组

按照一定格式排列起来的，具有相同类型的数据元素的集合

一维数组：

int num[5] = {0,1,2,3,4}

二维数组：若一维数组中的元素又是一维数组结构，称为二维数组

int num[2][3]; 两行三列

• 因为一个二维数组等于一个一维数组里面放入一维数组，所以二维数组的还可以使用下面的方式定义：

  typedef elemtype array2[m][n]

  等价于：elemtype为数据的类型，可以为int，float等

  typedef elemtype arry1[n]

  typedef arry1 arry2[m]

三维数组：若二位数数组中的元素又是一个一维数组，则称作为三维数组。

n维数组:若n-1维数组中的元素又是一个一维数组结构，则称作n维数组。

• 线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。
• 数组特点：结构固定，定以后维数和维界不再改变
• 数组的基本操作：除了结构的初始化和销毁以外，只有取元素和修改元素值的操作。

数组的存储

• 因为数组的结构固定，维数和维界不变，且数组的基本操作一般为初始化，销毁，取元素，修改元素值，一般不做插入和删除操作，故数组一般都是用顺序存储，而不使用链式存储的方式。
• 注意：数组可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。
  • 列如：定义数组

    int a[5]

    ；每个元素占用4个字节，假设a[0]存储在2000单元，a[3]存储在2012到2015；

    

  • 假设初始的地址为i，第i个元素的存储地址LOC(I) = a+i*L，L是数据结构占用的大小，如int型L=4，a是起始地址；
• 二维数组的空间存储结构
  • 有两种存储方式，行优先与列优先，C语言与JAVA等都是使用的行优先的存储方式

    

    行存储方式就是一行一行的存储，如上图所示；同理列序的存储方式就是按照列一列一列的存储
  • 有二维数组A[m][n],LOC(a[i][j]) = LOC(0, 0) + (ni+j)L;L是数据类型占用的大小，如int的时候就是4；i是所在行数，j是所在的列数，注意i和j都是从0开始的，不是从1开始的。
• 三维数组，每一个页来存，页内按照二维数组的存储方式
• n维元素的存储方式

  

特殊矩阵的压缩存储

• 对称矩阵

  

  

• 三角矩阵

  

• 对角矩阵

  

• 稀疏矩阵

  三元组的法进行保存

  

第一行代表当前矩阵有多少行多少列，且一共有多少个元素是非零的

• 三元组法的缺点，顺序读取与存储，插入和查找麻烦

  

• 稀疏矩阵的链式存储结构----十字链表

广义表

• 广义表的长度与与深度
  • 长度：最外层所包含元素的个数
  • 深度：广义表展开后所包含的括号重数