6二维数组.ppt

数组、矩阵与集合 数组的相关概念 数组是n(n1)个具有相同数据类型的数据元素a0, a1, a2,…an-1构成的占用连续存储单元的有限序列。 操作:主要是存取数据元素。 特点：采用顺序的存储结构，且不进行插入、删除等操作。 地址计算： 假设数组A的首地址为l0 ，每个元素占k个存储单元，则数组第i个元素的存储位置pos(A[i])可由下式确定： pos(A[i])＝pos(A[0])＋i×k＝l0＋i×k (0=in) 特别地，当k = 1时，有：pos(A[i])＝l0＋i ; 数组抽象数据类型 数据元素： 数组的数据元素集合可表示为a0, a1, a2,…an-1，其中每个数据元素具有相同数据类型。 结构关系： 数组元素呈线性结构，且限定数组元素必须存储在地址连续的内存单元中。 基本操作： 对数组可执行以下的基本操作。 Initiate(A) 构造数组A。 Size(A) 求长度。函数值为给定数组A中数据元素的个数。 Set(A,i,x) 存数组元素。把数据x存入数组A的下标为i的数组元素中，其约束条件为0=i= length(A)-1。 Get(A,i ) 取数组元素。取出数组A中下标为i的数组元素，其约束条件为0=i= length(A)-1。 数组类定义及实现 template class T class Array { private: T *a; int size; public: Array(int sz=100) ; Array(const ArrayT arr) ; ~Array(){delete[] a;}; int getsize(){return size;}; T operator[](int i); ArrayT operator= (const ArrayT arr) ; void resize(int sz=100) ; void prnt() {for(int i=0;isize;i++)cout a[i] ; coutendl; } }; 数组类构造函数与赋值函数 Array(int sz=100) {if(sz=0){cout数组长度无效endl;exit(0);} size=sz; a=new T[size]; }; Array(const ArrayT arr) { size=arr.size; a=new T[size]; for(int i=0;isize;i++)a[i]=arr.a[i]; }; ArrayT operator= (const ArrayT arr) { delete[] a; size=arr.size; a=new T[size]; for(int i=0;isize;i++)a[i]=arr.a[i]; return *this; }; 数组类重置函数 //重新分配空间 void resize(int sz=100) {if(sz=0){cout数组长度无效endl;exit(0);} if(sz==size) return; T *newa=new T[sz]; int n=(sz=size)? sz:size; for(int i=0;in;i++)newa[i]=a[i]; delete []a; a=newa; size=sz; }; 二维数组的初步认识 二维数组可看作线性表的一种扩展,在逻辑上可看成由若干行、列组成的表格或矩阵，例如以下的m行n列的矩阵: a11 a12 a13 … a1n a21 a22 a23 … a2n …… am1 am2 am3 … amn 可表示成二维数组 int A[m][n]; 二维数组的初步认识 将二维数组看作是线性表的扩展, 例如，如果将每一列看作为一个元素，则以上m行n列矩阵所对应的二维数组a可看成如下线性表： a＝(α1,α2 ,…αn) 其中每一个数据元素αj是一个列向量 αj＝(a1j, a2j, a3j, …amj) 类似地，如果将每一行看作为一个元素，则a可看成如下线性表： a＝(β1, β2 ,…βm) 其中每一个数据元素βi是一个行向量 βi ＝(ai1, ai2, ai3,… …ain,) 二维数组的初步认识 一般地，二维数组的逻辑结构可表示为： Array_2 = (D, R) 其中， D={aij | i=c1, c1+1,…, d1; j= c2, c2+1,…, d2； aij∈Data