數組、字符串、集合類

1、 第五章第五章 數組、字符串、集合類數組、字符串、集合類 數組的存儲數組的存儲 數組元素在內存中是順序、連續(xù)存儲的；數組元素在內存中是順序、連續(xù)存儲的； 數組的存儲分配按行（列）進行；數組的存儲分配按行（列）進行； 數組名字表示該數組的首元素地址，是常量。數組名字表示該數組的首元素地址，是常量。 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靜態(tài)數組

4、的規(guī)模在編譯時已經確定，無法在運行時根據靜態(tài)數組的規(guī)模在編譯時已經確定，無法在運行時根據 具體需要進行修改具體需要進行修改 1 1 動態(tài)數組類動態(tài)數組類 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，用動，用動 態(tài)數組態(tài)數組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 為稀疏矩陣。為稀疏矩陣。 特點：零元素的分布一般沒有規(guī)律。特點：零元素的分布一般沒有規(guī)律。 作用：解決空間浪費的問題。作用：解決空間浪費的問題。 1 1 三元組表三元組表 將表示稀疏矩陣的非零元素的三元組將表示稀疏矩陣的非零元素的三元組 結點按行優(yōu)先的順序排列，得到一個線性表，將此線性結點按行優(yōu)先的順序排列，得到一個線性表，將此線性 表用順序存儲結構存儲起來，稱之為三元組表。表用順序存儲結構存

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); / / 創(chuàng)建一個稀疏矩陣創(chuàng)建一個稀疏矩陣 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 矩陣的每一行、每一列都設置為由一個表頭結點引導的矩陣的每一行、每一列都設置為由一個表頭結點引導的 循環(huán)鏈表，并且各行和各列的表頭結點有如下特點：循環(huán)鏈表，并且各行和各列的表頭結

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: / / 構造函數，創(chuàng)建空整型集合構造函數，創(chuàng)建空整型集合 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，以創(chuàng)建空集，以創(chuàng)建空集 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