《刘大有数据结构》 chapter 5 数组字符串和集合类

第五章数组字符串和集合类•5.1数组•5.2字符串•5.3整型集合5.1数组•5.1.1顺序存储的数组•5.1.2静态数组与动态数组•5.1.3稀疏矩阵5.1.1顺序存储的数组•任何程序语言都提供一维数组.一个一维数组就是若干个元素的一个有限序列，每个元素都通过一个下标来指定，元素本身就是一个数据结构（或是整型、逻辑型、字符型，或是数组、记录）.对一维数组唯一的限制是所有的数组元素都必须具有相同的类型，即每个数组元素都占据相同大小的存储空间.•数组在内存中一般是以顺序方式存储的.•设一维数组A[n]存放在n个连续的存储单元中，每个数组元素占一个存储单元（不妨设为C个连续字节）.如果数组元素A[0]的首地址是L，则A[1]的首地址是L+C，A[2]的首地址是L+2C，……，依次类推，对于有：•对于高维数组，可将其转化为一维数组来考虑.高维数组存在着两种存储方式——按行优先顺序和按列优先顺序。01inCiALociALoc*])0[(])[(•所谓按行优先顺序，就是将数组元素按行向量的顺序存储，第个行向量存储在第个行向量之后。换句话说，就是将数组转化为一维数组来考虑。•以按行优先顺序存储的二维数组为例，它可以被看作一个一维数组，其中B[i]是由的第行的n个元素构成的一个一维数组（第个行向量），即B[i]={A[i][0]，A[i][1]，…，A[i][n-2]，A[i][n-1]}1ii][]][[21nmmma][1mbAmn[][]Bm[]Aii•下面我们计算二维数组A[m][n]中任一元素A[i][j]的存储地址，设每个数组元素所占空间为C个连续字节,有•再例如三维数组D[3][3][4]，可以把它看作一维数组B1[3]={D[0][3][4]，D[1][3][4]，D[2][3][4]}Loc（A[i][j]）=Loc（A[0][0]）+Cni**+Cj*=Loc（A[0][0]）+Cjni*)*(•对于B1[3]中的数组元素D[i][3][4]（i=0,1,2），又可看作一个一维数组Bi2[3]=D[i][3][4]={D[i][0][4]，D[i][1][4]，D[i][2][4]}；而Bi2[3]中的数组元素D[i][j][4]（i=0,1,2，j=0,1,2），就是一个一维数组Bij3[4]=D[i][j][4]={D[i][j][0]，D[i][j][1]，D[i][j][2]，D[i][j][3]}，•因此，三维数组D[3][3][4]的顺序存储次序是D[0][0][0]，D[0][0][1]，D[0][0][2]，D[0][0][3]D[0][1][0]，D[0][1][1]，D[0][1][2]，D[0][1][3]D[0][2][0]，D[0][2][1]，D[0][2][2]，D[0][2][3]……D[2][0][0]，D[2][0][1]，D[2][0][2]，D[2][0][3]D[2][1][0]，D[2][1][1]，D[2][1][2]，D[2][1][3]D[2][2][0]，D[2][2][1]，D[2][2][2]，D[2][2][3]•我们把该问题推而广之，对于n维数组，设其每个元素占C个字节，且第一个元素的地址为，该数组的任一个元素的地址为：][]][[21nmmma)0,,0,0(Loc][]][[21niiia11221*),,,0(),,,(CiiiLociiiLocnn11223**),,,0,0(CiCiiiLocn...1111***)0,,0(CiCiCiLocnnn211*******)0,,0(mmCimCiCiLocnnnnCimiLocnnknkppk*})*({)0,,0(111•所谓按列优先顺序，就是将数组元素按列向量的顺序存储，第i+1个列向量存储在第i个列向量之后。换句话说，就是将数组转化为一维数组来考虑。请读者计算以按列优先顺序存储的多维数组中任一个元素的存储地址.][]][[21nmmma][]][[21nmmma][]][[21niiia5.1.2静态数组与动态数组•所谓静态数组，是指在声明一个数组时，就为整个数组分配了固定大小的内存空间.但静态数组有一个很大的缺陷：数组的规模（大小）在编译时就已确定，无法在运行时根据具体需要进行修改.为了弥补静态数组的缺陷，我们给出动态数组类Array的定义.#includeiostream.h#includestdlib.htemplateclassTclassArray{private:intFSize;//数组的大小T*alist;//指向数组的第一个元素的指针voidAllocate（）;//为数组申请内存空间public://构造函数Array（intsz=50）;//复制构造函数Array（constArrayT&x）;//析构函数～Array（void）{delete[]alist;}//赋值运算符“=”的重载（实现与复制构造函数相同）ArrayT&operator=（constArrayT&x）;//标识下标的符号“[]”的重载T&operator[]（inti）;//指针转换ArrayTOperatorT*（void）const{returnalist;}//返回表的大小intListSize（void）const{returnFSize;}//修改数组大小voidResize（intNewSize）;};Array类的实现：//私有函数Allocate：为数组分配空间TemplateclassTvoidArrayT::Allocate（）{alist=newT[FSize];if（alist==0）cerr“MemoryAllocationFail.”endl;}//构造函数templateclassTArrayT::Array（intsz=50）{if（sz=0）{cerr“InvalidArraySize.”endl;return;}FSize=sz;Allocate（）;}//复制构造函数：在声明数组时复制动态数组xtemplateclassTArrayT::Array（constArrayT&x）{FSize=x.FSize;Allocate（）;for（inti=0;iFSize;i++）alist[i]=x.alist[i];}//[]的重载templateclassTT&ArrayT::operator[]（inti）{if（i0||i=FSize）{cerr“invalidindex.”endl;exit（1）;}returnalist[i];}//修改数组大小templateclassTvoidArrayT::ReSize（newSize）{if（newSize=0）{cerr“invalidArraySize.”endl;return;}if（newSize!=FSize）{newArray=newT[newSize];if（newArray==0）{cerr“MemoryAllocationFail.”endl;return;}//n取较小值intn=（newSize=FSize?newSize;FSize）;//复制数组for（inti=0;in;i++）newArray[i]=alist[i];delete[]alist;//释放原数组所占空间alist=newArray;FSize=newSize;}•下面我们给出一个Array类的应用例子.•例5.1编写一个函数，要求输入一个整数N，用动态数组A来存放2～N之间所有5或7的倍数，输出该数组.•说明：因为N由用户给出，编写程序时无法知道需要多大的数组来存放数据，因此采用动态数组（初始时大小为10），每当数组满时就调整数组大小，给它增加10个元素.//求2～N之间的5或7的倍数，并动态存放在数组A中#includeiostream.h#include＂array.h＂//该文件中包含Array类的定义voidmultiple（void）{ArrayintA[10];intN，count=0;cout“N=?”;cinN;for（inti=5;i=N;i++）{if（count==A.ListSize（））A.ReSize（count+10）;if（i%5==0||i%7==0）A[count++]=i;}//输出数组for（intj=0;jcount;j++）{coutA[j]“”;//每输出5个数换行if（（j+1）%5==0）coutendl;}}运行结果如下：（输出）N=?（输入）52↙（输出）5710141520212528303540424549505.1.3稀疏矩阵•稀疏矩阵，简单的讲，就是零元素很多的矩阵.对于一个用二维数组来存储的稀疏矩阵，如果假设存储每个数组元素需要L个字节，那么存储整个矩阵需要个字节.但是，这些存储空间的大部分存放的是零元素，这样造成大量空间浪费.为了节省存储空间，应该采用某种方法，使得只存储非零元素就可以达到存储稀疏矩阵的目的.AmnLnm•我们知道，对于矩阵的每个元素，知道其行号和列号，就可以确定该元素在矩阵中的位置.因此，如果用一个结点来存储一个非零元素的话，那么该结点可以设计如下：•如上所示的由三个域（行号、列号和元素值）构成的结点被称为三元组结点：矩阵的每个非零元素由一个三元组结点(,,)唯一确定.ijaijijaij•如何在三元组结点的基础上实现对整个稀疏矩阵的存储？下面我们分别给出用顺序存储方式和链接存储方式实现的稀疏矩阵类的声明和实现.•三元组表•十字链表5.1.3.1三元组表•将表示稀疏矩阵的非零元素的三元组结点按行优先的顺序排列，可以得到一个线性表，将此线性表用顺序存储结构存储起来，称之为三元组表.•例如：稀疏矩阵506030000002001000050A•其对应的三元组表为：B[0]B[1]B[2]B[3]B[4]B[5]00501010122030-3032-60335稀疏矩阵类声明//三元组的结点类templateclassTclassTrituple{friendclassSparseMatrix;private://非零元素的行号、列号introw，col;//非零元素的值Tvalue;};//稀疏矩阵的类声明templateclassTclassSparseMatrix{private://稀疏矩阵的行数、列数及非零元素个数intRows，Cols，Count;//存储三元组表的数组TritupleTsmArray[MaxTerm];public://构造函数，建立一个Mrows行Mcols列的稀疏矩阵SparseMatrix（intMrows，intMcols）;//求转置矩阵SparseMatrixTTranspose（）;//求矩阵的和SparseMatrixTAdd（SparseMatrixTb）;//求矩阵的乘积SparseMatrixTMultiply（SparseMatrixTb）;};稀疏矩阵类实现//求转置矩阵templateclassTSparseMatrixTSparseMatrixT::Transpose（）{SparseMatrixTb;//声明一个稀疏矩阵bb.Rows=Cols;//b的行数等于原矩阵的列数b.Cols=Rows;//b的列数等于原矩阵的行数b.Count=Count;//b与原矩阵的非零元素个数相同接下页if（Count0）//若有非零元素{intBnumber=0;for（k=0;kCols;k++）//对矩阵b按行优先依次确认非零元素f