数据结构课件：第3章 数组和字符串

第三章第三章 数组和字符串数组和字符串3.1 数组数组3.2 矩阵矩阵3.3 字符串字符串3.1 数组数组3.1.1 数组的存储和寻址数组的存储和寻址3.1.2 动态数组动态数组一维数组是若干个元素的一维数组是若干个元素的有限序列有限序列。元素本身就是一个数据结构。元素本身就是一个数据结构。一维数组的元素必须具有一维数组的元素必须具有相同的类相同的类型型，每个数组元素都占据，每个数组元素都占据相同大小的相同大小的存储空间存储空间。n一维数组采用顺序存储结构。一维数组采用顺序存储结构。n每个元素都通过一个下标来指定，故一每个元素都通过一个下标来指定，故一个一维数组对应一个下标函数。个一维数组对应一个下标函数。n一维数组一维数组An，设设每个数组元素每个数组元素的长度的长度为为C（不妨设为（不妨设为C个连续字节）个连续字节）.数组元数组元素素A0的首地址的首地址Loc(A0)，则对于，则对于0i n-1，有：，有：Loc(Ai)=Loc(A0)+i*C n n高维数组可转化为一维数组计算元高维数组可转化为一维数组计算元素的地址。素的地址。n n高维数组有两种存放次序：高维数组有两种存放次序：按行优按行优先先顺序和顺序和按列优先按列优先顺序。顺序。n nBASIC、PASCAL、C/C+等等程程序序设设计计语语言言中中，数数组组按按行行优优先先顺顺序序存存放放；FORTRAN语语言言、Matlab语语言言中，数组则按列优先顺序存放。中，数组则按列优先顺序存放。n n按按行行优优先先顺顺序序，就就是是将将数数组组元元素素按按行行向向量量的的顺顺序序存存储储，第第i+1个个行行向向量量存存储储在在第第i个行向量之后。个行向量之后。n n二维数组的行优先存储二维数组的行优先存储例intx23/*有23个数组元素*/x00 x01x02x10 x11x12按行优先顺序存放按行优先顺序存放存储分配顺序为：存储分配顺序为：x00 x01 x02 x10 x11 x12x00 x01x02x10 x11x12二维数组可以看作是一种特殊的一维数组。二维数组可以看作是一种特殊的一维数组。例例 float a34;b0 a00 a01 a02 a03 b-b1 a10 a11 a12 a13 b2 a20 a21 a22 a23 二维数组二维数组amn中元素中元素aij的地址：的地址：Loc(aij)=Loc(bi)+jCLoc(bi)=Loc(b0)+iC /C=nCLoc(aij)=Loc(a00)+inC+jC =Loc(a00)+(in+j)C b0 b0 a00 a01 a02 a03 a00 a01 a02 a03 b-b1 a10 a11 a12 a13 b-b1 a10 a11 a12 a13 b2 a20 a21 a22 a23 b2 a20 a21 a22 a23例例 float a34Loc(a12)=Loc(a00)+(in+j)C =Loc(a00)+(14+2)4=Loc(a00)+24n n多多维维数数组组元元素素在在内内存存中中的的排排序序顺顺序序为为：第第一一维维的下标变化最慢，最右边的维下标变化最快。的下标变化最慢，最右边的维下标变化最快。n n 例例 float a234三维数组三维数组a000a001a002a003a010a011a012a013a020a021a022a023a100a101a102a103 a110a111a112a113 a120a121a122a123 三三维维数数组组Amnp中数中数组组元素元素aijk地址地址计计算公式算公式为为：Loc(aijk)=Loc(a000)+i*n*p*C+j*p*C+k*Cn n按按列列优优先先顺顺序序，就就是是将将数数组组元元素素按按列列向向量量的的顺顺序序存存储储，第第i+1个个列列向向量量存存储储在在第第i个列向量之后。个列向量之后。n n二维数组二维数组x23的按列优先存储的按列优先存储x00 x01x02x10 x11x12x00 x10 x01x11x02x123.1 数组数组3.1.1 数组的存储和寻址数组的存储和寻址3.1.2 动态数组动态数组动态数组动态数组动态数组类动态数组类动态数组类动态数组类 Array Array 的定义的定义的定义的定义 template template class Array class Array private private：int FSize;/int FSize;/数组的大小数组的大小数组的大小数组的大小 T*alist;/T*alist;/指向数组的第一个元素的指针指向数组的第一个元素的指针指向数组的第一个元素的指针指向数组的第一个元素的指针 publicpublic：ArrayArray(int sz=50);(int sz=50);ArrayArray(const Array&x);/(const Array&x);/复制构造函数复制构造函数复制构造函数复制构造函数 Array Array()delete alist;()delete alist;int int ListSize ListSize(void)const(void)const return Fsize;return Fsize;Array&Array&operator=operator=(const Array&x);(const Array&x);T&operator T&operator(int i);int i);void Resize(int NewSize);/void Resize(int NewSize);/重新定义数组的大小重新定义数组的大小重新定义数组的大小重新定义数组的大小;template /template /修改数组的大小修改数组的大小修改数组的大小修改数组的大小 void Array void Array ReSizeReSize(int newSize)(int newSize)if(newSize=0)if(newSize=0)cerr“cerr“数组大小无效数组大小无效数组大小无效数组大小无效.”endl;return;.”endl;return;if(if(newSize!=FsizenewSize!=Fsize)newArray=newArray=new TnewSizenew TnewSize;if(newArray=0)if(newArray=0)cerr“cerr“内存分配异常内存分配异常内存分配异常内存分配异常.”endl;.”endl;return;return;int n=(int n=(newSize=Fsize?newSsize:FsizenewSize=Fsize?newSsize:Fsize););for(int i=0;in;i+)for(int i=0;in;i+)newArrayi=alisti;newArrayi=alisti;/保留原数组中元素保留原数组中元素保留原数组中元素保留原数组中元素 delete alist;delete alist;alist=newArray;alist=newArray;FSize=newSize;FSize=newSize;例例 编写一个函数，要求输入一个整数编写一个函数，要求输入一个整数N，用动，用动态数组态数组A来存放来存放2 N之间所有之间所有5或或7的倍数，输出的倍数，输出该数组。该数组。#include#include“array.h”void main()Array A(10);int N,count=0;cinN;for(int i=5;i=N;i+)if(i%5=0|i%7=0)Acount+=i;if(count=A.ListSize()A.ReSize(count+10);for(int j=0;jcount;j+)coutAj“”;if(j+1)%5=0)cout j j时时时时有有有有M(M(i i,j j)=0)=0.n n方方方方阵阵阵阵MM是是是是下下下下对对对对角角角角矩矩矩矩阵阵阵阵，当当当当且且且且仅仅仅仅当当当当i i j j时时时时有有有有M(M(i i,j j)=0)=0.50 15 35 2550 15 35 25 0 10 20 60 0 10 20 60 0 0 30 10 0 0 30 10 0 0 0 40 0 0 0 4050 0 0 050 0 0 015 10 0 015 10 0 035 20 30 0 35 20 30 0 25 60 10 4025 60 10 40n n以下三角矩阵为例，讨论其以下三角矩阵为例，讨论其以下三角矩阵为例，讨论其以下三角矩阵为例，讨论其压缩存储方法压缩存储方法压缩存储方法压缩存储方法。n n考虑一个考虑一个考虑一个考虑一个n n n n维下三角矩阵，其第一行有维下三角矩阵，其第一行有维下三角矩阵，其第一行有维下三角矩阵，其第一行有1 1个非零元素，个非零元素，个非零元素，个非零元素，第二行有第二行有第二行有第二行有2 2个非零元素，个非零元素，个非零元素，个非零元素，第，第，第，第n n行有行有行有行有n n个非零元素，非零个非零元素，非零个非零元素，非零个非零元素，非零元素共有元素共有元素共有元素共有(1+2+(1+2+n n)=)=n n(n n+1)/2+1)/2个。可以用大小为个。可以用大小为个。可以用大小为个。可以用大小为n n(n n+1)/2+1)/2的一维数组来存储下三角矩阵，即把下三角矩阵的一维数组来存储下三角矩阵，即把下三角矩阵的一维数组来存储下三角矩阵，即把下三角矩阵的一维数组来存储下三角矩阵，即把下三角矩阵MM的非零的非零的非零的非零元素映射到一个一维数组元素映射到一个一维数组元素映射到一个一维数组元素映射到一个一维数组d d中。中。中。中。n n映射次序可采用按行优先或按列优先。假设映射采取按行映射次序可采用按行优先或按列优先。假设映射采取按行映射次序可采用按行优先或按列优先。假设映射采取按行映射次序可采用按行优先或按列优先。假设映射采取按行优先，非零元素优先，非零元素优先，非零元素优先，非零元素M(M(i i,j j)会映射到一维数组会映射到一维数组会映射到一维数组会映射到一维数组d d中的哪个元素？中的哪个元素？中的哪个元素？中的哪个元素？n n设元素设元素M(i,j)前面有前面有k个元素，可以计算出个元素，可以计算出 k=1+2+(i-1)+(j-1)=i(i-1)/2+(j-1)n n设设一一维维数数组组d的的下下标标是是从从0开开始始，则则M(i,j)映映射射到到d中中所所对对应应的的元元素素是是dk.有有了了k的的计计算算公公式式，可可以以很很容容易易实实现现下下三三角角矩矩阵阵的的压缩存储。压缩存储。3、对称矩阵的压缩存储、对称矩阵的压缩存储n n方方阵阵Mn n是是对对称称矩矩阵阵，当当且且仅仅当当对对于于任任何何1 i,j n，均有，均有M(i,j)=M(j,i).n n因因为为对对称称矩矩阵阵中中M(i,j)与与M(j,i)的的信信息息相相同同，所所以以只只需需存存储储M的的上上三三角角部部分分或或下下三三角角部部分分的元素信息。的元素信息。n n参参参参 照照照照 下下下下 三三三三 角角角角 矩矩矩矩 阵阵阵阵 的的的的 压压压压 缩缩缩缩 存存存存 储储储储 方方方方 法法法法，即即即即 用用用用 大大大大 小小小小 为为为为n n(n n+1)/2+1)/2的的的的一一一一维维维维数数数数组组组组来来来来存存存存储储储储，对对对对于于于于对对对对称称称称矩矩矩矩阵阵阵阵中中中中的的的的下下下下三三三三角角角角矩矩矩矩阵阵阵阵元元元元素素素素M(M(i i,j j)(i i j j)，和和和和下下下下三三三三角角角角矩矩矩矩阵阵阵阵压压压压缩缩缩缩存存存存储储储储的的的的映射公式一样，映射到映射公式一样，映射到映射公式一样，映射到映射公式一样，映射到ddk k(其中