第4章 数组、字符串与广义表.ppt

1、第4章 数组、字符串与广义表（4课时）,数组这种数据结构可以看成是线性表的推广，几乎所有的高级程序设计语言都支持这种数据结构。科学计算中涉及到大量的矩阵运算，在高级语言编程时，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。当矩阵规模很大且具有特殊结构时，如对角矩阵、三角矩阵、对称矩阵、稀疏矩阵等，为减少程序的时间和空间需求，一般需要对这类矩阵进行压缩存储。在非数值处理、事务处理等问题中要大量使用字符串，字符串的逻辑结构是一种由字符构成的线性表，但字符串与一般线性表的操作有所不同。广义表也是线性表的推广和扩充，具有广泛的应用价值，特别是在人工智能领域。本章主要介绍数组、矩阵、

2、字符串和广义表的特性和存储表示等相关知识。,4.1 数组与矩阵,本节先介绍数组的特性和基本操作，并给出一维和二维数组的表示和实现；然后介绍矩阵的特性和基本操作，并给出矩阵的表示和实现方法；最后介绍特殊矩阵的压缩存储处理方法。,4.1.1 数组及数组的抽象数据类型,1. 什么是数组 数组可以看成是形如（index,value）的数据集合，其中，index是元素的索引，表示数据的逻辑位置，任意两个数据的index都不相同；value表示数据元素的值。元素的索引index由一个因素构成的数组是一维数组。如果数组元素的索引由多个因素构成，这样的数组就是多维数组。很多问题都可以抽象成数组这样的数据结构。

3、 【例4-1】一维数组实例。下面关于学生编号和姓名的问题可用一维数组表示。 (1,安华)，(2,李响),（3,刘晓）,(4,张肖) 由于每一个元素的值（姓名）都仅由一个因素“编号”就可以唯一确定，所以，这个问题可以用一维数组表示。假设用A来描述这个一维数组，数组中的元素为ai，i=1,2,n。其中，i称为元素的下标，n是一维数组的长度。对于【例4-1】，n=4，则数组A的逻辑关系如图4-1所示。,4.1.1 数组及数组的抽象数据类型,【例4-2】二维数组实例。下面关于各班级的学生编号和姓名的问题可用二维数组表示。 （1班,1,梁冰),（1班,2,李小天),（2班,1,张爽）,(2班,2,徐成城

4、) （3班,1,江涛）,(3班,2,郭敏敏) 由于每一个元素的值（姓名）都需要由两个因素“班级”和“编号”才能唯一确定，所以，这个问题可以用二维数组表示。可以将二维数组直观地看成是一个定长的一维数组，它的每个元素又是一个定长的一维数组。 假设用A来描述这个二维数组，首先将数组A看成是以某一因素为索引的一个一维数组，数组元素为Ai，i=1,2,m，其中，i称为元素的下标，m称为一维数组的长度。每一个元素Ai又是以另一个因素为索引的一维数组，数组元素为aij，i=1,2,m;j=1,2,n,其中，i和m同上；j是第2个下标，n是第2个下标的长度。,4.1.1 数组及数组的抽象数据类型,对于【例4-

5、2】，如果将数组A看成是以“班级”为索引的一维数组，则m=3，数组元素分别是A1,A2,A3。他们又分别是以“编号”为索引的一维数组，则n=2，数组元素分别为A1=（a11,a12）,A2=(a21,a22),A3=(a31,a32)。二维数组A的逻辑关系如图4-2(a)所示。 如果将数组A看成是以“编号”为索引的一维数组，则m=2，数组元素分别是A1、A2。他们又分别是以“班级”为索引的一维数组，n=3，数组元素分别为A1=（a11,a21,a31）,A2=（a21,a22,a32）。二维数组A的逻辑关系如图4-2(b)所示。,4.1.1 数组及数组的抽象数据类型,从图4-2中可以看出，对于

6、同一个二维数组问题，可以采用按行或按列的方式来组织数组。图4-2（a）中，数组A的数据元素Ai构成了一个行向量。图4-2（b）中，数组A的数据元素Ai构成了一个列向量。 n（n3）维数组的情况类似，即每个数据元素都受到n维关系的约束。在此不再赘述。,4.1.1 数组及数组的抽象数据类型,2. 数组在计算机中的存储 数组一般都是采用顺序存储的方法来表示。采用顺序方法表示数组时，每个元素的存储地址可以通过简单的线性函数计算出来，因此，可以对数组元素进行随机存取。 计算机的内存结构是一维地址结构，对于多维数组，将其存放(映射)到内存一维结构时，需要由数组元素的索引值来确定该元素在内存中的位置，以便实

7、现相应的读写操作。多维数组在计算机中有两种映射：行映射和列映射。 行映射：左边下标变化最慢，右边下标变化最快，右边下标变化一轮，与之相邻的左边下标才变化一次。 列映射：右边下标变化最慢，左边下标变化最快，左边下标变化一轮，与之相邻的右边下标才变化一次。,4.1.1 数组及数组的抽象数据类型,以二维数组为例，假设二维数组A的数据元素为aij，则： 按行优先顺序存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 设数组在内存开始存放的地址为 LOC(a11)，每个元素占用 d 个存储单元，则下标为i、j的元素aij的存储地址为： LOC(aij) = LOC

8、(a11)+(i-1)*n*d+(j-1)*d 按列优先顺序存储的线性序列为： a11,a21,am1,a12,a22,am2,an1,an2,anm 设数组在内存中存放的起始地址为 LOC(a11)，每个元素占用d个存储单元，则下标为i、j的元素aij的存储地址为： LOC(aij) = LOC(a11)+(j-1)*m*d+(i-1)*d,4.1.1 数组及数组的抽象数据类型,3. 数组的特点 数组具有如下特点： 数组中所有数据元素的数据类型相同。 可按元素的索引直接存储和访问数组元素。 数组中的数据元素个数固定不变。,4.1.1 数组及数组的抽象数据类型,4. 数组的基本操作 数组一般需

9、要进行下面的基本操作： 创建一个不含任何元素的空数组 删除数组 将索引为index的数组元素赋值为value 返回索引为index的数据元素值value 数组赋值 输出数组 提示：数组与线性表的不同之处在于数组可以按元素的索引直接存储和访问数组元素。所以，数组可以看成是线性表的一种推广。多维数组又是一维数组的推广，多维数组是一种非线性结构，其特点是每一个数据元素可以有多个直接前驱和多个直接后继。由于数组元素的下标具有固定的下界和上界，因此多维数组又比其他复杂的非线性结构简单。,5. 数组的抽象数据类型 由于抽象数据类型与数组元素的类型无关，所以下面的元素类型用T来表示， T当然也可以是数组。根

10、据数组的特点及其基本操作，数组的抽象数据类型Array定义如下： ADT Array 数据对象D=ei|ei是形如(index,value)的数据对，valueT, i=1,2,n，n=1 数据关系R=index|indexiindexj 当ij，i、j=1,2,3,n 基本操作P： Create()：创建一个空数组 Delete()：删除数组 Store(index,value)：将索引为index的数组元素赋值为value Retrieve(index)：返回索引为index的数据元素值value =：数组赋值 void OutPut()：输出数组 ADT Array,4.1.2 一维数组

11、和二维数组的表示及实现,虽然C+支持一维数组、二维数组及多维数组，但它无法保证数组下标的合法性，也没有提供数组的输入、输出以及简单的操作（如数组赋值）等。为了方便数组的应用，克服C+数组的不足，将数组的数据和基本操作进行封装，为一维数组和二维数组分别设计了ArrayOneD类和ArrayTwoD类。为了与C+中数组的下标从0开始相一致，数组类ArrayOneD和ArrayTwoD的下标也从0开始。,4.1.2 一维数组和二维数组的表示及实现,1.一维数组的表示及实现 下面这个描述是为一维数组定义的ArrayOneD类，该类的每个实例A都是一个一维数组。Element存放数组元素，size存放数

12、组元素个数，第i个数组元素位于A.element i，其中，0isize。构造函数、拷贝构造函数用于实现创建数组的操作，析构函数用于实现删除数组的操作。重载下标运算符“”用于实现根据索引（下标）index直接存储和访问数组元素，用来实现抽象数据类型中的Store(index,value)和Retrieve(index)操作。例如为数组的第i个元素（A.element i）赋值w，可以直接使用下标运算符Ai=w。重载了赋值运算符“=”是为了实现数组之间进行赋值的操作，例如有数组A和数组B，可以进行A=B的赋值运算。成员函数ReSize()能够实现重新为数组分配内存空间，并调整数组长度的操作。,【

13、描述4-1】一维数组类模板的C+描述。 #include #include using namespace std; template class ArrayOneD public: ArrayOneD(int sz=0);/构造函数，创建一维数组 ArrayOneD(const ArrayOneD 提示：【描述4-1】不可能穷举所有数组应用问题的全部操作。读者可根据不同问题的需要为数组添加相应的操作。例如，对于实数数组，经常要进行加、减、乘、除操作，可根据需要重载+、-、*、/等运算符。,4.1.2 一维数组和二维数组的表示及实现,【描述4-2】一维数组基本操作的实现。 /实现构造函数 te

14、mplate ArrayOneD:ArrayOneD(int sz) assert(sz=0);/下标检查 size=sz; element=new Tsz; /实现拷贝构造函数 template ArrayOneD:ArrayOneD(const ArrayOneD ,4.1.2 一维数组和二维数组的表示及实现,/实现析构函数 template ArrayOneD:ArrayOneD() delete element; /取索引是index的元素，实现赋值和取值 template T ,4.1.2 一维数组和二维数组的表示及实现,/实现重载赋值运算符 template ArrayOneD ,

15、4.1.2 一维数组和二维数组的表示及实现,/实现取数组长度 template int ArrayOneD:Length() return size; /实现重新设置数组长度 template void ArrayOneD:ReSize(int sz) delete element; assert(sz=0); size = sz; element = new Tsize; ,4.1.2 一维数组和二维数组的表示及实现,/实现一维数组的输出 template void ArrayOneD: OutPut(ostream ,4.1.2 一维数组和二维数组的表示及实现,提示：C/C+语言对数组下标

16、不进行有效性检查，即超出下标范围引用数组元素（数组越界）也是“合法”的。有的时候，数组越界是一种很危险的行为。因此，在ArrayOneD类中，使用assert宏对数组下标进行有效性检查。assert宏定义在中。 同样，将【描述4-1】关于一维数组类模板的声明代码和【描述4-2】关于一维数组类模板的实现代码一起存储在ArrayOneD.h文件中，以后就可以基于该类模板快速完成一维数组的相关应用问题的求解。,【例4-3】一维数组类ArrayOneD简单应用实例。设数组元素的类型为char型，编写代码，测试ArrayOneD类。 /*TestArrayOneD.cpp 测试一维数组类ArrayOne

17、D*/ #include using namespace std; #include ArrayOneD.h int main() ArrayOneD A(10);/声明一个有个元素的一维数组A for(int i=0;i B(A);/调用拷贝构造函数由数组A创建数组B ArrayOneD C;/声明一个空的一维数组 C=A;/调用数组赋值运算符=，用数组A给数组C赋值 coutA;/输出数组A coutB;/输出数组B coutC;/输出数组C coutC.Length()endl;/输出数组C的长度 C.ReSize(15);/重新为数组C的分配空间 coutC.Length()endl;

18、/输出新数组C的长度 提示：这个实例测试了ArrayOneD类的每一个函数，请读者自己给出程序的运行结果。读者在以后遇到一维数组的应用问题时，可参考这个实例中的关于数组的声明和函数调用的方法。,4.1.2 一维数组和二维数组的表示及实现,2.二维数组的表示及实现 二维数组可看成是一维数组的集合。在为二维数组设计的ArrayTwoD类中，使用一维数组row来直接存储二维数组的每个行数组，即rowi是类型为ArrayOneD的一维数组，它代表二维数组的第i行。 【描述4-3】二维数组类模板的C+描述。 #include #include #include ArrayOneD.h using nam

19、espace std; template ,class ArrayTwoD public: ArrayTwoD(int rsz=0,int csz=0);/构造函数，创建二维数组 ArrayTwoD(const ArrayTwoD,提示：可根据实际需要为二维数组添加其他操作。 实现构造函数的算法 在实现构造函数时，使用语句：“row=new ArrayOneDrsize;”，创建一个具有rsize个元素的一维数组row，元素的数据类型都是一维数组ArrayOneD。在创建数组row时，创建每个元素rowi都会调用ArrayOneD类的缺省构造函数，因此，rowi是一个具有缺省大小（为0）的一维

20、数组，0irsize。为了使rowi具有csize个元素，需循环执行“rowi.Resize(csize)”，依次调整row中每个一维数组的大小。 实现下标运算符的算法 在实现取下标运算符“”时，使用语句“return rowi;”，返回的是一维数组row的第i个元素（0irsize），即rowi。由于rowi本身又是ArrayOneD类型的，可以继续使用ArrayOneD的下标运算符“”，即直接使用rowij来访问一维数组rowi的第j个元素(0jcsize)。所以，对于二维数组A，直接使用Aij就可以访问二维数组的任意一个元素（0irsize，0jcsize）。,4.1.2 一维数组和二维

21、数组的表示及实现,【描述4-4】二维数组基本操作的实现。 /实现构造函数 template ArrayTwoD:ArrayTwoD(int rsz,int csz) assert(rsz=0 ,4.1.2 一维数组和二维数组的表示及实现,/实现拷贝构造函数 template ArrayTwoD:ArrayTwoD(const ArrayTwoD ,4.1.2 一维数组和二维数组的表示及实现,/实现析构函数 template ArrayTwoD:ArrayTwoD() delete row; /实现下标运算符 template ArrayOneD ,4.1.2 一维数组和二维数组的表示及实现,/

22、实现重载赋值运算符 template ArrayTwoD ,4.1.2 一维数组和二维数组的表示及实现,/实现取数组的行数 template int ArrayTwoD:Rows() return rsize; /实现取数组的列数 template int ArrayTwoD:Columns() return csize; ,4.1.2 一维数组和二维数组的表示及实现,/实现二维数组的输出 template void ArrayTwoD: OutPut(ostream ,提示：同样，将【描述4-3】和【描述4-4】关于二维数组类模板的代码一起存储在ArrayTwoD.h文件中，以后就可以基于该

23、类模板快速完成二维数组的相关应用问题的求解。注意，ArrayTwoD.h文件包含一维数组类模板文件ArrayOneD.h。,4.1.2 一维数组和二维数组的表示及实现,【例4-4】二维数组类ArrayTwoD简单应用实例。设二维数组元素的类型为int型，编写代码，测试ArrayTwoD类。 参考程序如下： /*TestArrayTwoD.cpp测试二维数组类ArrayTwoD*/ #include using namespace std; #include ArrayTwoD.h int main() ArrayTwoD A(4,5);/声明行列二维数组A for(int i=0;i B(A)

24、;/调用拷贝构造函数由数组A创建数组B ArrayTwoD C;/声明一个空的二维数组 C=A;/调用赋值运算符=,4.1.2 一维数组和二维数组的表示及实现,coutA;/输出数组A coutB;/输出数组B coutC;/输出数组C coutC.Rows()endl;/输出数组C的行数 coutC.Columns()endl;/输出数组C的列数 提示：这个实例测试了ArrayTwoD类的每一个函数，请读者自己给出程序的运行结果。读者在以后遇到二维数组的应用问题时，可参考这个实例中的数组声明和函数调用的方法。,4.1.3 矩阵的定义与操作,科学与工程计算问题都离不开矩阵。矩阵是指纵横排列的二

25、维数据表格。图4-3所示的是一个4行5列的矩阵。m行n列的矩阵记为Amn。矩阵Amn中每个元素A(i,j)受到两个线性表的约束，即第i行的线性表和第j列的线性表。在高级语言编程时，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。,图4-3 一个45矩阵,4.1.3 矩阵的定义与操作,矩阵常见的操作包括： 矩阵的转置 一个mn的矩阵A的转置是一个nm的矩阵AT。矩阵与其转置矩阵的关系：,矩阵相加 当两个矩阵具有相同的行数和列数时才可以相加。两个mn的矩阵A和B相加，结果矩阵C也是mn的矩阵，并且：,4.1.3 矩阵的定义与操作,矩阵相减 当两个矩阵具有相同的行数和列数时才可以相

26、减。两个mn的矩阵A和B相减，结果矩阵C也是mn的矩阵，并且：,矩阵相乘 一个mn的矩阵和一个np的矩阵才可以相乘，即第一个矩阵的列数与第二个矩阵的行数必须相等。mn的矩阵A和np的矩阵B相乘，结果矩阵C是一个mp的矩阵，并且：,4.1.4 矩阵的表示与实现,矩阵通常被描述成一个二维数组。不过，矩阵的索引通常从1而不是像数组那样从0开始，并且是使用A(i,j)而不是Aij的形式来引用矩阵中的元素。为了更好地描述矩阵及矩阵的操作，下面设计了一个矩阵类Matrix。在Matrix类中，用rsize和csize记录矩阵的行数和列数，用一个一维数组element来存储矩阵中的rsizecsize个元素

27、，并且各行和各列的索引值都是从1开始的；使用运算符“（）”来引用每个元素，因此重载了括号运算符“（）”；次外，还重载了赋值运算符“=”，并以友元的形式重载了矩阵的基本运算“+”、“*”和矩阵转置操作“Transpose”。,4.1.4 矩阵的表示与实现,【描述4-5】矩阵类模板的C+描述。 #include using namespace std; template class Matrix public: Matrix(int rsz=1,int csz=1);/构造函数，创建矩阵 Matrix(const Matrix/取矩阵的列数,4.1.4 矩阵的表示与实现,template frie

28、nd Matrix operator+(const Matrix /矩阵相减，友元函数,4.1.4 矩阵的表示与实现,template friendMatrix Transpose(const Matrix 提示：矩阵还有一些其他运算，如一个数与矩阵相乘以及矩阵的其他复杂运算。读者可根据不同问题的需要为矩阵添加相应的操作。注意，在类模板中声明友元函数时，需要在函数头前面加“templatefriend”。,4.1.4 矩阵的表示与实现,【描述4-6】矩阵基本操作的实现。 /实现构造函数 template Matrix:Matrix(int rsz,int csz) rsize=rsz; csi

29、ze=csz; element=new Trsize*csize; ,4.1.4 矩阵的表示与实现,/实现拷贝构造函数 template Matrix:Matrix(const Matrix ,4.1.4 矩阵的表示与实现,/实现下标运算符，方便矩阵元素的赋值和取值 template T ,4.1.4 矩阵的表示与实现,/实现重载赋值运算符 template Matrix ,4.1.4 矩阵的表示与实现,/实现取矩阵行数 template int Matrix:Rows() return rsize; /实现取矩阵列数 template int Matrix:Columns() return

30、csize; ,4.1.4 矩阵的表示与实现,/实现矩阵相加 template Matrix operator+(const Matrix ,4.1.4 矩阵的表示与实现,/实现矩阵相减 template Matrix operator-(const Matrix ,4.1.4 矩阵的表示与实现,/实现矩阵相乘 template Matrix operator*(const Matrix ,4.1.4 矩阵的表示与实现,/实现矩阵转置 template Matrix Transpose(const Matrix ,4.1.4 矩阵的表示与实现,/实现一维数组的输出 template void

31、Matrix: OutPut(ostream ,4.1.4 矩阵的表示与实现,/重载插入运算符 ostream 提示：将【描述4-5】和【描述4-6】关于矩阵类模板的代码一起存储在Matrix.h文件中，以后就可以基于该类模板快速完成矩阵的相关应用问题的求解。,【例4-5】矩阵类Matrix简单应用实例。设矩阵元素的类型为float型，编写代码，测试Matrix类。 /*TestMatrix.cpp 测试矩阵类Matrix*/ #include using namespace std; #include Matrix.h int main() Matrix A(4,5),B(4,5),C(5,

32、4); /声明矩阵A45，B45，C54 for(int i=1;i=A.Rows();i+) for(int j=1;j=A.Columns();j+) A(i,j)=(float)0.1*i; /调用下标运算符（）为矩阵A的元素赋值 B(i,j)=(float)0.3*j; /调用下标运算符（）为矩阵B的元素赋值 C(j,i)=(float)0.5*i*j; /调用下标运算符（）为矩阵C的元素赋值 ,4.1.4 矩阵的表示与实现,cout D;/声明空矩阵D D=A+B;/调用运算符+和运算符= coutDendl;/将矩阵A和B的和输出 D=A*C;/调用运算符*和运算符= coutDe

33、ndl;/将矩阵A和C的乘积输出 D=Transpose(A);/调用转置操作函数Transpos和赋值运算符= coutDendl;/输出矩阵A的转置矩阵 return 0; 提示：这个实例测试了Matix类的每一个函数，请读者自己给出程序的运行结果。读者在以后遇到Matrix的应用问题时，可参考这个实例中关于矩阵声明和函数调用的方法。,4.1.5 特殊矩阵与稀疏矩阵,用顺序存储的方法表示矩阵，其存储密度高，并且由于可以随机存储，矩阵元素的存取速度很快。对于一些特殊形态的矩阵，还可以对他们的存储方式进行改进，以便减少存储空间。,4.1.5 特殊矩阵与稀疏矩阵,用顺序存储的方法表示矩阵，其存储

34、密度高，并且由于可以随机存储，矩阵元素的存取速度很快。对于一些特殊形态的矩阵，还可以对他们的存储方式进行改进，以便减少存储空间。 1. 特殊矩阵 当矩阵中的大多数元素为0，且非0元素的分布具有一定的规律时，可以根据具体情况采用节省空间的顺序存储结构。,方阵是指具有相同行数和列数的矩阵。常用的特殊形式的方阵有： 对角矩阵：M是一个对角矩阵当且仅当ij时有M(i, j) = 0。如图4-4(a)所示。 三对角矩阵：M是一个三对角矩阵当且仅当|i-j|1时有M(i, j) = 0。如图4-4(b)所示。 下三角矩阵：M是一个下三角矩阵当且仅当ij时有M(i, j) = 0。如图4-4(d)所示。 对

35、称矩阵：M是一个对称矩阵当且仅当对于所有的i和j有M(i, j) = M(j, i)。如图4-4(e)所示。,4.1.5 特殊矩阵与稀疏矩阵,（1）对角矩阵的顺序表示 由于一个对角矩阵M最多包含n个非0元素，所以可以采用一个长度为n的一维数组m来描述对角矩阵： 对角矩阵M的元素M(i, j)与一维数组元素mi的对应关系为：,（2）三对角矩阵的顺序表示 在一个nn三对角矩阵M中，非0元素排列在如下的三条对角线上： 1）主对角线（i=j）。 2）主对角线之下的对角线（i=j+1）。 3）主对角线之上的对角线（i=j-1）。 这三条对角线上的元素总数为3n-2。因此可以使用一长度为3n-2的一维数组

36、m来描述三对角矩阵M。 元素的顺序有三种方式：把对角线上的元素逐行映射到m中；把对角线上的元素逐列映射到m中；或者按照对角线的次序（从最下面的对角线开始）进行映射。假设是以第3种方式存储三对角矩阵，则三对角矩阵M的元素M(i, j)与一维数组元素mi的对应关系为：,（3）三角矩阵的顺序表示 无论是上三角矩阵还是下三角矩阵，矩阵的非0元素的总数为n(n+1)/2。因此可以使用一长度为n(n+1)/2的一维数组m来描述三角矩阵M。 在一维数组m中存储三角矩阵的非零元素，可采用按行和按列两种不同的映射方式。假设存储的是下三角矩阵，并且按行映射的方式存储，则三角矩阵M的元素M(i, j)与一维数组元素

37、mi的对应关系为：,（4）对称矩阵的顺序表示 一个nn的对称矩阵可以用一个大小为n(n+1)/2的一维数组来描述，只需要存储矩阵的上三角或下三角。可以根据M(i, j)=M(j, i)，由已存储的元素来推算出未存储的元素。 提示：特殊矩阵的设计留给感兴趣的读者自己练习完成。 对于对角矩阵、三对角矩阵或是三角矩阵等特殊矩阵，由于其非0元素的分布都是有规律的，所以总能找到一种方法将它们压缩存储到一个一维数组中，并且能找到矩阵中的元素与该数组的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。,4.1.5 特殊矩阵与稀疏矩阵,2. 稀疏矩阵 如果一个矩阵中非零元素个数远远少于矩阵元素个数，则该矩

38、阵就是稀疏矩阵。非稀疏矩阵被称为稠密矩阵，稀疏矩阵和稠密矩阵之间并没有一个精确的界限。一个mn的矩阵M有s个非零元素，设=s/(nm)，则称为稀疏因子。一般地，如果某一矩阵的稀疏因子满足0.05，则称该矩阵为稀疏矩阵。 对于对角矩阵、三对角矩阵或是三角矩阵，由于非0元素的分布具有一定的规律性，可以采用上面的方法用顺序存储的方式来表示。,4.1.5 特殊矩阵与稀疏矩阵,下面介绍的是具有不规则非0区域的稀疏矩阵表示问题。为了节省空间，如果只存储稀疏矩阵的非0元素，很难保持用顺序表示时所具有的随机存取矩阵元素的优点。存储稀疏矩阵的方法有很多，下面介绍三元组表示法、伪地址法和链接表示法。 三元组表示法

39、 三元组表示法是用一个一维数组来表示稀疏矩阵。数组中每个元素都是一个表示稀疏矩阵中非0元素的三元组，分别是非0元素的行下标、列下标和值，可以采用按行映射或按列映射的方式存储。图4-5是稀疏矩阵三元组表示法示意图，图中采用的是按行映射的方式来存储左边的稀疏矩阵中非0元素的值。,4.1.5 特殊矩阵与稀疏矩阵,在三元组表示法中，设k是稀疏矩阵非0元素的个数，在一维数组需要增加2k个存储单元来存储非0元素的行下标和列下标。但由于不需要存储大量的0元素，所以，这种表示法仍然能够大量地节省存储空间。,图4-5 稀疏矩阵的三元组表示,4.1.5 特殊矩阵与稀疏矩阵,三元组表示法由于是顺序存储，行下标i和列

40、下标j是递增排列，因此可以将ij拼接成一个整数，作为关键字，例如，11、14、33、42、45分别是图4-5所示矩阵中5个非0元素的关键字。可用二分查找法查找一维数组中的ij，从而找到稀疏矩阵的第i行第j列非0元素的值。例如，将稀疏矩阵M用一维数组m表示，m中的每一个元素是一个三元组（行下标，列下标，数值），只存放非0元素。假设行下标为i、列下标为j的非0元素值用mij来表示。稀疏矩阵M的元素M(i, j)与一维数组元素mij的对应关系为：,4.1.5 特殊矩阵与稀疏矩阵,三元组表示法的缺点是矩阵的修改不方便。当矩阵中一个非0元素的值变成0，或者一个原来值为0的元素变成非0，就需要对一维数组进

41、行插入或删除操作。为了维护表中元素的有序性以便进行二分查找，与线性表的插入删除操作一样、需要移动元素。 提示：一个算法和一种存储结构是紧密结合的，如上面的二分查找法是为了提高顺序表的查找速度。二分查找法将在第8章中介绍。,伪地址表示法 在三元组表示法的基础上，为了进一步节省稀疏矩阵的存储空间，可以采用伪地址表示法。设mn的矩阵M，则元素M(i, j)的伪地址为(i-1)n+j。伪地址表示法是用一个一维数组来表示稀疏矩阵，数组中每个元素包括两个字段，分别是矩阵中非0元素的伪地址和值，可以采用按行映射或按列映射的方式存储。图4-6是图4-5中稀疏矩阵的按行映射方式存储的伪地址表示。 设k是稀疏矩阵

42、非0元素的个数，伪地址表示法比三元组表示法节省k个存储空间，但在存储和查找矩阵元素时需要根据元素的下标计算伪地址。伪地址表示法同样可以将伪地址作为关键字进行二分查找，它的缺点与三元组表示法的缺点相同。,图4-6 稀疏矩阵的伪地址表示,4.1.5 特殊矩阵与稀疏矩阵,链接表示法 用顺序存储的一维数组来描述稀疏矩阵除了有当进行插入/删除操作时需要移动元素的问题，还存在另一个缺点：当创建一个一维数组时，必须知道稀疏矩阵中的非0元素总数，而且，随着矩阵各种操作的执行，非0元素的数目会发生变化。因此如果数组初始的长度太长，会浪费很多空间。当然可以随时根据实际非0元素的数目，重新分配一个新的数组，然后从老

43、数组中把元素复制出来并删除老数组。但是这种额外工作将降低算法的效率。,4.1.5 特殊矩阵与稀疏矩阵,链接表示法是解决上述问题的一种方法。这种方法需要额外的指针域来表示元素之间的逻辑关系，基于指针的操作可以避免存储的再分配以及部分结果的复制等额外操作。图4-7所示的是图4-5中稀疏矩阵的一种链接表示法。它是把每行的非0元素链接在一起，构成一个链表。链接表示法包含两类链表：一个是链接一行非0元素的链表，此处称为行链表；另一个是将所有行链表链接在一起的链表，此处称为头结点链表。 行链表中的每一个结点都有三个域：非0元素所在列号（col）、非0元素的值（data）和指向同行的下一个非零元素的指针（n

44、ext）。只有当矩阵某行中至少包含一个非0元素时才会为该行创建一个行链表。在行链表中，每个结点按其col值的升序顺序排列。,4.1.5 特殊矩阵与稀疏矩阵,头结点链表中的每一个结点是一个行链表的头结点，它也有三个域：行链表的行号(row)、指向下一个头结点的指针（next）和指向行链表第一个数据结点的指针（first）。各结点按其row值的升序排列，空的头结点链表代表矩阵所有元素都为0。 整个稀疏矩阵的链表用指针Head指向。,图4-7 稀疏矩阵的链表表示,4.1.5 特殊矩阵与稀疏矩阵,提示：上面比较简单直观地讨论了稀疏矩阵的顺序存储和链接存储方法，但没有给出相应存储结构下的基本操作的实现算

45、法。感兴趣的读者可以自己练习完成。 通过对稀疏矩阵表示方法的介绍，读者应该对数据结构和算法的时间代价和空间代价有了一定的认识。时间代价和空间代价往往是互相关联的，对于同一个问题，提高处理速度一般会导致需要存储更多的有利于提高计算速度的信息；反之，节省存储空间开销一般会造成处理速度上的损失。因此，在选择什么样的数据结构和相应的算法时，需要根据计算机的资源情况和求解问题的特点来确定。,4.2 字符串,日常生活中大量的非数值计算问题要使用字符串。字符串的逻辑结构是一种由字符构成的线性表，但由于字符串的特殊性，字符串与线性表的基本操作有许多不同。下面介绍字符串的抽象数据类型、基本操作及其算法实现以及字

46、符串的匹配算法。,4.2.1 字符串的抽象数据类型,1. 字符串的基本概念 字符串是日常生活中最常见的一种数据类型，例如，学生的姓名和学号、学校或各单位的名称、国家名称、一篇文章、一个高级语言源程序等，都可归结为字符串。 字符串简称串，它是一种以字符为元素的特殊线性表。一个字符串记为s=s1s2sn，其中，s是字符串的名称；si（1in）是组成字符串的字符，可以是字母字符、数字字符、汉字或其他字符；双引号括起来的字符序列是串值；n是字符串的长度。长度为0的字符串称为空串，空串不包含任何字符，也不含空白字符，空串用s=来表示。,4.2.1 字符串的抽象数据类型,如果在一个字符串s1中取一部分作生

47、成为一个新字符串s2，则s2称为s1的子串，s1称为s2的主串。空串是任意串的子串，任意串是它本身的子串。子串在主串中的位置是指该子串的第一个字符在主串中的位置，子串在主串中的位置可能有多个。两个字符串相等的充要条件是两个字符串互为子串，即他们的长度相等并且各对应位置上的字符也相同。 字符串一般要进行下面的基本操作： 创建一个新的空串 由已知字符串创建一个新串 删除字符串 判断是否为空串 求字符串长度 两个字符串拼接成一个新串 求子串的位置 判断两个字符串是否相等 输出字符串,2.字符串的抽象数据类型 根据字符串的性质和基本操作，下面给出字符串的抽象数据类型： ADT String 数据对象D

48、= si|siT, i=1,2,n，n0 数据关系R=|si-1，siD, i=2,3,n 基本操作P： Create():创建一个空串 Create(str)：由一个字符串常量str创建一个值为str的串 Delete()：删除一个字符串 IsEmpty ():判断字符串是否是空串 Length()：求字符串的长度 StrCat(t)：将串t连接到当前串的尾部 SubStr (pos, len, sub)：从第pos个字符起取长度为len的子串放到sub中 =str: 判断当前字符串与str是否相等 index(str): 如果str是当前字符串的子串，则返回它在串中第一次出现的位置；否则返

49、回0 void OutPut() const：输出串 ADT String,4.2.1 字符串的抽象数据类型,提示：字符串也有与线性表相似的操作，如字符的插入、删除等运算。由于本节主要讨论的是字符串，所以在此略去。字符串的一些其他的操作，在此也不一一列举了，读者可根据实际应用问题的需要自己添加。 使用字符型数组进行字符串的处理比较困难，因为通常在实现字符串的操作时会使用指针。事实上，C+标准程序库中提供了一个string类，专门用来处理字符串操作。使用string类来操作字符串比之前使用char*字符串或字符型数组就要方便很多，不必考虑存储字符串所需内存尺寸等问题。标准C+中提供的string

50、类的功能非常强大，一般都能满足开发项目时对字符串处理的需求。读者可以把string类看成是C+的一个基本数据类型，能像处理普通变量那样处理字符串。使用string类时，必须在程序中包含头文件string（注意不是string.h）。,4.2.2 字符串的表示及实现,1.字符串的顺序表示及实现 字符串的顺序表示是用一组连续的存储单元来存放字符串中的字符序列，简称顺序串。顺序串可直接使用定长的字符数组来定义，顺序串的基本操作都是基于数组的操作，比较容易理解。下面将字符串类命名为LinearString。,4.2.2 字符串的表示及实现,【描述4-7】顺序串的类及基本操作的C+描述。 class L

51、inearString public: LinearString(int LSMaxSize=100);/构造函数，创建空串 LinearString(const char *str); /由字符串常量str创建串的构造函数 LinearString(const LinearString/输出字符串,4.2.2 字符串的表示及实现,private: int length; int MaxSize; char *string; /一维数组 ; /实现创建空串的构造函数 LinearString:LinearString(int LSMaxSize) MaxSize=LSMaxSize; stri

52、ng=new charLSMaxSize; length=0; ,4.2.2 字符串的表示及实现,/实现构造函数 LinearString:LinearString(const char* str) int len=0; while(strlen)len+;/计算字符串常量str的长度 MaxSize=len; length=len; string=new charlen; for(int i=0;ilen;i+) stringi=stri; ,4.2.2 字符串的表示及实现,/实现拷贝构造函数 LinearString:LinearString(const LinearString ,4.2

53、.2 字符串的表示及实现,/实现判断是否为空串 bool LinearString:IsEmpty() const return length=0; /实现求串的长度 int LinearString:Length() const return length; ,4.2.2 字符串的表示及实现,/实现将串t连接到串后形成新串 bool LinearString:StrCat(const LinearString ,4.2.2 字符串的表示及实现,/实现求从第pos个字符起长度为len的子串 bool LinearString:SubStr(int pos,int len,LinearStrin

54、g ,4.2.2 字符串的表示及实现,/实现判断串是否与str相等 bool LinearString:operator=(const LinearString ,4.2.2 字符串的表示及实现,/实现如果str是的子串，返回它在串中第一次出现的位置，不是子串则返回 int LinearString:index(const LinearString ,4.2.2 字符串的表示及实现,/实现顺序串的输出 void LinearString: OutPut(ostream ,4.2.2 字符串的表示及实现,2.字符串的链接表示及实现 链式存储的字符串称为链接串，它与线性链表的存储类似，每一个结点也

55、包含数据域和指针域，在数据域存放字符，指针域中存放指向下一结点的指针。 在结点的数据域中，可存放的字符个数称为结点的大小。如果每个结点仅存放一个字符，则结点的指针域就非常多，造成存储空间的浪费。为节省存储空间，可考虑字符串结构的特殊性，在每个结点中存放多字符，这种结构称为块链结构。但是一个块(结点)内存放多个字符时，当进行插入或删除字符操作时，通常需要在块间移动字符，会使操作过程变得较为复杂。所以，需要根据问题来权衡时间开销和空间开销。假设有字符串“abcdefg”，图4-8示意了带头结点、单向，结点大小为1的链接串结构和结点大小为3的链块结构。,4.2.2 字符串的表示及实现,图4-8 不同

56、链接串结构示意图,下面使用带头结点的单向链表来表示字符串，每个结点仅存储一个字符。为了便于计算和理解，在链接串类中声明了用来表示字符串长度的数据成员length，和将字符串清空的成员函数Delete()。 【描述4-8】链接串存储结点类StrNode、链接串类LinkString及基本操作的C+描述。 /*存储结点类*/ class StrNode friend class LinkString;/将链接串声明为结点类的友类 public: StrNode()/构造函数 next=NULL; private: char data;/存放字符 StrNode *next;/指向下一个字符 ;,4

57、.2.2 字符串的表示及实现,/*链接串类*/ class LinkString public: LinkString();/构造函数，创建空串 LinkString(const char *str);/由字符串常量str创建串的构造函数 LinkString(const LinkString/将串t连接到串后形成新串,4.2.2 字符串的表示及实现,bool SubStr(int pos,int len,LinkString ,4.2.2 字符串的表示及实现,/实现创建空串的构造函数 LinkString:LinkString() head=new StrNode();/创建头结点 leng

58、th=0; ,/实现构造函数 LinkString:LinkString(const char* str) StrNode *p,*q; int i=0; head=new StrNode();/创建头结点 p=head; while(stri) q=new StrNode();/q指向新结点 q-data=stri;/向数据域赋值 p-next=q;/新结点入链 p=q;/p指向最后一个节点 i+; length=i;/设置链的长度 ,/实现拷贝构造函数 LinkString:LinkString(const LinkString ,4.2.2 字符串的表示及实现,/实现析构函数 LinkString:LinkString() StrNode *p,*q; p=head-next; for(int i=0;inext;/指向下一结点 delete q;/删除结点 ,4.2.2 字符串的表示及实现,/实现判断是否为空串 bool LinkString:IsEmpty() const return length=0; /实现求串的长度 int LinkString:Length() const return length; ,4.2.2 字符串的表示及实现,/实现置空串函数 void LinkString:Delete