资源描述：
《第四章 字符串、数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章字符串、数组和广义表4.1字符串的基本概念4.2字符串的存储结构4.3字符串的模式匹配4.4数组的基本概念4.5矩阵的压缩存储4.6广义表4.7典型例题4.1字符串基本概念字符已成为非数值应用重要的处理对象.如文字编辑,情报检索,自然语言翻译和各种事务处理系统等。字符串是由某字符集上的字符所组成的任何有限字符序列.当一个字符串不包含任何字符时,称它为空字符串。一个字符串所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。包含子串的串相应地称为主串。在C语言中,字符串常量是用一对双引导括起来若干字符来表示。通常称字符在序列中的序号为该字符
2、在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示.例4.1:假如a,b,c,d为如下的四个串:a=“BEI”,b=“JING”c=“BEIJING”,d=“BEIJING”则它们的长度为：3，4，7和8；并且a和b都是c和d的子串；a在c和d中的位置都是1；而b在c中的位置是在d中的位置是5。另外，每个字符串的最后一个有效字符之后有一个字符串结束符，记为‘ ’。字符串通常存于足够大的字符数组中。★如要称两个串是相等的，当且仅当这两面个串的值相等。也就是说，只有当两个串的长度相等，并且各对应位置的字符都相等时才相等。4.2字符串的存储结构对于字符串常量，只
3、需作为一个字符的序列存储。对于字符串变量，赋给它一个串名，对串运算时，通过变量名访问其值。其存储分配有两种形式，一是将字符串设计成一种结构类型（如pascal语言和c语言中，字符串都是用字符数组来实现），从字符串名可直接访问到字符串值，字符串值的存储分配是在编译时完成的；另一是字符串值的存储分配在程序运行时完成，在字符串名和字符串值之间需建立一个对照表（称为串名的存储映象），字符串的访问通过串名的存储映象进行。我们称前一种为顺序存储结构，后一种为链式存储结构。4.2.1串的存储结构和线性表的顺序存储结构类似，用一组地址连续的存储单元存储串的字符序列。在C语言中用一维数组来实现。（
4、一）紧缩格式假定，一个存储单元可存放K个字符，而且给出的串长度为N，那么此字符串的字符串值就要占[N/K]个存储单元紧缩格式是以字符为单位依次将字符存放在存储单元里。（PASCAL语言中的紧缩数组）（二）非紧缩格式在一个存储单元中存放一个字符，所需存储单元个数就是串长。紧缩格式可节省存储空间，但在进行串运算时需要花费较时间去分离同一存储单元中的字符。4.2.2串的链式存储结构和线性表的链式存储结构类似，也可采用链表方式存储串值。由于串结构的特殊性——结构中的每个数据元素是一个字符，则可用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可存放多个字符。he
5、ad结点大小为4示图head结点大小为1示图ABDCEFGHI ^ ABCD4.3字符串的模式匹配设s和t是给定的两个串，在串s中寻找等于t的子串的位置的过程称为模式匹配，其中，s串称为主串，t串称为模式，如在s中找到等于t的子串，则称匹配成功，并返回模式t在s串的序号：反之匹配失败，并返回于序号为零。例4.2:1、s=“abcdefg”,t=“efg”则模式t在主串s中的序号等于52、s=“abcdefg”,t=“abcdg”则t在s中的序号等于03﹑s=“abcdefabc”,t=“abc”如从s串的第一个字符开始搜索则序号等于1；如从s第三个字符开始搜索，则序号等于
6、7。4.3.1模式匹配的BF算法算法的基本思想是：从主串s的第一个字符起和模式的第一趟匹配。第一个字符比较之，若相等，则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式的字符比较之。依次类推，直至模式t中的每个字符依次和主串s中的一个连续的字符序列相等，则称匹配成功，函数值为和模式t中第一个字符相等的字符在主串s中的序号，否则称匹配不成功，函数值为零。如果s=“ababcabcacbab”t=“abcac”t在s中的模式匹配过程如下i=2第一趟匹配ababcabcacbababcj=2i=1第二趟匹配ababcabcacbabaj=0i=6第三趟匹配ababcabcac
7、bababcacj=4i=3t在s中的模式匹配过程(续)i=3第四趟匹配ababcabcacbabaj=0i=4第五趟匹配ababcabcacbabaj=0i=10第六趟匹配ababcabcacbababcacj=5方法一：BF算法的实现函数：intindex(chars[],chart[],intstart){intI,j,m,n;m=strlen(s);n=strlen(t);if(start<0
8、
9、start+n>m+1
10、
11、n==0)return(0);else{i=sta
