04 数组与矩阵.pdf

下载 下载 第4 章 数组和矩阵 在实际应用过程中，数据通常以表的形式出现。尽管用数组来描述表数据是最自然的方式， 但有时为了减少程序的时间和空间需求，通常会采用自定义的描述方式，比如，当表中大部分 数据全为0时。 本章首先检查了多维数组的行主描述形式和列主描述形式。通过行主描述和列主描述，可 以把多维数组映射成一维数组。 尽管C + +支持多维数组，但它无法保证数组下标的合法性。同时， C + +也未能提供数组的 输入、输出以及简单的算术运算（如数组赋值和数组相加）。为了克服这些不足，我们针对一 维数组和二维数组分别设计了类A r r a y 1 D和类A r r a y 2 D 。 矩阵通常被描述成一个二维数组。不过，矩阵的索引通常从 1开始，而不是像数组那样从0 开始，并且通常使用 A (i ,j )而不是A [i ] [j ]来引用矩阵中的元素 (i ,j ) 。为此，设计了另一个类 Matrix 以便更好地描述矩阵。 本章还考察了一些具有特殊结构的矩阵，如对角矩阵、三对角矩阵、三角矩阵和对称矩阵。 与采用二维数组描述矩阵相比，采用公式化的方法来描述这些特殊矩阵所需要的空间将大大减小， 同时，公式化的描述方法还可以显著地节省诸如矩阵加和矩阵减操作所需要的运行时间。 本章的最后一节给出了稀疏矩阵（即大部分元素为 0 的矩阵）的公式化描述和链表描述， 这两种描述方法对于0元素都做了特殊处理。 4.1 数组 4.1.1 抽象数据类型 数据对象a rr a y 的每个实例都是形如（i n d e x ，v a l u e ）的数据对集合，其中任意两对数据的 i n d e x值都各不相同。有关数组的操作如下： • C re a t e——创建一个初始为空的数组（即：不含任何数据） • S t o re——向数组中添加一对（ i n d e x ，v a l u e ）数据，如果数组中已经存在索引值与 i n d e x 相同的数据对，则删除该数据对。 • R e t r i e v e——返回具有给定i n d e x值的数据对的v a l u e值。 A D T 4 - 1给出了具有上述三种操作的抽象数据类型A r r a y 。 ADT 4-1 数组的抽象数据类型描述 抽象数据类型A rr a y { 实例 形如 ( i n d e x , v a l u e ) 的数据对集合，其中任意两对数据的 i n d e x值都各不相同 操作 C re a t e( ) ：创建一个空的数组 S t o re(index, value) ：添加数据(index, value) ，同时删除具有相同i n d e x值的数据对（如果存在） R e t r i e v e (i n d e x) ：返回索引值为i n d e x 的数据对 第 4章 数组和矩阵 1 2 9 下载 例4-1 上个星期每天的高温（华氏度数）可用如下的数组来表示： h i g h= { ( s u n d a y, 82), (monday, 79), (tuesday, 85), (wednesday, 92),(thursday, 88), (friday, 89), ( s a t u r d a y, 91)} 数组中的每对数据都包含一个索引（星期）和一个值（当天的温度），数组的名称为h i g h 。通 过执行如下操作，可以将m o n d a y 的温度改变为8 3。 S t o re( m o n d a y, 83) 通过执行如下操作，还可以确定f r i d a y 的温度： R e t r i e v e( f r i d a y ) 也可以采用如下的数组来描述每天的温度： h i g h={(0,82), (1,79), (2,85), (3,92)