本 章 说 明 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存贮结构

Presentation on theme: "本 章 说 明 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存贮结构"— Presentation transcript:

1 本 章 说 明 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存贮结构
5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存贮结构 本 章 小 结 返回主目录

2 理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主” 、“以列为主”的存储表示中的地址计算方法。
本章说明 学习目标 理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主” 、“以列为主”的存储表示中的地址计算方法。 掌握特殊矩阵的存储压缩表示方法。 理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。 从学习利用高级语言编制程序开始，数组是大家惯用的存储批量数据的工具，前几章讨论的线性结构的顺序存储结构也都是利用数组来描述的，那么数组本身又是怎么实现的呢？因此本章的学习目的主要是了解数组类型的特点以及在高级编程语言中的实现方法。对于本章讨论的随机稀疏矩阵运算的各个算法主要是理解问题的处理方法。 　

3 数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。
本章说明 重点和难点 重点是学习数组类型的定义及其存储表示。 知识点 数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储表示方法。 从学习利用高级语言编制程序开始，数组是大家惯用的存储批量数据的工具，前几章讨论的线性结构的顺序存储结构也都是利用数组来描述的，那么数组本身又是怎么实现的呢？因此本章的学习目的主要是了解数组类型的特点以及在高级编程语言中的实现方法。对于本章讨论的随机稀疏矩阵运算的各个算法主要是理解问题的处理方法。 　

4 5.1 数组的定义 数组是线性表的推广 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。 列向量 行向量
二维数组可定义为"其数据元素为一维数组的线性表"。可表示为： 　　A(2) = ( A(1)0，A(1)1，……，A(1)m-1 ) 　其中每个数据元素是一个一维数组 　　A(1)i = ( ai,0，ai,1，……，ai,n-1 ) i = 0，1，……，m-1 　类似地，N维数组是N-1维数组的线性表 　　A(N) = ( A(N-1)0，A(N-1)1，……，A(N-1)s-1 ) 行向量

5 5.1 数组的定义 数组的抽象数据类型定义 ADT Array {
数据对象：ji=0,..., bi-1, i=1,2,..,n D＝{aj1,j2,...jn|n(>0)为数组的维数，bi为数组第i维的长度， ji为数组元素的第i维下标， aj1,j2,...jn ∈ElemSet } 数据关系：R＝{R1, R2, ..., Rn} Ri＝{< aj1,…，ji, …,jn, aj1,…，ji+1, …,jn > | 　　　　　　　　　0≤jk≤bk-1, 1≤k≤n 且ki, 　　　　　　　　　0≤ji≤bi-2, 　　　　　　　　　aj1,…，ji, …,jn, aj1,…，ji+1, …,jn ∈D, i=2,...,n } 二维数组中共有 mn 个元素，每个元素 同时处于"行"和"列"的两个关系中，它既在"行关系ROW"中是 (i>0)的后继，又在"列关系COL"中是 (j>0)的后继。 　　

6 5.1 数组的定义 基本操作: InitArray(&A, n, bound1, ..., boundn) 操作结果：若维数 n 和各维长度合法，则构造相应的数组A。 DestroyArray(&A) 初始条件：数组 A 已经存在。 操作结果：销毁数组 A。 Value(A, &e, index1, ..., indexn) 初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。 Assign(&A, e, index1, ..., indexn) 初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若下标不超界，则将 e 的值赋给A中指定下标的元素。 } ADT Array 数组一旦被定义，其维数(N)和每一维的上、下界均不能再变，数组中元素之间的关系也不再改变。因此数组的基本操作除初始化和结构销毁之外，只有通过给定的"一组下标"索引取得元素或修改元素的值。

7 “以行(序)为主(序)” ：对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中
5.2 数组的顺序表示和实现 用一组连续的存储单元来表示数组。 有两种映象方法： “以行(序)为主(序)” ：对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中 “以列(序)为主(序)”对二维数组进行“按列切分”，即将数组中的数据元素"按列依次排放"在存储器中。　 由于数组不作插入和删除的操作，因此,采用顺序存储结构表示数组是自然的事。这是我们只介绍数组的顺序存储表示的原因。 由于数组中的数据元素之间是一个"多维"的关系，而存储地址是一维的，因此数组的顺序存储表示要解决的是一个"如何用一维的存储地址来表示多维的关系"的问题。 现有的高级语言中的大多数都是按"以行为主"实现数组类型的。

8 5.2 数组的顺序表示和实现 按行序为主序存放 a00 1 a01 ……. a0,n-1 n-1 a10 n a11 …….. a1,n-1
1 n-1 m*n-1 n a00   按行序为主序存放 a01 ……. a0,n-1 a10 a11 …….. a1,n-1 ……… am-1,0 am-1,1 …….. am-1,n-1

9 5.2 数组的顺序表示和实现 按列序为主序存放 a00 a10 1 ……. am-1,1 m-1 m a01 a11 …….. am-1,1
  按列序为主序存放 1 m-1 m*n-1 m a00 a10 ……. am-1,1 a01 a11 …….. am-1,1 ………. a0,n-1 a1,n-1 …….. am-1 ,n-1

10 5.2 数组的顺序表示和实现 按行序为主序存放 每个数据元素占L个存储单元;
  按行序为主序存放 am-1,n-1 …….. am-1,1 am-1,0 ……… a1,n-1 a11 a10 a0,n-1 ……. a01 a00 1 n-1 m*n-1 n 每个数据元素占L个存储单元; LOC(0,0)表示数据元素a00的存储地址 是数组的起始地址（基地址）; LOC(i,j)表示下标为(i,j)的数据元素 aij的存储地址 LOC(i,j)=LOC(0,0)+(i*n+j)*L 这个公式可以推广到n维数组。

11 5.2 数组的顺序表示和实现 按列序为主序存放 每个数据元素占L个存储单元;
  按列序为主序存放 am-1 ,n-1 …….. a1,n-1 a0,n-1 ………. am-1,1 a11 a01 ……. a10 a00 1 m-1 m*n-1 m 每个数据元素占L个存储单元; LOC(0,0)表示数据元素a00的存储地址， 是数组的起始地址（基地址） LOC(i,j)表示下标为(i,j)的数据元素 aij的存储地址 LOC(i,j)=LOC(0,0)+(j*m+i)*L 这个公式可以推广到n维数组。

12 为多个值相同的矩阵元只分配一个存储空间；对零元不分配空间。
5.3 矩阵的压缩存储 压缩存储 为多个值相同的矩阵元只分配一个存储空间；对零元不分配空间。 矩阵是很多科学与工程计算问题中研究的对象，在数值分析中，经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者零元素。 为了节省存储空间，可以对这类矩阵进行压缩存储。

13 值相同的元素或者零元素在矩阵中的分布有一定规律
5.3 矩阵的压缩存储 5.3.1 特殊矩阵 特殊矩阵 值相同的元素或者零元素在矩阵中的分布有一定规律 对称矩阵 n阶矩阵； aij=aji 1i,j n

14 特殊矩阵 5.3 矩阵的压缩存储 值相同的元素或者零元素在矩阵中的分布有一定规律 n阶矩阵；
三角矩阵 n阶矩阵； 下（上）三角矩阵：矩阵的上（下）三角（不包括对角线）中的元均为常数c或零。

15 特殊矩阵 5.3 矩阵的压缩存储 值相同的元素或者零元素在矩阵中的分布有一定规律 n阶矩阵 所有的非零元都集中在以主对角线为中心的带状区域中
对角矩阵 n阶矩阵 所有的非零元都集中在以主对角线为中心的带状区域中

16 5.3 矩阵的压缩存储 压缩存储——对称矩阵 a11 a12 …. … ….. a1n a21 a22 …….. ……. a2n
仅存储下三角 压缩存储——对称矩阵 a a12 …. … ….. a1n a a22 …….. ……. a2n an1 an2 …… ann …………………. 按行序为主序： 虽然可以压缩存储，但是不能改变随机存储的性质，即任意给定I,j，应能立即找到其值。 4 3 2 1 k=0 a11 a21 a22 a31 a32 … an1 … ann

17 5.3 矩阵的压缩存储 压缩存储——下三角矩阵 a11 1 1 …….. 1 a21 a22 1 …….. 1 …………………. 1
仅存储下三角 压缩存储——下三角矩阵 a …… a a …… an1 an2 an3…….. ann ………………… 按行序为主序： a11 4 3 2 1 k=0 a21 a22 a31 a32 … an1 … ann 1 虽然可以压缩存储，但是不能改变随机存储的性质，即任意给定I,j，应能立即找到其值。

18 5.3 矩阵的压缩存储 压缩存储——对角矩阵 a11 a12 0 …………… . 0 a21 a22 a23 0 …………… 0
仅存储主对角线非0元素 压缩存储——对角矩阵 a a …………… . 0 a a a …………… 0 … an-1,n-2 an-1,n-1 an-1,n … … … an,n-1 an,n a a a ……… 0 …………………………… 公式：请同学们自己写出来，可以到图书馆查找结果 按行序为主序： 4 3 2 1 k=0 a11 a12 a21 a22 a23 … an,n-1 an,n

19 5.3 矩阵的压缩存储 5.3.2 稀疏矩阵 稀疏矩阵 非零元较零元少，且分布没有一定规律的矩阵。
压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值。 矩阵维数 （6,7） 非零元 (1,2,12) (1,3,9) (3,1,-3) (3,6,14) (4,3,24) (5,2,18) (6,1,15) (6,4,-7) 请学生思考为什么要存储维数？

20 5.3 矩阵的压缩存储 1.压缩存储——稀疏矩阵(三元组顺序表) 以顺序存储结构来表示三元组。 稀疏矩阵的三元组顺序表存储表示
#define MAXSIZE //假设非零元个数的最大值为12500 typedef struct{ int i,j; //该非零元的行下标和列下标 ElemType e; }Triple; typedef struct{ Triple data[MAXSIZE+1]; //非零元三元组表，data[0]未用 int mu, nu, tu; //矩阵的行数、列数和非零元个数 }TSMatrix ; 行序 共有三种压缩存储的方法，本节介绍的是顺序存储

21 5.3 矩阵的压缩存储 行列下标 非零元值 data i j e data[0].i,data[0].j,data[0].e分别存放矩阵行列维数和非零元个数 三元组表所需存储单元个数为3(tu+1),其中tu为非零元个数

22 5.3 矩阵的压缩存储 求转置矩阵 问题描述 已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。 解决思路 将矩阵行、列维数互换； 将每个三元组中的i和j相互调换； 重排三元组次序。

23 5.3 矩阵的压缩存储 i j e M.data i j e T.data 两种转换方法：一、按data2中的顺序，在data1中找到合适的值进行转置；二、按data1的顺序，在data2中找到合适的位置进行转置。 ?

24 5.3 矩阵的压缩存储 方法一：按矩阵的列序转置 按T.data中三元组次序依次在M.data中找到相应的三元组进行转置
Col从1~n在M中找每1列 i j e M.data i j e T.data p p q p p q col=1 p p q p 为找到转置矩阵中每一列所有非零元素，需对其三元组表a.data从第一行起扫描一遍。由于a.data中以矩阵行序为主序,所以由此得到的恰是b.data中应有的顺序 p q col=2 p p q p p p p p p

25 5.3 矩阵的压缩存储 按矩阵的列序转置的算法思想 (1)令T.mu=M.nu, T.nu=M.mu, T.tu=M.tu, col=1，q=1(T的三元组下标初始化，指向转置后的第1个位置)，p=1 (指向M的第1个位置) (2)如p所指元素的列下标=col，则送q所指位置，q++ (3)p++,若p<=M.tu(1~最后1个非0元),则(2),否(4) (4)col++，如果col<=M.nu，转(2)，否(5) (5)结束 当tu和mu*nu同数量级时，算法的时间复杂度为O(mu*nu2)，例如在100*500的矩阵中有tu=10000个非零元素 虽然空间节省了，但时间复杂度提高了。因为不经压缩的矩阵在求转置矩阵的时间复杂度为O(mu*nu)， 算法实现： 算法5.1 适用于tu<<mu*nu 时间复杂度为O(nutu)

26 按M.data中三元组次序转置，转置结果放入T.data中恰当位置。
5.3 矩阵的压缩存储 方法二：按矩阵的行序转置 按M.data中三元组次序转置，转置结果放入T.data中恰当位置。 此法关键是要预先确定M.data中每一列第一个非零元在T.data中位置。(cpot[col]) 为确定这些位置，转置前应先求得M.data的每一列中非零元个数。(num[col]) 设num[col]记录M中第col列中非0元个数，cpot[col]记录M中第col列的第1个非0元在T中的恰当位置，有： cpot[1]=1; cpot[col]=cpot[col-1]+num[col-1] 2≤col≤M.mu

27 5.3 矩阵的压缩存储 p p p p p p p p M.data T.data col num[col] cpot[col] 1 2 3
4 7 8 6 9 2 4 6 8 9 3 5 7 i j e M.data i j e T.data p p p num[col]：表示矩阵M中第col列中非零元个数 cpot[col]：指示M中第col列第一个非零元在mb中位置 cpot[1]=1; cpot[col]=cpot[col-1]+num[col-1]; (2col ma[0].j) p p p p p

28 方法二:按矩阵的行序转置的实现 5.3 矩阵的压缩存储 时间复杂度为O(nu+tu) 算法5.2 用空间换取时间
在tu与mu*nu同数量级时，其时间复杂为O(nu*mu)，和经典算法的时间复杂度相同。 时间复杂度为O(nu+tu)

29 非零元在表中按行序有序存储，便于进行依行序处理的矩阵运算。
5.3 矩阵的压缩存储 三元组顺序表的特点 优点 非零元在表中按行序有序存储，便于进行依行序处理的矩阵运算。 缺点 若需按行号存取某一行的非零元，则需从头开始进行查找。

30 2.压缩存储——稀疏矩阵(行逻辑链接的的顺序表)
5.3 矩阵的压缩存储 2.压缩存储——稀疏矩阵(行逻辑链接的的顺序表) 为了便于随机存储任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置 解决方法：将cpot固定在稀疏矩阵的存储结构中。 #define MAXSIZE //假设非零元个数的最大值为12500 typedef struct{ int i,j; //该非零元的行下标和列下标 ElemType e; }Triple; typedef struct{ Triple data[MAXSIZE+1]; //非零元三元组表，data[0]未用 int rpos[MAXRC+1]; //各行第一个非零元的位置表 int mu,nu,tu; //矩阵的行数、列数和非零元个数 }RLSMatrix ; 矩阵压缩存储的第二种方法，

31 5.3 矩阵的压缩存储 矩阵乘法运算 如何求？ M.data N.data Q.data 3 4 4 1 1 3 1 4 5 2 2 -1
i j e M.data i j e N.data i j e Q.data

32 5.3 矩阵的压缩存储 (1)稀疏矩阵MxN,只需在M、N中找到相应的各对非0元素相乘,即M.data中的j值和N.data中的i值相等的各对非0元素相乘。例如M中的(1,1,3)p=1和N中的(1,1,0) 、(1,2,2)q=1相乘。为此,设两个:num[brow]表示N中第brow行的非0元个数,rpos[brow]表示N中第brow行的第1个非0元在N.data中的位置,N.rpos[1]=1, N.rpos[brow]=rpos[brow-1]上一行+num[brow-1]上一行,2≤brow≤n。N.rpos[brow]、M.rpos[arow]称为行逻辑链接的顺序表。(并在进入下面的算法前,预先求得一维数组rpos的值。 (2)乘积矩阵Q中每个元素的值是个累计和(也可能为和),对每个元素设一中间变量,temp[]列数,初值为0,将相应非0元素的乘积累加。例如,Ma中的(1,1,3)1与Nb中的(1,1,1)1的乘积,以及Ma中的(1,3,4)2与Nb中的(3,1,-2)3的乘积累加为Q中的(1,1,-5)1 (3)因(M)是“以行为主”排列,(Q)也应“以行为主”排列,故对Q逐行处理。中间变量ctemp[最大为Q的列数]存放Q的一行,检查这行中各元素是否零,然后,再将非0元素(结果)存到Q.data中。 累加器的时间复杂度为O(M.mu*N.nu),求Q所有非零元的时间复杂度为O(M.tu*N.tu/N.mu),进行压缩存储的时间复杂度为O(M.mu*N.nu),

33 5.3 矩阵的压缩存储 6 4 ctemp累加器 arow=2 arow=1 arow=3 rpos[row] M.data N.data
ctemp累加器 arow=2 arow=1 arow=3 4 3 1 rpos[row] 2 row 矩阵M的rpos 5 矩阵N的rpos i j e M.data N.data 6 p p -1 p p 4 p p p 矩阵Q的rpos row 1 2 3 rpos[row] 1 2 3 i j e Q.data

34 5.3 矩阵的压缩存储 算法思想 ①初始化(行数Q<=M,列数Q<=N赋值,Q的下标Q.tu=0,准备接收);
②for(arow=1;arow<=M.mu;++arow),处理M的每一行; ③中间变量一维数组ctemp(行)清0(例子中,Q一行只有2列,故ctemp[1],ctemp[2]即2)。顺便记下Q当前行非0元的起始位置Q.tu ④对M的当前行中的非0元,(逐个)做:(p<tp) ⑤取M中当前非0元的列号(j),即为N中的i(N中的行号brow); ⑥根据N的行号,对该行的非0元逐个做:(有几个就做几次)(q<t) ⑦取N中当前非0元的列号为Q的列号(Q的列号为ccol); ⑧M、N中相应的非0元相乘,并累加到ctemp[Q的列号]ccol中; ⑨逐个将当前Q的一行中的非0元素存入Q中。 累加器的时间复杂度为O(M.mu*N.nu),求Q所有非零元的时间复杂度为O(M.tu*N.tu/N.mu),进行压缩存储的时间复杂度为O(M.mu*N.nu),

35 矩阵相乘算法实现 5.3 矩阵的压缩存储 算法时间复杂度 累加器ctemp[]初始化的时间复杂度为： O(M.mu×N.nu)
算法5.3 算法时间复杂度 累加器ctemp[]初始化的时间复杂度为： O(M.mu×N.nu) 求Q的所有非0元的时间复杂度为： O(M.nu×N.tu/N.mu) 压缩存储的时间复杂度为： 所以，总的时间复杂度为： O(M.mu×N.nu+M.tu×N.tu/N.mu) 累加器的时间复杂度为O(M.mu*N.nu),求Q所有非零元的时间复杂度为O(M.tu*N.tu/N.mu),进行压缩存储的时间复杂度为O(M.mu*N.nu),

36 5.3 矩阵的压缩存储 3.压缩存储——稀疏矩阵(十字链表) 引入原因
当矩阵的非零元的个数发生变化时，不宜采用三元组表。如A=A+B，非零元的插入或删除将会引起A.data中的数据移动，这是顺序结构三元组的弱势。 十字链表结点形式 非零元的行、列、值 typedef struct OLNode{ int i,j; ElemType e; struct OLNode *right,*down; }OLNod; *OLink; typedef struct Olink *rhead,*chead; int mu, nu, tu; }CrossList; i j e down right 同一行下一个非零元 同一列下一个非零元

37 5.3 矩阵的压缩存储 列链表头指针 M.chead M.rhead 1 3 4 8 2 5 ^ 行链表头指针 ^ ^ ^ ^ ^ ^

38 5.3 矩阵的压缩存储 建立十字链表的思想 m=4,n=3,t=5 1,1,3 2,2,5 2,3,4 4,1,8 2,1,7 ^ 1 3
M. rhead M.cread 2,3,4 4,1,8 1 3 ^ 2,1,7 2 1 7 ^ 2 5 ^ 2 3 4 ^ 4 1 8 ^

39 5.3 矩阵的压缩存储 建立十字链表的算法思想 （1）初始化 （2）循环输入各非0元的(i,j,e)，直到最后一个，重复做： （3）申请结点，赋值 （4）寻找行i插入位置，插入 （5）寻找列j插入位置，插入 对于m行、n列有t个非零元的稀疏矩阵，算法的执行时间为O(t*s)，s=max(m.n)，因为每建立一个非零元的结点时都要寻查它在行表和列表中的插入位置。 建立十字链表的算法实现 算法5.4 时间复杂度为O( t*s) ，s=max(m.n)

40 广义表(列表) 5.4 广义表的定义 是线性表的推广，广泛地应用于人工智能等领域的表处理语言LISP语言。
一般记作LS=(a1,a2,…,an) (n0) 名称：LS； 长度：n； 原子：ai是单个元素，一般用小写字母表示； 子表：ai是广义表，一般用大写字母表示。 表头(Head)：非空广义表 LS的第一个数据元素a1； 表尾(Tail)：非空广义表 LS除第一个数据元素外的其余数据元素构成的广义表 (a2,…,an) 。 由于广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，因此在教材中和“数组”合为一章。但由于广义表比数组更为复杂，它兼有“多层次”的特点，特别是它的存储表示和操作的实现和树的操作极为类似。因此在本章的学习中应善于和第六章的内容相对照，反之通过本章的学习恰好是对实现树操作的递归算法的复习和巩固。希望你通过本章的学习能自己总结出如何利用“分治法”的算法思想设计递归定义的结构的递归算法的规律来 广义表是递归的概念，描述广义表时又用到了广义表的概念。 和数组不同，二维数组中的每个数据元素是结构相同的一维数组，而广义表中的每个数据元素，其结构不一定相同。

41 广义表的元素可以是子表，而子表的元素还可是子表 广义表可以为其它列表共享 广义表可以是一个递归的表
5.4 广义表的定义 广义表与数组的区别 广义表特性 A=() F=(b,(c,d,e)) E=(b,(c),(d,e)) D=(E,A,F) C=(A,D,F) B=(a,B)=(a,(a,(a,v...))) 广义表中的数据元素有固定的相对次序　　 广义表的元素可以是子表，而子表的元素还可是子表 广义表可以为其它列表共享 广义表可以是一个递归的表

42 广义表中元素的“长度"应由最外层括弧中的"逗号"来定。
5.4 广义表的定义 操作——长度 A=() F=(b,(c,d,e)) E=(b,(c),(d,e)) D=(E,A,F) C=(A,D,F) B=(a,B)=(a,(a,(a,v...))) A的长度为0 F的长度为2 E的长度为3 D的长度为3 C的长度为3 B的长度为2 （）和（（））是不同的，前者长度为0，后者长度为1 广义表中元素的“长度"应由最外层括弧中的"逗号"来定。

43 操作——取表头、取表尾 F=(b,(c,d,e))
5.4 广义表的定义 操作——取表头、取表尾 F=(b,(c,d,e)) GetHead(F)=b GetTail(F)=((c,d,e))=F1 GetHead(F1)=(c,d,e)=F2，GetTail(F1)=( ) GetHead(F2)=c，GetTail(F2)=(d,e)=F3 GetHead(F3)=d，GetTail(F3)=(e)=F4 GetHead(F4)=e，GetTail(F4)=( ) （）和（（））是不同的，前者不能进行这两个操作，后者可以进行这两个操作。 两个操作只对非空表有意义； 取表头的结果可能是原子，也可能是个广义表； 取表尾"必定"是个广义表，但可能是个空的广义表。

44 5.5 广义表的存储结构 采用链式存储结构。 两种结构的结点 表结点：用来表示列表； 原子结点：用来表示子表。 表尾指针 表结点 tag=1
hp tp 原子结点 tag=0 atom 因为，广义表的数据元素可以具有不同的结构，采用顺序存储结构表示将非常困难，通常采用链式结构。 标志域 值域 标志域 表头指针

45 5.5 广义表的存储结构 A=() B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E) A C B D E 1 
e a 1 1 1  结构复杂 D 1  b c d 1 1  E 1 1  a

46 5.5 广义表的存储结构 另一种结点结构 下一个元素指针 值域 表结点 tag=1 hp tp 原子结点 tag=0 atom tp 标志域
表头指针 下一个元素指针

47 5.5 广义表的存储结构 A=() B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E) A C B D E 1 
a 1  e  D 1  b c d  结构复杂 1  1 1  E 1  a 1 

48 本章小结 了解数组的类型定义及其在高级语言中实现的方法。 数组的特点是一种多维的线性结构，并只进行存取或修改某个元素的值，因此它只需要采用顺序存储结构。 介绍了稀疏矩阵的三种表示方法。至于在具体应用问题中采用哪一种表示法这取决于该矩阵主要进行什么样的运算。 广义表是一种递归定义的线性结构，因此它兼有线性结构和层次结构的特点。

49 基础知识题(数组部分) 假设有二维数组 A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置(基地址)为 1000，计算： 数组 A 的存储； 数组 A 的最后一个元素 a5,7 的第一个字节的地址; 按行存储时，元素 a1,4 的第一个字节的地址; 按列存储时，元素 a4,7 的第一个字节的地址。

50 基础知识题(广义表部分) 求下列广义表操作的结果： GetHead((p,h,w)); GetTail((b,k,p,h)); GetHead(((a,b),(c,d))); GetTail(((a,b),(c,d))); GetHead(GetTail(((a,b),(c,d)))); GetTail(GetHead(((a,b),(c,d)))); GetHead(GetTail(GetHead(((a,b),(c,d))))); GetTail(GetHead(GetTail(((a,b),(c,d)))))。

51 基础知识题(广义表部分) 利用广义表的 GetHead 和 GetTail 操作写出函数表达式，把原子 banana 分别从下列广义表中分离出来。 L1 = (apple,pear,banana,orange); L2 = ((apple,pear),(banana,orange)); L3 = (((apple),(pear),(banana),(orange))); L4 = (apple,(pear),((banana)),(((orange)))); L5 = ((((apple))),((pear)),(banana),orange); L6 = ((((apple),pear),banana),orange); L7 = (apple,(pear,(banana),orange));

52 基础知识题(广义表部分) 画出下列广义表的存储结构图。 ((( )), a, ((b, c), ( ), d), (((e))))
((((a), b)), ((( ), (d)), (e, f))) 已知右侧各图为广义表的存储结构图，写出各图表示的广义表。