《数据结构与算法设计PPT (13).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (13).pdf（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 字符串与数组3.3 数组的存储结构存储在一个连续的存储空间中的具有相同数据类型的数据元素的集合。数组的逻辑特征相同数据类型的n（n=0）个元素的有限序列 一维数组的示例int a10=35,27,49,18,60,54,77,83,41,2;一维数组的存储一维数组的特点 连续存储的线性聚集（别名 向量）除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。已知首地址和元素大小可以计算任意一个元素的位置数组的定义和初始化两种定义方法：创建静态数组创建动态数组#include class szclint e;public:szcl
2、()e=0;szcl(int value)e=value;int get_value()return e;main()szcl a13=3,5,7,*elem;for(int i=0;i 3;i+)cout a1i.get_value()“n”;/打印静态数组elem=a1;for(int i=0;i 3;i+)cout get_value()“n”;/打印动态数组elem+;return 0;静态数组动态指针动态数组szcl a1=new szcl4;作为抽象数据类型的数组一维数组(Array)类的定义#include#include template classArray Type*ele
3、ments;/数组存放空间int ArraySize;/当前长度void getArray();/建立数组空间public:Array(int Size=DefaultSize);Array(const Array&x);Array()delete elements;Array&operator=/数组复制(const Array&A);Type&operator (int i);/取元素值Type*operator()const /指针转换 returnelements;int Length()const /取数组长度 return ArraySize;void ReSize(int sz)
4、;/扩充数组数组的大小可以动态增长作为抽象数据类型的数组template void Array:getArray()/私有函数：创建数组存储空间elements=new TypeArraySize;if(elements=0)ArraySize=0;cerr Memory Allocation Error endl;return;一维数组公共操作的实现判断内存操作是否失败template Array:Array(int sz)/构造函数if(sz=0)ArraySize=0;cerr“非法数组大小”endl;return;ArraySize=sz;getArray();判断参数是否合法一维数组
5、构造方法template Array:Array(const Array&x)/复制构造函数intn=ArraySize=x.ArraySize;elements=new Typen;if(elements=0)ArraySize=0;cerr“存储分配错”endl;return;Type*srcptr=x.elements;Type*destptr=elements;while(n-)*destptr+=*srcptr+;深复制实现深复制的复制构造template Type&Array:operator (int i)/按数组名及下标i，取数组元素的值if(i ArraySize-1)cer
6、r“数组下标超界”endl;return NULL;return elementi;使用该函数于赋值语句Pos=Positioni-1+Numberi-1判断参数是否合法数组运算符重载template void Array:Resize(int sz)if(sz=0&sz!=ArraySize)Type*newarray=new Typesz;if(newarray=0)cerr“存储分配错”endl;return;int n=(sz=ArraySize)?sz:ArraySize;Type*srcptr=elements;Type*destptr=newarray;while(n-)*des
7、tptr+=*srcptr+;获取获取复制复制释放释放delete elements;elements=newarray;ArraySize=sz;二维数组三维数组行向量 下标 i页向量 下标 i列向量 下标j 行向量 下标j列向量 下标k二维数组的存储-=111101121202111101101000mnananamaaamaaamaaaa!#!行优先LOC(i,j)=a+(i*m+j)*la00a01a0m-1a10a11a1m-1a20a21二维数组的存储-=111101121202111101101000mnananamaaamaaamaaaa!#!列优先LOC(i,j)=a+(j*
8、n+i)*la00a10an-10a01a11an-11a02a12三维数组的存储 各维元素个数为m1,m2,m3 下标为i,j,k的数组元素的存储地址：LOC(i,j,k)=a+(i*m2*m3+j*m3+k)*l 三维数组的行主序的存放方式a000a001a002a010a011a012a020a021a022a100a101a102a110a111a112a120a121a122a000a001a002a010a011a012a020a021a022a100a101a102a110a111LOC(i,j,k)=a+(i*m2*m3+j*m3+k)*l 三维数组的行主序的存放方式a000a100a200a010a110a210a020a121a220a001a101a201A011a111A001a011a021a101a111a121a201a211a221a000a110a020a100a110a120a200a210a220LOC(i,j,k)=a+(k*m1*m2+j*m1+i)*l n维数组各维元素个数为m1,m2,m3,mn 下标为i1,i2,i3,in的数组元素的存储地址：limianjnjknkj*111+*+=-=+=LOC(i1,i2,in)=a+(i1*m2*m3*mn+i2*m3*m4*mn+in-1*mn+in)*l