V第二十二讲(广义表的逻辑结构与存储结构)

6.3.1 广义表的定义
广义表是线性表的推广，是有限个元素的序列，其逻辑 结构采用括号表示法表示如下： GL=（a1，a2，…，ai，…，an）
若n=0时称为空表 ai为广义表的第i个元素。如果ai属于原子类型，称之为广义表 GL的原子 如果ai又是一个广义表，称之为广义表GL的子表 1/18
广义表重要概念：
5/18
6.3.3 广义表的运算
1
解法1
广义表算法设计方法
整个广义表的头结点
1
∧
第1个元素 第2个元素
子表的头结点
0 a
1
∧0ຫໍສະໝຸດ b0c0 d ∧
6
子表的处理和整个广义表的处理是相似的。从这个角 度出发设计求解广义表递归算法的一般格式如下：
7/18
解法2
广义表的表结点g
g的兄弟：g->link
1
0
个算法求原子个数。
C
1
∧
0 a
1
∧
0
b
0
c
0 d ∧
原子个数为4
14/18
解：需要扫描广义表g中的所有结点，可以采用前面
介绍的广义表算法设计方法中的两种解法来实现。
15/18
//采用解法1的方法
int Count1(GLNode *g) { int n=0; GLNode *g1=g->val.sublist; while (g1!=NULL) { if (g1->tag==0) n++; else n+=Count1(g1); g1=g1->link; } return n; } //求广义表g的原子个数
广义表的长度定义为最外层包含元素个数。 广义表的深度定义为所含括弧的重数。其中，原子的深 度为0，空表的深度为1 。

数组的特点
➢元素本身可以具有某种结构，属于同一数据类型； ➢数组是一个具有固定格式和数量的数据集合。
5
数组示例
a11 a12 … a1n
A=
a21 a22 … a2n … … ……
am1 am2 … amn
例如，元素a22受两个线性关系的约束，在行上有
一个行前驱a21和一个行后继a23，在列上有一个列 前驱a12和和一个列后继a32。
维界虽未变，但此时的a[32, 58] 不再是原来的a[32, 58]
数组的存储结构与寻址——多维数组
n（n＞2）维数组一般 也采用按行优先和按列优 先两种存储方法。
（1）按行优先：最右边 的下标先变化，即最右边 下标从小到大，循环一遍 后，右边第2个下标再 变，…，最后是最左下标。
（2）按列优先：P118
每个元素占用 l 个存储单元
则a[i][j]的存储地址：
LOC ( i, j ) = a + ( j个二维数组A，行下标的范围是1到6，列下标 的范围是0到7，每个数组元素用相邻的6个字节存储， 存储器按字节编址。那么，这个数组的体积是288 个 字节。
答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288
…
ah1h2
Loc(al1l2) (i -l1)×(h2 -l2＋1)＋(j -l2)个元素 Loc(aij)
Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c
按列优先存储的寻址方法与此类似。
13
例1：如何求出a(3,2)的存储地址？
0
0 a(0,0)
1 a(1,0)
aij在本行中的序号

2 3
1
1
4
一、广义表的类型定义
广义表的特性: 有次序性,有长度,有
深度,可共享,可递归。
D
A
B
C
f
a
E
e
b
c
d
11
广义表基本操作
1．GenListNode<ElemType> *First() const 初始条件：广义表已存在。 操作结果：返回广义表的第一个元素。 2．GenListNode<ElemType> *Next(GenListNode<ElemType> *elemPtr) const 初始条件：广义表已存在，elemPtr指向的广义表元素。 操作结果：返回elemPtr指向的广义表元素的后继 3．bool Empty() const 初始条件：广义表已存在。 操作结果：如广义表为空，则返回true，否则返回false
ref (a)头结点
nextLink
tag=ATOM(1)
atom (b)原子结点
nextLink
tag=LIST(2)
subLink (c)表结点
nextLink
15
A=()，B=(x, y, z)，C=(B, y, z)，D=(x,(y, z))，E=(x, E)
A B C D E 0 0 0 0 0 1 2 1 1 2 ∧ 1 2 1 2 x ∧ x 1 1 2 0 1 y y ∧ 1 y 1 z ∧ 1 1 z z ∧ ∧
本讲小结
重点： 1、广义表的基本概念 2、广义表的存储
难点： 1、广义表的递归算法
22
例1 求广义表的深度 P174 DepthHelp() 例2 复制广义表
P173 CopyHelp()

数组的存储结构与寻址——多维数组
n（n＞2）维 数组一般也采用 按行优先和按列 优先两种存储方 法。请自行推导 任一元素存储地 址的计算方法。
Loc(aijk ) = Loc(a000) +( i×m2×m3 + j×m3 + k )×c
矩阵的压缩存储
数据结构（C#版）
特殊矩阵和稀疏矩阵
特殊矩阵：矩阵中很多值相同的元素并且它们的分布 有一定的规律。
A=
0 a21 a22 a23 0 域立起来
0 0 a32 a33 a34 0 0 0 a43 a44
B=
a21 a22 a23 a32 a33 a34 a43 a44 0
t=i 映射到二维数组B中，映射关系 s＝j-i+1
矩阵的压缩存储
数据结构（C#版）
对角矩阵的压缩存储
a00 a01 0 0 0
多维数组
数据结构（C#版）
数组的定义
数组是由一组类型相同的数据元素构成的有序集 合，每个数据元素称为一个数组元素（简称为元 素），每个元素受n(n≥1)个线性关系的约束，每 个元素在n个线性关系中的序号i1、i2、…、in称为 该元素的下标，并称该数组为 n 维数组。
数组的特点
元素本身可以具有某种结构，属于同一数据类型；
(a) 下三角矩阵
(b) 存储说明
(c) 计算方法
矩阵的压缩存储
对称矩阵的压缩存储
数据结构（C#版）
01 2 34 5
a00 a10 a11 a20 a21 a22 …
第0行 第1行
第2行
k aij …
n(n+1)/2-1
a n-10 aΒιβλιοθήκη -11 … an-1n-1第n-1行