南邮《数据结构A》第04章

《南邮《数据结构A》第04章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章数组和字符串南京邮电大学计算机学院2006年9月4.1数组4.2特殊矩阵4.3稀疏矩阵4.4字符串南京邮电大学计算机学院2006年9月4.1数组南京邮电大学计算机学院2006年9月数组是非常有用的数据结构，几乎所有的高级程序设计语言中都提供了数组类型。本章从数据结构的角度介绍数组的概念、它的抽象数据类型和类的定义。在自然科学中，矩阵常被用于解决许多实际问题。由于稀疏矩阵在存储表示上的特点，本章也对它进行专门的讨论。南京邮电大学计算机学院2006年9月数组的定义数组是下标index和值value组成的序对的集合。(index,value)一维数组：A={(0,15),(1,24),(2,

2、33),(3,21)}4.1.1数组ADT南京邮电大学计算机学院2006年9月数组抽象数据类型ADTArray{Data:下标index和元素值value组成的数据对集合,其中任意两个数据对的下标index各不相同。Operations:Create():建立一个数组。Retrieve(i):返回下标为i的元素值。Store(i,x):将下标为i的数据对的值置为x。};南京邮电大学计算机学院2006年9月一维数组的顺序表示二维数组的顺序表示多维数组的顺序表示4.1.2数组的顺序表示南京邮电大学计算机学院2006年9月一维数组的顺序表示地址计算:设第一个数组元素a[0]的存储地址是loc(a[

3、0])，若已知每个数组元素占k个存储单元，则下标为i的数组元素a[i]的存储地址loc(a[i])为loc(a[i])=loc(a[0])+i*ki=0,1,2,…,n-1。南京邮电大学计算机学院2006年9月二维数组的顺序表示二维数组a[m][n]映射到一维的存储空间时有两种顺序：行优先和列优先。大多数语言如PASCAL、BASIC、C、C++等都是按行优先顺序存储的，FORTRAN是按列优先顺序存储的。南京邮电大学计算机学院2006年9月地址计算loc(a[i][j])=loc(a[0][0])+(i*n+j)*k(0i

4、i][j])=loc(a[0][0])+(j*m+i)*k南京邮电大学计算机学院2006年9月多维数组的顺序表示推广到多维数组a[m1][m2]…[mn]，数组元素a[i1][i2]…[in]的存储地址为：loc(a[i1][i2]…[in])=loc(a[0]…[0])+(i1*m2*m3*…*mn+i2*m3*m4*…*mn+…+in-1*mn+in)*k=南京邮电大学计算机学院2006年9月用C++的模板类定义的一维数组抽象数据类型。公有成员函数包括：构造函数析构函数重载下标操作符：[]重载下标操作符用来返回指向第i个元素的引用重载数组赋值：＝赋值操作符实现数组的整体赋值。4.1.3一

5、维数组的C++类南京邮电大学计算机学院2006年9月#includetemplateclassArray1D{public:Array1D(intsz=0);~Array1D(){delete[]elements;}T&operator[](inti)const;Array1D&operator=(constArray1D&r);friendistream&operator>>(istream&in,Array1D&r);friendostream&operator<<(ostream&out,constArray1D&r);pri

6、vate:intsize;T*elements;};南京邮电大学计算机学院2006年9月templateArray1D::Array1D(intsz){assert(sz>=0);//越界检查size=sz;elements=newT[sz];}南京邮电大学计算机学院2006年9月templateT&Array1D::operator[](inti)const{//越界检查assert(i>=0&&iArray1D&Arra

7、y1D::operator=(constArray1D&r)//数组r整体赋值给this{if(this!=&r){//防止自我赋值size=r.size;delete[]elements;//释放原空间elements=newT[size];//重新分配空间for(inti=0;i