数据结构与数据库精品课程第五章 数组

数据结构（c语言版）第五章答案第五章1、设二维数组A【8】【10】是一个按行优先顺序存储在内存中的数组，已知A【0】【0】的起始存储位置为1000，每个数组元素占用4个存储单元，求：（1）A【4】【5】的起始存储位置。

A【4】【5】的起始存储位置为1000+（10*4+5）*4=1180；（2）起始存储位置为1184的数组元素的下标。

起始存储位置为1184的数组元素的下标为4（行下标）、6（列下标）。

2、画出下列广义表D=（（c），(e)，(a，(b，c，d))）的图形表示和它们的存储表示。

略，参考第5·2节应用题第5题分析与解答。

3、已知A为稀疏矩阵，试从时间和空间角度比较采用两种不同的存储结构（二维数组和三元组表）实现求∑a(i，j)运算的优缺点。

稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，完成求∑ii a(1≤i≤n)时，由于a【i】【i】随机存取，速度快。

但采用三元组表时，若非零元素个数为t，需3t+3个存储单元（t个分量存各非零元素的行值、列值、元素值），同时还需要三个存储单元存储存稀疏矩阵A的行数、列数和非零元素个数，比二维数组节省存储单元；但在求∑ii a（1≤i≤n）时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。

4、利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间？当m行n列稀疏矩阵中非零元素个数为t，当满足关系3*t<m*n 时，利用三元组存储稀疏数组时，才能节省存储空间。

< bdsfid="74" p=""></m*n时，利用三元组存储稀疏数组时，才能节省存储空间。

<>5、求下列各广义表的操作结果。

（1）GetHead((a,(b,c),d))GetHead((a,(b,c),d))=a（2）GetTail((a,(b,c),d))GetTail((a,(b,c),d))=((b,c),d)（3）GetHead(GetTail((a,(b,c),d)))GetHead(GetTail((a,(b,c),d)))=(b,c)（4）GetTail(GetHead((a,(b,c),d)))GetTail(GetHead((a,(b,c),d)))=()第六章1、已知一棵树边的集合为{（i,m）,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶结点？（3）哪个是g的双亲？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？（11）树的度数是多少？略。

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中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：

Loc（A[i][j]）= Loc（A[0][0]）+ i *n*C + j*C = Loc（A[0][0]）+(i * n + j) *C
再例如三维数组 再例如三维数组D[3][3][4]，可以把它看作一维 ， 数组 B1[3] = { D[0][3][4]，D[1][3][4]，D[2][3][4] } ， ，
下面我们给出一个 下面我们给出一个Array类的应用例子 类的应用例子. 类的应用例子 例5.1 编写一个函数，要求输入一个整数 ， 编写一个函数，要求输入一个整数N， 用动态数组A来存放 来存放2～ 之间所有 之间所有5或 的倍数 的倍数， 用动态数组 来存放 ～N之间所有 或7的倍数， 输出该数组. 输出该数组 说明 ： 因为 由用户给出 ， 编写程序时无法知 说明：因为N由用户给出 由用户给出， 道需要多大的数组来存放数据， 道需要多大的数组来存放数据，因此采用动态 数组（初始时大小为10） 数组（初始时大小为 ），每当数组满时就调 整数组大小，给它增加10个元素 个元素. 整数组大小，给它增加 个元素
数组在内存中一般是以顺序方式存储的 数组在内存中一般是以顺序方式存储的. 设一维数组 设一维数组A[n]存放在 个连续的存储单元中 ， 存放在n个连续的存储单元中 存放在 个连续的存储单元中， 每个数组元素占一个存储单元（不妨设为C个 每个数组元素占一个存储单元 （ 不妨设为 个 连续字节） 如果数组元素A[0]的首地址是 ， 的首地址是L， 连续字节）. 如果数组元素 的首地址是 则 A[1] 的 首 地 址 是 L+C ， A[2] 的 首 地 址 是 L+2C，… …，依次类推，对于 0 ≤ i ≤ n 1 有： ， ，依次类推，
B[i]={ A[i][0]，A[i][1]，…，A[i][n-2]，A[i][n-1] } -

中的元素均为常数。下三角矩阵正好相反，它的主对
数据结构讲义
第5章 数组与广义表
—数组
数组和广义表
数组和广义表可看成是一种特殊的 线性表，其特殊在于，表中的数据 元素本身也是一种线性表。
几乎所有的程序设计语言都有数组 类型。本节重点讲解稀疏矩阵的实 现。
5.1 数组的定义
由于数组中各元素具有统一的类型，并且 数组元素的下标一般具有固定的上界和下 界，因此，数组的处理比其它复杂的结构 更为简单。
nm
aa1221
aa2222
…………....
aam2n2 ………………..
aamm11 aamm22 ………….... aammnn LLoocc(a( iaj)ij=)L=Loco(ca(a111)1+)[+([j(-i1-)1m)n++((i-j1-1)])*]*l l
aa1mn 1 aa2mn2 …………....
其存储形式如图所示：
15137 50800 18926 30251
a00 a10 a 11 a20 a21 a23 ………………..
70613
an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
图 5.1 对称矩阵
在这个下三角矩阵中，第i行恰有i+1个元素，元素总
数为：
n(n+1)/2
5.2 数组的顺序表示和实现
由于计算机的内存结构是一维的，因此用 一维内存来表示多维数组，就必须按某种 次序将数组元素排成一列序列，然后将这 个线性序列存放在存储器中。
又由于对数组一般不做插入和删除操作， 也就是说，数组一旦建立，结构中的元素 个数和元素间的关系就不再发生变化。因 此，一般都是采用顺序存储的方法来表示 数组。