南京邮电大学数据结构A第4章

数据结构A·第4章数组与字符串第4章数组和字符串内容提要1、介绍数组的概念2、讨论数组抽象数据类型3、讨论特殊矩阵的存储方法4、讨论稀疏矩阵的顺序存储方法5、讨论稀疏矩阵转置算法6、讨论字符串抽象数据类型7、讨论字符串的存储方法8、讨论字符串的模式匹配算法4.1数组4.1.1数组抽象数据类型1.数组的定义课堂提要第4章数组和字符串4.1数组4.1.1数组抽象数据类型4.1.2数组的顺序表示4.1.3一维数组的C++类4.2特殊矩阵4.3稀疏矩阵4.4字符串数组是下标index和值value组成的偶对的集合。每个偶对形如：(index,value)在数组中，每个有定义的下标都与一个值对应，这个值称做数组元素。一维数组：A={(0,15),(1,24),(2,33),(3,21)}4.1数组4.1.1数组抽象数据类型2.数组的抽象数据类型ADT4.1数组抽象数据类型ADTArray{数据:下标index和元素值value组成的数据对集合，其中任意两个数据对的下标index各不相同。运算:Create():建立一个数组。Retrieve(i):返回下标为i的元素值。Store(i,x):将下标为i的数据元素的值置为x。};4.1数组4.1.2数组的顺序表示课堂提要第4章数组和字符串4.1数组4.1.1数组抽象数据类型4.1.2数组的顺序表示4.1.3一维数组的C++类4.2特殊矩阵4.3稀疏矩阵4.4字符串数组通常采用顺序表示：1.一维数组的顺序表示2.二维数组的顺序表示3.多维数组的顺序表示4.1数组4.1.2数组的顺序表示设第一个数组元素a[0]的地址是loc(a[0])，若已知每个元素占k个存储单元，则a[i]的地址loc(a[i])为loc(a[i])=loc(a[0])+i*k(i=0,1,2,…,n-1)。1.一维数组的顺序表示二维数组a[m][n]映射到一维的存储空间时有两种顺序：行优先和列优先。多数语言如PASCAL、BASIC、C、C++等都是按行优先顺序存储的，FORTRAN是按列优先顺序存储的。2.二维数组的顺序表示4.1数组4.1.2数组的顺序表示行优先顺序的地址计算：若已知每个元素占k个存储单元，第一个数组元素a[0][0]的地址是loc(a[0][0]),则数组元素a[i][j]的地址loc(a[i][j])为loc(a[i][j])=loc(a[0][0])+(i*n+j)*k(0im;0jn)a[0][0]a[0][1]…a[0][n-1]a[1][0]a[1][1]…a[1][n-1]…a[m-1][0]a[m-1][1]…a[m-1][n-1]下标为0的行下标为1的行…下标为m-1的行(a)行优先的顺序表示[0][0][0][1][0][1][1][0][1][1][1][1][][][1][0][1][1][1][1]aaanaaanaijamamamn4.1数组4.1.2数组的顺序表示a[0][0]a[1][0]…a[m-1][0]a[0][1]a[1][1]…a[m-1][1]…a[0][n-1]a[1][n-1]…a[m-1][n-1]下标为0的列下标为1的列…下标为n-1的列(a)列优先的顺序表示列优先顺序存储：loc(a[i][j])=loc(a[0][0])+(j*m+i)*k(0im;0jn)[0][0][0][1][0][1][1][0][1][1][1][1][][][1][0][1][1][1][1]aaanaaanaijamamamn4.1数组4.1.2数组的顺序表示[0][0][1][0][2][0]...[i][0]...[m-1][0][0][1][0][2][0][3]......[0][j][1][j][2][j][m-1][j]...[0][n-2][0][n-1][1][n-1][2][n-1]...[i][n-1]...[m-1][n-1][i][j]行优先：loc(a[i][j])=loc(a[0][0])+(i×n+j)×k列优先：loc(a[i][j])=loc(a[0][0])+(j×m+i)×k4.1数组4.1.2数组的顺序表示3.多维数组的顺序表示课堂提要第4章数组和字符串4.1数组4.1.1数组抽象数据类型4.1.2数组的顺序表示4.1.3一维数组的C++类4.2特殊矩阵4.3稀疏矩阵4.4字符串推广到多维数组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=(0ijmj,1jn)111([0][0][0])((*))*nnjknjkjLocaaimik4.1数组4.1.2数组的顺序表示3.多维数组的顺序表示10×10的整型数组A，其每个数组元素占2个字节，已知A[0][0]在内存中的地址是100，按列主序，A[4][6]的地址是。A．228B．192C．124D．138[0][0][1][0][2][0][3][0][4][0][5][0][6][0][7][0][8][0][9][0][0][1][0][2][0][3][0][4][0][5][0][6][1][6][2][6][3][0][4][6][5][0][6][0][7][0][8][0][9][0][0][7][0][8][0][9]如果列优先228，如果行优先是1924.1数组4.1.3一维数组的C++类程序4.1一维数组的C++类#includeassert.htemplateclassTclassArray1D{public:Array1D(intsz=0);//缺省时长度为0~Array1D(){delete[]elements;}T&operator[](inti)const;//取元素值Array1DT&operator=(constArray1DT&r);//整体赋值friendistream&operator(istream&in,Array1DT&r);friendostream&operator(ostream&out,constArray1DT&r);private:intsize;T*elements;};4.1数组4.1.3一维数组的C++类1.构造函数templateclassTArray1DT::Array1D(intsz){//创建动态一维数组assert(sz=0);//越界检查size=sz;elements=newT[sz];}在函数的实现中使用了一种断言函数assert，若断言语句的条件满足，则继续执行后面的语句；否则出错处理，程序终止。4.1数组4.1.3一维数组的C++类1.构造函数size=3elements=0x0012FF7C012112333ArrayintA(3);A的结构如图所示。4.1数组4.1.3一维数组的C++类2.重载下标操作符templateclassTT&Array1DT::operator[](inti)const{assert(i=0&&isize);//越界检查returnelements[i];}（1）函数返回引用的作用：A[i]可以作为赋值运算的任一边（2）[]，＝只能作为类的成员函数重载。4.1数组4.1.3一维数组的C++类3.重载赋值操作符templateclassTArray1DT&Array1DT::operator=(constArray1DT&r){if(this!=&r)//防止自我赋值{size=r.size;delete[]elements;//释放原空间elements=newT[size];//重新分配空间for(inti=0;isize;i++)elements[i]=r.elements[i];//复制元素}return*this;}4.1数组4.1.3一维数组的C++类4.重载输入操作符templateclassTistream&operator(istream&in,Array1DT&r){coutIntputarray\n;for(inti=0;ir.size;i++)inr.elements[i];returnin;}5.重载输出操作符templateclassTostream&operator(ostream&out,constArray1DT&r){coutArray=;for(inti=0;ir.size;i++)outr.elements[i]'';outendl;returnout;}4.1数组4.1.3一维数组的C++类程序4.2应用一维数组类的主程序#includearray1d.hvoidmain(){Array1Dinta(5),b(8);Array1Dintc;//采用缺省长度0cina;coutaa;cinb;coutbb;coutcc;couta[0]=a[0];b[5]=b[5]endl;c=b;coutc=b,cc;b=a;coutb=a,bb;}4.2特殊矩阵4.2.1对称矩阵1.对称矩阵在n×n的矩阵A中，若aij=aji(1≤i,j≤n)，则为n阶对称矩阵。课堂提要第4章数组和字符串4.1数组4.1.1数组抽象数据类型4.1.2数组的顺序表示4.1.3一维数组的C++类4.2特殊矩阵4.3稀疏矩阵4.4字符串对于对称矩阵，可以只存储上三角(或下三角)中的元素(包括对角线上的元素)：n2个元素的对称矩阵，只需要n(n+1)/2个元素的存储空间4.2特殊矩阵4.2.1对称矩阵1.对称矩阵若用一维数组b[num]以行优先顺序存储下三角(包括对角线)元素，则矩阵元素aij的下标（i,j）和该元素在数组b中的存储位置k之间有如下关系：a00a10a11a20…aij…an-1n-10123...k...num-1对称矩阵的存储表示(1)2(1)2iijijkjjiji0010111,01,11,1nnnnaaaaaa4.2特殊矩阵4.2.1对称矩阵2.上（下）三角矩阵主对角以下元素全为0的方阵称为上三角矩阵。主对角以上元素全为0的方阵称为下三角矩阵。上、下三角矩阵也可以采用对称矩阵的存储方式:只存储非0的上（或以下）三角中的元素。课堂提要第4章数组和字符串4.1数组4.2特殊矩阵4.2.1对称矩阵4.3稀疏矩阵4.4字符串4.3稀疏矩阵定义：大多数元素为零的矩阵称为稀疏矩阵。为了节省空间，对于稀疏矩阵可只存非零元素。课堂提要第4章数组和字符串4.1数组4.2特殊矩阵4.3稀疏矩阵4.3.1抽象数据类型4.3.2稀疏矩阵顺序表示4.3.3稀疏矩阵转置4.4字符串M稀疏矩阵00015000000000000091000000008000000312016022001665432105432104.3稀疏矩阵4.3.1稀疏矩阵抽象数据类型1.稀疏矩阵的操作在稀疏矩阵上执行的操作本质上与普通矩阵完全相同.•标量加法、乘法；•矩阵加法、乘法；•转置、求逆；•…4.3稀疏矩阵4.3.1稀疏矩阵抽象数据类型2稀疏矩阵抽象数据类型ADT4.2稀疏矩阵抽象数据类型ADTSparseMatrix{数据:绝大多数元素为零的矩阵。运算:Create();建立一个稀疏矩阵。Destroy()；撤消一个稀疏矩阵。Add(B,C)：当前矩阵对象与B相加，C中返回相加和。Multipl