数组、字符串、集合类

1、 第五章第五章 数组、字符串、集合类数组、字符串、集合类 数组的存储数组的存储 数组元素在内存中是顺序、连续存储的；数组元素在内存中是顺序、连续存储的； 数组的存储分配按行（列）进行；数组的存储分配按行（列）进行； 数组名字表示该数组的首元素地址，是常量。数组名字表示该数组的首元素地址，是常量。 1 1、一维数组、一维数组 对于一维数组而言，各元素按下标次序依次存放，对于一维数组而言，各元素按下标次序依次存放， 如如a0a0，a1a1，a2a2，等等。且有：等等。且有： float a34; 二维数组元素二维数组元素aijaij的地址可以这样得到：的地址可以这样得到： Loc(a ijij)

2、= = Loc(bibi) +j +j* *C C Loc(bibi) = = Loc(b0b0) + i + i* *C C / C / C=n=n* *C C Loc(aijaij) = = Loc(a00a00) + i + i* *n n* *C+jC+j* *C C = = Loc(a00a00) + (i + (i* *n+j)n+j)* *C C 例例 Loc(a12) = a+(ia12) = a+(i* *n+j)Cn+j)C =a+(1 =a+(1* *4+2)4+2)* *4 = a+244 = a+24 3 3、三维数组、三维数组 多维数组元素在内存中的排序顺序为：第一

3、维多维数组元素在内存中的排序顺序为：第一维 的下标变化最慢，最右边的下标变化最快。的下标变化最慢，最右边的下标变化最快。 例例 float a234;float a234; a000a001a002a003 a010a011a012a013 a020a021a022a023 a100a101a102a103 a110a111a112a113 a120a121a122a123 Loc(aijaij) = = Loc(a00a00) + j + j* *m m* *C+iC+i* *C C 数组、字符串、集合类数组、字符串、集合类 165L+15K+3J+I 165L+15K+3J+I w静态数组

4、的规模在编译时已经确定，无法在运行时根据静态数组的规模在编译时已经确定，无法在运行时根据 具体需要进行修改具体需要进行修改 1 1 动态数组类动态数组类 Array Array 的定义的定义 P73P73 w声明：声明： # include # include # include # include template template class Array class Array private private： int FSize;/int FSize;/数组的大小数组的大小 T T* * alist;/ alist;/指向数组的第一个元素的指针指向数组的第一个元素的指针 void All

5、ocate( );/void Allocate( );/为数组分配空间为数组分配空间 publicpublic： Array( int sz=50 );Array( int sz=50 ); Array( const Array Array( const Array /复制构造函数复制构造函数 Array( void )Array( void ) delete alist; delete alist; Array Array T T Array Operator T Array Operator T* *(void)const(void)const return alist; return a

6、list; int ListSize(void) const int ListSize(void) const return Fsize; return Fsize; void Resize(int NewSize);void Resize(int NewSize); ; ArrayArray类的实现：类的实现： Template / Template / 为数组分配空间为数组分配空间 Void ArrayAllocate( )Void ArrayAllocate( ) alist = new TFsize;alist = new TFsize; if( alist=0 )if( alist=

7、0 ) cerrcerr“Memory Allocation Fail.Memory Allocation Fail.”endl;endl; Template Template / / 构造函数构造函数 ArrayArray(int sz=50)ArrayArray(int sz=50) if(sz=0) if(sz=0) cerr cerr“Invalid Array Size.Invalid Array Size.”endl;endl; return; return; Fsize=sz; Fsize=sz; Allocate( ); Allocate( ); template /templ

8、ate /复制构造函数复制构造函数 ArrayArray(const Array Fsize=x.Fsize; Allocate( ); Allocate( ); for(int i=0;i Fsize;i+) for(int i=0;i Fsize;i+) alisti = x.alisti; alisti = x.alisti; template / template / 的重载的重载 Tendl;exit(1);endl;exit(1); return alisti; return alisti; template / template / 修改数组的大小修改数组的大小 void Arr

9、ayReSize(newSize)void ArrayReSize(newSize) if (newSize = 0)if (newSize = 0) cerr cerr“invalid Array Size.invalid Array Size.”endl;endl; return; return; if(newSize != Fsize) if(newSize != Fsize) newArray = new TnewSize; newArray = new TnewSize; if(newArray=0) if(newArray=0) cerr cerr“Memory Allocatio

10、n Fail.Memory Allocation Fail.” endl;return; endl;return; int n=(newSize = Fsize?newSize;Fsize); int n=(newSize = Fsize?newSize;Fsize); for(int i=0 for(int i=0;in;i+)in;i+) newArrayi=alisti; newArrayi=alisti; delete alist; delete alist; alist=newArray; alist=newArray; FSize=newSize; FSize=newSize; 例

11、例 编写一个函数，要求输入一个整数编写一个函数，要求输入一个整数N N，用动，用动 态数组态数组A A来存放来存放2 N2 N之间所有之间所有5 5或或7 7的倍数，输出的倍数，输出 该数组。该数组。 #include #include #include #include ”array.harray.h” void multiple(void)void multiple(void) Array A(10); Array A(10); int N,count = 0; int N,count = 0; cout coutN; cinN; for(int i=5;i=N;i+)for(int i=

12、5;i=N;i+) if(count=A.ListSize( ) if(count=A.ListSize( ) A.ReSize(count+10);A.ReSize(count+10); if(i%5=0|i%7=0) if(i%5=0|i%7=0) Acount+=i; Acount+=i; for(int j=0;jcount;j+)for(int j=0;jcount;j+) coutAj coutAj“ “; ; if(j+1) % 5=0) if(j+1) % 5=0) coutendl; coutendl; out : 5 7 10 14 15 20 21 25 28 30 35

13、 40 42 45 49 50 out :N？ in: 52 定义：设矩阵定义：设矩阵 A Am m n n中非零元素的个数远远小中非零元素的个数远远小 于零元素的个数，则称于零元素的个数，则称 A A 为稀疏矩阵。为稀疏矩阵。 特点：零元素的分布一般没有规律。特点：零元素的分布一般没有规律。 作用：解决空间浪费的问题。作用：解决空间浪费的问题。 1 1 三元组表三元组表 将表示稀疏矩阵的非零元素的三元组将表示稀疏矩阵的非零元素的三元组 结点按行优先的顺序排列，得到一个线性表，将此线性结点按行优先的顺序排列，得到一个线性表，将此线性 表用顺序存储结构存储起来，称之为三元组表。表用顺序存储结构存

14、储起来，称之为三元组表。 三元组结点三元组结点 ijaij 50 0 0 0 50 0 0 0 10 0 20 0 10 0 20 0 0 0 0 0 0 0 0 0 30 0 30 0 60 560 5 A B0 B1 B2 B3 B4 B5 00 2 1 5 0 1 3 3 3 -60 20 -30 10 3 50 2 0 例例 稀疏矩阵稀疏矩阵 三元组表三元组表 w 稀疏矩阵类的声明稀疏矩阵类的声明 w template / template / 三元组的结点类三元组的结点类 w class Tritupleclass Trituple w w firend class SparseMa

15、trix; firend class SparseMatrix; w private: private: w int row,col; int row,col; / 非零元素的行号、列号非零元素的行号、列号 w T value; T value; / 非零元素的值非零元素的值 w ; w template / template / 稀疏矩阵类的声明稀疏矩阵类的声明 class SparseMatrixclass SparseMatrix private: private: / 稀疏矩阵的行数、列数及非零元素个数稀疏矩阵的行数、列数及非零元素个数 int Rows,Cols,Count;int

16、Rows,Cols,Count; / / 存储三元组表的数组存储三元组表的数组 Trituple smArrayMaxTerm;Trituple smArrayMaxTerm; public:public: SparseMatrix( int Mrows,int Mcols); SparseMatrix( int Mrows,int Mcols); / / 创建一个稀疏矩阵创建一个稀疏矩阵 SparseMatrix Transpose( );SparseMatrix Transpose( ); / / 求转置矩阵求转置矩阵 SparseMatrix Add(SparseMatrix b);Sp

17、arseMatrix Add(SparseMatrix b); / / 求矩阵的和求矩阵的和 SparseMatrix SparseMatrix Multiply(SparseMatrix b); Multiply(SparseMatrix b); / / 求矩阵的乘积求矩阵的乘积 ; 50 10 0 -30 50 10 0 -30 0 0 0 0 0 0 0 0 0 20 0 -60 0 20 0 -60 0 0 0 5 0 0 0 5 A 例例 稀疏矩阵稀疏矩阵 50 0 0 0 50 0 0 0 10 0 20 0 10 0 20 0 0 0 0 0 0 0 0 0 30 0 30 0

18、60 560 5 A 转置矩阵转置矩阵 50 10 0 -30 50 10 0 -30 0 0 0 0 0 0 0 0 0 20 0 -60 0 20 0 -60 0 0 0 5 0 0 0 5 A 例例 稀疏矩阵稀疏矩阵 50 0 0 0 50 0 0 0 10 0 20 0 10 0 20 0 0 0 0 0 0 0 0 0 30 0 30 0 60 560 5 A b0 b1 b2 b3 b4 b5 0050 30-30 1010 335 32-60 1220 a0 a1 a2 a3 a4 a5 0050 2120 0110 335 23-60 03-30 w 稀疏矩阵类的实现稀疏矩阵类

19、的实现 template / template / 求求转置矩阵转置矩阵 SparseMatrix SparseMatrix:Transpose( )SparseMatrix SparseMatrix:Transpose( ) SparseMatrix b; SparseMatrix b; / 声明一个稀疏矩阵b b.Rows = Cols; b.Rows = Cols; / b的行数等于原矩阵的列数 b.Cols = Rows; b.Cols = Rows; / b的列数等于原矩阵的行数 b.Count = Count; b.Count = Count; / b与原矩阵的非零元素个数相同 i

20、f ( Count 0 if ( Count 0 ） / 若有非零元素 int Bnubmer = 0;int Bnubmer = 0; for(k=0;kCols;k+) for(k=0;kCols;k+) for(i=0;iCount;i+) for(i=0;iCount;i+) if(smArrayi.col=k) if(smArrayi.col=k) b.smArrayBnumber.row=k; b.smArrayBnumber.row=k; b.smArrayBnumber.col= b.smArrayBnumber.col= smArrayi.row; smArrayi.row;

21、 b.smArrayBnumber.value= b.smArrayBnumber.value= smArrayi.value; smArrayi.value; Bnumber+; Bnumber+; return b; / return b; / 返回转置矩阵返回转置矩阵 b b b0 b1 b2 b3 b4 b5 0050 30-30 1010 335 32-60 1220 a0 a1 a2 a3 a4 a5 0050 2120 0110 335 23-60 03-30 2 2 十字链表十字链表 矩阵的元素结构如下：矩阵的元素结构如下：分别表示该元素的左邻非分别表示该元素的左邻非 零元素、

22、上邻非零元素、所在的行、所在的列和它的零元素、上邻非零元素、所在的行、所在的列和它的 值。值。 例例 稀疏矩阵稀疏矩阵 LEFTLEFTUPUP ROWROWCOLCOLVALVAL 8000 7090 0004 0600 3 2 1 0 3210 8000 7090 0004 0600 3 2 1 0 3210 -1 -1 -1 -1 -1 -1 -1 -1 1 3 6 2 1 4 3 2 9 3 4 7 4 4 8 矩阵的每一行、每一列都设置为由一个表头结点引导的矩阵的每一行、每一列都设置为由一个表头结点引导的 循环链表，并且各行和各列的表头结点有如下特点：循环链表，并且各行和各列的表头结

23、点有如下特点： - -1 = COL（Loc（BASEROWi） 0 - -1 = ROW（Loc（BASECOLj） ，= ， ， = ，= = ，!= 的重载的重载. w 2 串拼接运算符的重载串拼接运算符的重载. w 3 从从start位置确定字符位置确定字符c的位置：的位置： 函数函数int Find （char c，int start）const w 4 确定字符确定字符c最后一次出现的位置：最后一次出现的位置： 函数函数int FindLast（char c） const w 5 取子串：取子串： 函数函数String Substr（int index，int count） con

24、st w 6 在在index处插入字符串处插入字符串s： 函数函数void Insert（const String j = x MOD 16; 例如：例如：33对应的存储位置是对应的存储位置是 member2中的第中的第1位位 2 2 集合类集合类SetSet的声明的声明 P91P91 # include # include # include # include template class Settemplate class Set private:private: / / 集合中元素个数的最大值集合中元素个数的最大值 int setrange ; int setrange ; / / 位

25、数组的元素个数和数组指针位数组的元素个数和数组指针 int arraySize ; int arraySize ; unsigned short unsigned short * *member ; member ; / / 确定确定eltelt属于数组属于数组membermember中的哪个数组元素中的哪个数组元素 int ArrayIndexint ArrayIndex（const T const ; / /* * 返回一个返回一个1616位的短整数，其中除了位的短整数，其中除了eltelt所在所在 的位值为的位值为1 1外，其余的位值为外，其余的位值为0 0 * */ / unsign

26、short BitMaskunsign short BitMask（const T const ; public:public: / / 构造函数，创建空整型集合构造函数，创建空整型集合 SetSet（int setrangeint setrange） ; ; / / 析构函数析构函数 Set Set（voidvoid） ; ; / / 定义定义“+ +”为两个集合的并为两个集合的并 Set Operator +Set Operator +（const Set const ; / / 判断判断eltelt是否在集合中是否在集合中 Int IsMember(const T ; ; / / 插入元

27、素插入元素eltelt void Insertvoid Insert（const T ; ; 3 3 集合类集合类SetSet的实现的实现 P93P93 构造函数构造函数/产生一个空集合，其全集大小为产生一个空集合，其全集大小为 szsz templatetemplate Set:SetSet:Set（int szint sz）:setrange:setrange（szsz） arraySize = arraySize = （setrange+15setrange+15） 4 ; 4 ; 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 01 11 11 10

28、00 0 1515 1414 1313 1212 1111 10109 98 87 76 65 54 43 31 12 20 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 01 10 00 00 0 1515 1414 1313 1212 1111 10109 98 87 76 65 54 43 31 12 20 0 /申请数组空间申请数组空间 member = new unsigned short arraySize ; member = new unsigned short arraySize ; ifif（member = = NULLmem

29、ber = = NULL） ErrorError（OutOfMemoryOutOfMemory） ; ; / / 将所有位置设为将所有位置设为0 0，以创建空集，以创建空集 forfor（i = 0 ; i arraySize ; i+ i = 0 ; i arraySize ; i+ ） memberi = 0 ; memberi = 0 ; 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 00 00 00 00 0 1515 1414 1313 1212 1111 10109 98 87 76 65 54 43 31 12 20 0 0 00 0 0

30、 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 00 00 00 00 0 3131 3030 2929 2828 2727 2626 2525 2424 2323 2222 2121 2020 1919171718181616 w 集合并集合并+ + A = 1,2,5,20 A = 1,2,5,20 B = 1,3,31 B = 1,3,31 C = 1,2,3,5,20,31 C = 1,2,3,5,20,31 C=A+B C=A+B 集合并运算符集合并运算符“+ +”的重载的重载 P93P93 templatetemplate Set Set:Operator+

31、Set Set:Operator+（const Set ; / / 用集合用集合tmptmp存放并集存放并集 Set tmpSet tmp（setrangesetrange）; ; / / 故并集的位值为两个集合的按位或故并集的位值为两个集合的按位或 forfor（i = 0 ; i ArraySize ; i+ i = 0 ; i member0this-member0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 10 00 00 00 00 0 3131 3030 2929 2828 2727 2626 2525 2424 2323 2222 2121

32、 2020 1919171718181616 * *thisthis 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 00 00 00 00 0 3131 3030 2929 2828 2727 2626 2525 2424 2323 2222 2121 2020 1919171718181616 X X tmp tmp 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 10 00 00 00 00 0 3131 3030 2929 2828 2727 2626 2525 2424 2323 2222 2121 2020

33、1919171718181616 this-member1this-member1 判断判断eltelt是否在集合中是否在集合中 P94P94 templatetemplate int Set:IsMemberint Set:IsMember（const T ; / / 若若eltelt不在集合中，返回不在集合中，返回0 0；否则，返回一个非；否则，返回一个非0 0值值 return return member ArrayIndexmember ArrayIndex（eltelt） 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 10 00 00 00 00

34、0 1515 1414 1313 1212 1111 10109 98 87 76 65 54 43 31 12 20 0 BitMask(4)BitMask(4) 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 00 00 00 00 0 1515 1414 1313 1212 1111 10109 98 87 76 65 54 43 31 12 20 0 member ArrayIndexmember ArrayIndex（4 4） ; / / 置置eltelt所在位值为所在位值为1 1 member ArrayIndex(elt)|= BitMas

35、k(elt) ; member ArrayIndex(elt)|= BitMask(elt) ; member ArrayIndex(elt)|= BitMask(elt) ; member ArrayIndex(elt)|= BitMask(elt) ; 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 10 00 00 00 00 0 1515 1414 1313 1212 1111 10109 98 87 76 65 54 43 31 12 20 0 BitMask(4)BitMask(4) 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 00 00 01 10 00 0 1515 1414 1313 1212 1111 10109 98 87 76 65 54 43 31 12 20 0 member ArrayIndexmember ArrayIndex（4 4） 0 0 删除元素删除元素elt templatetemplate void Set:Deletevoid Set:Delete（const T ; / / 置置eltelt所在位值为所在位值为0 0 member ArrayIndex(elt) member ArrayIndex(elt) member Arr