第五章数组、字符串、集合类.ppt
《第五章数组、字符串、集合类.ppt》由会员分享,可在线阅读,更多相关《第五章数组、字符串、集合类.ppt(64页珍藏版)》请在三一文库上搜索。
1、第五章 数组、字符串、集合类,5.1 数组 5.1.1 顺序存储的数组 一维数组是若干个元素的一个有限序列。 一维数组的元素都必须具有相同的类型,即每个数组元素都占据相同大小的存储空间。 顺序方式存储,一维数组An ,每个数组元素占一个存储单元(不妨设为C个连续字节). 数组元素A0的首地址Loc(A0),则对于0i n-1,有: Loc(Ai)=Loc(A0)+i*C 对于高维数组,可以将其转化为一维数组,其存在两种存储方式:按行优先顺序和按列优先顺序。, 数组的存储 数组元素在内存中是顺序、连续存储的; 数组的存储分配按行(列)进行; 数组名字表示该数组的首元素地址,是常量。 1、一维数组
2、 对于一维数组而言,各元素按下标次序依次存放, 如a0,a1,a2,等等。且有: &a0: &a1: &a2:,数组中任一元素Ai的地址可表示为: Loc(ai) = Loc(a0) +i*C C为每个元素占用存储空间的字节数。 2、二维数组 按行存放 例 int x23/*它有23个数组元素*/ x00 x01 x02 x10 x11 x12,x00 x01 x02 x10 x11 x12 其存储分配顺序为: x00-x01-x02-x10-x11-x12 &x00 &x01 &x02 &x10 &x11 &x12,中的二维数组可以看作是一种特殊的一维数组。 例 float a34; b0
3、a00 a01 a02 a03 b- b1 a10 a11 a12 a13 b2 a20 a21 a22 a23 二维数组元素aij的地址可以这样得到: Loc(a ij) = Loc(bi) +j*C Loc(bi) = Loc(b0) + i*C / C=n*C Loc(aij) = Loc(a00) + i*n*C+j*C = Loc(a00) + (i*n+j)*C 例 Loc(a12) = a+(i*n+j)C =a+(1*4+2)*4 = a+24,3、三维数组 多维数组元素在内存中的排序顺序为:第一维的下标变化最慢,最右边的下标变化最快。 例float a234;,所谓按列优先顺
4、序,就是将数组元素按列向量的顺序存储,第i+1个列向量存储在第i个列向量之后。 Loc(aij) = Loc(a00) + j*m*C+i*C,A0:2,0:4,0:10,0:2 分别给出按行优先、列优先存储下的 AIJKL地址计算公式。 Loc(A)+165I+33J+3K+L Loc(A)+ 165L+15K+3J+I,5.1.2 静态数组和动态数组 静态数组的规模在编译时已经确定,无法在运行时根据 具体需要进行修改 1 动态数组类 Array 的定义 P73 声明: # include # include template class Array private: int FSize;/
5、数组的大小 T* alist;/指向数组的第一个元素的指针 void Allocate( );/为数组分配空间,public: Array( int sz=50 ); Array( const Array ,void Resize(int NewSize); ; Array类的实现: Template / 为数组分配空间 Void ArrayAllocate( ) alist = new TFsize; if( alist=0 ) cerr“Memory Allocation Fail.”endl; ,Template / 构造函数 ArrayArray(int sz=50) if(sz=0)
6、 cerr“Invalid Array Size.”endl; return; Fsize=sz; Allocate( ); ,template /复制构造函数 ArrayArray(const Array ,template / 的重载 T ,template / 修改数组的大小 void ArrayReSize(newSize) if (newSize = 0) cerr“invalid Array Size.”endl; return; if(newSize != Fsize) newArray = new TnewSize; if(newArray=0) cerr“Memory All
7、ocation Fail.” endl;return;,int n=(newSize = Fsize?newSize;Fsize); for(int i=0;in;i+) newArrayi=alisti; delete alist; alist=newArray; FSize=newSize; ,例 编写一个函数,要求输入一个整数N,用动态数组A来存放2 N之间所有5或7的倍数,输出该数组。 #include #include ”array.h” void multiple(void) Array A(10); int N,count = 0; coutN;,for(int i=5;i=N;
8、i+) if(count=A.ListSize( ) A.ReSize(count+10); if(i%5=0|i%7=0) Acount+=i; for(int j=0;jcount;j+) coutAj“ “; if(j+1) % 5=0) coutendl;,out : 5 7 10 14 15 20 21 25 28 30 35 40 42 45 49 50,out :N? in: 52,5.1.3 稀疏矩阵 定义:设矩阵 Amn中非零元素的个数远远小 于零元素的个数,则称 A 为稀疏矩阵。 特点:零元素的分布一般没有规律。 作用:解决空间浪费的问题。 1 三元组表 将表示稀疏矩阵的非
9、零元素的三元组结点按行优先的顺序排列,得到一个线性表,将此线性表用顺序存储结构存储起来,称之为三元组表。 三元组结点,i,j,aij,例 稀疏矩阵,三元组表,稀疏矩阵类的声明 template / 三元组的结点类 class Trituple firend class SparseMatrix; private: int row,col; / 非零元素的行号、列号 T value; / 非零元素的值 ;,template / 稀疏矩阵类的声明 class SparseMatrix private: / 稀疏矩阵的行数、列数及非零元素个数 int Rows,Cols,Count; / 存储三元组
10、表的数组 Trituple smArrayMaxTerm;,public: SparseMatrix( int Mrows,int Mcols); / 创建一个稀疏矩阵 SparseMatrix Transpose( ); / 求转置矩阵 SparseMatrix Add(SparseMatrix b); / 求矩阵的和 SparseMatrix Multiply(SparseMatrix b); / 求矩阵的乘积 ;,例 稀疏矩阵,转置矩阵,例 稀疏矩阵,b0 b1 b2 b3 b4 b5,稀疏矩阵类的实现 template / 求转置矩阵 SparseMatrix SparseMatrix
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 数组 字符串 集合
链接地址:https://www.31doc.com/p-3453639.html