串、数组和广义表---一站式入门,数据结构其实很简单(数组和广义表)
数组
数组特点:结构固定,维数和维界不变。
数组基本操作:初始化、销毁、取元素、修改元素值。
一般不做插入和删除操作。
一般都是采用顺序存储结构来表示数组。
注意:数组可以是多维的,但存储数据元素的内存单元地址是一维的,因
此,在存储数组结构之前,需要解决将多维关系映射到一维关系的问题。
存储单元是一维结构,而数组是个多维结构,则用一组连续存储单元存放数组的数据元素就有个次序约定问题。
二维数组两种存储方式:以行序为主序;以列序为主序。
以行序为主序:
设数组开始存储位置LOC( 0, 0 ) ,存储每个元素需要L个存储单元
数组元素a[i][j]的存储位置是: LOC(i, j)= LOC(0,0)+(n*i+j)*L
矩阵的常规存储:
将矩阵描述为一个二维数组。
矩阵的常规存储的特点:
可以对其元素进行随机存取;
矩阵运算非常简单;存储的密度为1。
不适宜常规存储的矩阵:值相同的元素很多且呈某种规律分布;零元素多。
矩阵的压缩存储:为多个相同的非零元素只分配一个存储空间; 对零元
素不分配空间。如:对称矩阵,对角矩阵,三角矩阵,稀疏矩阵(非零元素<95%)
类型相关\矩阵类型 | 对称矩阵 | 三角矩阵 | 对角矩阵 | 稀疏矩阵 |
---|---|---|---|---|
特点 | aij=aji(1<=i,j<=n) | 对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。 | 只有对角线附近有值 | 非零元素<95% |
储存方式 | 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+ 1)/2个元素空间。 | 重复元素c共享一个元素存储空间,共占用n(n+ 1)/2+1个元素空间 |
化斜线为行,大大节省空间 |
三元组法;十字链表 |
三元组顺序表又称有序的双下标法。
a[行][列][对应位置的值]
三元组顺序表的优点:非零元在表中按行序有序存储,因此便于进
行依行顺序处理的矩阵运算。
三元组顺序表的缺点:不能随机存取。若按行号存取某一行中的非零元,则需从头开始进行查找。
广义表
广义表(又称列表Lists) 是n20个元素a0, a1, … an-1的有限序列,其中每一个a;或者是原子,或者是一个广义表。
广义表通常记作: LS= (a1,a2, … an)其中: LS为表名,n为表的长度,每一个a为表的元素。
习惯上,一般用大写字母表示广义表,小写字母表示原子。
表头:若LS非空(n≥1 ),则其第一个元素a就是表头。
记作head(LS) = a1。
注:表头可以是原子,也可以是子表。
表尾:除表头之外的其它元素组成的表。
记作tail(LS)= (a2, … an)。
注:表尾不是最后一个元素,而是一个子表。 ,
(1)广义表中数据元素有相对次序:一个直接前驱,一个直接后继。
(2)广义表的长度定义为最外层所包含元素的个数;
如:C=(a, (b, d)) 是长度为2的广义表。
(3)广义表的深度定义为该广义表展开后所含括号的重数;
A=(b, d)的深度为1, B= (A, d)的深度为2,C= (f, B, h)的深度为3。
注意: "原子” 的深度为0; "空表” 的深度为1。
(4)广义表可以为其他广义表共享;如:广义表B就共享表A。
在B中不必列出A的值,而是通过名称来引用,B= (A)
(5)广义表可以是一个递归的表。如: F=(a, F)=(a, (a, (a, …))
注意:递归表的深度是无穷值,长度是有限值。