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

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

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

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

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

1、一維數(shù)組

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

Loc(a[i])=Loc(a[0])+i*CC為每個(gè)元素占用存儲(chǔ)空間的字節(jié)數(shù)。2、二維數(shù)組按行存放[例]intx[2][3]/*它有2×3個(gè)數(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]其存儲(chǔ)分配順序?yàn)椋簒[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)存中的排序順序?yàn)椋旱谝痪S的下標(biāo)變化最慢，最右邊的下標(biāo)變化最快。[例]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ù)組元素按列向量的順序存儲(chǔ)，第i+1個(gè)列向量存儲(chǔ)在第i個(gè)列向量之后。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)先存儲(chǔ)下的A[I][J][K][L]地址計(jì)算公式。Loc(A)+165I+33J+3K+L

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

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

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

classArray

{private：

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

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

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類的實(shí)現(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; } }

[例]編寫(xiě)一個(gè)函數(shù)，要求輸入一個(gè)整數(shù)N，用動(dòng)態(tài)數(shù)組A來(lái)存放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中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小 于零元素的個(gè)數(shù)，則稱A為稀疏矩陣?！籼攸c(diǎn)：零元素的分布一般沒(méi)有規(guī)律?！糇饔茫航鉀Q空間浪費(fèi)的問(wèn)題。

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

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

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

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

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

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

public:

SparseMatrix(intMrows,intMcols);//創(chuàng)建一個(gè)稀疏矩陣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稀疏矩陣類的實(shí)現(xiàn)

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

SparseMatrix<T>SparseMatrix::Transpose(){SparseMatrix<T>b;//聲明一個(gè)稀疏矩陣bb.Rows=Cols;//b的行數(shù)等于原矩陣的列數(shù)b.Cols=Rows;//b的列數(shù)等于原矩陣的行數(shù)b.Count=Count;//b與原矩陣的非零元素個(gè)數(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è)置為由一個(gè)表頭結(jié)點(diǎn)引導(dǎo)的循環(huán)鏈表，并且各行和各列的表頭結(jié)點(diǎn)有如下特點(diǎn)：-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串的定義和操作●

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

an-1”，串名串值串的長(zhǎng)度

●

空串：長(zhǎng)度為零的串稱為空串。

●

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

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

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

[1]

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

串拼接運(yùn)算符的重載.[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串的存儲(chǔ)方式

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

●

非緊縮格式

//一個(gè)存儲(chǔ)單元存放一個(gè)字符[例]S＝“a0a1…

an-1”

a0a1an-1Word0Word1Wordn-1…………a

●

緊縮格式//一個(gè)存儲(chǔ)單元存放多個(gè)字符[例]S=“a0a1…

an-1”//一個(gè)存儲(chǔ)單元存放4個(gè)字符

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

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

5china∧p●

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

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

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

●

集合特點(diǎn)：成員互不相同

●

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

●

集合最基本操作：并、交、差。并交差集合的實(shí)現(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

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

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

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

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

Set（intsetrange）;//析構(gòu)函數(shù)~Set（void）;//定義“+”為兩個(gè)集合的并Set<T>Operator+（constSet<T>&X）const;//判斷elt是否在集合中IntIsMember(constT&X）;;//插入元素eltvoidInsert（constT&elt）;……};3集合類Set的實(shí)現(xiàn)P93①構(gòu)造函數(shù)//產(chǎn)生一個(gè)空集合，其全集大小為sztemplate<classT>Set<T>::Set（intsz）:setrange（sz）{arraySize=（setrange+15）>>4;0000000001011100151413121110987654312000000000000010001514131211109876543120//申請(qǐng)數(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②集合并運(yùn)算符“+”的重載P93template<classT>Set<T>Set<T>::Operator+（constSet<T>&X）const{ if（setrange!=X.setrange） Error（SetDifferentSize）;//用集合tmp存放并集Set<T>tmp（setrange）;//故并集的位值為兩個(gè)集合的按位或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；否則，返回一個(gè)非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）