第5章数组与广义表

一、基本内容

数组的类型定义和表示方式;特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现;广
义表的逻辑结构和存储结构、
m 
元多项式的广义表表示以及广义表的操作的递归算法
举例。

二、学习要点

1. 了解数组的两种存储表示方法,并掌握数组在以行为主的存储结构中的地址计算
方法。
2. 掌握对特殊矩阵进行压缩存储时的下标变换公式。
3. 了解稀疏矩阵的两种压缩存储方法的特点和适用范围,领会以三元组表示稀疏矩
阵时进行矩阵运算采用的处理方法。
4. 掌握广义表的结构特点及其存储表示方法,读者可根据自己的习惯,熟练掌握任
意一种结构的链表,学会对非空广义表进行分解的两种分析方法:即可将一个非空广义表
分解为表头和表尾两部分或者分解为
n 
个子表。
**5. 学习利用分治法的算法设计思想编制递归算法的方法。
在下列这组习题中,第一类习题对应教科书5.2节C语言风格的数组存储分
1和5.
配和元素地址计算(各维下界为0); 第二类习题是推导特殊矩阵实现各种压缩存储时的
下标变换公式;第三类习题涉及稀疏矩阵的各种压缩存储方法;第四类习题帮助读者熟悉
广义表的存储结构和表头、表尾的分析方法;第五类习题则是为学习编写递归算法而安
排的。

三、算法演示内容

在DSDEMO 系统的选单“广义表”下,有以下算法演示: 

(1)求广义表的深度(Ls-Depth); 
(2)复制广义表(Ls-Copy); 
(3)遍历广义表(Ls-Mark); 
(4)建立广义表的存储结构(Crt-Lists)。
四、基础知识题

5.存储器按字节编
1① 假设有二维数组A6×8,每个元素用相邻的6个字节存储, 
址。
(
已知A的起始存储位置(基地址)为1000,计算: 

1)数组A的体积(即存储量); 
·31· 


(2)数组A 的最后一个元素a57的第一个字节的地址; 
(3)按行存储时,元素a14的第一个字节的地址; 
(4)按列存储时,元素a47的第一个字节的地址。
5.2① 假设按低下标优先存储整数数组A9×3×5×8时,第一个元素的字节地址是100, 
每个整数占四个字节。问下列元素的存储地址是什么? 
(1)a0000 (2)a1111 (3)a3125 (4)a8247 
5.3① 按高下标优先存储方式(以最右的下标为主序),顺序列出数组A2×2×3×3中所
有元素aijkl,为了简化表达,可以只列出(i,j,k,l)的序列。
5.4① 将教科书5.3.1节中的式(5-3)改写为一个等式的形式。
5.5③ 设有上三角矩阵(aij)n×n ,将其上三角元素逐行存于数组B[m]中(m 充分
大),使得B[k]=aij且k=f1(i)+f2(j)+c。试推导出函数f1,f2 和常数c (要求f1 
和f2 中不含常数项)。
5.6② 设有三对角矩阵(aij)n×n ,将其三条对角线上的元素存于数组B[3][n]中,使
得元素B[u][v]=aij,试推导出从(i,j)到(u,v)的下标变换公式。
5.7③ 设有三对角矩阵(aij)n×n ,将其三条对角线上的元素逐行地存于数组B[3n- 
2]中,使得B[k]=aij,求: 
(1)用i,j 表示k 的下标变换公式; 
(2)用k 表示i,j 的下标变换公式。
5.8③ 假设一个准对角矩阵
a11 a12 
a21 a22 
a33 a34 
a43 a44 
… 
ai,j 
… 
a2m-1,2m-1 a2m-1,2m 
a2m ,2m-1 a2m ,2m 
é
.
êêêêêêêêêêêêêê
ê 
ù
.
úúúúúúúúúúúúúú
ú 
按以下方式存于一维数组B[4m]中: 
0 1 2 3 4 5 6 k 4m-2 4m-1 
a11 a12 a21 a22 a33 a34 a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m 
写出由一对下标(i,j )求k 的转换公式。
5.9② 已知A 为稀疏矩阵,试从空间和时间角度比较采用两种不同的存储结构(二
·32·

n 

维数组和三元组表)完成求Σai 
运算的优缺点。

=

5的结果
:
(1)GetHea(h,】.10②求下列广义表操(i) 作(1) 
d【p,w)
;
(2)GtTi(k,h)】


eal【b,p,
3)GetHeaa,c,


(d【((b),(d)) 】; 

(4)GtTi((b),(d)) ;

eal【a,c,
】
(5)GtHed【eal【a,c,
】


eaGtTi((b),(d)) 】
;
(6)GetTail【GetHea((b),(d)) 】


d【a,c,
】
(7)GtHed【eal【ea((b),(d)) 】
;


eaGtTiGtHed【a,c,】
】
(l【d【l【((b),(d)) 】】】
。


8)GetTaiGetHeaGetTaia,c,

注意:【】是函数的符号。

5.11② 利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子
bana 
分别从下列广义表中分离出来。(1(n) (a) )L1=appe,pabnnoage);(ler,aaa,rn((e,r),(a,

(2)L2=pplpabange))
;
applpeabanana(o) orang


(3)L3=((((a) e),((e) r),((n) (a) ),((n) (a) (r) e)))
;
(4)L4=lpr),((a)),(((e))))
;


(ppe,(bng
5)L5=applpear(a) bananorang


((((((a) e))(e) ),(((a) )),((n) (a) (n) a),(a) (r) (o) e)
;
(6)L6=appe),pr),nonge)
;


((((laba)
,
(7)L7=appe,(abnnoage(r) 

(lper,((e) aaa),(a) (n) (a) rn));(a) 

5.5节中图5.画出下列广义表的存储结构图,
12② 按教科书5.8所示结点结构, 并

求它的深度。
a,((e))))(1)((()),b,c),(),d),(((
a),b)),(((),d),(

(2)((((e,f))) 
12题相同。写出各

5.13② 已知以下各图为广义表的存储结构图,其结点结构和5.
图表示的广义表
。
(1) 
·33· 


(2) 
5.已知等差数列的第一项为a1,公差为d,试写出该数列前
n 
项的和
14③
S(n≥0)的递归定义。n)(
15④ 写出求给定集合的幂集的递归定义。

5.
5.++” --
”
16③ 试利用C语言中的增量运算“ 和减量运算“ 写出两个非负整数
a 
和
b 
相加的递归定义。

5.试分别以函数形式写出下列运算的递归
17③ 已知顺序表
L 
含有
n 
个整数
,
算法
:


(1)求表中的最大整数;
(2)求表中的最小整数;
(3)求表中
n 
个整数之和;
(4)求表中
n 
个整数之积;
(5)求表中
n 
个整数的平均值。
五、算法设计题

5.18⑤ 试设计一个算法,将数组A0] n-1]循环右移
k 
位, 
要求只用一个元素大小的附加存储,元素移(n) 中的元素A[至An 
[并
动或交换次数为O()。

5.中的某个元素aij 
同时又是第
j 
列中的最
19④ 若矩阵Am×n 
是第
i 
行中的最小值, 
大值,则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Am×n 
,试编写求
出矩阵中所有马鞍点的算法,并分析你的算法在最坏情况下的时间复杂度。

20⑤ 类似于以一维数组表示一元多项式,以
m 
维数组:(),0≤ji= 
1,2,…,m,表示
m 
元多项式,数组元素a表示多项式中xe1e2em 
的系数。例

5.aj1j2…jm 
i≤n,

e1e2…em 
1x2…xm 

如,和二元多项式x2+3xy+4y2-x+2 相应的二维数组为

y 
0 1 2 
0 2 0 4 
1 -1 3 0 
2 1 0 0 

x

试编写一个算法将
m 
维数组表示的
m 
元多项式以常规表示的形式(按降幂顺序)输出。

11xe2em 
j=

可将其中一项ckxem 
印成ckm 
(其中m,
k 
和ej 
(2,…, 

2…xx1Ee1x2Ee2…xmEec1,

·34· 


m )印出它们具体的值),当ck 或ej(j=1,2,…,m )为1时,ck 的值或“E”和ej 的值可省
略不印。
5.21④ 假设稀疏矩阵A 和B 均以三元组顺序表作为存储结构。试写出矩阵相加
的算法,另设三元组表C 存放结果矩阵。
5.22④ 假设系数矩阵A 和B 均以三元组顺序表作为存储结构。试写出满足以下
条件的矩阵相加的算法:假设三元组顺序表A 的空间足够大,将矩阵B 加到矩阵A 上, 
不增加A ,B 之外的附加空间,你的算法能否达到O(m +n)的时间复杂度? 其中m 和n 
分别为A ,B 矩阵中非零元的数目。
5.23② 三元组顺序表的一种变型是,从三元组顺序表中去掉行下标域得到二元组
顺序表,另设一个行起始向量,其每个分量是二元组顺序表的一个下标值,指示该行中第
一个非零元素在二元组顺序表中的起始位置。试编写一个算法,由矩阵元素的下标值i, 
j 求矩阵元素。试讨论这种方法和三元组顺序表相比有什么优缺点。
5.24② 三元组顺序表的另一种变型是,不存矩阵元素的行、列下标,而存非零元在
矩阵中以行为主序时排列的顺序号,即在LOC(0,0)=1,l=1时按教科书5.2节中公式
(5-2)计算出的值。试写一算法,由矩阵元素的下标值i,j 求元素的值。
5.25③ 若将稀疏矩阵A 的非零元素以行序为主序的顺序存于一维数组V 中,并用
二维数组B 表示A 中的相应元素是否为零元素(以0和1分别表示零元素和非零元素)。
例如, 
A = 
15 0 0 22 
0 -6 0 0 
91 0 0 0 
é
.
êêêê 
ù
.
úúúú 可用V=(15,22,-6,9)和B= 
1 0 0 1 
0 1 0 0 
1 0 0 0 
é
.
êêêê 
ù
.
úúúú
表示。
试写一算法,实现在上述表示法中实现矩阵相加的运算。并分析你的算法的时间复
杂度。
5.26③ 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其
下标的算法。
5.27④ 试按教科书5.3.2节中定义的十字链表存储表示编写将稀疏矩阵B 加到稀
疏矩阵A 上的算法。
5.28④ 采用教科书5.6节中给出的m 元多项式的表示方法,写一个求m 元多项式
中第一变元的偏导数的算法。
5.29④ 采用教科书5.6节中给出的m 元多项式的表示方法,写一个m 元多项式相
加的算法。
5.30③ 试按表头、表尾的分析方法重写求广义表的深度的递归算法。
5.31③ 试按教科书5.5节图5.10所示结点结构编写复制广义表的递归算法。
5.32④ 试编写判别两个广义表是否相等的递归算法。
5.33④ 试编写递归算法,输出广义表中所有原子项及其所在层次。
·35·

5.逆转广义表中的数据元素。
34⑤ 试编写递归算法
,
例如:将广义
表
(b,d),f)
)


a,((c),()),(((e),
逆转为: 
((f,(d))),((),(b)),)。

e,(c,
a 

35⑤ 假设广义表按如下形式的字符串表示。
(α2,…,)
其中α或为单字母表示的原子, 
α1,αnn=
n≥0 

5.
或为广义表;0时为只含空格字符的空表()。试按(i) 教科书5.8所示链表结点结构编写,

5节图5.按照读入的一个广义表字符串建立
其存储结构的递归算法。

5.5节图5.编写按上题描述的格式输出广义表
36⑤ 试按教科书5.8所示存储结构, 
的递归算法。

37⑤ 试编写递归算法,删除广义表中所有值等于
x 
的原子项。

5.
38④ 试编写算法,依次从左至右输出广义表中第
l 
层的原子项。
项;
例如:广义表(b,(d)) 
b 
和
d 
为第二层的原子

5.
a,(c)),(中的
a 
为第一层的原子项
;
c 
为第三层的原子项
。


·36·