第五章數(shù)組、字符串、集合類

第五章數(shù)組、字符串、集合類

5.1數(shù)組5.1.1順序存儲的數(shù)組一維數(shù)組是若干個元素的一個有限序列。一維數(shù)組的元素都必須具有相同的類型，即每個數(shù)組元素都占據(jù)相同大小的存儲空間。順序方式存儲

一維數(shù)組A[n]，每個數(shù)組元素占一個存儲單元（不妨設(shè)為C個連續(xù)字節(jié)）.數(shù)組元素A[0]的首地址Loc(A[0])，則對于0≤i≤n-1，有：Loc(A[i])=Loc(A[0])+i*C

對于高維數(shù)組，可以將其轉(zhuǎn)化為一維數(shù)組，其存在兩種存儲方式：按行優(yōu)先順序和按列優(yōu)先順序?！駭?shù)組的存儲①數(shù)組元素在內(nèi)存中是順序、連續(xù)存儲的；②數(shù)組的存儲分配按行（列）進行；③數(shù)組名字表示該數(shù)組的首元素地址，是常量。

1、一維數(shù)組

對于一維數(shù)組而言，各元素按下標次序依次存放，如a[0]，a[1]，a[2]，…等等。且有：&a[0]:&a[1]:&a[2]:數(shù)組中任一元素A[i]的地址可表示為：

Loc(a[i])=Loc(a[0])+i*CC為每個元素占用存儲空間的字節(jié)數(shù)。2、二維數(shù)組按行存放[例]intx[2][3]/*它有2×3個數(shù)組元素*/

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]其存儲分配順序為：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]Ｃ中的二維數(shù)組可以看作是一種特殊的一維數(shù)組。[例]floata[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]二維數(shù)組元素a[i][j]的地址可以這樣得到：Loc(a[i][j])

=

Loc(b[i])

+j*CLoc(b[i])=Loc(b[0])

+i*C’//C’=n*CLoc(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+243、三維數(shù)組

多維數(shù)組元素在內(nèi)存中的排序順序為：第一維的下標變化最慢，最右邊的下標變化最快。[例]floata[2][3][4];

a[0][0][0]→a[0][0][1]→a[0][0][2]→a[0][0][3]→a[0][1][0]→a[0][1][1]→a[0][1][2]→a[0][1][3]→a[0][2][0]→a[0][2][1]→a[0][2][2]→a[0][2][3]→a[1][0][0]→a[1][0][1]→a[1][0][2]→a[1][0][3]a[1][1][0]→a[1][1][1]→a[1][1][2]→a[1][1][3]a[1][2][0]→a[1][2][1]→a[1][2][2]→a[1][2][3]所謂按列優(yōu)先順序，就是將數(shù)組元素按列向量的順序存儲，第i+1個列向量存儲在第i個列向量之后。Loc(a[i][j])=Loc(a[0][0])

+j*m*C+i*C

A[0:2,0:4,0:10,0:2]分別給出按行優(yōu)先、列優(yōu)先存儲下的A[I][J][K][L]地址計算公式。Loc(A)+165I+33J+3K+L

Loc(A)+165L+15K+3J+I

5.1.2靜態(tài)數(shù)組和動態(tài)數(shù)組靜態(tài)數(shù)組的規(guī)模在編譯時已經(jīng)確定，無法在運行時根據(jù)具體需要進行修改1動態(tài)數(shù)組類Array的定義P73聲明：

#include<iostream.h>#include<stdlib.h>template<classT>

classArray

{private：

intFSize;//數(shù)組的大小

T*alist;//指向數(shù)組的第一個元素的指針

voidAllocate();//為數(shù)組分配空間

public：

Array(intsz=50);

Array(constArray<T>&x);//復(fù)制構(gòu)造函數(shù)

Array(void){delete[]alist;}Array<T>&operator=(constArray<T>&x);T&operator[](inti);Array<T>OperatorT*(void)const{returnalist;}intListSize(void)const{returnFsize;}

~ voidResize(intNewSize);};Array類的實現(xiàn)：Template<classT>//為數(shù)組分配空間VoidArray<T>∷Allocate(){

alist=newT[Fsize]; if(alist==0)cerr<<“MemoryAllocationFail.”<<endl;}

Template<classT>//構(gòu)造函數(shù) Array<T>∷Array(intsz=50)

{ if(sz<=0){cerr<<“InvalidArraySize.”<<endl;return;}

Fsize=sz; Allocate();}

template<classT>//復(fù)制構(gòu)造函數(shù) Array<T>∷Array(constArray<T>&x) { Fsize=x.Fsize; Allocate();

for(inti=0;i<Fsize;i++) alist[i]=x.alist[i]; }

template<classT>//[]的重載 T&Array<T>∷operator[](inti) { if(i<0∣∣i>=Fsize) {cerr<<“invalidindex.”<<;endl;exit(1);}

returnalist[i];

}

template<classT>//修改數(shù)組的大小 voidArray<T>∷ReSize(newSize) { if(newSize<=0) {cerr<<“invalidArraySize.”<<endl; return;} if(newSize!=Fsize) {newArray=newT[newSize]; if(newArray==0) {cerr<<“MemoryAllocationFail.” <<endl;return;}

intn=(newSize<=Fsize?newSize;Fsize); for(inti=0;i<n;i++) newArray[i]=alist[i]; delete[]alist; alist=newArray; FSize=newSize; } }

[例]編寫一個函數(shù)，要求輸入一個整數(shù)N，用動態(tài)數(shù)組A來存放2N之間所有5或7的倍數(shù)，輸出該數(shù)組。 #include<iostream.h> #include”array.h” voidmultiple(void) {

Array<int>A(10); intN,count=0; cout<<“N=?”; cin>>N;

~

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;j<count;j++) {cout<<A[j]<<““; if(j+1)%5==0) cout<<endl;

out:

571014152021252830354042454950

out:N＝？in:52

5.1.3稀疏矩陣◆定義：設(shè)矩陣Amn中非零元素的個數(shù)遠遠小 于零元素的個數(shù)，則稱A為稀疏矩陣?！籼攸c：零元素的分布一般沒有規(guī)律?！糇饔茫航鉀Q空間浪費的問題。

1三元組表將表示稀疏矩陣的非零元素的三元組結(jié)點按行優(yōu)先的順序排列，得到一個線性表，將此線性表用順序存儲結(jié)構(gòu)存儲起來，稱之為三元組表。

三元組結(jié)點ijaij500001002000000－300－605A＝B[0]B[1]B[2]B[3]B[4]B[5]0021501333-6020-301035020[例]稀疏矩陣三元組表

稀疏矩陣類的聲明template<classT>//三元組的結(jié)點類classTrituple{

firendclassSparseMatrix;private:introw,col;//非零元素的行號、列號Tvalue;//非零元素的值};

template<classT>//稀疏矩陣類的聲明classSparseMatrix{private:

//稀疏矩陣的行數(shù)、列數(shù)及非零元素個數(shù)intRows,Cols,Count; //存儲三元組表的數(shù)組Trituple<T>smArray[MaxTerm];

public:

SparseMatrix(intMrows,intMcols);//創(chuàng)建一個稀疏矩陣SparseMatrix<T>Transpose();

//求轉(zhuǎn)置矩陣SparseMatrix<T>Add(SparseMatrix<T>b);//求矩陣的和SparseMatrix<T>

Multiply(SparseMatrix<T>b);//求矩陣的乘積};

50100-3000000200-600005A`＝[例]稀疏矩陣500001002000000－300－605A＝轉(zhuǎn)置矩陣50100-3000000200-600005A`＝[例]稀疏矩陣500001002000000－300－605A＝b[0]b[1]b[2]b[3]b[4]b[5]005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30稀疏矩陣類的實現(xiàn)

template<classT>//求轉(zhuǎn)置矩陣

SparseMatrix<T>SparseMatrix::Transpose(){SparseMatrix<T>b;//聲明一個稀疏矩陣bb.Rows=Cols;//b的行數(shù)等于原矩陣的列數(shù)b.Cols=Rows;//b的列數(shù)等于原矩陣的行數(shù)b.Count=Count;//b與原矩陣的非零元素個數(shù)相同if(Count>0）//若有非零元素

{

intBnubmer=0;for(k=0;k<Cols;k++)for(i=0;i<Count;i++)if(smArray[i].col==k)

{

b.smArray[Bnumber].row=k;b.smArray[Bnumber].col=smArray[i].row;b.smArray[Bnumber].value=smArray[i].value;Bnumber++;}

}returnb;//返回轉(zhuǎn)置矩陣b}b[0]b[1]b[2]b[3]b[4]b[5]005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-302十字鏈表

矩陣的元素結(jié)構(gòu)如下：分別表示該元素的左鄰非零元素、上鄰非零元素、所在的行、所在的列和它的值。[例]稀疏矩陣

LEFTUPROWCOLVAL矩陣的每一行、每一列都設(shè)置為由一個表頭結(jié)點引導(dǎo)的循環(huán)鏈表，并且各行和各列的表頭結(jié)點有如下特點：-1=COL（Loc（BASEROW[i]））<0-1=ROW（Loc（BASECOL[j]））<0[例]“主步驟”操作：要求主行主列元素非零。

主行別列主列別行ac…...…......bd…...…......……變換前

主行別列主列別行1/a…...…......b/ad-bc/a…...…......…-c/a變換后5.2字符串5.2.1串的定義和操作●

串的定義：串是零個或多個字符組成的有限序 列。記為S＝“a0a1…

an-1”，串名串值串的長度

●

空串：長度為零的串稱為空串。

●

空白串：由一個或多個空格組成的串稱為空白 串。

子串：串中任意個連續(xù)字符組成的子序列稱為該串的子串。

主串：包含子串的串相應(yīng)地稱為主串。子串在主串中的位置：子串在主串中第一次出現(xiàn)時，子串第一個字符在主串中的序號。[例]A=“Thisisastring”B=“is”類String的串運算

[1]

關(guān)系運算符>，>=，<，<=，==，!=的重載.[2]

串拼接運算符的重載.[3]

從start位置確定字符c的位置：函數(shù)intFind（charc，intstart）const[4]

確定字符c最后一次出現(xiàn)的位置：函數(shù)int

FindLast（charc）const[5]

取子串：函數(shù)StringSubstr（intindex，intcount）const[6]

在index處插入字符串s：函數(shù)voidInsert（constString&s，intindex）

……5.2.2串的存儲方式

1串的順序存儲：把一個串所包含的字符序列相繼存入連續(xù)的字節(jié)中

●

非緊縮格式

//一個存儲單元存放一個字符[例]S＝“a0a1…

an-1”

a0a1an-1Word0Word1Wordn-1…………a

●

緊縮格式//一個存儲單元存放多個字符[例]S=“a0a1…

an-1”//一個存儲單元存放4個字符

a1a4an-1Word0Word1……a0a2a3a5a6a7an-2Wordn/4-1……a

2串的鏈式存儲串的鏈接存儲是把可用的存儲空間分成一系列大小相同的結(jié)點，其中每個結(jié)點的結(jié)構(gòu)為：（str,link）

5china∧p●

結(jié)點大小為4的鏈Sc5hian∧●

結(jié)點大小為1的鏈串的模式匹配算法P87

5.3整型集合集合的定義和操作

●

集合特點：成員互不相同

●

集合表示：{1,2,4,}//與{4,2,1}為同一集合

●

集合最基本操作：并、交、差。并交差集合的實現(xiàn)方法

由數(shù)據(jù)類型為整型（整數(shù)類型、字符類型、枚舉類型）的元素構(gòu)成的集合。本節(jié)我們以整數(shù)集合為代表。1.用一維數(shù)組存放集合集合中整數(shù)的取值范圍：0~setrange-1；

集合全集為{0,1,2,…,setrange-1},表示元素與集合隸屬關(guān)系的數(shù)組：member[setrange]；取值{0，1}數(shù)組member表示元素與集合的從屬關(guān)系。

[例]集合A={0,1,2,4,5,8,9}

3415278611101001190member[setrange]1

按位存儲方式[例]集合A={0,1,2,5,6,7,9,12,13,14,16,20,21,28,31}01100101110011111514131211109876543120101000000110001031302928272625242322212019171816

元素x對應(yīng)member[i]中的第j位（最左邊第1位為0）i=xDIV16;j=xMOD16;例如：33對應(yīng)的存儲位置是member[2]中的第1位2集合類Set的聲明P91#include<iostream.h>#include<stdlib.h>template<classT>classSet{ private://集合中元素個數(shù)的最大值 intsetrange;//位數(shù)組的元素個數(shù)和數(shù)組指針intarraySize;

unsignedshort*member;//確定elt屬于數(shù)組member中的哪個數(shù)組元素intArrayIndex（constT&elt）const;

/*返回一個16位的短整數(shù)，其中除了elt所在的位值為1外，其余的位值為0*/unsignshortBitMask（constT&elt）const;public://構(gòu)造函數(shù)，創(chuàng)建空整型集合

Set（intsetrange）;//析構(gòu)函數(shù)~Set（void）;//定義“+”為兩個集合的并Set<T>Operator+（constSet<T>&X）const;//判斷elt是否在集合中IntIsMember(constT&X）;;//插入元素eltvoidInsert（constT&elt）;……};3集合類Set的實現(xiàn)P93①構(gòu)造函數(shù)//產(chǎn)生一個空集合，其全集大小為sztemplate<classT>Set<T>::Set（intsz）:setrange（sz）{arraySize=（setrange+15）>>4;0000000001011100151413121110987654312000000000000010001514131211109876543120//申請數(shù)組空間member=newunsignedshort[arraySize];if（member==NULL） Error（OutOfMemory）;//將所有位置設(shè)為0，以創(chuàng)建空集for（i=0;i<arraySize;i++） member[i]=0;}

00000000000000001514131211109876543120000000000000000031302928272625242322212019171816②集合并+A={1,2,5,20}B={1,3,31}C={1,2,3,5,20,31}C=A+B②集合并運算符“+”的重載P93template<classT>Set<T>Set<T>::Operator+（constSet<T>&X）const{ if（setrange!=X.setrange） Error（SetDifferentSize）;//用集合tmp存放并集Set<T>tmp（setrange）;//故并集的位值為兩個集合的按位或for（i=0;i<ArraySize;i++）

tmp.member[i]=member[i]∣X.member[i]; returntmp;}00000000010111001514131211109876543120tmp0000000001001100151413121110987654312000000000000110001514131211109876543120*thisXthis->member[0]

000000000010000031302928272625242322212019171816*this100000000000000031302928272625242322212019171816Xtmp100000000010000031302928272625242322212019171816this->member[1]③判斷elt是否在集合中P94template<classT>intSet<T>::IsMember（constT&elt）const{if(int(elt)<0||int(elt)>=setrange) Error（InvalidMemberRef）;//若elt不在集合中，返回0；否則，返回一個非0值returnmember[ArrayIndex（elt）]&BitMask(elt);}

00000000001000001514131211109876543120BitMask(4)00000000000000001514131211109876543120member[ArrayIndex（4）]&BitMask(4)00000000010001001514131211109876543120member[ArrayIndex（4）]④插入元素elttemplate<classT>voidSet<T>::Insert（constT&elt）{//elt是否在0~setrange-1之間if（int（elt）<0‖int（elt）>=setrange） Error（InvalidMemberRef）