第五章数组、字符串、集合类

第五章数组、字符串、集合类nullnull 第五章数组、字符串、集合类null 5.1 数组 5.1.1 顺序存储的数组一维数组是若干个元素的一个有限序列。一维数组的元素都必须具有相同的类型，即每个数组元素都占据相同大小的存储空间。顺序方式存储null 一维数组A[n] ，每个数组元素占一个存储单元（不妨设为C个连续字节）. 数组元素A[0]...

nullnull 第五章数组、字符串、集合类null 5.1 数组 5.1.1 顺序存储的数组一维数组是若干个元素的一个有限序列。一维数组的元素都必须具有相同的类型，即每个数组元素都占据相同大小的存储空间。顺序方式存储null 一维数组A[n] ，每个数组元素占一个存储单元（不妨设为C个连续字节）. 数组元素A[0]的首地址Loc(A[0])，则对于0≤i ≤n-1，有： Loc(A[i])=Loc(A[0])+i*C 对于高维数组，可以将其转化为一维数组，其存在两种存储方式：按行优先顺序和按列优先顺序。null ● 数组的存储 ① 数组元素在内存中是顺序、连续存储的； ② 数组的存储分配按行（列）进行； ③ 数组名字表示该数组的首元素地址，是常量。 1、一维数组对于一维数组而言，各元素按下标次序依次存放，如a[0]，a[1]，a[2]，…等等。且有： &a[0]: &a[1]: &a[2]: null 数组中任一元素A[i]的地址可表示为： Loc(a[i]) = Loc(a[0]) +i*C C为每个元素占用存储空间的字节数。 2、二维数组按行存放 [例] int x[2][3]/*它有2×3个数组元素*/ x[0][0] x[0][1] x[0][2] x[1][0] x[1][1] x[1][2] nullx[0][0] x[0][1] x[0][2] x[1][0] x[1][1] x[1][2] 其存储分配顺序为： x[0][0]->x[0][1]->x[0][2]->x[1][0]->x[1][1]->x[1][2] &x[0][0] &x[0][1] &x[0][2] &x[1][0] &x[1][1] &x[1][2]nullＣ中的二维数组可以看作是一种特殊的一维数组。 [例] float a[3][4]; b[0] a[0][0] a[0][1] a[0][2] a[0][3] b- b[1] a[1][0] a[1][1] a[1][2] a[1][3] b[2] a[2][0] a[2][1] a[2][2] a[2][3] 二维数组元素a[i][j]的地址可以这样得到： Loc(a [i][j]) = Loc(b[i]) +j*C Loc(b[i]) = Loc(b[0]) + i*C’ // C’=n*C Loc(a[i][j]) = Loc(a[0][0]) + i*n*C+j*C = Loc(a[0][0]) + (i*n+j)*C [例] Loc(a[1][2]) = a+(i*n+j)C =a+(1*4+2)*4 = a+24null 3、三维数组多维数组元素在内存中的排序顺序为：第一维的下标变化最慢，最右边的下标变化最快。 [例]float a[2][3][4]; nullnull 所谓按列优先顺序，就是将数组元素按列向量的顺序存储，第i+1个列向量存储在第i个列向量之后。 Loc(a[i][j]) = Loc(a[0][0]) + j*m*C+i*C null 5.1.2 静态数组和动态数组静态数组的规模在编译时已经确定，无法在运行时根据具体需要进行修改 1 动态数组类 Array 的定义声明： # include # include template class Array { private： int FSize;//数组的大小 T* alist;//指向数组的第一个元素的指针 void Allocate( );//为数组分配空间 null public： Array( int sz=50 ); Array( const Array & x ); //复制构造函数 Array( void ) { delete[ ] alist;} Array& operator=(const Array& x); T& operator[ ](int i); Array Operator T*(void)const {return alist;} int ListSize(void) const { return Fsize;} ~null void Resize(int NewSize); }; Array类的实现： Template // 为数组分配空间 Void Array∷Allocate( ) { alist = new T[Fsize]; if( alist==0 ) cerr<<“Memory Allocation Fail.”< // 构造函数 Array∷Array(int sz=50) { if(sz<=0) { cerr<<“Invalid Array Size.”<//复制构造函数 Array∷Array(const Array& x ) { Fsize=x.Fsize; Allocate( ); for(int i=0;i< Fsize;i++) alist[i] = x.alist[i]; } null template // [ ]的重载 T& Array∷operator[ ](int i) { if(i<0∣∣i>=Fsize) { cerr<<“invalid index.”<<;endl;exit(1); } return alist[i]; }null template // 修改数组的大小 void Array∷ReSize(newSize) { if (newSize <= 0) { cerr<<“invalid Array Size.”< #include ”array.h” void multiple(void) { Array A(10); int N,count = 0; cout<<“N=?”; cin>>N; ~null for(int i=5;i<=N;i++) { if(count==A.ListSize( )) A.ReSize(count+10); if(i%5==0||i%7==0) A[count++]=i; } for(int j=0;j 题。 1 三元组表将表示稀疏矩阵的非零元素的三元组结点按行优先的顺序排列，得到一个线性表，将此线性表用顺序存储结构存储起来，称之为三元组表。三元组结点 ijaijnull[例] 稀疏矩阵三元组表null 稀疏矩阵类的声明 template // 三元组的结点类 class Trituple { firend class SparseMatrix; private: int row,col; // 非零元素的行号、列号 T value; // 非零元素的值 }; null template // 稀疏矩阵类的声明 class SparseMatrix { private: // 稀疏矩阵的行数、列数及非零元素个数 int Rows,Cols,Count; // 存储三元组表的数组 Trituple smArray[MaxTerm]; null public: SparseMatrix( int Mrows,int Mcols); // 建立一个稀疏矩阵 SparseMatrix Transpose( ); // 求转置矩阵 SparseMatrix Add(SparseMatrix b); // 求矩阵的和 SparseMatrix Multiply(SparseMatrix b); // 求矩阵的乘积 }; null[例] 稀疏矩阵转置矩阵null[例] 稀疏矩阵b[0] b[1] b[2] b[3] b[4] b[5]null 稀疏矩阵类的实现 template // 求转置矩阵 SparseMatrix SparseMatrix::Transpose( ) { SparseMatrix b; // 声明一个稀疏矩阵b b.Rows = Cols; // b的行数等于原矩阵的列数 b.Cols = Rows; // b的列数等于原矩阵的行数 b.Count = Count; // b与原矩阵的非零元素个数相同 if ( Count > 0 ） // 若有非零元素 null { int Bnubmer = 0; for(k=0;k ，>= ，< ，< = ，= = ，!= 的重载. [2] 串拼接运算符的重载. [3] 从start位置确定字符c的位置：函数int Find （char c，int start）const [4] 确定字符c最后一次出现的位置：函数int FindLast（char c） const [5] 取子串：函数String Substr（int index，int count） const [6] 在index处插入字符串s：函数void Insert（const String & s，int index） ……null5.2.2 串的存储方式 1 串的顺序存储：把一个串所包含的字符序列相继存入连续的字节中 ● 非紧缩格式 // 一个存储单元存放一个字符 [例] S ＝ “a0a1… an-1” anull ● 紧缩格式 // 一个存储单元存放多个字符 [例] S=“a0a1… an-1” // 一个存储单元存放4个字符 a● 结点大小为1的链● 结点大小为1的链 2 串的链式存储串的链接存储是把可用的存储空间分成一系列大小相同的结点，其中每个结点的结构为：（str, link） null5.3 整型集合集合的定义和操作 ● 集合定义：互不相同的成员。 ● 集合表示：{ 1,2,4,} //与 { 4,2,1 }为同一集合 ● 集合最基本操作：并、交、差。集合的实现方法由数据类型为整型（整数类型、字符类型、枚举类型）的元素构成的集合。本节我们以整数集合为代表。 1 . 用一维数组存放集合集合中整数的取值范围：0 ~ setrange-1；集合全集为{ 0,1,2,… ,setrange-1 }, 表示元素与集合隶属关系的数组：B[setrange]；取值{0，1} 数组member表示16个元素与集合的从属关系。位 null [例] 集合 A ={0,1,2,4,5,8,9} null [例] 集合 A ={0,1,2,5,6,7,9,12,13,14,16,20,21,28,31} null2 集合类Set的声明 # include # include template < class T > class Set { private: // 集合中元素个数的最大值 int setrange ; null// 位数组的元素个数和数组指针 int arraySize ; unsigned short *member ; // 确定elt属于数组member中的哪个数组元素 int ArrayIndex（const T & elt） const ; /* 返回一个16位的短整数，其中除了elt所在的位值为1外，其余的位值为0 */ unsign short BitMask（const T& elt）const ; nullpublic: // 构造函数，创建空整型集合 Set（int setrange） ; // 析构函数 ~ Set（void） ; // 定义“+”为两个集合的并 Set Operator +（const Set& X）const ; // 判断elt是否在集合中 Int IsMember(const T & X）;; // 插入元素elt void Insert（const T & elt） ; … … };null3 集合类Set的实现 ①构造函数//产生一个空集合，其全集大小为sz template Set::Set（int sz）:setrange（sz） { arraySize = （setrange+15）>> 4 ; null//申请数组空间 member = new unsigned short [arraySize] ; if（member = = NULL） Error（OutOfMemory） ; // 将所有位置设为0，以创建空集 for（i = 0 ; i < arraySize ; i++ ） member[i] = 0 ; } null② 集合并+ A = {1,2,5,20} B = {1,3,31} C = {1,2,3,5,20,31} C=A+Bnull② 集合并运算符“+”的重载 template Set Set::Operator+（const Set& X）const { if（setrange != X.setrange ） Error（SetDifferentSize）; // 用集合tmp存放并集 Set tmp（setrange）; null// 故并集的位值为两个集合的按位或 for（i = 0 ; i < ArraySize ; i++ ） tmp.member[i] = member[i]∣X.member[i] ; return tmp ; }null this->member[1]null ③ 判断elt是否在集合中 template< class T > int Set::IsMember（const T& elt）const {if(int(elt)<0||int(elt)> = setrange) Error（ InvalidMemberRef）; // 若elt不在集合中，返回0；否则，返回一个非0值 return member[ ArrayIndex（elt）] & BitMask(elt); } nullmember[ ArrayIndex（elt）] member[0]member[1]null null ④ 插入元素elt template void Set::Insert（const T & elt ） { // elt是否在0~setrange-1之间 if（int（elt）< 0 ‖ int（elt）> = setrange ） Error（InvalidMemberRef）; // 置elt所在位值为1 member[ ArrayIndex(elt)]|= BitMask(elt) ; }nullmember[ ArrayIndex(elt)]|= BitMask(elt) ; null⑤ 删除元素elt template void Set::Delete（const T & elt ） { // elt是否在0~setrange-1之间 if（int（elt）< 0 ‖ int（elt）> = setrange ） Error（InvalidMemberRef）; // 置elt所在位值为0 member[ ArrayIndex(elt)]&=(!BitMask(elt)); } null member[ ArrayIndex(elt)]&=(!BitMask(elt)); null本章小结 1．多维数组在计算机中有两种存放形式：行优先和列优先。 2．行优先规则是左边下标变化最慢，右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。 3．列优先规则是右边下标变化最慢，左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。 4．稀疏矩阵的非零元排列无任何规律，为节省内存单元，进行压缩存储时，可以采用三元组表示方法，即存储非零元素的行号、列号和值。若干个非零元有若干个三元组，若干个三元组称为三元组表。null第五章作业课后第2题null练习题 1．按行优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])）。 2．按列优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])）。. 3．若矩阵Amn中的某个元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Amn，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。null4．试写一个算法，查找十字链表中某一非零元素x。 5．给定矩阵A如下，写出它的三元组表和十字链表。 6．对上题的矩阵，画出它的带行指针的链表，并给出算法来建立它。 7．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。

                    本文档为【第五章 数组、字符串、集合类】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

第五章 数组、字符串、集合类

你可能还喜欢

第五章数组、字符串、集合类