工学数据结构5-数组和字符串课件

第5讲DATASTRUCTURE第5讲DATASTRUCTUREDATASTRUCTURE第4章数组和字符串数组1特殊矩阵2稀疏矩阵3字符串4数组1DATASTRUCTURE第4章数组和字符串数组1特殊DATASTRUCTURE§4.1.1

数组ADT数组的定义数组是下标index和值value组成的序对的集合。

(index,value)一维数组： A={(0,15),(1,24),(2,33),(3,21)}

012315243321DATASTRUCTURE§4.1.1

数组ADT数组的DATASTRUCTURE§4.1.1

数组ADT数组ADT

ADTArray{数据：

下标index和元素值value组成的数据对集合,其中任意两个数据对的下标index各不相同。运算：

Create():建立一个数组。

Retrieve(i):返回下标为i的元素值。

Store(i,x):将下标为i的数据对的值置为x。};

DATASTRUCTURE§4.1.1

数组ADT数组ADATASTRUCTURE§4.1.2

数组的顺序表示一维数组的顺序表示

loc(a[i])

=

loc(a[0])+i*k

(

i

=

0,

1,

2,

…,

n-1

)基地址：loc(a[0])每个元素占

k个存储单元。

template<classT>A[]={a0,a1,…,ai,…,an-1};

pA=newT[100];//然后赋值Tb1=pA[i];//获取第i个元素Tb2=*(pA+i);//获取第i个元素DATASTRUCTURE§4.1.2

数组的顺序表示一DATASTRUCTURE§4.1.2

数组的顺序表示二维数组的顺序表示二维数组a[m][n]映射到一维的存储空间时有两种顺序：行优先和列优先。大多数语言如PASCAL、BASIC、C、C++等都是按行优先顺序存储的，FORTRAN是按列优先顺序存储的。A[m][n]={{a0,0,a0,1,…a0,n-1},…,{ai,0,ai,1,…ai,n-1},…,{am-1,0,am-1,1,…am-1,n-1}};C/C++行优先的存储方法DATASTRUCTURE§4.1.2

数组的顺序表示二DATASTRUCTURE§4.1.2

数组的顺序表示二维数组的顺序表示

loc(a[i][j])=loc(a[0][0])+(i*n+j)*k

(0i<m;0j<n)基地址：loc(a[0][0])每个元素占

k个存储单元。

DATASTRUCTURE§4.1.2

数组的顺序表示二DATASTRUCTURE§4.1.2

数组的顺序表示C/C++中申请二维数组的方法：introw=3,col=4;//方法1：=====================================intMtrx[row][col]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};//方法2：=====================================int**ppMtrx=new

int*[row];for(inti=0;i<row;i++) ppMtrx[i]=new

int[col];intn=0;for(i=0;i<row;i++)

for(intj=0;j<col;j++) ppMtrx[i][j]=++n;for(i=0;i<row;i++)

delete[]ppMtrx[i];delete[]ppMtrx;申请指针数组再为指针数组申请空间为二维数组赋值删除二维数组DATASTRUCTURE§4.1.2

数组的顺序表示DATASTRUCTURE§4.1.2

数组的顺序表示//方法3：=====================================#definerow3#definecol4typedefintMtrx[row];

main(){

intn=0;

Mtrx*pMtrx=newMtrx[col];//用法与二维数组相同

for(inti=0;i<row;i++)

for(intj=0;j<col;j++) pMtrx[i][j]=++n;

delete[]pMtrx;}

定义二维数组将数组定义为数据类型DATASTRUCTURE§4.1.2

数组的顺序表示/DATASTRUCTURE§4.1.2

数组的顺序表示多维数组的顺序表示推广到多维数组a[m1][m2]…[mn]，数组元素a[i1][i2]…[in]的存储地址为：

loc(a[i1][i2]…[in])=

loc(a[0]…[0])+(i1*m2*m3*…*mn+i2*m3*m4*…*mn+…+in-1*mn+in)*k

=DATASTRUCTURE§4.1.2

数组的顺序表示多DATASTRUCTURE§4.1.3

一维数组的C++类用C++的模板类定义的一维数组抽象数据类型。公有成员函数包括：

构造函数析构函数重载下标操作符：[]

重载下标操作符用来返回指向第i个元素的引用

重载数组赋值：＝

赋值操作符实现数组的整体赋值。DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTURE§4.1.3

一维数组的C++类#include<assert.h>template<classT>classArray1D{public:Array1D(intsz=0);~Array1D(){delete[]elements;}T&operator[](inti)const;Array1D<T>&operator=(constArray1D<T>&r);friendistream&operator>>(istream&in,Array1D<T>&r);friendostream&operator<< (ostream&out,constArray1D<T>&r);private:

intsize; T*elements;};取元素值整体赋值缺少拷贝构造函数！DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTURE§4.1.3

一维数组的C++类构造函数，申请数组空间template<classT>Array1D<T>::Array1D(intsz){

assert(sz>=0);//越界检查

size=sz; elements=newT[sz];}运算符[]，获取第i个元素template<classT>T&Array1D<T>::operator[](inti)const{

assert(i>=0&&i<size);//越界检查

returnelements[i];}

DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTURE§4.1.3

一维数组的C++类重载运算符=

template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&r)

//数组r整体赋值给this{

if(this!=&r){//防止自我赋值

size=r.size;

delete[]elements;//释放原空间

elements=newT[size];//重新分配空间

for(inti=0;i<size;i++) elements[i]=r.elements[i];}

return*this;}DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTURE§4.1.3

一维数组的C++类重载流运算符>>和<<template<classT>istream&operator>>(istream&in,Array1D<T>&r){

cout<<"Intputarray\n";

for(inti=0;i<r.size;i++)in>>r.elements[i];

returnin;}template<classT>ostream&operator<<(ostream&out,constArray1D<T>&r){

cout<<"Array=";

for(inti=0;i<r.size;i++)out<<r.elements[i]<<''; out<<endl; returnout;}

DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTUREmain中测试该类的效果#include"array1d.h"main(){Array1D<int>a(5),b(8); Array1D<int>c;//采用缺省长度0

cin>>a;cout<<"a"<<a;

cin>>b;cout<<"b"<<b;

cout<<"c"<<c;

cout<<"a[0]="<<a[0]<<“;“<<"b[5]="<<b[5]<<endl;c=b;cout<<"c=b,c"<<c;b=a;cout<<"b=a,b"<<b;}§4.1.3

一维数组的C++类DATASTRUCTUREmain中测试该类的效果§4.1DATASTRUCTURE§1

C++中有关数组的类classArray{public: Array(intsize=0,char*ptr=NULL);

//defaultconstructor Array(constArray&);//copyconstructor ~Array();//destructor

char*getPtr()const{returnm_ptr;}

voidSetArray(intsize,char*ptr);private:

int*m_ptr;//pointertothe //firstelementofthearray.

intm_size;};DATASTRUCTURE§1

C++中有关数组的类cDATASTRUCTURE§1

C++中有关数组的类Array::Array(intsize,char*ptr/*=NULL*/){m_ptr=NULL; SetArray(size,ptr);}Array::Array(constArray&ar){SetArray(ar.m_size,ar.m_ptr);}Array::~Array(){if(m_ptr!=NULL)delete[]m_ptr;}voidArray::SetArray(intsize,char*ptr)

//有问题的函数！{m_size=size;m_ptr=ptr;}浅拷贝！要改成深拷贝。DATASTRUCTURE§1

C++中有关数组的类ADATASTRUCTURE§1

C++中有关数组的类#include<iostream.h>#include<string.h>main(){

charstr[9]; strcpy(str,“Software”);

//注意：此处不能用char*str=”Software”;//因为这样的字符串是只读的。 Arrayar1(8,str); Arrayar2(ar1);

//调用拷贝构造函数，其中调用了SetArray() str[0]=‘6’;//改变数组内容

cout<<ar1.getPtr()<<“”;

cout<<ar2.getPtr()<<endl;}输出：6oftware6oftware浅拷贝的后果。DATASTRUCTURE§1

C++中有关数组的类#DATASTRUCTURE§1

C++中有关数组的类voidArray::SetArray(intsize,char*ptr){

if(size==0||ptr==NULL)return;

if(m_ptr!=NULL)delete[]m_ptr;

//释放原数组

m_size=size; m_ptr=new

char[size];//申请新的空间

strncpy(m_ptr,ptr,size);//拷贝}

输出：Software6oftwareDATASTRUCTURE§1

C++中有关数组的类vDATASTRUCTURE第4章数组和字符串数组1特殊矩阵2稀疏矩阵3字符串4数组1特殊矩阵2DATASTRUCTURE第4章数组和字符串数组1特殊DATASTRUCTURE§4.2.1

对称矩阵对称矩阵和三角矩阵在n×n的矩阵A中，若aij=aji(0<i,j<n)，则称其为n阶对称矩阵。对于对称矩阵，可以只存储上三角(或下三角)中的元素(包括对角线上的元素)。DATASTRUCTURE§4.2.1

对称矩阵对称矩阵DATASTRUCTURE§4.2.1

对称矩阵如果采用二维数组，n维对称矩阵的元素为n2。如果只存储三角中元素，则元素个数为

n(n+1)/2其中行列序号与元素序号的对应关系：0123…num-1a0,0a1,0a1,1a2,0…an-1,0…an-1,n-1DATASTRUCTURE§4.2.1

对称矩阵如果采用DATASTRUCTURE第4章数组和字符串数组1特殊矩阵2稀疏矩阵3字符串4数组1特殊矩阵2稀疏矩阵3DATASTRUCTURE第4章数组和字符串数组1特殊DATASTRUCTURE§4.3.1

稀疏矩阵ADT稀疏矩阵大多数元素为零的矩阵称为稀疏矩阵。对于稀疏矩阵可只存非零元素。DATASTRUCTURE§4.3.1

稀疏矩阵ADT稀DATASTRUCTURE§4.3.1

稀疏矩阵ADT稀疏矩阵ADT

ADTSparseMatrix{数据：绝大多数元素为零的矩阵。运算：

Create():建立一个稀疏矩阵。

Destroy():撤消一个稀疏矩阵。

Add(B,C):当前矩阵对象与B相加，C中返回相加和。

Mul(B,C):当前矩阵对象与B相乘，C中返回相乘积。

Transpose(B):B中返回当前矩阵对象的转置矩阵。}

DATASTRUCTURE§4.3.1

稀疏矩阵ADT稀DATASTRUCTURE§4.3.1

稀疏矩阵ADT#include<iostream.h>template<classT>classSparseMatrix{public: SparseMatrix(intmaxRowSize,intmaxColSize){} ~SparseMatrix(){}

virtualvoidAdd(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;

virtualvoidMul(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;

virtualvoidTranspose(SparseMatrix<T>&B)const;private:

intmaxRows,maxCols;};稀疏矩阵的C++类DATASTRUCTURE§4.3.1

稀疏矩阵ADT#DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表示三元组表示法按照压缩存储的思想，稀疏矩阵Am

n中的每一个非零元素aij

的值、行号和列号可以用一个三元组（i,j,v）表示。三元组可以按行或按列的顺序存储。三元组的Term类template

<classT>structTerms{

introw,col;Tvalue;};DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表示0016032205-16111212323-840916215DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表示#include<iostream.h>template<classT>classSeqTriple{public: SeqTriple(intmSize); ~SeqTriple(){delete[]trip;};

voidAdd(constSeqTriple<T>&B,SeqTriple<T>&C)const;

voidMul(constSeqTriple<T>&B,SeqTriple<T>&C)const;

voidTranspose(SeqTriple<T>&B)const; friendistream&operator>>(istream&input, constSeqTriple<T>&); friendostream&operator<<(ostream&output,

constSeqTriple<T>&);private:

intmaxSize;//最大元素个数

intm,n,t;//行数、列数和非零元素个数

Term<T>*trip;//动态一维数组的指针};行三元组表的C++类DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表DATASTRUCTURE第4章数组和字符串数组1特殊矩阵2稀疏矩阵3字符串4数组1特殊矩阵2稀疏矩阵3字符串4DATASTRUCTURE第4章数组和字符串数组1特殊DATASTRUCTURE§4.4.1

字符串ADT字符串的定义字符串(简称为串)是由n(≥0)个字符组成的有限序列。S=“a0

a1…an-1”(n≥0)其中，S

是串名，单引号括起来的字符序列是串S的值。n是串中字符个数，又称串长度，n=0的串称为空串。要注意区分空串和空白串。串中任意连续个字符组成的子序列称为该串的子串，包含子串的串称为主串。通常以子串的首字符在主串中的位置作为子串在主串中的位置。

S=“abcabcaabcbcde”

P=“aabc”DATASTRUCTURE§4.4.1

字符串ADT字符DATASTRUCTURE§4.4.1

字符串ADT字符串ADTADTString{数据：字符串是由n(≥0)个字符组成的有限序列

S

=

“a0a1…an-1”，0

≤

i

<n。运算：

Create():建立一个空串。Destroy():撤消一个串。Length():返回当前串对象的长度。Clear():置为空串。

Assign(S):串S的值赋给当前串对象。

Concat(b):将串b连接在当前串对象之后。DATASTRUCTURE§4.4.1

字符串ADT字符DATASTRUCTURE§4.4.1

字符串ADTInsert(P,i):将串P插在当前串对象的位置i处。

Delete(i,len):从当前串对象的位置i起删除len个字符。

Substr(i,len):返回当前串对象中，从位置i开始的len个字符组成的子串。Find(i,P):返回子串P在当前串对象中的位置。若当前串对象不包含串P，则返回-1。}DATASTRUCTURE§4.4.1

字符串ADTDATASTRUCTURE§4.4.2

字符串的存储表示顺序表示串的顺序表示可用C++的一维字符数组来描述。

#include<string.h>chars[20]=“cdabcde“；链接表示…ABCI∧firstfirstABCDEFGHI∧\0

DATASTRUCTURE§4.4.2

字符串的存储表示DATASTRUCTURE§4.4.2

字符串的存储表示#include<string.h>classString{public: String();String(const

char*p);~String(){delete[]str;} intFind(inti,String&P);private:

intn;//当前串长

char*str;//动态一维字符数组的指针};String::String(const

char*p){ n=strlen(p);str=newchar[n+1];strcpy(str,p);}DATASTRUCTURE§4.4.2

字符串的存储表示DATASTRUCTURE§4.4.2

字符串的存储表示C语言中字符串操作函数函数原型:char*strdup(constchar*s)函数功能:字符串拷贝，目的空间由该函数分配函数返回:指向拷贝后的字符串指针函数原型:char*strcpy(char*str1,char*str2);函数功能:把str2指向的字符串拷贝到str1中去函数返回:返回str1,即指向str1的指针函数原型:char*strncpy(char*dest, constchar*src，intcount)

函数功能:将字符串src中的count个字符拷贝到字符串dest中去函数返回:指向dest的指针函数原型:unsignedintstrlen(char*str);函数功能:统计字符串str中字符的个数(不包括终止符''\0'')函数返回:返回字符串的长度.DATASTRUCTURE§4.4.2

字符串的存储表示DATASTRUCTURE§4.4.2

字符串的存储表示C语言中字符串操作函数函数原型:

char*strchr(char*str,charch);函数功能:找出str指向的字符串中第一次出现字符ch的位置函数返回:返回指向该位置的指针,如找不到,则返回空指针函数原型:char*

strrchr(constchar*s,intc)函数功能:得到字符串s中最后一个含有c字符的位置指针函数返回:位置指针函数原型:char*strstr(char*str1,char*str2);函数功能:找出str2字符串在str1字符串中第一次出现的位置(不包括str2的串结束符)函数返回:返回该位置的指针,如找不到,返回空指针函数原型:char*strpbrk(constchar*s1,constchar*s2)

函数功能:得到s1中第一个“同时也出现在s2中”字符的位置指针函数返回:位置指针DATASTRUCTURE§4.4.2

字符串的存储表示DATASTRUCTURE§4.4.2

字符串的存储表示C语言中字符串操作函数函数原型:char*

strnset(char*

s,intch,size_tn)函数功能:将字符串s中前n个字符设置为ch的值函数返回:指向s的指针函数原型:char*

strset(char*s,intch)函数功能:将字符串s中所有字符设置为ch的值函数返回:指向s的指针函数原型:char*

strupr(char*s)

函数功能:将字符串s中的字符变为大写函数返回:指向s的指针函数原型:char*

strlwr(char*s)

函数功能:将字符串中的字符变为小写字符函数返回:指向s的指针DATASTRUCTURE§4.4.2

字符串的存储表示DATASTRUCTURE§4.4.2

字符串的存储表示C语言中字符串操作函数还有：intmemcmp(constvoid*s1,constvoid*s2,size_tn)intmemicmp(constvoid*s1,constvoid*s2,size_tn)void*memmove(void*dest,constvoid*src,size_tn)DATASTRUCTURE§4.4.2

字符串的存储表示DATASTRUCTURE习题

p.52实现书上程序4.1与程序4.2一维数组类（要求：增加拷贝构造函数，并在main中增加适当测试代码）===============================================文件名：

D+学号后两位+姓名+布置作业日期例如

D01张三0422

工程名：

D+学号后两位+姓名缩写+布置作业日期例如

D01ZS0422最后把debug目录删除，打包按文件名发送===============================================§作业0422DATASTRUCTURE习题§作业0422第5讲DATASTRUCTURE第5讲DATASTRUCTUREDATASTRUCTURE第4章数组和字符串数组1特殊矩阵2稀疏矩阵3字符串4数组1DATASTRUCTURE第4章数组和字符串数组1特殊DATASTRUCTURE§4.1.1

数组ADT数组的定义数组是下标index和值value组成的序对的集合。

(index,value)一维数组： A={(0,15),(1,24),(2,33),(3,21)}

012315243321DATASTRUCTURE§4.1.1

数组ADT数组的DATASTRUCTURE§4.1.1

数组ADT数组ADT

ADTArray{数据：

下标index和元素值value组成的数据对集合,其中任意两个数据对的下标index各不相同。运算：

Create():建立一个数组。

Retrieve(i):返回下标为i的元素值。

Store(i,x):将下标为i的数据对的值置为x。};

DATASTRUCTURE§4.1.1

数组ADT数组ADATASTRUCTURE§4.1.2

数组的顺序表示一维数组的顺序表示

loc(a[i])

=

loc(a[0])+i*k

(

i

=

0,

1,

2,

…,

n-1

)基地址：loc(a[0])每个元素占

k个存储单元。

template<classT>A[]={a0,a1,…,ai,…,an-1};

pA=newT[100];//然后赋值Tb1=pA[i];//获取第i个元素Tb2=*(pA+i);//获取第i个元素DATASTRUCTURE§4.1.2

数组的顺序表示一DATASTRUCTURE§4.1.2

数组的顺序表示二维数组的顺序表示二维数组a[m][n]映射到一维的存储空间时有两种顺序：行优先和列优先。大多数语言如PASCAL、BASIC、C、C++等都是按行优先顺序存储的，FORTRAN是按列优先顺序存储的。A[m][n]={{a0,0,a0,1,…a0,n-1},…,{ai,0,ai,1,…ai,n-1},…,{am-1,0,am-1,1,…am-1,n-1}};C/C++行优先的存储方法DATASTRUCTURE§4.1.2

数组的顺序表示二DATASTRUCTURE§4.1.2

数组的顺序表示二维数组的顺序表示

loc(a[i][j])=loc(a[0][0])+(i*n+j)*k

(0i<m;0j<n)基地址：loc(a[0][0])每个元素占

k个存储单元。

DATASTRUCTURE§4.1.2

数组的顺序表示二DATASTRUCTURE§4.1.2

数组的顺序表示C/C++中申请二维数组的方法：introw=3,col=4;//方法1：=====================================intMtrx[row][col]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};//方法2：=====================================int**ppMtrx=new

int*[row];for(inti=0;i<row;i++) ppMtrx[i]=new

int[col];intn=0;for(i=0;i<row;i++)

for(intj=0;j<col;j++) ppMtrx[i][j]=++n;for(i=0;i<row;i++)

delete[]ppMtrx[i];delete[]ppMtrx;申请指针数组再为指针数组申请空间为二维数组赋值删除二维数组DATASTRUCTURE§4.1.2

数组的顺序表示DATASTRUCTURE§4.1.2

数组的顺序表示//方法3：=====================================#definerow3#definecol4typedefintMtrx[row];

main(){

intn=0;

Mtrx*pMtrx=newMtrx[col];//用法与二维数组相同

for(inti=0;i<row;i++)

for(intj=0;j<col;j++) pMtrx[i][j]=++n;

delete[]pMtrx;}

定义二维数组将数组定义为数据类型DATASTRUCTURE§4.1.2

数组的顺序表示/DATASTRUCTURE§4.1.2

数组的顺序表示多维数组的顺序表示推广到多维数组a[m1][m2]…[mn]，数组元素a[i1][i2]…[in]的存储地址为：

loc(a[i1][i2]…[in])=

loc(a[0]…[0])+(i1*m2*m3*…*mn+i2*m3*m4*…*mn+…+in-1*mn+in)*k

=DATASTRUCTURE§4.1.2

数组的顺序表示多DATASTRUCTURE§4.1.3

一维数组的C++类用C++的模板类定义的一维数组抽象数据类型。公有成员函数包括：

构造函数析构函数重载下标操作符：[]

重载下标操作符用来返回指向第i个元素的引用

重载数组赋值：＝

赋值操作符实现数组的整体赋值。DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTURE§4.1.3

一维数组的C++类#include<assert.h>template<classT>classArray1D{public:Array1D(intsz=0);~Array1D(){delete[]elements;}T&operator[](inti)const;Array1D<T>&operator=(constArray1D<T>&r);friendistream&operator>>(istream&in,Array1D<T>&r);friendostream&operator<< (ostream&out,constArray1D<T>&r);private:

intsize; T*elements;};取元素值整体赋值缺少拷贝构造函数！DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTURE§4.1.3

一维数组的C++类构造函数，申请数组空间template<classT>Array1D<T>::Array1D(intsz){

assert(sz>=0);//越界检查

size=sz; elements=newT[sz];}运算符[]，获取第i个元素template<classT>T&Array1D<T>::operator[](inti)const{

assert(i>=0&&i<size);//越界检查

returnelements[i];}

DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTURE§4.1.3

一维数组的C++类重载运算符=

template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&r)

//数组r整体赋值给this{

if(this!=&r){//防止自我赋值

size=r.size;

delete[]elements;//释放原空间

elements=newT[size];//重新分配空间

for(inti=0;i<size;i++) elements[i]=r.elements[i];}

return*this;}DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTURE§4.1.3

一维数组的C++类重载流运算符>>和<<template<classT>istream&operator>>(istream&in,Array1D<T>&r){

cout<<"Intputarray\n";

for(inti=0;i<r.size;i++)in>>r.elements[i];

returnin;}template<classT>ostream&operator<<(ostream&out,constArray1D<T>&r){

cout<<"Array=";

for(inti=0;i<r.size;i++)out<<r.elements[i]<<''; out<<endl; returnout;}

DATASTRUCTURE§4.1.3

一维数组的C++DATASTRUCTUREmain中测试该类的效果#include"array1d.h"main(){Array1D<int>a(5),b(8); Array1D<int>c;//采用缺省长度0

cin>>a;cout<<"a"<<a;

cin>>b;cout<<"b"<<b;

cout<<"c"<<c;

cout<<"a[0]="<<a[0]<<“;“<<"b[5]="<<b[5]<<endl;c=b;cout<<"c=b,c"<<c;b=a;cout<<"b=a,b"<<b;}§4.1.3

一维数组的C++类DATASTRUCTUREmain中测试该类的效果§4.1DATASTRUCTURE§1

C++中有关数组的类classArray{public: Array(intsize=0,char*ptr=NULL);

//defaultconstructor Array(constArray&);//copyconstructor ~Array();//destructor

char*getPtr()const{returnm_ptr;}

voidSetArray(intsize,char*ptr);private:

int*m_ptr;//pointertothe //firstelementofthearray.

intm_size;};DATASTRUCTURE§1

C++中有关数组的类cDATASTRUCTURE§1

C++中有关数组的类Array::Array(intsize,char*ptr/*=NULL*/){m_ptr=NULL; SetArray(size,ptr);}Array::Array(constArray&ar){SetArray(ar.m_size,ar.m_ptr);}Array::~Array(){if(m_ptr!=NULL)delete[]m_ptr;}voidArray::SetArray(intsize,char*ptr)

//有问题的函数！{m_size=size;m_ptr=ptr;}浅拷贝！要改成深拷贝。DATASTRUCTURE§1

C++中有关数组的类ADATASTRUCTURE§1

C++中有关数组的类#include<iostream.h>#include<string.h>main(){

charstr[9]; strcpy(str,“Software”);

//注意：此处不能用char*str=”Software”;//因为这样的字符串是只读的。 Arrayar1(8,str); Arrayar2(ar1);

//调用拷贝构造函数，其中调用了SetArray() str[0]=‘6’;//改变数组内容

cout<<ar1.getPtr()<<“”;

cout<<ar2.getPtr()<<endl;}输出：6oftware6oftware浅拷贝的后果。DATASTRUCTURE§1

C++中有关数组的类#DATASTRUCTURE§1

C++中有关数组的类voidArray::SetArray(intsize,char*ptr){

if(size==0||ptr==NULL)return;

if(m_ptr!=NULL)delete[]m_ptr;

//释放原数组

m_size=size; m_ptr=new

char[size];//申请新的空间

strncpy(m_ptr,ptr,size);//拷贝}

输出：Software6oftwareDATASTRUCTURE§1

C++中有关数组的类vDATASTRUCTURE第4章数组和字符串数组1特殊矩阵2稀疏矩阵3字符串4数组1特殊矩阵2DATASTRUCTURE第4章数组和字符串数组1特殊DATASTRUCTURE§4.2.1

对称矩阵对称矩阵和三角矩阵在n×n的矩阵A中，若aij=aji(0<i,j<n)，则称其为n阶对称矩阵。对于对称矩阵，可以只存储上三角(或下三角)中的元素(包括对角线上的元素)。DATASTRUCTURE§4.2.1

对称矩阵对称矩阵DATASTRUCTURE§4.2.1

对称矩阵如果采用二维数组，n维对称矩阵的元素为n2。如果只存储三角中元素，则元素个数为

n(n+1)/2其中行列序号与元素序号的对应关系：0123…num-1a0,0a1,0a1,1a2,0…an-1,0…an-1,n-1DATASTRUCTURE§4.2.1

对称矩阵如果采用DATASTRUCTURE第4章数组和字符串数组1特殊矩阵2稀疏矩阵3字符串4数组1特殊矩阵2稀疏矩阵3DATASTRUCTURE第4章数组和字符串数组1特殊DATASTRUCTURE§4.3.1

稀疏矩阵ADT稀疏矩阵大多数元素为零的矩阵称为稀疏矩阵。对于稀疏矩阵可只存非零元素。DATASTRUCTURE§4.3.1

稀疏矩阵ADT稀DATASTRUCTURE§4.3.1

稀疏矩阵ADT稀疏矩阵ADT

ADTSparseMatrix{数据：绝大多数元素为零的矩阵。运算：

Create():建立一个稀疏矩阵。

Destroy():撤消一个稀疏矩阵。

Add(B,C):当前矩阵对象与B相加，C中返回相加和。

Mul(B,C):当前矩阵对象与B相乘，C中返回相乘积。

Transpose(B):B中返回当前矩阵对象的转置矩阵。}

DATASTRUCTURE§4.3.1

稀疏矩阵ADT稀DATASTRUCTURE§4.3.1

稀疏矩阵ADT#include<iostream.h>template<classT>classSparseMatrix{public: SparseMatrix(intmaxRowSize,intmaxColSize){} ~SparseMatrix(){}

virtualvoidAdd(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;

virtualvoidMul(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;

virtualvoidTranspose(SparseMatrix<T>&B)const;private:

intmaxRows,maxCols;};稀疏矩阵的C++类DATASTRUCTURE§4.3.1

稀疏矩阵ADT#DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表示三元组表示法按照压缩存储的思想，稀疏矩阵Am

n中的每一个非零元素aij

的值、行号和列号可以用一个三元组（i,j,v）表示。三元组可以按行或按列的顺序存储。三元组的Term类template

<classT>structTerms{

introw,col;Tvalue;};DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表示0016032205-16111212323-840916215DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表示#include<iostream.h>template<classT>classSeqTriple{public: SeqTriple(intmSize); ~SeqTriple(){delete[]trip;};

voidAdd(constSeqTriple<T>&B,SeqTriple<T>&C)const;

voidMul(constSeqTriple<T>&B,SeqTriple<T>&C)const;

voidTranspose(SeqTriple<T>&B)const; friendistream&operator>>(istream&input, constSeqTriple<T>&); friendostream&operator<<(ostream&output,

constSeqTriple<T>&);private:

intmaxSize;//最大元素个数

intm,n,t;//行数、列数和非零元素个数

Term<T>*trip;//动态一维数组的指针};行三元组表的C++类DATASTRUCTURE§4.3.2

稀疏矩阵的顺序表DATASTRUCTURE第4章数组和字符串数组1特殊矩阵2稀疏矩阵3字符串4数组1特殊矩阵2稀疏矩阵3字符串4DATASTRUCTURE第4章数组和字符串数组1特殊DATASTRUCTURE§4.4.1

字符串ADT字符串的定义字符串(简称为串)是由n(≥0)个字符组成的有限序列。S=“a0

a1…an-1”(n≥0)其中，S

是串名，单引号括起来的字符序列是串S的值。n是串中字符个数，又称串长度，n=0的串称为空串。要注意区分空串和空白串。串中任意连续个字符组成的子序列称为该串的子串，包含子串的串称为主串。通常以子串的首字符在主串中的位置作为子串在主串中的位置。

S=“abcabcaabcbcde”

P=“aabc”DATASTRUCTURE§4.4.1

字符串ADT字符DATASTRUCTURE§4.4.1

字符串ADT字符串ADTADTString{数据：字符串是由n(≥0)个字符组成的有限序列

S

=

“a0a1…an-1”，0

≤

i

<n。运算：

Create():建立一个空串。Destroy():撤消一个串。Length():返回当前串对象的长度。Clear():置为空串。

Assign(S):串S的值赋给当前串对象。

Concat(b):将串b连接在当前串对象之后。DATASTRUCTURE§4.4.1

字符串ADT字符DATASTRUCTURE§4.4.1

字符串ADTInsert(P,i):将串P插在当前串对象的位置i处。

Delete(i,len):从当前串对象的位置i起删除len个字符。

Substr(i,len):返回当前串对象中，从位置i开始的len个字符组成的子串。Find(i,P):返回子串P在当前串对象中的位置。若当前串对象不包含串P，则返回-1。}DATASTRUCTURE§4.4.1

字符串ADTDA