数据结构之数组和广义表

数组的定义及特点

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

数组特点：结构固定：定义后，维数和维界不再改变

数组基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作

数组的抽象数据类型定义

n维数组的抽象数据类型

ADT Array{
   数据对象：
   ji=0,bi-1, i=1,2,3...n
   D={aj1j2j3..jn|aj1j2j3..jn属于Elemset}  

   数据关系

   基本操作：
   构造数组
   销毁数组
   取数组元素值
   给数组元素赋值
   ...
}ADT Array

数组的顺序存储

一维数组

二维数组

存储单元是一维结构，而数组是个多维结构，则用一组连续存储单元存放数组的元素就有次序问题

三维数组

n维数组

特殊矩阵的压缩存储

矩阵：一个由m*n个元素排成的m行n列的表

1.对称矩阵：
可以只存储上半部分或下半部分，对于一个n*n矩阵，只需要存储n(n+1)/2个元素空间

2.三角矩阵

3.对角矩阵

以对角线的顺序存储

稀疏矩阵存储

顺序存储结构：三元组法


链式存储结构：十字链表

例如：

广义表

线性表的推广，其中每一个元素可以是原子或者一个广义表

广义表的性质

1.广义表中的数据元素有相对次序，一个直接前驱和一个直接后继
2.广义表的长度定义为最外层所包含元素的个数，如：C=(a,(b,c))是长度为2的广义表
3.广义表的深度定义为该广义表展开后所含括号的重数
4.广义表可以为其他广义表共享；如：广义表B就共享表A，在B中不必列出A的值，而是通过名称来引用，B=(A)
5.广义表可以是一个递归的表。如：F=(a,F)=(a,(a,(a,…)))
注意：递归表的深度是无穷值，长度是有限值
6.广义表是对层次结构，广义表的元素可以是氮元素，也可以是子表，而子表的元素还可以是子表