《字符串数组和广义表》由会员分享，可在线阅读，更多相关《字符串数组和广义表（64页珍藏版）》请在金锄头文库上搜索。
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=“BEI JING”则它们的长度为：3，4 ，7和8；并且a和b都是 c和d的子串；a在c和d中的位置都是1；而b在c 中的位置是在d中的位置是5。另外，每个字符串的最后一个有效字符之后有 一个字符串结束符，记为0。字符串通常存于 足够大的字符数组中。 如要称两个串是相等的，当且仅当这两面个 串的值相等。也就是说，只有当两个串的长度 相等，并且各对应位置的字符都相等时才相等 。4.2字符串的存储
3、结构对于字符串常量，只需作为一个字符的序列存储 。对于字符串变量，赋给它一个串名，对串运算 时，通过变量名访问其值。其存储分配有两种形 式，一是将字符串设计成一种结构类型（如pascal 语言和c语言中，字符串都是用字符数组来实现） ，从字符串名可直接访问到字符串值，字符串值 的存储分配是在编译时完成的；另一是字符串值 的存储分配在程序运行时完成，在字符串名和字 符串值之间需建立一个对照表（称为串名的存储 映象），字符串的访问通过串名的存储映象进行 。我们称前一种为顺序存储结构，后一种为链式 存储结构。4.2.1串的存储结构 和线性表的顺序存储结构类似，用一组地址连 续的存储单元存储串的字符序
4、列。在C语言中用 一维数组来实现。 （一）紧缩格式 假定，一个存储单元可存放K个字符，而且给出 的串长度为N，那么此字符串的字符串值就要占 N/K个存储单元 紧缩格式是以字符为单位依次将字符存放在存 储单元里。（PASCAL语言中的紧缩数组） （二）非紧缩格式 在一个存储单元中存放一个字符，所需存储单 元个数就是串长。紧缩格式可节省存储空间， 但在进行串运算时需要花费较时间去分离同一 存储单元中的字符。4.2.2串的链式存储结构和线性表的链式存储结构类似，也可采用链表方式 存储串值。由于串结构的特殊性结构中的每个 数据元素是一个字符，则可用链表存储串值时，存 在一个“结点大小”的问题，即每个结
5、点可以存放 一个字符，也可存放多个字符。 head 结点大小为4示图 head 结点大小为1示图 A BDCE F GHI000A B C D 4.3 字符串的模式匹配设s和t是给定的两个串，在串s中寻找等于t的子串的位置 的过程称为模式匹配，其中，s串称为主串，t串称为模 式，如在s中找到等于t的子串，则称匹配成功，并返回 模式t在s串的序号：反之匹配失败，并返回于序号为零 。 例4.2 : 1、s=“abcdefg”,t=“efg” 则模式t在主串s中的序号等于5 2、s=“abcdefg”,t=“abcdg” 则t在s中的序号等于0 3s=“abcdefabc”,t=“abc” 如从s串
6、的第一个字符开始搜索则序号等于1；如从s第三 个字符开始搜索，则序号等于7。4.3.1模式匹配的BF算法算法的基本思想是：从主串s的第一个字符起和模式 的第一趟匹配。第一个字符比较之，若相等，则继 续逐个比较后续字符，否则从主串的第二个字符起 再重新和模式的字符比较之。依次类推，直至模式t 中的每个字符依次和主串s中的一个连续的字符序列 相等，则称匹配成功，函数值为和模式t中第一个字 符相等的字符在主串s中的序号，否则称匹配不成功 ，函数值为零。如果s=“ababcabcacbab” t=“abcac”t在s中的模式匹配过程如下 i=2 第一趟匹配 a b a b c a b c a c b
7、a b a b c j=2 i=1 第二趟匹配 a b a b c a b c a c b a b a j=0 i=6 第三趟匹配 a b a b c a b c a c b a b a b c a c j=4 i=3 t在s中的模式匹配过程(续) i=3 第四趟匹配 a b a b c a b c a c b a b a j=0 i=4 第五趟匹配 a b a b c a b c a c b a b a j=0 i=10 第六趟匹配 a b a b c a b c a c b a b a b c a c j=5方法一： BF算法的实现函数： int index(char s,char t,
8、int start) int I,j,m,n; m=strlen(s); n=strlen(t); if(startm+1 | n=0) return(0); else i=start; /*从S中的第start位开始匹配*/ j=0; while(i=n) return(i-n); else return(0); 方法二：BF算法也可用如下函数表示： int simple match(char *s,char *t) int n=strlen(s),m=strlen(t),i,j,k; for(j=0;jp 16 else *q=0; 17 return (5) ; 18 19 void m
9、ain() 20 21 char str =”we are Chinese “ 22 printf(“%sn”,sdel(str); 23 4.4 数组的基本概念在概念上，数组由固定个数的元素组成，全部元素的类型相 同，元素依次顺序存储。每个元素对应一个下标，数组元 素按数组名和元素的下标引用，引用数组元素的下标个数 称为数组的维数。 在C语言中，约定数组的第一个元素的下标为0，其余依次类 推，由n个元素组成的数组，其最后一个元素的下标为n-1 。数组元素可以是任何类型的，当元素本身又是数组时就 构成多维数组。数组通常是顺序存储的，对于多维数组， C语言按行优先顺序存放。如有以下数组定义：in
10、t a110,a289,a3789； 则数组a1是一维数组，a2是二维数组，a3是三维数组。记元 素X的内存地址为Loc(x),设每个元素所需内存字节数为s， 存储元素a1 i,a2ij,a3ijk的内存地址分别可由以下算式 确定：内存地址计算Loc(a1i)=Loc(a10)+i*s Loc(a2 ij)=Loc(a200)+(i*9+j)*s Loc(a3ijk)=Loc(a3000)+(i*8+j)*9+k)*s 若用C语言的指针来描述，以上算式可分别简成： int colum; int value; tyredef struct node NODE; NODE maxMAX;2、稀疏矩
11、阵的十字链表表示法 ：在十字链表中，稀疏矩阵的每一行用一个带表头节点的循环表示，每 一列也用一个带表头的循环链表表示。在这个结构中，除表头节点外 ，每一个节点都代表矩阵中的一个非零元素，它由五个域组成；行域 （row），列域（col）,值域(val),向下域(down)和向右域(right)。节点结 构和存储表示如下： 表结点 行（列）头结点 表头结点 Down rowrightcowvolrightdown00linkmnlink举例（）若有矩阵M如下: 例 题目：求一个3*3矩阵对角线元素之和 1.程序分析：利用双重for循环控制输 入二维数组，再将aii累加后输出。 2.程序源代码：#i
12、nclude void main() float a33,sum=0; int i,j; printf(“please input rectangle element:n“); for(i=0;itag) x= (4) ; else x= (5) ; if(x) return ( (6) ); return 0; 4.7 典型例题 1以下能正确定义一维数组的选项是 _。A）int num; B）#define N 100; int numN; C）int num0100 D）int N=100; int numN; 答案B)（知识点：一维数组的定义）2假设int类型变量占用两个字节，其有定 义：int x10=0,2,4;，则数组x在内存中所 占的字节数是_。A）3 B）6C）10D）20 答案 D)（知识点：一维数组的定义）4.7 典型例题 3以下程序运行后的输出结果是 _。main() int i,n=0,0,0,0,0; for(i=1;i #include main() char ss10=“12345“; get
