1、第4章 串和数组主要内容 4.1 串的基本概念、抽象描述和分类 4.2 串的模式匹配 4.3 数组的概念、特性、遍历 4.4 特殊矩阵的压缩存储 总结4.14.1串的基本概念、抽象描述串的基本概念、抽象描述和分类和分类字符串也叫串，是由字符组成的有限序列，是一种常用的非数值数据。串的逻辑结字符串也叫串，是由字符组成的有限序列，是一种常用的非数值数据。串的逻辑结构是线性表，串是一种特殊的线性表，其每个数据元素都是一个字符。但是串的操构是线性表，串是一种特殊的线性表，其每个数据元素都是一个字符。但是串的操作特点与线性表不同，主要是对子串进行操作，通常采用顺序存储结构存储。作特点与线性表不同，主要是
2、对子串进行操作，通常采用顺序存储结构存储。字符串可以表示为字符串可以表示为str=a0a1aian-1str=a0a1aian-1，其中，其中strstr为串名，也叫串变量；为串名，也叫串变量；i i为字为字符符aiai在串中的位序号；在串中的位序号；双引号中的字符序列称为串值；双引号中的字符序列称为串值；n n为串的长度；为串的长度；当当n=0n=0时时字符串不包含任何字符，为空串；字符串不包含任何字符，为空串；当字符串由一个或多个空白字符组成时为空白当字符串由一个或多个空白字符组成时为空白串。串。4.1.1 4.1.1 串的基本概念串的基本概念4.1.1 4.1.1 串的基本概念串的基本概
3、念字符串中任意个连续字符组成的子序列称为字符串的子串，此字符串为该子串的字符串中任意个连续字符组成的子序列称为字符串的子串，此字符串为该子串的主串。子串在主串中的位置是指子串在主串中第一次出现时的第一个字符在主串主串。子串在主串中的位置是指子串在主串中第一次出现时的第一个字符在主串中的位置。空串是任意串的子串，每个字符串都是其自身的子串，除自身外，主中的位置。空串是任意串的子串，每个字符串都是其自身的子串，除自身外，主串的其他子串称为主串的真子串。串的其他子串称为主串的真子串。串的比较规则和字符的比较规则有关，字符的比较规则由所属的字符集的编码决串的比较规则和字符的比较规则有关，字符的比较规则
4、由所属的字符集的编码决定。两个串相等是指串长度相同并且各对应位置上的字符也相同。两个串的大小定。两个串相等是指串长度相同并且各对应位置上的字符也相同。两个串的大小由对应位置上的首个不同字符的大小决定，字符比较次序是从头开始依次向后。由对应位置上的首个不同字符的大小决定，字符比较次序是从头开始依次向后。当两个串的长度不等而对应位置上的字符都相同时较长的串定义为较大。当两个串的长度不等而对应位置上的字符都相同时较长的串定义为较大。4.1.2 4.1.2 串的串的抽象数据类型描述抽象数据类型描述字符串是数据元素类型为字字符串是数据元素类型为字符的线性表，其抽象数据类符的线性表，其抽象数据类型描述与线
5、性表相似，又根型描述与线性表相似，又根据串在实际问题中的应用抽据串在实际问题中的应用抽象出串的基本操作，可得串象出串的基本操作，可得串的抽象数据类型的抽象数据类型Python语言语言描述如左边所示。描述如左边所示。4.1.2 4.1.2 串的串的抽象数据类型描述抽象数据类型描述字符串的抽象数据类型字符串的抽象数据类型Python抽象类包含了串的主抽象类包含了串的主要基本操作，如果要使用这要基本操作，如果要使用这个接口，还需要具体的类来个接口，还需要具体的类来实现。串的实现。串的Python抽象类的抽象类的实现方法主要有以下两种：实现方法主要有以下两种：(1)基于顺序存储的实现，基于顺序存储的实
6、现，为顺序串；为顺序串；(2)基于链式存储的实现，基于链式存储的实现，为链串为链串。4.1.3 4.1.3 顺序串顺序串1.1.顺序串的描述：顺序串的描述：顺序串与顺序表的逻辑结构相同，存储结构类似，均可用数组来存储数据元素。顺序串与顺序表的逻辑结构相同，存储结构类似，均可用数组来存储数据元素。但串具有独特的不同于线性表的操作，属于特殊类型的线性表。但串具有独特的不同于线性表的操作，属于特殊类型的线性表。下下图所示为顺序图所示为顺序串。串。4.1.3 4.1.3 顺序串顺序串实现实现IString抽象类的顺序串类的抽象类的顺序串类的Python语言描述如下：语言描述如下：4.1.3 4.1.3
7、 顺序串顺序串 2.顺序串基本操作的实现顺序串基本操作的实现 顺序串顺序串有许多基本操作，例如，求子串操作、插入操作、删除操作、连接操作、有许多基本操作，例如，求子串操作、插入操作、删除操作、连接操作、比较操作。比较操作。下面，我们对这几个操作逐个使用下面，我们对这几个操作逐个使用Python实现。实现。4.1.3 4.1.3 顺序串顺序串求子串操作求子串操作subString(begin,end)是返是返回长度为回长度为n的字符串中位序号从的字符串中位序号从begin到到end-1的字符序列，其中的字符序列，其中0beginn-1，beginendn。其主要步骤如下：。其主要步骤如下：(1)
8、检查参数检查参数begin和和end是否满足是否满足0beginn-1和和beginendn，若不满，若不满足，抛出异常。足，抛出异常。(2)返回位序号为返回位序号为begin到到end-1的字的字符序列。符序列。代码如左图所示代码如左图所示1)求子串操作求子串操作4.1.3 4.1.3 顺序串顺序串插入操作插入操作insert(i,str)是在长度为是在长度为n的的字符串的第字符串的第i个元素之前插入串个元素之前插入串str，其，其中中0in。其主要步骤如下：。其主要步骤如下：(1)判断参数判断参数i是否满足是否满足0in，若不，若不满足，则抛出异常。满足，则抛出异常。(2)重新分配存储空间
9、为重新分配存储空间为n+m，m为为插入的字符串插入的字符串str的长度。的长度。(3)将第将第i个及之后的数据元素向后移个及之后的数据元素向后移动动m个存储单元。个存储单元。(4)将将str插入到字符串从插入到字符串从i开始的位置。开始的位置。2)插入操作插入操作4.1.3 4.1.3 顺序串顺序串删除操作删除操作delete(begin,end)是将长度是将长度为为n的字符串的位序号为的字符串的位序号为begin到到end-1的元素删除，其中参数的元素删除，其中参数begin和和end满满足足 0 b e g i n c u r L e n-1 和和beginendcurLen。其主要步骤如
10、下：。其主要步骤如下：(1)判断参数判断参数begin和和end是否满足是否满足0begincurLen-1和和begin end curLen，若不满足，则抛出异常。，若不满足，则抛出异常。(2)将字符串位序号为将字符串位序号为end的数据元的数据元素及其之后的数据元素向前移动到位素及其之后的数据元素向前移动到位序号为序号为begin的位置。的位置。(3)字符串长度减小字符串长度减小end-begin。3)删除操作删除操作4.1.3 4.1.3 顺序串顺序串4)concat(str)是将串是将串str插入到字符串插入到字符串的尾部，此时调用的尾部，此时调用insert(curLen,str)
11、即即可实现。可实现。5)比较操作比较操作compareTo(str)是将字符是将字符串与串串与串str按照字典序进行比较。若当按照字典序进行比较。若当前字符串较大，返回前字符串较大，返回1；若相等，返回若相等，返回0。若当前字符串较小，返回。若当前字符串较小，返回-1。其主。其主要步骤如下：要步骤如下：(1)确定需要比较的字符的个数确定需要比较的字符的个数n为为两个字符串长度的较小值。两个字符串长度的较小值。(2)从下标从下标0至至n-1依次进行比较。依次进行比较。4)连接操作连接操作5)比较操作比较操作4.1.3 4.1.3 顺序串顺序串【例例4.1】编写一个程序，完成构造串、判断串是否为空
12、、返回串的长度、求子串编写一个程序，完成构造串、判断串是否为空、返回串的长度、求子串等操作。等操作。示例答案：示例答案：4.1.4 4.1.4 链串链串链串的描述：链串的描述：链串采用链式存储结构，和线性表的链式存储结构类似，可以采用单链表存储串值。链串由一系列大小相同的结点组成，每个结点用数据域存放字符，指针域存放指向下一个结点的指针。与线性表不同的是每个结点的数据域可以是一个字符或者多个字符。若每个结点的数据域为一个字符，这种链表称为单字符链表；若每个结点的数据域为多个字符，则称为块链表。在块链表中每个结点的数据域不一定被字符占满，可通过添加空字符或者其他非串值字符来简化操作。如图所示为两
13、种不同类型的链串。4.1.4 4.1.4 链串链串链串的优缺点：链串的优缺点：在串的链式存储结构中，单字符链表的插入、删除操作较为简单，但存储效率低。块链表虽然存在串的链式存储结构中，单字符链表的插入、删除操作较为简单，但存储效率低。块链表虽然存储效率较高但插入、删除操作需要移动字符，较为复杂。此外，与顺序串相比，链串需要从头部储效率较高但插入、删除操作需要移动字符，较为复杂。此外，与顺序串相比，链串需要从头部开始遍历才能访问某个位置的元素。开始遍历才能访问某个位置的元素。所以用户在应用中需要根据实际情况选择合适的存储结构。所以用户在应用中需要根据实际情况选择合适的存储结构。4.24.2串的模
14、式匹配串的模式匹配4.2 4.2 串的模式匹配串的模式匹配串的模式匹配也叫查找定位，串的模式匹配也叫查找定位，指的是在当前串中寻找模式指的是在当前串中寻找模式串的过程，主要的模式匹配串的过程，主要的模式匹配算法有算法有Brute ForceBrute Force算法和算法和KMPKMP算法。算法。4.2.1 Brute Force 4.2.1 Brute Force 算法算法Brute ForceBrute Force算法从主串的第一个算法从主串的第一个字符开始和模式串的第一个字符进字符开始和模式串的第一个字符进行比较，若相等，则继续比较后续行比较，若相等，则继续比较后续字符；字符；否则从主串
15、的第二个字符否则从主串的第二个字符开始重新和模式串进行比较。依此开始重新和模式串进行比较。依此类推，直到模式串的每个字符依次类推，直到模式串的每个字符依次与主串的字符相等，匹配成功。与主串的字符相等，匹配成功。4.2.1 Brute Force 4.2.1 Brute Force 算法算法Brute ForceBrute Force算法的实现简单，但效率非常低。算法的实现简单，但效率非常低。m m为模式串的长度，为模式串的长度，n n为主串的长度。为主串的长度。（1 1）最好情况：最好情况：第一次匹配即成功，比较次数为模式串的长度第一次匹配即成功，比较次数为模式串的长度m m，时间复杂度为，时
16、间复杂度为O(m)O(m)。（2 2）最坏情况：最坏情况：每次匹配比较至模式串的最后一个字符，并且比较了目标串中所有长度为每次匹配比较至模式串的最后一个字符，并且比较了目标串中所有长度为m m的子串，的子串，此时的时间复杂度为此时的时间复杂度为O(mO(mn)n)。缺点缺点：每次匹配没有利用前一次匹配的比较结果，使算法中存在较多的重复比较，降低了算法的效率；：每次匹配没有利用前一次匹配的比较结果，使算法中存在较多的重复比较，降低了算法的效率；如果利用部分字符匹配的结果，可将算法的效率提高。因此提出了如果利用部分字符匹配的结果，可将算法的效率提高。因此提出了KMPKMP算法，在下一节进行介绍。算
17、法，在下一节进行介绍。4.2.2 KMP 4.2.2 KMP 算法算法1.1.算法分析算法分析设主串为设主串为s=aba bcabdabcabcas=aba bcabdabcabca、模式串为、模式串为p=abcabcp=abcabc，指针，指针i i、j j分别指示主串和模分别指示主串和模式串所比较字符的位序号。当某次匹配不成功时有式串所比较字符的位序号。当某次匹配不成功时有sipjsipj，并且，并且si-jsi-j+1si-si-jsi-j+1si-1=p0p1pj-11=p0p1pj-1。此时需要寻找前缀子串。此时需要寻找前缀子串p0p1pk-1=pj-kpj-k+1pj-1p0p1p
18、k-1=pj-kpj-k+1pj-1，其中，其中0kj0kj，这时候即满足这时候即满足si-ksi-k+1si-1=p0p1pk-1si-ksi-k+1si-1=p0p1pk-1，下一次匹配可直接比较，下一次匹配可直接比较sisi和和pkpk。此外，。此外，为了减少比较次数，为了减少比较次数，k k应取最大值，即应取最大值，即p0p1pk-1p0p1pk-1应为满足此性质的最长前缀子串。若应为满足此性质的最长前缀子串。若k k不存在，下一次匹配则直接比较不存在，下一次匹配则直接比较sisi和和p0p0。4.2.2 KMP 4.2.2 KMP 算法算法2.K2.K值的计算值的计算通过前面的分析已
19、知，每次模式串开始比较的位置（即通过前面的分析已知，每次模式串开始比较的位置（即k k的值）仅与模式串本身有关。一般用的值）仅与模式串本身有关。一般用nextjnextj来来表示表示pjpj对应的对应的k k值。值。初始时可定义初始时可定义next0=-1next0=-1，next1=0next1=0。设设nextj=knextj=k，则，则p0p1pk-1=pj-kpj-k+1pj-1p0p1pk-1=pj-kpj-k+1pj-1，k k为满足等式的最大值。计算为满足等式的最大值。计算nextj+1nextj+1的值。的值。(1)(1)若若pk=pjpk=pj，则存在，则存在p0p1pk-1
20、pk=pj-kpj-k+1pj-1pjp0p1pk-1pk=pj-kpj-k+1pj-1pj，此时，此时nextj+1=k+1nextj+1=k+1。(2)(2)若若pkpjpkpj，可以把计算，可以把计算nextjnextj的值的问题看成新的模式匹配过程，主串为的值的问题看成新的模式匹配过程，主串为p p，模式串为，模式串为p p的前缀子的前缀子串。串。出现不匹配，应将模式串的比较位置变为出现不匹配，应将模式串的比较位置变为k=nextkk=nextk，若，若pj=p_(k)pj=p_(k)，则，则nextj+1=k+1=nextk+1nextj+1=k+1=nextk+1，否则继续执行步骤
21、，否则继续执行步骤(2)(2)，直到，直到pj=pkpj=pk，或者当，或者当k=0k=0并且并且pjpkpjpk时时nextj+1=0nextj+1=0。4.2.2 KMP 4.2.2 KMP 算法算法2.K2.K值的计算值的计算代码实现：4.2.2 KMP 4.2.2 KMP 算法算法3.KMP3.KMP算法步骤算法步骤KMPKMP算法的主要步骤如下。算法的主要步骤如下。(1)(1)计算模式串的计算模式串的nextnext函数函数值。值。(2)(2)i i为主串的比较字符位序号，为主串的比较字符位序号，j j为模式串的比较字符位序号。为模式串的比较字符位序号。当字符相等时，当字符相等时，i
22、 i、j j分别加分别加1 1后后继续比较；继续比较；否则否则i i的值不变，的值不变，j=nextjj=nextj，继续比较。，继续比较。(3)(3)重复步骤重复步骤(2)(2)，直到，直到j j等于等于模式串的长度时匹配成功，否模式串的长度时匹配成功，否则匹配失败。则匹配失败。设主串的长度为n、模式串的长度为m，求next的时间复杂度为O(m)。在KMP中，因主串的下标不需要回退，比较次数最多为n-m+1，所以KMP算法的时间复杂度为O(m+n)。4.2.2 KMP 4.2.2 KMP 算法算法3.KMP3.KMP算法步骤算法步骤小测试：请计算小测试：请计算 str=“str=“abcab
23、abcabcababc”的的nextj nextj 的值的值参考答案：参考答案：当当j=0时，时，next0=-1;当当j=1时，时，next1=0;当当j=2时，时，next2=0;当当j=3时，时，next3=0;当当j=4时，时，next4=1;当当j=5时，时，next5=2;当当j=6时，时，next6=1;当当j=7时，时，next7=2。4.34.3数组的概念、特性和遍历数组的概念、特性和遍历数组是数组是n n个具有相同数据类型的数据元素构成的集合，数组元素按某种次序存储在个具有相同数据类型的数据元素构成的集合，数组元素按某种次序存储在地址连续的存储单元中地址连续的存储单元中,是
24、顺序存储的随机存储结构。是顺序存储的随机存储结构。数组元素在数组中的位置称为数组元素的下标，用户通过下标可以访问相应的数组数组元素在数组中的位置称为数组元素的下标，用户通过下标可以访问相应的数组元素。数组下标的个数是数组的维数，具有一个下标的数组叫一维数组，具有两个元素。数组下标的个数是数组的维数，具有一个下标的数组叫一维数组，具有两个下标的数组叫二维数组。一维数组的逻辑结构是线性表，多维数组是线性表的扩展下标的数组叫二维数组。一维数组的逻辑结构是线性表，多维数组是线性表的扩展。二维数组可以看成数组元素是一维数组的数组。下图所示为二维数组的矩阵表示。二维数组可以看成数组元素是一维数组的数组。下
25、图所示为二维数组的矩阵表示。4.3.1 4.3.1 数组的基本概念数组的基本概念0,00,11,01,1nm nmmnaaAaa二维数组中的每个数据元素二维数组中的每个数据元素ai,jai,j都受到两个关系的约束，即行关系和列关系。都受到两个关系的约束，即行关系和列关系。ai.,j+1ai.,j+1是是ai,jai,j在行在行关系中的后继元素；关系中的后继元素；ai+1,jai+1,j是是ai,jai,j在列关系中的后继元素。在列关系中的后继元素。因为二维数组可以看成数组元素是一维数组的数组，所以二维数组也可看成线性表，即因为二维数组可以看成数组元素是一维数组的数组，所以二维数组也可看成线性表
26、，即A=(a0,a1,an-1)A=(a0,a1,an-1)，其中每个数据元素，其中每个数据元素aiai是一个列向量的线性表，即是一个列向量的线性表，即ai=(a0i,a1i,am-1i);ai=(a0i,a1i,am-1i);或或者表述为者表述为A=(a0,a1,am-1)A=(a0,a1,am-1)，其中每个数据元素，其中每个数据元素aiai是一个行向量的线性表，即是一个行向量的线性表，即ai=(a0i,a1i,an-1i)ai=(a0i,a1i,an-1i)。其中，每个元素同时属于两个线性表，第。其中，每个元素同时属于两个线性表，第i i行的线性表和第行的线性表和第j j列的线性表列的线
27、性表，具体可以分析如下：，具体可以分析如下：（1 1）a0,0a0,0是起点，没有前驱元素；是起点，没有前驱元素；am-1,n-1am-1,n-1是终点，没有后继元素。是终点，没有后继元素。（2 2）边界元素边界元素ai,0ai,0和和a0,ja0,j（1jn,1im1jn,1im）只有一个前驱元素；）只有一个前驱元素；ai,n-1ai,n-1和和am-1,jam-1,j（0jn-0jn-1,1im-11,1im-1）只有一个后继元素。）只有一个后继元素。（3 3）ai,jai,j（1jn-1,1im-11jn-1,1im-1）有两个前驱元素和两个后继元素。）有两个前驱元素和两个后继元素。4.
28、3.1 4.3.1 数组的基本概念数组的基本概念数组元素被存放在一组地址连续的存储单元里，并且每个数据元素的大小相同，故只要已数组元素被存放在一组地址连续的存储单元里，并且每个数据元素的大小相同，故只要已知首地址和每个数据元素占用的内存单元大小即可求出数组中任意数据元素的存储地址。知首地址和每个数据元素占用的内存单元大小即可求出数组中任意数据元素的存储地址。对于对于一维数组一维数组AnAn，数据元素的存储地址为，数据元素的存储地址为Loc(i)=Loc(0)+iLoc(i)=Loc(0)+iL(0in)L(0in)，其中，其中Loc(i)Loc(i)是是第第i i个元素的存储地址，个元素的存储
29、地址，Loc(0)Loc(0)是数组的首地址，是数组的首地址，L L是每个数据元素占用的字节数。是每个数据元素占用的字节数。对于对于二维数组二维数组，采用行优先顺序进行存储，即先存储数组的第一行，再依次存储其他各行，采用行优先顺序进行存储，即先存储数组的第一行，再依次存储其他各行。对于一个。对于一个n nm m的数组的数组AnmAnm，数组元素的存储地址为，数组元素的存储地址为Loc(i,j)=Loc(0,0)+(iLoc(i,j)=Loc(0,0)+(im+j)m+j)L L，其中，其中Loc(i,j)Loc(i,j)是第是第i i行第行第j j列的数组元素的存储地址，列的数组元素的存储地址
30、，Loc(0,0)Loc(0,0)是数组的首地址，是数组的首地址，L L是每是每个数据元素占用的字节数。个数据元素占用的字节数。4.3.2 4.3.2 数组的特性数组的特性将计算数组元素的存储位置的公式推广到一般情况，可得将计算数组元素的存储位置的公式推广到一般情况，可得n n维数组维数组Am1m2mnAm1m2mn的数据的数据元素的存储位置：元素的存储位置：在在n n维数组中，计算数组中数据元素的存储地址的时间复杂度为维数组中，计算数组中数据元素的存储地址的时间复杂度为O(1)O(1)，n n维数组是一种随机维数组是一种随机存储结构。存储结构。4.3.2 4.3.2 数组的特性数组的特性12
31、1223111(,)(0,0,0)()(0,0,0)nnnnnnnnjknkjjLoc i iiLocimmimmimiLLocimiL 对二维数组进行遍历操作有两种次序，即行主序和列主序。对二维数组进行遍历操作有两种次序，即行主序和列主序。（1 1）行主序：行主序：以行序为主要次序，按行序递增访问数组的每行，同一行按列序递增访问以行序为主要次序，按行序递增访问数组的每行，同一行按列序递增访问数组元素。数组元素。（2 2）列主序：列主序：以列序为主要次序，按列序递增访问数组的每列，同一列按行序递增访问以列序为主要次序，按列序递增访问数组的每列，同一列按行序递增访问数组元素。数组元素。4.3.3
32、 4.3.3 数组的遍历数组的遍历举例：举例：请你请你设计设计一个算法，求二维数组一个算法，求二维数组An,nAn,n的两条对角线元素之和。的两条对角线元素之和。4.3.3 4.3.3 数组的遍历数组的遍历答案示例：答案示例：4.44.4特殊矩阵的压缩存储特殊矩阵的压缩存储在科学技术和工程计算的许多领域，矩阵是数值分析问题研究的对象。特殊矩阵是具有许在科学技术和工程计算的许多领域，矩阵是数值分析问题研究的对象。特殊矩阵是具有许多相同数据元素或者零元素且数据元素的分布具有一定规律的矩阵，例如对称矩阵、三角多相同数据元素或者零元素且数据元素的分布具有一定规律的矩阵，例如对称矩阵、三角矩阵和对角矩阵
33、。矩阵和对角矩阵。数据压缩技术是计算机软件领域研究的一个重要问题，图像、音频、视频等多媒体信息都数据压缩技术是计算机软件领域研究的一个重要问题，图像、音频、视频等多媒体信息都需要进行数据压缩存储。本节将以特殊矩阵为例介绍矩阵的压缩存储。需要进行数据压缩存储。本节将以特殊矩阵为例介绍矩阵的压缩存储。矩阵采用二维数组进行存储，至少占用矩阵采用二维数组进行存储，至少占用m mn n个存储单元。当矩阵的阶数很大时，矩阵所占个存储单元。当矩阵的阶数很大时，矩阵所占用的存储空间巨大，因此需要研究矩阵的压缩存储问题，根据不同矩阵的特点设计不同的用的存储空间巨大，因此需要研究矩阵的压缩存储问题，根据不同矩阵的
34、特点设计不同的压缩存储方法，节省存储空间，同时保证采用压缩存储的矩阵仍然能够正确地进行各种矩压缩存储方法，节省存储空间，同时保证采用压缩存储的矩阵仍然能够正确地进行各种矩阵运算。阵运算。4.4 4.4 特殊矩阵的压缩存储特殊矩阵的压缩存储常用的矩阵压缩存储方法主要有以下两种：常用的矩阵压缩存储方法主要有以下两种：(1)(1)对于零元素分布有规律的特殊矩阵，采用线性压缩或三角形的二维数组，只存对于零元素分布有规律的特殊矩阵，采用线性压缩或三角形的二维数组，只存储有规律的部分元素。储有规律的部分元素。(2)(2)对于零元素分布没有规律的特殊矩阵，只存储非零元素。对于零元素分布没有规律的特殊矩阵，只
35、存储非零元素。下面，我们分别介绍一下不同类型的矩阵压缩存储方式下面，我们分别介绍一下不同类型的矩阵压缩存储方式4.4 4.4 特殊矩阵的压缩存储特殊矩阵的压缩存储三角矩阵包括上三角矩阵和下三角矩阵。假如是一个三角矩阵包括上三角矩阵和下三角矩阵。假如是一个n n阶矩阵，由阶矩阵，由n n（n+1n+1）/2/2个元个元素组成。当素组成。当ijijij时，矩阵时，矩阵中的数据元素满足中的数据元素满足=0=0，矩阵为上三角矩阵。，矩阵为上三角矩阵。三角矩阵中具有近一半的分布有规律的零元素，所以三角矩阵采取只存储主对角线三角矩阵中具有近一半的分布有规律的零元素，所以三角矩阵采取只存储主对角线以及上以及
36、上/下三角部分的矩阵元素的压缩方法，主要分为以下两种：下三角部分的矩阵元素的压缩方法，主要分为以下两种：1.1.线性压缩存储线性压缩存储2.2.使用三角形的二维数组压缩存储使用三角形的二维数组压缩存储4.4.1 4.4.1 三角矩阵的压缩存储三角矩阵的压缩存储1.1.线性压缩存储线性压缩存储将下三角矩阵的主对角线及其以下元素按行主序顺序压缩成线性存储结构，存储元将下三角矩阵的主对角线及其以下元素按行主序顺序压缩成线性存储结构，存储元素的个数为素的个数为n n（n+1n+1）/2/2，其中元素的存储地址如下：，其中元素的存储地址如下：其中，注意其中，注意L L为数据元素所占据存储空间的字节数。为
37、数据元素所占据存储空间的字节数。计算各数据元素的存储地址的时间复杂度为计算各数据元素的存储地址的时间复杂度为O O（1 1）,三角矩阵的线性压缩存储结构三角矩阵的线性压缩存储结构是随机存储结构。是随机存储结构。4.4.1 4.4.1 三角矩阵的压缩存储三角矩阵的压缩存储(1)()*,()2,()i ijL ijkij空2.2.使用三角形的二维数组压缩存储使用三角形的二维数组压缩存储三角形的二维数组实际上是一种动态数组结构，第三角形的二维数组实际上是一种动态数组结构，第i i行一维数组的长度为行一维数组的长度为i+1i+1，存储，存储在在matijmatij中，如图中，如图4.44.4所示。计算
38、各数据元素的存储地址的时间复杂度为所示。计算各数据元素的存储地址的时间复杂度为O O（1 1）,此压缩存储结构是随机存储结构。此压缩存储结构是随机存储结构。4.4.1 4.4.1 三角矩阵的压缩存储三角矩阵的压缩存储n n阶对称矩阵是指一个阶对称矩阵是指一个n n阶矩阵中的数据元素满足阶矩阵中的数据元素满足ai,j=aj,iai,j=aj,i。对称矩阵在进行压缩。对称矩阵在进行压缩存储时只存储主对角线和上存储时只存储主对角线和上/下部分数据元素，即将对称矩阵的主对角线及其上下部分数据元素，即将对称矩阵的主对角线及其上/下下部分数据元素按行主序顺序压缩成线性存储，占用部分数据元素按行主序顺序压缩
39、成线性存储，占用n n（n+1n+1）/2/2个存储单元个存储单元,矩阵元矩阵元素的线性压缩存储地址为：素的线性压缩存储地址为：4.4.2 4.4.2 对称矩阵对称矩阵的压缩存储的压缩存储(1)()2(1)()2i ij ijkj ji ij如果一个矩阵的所有非零元素都集中在以主对角线为中心的带状区域，则称该矩阵如果一个矩阵的所有非零元素都集中在以主对角线为中心的带状区域，则称该矩阵为对角矩阵。它是一个为对角矩阵。它是一个n n阶矩阵，除了主对角线上的元素，其科元素均为阶矩阵，除了主对角线上的元素，其科元素均为0 0，则是主，则是主对角矩阵；对角矩阵；除了主对角线上及主对角线上下各一个元素外，
40、其余元素均为除了主对角线上及主对角线上下各一个元素外，其余元素均为0 0，为三，为三对角矩阵。对角矩阵。在压缩存储对角矩阵时，只存储主对角线及其两侧部分的元素。如压缩存储主对角在压缩存储对角矩阵时，只存储主对角线及其两侧部分的元素。如压缩存储主对角矩阵，将主对角元素顺序压缩成线性存储，存储元素个数为矩阵，将主对角元素顺序压缩成线性存储，存储元素个数为n n，矩阵数据元素的线，矩阵数据元素的线性压缩存储地址为：性压缩存储地址为：4.4.3 4.4.3 对角矩阵的压缩存储对角矩阵的压缩存储kikj或稀疏矩阵是指矩阵中的非零元素个数远远小于矩阵元素个数并且非零元素的分布没稀疏矩阵是指矩阵中的非零元素
41、个数远远小于矩阵元素个数并且非零元素的分布没有规律的矩阵。设矩阵中有有规律的矩阵。设矩阵中有t t个非零元素，非零元素占元素总数的比例称为矩阵的个非零元素，非零元素占元素总数的比例称为矩阵的稀疏因子，通常稀疏因子小于稀疏因子，通常稀疏因子小于0.050.05的矩阵称为稀疏矩阵。一般使用以下几种方法进的矩阵称为稀疏矩阵。一般使用以下几种方法进行稀疏矩阵的压缩存储。行稀疏矩阵的压缩存储。1.1.稀疏矩阵的非零元素三元组稀疏矩阵的非零元素三元组2.2.稀疏矩阵的十字链表存储稀疏矩阵的十字链表存储4.4.4.4.4 4 稀疏稀疏矩阵的压缩存储矩阵的压缩存储1.1.稀疏矩阵的非零元素三元组稀疏矩阵的非零
42、元素三元组稀疏矩阵的压缩存储原则是只存储矩阵中的非零元素，而仅存储非零元素是不够的稀疏矩阵的压缩存储原则是只存储矩阵中的非零元素，而仅存储非零元素是不够的，必须存储该元素在矩阵中的位置。矩阵元素的行号、列号和元素值称为该元素的，必须存储该元素在矩阵中的位置。矩阵元素的行号、列号和元素值称为该元素的三元组。三元组。在在PythonPython语言中稀疏矩阵的三元组表示的结点结构定义如下：语言中稀疏矩阵的三元组表示的结点结构定义如下：4.4.4.4.4 4 稀疏稀疏矩阵的压缩存储矩阵的压缩存储1.1.稀疏矩阵的非零元素三元组稀疏矩阵的非零元素三元组稀疏矩阵的三元组顺序表类的定义如下：稀疏矩阵的三元
43、组顺序表类的定义如下：4.4.4.4.4 4 稀疏稀疏矩阵的压缩存储矩阵的压缩存储1.1.稀疏矩阵的非零元素三元组稀疏矩阵的非零元素三元组初始化三元组顺序表是按先行序后列序的原则扫描稀疏矩阵，并把非零元素插入到初始化三元组顺序表是按先行序后列序的原则扫描稀疏矩阵，并把非零元素插入到顺序表中，其算法如下。顺序表中，其算法如下。4.4.4.4.4 4 稀疏稀疏矩阵的压缩存储矩阵的压缩存储2.2.稀疏矩阵的十字链表存储稀疏矩阵的十字链表存储 当稀疏矩阵中非零元素的位置或个数经常发生变化时不宜采用三元组顺序表存储结构，而当稀疏矩阵中非零元素的位置或个数经常发生变化时不宜采用三元组顺序表存储结构，而应该
44、采用链式存储结构表示。十字链表是稀疏矩阵的另一种存储结构，在十字链表中稀疏矩阵的非应该采用链式存储结构表示。十字链表是稀疏矩阵的另一种存储结构，在十字链表中稀疏矩阵的非零元素用一个结点来表示，每个结点由零元素用一个结点来表示，每个结点由5 5个域组成。个域组成。rowrow域存放该元素的行号，域存放该元素的行号，columncolumn域存放该元素域存放该元素的列号，的列号，valuevalue域存放该元素的值，域存放该元素的值，rightright域存放与该元素同行的下一个非零元素结点的指针，域存放与该元素同行的下一个非零元素结点的指针，downdown域存放与该元素同列的下一个非零元素结点
45、的指针。每个非零数据元素结点既是某个行链表中的一域存放与该元素同列的下一个非零元素结点的指针。每个非零数据元素结点既是某个行链表中的一个结点，也是某个列链表中的结点，整个稀疏矩阵构成了一个十字交叉的链表，这样的链表就称为个结点，也是某个列链表中的结点，整个稀疏矩阵构成了一个十字交叉的链表，这样的链表就称为十字链表。十字链表。4.4.4.4.4 4 稀疏稀疏矩阵的压缩存储矩阵的压缩存储2.2.稀疏矩阵的十字链表存储稀疏矩阵的十字链表存储在在PythonPython语言中可以将稀疏矩阵的十字链表表示的结点结构定义如下：语言中可以将稀疏矩阵的十字链表表示的结点结构定义如下：稀疏矩阵的十字链表类的定义
46、如右：稀疏矩阵的十字链表类的定义如右：4.4.4.4.4 4 稀疏稀疏矩阵的压缩存储矩阵的压缩存储下面，我们做一个例题，来深入了解不同存储结构的优缺点下面，我们做一个例题，来深入了解不同存储结构的优缺点:已知已知A A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求运算的优缺点。同的存储结构完成求运算的优缺点。参考答案参考答案:设稀疏矩阵为m行n列，如果采用二维数组存储，其空间复杂度为O(mn)；因为要将所有的矩阵元素累加起来，所以需要用一个两层的嵌套循环，其时间复杂度也为O(mn)。如果采用
47、三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为O(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度也为O(t)。当tmn时采用三元组顺序表存储可获得较好的时空性能。4.4.4.4.4 4 稀疏稀疏矩阵的压缩存储矩阵的压缩存储4.54.5总结总结(1)(1)字符串是数据元素类型为字符的线性表，串具有插入、删除、链接、查字符串是数据元素类型为字符的线性表，串具有插入、删除、链接、查找、比较等基本操作。找、比较等基本操作。(2)(2)字符串具有顺序存储结构和链式存储结构两种存储结构。字符串的顺序字符串具有顺序存储结构和链式存储结构两种存储结构。字符串的顺序存
48、储结构叫顺序串，与顺序表的逻辑结构相同，存储结构类似，均可用数组存储结构叫顺序串，与顺序表的逻辑结构相同，存储结构类似，均可用数组来存储数据元素。字符串的链式存储结构叫链串，和线性表的链式存储结构来存储数据元素。字符串的链式存储结构叫链串，和线性表的链式存储结构类似，可以采用单链表存储串值。链串由一系列大小相同的结点组成，每个类似，可以采用单链表存储串值。链串由一系列大小相同的结点组成，每个结点用数据域存放字符，指针域存放指向下一个结点的指针。结点用数据域存放字符，指针域存放指向下一个结点的指针。(3)(3)串的模式匹配也叫查找定位，指的是在当前串中寻找模式串的过程，主串的模式匹配也叫查找定位
49、，指的是在当前串中寻找模式串的过程，主要的模式匹配算法有要的模式匹配算法有Brute ForceBrute Force算法和算法和KMPKMP算法。算法。4.5 4.5 总结总结(4)(4)数组是数组是n n个具有相同数据类型的数据元素构成的集合，数组元素按某种次个具有相同数据类型的数据元素构成的集合，数组元素按某种次序存储在地址连续的存储单元中，是一种随机存储结构。序存储在地址连续的存储单元中，是一种随机存储结构。(5)(5)特殊矩阵是具有许多相同数据元素或者零元素且数据元素的分布具有一特殊矩阵是具有许多相同数据元素或者零元素且数据元素的分布具有一定规律的矩阵，例如对称矩阵、三角矩阵和对角矩阵。为了节省存储空间，定规律的矩阵，例如对称矩阵、三角矩阵和对角矩阵。为了节省存储空间，对矩阵进行压缩存储。特殊矩阵的压缩存储方法是将呈现规律性分布的、值对矩阵进行压缩存储。特殊矩阵的压缩存储方法是将呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间。相同的多个矩阵元素压缩存储到一个存储空间。(6)(6)稀疏矩阵是具有较多零元素，并且非零元素的分布无规律的矩阵。稀疏稀疏矩阵是具有较多零元素，并且非零元素的分布无规律的矩阵。稀疏矩阵的压缩存储是只给非零数据元素分配存储空间。矩阵的压缩存储是只给非零数据元素分配存储空间。4.5 4.5 总结总结
