数据结构复习数组和广义表.ppt

《数据结构复习数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构复习数组和广义表.ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构复习数组和广义表 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望一、数组1、数组的顺序存储方式和地址计算方法 数组的存储方式有：（1）行优先存储方式 （2）列优先存储方式 例5-1 二维数组 int a1010,以行优先存储,第1 个元素的首址是100,每个元素的长度为2,求A45的存储首址。A45的存储首址=100+（4*10+5）*2=100+45*2 =190 第第5章章 数组和广义表数组和广义表2、特殊矩阵压缩存储存储及压缩时的下标变换、特殊矩阵压

2、缩存储存储及压缩时的下标变换（1）对称矩阵和上（或下）三角矩阵的压缩存储。）对称矩阵和上（或下）三角矩阵的压缩存储。例：下三角矩阵的存储，按行主序方式。例：下三角矩阵的存储，按行主序方式。k=i(i+1)/2+j 当当i=j时时 0 当当i=j)或为或为0(ij)。（2）对角矩阵）对角矩阵 例：以三对角矩阵为例，按行主序方式存储，例：以三对角矩阵为例，按行主序方式存储，仅存储非零部分。仅存储非零部分。将一个将一个a100100的三对角矩阵以行主序存入一的三对角矩阵以行主序存入一维数组维数组B298中，元素中，元素a6564在在B数组中的位置数组中的位置k等等于于 。k=3、稀疏矩阵的存储方式

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 93 1 -33 6 144 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)