文档介绍：数据结构复习 (数组和广义表)
一、数组
1、数组的顺序存储方式和地址计算方法
数组的存储方式有:
(1)行优先存储方式
(2) 列优先存储方式
例5-1 二维数组 int a[10][10], 以行优先存储, 第1 个元素的首址是100, 每个元素的长度为2,求A[4][5]的存储首址。
A[4][5]的存储首址= 100 +(4*10+5)*2=100+45*2
=190
第5章数组和广义表
2、特殊矩阵压缩存储存储及压缩时的下标变换
(1)对称矩阵和上(或下)三角矩阵的压缩存储。
例:下三角矩阵的存储,按行主序方式。
k=i(i+1)/2+j 当i>=j时
0 当i<j时
a[i][j] 在一维数组s[k] 中(i>=j)或为0(i<j)。
(2)对角矩阵
例:以三对角矩阵为例,按行主序方式存储,
仅存储非零部分。
将一个a[100][100]的三对角矩阵以行主序存入一
维数组B[298]中,元素a[65][64]在B数组中的位置k等
于。
k=
3、稀疏矩阵的存储方式
——三元组法
矩阵A中有非零元个数s远远小于矩阵元素的
总数,则称A为稀疏矩阵。
0 12 9 0 0 0
0 0 0 0 0 0
-3 0 0 0 0 14
0 0 24 0 0 0
M=
i j v
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
二、广义表
1、广义表的定义
广义表 ls=(d1,d2,……,dn)。其中每个元素可以是原子,也可以是子表。
称d1为表头,d2,……,dn为表尾。
n: 表示广义表的长度,括号层数表示广义表的深度。
2、广义表与线性表的区别
线性表(a1,a2,……,an)中每个元素都具有相同的类型,有两种存储结构:顺序表和链表。
广义表(d1,d2,……,dn)中每个元素可以是原子,也可以是子表。可以将广义表看作是线性表的推广。由于原子和子表的类型不同,所以只能用链式存储结构。
3、广义表的链式存储结构
表结点原子结点
tag=1
hp
tp
tag=0
atom
例5-2:A=(( ),(e),(a,(b,c,d)))