数据结构 第2版 宗大华 陈吉人 数据结构 课件-4

《数据结构 第2版 宗大华 陈吉人 数据结构 课件-4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串、数组、矩阵1.2.3.本章讲述内容：4.串的基本知识；串的存储实现及各种处理算法；数组的基础知识及顺序存储；各种特殊矩阵(对称矩阵、三角矩阵)，及其压缩存储；5.稀疏矩阵及其压缩存储。4.1串4.1.1串的基本知识.所谓“串”，即是由0个或多个字符构成的一个有限序列，用双引号作为其定界符。它是通常所说的字符串。串是一种特殊的线性表。.若有一个串s：s="a1a2…an−1an"（n≥0）那么，称s为该串的“串名”，a1a2…an−1an是串s的取“值”。括住串值的双引号只起限定串的作用，本身并不是字符串的内容。.在字符串双引号内的字符个数n，称为字符串的“长度”。当n=0时，

2、称其是一个“空串”，空字符串是不含任何字符的串。字符串中每个字符在串里的序号，称为它在字符串的“位置”。字符串中任意多个连续字符所组成的子序列，称作是该串的“子串”，该字符串本身称为“主串”。一个子串第1个字符在主串中的位置，称作是该子串在“主串中的位置”。..线性表和字符串的本质区别，在于线性表只是以单个数据元素（这里就是字符）作为处理的对象，而字符串则可以以自己作为一个整体参与处理，也可以以该字符串的一个部分（子串）参与处理。4.1.2串的顺序存储实现.当采用顺序式存储结构存储字符串时，就称它为“顺序串”。由于字符串是线性表的一个特例，因此，顺序串就是顺序表的一个特例。.为建立顺序

3、串St，需通过数组申请一个连续的存储区，给出其最大容量St_max，设置一个串的长度计数器St_len，初始时它为0。即做如下三件事情：charSt[MAX];St_max=MAX;St_len=0;为了明确字符串的结束位置，需在串的末尾添加一个串结束符。在C语言里，把“”作为字符串的结束符，本书仍沿用它。.若开辟的数组最大容量为St_max，那么这个数组最多可以容纳的字符串长度应该是St_max-1，而不是St_max，因为至少要留一个位置来存放串结束符“”。.D1顺序串St:a2t3a45S6t7r8u9c10t11u12r13e14151617181920St_len

4、St_max在下图里，开辟的数组St的尺寸为20，即St_max=20，表示它最多可存放20个字符；当前存放在里面的串的长度为14，即St_len=14。实际上这个数组最多可以容纳的字符串长度应该只有19，而不是20。.连接两个顺序串的算法算法4-1算法描述(1)算法分析(2)Concat_St(St1,St2){charSt3[maxsize];St3_len=0;if(St1_len+St2_len>maxsize+1){printf("两串长度之和超长！");return(NULL);}else{for(i=1;i<=St1_len;i++)St3[i]=St1[i];for(j

5、=1;j<=St2_len;j++)St3[j+St1_len]=St2[j];St3_Len=St1_len+St2_len;St3[St3_len+1]="";return(St3);}}.算法先通过检测条件：St1_len+St2_len>maxsize+1来判断新串St3能否放下已知的串St1和St2。这里只要求St1_len+St2_len大于maxsize是不行的，因还要有一个存放串结束符的位置。.St1和St2连接后的St3结果如下图所示abcdSt1:zyuvwxSt2:abcd(a)St3:zyuvwx(b)(c).算法讨论(3)由于是把一个串连接到另

6、一个串的后面，因此必须小心处理两个串的连接位置（也就是边界），不要在连接处发生字符的重叠。判断两个顺序串相等的算法算法4-2算法描述(1)算法分析(2)说明：已知两个顺序串St1和St2，如果相等则返回1，否则返回0。Equal_St(St1,St2){if(St1_len!=St2_len)return(0);else{for(i=1;i<=St1_len;i++)if(St1[i]!=St2[i])return(0);return(1);}}..两个字符串相等的含义不仅是长度要相等，而且对应位置上的字符也必须完全一样。因此，算法一开始就检查条件“St1_len==St2_len”是

7、否满足。若不满足，就返回0。.在长度相等的基础上，通过for()循环去核对相应位置上的字符是否一样。如果检查出有一个不同，那么被检查的两个字符串就肯定不相等。只有完全一样，才返回1。算法讨论(3)也可以这样来描述算法：直接核对相应位置上的字符是否相同，然后分情况去做判断。一种是有不相同的字符出现，一种是有一个字符串比另一个串长，最后则是两个串完全相等。.算法的含义是：已知主串St1，要从第i个位置开始，把连续n个字符组成的子串赋给串St2。从主