[工学]数据结构5-数组和字符串课件.ppt

1、数数 据据 结结 构构第5讲DATA STRUCTUREDATA STRUCTURE第4章 数组和字符串数组数组1特殊矩阵特殊矩阵2稀疏矩阵稀疏矩阵3字符串字符串4数组数组1DATA STRUCTURE4.1.1 数组ADT 数组是下标index 和值value 组成的序对的集合。(index,value)一维数组：A=(0,15),(1,24),(2,33),(3,21)012315243321DATA STRUCTURE4.1.1 数组ADTADT Array 数据：数据：下标下标index和元素值和元素值value组成的数据对集合组成的数据对集合,其中任意两其中任意两个数据对的下标个数据

2、对的下标index各不相同。各不相同。运算：运算：Create():建立一个数组。建立一个数组。Retrieve(i):返回下标为返回下标为i的元素值。的元素值。Store(i,x):将下标为将下标为i的数据对的值置为的数据对的值置为x。;DATA STRUCTURE4.1.2 数组的顺序表示 template A=a0,a1,ai,an-1;pA=new T100;/然后赋值然后赋值 T b1=pAi;/获取第获取第i个元素个元素 T b2=*(pA+i);/获取第获取第i个元素个元素DATA STRUCTURE4.1.2 数组的顺序表示v 二维数组的顺序表示二维数组的顺序表示 二维数组am

3、n映射到一维的存储空间时有两种顺序：行优先和列优先。大多数语言如PASCAL、BASIC、C、C+等都是按行优先顺序存储的，FORTRAN是按列优先顺序存储的。1,11,10,11,1,0,1,11,10,11,01,00,0nmmmniiinnaaaaaaaaaaaaAmn=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+行优先的存储方法行优先的存储方法DATA STRUCTURE4.1.2 数组的顺序表示loc(aij)=loc(a00)+(i*n+j)*k (0 i m;0 j n)DATA STRUCTURE4.

4、1.2 数组的顺序表示 v C/C+中申请二维数组的方法：中申请二维数组的方法：v int row=3,col=4;/方法方法1：=int Mtrxrowcol=1,2,3,4,5,6,7,8,9,10,11,12;/方法方法2：=int*ppMtrx=new int*row;for(int i=0;i row;i+)ppMtrxi=new intcol;int n=0;for(i=0;i row;i+)for(int j=0;j col;j+)ppMtrxij=+n;for(i=0;i row;i+)delete ppMtrxi;delete ppMtrx;申请指针数组申请指针数组再为指针数

5、组申请空间再为指针数组申请空间为二维数组赋值为二维数组赋值删除二维数组删除二维数组DATA STRUCTURE4.1.2 数组的顺序表示/方法方法3：=#define row 3#define col 4typedef int Mtrxrow;main()int n=0;Mtrx*pMtrx=new Mtrxcol;/用法与二维数组相同用法与二维数组相同for(int i=0;i row;i+)for(int j=0;j col;j+)pMtrxij=+n;delete pMtrx;定义二维数组定义二维数组将数组定义为将数组定义为数据类型数据类型DATA STRUCTURE4.1.2 数组的顺

6、序表示v 多维数组的顺序表示多维数组的顺序表示v 推广到多维数组推广到多维数组am1m2 mn，数组元素，数组元素ai1i2 in的存储地址为的存储地址为：loc(ai1i2 in)=loc(a00)+(i1*m2*m3*mn +i2*m3*m4*mn +in-1*mn +in)*k=)1,(0 *)*()00 a(111njmikimilocjjnnjkknjjDATA STRUCTURE4.1.3 一维数组的C+类 v用用C+的模板类定义的一维数组抽象数据的模板类定义的一维数组抽象数据类型。公有成员函数包括：类型。公有成员函数包括：构造函数 析构函数 重载下标操作符：重载下标操作符用来返回

7、指向第i个元素的引用 重载数组赋值：赋值操作符实现数组的整体赋值。DATA STRUCTURE4.1.3 一维数组的C+类#include template class Array1Dpublic:Array1D(int sz=0);Array1D()delete elements;T&operator(int i)const;Array1D&operator=(const Array1D&r);friend istream&operator(istream&in,Array1D&r);friend ostream&operator(ostream&out,const Array1D&r);p

8、rivate:int size;T*elements;取元素值取元素值整体赋值整体赋值缺少拷贝构造函数！缺少拷贝构造函数！DATA STRUCTURE4.1.3 一维数组的C+类template Array1D:Array1D(int sz)assert(sz=0);/越界检查越界检查size=sz;elements=new Tsz;template T&Array1D:operator(int i)const assert(i=0&isize);/越界检查越界检查 return elementsi;DATA STRUCTURE4.1.3 一维数组的C+类 template Array1D&A

9、rray1D:operator=(const Array1D&r)/数组数组r整体赋值给整体赋值给this if(this!=&r)/防止自我赋值防止自我赋值 size=r.size;delete elements;/释放原空间释放原空间 elements=new Tsize;/重新分配空间重新分配空间 for(int i=0;i和和template istream&operator (istream&in,Array1D&r)cout Intput arrayn;for(int i=0;i r.elementsi;return in;template ostream&operator (os

10、tream&out,const Array1D&r)cout Array=;for(int i=0;ir.size;i+)out r.elementsi;outendl;return out;DATA STRUCTUREv main中测试该类的效果中测试该类的效果#include array1d.hmain()Array1D a(5),b(8);Array1D c;/采用缺省长度采用缺省长度0 cina;couta b;coutb b;coutc c;couta0=a0“;“b5=b5endl;c=b;coutc=b,c c;b=a;coutb=a,b b;4.1.3 一维数组的C+类DATA

11、 STRUCTURE1 C+中有关数组的类class Arraypublic:Array(int size=0,char*ptr=NULL);/default constructorArray(const Array&);/copy constructorArray();/destructorchar*getPtr()const return m_ptr;void SetArray(int size,char*ptr);private:int*m_ptr;/pointer to the /first element of the array.int m_size;DATA STRUCTURE1

12、 C+中有关数组的类Array:Array(int size,char*ptr/*=NULL*/)m_ptr=NULL;SetArray(size,ptr);Array:Array(const Array&ar)SetArray(ar.m_size,ar.m_ptr);Array:Array()if(m_ptr!=NULL)delete m_ptr;void Array:SetArray(int size,char*ptr)/有问题的函数！有问题的函数！m_size=size;m_ptr=ptr;浅拷贝！要改成深拷贝。DATA STRUCTURE1 C+中有关数组的类#include#incl

13、ude main()char str9;strcpy(str,“Software”);/注意：此处不能用注意：此处不能用char*str=”Software”;/因为这样的字符串是只读的。因为这样的字符串是只读的。Array ar1(8,str);Array ar2(ar1);/调用拷贝构造函数，其中调用了调用拷贝构造函数，其中调用了SetArray()str0 =6;/改变数组内容改变数组内容 cout ar1.getPtr()“”;cout ar2.getPtr()endl;输出：6oftware 6oftware浅拷贝的后果。DATA STRUCTURE1 C+中有关数组的类void A

14、rray:SetArray(int size,char*ptr)if(size=0|ptr=NULL)return;if(m_ptr!=NULL)delete m_ptr;/释放原数组释放原数组m_size=size;m_ptr=new charsize;/申请新的空间申请新的空间strncpy(m_ptr,ptr,size);/拷贝拷贝 输出：Software 6oftwareDATA STRUCTURE第4章 数组和字符串数组数组1特殊矩阵特殊矩阵2稀疏矩阵稀疏矩阵3字符串字符串4数组数组1特殊矩阵特殊矩阵2DATA STRUCTURE4.2.1 对称矩阵 在nn的矩阵A中，若aij=aj

15、i (0 i,j n)，则称其为n阶阶对称矩阵对称矩阵。对于对称矩阵，可以只存储上三角(或下三角)中的元素(包括对角线上的元素)。1,11,10,11,10,10,0nnnnaaaaaaDATA STRUCTURE4.2.1 对称矩阵v 如果采用二维数组，n维对称矩阵的元素为n2。v 如果只存储三角中元素，则元素个数为 n(n+1)/2v 其中行列序号与元其中行列序号与元素序号的对应关系：素序号的对应关系：0123num-1a0,0a1,0a1,1a2,0an-1,0 an-1,n-1 j ii 2)1j(jj ij 2)1i(ikDATA STRUCTURE第4章 数组和字符串数组数组1特殊

16、矩阵特殊矩阵2稀疏矩阵稀疏矩阵3字符串字符串4数组数组1特殊矩阵特殊矩阵2稀疏矩阵稀疏矩阵3DATA STRUCTURE4.3.1 稀疏矩阵ADT 大多数元素为零的矩阵称为稀疏矩阵。对于稀疏矩阵可只存非零元素。0001500000000000009100000000800000031201602200166543210DATA STRUCTURE4.3.1 稀疏矩阵ADTADT SparseMatrix 数据：数据：绝大多数元素为零的矩阵。绝大多数元素为零的矩阵。运算：运算：Create():建立一个稀疏矩阵。建立一个稀疏矩阵。Destroy():撤消一个稀疏矩阵。撤消一个稀疏矩阵。Add(B

17、,C):当前矩阵对象与当前矩阵对象与B相加，相加，C中返回相加和。中返回相加和。Mul(B,C):当前矩阵对象与当前矩阵对象与B相乘，相乘，C中返回相乘积。中返回相乘积。Transpose(B):B中返回当前矩阵对象的转置矩阵。中返回当前矩阵对象的转置矩阵。DATA STRUCTURE4.3.1 稀疏矩阵ADT#include template class SparseMatrixpublic:SparseMatrix(int maxRowSize,int maxColSize)SparseMatrix()virtual void Add(const SparseMatrix&B,Sparse

18、Matrix&C)const;virtual void Mul(const SparseMatrix&B,SparseMatrix&C)const;virtual void Transpose(SparseMatrix&B)const;private:int maxRows,maxCols;稀疏矩阵的稀疏矩阵的C+类类DATA STRUCTURE4.3.2 稀疏矩阵的顺序表示v 按照压缩存储的思想，稀疏矩阵按照压缩存储的思想，稀疏矩阵Am n中的每一个非零元素中的每一个非零元素 aij 的值、行号和列号可以用一个三元组（的值、行号和列号可以用一个三元组（i,j,v）表示。）表示。v 三元组可以

19、按行或按列的顺序存储。三元组可以按行或按列的顺序存储。v 三元组的三元组的Term类类template struct Terms int row,col;T value;DATA STRUCTURE4.3.2 稀疏矩阵的顺序表示00015000000000000091000000008000000312016022001665432100 0 160 3 220 5 -161 1 121 2 3 2 3 -84 0 916 2 15DATA STRUCTURE4.3.2 稀疏矩阵的顺序表示#include template class SeqTriple public:SeqTriple(in

20、t mSize);SeqTriple()delete trip;void Add(const SeqTriple&B,SeqTriple&C)const;void Mul(const SeqTriple&B,SeqTriple&C)const;void Transpose(SeqTriple&B)const;friend istream&operator(istream&input,const SeqTriple&);friend ostream&operator(ostream&output,const SeqTriple&);private:int maxSize;/最大元素个数最大元素个

21、数int m,n,t;/行数、列数和非零元素个数行数、列数和非零元素个数Term*trip;/动态一维数组的指针动态一维数组的指针;行三元组表的行三元组表的C+类类DATA STRUCTURE第4章 数组和字符串数组数组1特殊矩阵特殊矩阵2稀疏矩阵稀疏矩阵3字符串字符串4数组数组1特殊矩阵特殊矩阵2稀疏矩阵稀疏矩阵3字符串字符串4DATA STRUCTURE4.4.1 字符串ADT 字符串(简称为串)是由n(0)个字符组成的有限序列。S =“a0 a1 an-1”(n0)其中，S S 是串名，单引号括起来的字符序列是串S S的值。n 是串中字符个数，又称串长度，n=0的串称为空串。v要注意区分

22、要注意区分空串空串和和空白串空白串。v 串中任意连续个字符组成的子序列称为该串的串中任意连续个字符组成的子序列称为该串的子串子串，包含，包含子串的串称为子串的串称为主串主串。通常以子串的首字符在主串中的位置。通常以子串的首字符在主串中的位置作为子串在主串中的位置。作为子串在主串中的位置。S S=“abcabcaabcbcdeabcabcaabcbcde”P P=“aabcaabc”DATA STRUCTURE4.4.1 字符串ADTADT String数据：数据：字符串是由字符串是由n(0)个字符组成的有限序列个字符组成的有限序列S=“a0a1an-1”，0 i n。运算：运算：Create(

23、):建立一个空串。建立一个空串。Destroy():撤消一个串。撤消一个串。Length():返回当前串对象的长度。返回当前串对象的长度。Clear():置为空串。置为空串。Assign(S):串串S的值赋给当前串对象。的值赋给当前串对象。Concat(b):将串将串b连接在当前串对象之后。连接在当前串对象之后。DATA STRUCTURE4.4.1 字符串ADT Insert(P,i):将串将串P插在当前串对象的位置插在当前串对象的位置i处。处。Delete(i,len):从当前串对象的位置从当前串对象的位置i起删除起删除len个字符。个字符。Substr(i,len):返回当前串对象中，从

24、位置返回当前串对象中，从位置i开始的开始的len个字符组成的子串。个字符组成的子串。Find(i,P):返回子串返回子串P在当前串对象中的位置。若当前串在当前串对象中的位置。若当前串对象不包含串对象不包含串P，则返回，则返回-1。DATA STRUCTURE4.4.2 字符串的存储表示 v 串的顺序表示可用串的顺序表示可用C+的一维字符数组来描述。的一维字符数组来描述。#includechar s20=“cdabcde“；ABCIfirstfirstA B C DEF G HI0 DATA STRUCTURE4.4.2 字符串的存储表示#include class String public:

25、String();String(const char*p);String()delete str;int Find(int i,String&P);private:int n;/当前串长当前串长 char*str;/动态一维字符数组的指针动态一维字符数组的指针;String:String(const char*p)n=strlen(p);str=new charn+1;strcpy(str,p);DATA STRUCTURE4.4.2 字符串的存储表示v 函数原型函数原型:char*strdup(const char*s)函数功能:字符串拷贝，目的空间由该函数分配 函数返回:指向拷贝后的字符串

26、指针 v 函数原型函数原型:char*strcpy(char*str1,char*str2);函数功能:把str2指向的字符串拷贝到str1中去 函数返回:返回str1,即指向str1的指针 v 函数原型函数原型:char*strncpy(char*dest,const char*src，int count)函数功能:将字符串src中的count个字符拷贝到字符串dest中去 函数返回:指向dest的指针 v 函数原型函数原型:unsigned int strlen(char*str);函数功能:统计字符串str中字符的个数(不包括终止符0)函数返回:返回字符串的长度.DATA STRUCTU

27、RE4.4.2 字符串的存储表示v 函数原型函数原型:char*strchr(char*str,char ch);函数功能:找出str指向的字符串中第一次出现字符ch的位置 函数返回:返回指向该位置的指针,如找不到,则返回空指针 v 函数原型函数原型:char*strrchr(const char*s,int c)函数功能:得到字符串s中最后一个含有c字符的位置指针 函数返回:位置指针 v 函数原型函数原型:char*strstr(char*str1,char*str2);函数功能:找出str2字符串在str1字符串中第一次出现的位置(不包括str2的串结束符)函数返回:返回该位置的指针,如找

28、不到,返回空指针 v 函数原型函数原型:char*strpbrk(const char*s1,const char*s2)函数功能:得到s1中第一个“同时也出现在s2中”字符的位置指针 函数返回:位置指针 DATA STRUCTURE4.4.2 字符串的存储表示v 函数原型函数原型:char*strnset(char*s,int ch,size_t n)函数功能:将字符串s中前n个字符设置为ch的值 函数返回:指向s的指针 v 函数原型函数原型:char*strset(char*s,int ch)函数功能:将字符串s中所有字符设置为ch的值 函数返回:指向s的指针 v 函数原型函数原型:cha

29、r*strupr(char*s)函数功能:将字符串s中的字符变为大写 函数返回:指向s的指针 v 函数原型函数原型:char*strlwr(char*s)函数功能:将字符串中的字符变为小写字符 函数返回:指向s的指针 DATA STRUCTURE4.4.2 字符串的存储表示v 还有：还有：v int memcmp(const void*s1,const void*s2,size_t n)v int memicmp(const void*s1,const void*s2,size_t n)v void*memmove(void*dest,const void*src,size_t n)DATA STRUCTURE p.52 实现书上实现书上 程序程序4.1与与程序程序4.2一维数组类一维数组类（要求：（要求：增加拷贝构造函数，并在增加拷贝构造函数，并在main中增加适当测试代码）中增加适当测试代码）=v 文件名：文件名：D+D+学号后两位学号后两位+姓名姓名+布置作业日期布置作业日期v 例如例如 D01D01张三张三04220422 v 工程名：工程名：D+D+学号后两位学号后两位+姓名缩写姓名缩写+布置作业日期布置作业日期v 例如例如 D01ZS0422 D01ZS0422 v 最后把debug目录删除，打包按文件名发送v=作业0422