《数据结构A》第05章(黄刚)

The same general method is then used for these subproblems, and so recursion continues until the size of the subproblems is reduced to some smallest, base case, where the solution is given directly without using further recursion.
5.1.3
(1) Solving problems using recursion
5.1.3
(1) Solving problems using recursion
(1) Solving problems using recursion

Recursion Versus Iteration


5.1.4
(1) Solving problems using recursion

The idea that gives a solution is to concentrate on the hardest step: moving the bottom disk.
1 2 3
We have to get to this state and then move the bottom disk

分解模式在每一层递归上都有三个步骤：
分解(Divide): 将原问题分解成一系列子问题； 解决(Conquer): 递归地解决各子问题。若子问题足够小， 则直接求解。 合并(Combine): 将子问题的结果合并成原问题的解。

5.1.4

基本操作：
InitArray(&A, n, bound1, ..., boundn) DestroyArray(&A) Value(A, &e, index1, ..., indexn) Assign(&A, e, index1, ..., indexn)
InitArray(&A, n, bound1, ..., boundn)
①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120
G. 156 H. 234 I. 276 J. 282 K. 283 L. 288
⑤： A．行与列的上界相同
B. 行与列的下界相同
C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个 数相同
LJCIC
练习
一n×n的三角矩阵A=[aij]如下：
R＝{R1, R2, ..., Rn} Ri＝{<a , a > | j1,... ji,... jn j1, ...ji +1, ...jn 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,...,n } 基本操作:
} ADT Array
1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算，
遇除法，还需判别除数是否为零。
解决问题的原则:
1) 尽可能少存或不存零值元素；
2) 尽可能减少没有实际意义的运算；
3) 操作方便。 即： 能尽可能快地找到与
下标值(i，j)对应的元素， 能尽可能快地找到同
一行或同一列的非零值元。
有两类稀疏矩阵：
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 数组的顺序表示和实现
由于计算机的内存结构是一维的，因此用 一维内存来表示多维数组，就必须按某种 次序将数组元素排成一列序列，然后将这 个线性序列存放在存储器中。
又由于对数组一般不做插入和删除操作， 也就是说，数组一旦建立，结构中的元素 个数和元素间的关系就不再发生变化。因 此，一般都是采用顺序存储的方法来表示 数组。

对一个m行n列的二维数组， 由于计算机的存储单元 都是一维的， 就有一个二维向一维的映射问题， 用计算机 的术语称作行主序存放还是列主序存放的问题。 C语言中 数组元素采用行主序的存放方法， 即一行存完后再存放下
一行。 有些高级语言也采用列主序的存放方法。 对于行主 序的存放方法来说， 设a00是行下标和列下标均为0的数组 元素， Loc(a00)是a00的存储地址， k是每个数据元素所需的 字节个数， 则数组中任一数据元素aij的存储地址Loc(aij)可 由以下公式求出：
printf("内存空间不够！")； exit(0)； }
for(i ＝ 0； i < n； i＋＋) a［i］ ＝ i ＋ 1；
for(i ＝ 0； i < n； i＋＋)
printf("%d ", a［i］)； free(a)； /*动态释放指针a所指的n个内存空 间*/ }从例5 - 1可以看出， 使用动态数组时， 除了申请和 释放内存空间的方法和静态数组的方法不同外， 其他使用 方数组的设计方法
和静态数组不同的是， 动态数组的数组元素个数不需 在编译时就确定， 而是在使用时根据需要确定。 高级语言 一般都提供支持用户定义动态数组的函数或运算符。
C语言为用户提供了定义动态数组的函数。 C语言提供 的支持动态数组的函数主要是malloc( )函数和free( )函数。 malloc( )函数的功能是动态申请所需的连续地址的内存空 间， 并返回所分配内存空间的首地址。 free( )函数的功能 是动态释放内存空间。
}
for (i ＝ 0； i < row； i＋＋) if((a［i］ ＝ (int *)malloc(col * sizeof(int))) ＝