《chapter4数组和矩阵》由会员分享，可在线阅读，更多相关《chapter4数组和矩阵（50页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法,2009年秋季,授课教师：曾文 林伟华 授课班级：114081-3班,Chapter4 数组和矩阵,本章教学内容,数组 矩阵 特殊矩阵 稀疏矩阵,4.1 数组,从本质上讲，数组是 一个（）偶对的集合，其中每个数据元素都由一个值和一个下标组成。,一维数组是n（n0）个相同数据类型的数据元素a0，a1，an-1构成的有限线性序列，且该有限序列存储在一块地址连续的内存单元中。 其中，n叫做数组长度或数组大小； 如果n=0，则是空数组。,1、一维数组的定义,数组中的每一个元素在数组中的位置由下标唯一确定； 数组中的各数据元素处于一个线性结构中； 一维数组也叫做向量。,2、一维数组的特点
2、,3、 二维数组,当每一个数组元素ai（0in1）本身又是一个一维数组时，一维数组扩充为二维数组。 二维数组也叫做矩阵，如anm可以看作是由n个行向量和m个列向量所组成的向量。,例如：二维数组anm,总共有nm个数组元素； 每一个数组元素ajk同时处于两个向量之中； 数组元素ajk有两个直接前驱和两个直接后继； 数组元素在数组中的位置由下标的二元组jk唯一确定。,4、 在一个三维数组am1m2m3中： 总共有m1m2m3个数组元素； 每一个数组元素aijk同时处于三个向量之中； 数组元素aijk有三个直接前驱和三个直接后继； 数组元素在数组中的位置由下标的三元组ijk唯一确定。,5、在一个n维
3、数组am1m2mn中： 总共有m1m2mn个数组元素； 每一个数组元素ai1i2in同时处于n个向量之中； 数组元素ai1i2in有n个直接前驱和n个直接后继； 数组元素在数组中的位置由下标的n元组i1i2in唯一确定。,高维数组,1、数组ADT,抽象数据类型 Array 实例 形如(index , value)的数据对集合，其中任意两对数据的index值都各不相同 操作 Create( )：创建一个空的数组 Store(index, value)：添加数据(index, value)，同时删除具有相同index值的数据对（如果存在） Retrieve(index)：返回索引值为index的数
4、据对 ,设一维数组an的第一个数组元素的存储地址为a，每一个数组元素的存储大小为l，则任一数组元素的存储地址LOC(i)为：,a,l,LOC(i),il,LOC(i),a， i=0时,LOC(i-1)+l ，i0时,LOC(i) LOC(i-1)+l a+i*l,LOC(1) LOC(0)+l a+l,LOC(2) LOC(1)+l a+2*l,，,LOC(1),LOC(2),2、一维数组的顺序存储结构,用一组连续的存储单元存放二维数组将它的下标映射到其相应的一维数组的存储位置。,（1）行主映射：以行序为主的存储方式,如C、C+和PASCAL等语言采用这种存储方式。,（2）列主映射：以列序为主
5、的存储方式,如FORTRAN语言采用这种存储方式。,3、二维数组的顺序存储结构 如何用一维的存储地址来表示多维的关系,以行（列）序为主的存储方式：先存储第0行（列），再存储第1行（列），继续下去，最后存储第n-1行（m-1列） ； 第i+1行（j+1列）的第一个元素ai+10（a0j+1）是紧接在第i行（第j列）的最后一个元素之后存放的。,第0行,第1行,第n-1行,第0列,第1列,第m-1列,（a）以行序为主,（b）以列序为主,假设有二维数组anm，且下标均从0开始，每个数据元素的存储大小为l，那么，任一数组元素ajk在相应的一维数组中存放地址为：,LOC(j,k) = LOC(0,0)+(
6、j*m+k)*l,以行优先的顺序讨论地址的映射方法,LOC(i,j,k)=LOC(i,0,0)+(j*m3+k)*l,=LOC(i-1,0,0)+(m2*m3+j*m3+k)*l,=,= LOC(0,0,0)+(i*m2*m3+j*m3+k)*l,假设有三维数组am1m2m3，且下标均从0开始，每个数据元素的存储大小为l，那么，任一数组元素aijk在相应的一维数组中存放地址为：,三维数组的地址映射函数,推广到n维数组的映射函数,行主次序 列主次序,设W为一个二维数组，其中每个数据元素Wij占用6个字节，行下标i从0到8，列下标j从2到5，则二维数组W的数据元素共占用 A 个字节；W中第6行的元
7、素和第4列的元素共占用 B 个字节；若按行顺序存放二维数组W，其起始地址的字节号为100，则二维数组W的最后一个数据元素的起始地址的字节号为 C ，数据元素W34的起始地址号为 D ，而数据元素W22的起始地址号与当按列优先顺序存放时数据元素 E 的起始地址相同。 A （1）480 （2）192 （3）216 （4）144 B （1）78 （2）72 （3）66 （4）84 C （1）310 （2）311 （3）184 （4）185 D （1）179 （2）178 （3）184 （4）185 E （1）W05 （2）W28 （3）W52 （4）W82,【课堂练习】（软考真题）,W=,解：行下标
8、从0-8，共9行； 列下标从2-5，共4列。,总存储空间需946=216个字节,4、数组类的扩展,C+中的数组 不能控制越界访问 不能直接输出 不直接支持加、减、乘等运算。,int a3=1,4,2; couta;,int a3=1,4,2; a-1、a4,（1）一维数组类,定义一系列运算符,一维数组的构造,template Array1D:Array1D(int sz) if(sz0) cerr“Bad Initializers！”endl; size=sz; element=new Tsz; ,template Array1D:Array1D(Array1D ,构造函数,复制构造函数,下标
9、操作符重载： ,template T ,下标操作符必须能够出现在一个赋值操作符的左右两边，为了能在左边出现它的返回值必须是一个左值，可以通过把返回类型指定为一个引用来实现。,赋值操作符重载：=,template Array1D ,赋值操作符必须重载为成员函数； 赋值运算符必须传回一个指向其左操作数的引用，即*this。,二元减法操作符重载：-,template Array1D Array1D:operator-(Array1D ,一元负号操作符重载：-,template Array1D Array1D:operator-( ) const /返回w=-(*this) Array1D w(siz
10、e); for(int i=0;isize;i+) w.elementi=-elementi; return w; ,操作符重载：+=,template Array1D ,补充总结：操作符重载的规则,操作符重载的规则,（1） C+不允许用户自己定义新的操作符，只能对已有的C+操作符进行重载。,（2）C+中绝大部分的操作符允许重载，不能重载的操作符只有5个： . （成员访问操作符） * （成员指针访问操作符） （域操作符） sizeof （长度操作符） ?: （条件操作符）,（3）重载不能改变操作符操作对象（即操作数）的个数。,（4）重载不能改变操作符的优先级别。,（5）重载不能改变操作符的结合
11、性。,（6）除了对operator( )外对其他重载操作符提供缺省实参都是非法的。,（7）重载的操作符必须和用户定义的自定义类型的对象一起使用，其参数至少应有一个是类对象（或类对象的引用）。 参数不能全部是C+的标准类型，以防止用户修改用于标准类型数据的操作符的性质。,操作符重载的规则（续）,（8） 用于类对象的操作符一般必须重载，但有两个例外，操作符“=“和“&“不必用户重载。 赋值操作符（=）可以用于每一个类对象，可以利用它在同类对象之间相互赋值。 地址操作符&也不必重载，它能返回类对象在内存中的起始地址。,（9） 应当使重载操作符的功能类似于该操作符作用于标准类型数据时所实现的功能。,（
12、10） 操作符重载函数可以是类的成员函数，也可以是类的友元函数，还可以是既非类的成员也不是友元函数的普通函数。,操作符重载的规则（续）,重载为友元函数时，参数个数=原操作数个数，且至少应该有一个自定义类型的形参。 重载为类成员函数时，参数个数=原操作数个数-1（后置+、-除外），调用对象作为第一个参数使用。,Money Money:operator+(const Money ,total=cost + tax;,操作符重载的使用,重载和,输出操作符是一个双目操作符，它返回一个ostream 引用。 重载定义的通用框架如下 / 重载 output 操作符的通用框架 ostream ,它的第一个实
13、参是一个ostream 对象的引用，第二个一般是一个特定类类型的const引用； 返同类型是一个ostream引用，且它的值总是该输出操作符所应用的ostream 对象； 因为第一个实参是一个ostream 引用所以输出操作符必须定义为非成员函数，当输出操作符要求访问非公有成员时必须将它声明为该类的友元。,（插入操作符）：二元操作符,cout“Hello!n“;,操作数1：输出流,操作数2：字符串,Money amount(100); amount.output(cout);,int amount(100); coutamount;,coutamount;,重载操作符,重载和,课后练习（课下自
14、行完成）,Page136：练习1,（2）2维数组类,二维数组的构造,template Array2D:Array2D(int r，int c) if(rr; for(int i=0;ir; i+) rowi.Resize(c); /调整每个元素的大小 ,template void Array1D:ReSize(int sz) delete element; size=sz; element=new Tsize; ,二维数组的复制构造,template Array2D:Array2D(const Array2D /逐行复制 ,下标操作符重载： ,template Array1D ,Array2D
15、 X; Xij分解为：(X.operatori).operatorj 先调用Array2D:operator，返回指向X.rowi的引用，再调用Array1D:operator。,二元减法操作符重载：-,template Array2D Array2D:operator-(Array2D ,二元乘法操作符重载：*,template Array2D Array2D:operator*(Array2D ,课后练习（课下自行完成）,Page137：练习5,4.2 矩阵,矩阵是一个数值构成的表，具有行、列二维结构； 矩阵的行、列编号从1开始，而不是从0开始； 矩阵元素表达法是x(i, j) , 而非xij； 可以用2维数组来描述矩阵。,矩阵示例,54矩阵,矩阵运算,转置 加法 乘法,使用二维数组表示矩阵的缺陷,矩阵下标从1开始 C+数组不支持常规矩阵运算 需要为矩阵开发一个封装类！,矩阵类Matrix（自学）,类Matrix的构造函数,template Matrix:Matrix(int r，int
