数据结构课件：04 第三章 数组和字符串[新]

1、第三章 数组和字符串3.1 数组3.2 矩阵3.3 字符串13.1 数组3.1.1 数组的存储和寻址3.1.2 自定义数组类3.1.3 动态数组2一维数组是若干个元素的有限序列。元素本身就是一个数据结构。一维数组的元素必须具有相同的类型，每个数组元素都占据相同大小的存储空间。3一维数组采用顺序存储结构。每个元素都通过一个下标来指定，故一个一维数组对应一个下标函数。一维数组An ，每个数组元素占一个存储单元（不妨设为C个连续字节）. 数组元素A0的首地址Loc(A0)，则对于0i n-1，有：Loc(Ai)=Loc(A0)+i*C 4高维数组可转化为一维数组计算元素的地址。高维数组有两种存放次序

2、：按行优先顺序和按列优先顺序。BASIC、PASCAL、C/C+等程序设计语言中，数组按行优先顺序存放；FORTRAN语言、Matlab语言中，数组则按列优先顺序存放。5按行优先顺序，就是将数组元素按行向量的顺序存储，第i+1个行向量存储在第i个行向量之后。二维数组的行优先存储 例 int x23 /*有23个数组元素*/ x00 x01 x02 x10 x11 x126按行优先顺序存放存储分配顺序为： x00 x01 x02 x10 x11 x12x00 x01x02x10 x11x127二维数组可以看作是一种特殊的一维数组。例 float a34; b0 a00 a01 a02 a03 b

3、- b1 a10 a11 a12 a13 b2 a20 a21 a22 a23 8二维数组amn中元素aij的地址：Loc(aij) = Loc(bi) +jCLoc(bi)=Loc(b0)+iC / C=nCLoc(aij)=Loc(a00)+inC+jC = Loc(a00) + (in+j) C b0 a00 a01 a02 a03 b- b1 a10 a11 a12 a13 b2 a20 a21 a22 a23 9例 float a34Loc(a12) = Loc(a00) +(in+j) C = Loc(a00) +(14+2) 4 = Loc(a00) +2410多维数组元素在内存

4、中的排序顺序为：第一维的下标变化最慢，最右边的维下标变化最快。 例 float a234三维数组a000a001a002a003a010a011a012a013a020a021a022a023a100a101a102a103 a110a111a112a113 a120a121a122a123 11三维数组amnp中元素aijk地址计算公式为： Loc(aijk)=Loc(a000)+(inp+jp+k)C12例 float D334Loc(D122) = Loc(D000)+(inp+jp+k)C = Loc(D000)+ (134+24+2)4 = Loc(D000)+ 8813 多维数组a

5、m1m2mn中ai1i2in的存储地址 14按列优先顺序，就是将数组元素按列向量的顺序存储，第i+1个列向量存储在第i个列向量之后。二维数组x23的按列优先存储 x00 x01 x02 x10 x11 x12x00 x10 x01x11x02x1215如果计算按列优先顺序存储的数组元素地址？请同学们自己推导。163.1 数组3.1.1 数组的存储和寻址3.1.2 自定义一维数组类3.1.3 动态数组17自定义一维数组类 数组类型是高级程序设计语言所提供的基本数据类型之一，可定义一组相同类型的元素。但是直接创建的数组存在着一些问题，诸如： 无法执行一些基本数组运算，如数组加法和数组减法等操作；

6、越界索引保护问题，即检查数组的下标索引值是否在0到arraysize-1范围内。一些高级程序设计语言对越界索引访问并不一定会产生异常，没有越界索引保护会直接给程序调试带来难以预料的困难。为了弥补这些缺陷，可以自定义一个数组类。18一维数组类Array的类定义template class Array private:int size ; / 数组的规模T *alist ; / 指向数组的第一个元素的指针public:Array ( int size = 0 ) ;/ 初始构造函数Array ( const Array & v ) ;/ 复制构造函数Array ( ) delete alist ;

7、 ;/ 析构函数19 int ArraySize ( ) return size ; / 返回数组大小T & operator ( int i ) const ;/ 重载下标符号Array & operator = ( const Array & v )/ 重载赋值运算符=Array operator + ( ) const ;/ 重载一元加法运算符+Array operator + ( const Array & v ) const ; / 重载二元加法运算符+Array operator - ( ) const ;/ 重载一元减法运算符-Array operator - ( const A

8、rray & v ) const ; / 重载二元减法运算符-；203.1 数组3.1.1 数组的存储和寻址3.1.2 自定义数组类3.1.3 动态数组21动态数组动态数组类 Array 的定义 template class Array private： int FSize; /数组的大小 T* alist; /指向数组的第一个元素的指针22 public： Array( int sz=50 ); Array( const Array & x ); /复制构造函数 Array( ) delete alist; int ListSize(void) const return Fsize; Arr

9、ay& operator= (const Array& x); T& operator (int i); void Resize(int NewSize); /重定义数组大小，保留原来元素;23 template / 修改数组的大小 void ArrayReSize(int newSize) if (newSize = 0) cerr“数组大小无效.”endl; return; if (newSize != Fsize) newArray = new TnewSize; if (newArray=0) cerr“内存分配异常.” endl; return; 24 int n=(newSize

10、= Fsize?newSsize:Fsize); for(int i=0;in;i+) newArrayi=alisti;/保留原数组中元素 delete alist; alist=newArray; FSize=newSize; 25例 编写一个函数，要求输入一个整数N，用动态数组A来存放2 N之间所有5或7的倍数，输出该数组。#include #include “array.h”void main( ) Array A(10); int N,count = 0; cinN; 26 for(int i=5;i=N;i+) if (i%5= =0|i%7= =0) Acount+=i; if

11、(count=A.ListSize( ) A.ReSize(count+10); for(int j=0;jcount;j+) coutAj“ ”; out : 5 7 10 14 15 20 21 25 28 3035 40 42 45 4950 out :N？ in: 5227第三章 数组和字符串3.1 数组3.2 矩阵3.3 字符串283.2 矩阵3.2.1 矩阵类3.2.2 特殊矩阵3.2.3 三元组表3.2.4 十字链表29 矩 阵 矩阵是常用的数据组织方式。计算机工作者关心的是矩阵在计算机中如何存储，以及如何实现矩阵的基本操作。 用二维数组存放矩阵，或者利用自定义的二维数组类声明矩

12、阵对象，存在以下问题：数组的基本操作是数组加减，而矩阵的基本操作还有矩阵相乘、矩阵转置等；数组的下标从0开始, 而矩阵的下标一般从1开始；数组元素用aij表示, 而矩阵元素通常用a(i,j)表示。 因此，用二维数组类型或者自定义的二维数组类所创建的矩阵实用性不强，鉴于此，有必要自定义一个矩阵类。303.2.1 矩阵的类定义和实现 templateclass Matrixprivate:int rows, cols; / 矩阵的行数和列数T *element; / 矩阵的元素public:Matrix(int r = 0, int c = 0); / 构造函数Matrix(const Matri

13、x& m); / 复制构造函数 Matrix() delete element; / 析构函数int Rows() const return rows; / 返回矩阵行数int Columns() const return cols; / 返回矩阵列数31T & operator() (int i, int j) const; / 重载下标操作符Matrix& operator = (const Matrix& m); / 重载赋值运算符Matrix operator + ( ) const; / 重载一元加法运算符Matrix operator + (const Matrix & m) co

14、nst; / 重载二元加法运算符Matrix operator - ( ) const; / 重载一元减法运算符Matrix operator - (const Matrix & m) const; / 重载二元减法运算符Matrix operator * (const Matrix & m) const; / 重载乘法运算符；32算法Multi-1(A, B, C, m, p, n) / 求矩阵的乘积FOR i=1 TO m DO FOR j=1 TO n DO ( cij 0 . FOR k=1 TO p DO . ) 重载乘法操作符对于矩阵Amp和Bpn的乘积Cmn ，其第i行第j列元素

15、cij的计算公式为33 用一维数组存放矩阵，随着矩阵元素行号或列号的变化，其在对应的一维数组的下标也要进行相应变换。设矩阵A和B分别按行优先存放在一维数组s和t中，aik是矩阵A中第i行第k列的元素，bkj是矩阵B中第k行第j列的元素，则ai(k+1)在s中的下标比aik在s中的下标多1，b(k+1)j在t中的下标比bkj在t中的下标多n .34算法Multi-2(s, t, w, m, p, n)/* Amp用一维数组s存放，Bpn用一维数组t存放，求A与B的乘积Cmn并用一维数组w存放 */M1. 初始化 cw0 . / 初始时cw是c11在一维数组w中的下标M2. 循环 FOR i=1

16、TO m DO / 第一层循环 (cs(i-1)p. / cs为ai1在一维数组s中的下标35FOR j1 TO n DO / 第二层循环 ( ctj-1. / 令ct为b1j在t中的下标 wcw0 . FOR k1 TO p DO / 第三层循环，叠加aikbkj 并存于wcw中，cw为cij在w中的下标 ( wcwwcwscstct. cscs1. / cs为A中本行下一列元素在s中的下标 ctctn.) / ct为B中本列下一行元素在t中的下标 cwcw1. ) ) 36分析：矩阵乘法算法中包含三层循环，所以其时间复杂性为O(mnp) . 373.2 矩阵3.2.1 矩阵类3.2.2 特

17、殊矩阵3.2.3 三元组表3.2.4 十字链表381、对角矩阵的压缩存储nn维方阵M是对角矩阵，则对 i j (1 i , j n)，都有M(i, j)=0，即非对角线上的元素均为0 . 对于一个nn维对角矩阵，至多只有n个非零元素，因此只需存储其n个对角元素的信息。采用一维数组dn来压缩存储对角矩阵，其中di存储Mi,i的值。 392、三角矩阵的压缩存储三角矩阵分为上三角矩阵和下三角矩阵。方阵M是上对角矩阵，当且仅当ij时有M(i, j)=0 . 方阵M是下对角矩阵，当且仅当ij时有M(i, j)=0 . 50 15 35 25 0 10 20 60 0 0 30 10 0 0 0 4050

18、 0 0 015 10 0 035 20 30 0 25 60 10 4040以下三角矩阵为例，讨论其压缩存储方法。考虑一个nn维下三角矩阵，其第一行有1个非零元素，第二行有2个非零元素，第n行有n个非零元素，非零元素共有(1+2+n) = n(n+1)/2个。可以用大小为n(n+1)/2的一维数组来存储下三角矩阵，即把下三角矩阵M的非零元素映射到一个一维数组d中。映射次序可采用按行优先或按列优先。假设映射采取按行优先，非零元素M(i,j)会映射到一维数组d中的哪个元素？41设元素M(i,j)前面有k个元素，可以计算出 k =1+2+ (i-1) + (j-1)= i(i-1)/2 + (j-

19、1)设一维数组d的下标是从0开始，则M(i,j)映射到d中所对应的元素是dk . 有了k的计算公式，可以很容易实现下三角矩阵的压缩存储。 423、对称矩阵的压缩存储方阵Mnn是对称矩阵，当且仅当对于任何1 i, j n，均有M(i, j) = M(j, i) . 因为对称矩阵中M(i, j)与M(j, i)的信息相同，所以只需存储M的上三角部分或下三角部分的元素信息。43参照下三角矩阵的压缩存储方法，即用大小为n(n+1)/2的一维数组来存储，对于对称矩阵中的下三角矩阵元素M(i, j) (ij) ，和下三角矩阵压缩存储的映射公式一样，映射到dk (其中k = i(i-1)/2+(j-1) )

20、；对称矩阵中的上三角矩阵元素M(i, j)， 因其元素值与下三角中的M(j,i)相同，故映射到dq (其中q=j(j-1)/2+(i-1). 有了k和q的计算公式，即可实现对称矩阵的压缩存储。 444、稀疏矩阵的压缩存储 定义：设矩阵Amn中非零元素的个数远远小于零元素的个数，则称 A 为稀疏矩阵。 特点：零元素的分布没有规律。 作用：解决空间浪费的问题。45对于矩阵Amn 的每个元素aij，知道其行号i和列号j，就可以确定该元素在矩阵中的位置。因此，如果用一个结点来存储一个非零元素的话，那么该结点可以设计如下： ijaij46由三个域（行号、列号和元素值）构成的结点被称为三元组结点：矩阵的每

21、个非零元素可由一个三元组结点（i，j，aij）唯一确定。如何在三元组结点的基础上实现对整个稀疏矩阵的存储？用顺序存储方式实现的三元组表链接存储方式实现的十字链表。 473.2 矩阵3.2.1 矩阵类3.2.2 特殊矩阵3.2.3 三元组表3.2.4 十字链表48三元组表将表示稀疏矩阵的非零元素的三元组结点按行优先的顺序排列，得到一个线性表，将此线性表用顺序存储结构存储起来，称之为三元组表。 49 50 0 0 0 10 0 20 0 0 0 0 0 30 0 60 5AB0B1B2B3B4B50021501333-6020-301035020例 稀疏矩阵三元组表50 template / 三元

22、组的结点类 class Trituple firend class SparseMatrix; private: int row,col; / 非零元素的行号、列号 T value; / 非零元素的值 ; 稀疏矩阵类的声明51 class SparseMatrix private: / 稀疏矩阵的行数、列数及非零元素个数 int Rows,Cols,Count; int MaxTerm; / 存储三元组表的数组 Trituple smArrayMaxTerm; template / 稀疏矩阵类的声明52public: / 建立一个稀疏矩阵 SparseMatrix( int Mrows,int

23、 Mcols); / 求转置矩阵 SparseMatrix Transpose( ); /矩阵的其它运算 / 求矩阵的和 SparseMatrix Add (SparseMatrix b); / 求矩阵的乘积 SparseMatrix Multiply (SparseMatrix b); ; 53 50 10 0 -30 0 0 0 0 0 20 0 -60 0 0 0 5A例 稀疏矩阵 50 0 0 0 10 0 20 0 0 0 0 0 -30 0 -60 5A转置矩阵54 50 10 0 -30 0 0 0 0 0 20 0 -60 0 0 0 5A例 稀疏矩阵的三元组表示 50 0 0

24、 0 10 0 20 0 0 0 0 0 -30 0 -60 5Aa0a1a2a3a4a500502120011033523-6003-30b0b1b2b3b4b5005030-30101033532-60122055算法Transpose (a, b) / 已知矩阵A存放在三元组表a中，求A的转置矩阵并将其保存在三元组表b中 T1. 初始化 j0. / 首先考察三元组表b的第一个结点b0T2. a为空？ IF count 0 THEN/ 若a非空，开始确定bj中存放的非零元素的行号、列号、非零元素值 ( FOR k0 TO n-1 DO / 对每个列号k FOR i0 TO count-1

25、DO /依次扫描a中列号为k的元素 56 b0b1b2b3b4b5005030-30101033532-601220a0a1a2a3a4a500502120011033523-6003-30IF (col( ai )k THEN ( row(bj)k. / 该元素在b中的行号为k col(bj)row(ai). /在b中的列号为其在a中的行号 value( bj )value( ai ).) jj1. ) / 考察三元组表b中的下一个结点 57对于用三元组表存储的稀疏矩阵Amn，若矩阵非零元素个数为t，求Amn的转置矩阵的时间复杂性是多少呢？观察Transpose函数不难发现，函数中包含双重循

26、环，第一重循环是对转置矩阵A按行优先依次确认非零元素，故循环次数为A的行数n；第二重循环是扫描原矩阵的三元组表，执行次数是矩阵非零元素个数t，显然，求转置矩阵的时间复杂性为O(nt) .能否找到时间复杂性为O(n+t)的算法呢？（课后作业） 583.2 矩阵3.2.1 矩阵类3.2.2 特殊矩阵3.2.3 三元组表3.2.4 十字链表59LEFTUPROWCOLVAL 800070900004060043214321十字链表矩阵的元素结构如下：分别表示该元素的左邻非零元素、上邻非零元素、所在的行、所在的列和它的值。例：稀疏矩阵60 矩阵的每一行、每一列都设置为由一个表头结点引导的循环链表，并且

27、各行和各列的表头结点有如下特点： -1 = COL（Loc（BASEROWi） 0 -1 = ROW（Loc（BASECOLj）s1和couts2等。71class String private:char *str; / 指向动态申请的字符串首地址的指针int size; / 字符串的长度+1，多出一个字节以存放字符串尾部的结束符 0public:String ( char *s = “” ); / 构造函数String ( const String &s ); / 复制构造函数String (void); / 析构函数char & operator (int n); / 下标运算符重载Str

28、ing & operator = (const String & s); / 赋值运算符重载把String对象赋值给当前对象String & operator = (const char * s); / 赋值运算符重载把一个C+串赋值给当前对象/ 各种关系运算符的重载，如“= =”, “!=”, “”等 自定义字符串类String72/ 串拼接运算符重载String & operator + (const String & s) const; / 将当前对象与一个String拼接String & operator + (const char * s) const; / 将当前对象与一个C+串拼

29、接friend String operator + (char * str, const String & s); / 将C+串与String串拼接/ 串函数int Find (char c, int start) const; / 从start位置开始找字符cint FindLast (char c) const; / 返回字符c最后出现的位置String Substr (int index, int count); / 取子串 void Insert (const String & s, int index); / 在index位置插入一个String串void Insert ( char

30、 * s, int index); / 向当前对象的index位置插入一个C+串void Remove ( int index, int count);/ 删除子串operator char * (void) const; / 将String串转换成C+串friend ostream & operator (istream & istr, String & s); / 输入运算符重载intLength (void) const;int IsEmpty (void) const;void Clear (void);73(1) 构造函数，申请内存并将一个C+串复制给当前对象String:Strin

31、g ( char * s)size = strlen(s); / 串的长度str = new char size+1; / 为串申请空间if (str = = NULL) / 若申请失败，退出程序 cout“outofMemory” endl; exit(1); strcpy(str, s); / 将c+串s复制到str;字符串类部分函数的实现74(2)赋值运算符重载把一个String对象赋值给当前对象String & String: operator = (const String & s)/*若s的长度与当前对象长度不符，则删除当前对象所占空间，重新申请内存空间*/if (s.size !

32、= size)delete str;str = new chars.size+1;if (str = = NULL) / 若申请空间失败，则退出 cout“outofMemory” endl; exit(1); size = s.size;strcpy(str, s.str); / 将s复制到当前对象return *this;75(3)拼接运算符重载string+stringString String: operator + (const String & s) const String temp; / 创建一个临时串tempdelete temp.str; / 释放创建temp时所申请的空间

33、int len = size + s.size;temp.str = new charlen+1; / 为存放拼接串申请空间if (temp.str = = NULL) / 若申请空间失败，则退出 cout“outofMemory” = size ) / 若index大于串长return temp; / 返回空串if ( count charleft ) / 若count大于剩下的字符数，则子串取剩下的字符count = charleft;delete temp.str; / 释放创建temp时产生的空串temp.str = new charcount + 1; / 为子串动态申请空间if (

34、 temp.str = = NULL)/ 若申请失败，则返回 cout“outofMemory” endl; exit(1); 77 char *p = temp.str; / 令字符指针p指向暂无内容的字符数组temp.str的首字符处char *q = &strindex; / 令字符指针q指向当前对象的str数组下标index处for ( int i =0; i = size ) / start超过串长 cout“start位置无效” endl; exit(1); int i = start;while ( stri != 0 & stri != c ) i +; / 查找字符c，若当前

35、对象中没有字符c，则循环在串尾结束if ( stri = = 0 ) / 未找到字符c，则返回-1return -1;return i; / 否则，返回字符c在当前对象中的位置792、串的链式存储：串的链接存储是把可用的存储空间分成一系列大小相同的结点，其中每个结点的结构为： （str, link）5chinap 结点大小为4的链串Sc5hian 结点大小为1的链串80算法SI（S , T, i . S)/*S和T是两个链式串,算法SI将串T插到串S的第 i 个字符之后;串S和T之元素有两个域sym和link，sym域之值为字符， link域存放指向下一结点的指针，串S和T之首结点的sym域之

36、值为串长 */SI1.初始化L1STR(S). L2 STR(T). IF (iL1) THEN (PRINTString Length error. RETURN )IF L2=0 THEN RETURN. IF L1=0 THEN ( S T. RETURN )81STRI2寻找插入位置 P S. j 0.WHILE ( j i ) DO( P LINK(P). j j+1 )STRI3插入 T1 LINK(T). SAVE LINK(P).LINK(P) T1.WHILE LINK(T1) =NULL DOT1 LINK(T1). /*T1指向串的尾部结点*/LINK(T1) SAVE.STR(S) L1+L2. 823.3 字符串3.3.1字符串的定义和实现3.3.2 模式匹配算法83在目标串中寻找模式串出现的首位置； 给定两个字符串S和P，其中目标S有n个字符，模式P有m个字符，m=n。从S的第一个字符开始，搜索模式P，如果找到，返回模式P的第一个字符在S中的位置；如果没找到（即S中不包含P），则返回-1 。 例：S= “abaaabab”, P = “abab” 1、 模式匹配问题定义84模式匹配的应用 - 文本编辑器中常用的“查找”、“替换” - 搜索引擎中的关键