数据结构课件：第3章 数组和字符串

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

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

3、 b2 a20 a21 a22 a23 二维数组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 例 float a34Loc(a12) = Loc(a00) +(in+j) C = Loc(a00) +(14+2) 4 = Loc(a00) +24多维数组元素在内存中的排序顺序为：第一维的下标变化最慢，最右边的维

4、下标变化最快。 例 float a234三维数组a000a001a002a003a010a011a012a013a020a021a022a023a100a101a102a103 a110a111a112a113 a120a121a122a123 三维数组Amnp中数组元素aijk地址计算公式为： Loc(aijk)=Loc(a000)+i*n*p*C+j*p*C+k*C按列优先顺序，就是将数组元素按列向量的顺序存储，第i+1个列向量存储在第i个列向量之后。二维数组x23的按列优先存储 x00 x01 x02 x10 x11 x12x00 x10 x01x11x02x123.1 数组3.1.1

5、数组的存储和寻址3.1.2 动态数组动态数组动态数组类 Array 的定义 template class Array private： int FSize; /数组的大小 T* alist; /指向数组的第一个元素的指针 public： Array( int sz=50 ); Array( const Array & x ); /复制构造函数 Array( ) delete alist; int ListSize(void) const return Fsize; Array& operator= (const Array& x); T& operator (int i); void Resi

6、ze(int NewSize);/重新定义数组的大小; template / 修改数组的大小 void ArrayReSize(int newSize) if (newSize = 0) cerr“数组大小无效.”endl; return; if (newSize != Fsize) newArray = new TnewSize; if (newArray=0) cerr“内存分配异常.” endl; return; int n=(newSize = Fsize?newSsize:Fsize); for(int i=0;in;i+) newArrayi=alisti;/保留原数组中元素 de

7、lete alist; alist=newArray; FSize=newSize; 例 编写一个函数，要求输入一个整数N，用动态数组A来存放2 N之间所有5或7的倍数，输出该数组。#include #include “array.h”void main( ) Array A(10); int N,count = 0; cinN; for(int i=5;i=N;i+) if (i%5= =0|i%7= =0) Acount+=i; if (count=A.ListSize( ) A.ReSize(count+10); for(int j=0;jcount;j+) coutAj“ ”; if(

8、j+1) % 5=0) coutj时有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 0 0 015 10 0 035 20 30 0 25 60 10 40以下三角矩阵为例，讨论其压缩存储方法。考虑一个nn维下三角矩阵，其第一行有1个非零元素，第二行有2个非零元素，第n行有n个非零元素，非零元素共有(1+2+n) = n(n+1)/2个。可以用大小为n(n+1)/2的一维数组来存储下三角矩阵，即把下三角矩阵M的非零元素映射到一个一维数组d中。映射次序可采用按行优先或按列

9、优先。假设映射采取按行优先，非零元素M(i,j)会映射到一维数组d中的哪个元素？设元素M(i,j)前面有k个元素，可以计算出 k =1+2+ (i-1) + (j-1)= i(i-1)/2 + (j-1)设一维数组d的下标是从0开始，则M(i,j)映射到d中所对应的元素是dk . 有了k的计算公式，可以很容易实现下三角矩阵的压缩存储。 3、对称矩阵的压缩存储方阵Mnn是对称矩阵，当且仅当对于任何1 i, j n，均有M(i, j) = M(j, i) . 因为对称矩阵中M(i, j)与M(j, i)的信息相同，所以只需存储M的上三角部分或下三角部分的元素信息。参照下三角矩阵的压缩存储方法，即用

10、大小为n(n+1)/2的一维数组来存储，对于对称矩阵中的下三角矩阵元素M(i, j) (ij) ，和下三角矩阵压缩存储的映射公式一样，映射到dk (其中k = i(i-1)/2+(j-1) )；对称矩阵中的上三角矩阵元素M(i, j)， 因其元素值与下三角中的M(j,i)相同，故映射到dq (其中q=j(j-1)/2+(i-1). 有了k和q的计算公式，即可实现对称矩阵的压缩存储。 4、稀疏矩阵的压缩存储 定义：设矩阵Amn中非零元素的个数远远小于零元素的个数，则称 A 为稀疏矩阵。 特点：零元素的分布没有规律。 作用：解决空间浪费的问题。对于矩阵Amn 的每个元素aij，知道其行号i和列号j

11、，就可以确定该元素在矩阵中的位置。因此，如果用一个结点来存储一个非零元素的话，那么该结点可以设计如下： ijaij由三个域（行号、列号和元素值）构成的结点被称为三元组结点：矩阵的每个非零元素可由一个三元组结点（i，j，aij）唯一确定。如何在三元组结点的基础上实现对整个稀疏矩阵的存储？用顺序存储方式实现的三元组表链接存储方式实现的十字链表。 3.2 矩阵3.2.1 特殊矩阵3.2.2 三元组表3.2.3 十字链表三元组表将表示稀疏矩阵的非零元素的三元组结点按行优先的顺序排列，得到一个线性表，将此线性表用顺序存储结构存储起来，称之为三元组表。 50 0 0 0 10 0 20 0 0 0 0 0

12、 30 0 60 5AB0B1B2B3B4B50021501333-6020-301035020例 稀疏矩阵三元组表 template / 三元组的结点类 class Trituple firend class SparseMatrix; private: int row,col; / 非零元素的行号、列号 T value; / 非零元素的值 ; 稀疏矩阵类的声明 class SparseMatrix private: / 稀疏矩阵的行数、列数及非零元素个数 int Rows,Cols,Count; int MaxTerm; / 存储三元组表的数组 Trituple smArrayMaxTer

13、m; template / 稀疏矩阵类的声明public: / 建立一个稀疏矩阵 SparseMatrix( int Mrows,int Mcols); / 求转置矩阵 SparseMatrix Transpose( ); /矩阵的其它运算 / 求矩阵的和 SparseMatrix Add (SparseMatrix b); / 求矩阵的乘积 SparseMatrix Multiply (SparseMatrix b); ; 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

14、转置矩阵 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 5Aa0a1a2a3a4a500502120011033523-6003-30b0b1b2b3b4b5005030-30101033532-601220算法Transpose (a, b) 描述：假设稀疏矩阵存储在一个三元组表 a 中, 且 A 的非零元素个数为count, Transpose求A的转置矩阵并将其保存在三元组表b中. 算法的主要思想：针对每个列号k(k0, 1, , n1), 对a进行扫描,

15、考察a中是否有列号为k的结点, 若有记为au (假定au在a中的行号为i), 将au依次(可能列号为k的结点不止一个)保存在b的bw中, 则row(bw)k, col(bw) i, val(bw) val(au). 算法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 D

16、O /依次扫描a中列号为k的元素 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中的下一个结点 对于用三元组表存储的稀疏矩阵Amn，若矩阵非零元素个数为t，求Amn的转置矩阵的时间复杂性是多少呢？观察Transpose函数不难发现，函数中包含双重循环，第一重循

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

18、= ROW（Loc（BASECOLj） 0第三章 数组和字符串3.1 数组3.2 矩阵3.3 字符串3.3 字符串3.3.1字符串的定义和实现3.3.2 模式匹配算法串的定义：串是由零个或多个字符顺序排列组成的有限序列。如字符串 S 可记作： Sa0a1 an-1S是串名，引号中的字符序列是串值，字符个数n是串长度。 空串：长度为零的串称为空串。 空白串：由一个或多个空格组成的串称为空白串。 3.3.1 字符串的定义和实现子串：若把某个串称为主串，则主串中任意个连续的字符组成的子序列被称为子串。子串在主串中第一次出现时，其首字符在主串中的序号被称为该子串在主串中的位置。例 A = This i

19、s a string B = is 子串B = is在主串中的位置是3 1、串的顺序存储：把一个串所包含的字符序列相继存入连续的字节中 (1) 非紧缩格式 : 一个存储单元存放一个字符 例 S a0a1 an-1 a0a1an-1Word0Word1Wordn-1字符串的存储方式(2) 紧缩格式 : 一个存储单元存放多个字符 例 S= a0a1 an-1 / 一个存储单元存放4个字符 a1a4an-1Word0Word1a0a2a3a5a6a7an-2Word n/4 -12、串的链式存储：串的链接存储是把可用的存储空间分成一系列大小相同的结点，其中每个结点的结构为： （str, link）5

20、chinap 结点大小为4的链串Sc5hian 结点大小为1的链串class String private:char *str; / 指向动态申请的字符串首地址的指针int size; / 字符串的长度+1，多出一个字节以存放字符串尾部的结束符 0public:String ( char *s = “” ); / 构造函数String ( const String &s ); / 复制构造函数String (void); / 析构函数char & operator (int n); / 下标运算符重载String & operator = (const String & s); / 赋值运算符

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

22、tring & 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 * 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);3.3 字符串3.3.1字符串的定义和实现3.3.2 模式