内蒙古大学《算法与数据结构》讲义04数组和矩阵

下载第4章数组和矩阵在实际应用过程中，数据通常以表的形式出现。尽管用数组来描述表数据是最自然的方式，但有时为了减少程序的时间和空间需求，通常会采用自定义的描述方式，比如，当表中大部分数据全为0时。本章首先检查了多维数组的行主描述形式和列主描述形式。通过行主描述和列主描述，可以把多维数组映射成一维数组。尽管C + +支持多维数组，但它无法保证数组下标的合法性。同时， C + +也未能提供数组的输入、输出以及简单的算术运算（如数组赋值和数组相加） 。为了克服这些不足，我们针对一维数组和二维数组分别设计了类A r r a y 1 D和类A r r a y 2 D。矩阵通常被描述成一个二维数组。不过，矩阵的索引通常从 1开始，而不是像数组那样从0开始，并且通常使用 A(i,j)而不是Ai 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 上个星期每天的高温（华氏度数）可用如下的数组来表示：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), (4,88), (5,89), (6,91)在这个数组中，索引值是一个数值，而不是日期名，数值（ 0，1，2，. . .）代替了一周中每天的名称（s u n d a y，m o n d a y，t u e s d a y，. . .） 。4.1.2 C+数组尽管在C + +中数组是一个标准的数据结构，但 C + +数组的索引（也称为下标）必须采用如下形式：i1 i2 i3 . . . ikij为非负整数。如果k为1，则数组为一维数组，如果k 为2，则为二维数组。i1是索引的第一个坐标，i2是第二个，ik是第k个。在C + +中，值为整数类型的k 维数组s c o r e可用如下语句来创建：int scoreu1 u2 u3 . . . uk 其中ui是正的常量或由常量表示的正的表达式。对于这样一个数组描述，索引 ij的取值范围为：0ijuj, 1jk。因此，该数组最多可以容纳n=u1 u2 u3 . uk 个值。由于数组s c o r e中的每个值都是整数，所以需要占用 s i z e o f ( i n t )个字节，因而，整个数组所需要的内存空间为s i z e o f ( s c o r e ) = n * s i z e o f ( i n t )个字节。C + +编译器将为数组预留这么多空间。假如预留空间的始地址为s t a r t，则该空间将延伸至s t a r t + s i z e ( s c o r e ) - 1。4.1.3 行主映射和列主映射为了实现与数组相关的函数S t o r e和R e t r i e v e，必须确定索引值在s t a rt,s t a rt+n* s i z e o f ( s c o r e ) -1 中的相应位置。实际上就是把数组索引i1 i2 i3 . . . ik 映射到0, n- 1 中的某个数m a p(i1 , i2 , i3 ,., ik )，使得该索引所对应的元素值存储在以下位置：s t a rt + m ap(i1 , i2 , i3 , ., ik ) * s i z e of( i n t )当数组维数为1时（即k= 1） ，使用以下函数：m ap(i1 ) = i1 当数组维数为2时，各索引可按图4 - 1所示的表格形式进行排列，第一个坐标相同的索引位于同一行，第二个坐标相同的索引位于同一列。在图4 - 1中从第一行开始，依次对每一行中的每个索引从左至右进行连续编号，即可得到第4章数组和矩阵1 2 9下载图4-2a 所示的映射结果。这种把二维数组中的位置映射为0, n- 1 中某个数的方式被称为行主映射。C + +中即采用了这种行主映射模式。图4-2b 中给出了另一种模式，称之为列主映射。在列主映射模式中，对索引的编号从最左列开始，每一列按照从上到下的次序进行排列。 0 0 0 1 0 2 0 3 0 4 0 5 1 0 1 1 1 2 1 3 1 4 1 5 2 0 2 1 2 2 2 3 2 4 2 5 图4-1 int score36的索引排列表0 1 2 3 4 50 3 6 9 12 156 7 8 9 10 111 4 7 10 13 1612 13 14 15 16 172 5 8 11 14 17a) b) 图4-2 二维数组的映射a) 行主映射b) 列主映射行主次序所对应的映射函数为：map (i1, i2 ) = i1 u2 +i2其中u2是数组的列数。可以注意到，在行主映射模式中，在对索引i1 i2 进行编号时，第0，. . .，i1 -1 行中的i1 u2个元素以及第i1行中的前i2个元素都已经被编号。让我们用图4-2a 中的36数组来验证上述的行主映射函数。由于列数为 6，所以映射公式变成：map (i1 , i2 ) = 6i1 +i2因此有m a p( 1 , 3 ) = 6 + 3 = 9，m a p( 2 , 5 ) = 6 * 2 + 5 = 1 7。与图4-2a 中所给出的编号相同。可以扩充上述的行主映射模式来得到二维以上数组的映射函数。注意在行主次序中，首先列出所有第一个坐标为0的索引，然后是第一个坐标为1的索引，。第一个坐标相同的所有索引按其第二个坐标的递增次序排列，也即各个索引按照词典序进行排列。对于一个三维数组，首先列出所有第一个坐标为0的索引，然后是第一个坐标为1的索引，。第一个坐标相同的所有索引按其第二个坐标的递增次序排列，前两个坐标相同的所有索引按其第三个坐标的递增次序排列。例如数组s c o r e 3 2 4 中的索引按行主次序排列为：000, 001, 002, 003, 0l0, 0ll, 012, 013,100, l0l, 102, 103, 110, 111, 112, 113,200, 201, 202, 203, 210, 211, 2l2, 213三维数组的行主映射函数为：m a p(i1 , i2 , i3 ) = i1 u2u3 + i2 u3 +i3可以观察到，所有第一个坐标为i1的元素都位于第一个坐标小于i1的元素之前，第一个坐标都相同的元素数目为u2u3。因此第一个坐标小于i1的元素数目为i1u2u3，第一个坐标等于i1且第二个坐标小于i2的元素数目为i2u3，第一个坐标等于i1 且第二个坐标等于i2 且第三个坐标小于i3的元素数目为i3 。1 3 0第二部分数 据 结 构下载4.1.4 类A r r a y 1 D尽管C + +支持一维数组，但这种支持很不够。例如，可以使用超出正常范围之外的索引值来访问数组。考察如下的数组a：int a9可以访问数组元素a 3 ，a 9 和a 9 0 ，尽管3，9和9 0是非法的索引。允许使用非法的索引通常会使程序产生无法预料的行为并给调试带来困难。并且 C + +数组不能使用如下的语句来输出数组：cout a endl;也不能对一维数组进行诸如加法和减法等操作。为了克服这些不足，定义了类 A r r a y 1 D (见程序4 - 1 )，该类的每个实例X都是一个一维数组。X的元素存储在数组X . e l e m e n t之中，第i 个元素位于X.element i，0i s i z e。程序4-1 一维数组的类定义templateclass Array1D p u b l i c :Array1D(int size = 0);Array1D(const Array1D& v); / 复制构造函数Array1D() delete element;T& operator(int i) const;int Size() return size;Array1D& operator=(const Array1D& v);Array1D operator+() const; / 一元加法操作符Array1D operator+(const Array1D& v) const;Array1D operator-() const; / 一元减法操作符Array1D operator-(const Array1D& v) const;Array1D operator*(const Array1D& v) const;Array1D& operator+=(const T& x);p r i v a t e :int size;T *element; /一维数组; 这个类的共享成员包括：构造函数，复制构造函数，析构函数，下标操作符 ，返回数组大小的函数S i z e，算术操作符、*和。此外还可以添加其他的操作符。程序 4 - 2给出了构造函数和复制构造函数的代码。构造函数有点违背 ANSI C+的要求，它允许数组具有0个元素。如果我们不希望出现这种违规行为，可以对这段代码进行适当的修改。程序4-2 一维数组的构造函数templateArray1D:Array1D(int sz)/ 一维数组的构造函数if (sz 0) throw BadInitializers();size = sz;第4章数组和矩阵1 3 1下载element = new Tsz;templateArray1D:Array1D(const Array1D& v)/ 一维数组的复制构造函数size = v. s i z e ;element = new Tsize; / 申请空间for (int i = 0; i size; i+) / 复制元素ele