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

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

5.1数组5.1.1顺序存储的数组一维数组是若干个元素的一个有限序列。一维数组的元素都必须具有相同的类型，即每个数组元素都占据相同大小的存储空间。顺序方式存储

一维数组A[n]，每个数组元素占一个存储单元（不妨设为C个连续字节）.数组元素A[0]的首地址Loc(A[0])，则对于0≤i≤n-1，有：Loc(A[i])=Loc(A[0])+i*C

对于高维数组，可以将其转化为一维数组，其存在两种存储方式：按行优先顺序和按列优先顺序。●数组的存储①数组元素在内存中是顺序、连续存储的；②数组的存储分配按行（列）进行；③数组名字表示该数组的首元素地址，是常量。

1、一维数组

对于一维数组而言，各元素按下标次序依次存放，如a[0]，a[1]，a[2]，…等等。且有：&a[0]:&a[1]:&a[2]:数组中任一元素A[i]的地址可表示为：

Loc(a[i])=Loc(a[0])+i*CC为每个元素占用存储空间的字节数。2、二维数组按行存放[例]intx[2][3]/*它有2×3个数组元素*/

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]Ｃ中的二维数组可以看作是一种特殊的一维数组。[例]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]二维数组元素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、三维数组

多维数组元素在内存中的排序顺序为：第一维的下标变化最慢，最右边的下标变化最快。[例]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]所谓按列优先顺序，就是将数组元素按列向量的顺序存储，第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]分别给出按行优先、列优先存储下的A[I][J][K][L]地址计算公式。Loc(A)+165I+33J+3K+L

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

5.1.2静态数组和动态数组静态数组的规模在编译时已经确定，无法在运行时根据具体需要进行修改1动态数组类Array的定义P73声明：

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

classArray

{private：

intFSize;//数组的大小

T*alist;//指向数组的第一个元素的指针

voidAllocate();//为数组分配空间

public：

Array(intsz=50);

Array(constArray<T>&x);//复制构造函数

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类的实现：Template<classT>//为数组分配空间VoidArray<T>∷Allocate(){

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

Template<classT>//构造函数 Array<T>∷Array(intsz=50)

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

Fsize=sz; Allocate();}

template<classT>//复制构造函数 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>//修改数组的大小 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; } }

[例]编写一个函数，要求输入一个整数N，用动态数组A来存放2N之间所有5或7的倍数，输出该数组。 #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稀疏矩阵◆定义：设矩阵Amn中非零元素的个数远远小 于零元素的个数，则称A为稀疏矩阵。◆特点：零元素的分布一般没有规律。◆作用：解决空间浪费的问题。

1三元组表将表示稀疏矩阵的非零元素的三元组结点按行优先的顺序排列，得到一个线性表，将此线性表用顺序存储结构存储起来，称之为三元组表。

三元组结点ijaij500001002000000－300－605A＝B[0]B[1]B[2]B[3]B[4]B[5]0021501333-6020-301035020[例]稀疏矩阵三元组表

稀疏矩阵类的声明template<classT>//三元组的结点类classTrituple{

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

template<classT>//稀疏矩阵类的声明classSparseMatrix{private:

//稀疏矩阵的行数、列数及非零元素个数intRows,Cols,Count; //存储三元组表的数组Trituple<T>smArray[MaxTerm];

public:

SparseMatrix(intMrows,intMcols);//创建一个稀疏矩阵SparseMatrix<T>Transpose();

//求转置矩阵SparseMatrix<T>Add(SparseMatrix<T>b);//求矩阵的和SparseMatrix<T>

Multiply(SparseMatrix<T>b);//求矩阵的乘积};

50100-3000000200-600005A`＝[例]稀疏矩阵500001002000000－300－605A＝转置矩阵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稀疏矩阵类的实现

template<classT>//求转置矩阵

SparseMatrix<T>SparseMatrix::Transpose(){SparseMatrix<T>b;//声明一个稀疏矩阵bb.Rows=Cols;//b的行数等于原矩阵的列数b.Cols=Rows;//b的列数等于原矩阵的行数b.Count=Count;//b与原矩阵的非零元素个数相同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;//返回转置矩阵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十字链表

矩阵的元素结构如下：分别表示该元素的左邻非零元素、上邻非零元素、所在的行、所在的列和它的值。[例]稀疏矩阵

LEFTUPROWCOLVAL矩阵的每一行、每一列都设置为由一个表头结点引导的循环链表，并且各行和各列的表头结点有如下特点：-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”，串名串值串的长度

●

空串：长度为零的串称为空串。

●

空白串：由一个或多个空格组成的串称为空白 串。

子串：串中任意个连续字符组成的子序列称为该串的子串。

主串：包含子串的串相应地称为主串。子串在主串中的位置：子串在主串中第一次出现时，子串第一个字符在主串中的序号。[例]A=“Thisisastring”B=“is”类String的串运算

[1]

关系运算符>，>=，<，<=，==，!=的重载.[2]

串拼接运算符的重载.[3]

从start位置确定字符c的位置：函数intFind（charc，intstart）const[4]

确定字符c最后一次出现的位置：函数int

FindLast（charc）const[5]

取子串：函数StringSubstr（intindex，intcount）const[6]

在index处插入字符串s：函数voidInsert（constString&s，intindex）

……5.2.2串的存储方式

1串的顺序存储：把一个串所包含的字符序列相继存入连续的字节中

●

非紧缩格式

//一个存储单元存放一个字符[例]S＝“a0a1…

an-1”

a0a1an-1Word0Word1Wordn-1…………a

●

紧缩格式//一个存储单元存放多个字符[例]S=“a0a1…

an-1”//一个存储单元存放4个字符

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

2串的链式存储串的链接存储是把可用的存储空间分成一系列大小相同的结点，其中每个结点的结构为：（str,link）

5china∧p●

结点大小为4的链Sc5hian∧●

结点大小为1的链串的模式匹配算法P87

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

●

集合特点：成员互不相同

●

集合表示：{1,2,4,}//与{4,2,1}为同一集合

●

集合最基本操作：并、交、差。并交差集合的实现方法

由数据类型为整型（整数类型、字符类型、枚举类型）的元素构成的集合。本节我们以整数集合为代表。1.用一维数组存放集合集合中整数的取值范围：0~setrange-1；

集合全集为{0,1,2,…,setrange-1},表示元素与集合隶属关系的数组：member[setrange]；取值{0，1}数组member表示元素与集合的从属关系。

[例]集合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对应member[i]中的第j位（最左边第1位为0）i=xDIV16;j=xMOD16;例如：33对应的存储位置是member[2]中的第1位2集合类Set的声明P91#include<iostream.h>#include<stdlib.h>template<classT>classSet{ private://集合中元素个数的最大值 intsetrange;//位数组的元素个数和数组指针intarraySize;

unsignedshort*member;//确定elt属于数组member中的哪个数组元素intArrayIndex（constT&elt）const;

/*返回一个16位的短整数，其中除了elt所在的位值为1外，其余的位值为0*/unsignshortBitMask（constT&elt）const;public://构造函数，创建空整型集合

Set（intsetrange）;//析构函数~Set（void）;//定义“+”为两个集合的并Set<T>Operator+（constSet<T>&X）const;//判断elt是否在集合中IntIsMember(constT&X）;;//插入元素eltvoidInsert（constT&elt）;……};3集合类Set的实现P93①构造函数//产生一个空集合，其全集大小为sztemplate<classT>Set<T>::Set（intsz）:setrange（sz）{arraySize=（setrange+15）>>4;0000000001011100151413121110987654312000000000000010001514131211109876543120//申请数组空间member=newunsignedshort[arraySize];if（member==NULL） Error（OutOfMemory）;//将所有位置设为0，以创建空集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）