当前位置：文档之家 › 数据结构 第五章数组和广义表

数据结构 第五章数组和广义表

  • 格式：doc
  • 大小：63.00 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

数据结构第五章 数组与广义表

数据结构第五章 数组与广义表
an-1,n-1
压缩存储方法：只需要存储下三角 （含对角线）上的元素。可节省一 半空间。
可以使用一维数组Sa[n(n+1)/2]作为n阶对称矩阵A的存 储结构，且约定以行序为主序存储各个元素，则在Sa[k]和矩
阵元素aij之间存在一一对应关系： （下标变换公式）
i(i+1)/2 + j 当i≥j k = j(j+1)/2 + i 当i<j
q = cpot[col];
T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; ++cpot[col]; }
分析算法FastTransposeSMatrix的时间 复杂度：
for (col=1; col<=M.nu; ++col) … … for (t=1; t<=M.tu; ++t) … … for (col=2; col<=M.nu; ++col) … … for (p=1; p<=M.tu; ++p) … …
//对当前行中每一个非零元
处
brow=M.data[p].j;
理
if (brow < N.nu ) t = N.rpos[brow+1];
M
else { t = N.tu+1 }
的
for (q=N.rpos[brow]; q< t; ++q) { ccol = N.data[q].j; // 乘积元素在Q中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：

数据结构(C语言版 李素若)第五章 数组和广义表PPT资料优秀版

数据结构(C语言版 李素若)第五章 数组和广义表PPT资料优秀版
if(StrE按mpty行(S))*优ls = N先UL的L; 顺序存放元素，因此，数组元素地址的计算公式为
OLink *hl; Head（B）＝e Tail（B）＝（） 4．求广义表的深度
h广p义), s表ub的); 定q=义p;并没有限制元L素O的递C归(，)=即广L义O表也C可(以a是11其1自)+身d的2子d表3。(i1-1)+d3(i2-1)+(i3-1)
5.3 矩阵压缩存储 18
5.3.1 对称矩阵
对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中 1≤i,j≤n。对称矩阵关于主对角线对称，比如，我们只存储下三 角中的元素aij，其特点是中j≤i且1≤i≤n，对于上三角中的元素 aij，它和对应的aji相等，因此当访问的元素在上三角时，直接 去访问和它对应的下三角元素即可，这样，原来需要n*n个存 储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个 存储单元，当n较大时，这是可观的一部分存储资源。
第5章 数组和广义表
1
5.1 数组类型定义 5.2 数组顺序存储和实现 5.3 矩阵压缩存储 5.4 稀疏矩阵 5.5 广义表
5.1 数组类型的定义 2
1．一维数组 一维数组可以看成是一个线性表或一个向量（第2章已经介 绍），它在计算机内是存放在一块连续的存储单元中，适合于 随机查找。这在第2章的线性表的顺序存储结构中已经介绍。 2．二维数组 二维数组中的每一个元素最多可有两个直接前驱和两个直接 后继（边界除外），故是一种典型的非线性结构。例如，设A 是一个有m行n列的二维数组，则A可以表示为：
LOC(bij)=LOC(b11)+(d2-c2+1)(i-1)+(j-1) 公式中第2项是i-1个整行元素，每行d2-c2+1个元素。也可以解 释为第1维下标减1乘上后面第2维下标区间。

数据结构-第五章 数组与广义表-文档资料

数据结构-第五章 数组与广义表-文档资料

上 三 角 矩 阵 下 三 角 矩 阵
a00 a10 a 20 an10
0 1 2
a01 a11 a21 an11
3 4
a02 a12 a22 an12
5

6 7
a0 n1 a1n1 a2 n1 an1n1
行 列 值 (row) (col) (value) 0 4 91 1 1 11 2 5 28 3 0 22 3 2 -6 5 1 17 5 3 39 6 0 16
用三元组表表示的稀疏矩阵及其转置
行 列 值 (row) (col) (value) 0 3 22 0 6 15 1 1 11 1 5 17 2 3 -6 3 5 39 4 0 91 5 2 28 行 列 值 (row) (col) (value) 0 4 91 1 1 11 2 5 28 3 0 22 3 2 -6 5 1 17 5 3 39 6 0 16
4 5 6 7 8 9 10
B a00 a01 a10 a11 a12 a21 a22 a23 … an-1n-2 an-1n-1
三对角矩阵中除主对角线及在主对角线上 下最临 近的两条对角线上的元素外，所有其它元素均为 0。总共有3n-2个非零元素。 将三对角矩阵A中三条对角线上的元素按行存放在 一维数组 B 中，且a00存放于B[0]。 在三条对角线上的元素aij 满足 0 i n-1, i-1 j i+1 在一维数组 B 中 A[i][j] 在第 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所 以元素 A[i][j] 在 B 中位置为 k = 2*i + j。
三对角矩阵的压缩存储

数据结构第五章数组和广义表

数据结构第五章数组和广义表
typedef elemtype Array2[m][n]; 等价于
typedef elemtype Array1[n]; typedef Array1 Array2[m]; 同理，可以用 n-1 维数组的数据类型来定义 n 维数组。
8
第8页
5．2 数组的顺序存贮结构
一、数组的顺序表示和实现
(1) 类型特点 ① 只有引用型操作，一般不作插入或删除操作； ② 数组是多维的结构，而存储空间是一个一维的结构。
第 17 页
(2) 压缩存储的有关概念 ① 压缩存储：为多个值相同的元素分配一个存储空间，对零 元不分配空间。 ② 特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定 规律。 ③ 稀疏矩阵：值相同的元素或者零元素在矩阵中的分布无规 律。
第 18 页
(3) 特殊矩阵
① 概念：若n阶矩阵 A 中的元满足：aij=aji 1≤i,j≤n，则 称为n 阶对称矩阵。
第1页
第五章 数组和广义表
5. 1 数组的定义 5.2 数组的顺序存储结构 5. 3 矩阵的压缩存储 5. 4 广义表的定义 5.5 广义表的存储结构
第2页
第五章 数组和广义表
前4章介绍的数据结构共同特点： ▲ 都属于线性数据结构； ▲ 每种数据结构中的数据元素，都作为原子数据， 不再进行分解； 本章讨论的两种数据结构：数组和广义表，其共 同特点是： ▲ 从逻辑结构上看它们，可看成是线性结构的一 种扩展； ▲ 数据元素本身也是一个数据结构；
4
第4页
(2) 二维数组的解释
二维数组中的每个元素都受两个 线性关系的约束，即行关系和列关系， 在每个关系中，每个元素aij都有且仅 有一个直接前趋，都有且仅有一个直 接后继。
aa … 00 01

《数据结构——用C语言描述(第二版)》第5章 数组和广义表

《数据结构——用C语言描述(第二版)》第5章 数组和广义表
是指矩阵的下三角（不含对角线）中的元素均为常数C或零的n阶矩阵，下 三角矩阵则与之相反，如图5.3所示。
第五章 数组和广义表
在压缩存储时，矩阵中值相同的元素C可共享一个存储空间，元素 为零则可不必分配空间，而其余的元素有 n(n+1)/2个，因此三角矩阵 可用一维数组M[n×(n+1)/2+1]来存储，其中常数C放在数组的最后一 个下标变量中。
假设A和B矩阵分别用matrix型指针变量a和b表示，矩阵的转置可以 按以下进行：由于Ｂ的行是Ａ的列，所以可按照b->data三元组表的次序在 a->data中找到相应的三元组进行转置，即可按a->data的列序转置，所得 到的转置矩阵Ｂ的三元组表b->data必定是按行优先存放的。因此，可以对 三元组表a->data从第一行起扫描，找到Ａ的每一列中所有的非零元素，就 可以实现转置。
LOC ( aij ) =LOC ( a00) +(i×n+j) × c 同理可推导出以列为主序优先存储时数据元素a i j 的存储地址，其计算公式 为：
LOC( a i j ) =LOC( a00 ) +( j × n +i ) × c 对于三维数组Am×n×p而言，若以行为主序优先存储时，则其数据元 素aijk的存储地址可为： LOC ( a i j k) =LOC ( a000) +[ i × m×p +j ×p +k] × c 对于一般的二维数组A[c1…d1，c2…d2]而言，此处c1，c2的值不一定是 0，a i j 的地址为： LOC ( a i j ) =LOC ( a c 1 c 2 ) +[ ( i – c 1 )* ( d 2 – c 2 +1) +j – c 2 ] * c

数据结构第五章

数据结构第五章

5.3.1 特殊矩阵
是指非零元素或零元素的分布有一定规律的矩阵。
1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij = aji 0≦i,j≦n-1 则称A为对称矩阵。
对称矩阵中的元素关于主对角线对称，故只 要存储矩阵中上三角或下三角中的元素，这样， 能节约近一半的存储空间。

2013-7-25 第4章 18
5.3 矩阵的压缩存储

在科学与工程计算问题中，矩阵是一种常用 的数学对象，在高级语言编制程序时，常将 一个矩阵描述为一个二维数组。 当矩阵中的非零元素呈某种规律分布或者矩 阵中出现大量的零元素的情况下，会占用许 多单元去存储重复的非零元素或零元素，这 对高阶矩阵会造成极大的浪费。 为了节省存储空间，我们可以对这类矩阵进 行压缩存储：
5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的， 因此用一维内存来表示多维数组，就必 须按某种次序将数组元素排成一列序列 ，然后将这个线性序列存放在存储器中 。 又由于对数组一般不做插入和删除 操作，也就是说，数组一旦建立，结构 中的元素个数和元素间的关系就不再发 生变化。因此，一般都是采用顺序存储 的方法来表示数组。
即为多个相同的非零元素只分配一个存储空间； 对零元素不分配空间。


课堂讨论： 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的 存储空间，且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？ 未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵， 稀疏矩阵等。 4. 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5%）
通常有两种顺序存储方式：
⑴行优先顺序——将数组元素按行排列，第i+1个行 向量紧接在第i个行向量后面。以二维数组为例，按 行优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存 储的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1 个列向量紧接在第j个列向量之后，A的m*n个元素按 列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。

数据结构之数组与广义表课件PPT课件


对称矩阵有n*n个元素，但只存储n*(n+1)/2 个元素即可. 若以行序为主序，把下三角中的 元素，存储在一个一维数组SA[n*(n+1)/2] 中， 则 A[i,j] 和SA[k] 的对应关系如下：
若 i>=j , 则A[i, j]在下三角中，A[i, j]之前共有 1+2+……+i+j = i*(i+1)/2+j 个元素，因此有
2
3 -1
3
1
-1

6
4
5
2
8
6
1
5
7
6
9
7 7 7
t: 1 3 -1
165 212 258 3 1 -1 634 679
➢ 基本思想：
把S转置成T，就是把S中的每一个三元组的 行号和列号（row 和col）交换，并存储在T 中。但是，这样的结果是按列优先存储的稀 疏矩阵T，所以，还必须重新排列三元组的 顺序。
3.稀疏矩阵的压缩存储
➢ 若一个m*n矩阵，有s个非0元素， 记 e=s/(m*n) e 称为稀疏因子。 当 e0.05时，则称为稀疏矩阵。
例: M=
0 2 -1 0 0 0 0 0000000 -1 0 0 0 0 4 0 0000000 0800000 5000000 0000090
➢ 在稀疏矩阵中，非0元素的排列无规律，所以不 能采用以前的压缩方法。
1. 一维数组的寻址公式
对于一维数组，若其第一个元素的首地
址为Loc(a0)，下标为 i 的数组元素A[i]的地
址为Loc(ai)，
a a 则 Loc( i) = Loc( 0) + k * i
( 0≤i≤n-1)

数组和广义表 数据结构


3.建立广义表的存储结构 假定广义表中的元素类型ElemType为chai类型，每个原子的值被限 定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一 个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号 内不包含任何字符。例如“(a，(b, c, d))”就是一个符合上述规定的广 义表格式。 建立广义表存储结构的算法同样是一个递归算法。该算法使用一个 具有广义表格式的字符串参数s,返回由它生成的广义表存储结构的头结 点指针h。在算法的执行过程中，需要从头到尾扫描s的每一个字符。当 碰到左括号时，表明它是一个表元素的开始，则应建立一个由h指向的表 结点，并用它的sublist域作为子表的表头指针进行递归调用，来建立子 表的存储结构；当碰到一个英文字母时，表明它是一个原子，则应建立 一个由h指向的原子结点；当碰到一个“）”字符时，表明它是一个空表， 则应置h为空。当建立了一个由h指向的结点后，接着碰到逗号字符时， 表明存在后继结点，需要建立当前结点(即由h指向的结点）的后继表； 当碰到右括号或分号字符时，表明当前所处理的表已结束，应该置当前 结点的link域为空。 4.输出广义表 5.广义表的复制
广义表的转换过程
为了使子表和原子两类结点既能在形式上保持一致，又能进
行区别，可采用如下结构形式：
其中，tag域为标志字段，用于区分两类结点。sublist或data
域由tag决定。若tag=0，表示该结点为原子结点，则第二个 域为data，存放相应原子元素的信息；若tag=l，表示该结点 为表结点，则第二个域为sublist，存放相应子表第一个元素 对应结点的地址。link域存放与本元素同一层的下一个元素所 在结点的地址，当本元素是所在层的最后一个元素时，link域 为NULL。 例：前面的广义表C的存储结构如下图所示(很多《数据结构 公教科书上称之为带表头结点的广义表的链表存储结构

第5章 数组和广义表

第五章数组和广义表讲课提要【主要内容】1．多维数组的顺序存储结构2．特殊矩阵的压缩存储3．广义表的定义及其与线性表的关系4．广义表的存储结构5．广义表运算实现中递归的应用【教学目标】1．掌握多维数组的顺序存储结构2．掌握特殊矩阵的压缩存储方法3．掌握广义表的定义及其与线性表的关系4．掌握广义表的存储结构5．了解广义表运算实现中递归的应用学习指导1．多维数组的顺序存储结构对于多维数组，有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。

设有m×n二维数组A mn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。

设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算a ij 的物理地址的函数为：LOC(a ij) = LOC(a11) + ( (i-1)*n + j-1 ) * L同理，对于三维数组A mnp，即m×n×p数组，对于数组元素a ijk其物理地址为：LOC(a ijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L注意：在C语言中，数组中每一维的下界定义为0，则：LOC(a ij) = LOC(a00) + ( i*n + j ) * L【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。

大学数据结构课件--第5章 数组和广义表


a 32 a 33 a 34 0 0
a 43 a 44 a 45 0
a 54 a 55 a 56 a 65 a 66
5.3.2 稀疏矩阵
稀疏矩阵的存储：如何表示非零元素的位置信息 1. 三元组表：每个元素用一个三元组（i，j，v）来表示。 i j v
0 1 6 1 1 6 2 3 8 12 9
2
3 4 5 6 7 8
2
5.2 数组的顺序表示和实现
a00 a00 a10 a01 存储单元是一维结构，而数组是个多维结构 , …… …… 则用一组连续存储单元存放数组的数据元素就有 am-1,0 a0,n-1 个次序约定问题。 a01 a10
a11
……
a11
……
二维数组可有两种存储方式： am-1,1 a1,n-1
……
K=
i*n-i(i-1)/2+j-i n(n+1)/2
当 i≤j 当i>j
0 a11 ... a1n-1 ... ... ... ... 0 0 0 an-1n-1
当i ≤ j时,a[i][j]是非零元素, a[i][j]前面有i行,共有n+(n-1)+(n-2)+…(n-(i-1))
=i(n+[n-(i-1)])/2=i*n-i(i-1)/2个元素，a[i][j]前面有j列，共j-i个非零元素，
A m× n
( a10 a11 … a1,n-1 )
=
注：
( … … …… ) ( am-1,0 am-1,2 … am-1,n-1 ) ( ( ( (
① 数组中的元素都具有统一的类型; ② 数组元素的下标一般都具有固定的上界和下界，即数组一旦 被定义，它的维数和维界就不再发生改变； ③ 数组的基本操作简单：初始化、销毁、存取元素和修改元素值
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第五章数组和广义表：习题习题一、选择题1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。

A. 808B. 818C. 1010D. 10202．同一数组中的元素( )。

A. 长度可以不同B．不限C．类型相同 D. 长度不限3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节。

(2)A的第8列和第5行共占( )个字节。

(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址一致。

供选择的答案：(1)A. 90 B. 180 C. 240 D. 270(2) A. 108 B. 114 C. 54 D. 60(3)[8][5] B. A[3][10] [5][8] [O][9]4.数组与一般线性表的区别主要是( )。

A.存储方面B.元素类型方面C.逻辑结构方面D.不能进行插入和删除运算5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A. (i-l)×n+jB. (i-l)×n+j-lC．i×(j-l) D. j×m+i-l6．所谓稀疏矩阵指的是( )。

A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7．对稀疏矩阵进行压缩存储的目的是( )。

A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D. 降低运算的时间复杂度8．稀疏矩阵一般的压缩存储方法有两种，即( )。

A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。

A. 60B. 66 C．18000 D．3310. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+I)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是( )。

A. i(i-l)/2+jB. j(j-l)/2+iC. i(j-i)/2+1D. j(i-l)/2+111．已知广义表L=((x，y,z)，a，(u，t，w))，从L表中取出原子项t的运算是( )A. head(tail(tail(L)))B. tail(head(head(taiI(L))))C. head(tail(head(taiI(L))))D. head(tail(head(tail(tail(L)))))12.广义表A=(a，b，(c，d)，(e，(f,g)))，则下面式子的值为( )。

Head(TaiI(Head(TaiI(Tail(A)))))A．(g) B．(d)13．广义表((a，b，c，d))的表头是( )，表尾是( )。

B.( )C.(a,b,c,d)D.(b,c,d)14．设广义表L=((a，b，c))，则L的长度和深度分别为( )。

和1 和3 和2 和315.下面说法不正确的是( )。

A. 广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构二、填空题1.数组的存储结构采用____存储方式。

2.二维数组A[10][20]每个元素占一个存储单元，并且A[0][O]的存储地址是200，若采用行序为主方式存储，则A[6][12]的地址是____ ，若采用列序为主方式存储，则A[6][12]的地址是____。

3.三维数组a[4][5][6]（下标从0开始计，a有4×5×6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。

（设a[0][0][0]的地址是1000，数据以行为主方式存储）4. n阶对称矩阵a满足a[i][j]=a[j][i]，i,j=1．．n，，用一维数组t存储时，t的长度为____，glist p；{ glist q，h，t，s；if (p==NULL) q=NULL;else{ if____{q= (glist)malloc( sizeof (gnode));q->tag=0;q->=p->; }elsef____；if______{ t=reverse (p->val. ptr. tp);s=t;while( s->val. ! =NULL)s=s->val .;s->val .ptr. tp=( glist) malloc( sizeof (gnode));s=s->val .; s->tag=l;s->val．=NULL;s-> }else{ q=( glist) malloc( sizeof( gnode));q->tag=l;q-> }}}return (q)；}三、判断题1.数组不适合作为任何二叉树的存储结构。

( )2.稀疏矩阵压缩存储后，必会失去随机存取功能。

( )3.数组是同类型值的集合。

( )4.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。

( )5.一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。

( )6.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。

( )7.若一个广义表的表头为空表，则此广义表亦为空表。

( )8.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。

( )9.所谓取广义表的表尾就是返回广义表中最后一个元素。

( )10.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。

( )11. 一个广义表可以为其他广义表所共享。

( )四、简答题1.在以行序为主序的存储结构中，给出三维数组A2*3*4的地址计算公式（下标从0开始计数）。

2.数组A中，每个元素A嘶]的长度均为32个二进位，行下标从-1到9，列下标从1到11，从首地址s开始连续存放主存储器中，主存储器字长为16位。

求：(1)存放该数组所需多少单元(2)存放数组第4列所有元素至少需多少单元(3)数组按行存放时，元素A[7，4]的起始地址是多少(4)数组按列存放时，元素A[4，7]的起始地址是多少3．将数列1，2，3，…，n*n，依次按下列方式存放在二维数组A[1．．n，1一n]中。

例如：n=5时，二维数组为4．画出下列广义表的链接存储结构，并求其深度。

((((),a,((b,c),(),d),(((e))))5．已知题图5-1为广义表的链接存储结构，写出该图表示的广义表。

题图5-16．设有广义表K1(K2(K5(a，K3(c，d，e))，K6(b，k))，K3，K4(K3，f))，要求：(1)指出K1的各个元素及元素的构成。

(2)计算表K1，K2，K3，K4，Ks，K6的长度和深度。

(3)画出K1的链表存储结构。

五、算法设计题1．对于二维整型数组A[m,n]，分别编写相应函数实现如下功能：(1)求数组A4边元素之和。

(2)当m=n时分别求两条对角线上的元素之和，否则显示m≠n的信息。

2．编写子程序，将一维数组A[n*n](n<=10)中的元素按蛇形方阵存放在二维数组B[n] [n]中，即：B[0][0]=A[0]；B[0][1]=A[1];B[1][0]= A[2]；B[2][0]=A[3];B[1][1]=A[4];B[0][3]=A[6]；依此类推，如图题5-2所示：3．编写一个函数将两个广义表合并成一个广义表。

合并是指元素的合并，如两个广义表((a，b)，(c))与(a，(e，f))合并后的结果是((a，b)，(c)，a，(e，f第五章数组与广义表第5章数组与广义表一、选择题, A,B,B二、填空题1．顺序存储方式。

2. 313, 327。

3. 1166。

*(n+1)/2,i*(i+l)/2。

5．线性表。

6．由其余元素构成的子表。

7．深度。

8．()，(())，2，2。

9. head (head (tail(L))). 10. (i= =k) break, i+l, i-l, i!=k。

11. p->tag==0, h=p-> p->next!=NULL, q=t, reverse(h)。

三、判断题1．×2．×3．√ 4．× 5．×6．×7．×8．×9．× 10. √11. √四、简答题1. LOC(A[i][j][k]=LOC(A[0][0][0]+i*12+j*4+k.2．(1) 12l*32/16=242。

(2) 11*32/16=22(3) LOC(A[0][0])+(8*11+3)*32/16=LOC(A[0][0])+182.(4) LOC(A[0][0])+182。

3．程序如下所示：#define NMAX 10#include <stdio．h>main(){int i,j，n，k，m;int a [NMAX] [NMAX];scanf( "%d", &n);m=l;for (i=O; i<n; i++){ for (j=i*n,k=O; j<(i+1)*n; j++,k++)a[i][k]=m++;}for(i=O; i<n; i++){for(j=O;j<n;j++)printf ("%4d",a [i][j]);printf(¨\n");}}4．深度为4广义表的链接存储结构为：5.((x,(y)),((()),(),(z)))6．ki由k2, k3, k4构成k1k2 k3k4 k5 k6长度： 3 2 3 2 2 2深度： 4 3 1 2 2 l五、算法设计题1．(1)#define M 5#define N 7long sum side (int a[M] [N]) int equal(GListNode *ha, GListNode *hb);sublist;while(p!=NULL) data= =hb->val. data)return l;elsereturn O;else sublist;q=hb->val．sublist; sublist;r=h; //r指向前驱while (p!=NULL){r-p;p=p->link;}r->link=s;s->link=NULL; }。