第三章字符串

第三章1、L(G[S])={ abc }2、L(G[N])={ n位整数或空字符串| n>0 }3、G[E]：E—>E+D | E-D | DD—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、L(G[Z])={ a n b n | n>0 }5、(1) 考虑不包括“0”的情况G[S]：S—>0S | ABC | 2 | 4| 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8考虑包括“0”的情况：G[S]：S—>AB | CB—>AB | CA—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>0 | 2 | 4 | 6 | 8(2)方法1：G[S]：S—> ABC | 2 | 4 | 6 | 8A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B—>AB | 0B | εC—>0 | 2 | 4 | 6 | 8方法2：G[S]：S—>AB | CB—> AB | 0B | C | 0A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C—>2 | 4 | 6 | 86、设<表达式>为E，<项>为T，<因子>为F，注：推导过程不能省略，以下均为最左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I7、<表达式><表达式>*<表达式><表达式>+<表达式>i i i<表达式><表达式>+<表达式>i <表达式>*<表达式>i i8、是有二义性的，因为句子abc 有两棵语法树（或称有两个最左推导或有两个最右推导）最左推导1：S => Ac => abc最左推导2：S => aB => abc9、(1)(2) 该文法描述了变量a 和运算符+、*组成的逆波兰表达式10、(1) 该文法描述了各种成对圆括号的语法结构(2) 是有二义性的，因为该文法的句子()()存在两种不同的最左推导：最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()()最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S => ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因为从文法的开始符E 出发可推导出E+T*F ，推导过程如下：E => E+T => E+T*F ，所以E+T*F 是句型。

串
子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串。 子串的位置：子串的第一个字符在主串中的序号。
S1="ab12cd " S2="ab12" S3="ab13" S4="ab12φ" S5=" " S6="φφφ "
串
串的比较：通过组成串的字符之间的比较来进行的。
给定两个串：X="x1x2…xn"和Y="y1y2…ym"，则： 1. 当n=m且x1=y1，…，xn=ym时，称X=Y； 2. 当下列条件之一成立时，称X＜Y： ⑴ n＜m且xi=yi（1≤ i≤n）； ⑵存在k≤min(m,n)，使得xi=yi(1≤i≤k-1)且xk＜yk。 例：S1="ab12cd "，S2="ab12"，S3="ab13"
串
例：主串S="ababcabcacbab"，模式T="abcac"
i
第 4 趟
a b a b c a b c a c b a b a b c a c
j
i=4，j=1失败 i回溯到5，j回溯到1
Hale Waihona Puke 串例：主串S="ababcabcacbab"，模式T="abcac"
i
第 5 趟
a b a b c a b c a c b a b a b c a c
为什么BF算法时间性能低？
在每趟匹配不成功时存在大量回溯，没有利用已经 部分匹配的结果。
如何在匹配不成功时主串不回溯？
主串不回溯，模式就需要向右滑动一段距离。

typedef struct lnode {
char data; struct lnode *next;
}lstring;
3.3.3 串的存储结构——链式存储结构
当结点大小>1时，可以采用块链结构。
#define CHUNKSIZE 100
/*可由用户定义块的大小*/
typedef struct Chunk
第三章 串与数组
本章要点
➢字符串的基本概念与基本运算 ➢字符串的存储和基本运算的实现 ➢数组的概念和基本运算 ➢数组的存储结构 ➢特殊矩阵的压缩存储及运算 ➢广义表的概念及相关术语 ➢广义表的存储形式
3.1 “文学研究助手”案例导入
“文学研究助手”引例：请从下面的英文文章里，统计其中 good出现的次数和位置，并查找单词the所在的行号，该行中出 现的次数以及在该行中的相应位置。
3.4.1 数组的定义
数组是n个具有相同类型的数据元素构成的有限序列，数组 中的数据是按顺序存储在一块地址连续的存储单元中。
数组中的每一个数据通常称为数组元素，数组元素用下标 区分，其中下标的个数由数组的维数决定。
若线性表中的数据元素为非结构的简单元素，则称为一维 数组，又称为向量；若一维数组中的数据元素又是一维数组结 构，则称为二维数组；依次类推，若二维数组中的元素又是一 个一维数组结构，则称作三维数组。
3.3.4 串的基本操作的实现算法
第二种顺序存储方式下几种基本操作的算法
算法1：串连接操作 算法2：串比较操作 算法3：取子串操作 算法4：串插入操作 算法5：串删除操作 算法6：串置换函数 算法7：子串定位操作
3.3.5 串的应用
【例3-1】设计一个算法求串s中出现的第1个最长重复子串 及其位置。

§3.3 赋值语句
“=“是一个运算符 注意赋值表达式与赋值语句的区别
§3.4 输入输出在c中的实现
输入输出是以计算机主机为主体而言 输入输出是由函数来实现的
库函数：由厂商预先编写好，并编译成目标文件 使用库函数时，用预编译命令“#include”将有
关的“头文件”包含到用户源文件中。
#include <stdio.h> printf,scanf可不加#include命令
%m.ne和%-m.ne ，n指小数部分的小数位数 printf（“%e%10e%10.2e%.2e%-10.2e”，f，f，f， f，f）； 设f=123.456，输出结果为
1.23456e+02 1.23456e+02 1.2e+02 1.2e+02 1.2e+02 ❖g格式符，用来输出实数，根据数值的大小，自动选
printf（“%f %10f %10.2f %.2f %-10.2f \n”，f，f，f，f，f） ；
运} 行结果：
123.456001 123.456001 123.46 123.46 123.46
❖e格式符：以指数形式输出实数 %e ，不指定输出数据所占宽度和数字部分的小数位数。 数值按规范化指数形式输出。 如：printf（“%e”，123.456）；输出结果为1.23456e+02
❖格式控制：包含两种信息 格式说明： %格式字符 ，用于指定输出格式
普通字符或转义序列：原样输出
❖输出表列：要输出的数据（可以没有，也可以是表达 式，多个时以“,”分隔
printf（参数1，参数2，参数3……参数n ）
格式字符
❖d格式符：输出十进制整数 %d ，按整型数据的实际长度输出 %md，m为指定的输出字段的宽度。如果数据的位数 小于m，则左端补空格，否则按实际位数输出 例：printf（“%4d，%4d”，a，b）； 若a=123，b=12345，则输出结果为▂123，12345 %ld，输出长整型数据 例：long a=135790；printf（“%ld”，a）； 也可以指定字段宽度，如%8ld