串
串的定义
串（String）（或字符串）：零个或多个任意字符组成的有限序列
概念图示：
关于串的术语：
子串：串和子串、集合与子集的概念类似（空串和真子串），计算子串时要考虑空串；
主串：包含子串的串相应地称为主串；
模式串：子串又称为模式串；
字符位置：字符在序列中的序号称为该字符在串中的位置；
子串位置：子串中第一个字符在主串中的位置；
空格串：由一个或多个空格组成的串，与空串不同；在计算串的长度时，空格也要计入；
串相等：当且仅当两个串的长度相等，并且各个对应位置上的字符都相同时，这两个串才是相等的；所有的空串都是相等的。
串的类型定义、存储结构及其运算
串的类型定义
串的存储结构
串的顺序存储结构
#define MAXLEN 255
typedef struct{
char ch[MAXLEN+1];//存储串的一维数组，因为通常不使用[0]，所以加一，，这样也能存MAXLEN个字符，这样更简便，不易混淆
int length;//串的当前长度
}SString;串的链式存储结构——块链结构
单链表式的串操作方便，但存储密度较低（存储密度=串值所占的存储/实际分配的存储）；
所以可以将多个字符存放在一个结点中，以客服其缺点；这样的结点称为块。
#define CHUNKSIZE 80
typedef struct Chunk{//定义块
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{//定义块链结构的字符串
Chunk *head,*tail;//串的头指针和尾指针
int curlen;//串的当前长度
}LString;串的模式匹配算法
算法目的：确定主串（正文串）中所含子串（模式串）第一次出现的位置（定位）。
算法种类：
BF算法（Brute-Force）：又称暴力破解法，简单匹配法，朴素的模式匹配，采用穷举的思路；
KMP算法：速度快。
BF算法
思路：从正文串的每一个字符开始依次与模式串的字符进行匹配。
int index_BF(SString S,SString T,int pos){//从S的第pos个字符开始，与T的每个字符依次匹配
int i=pos,j=1;
while(i<=S.length&&j<=T.length){
if(S.ch[i]==T.ch[j]){
i++,j++;//主串和子串依次匹配下一个字符
}
else{
i=i-j+2;//i减j后到了上一次匹配的字符前一个位置，所以要+2
j=1;//主串、子串回溯重新开始下一次匹配
}
}
if(j>=T.length) return i-T.length;//返回匹配的第一个字符的下标，注意是下标
else return 0;
}算法时间复杂度：
KMP算法
由三个人共同提出，故以三人名字首字母命名。
比起BF算法更高效的原因：主串的指针i不需要回溯，模式串的指针j不用每次都从头再来。
int Index_KMP(SString S,SString T,int pos){
i=pos,j=1;
while(i<S.length&&j<T.length){
if(j==0||S.ch[i]==T.ch[j]){i++;j++;}
else j=next[j];
}
if(j>T.length) return i-T,length;
else return 0;
}
void get_next(SString T,int &next[]){
i=1;
next[1]=0;
j=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
++i;++j;
next[i]=j;//下标为i 的字符前的字符串最长相等前后缀的长度为j
}
else j=next[j];
}
}数组
数组的基本概念
数组：按一定格式排列起来的、具有相同类型的数据元素的集合。
一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组。
一维数组的逻辑结构：线性结构，其实质上为定长的线性表。
二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。
二维数组的逻辑结构：二维数组中既有非线性结构，又有线性结构。
线性表和数组的关系：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。
数组的特点：结构固定，维数和维界不能改变。
数组的基本操作：初始化，销毁，存取。
数组的顺序存储
存储单元是一维结构，而数组是个多维结构，则用一组连续存储单元存放数组的数据元素就有一个次序约定问题，既可以以行序为主序，也可以以列序为主序。
特殊矩阵的压缩存储
用三元组顺序表来压缩存储稀疏矩阵
稀疏矩阵的十字链表
广义表
广义表的基本概念
也就是说，广义表中的每一个元素也是广义表，广义表就是拓宽了的线性表。
广义表的性质
广义表是线性表的推广，线性表是广义表的特例。
广义表的基本运算
课后习题
课本
（4）串“ ababaabab ”的nextval 为（ ）。
A ． 010104101 B． 010102101
C ． 010100011 D ． 010101011
答案：A
解析：（画图理解更清晰）
下标 i : 1 2 3 4 5 6 7 8 9
字符串s: a b a b a a b a b
next [ i ]: 0 1 1 2 3 4 2 3 4
nextval[i]: 0 1 0 1 0 4 1 0 1
先计算前缀next[i]的值：
计算字符串的next函数值,可以参考"KMP模式匹配算法".
next [ i ]: 0 1 1 2 3 4 2 3 4
接下来计算nextval[i]的值：
第一位的nextval 值必定为0，第二位如果于第一位相同则为0，如果不同则为1。
第三位的next 值为1，那么将第三位和第一位进行比较，均为a，相同，则第三位的nextval 值为0。
第四位的next 值为2，那么将第四位和第二位进行比较，相同，第二位的next 值为1，则继续将第二位与第一位进行比较，不同，则第四位的nextval 值为第二位的next 值，为1。
第五位的next 值为3，那么将第五位和第三位进行比较，相同，第三位的next 值为1，则继续将第三位与第一位进行比较，相同，则第五位的nextval 值为第一位的next 值，为0。
第六位的next 值为4，那么将第六位和第四位进行比较，不同，则第六位的nextval 值为其next 值，为4。
第七位的next 值为2，那么将第七位和第二位进行比较，相同，第二位的next 值为1，则继续将第二位与第一位进行比较，不同，则第七位的nextval 值为第二位的next 值，为1。
第八位的next 值为3，那么将第八位和第三位进行比较，相同，第三位的next 值为1，则继续将第三位与第一位进行比较，相同，则第八位的nextval 值为第一位的next 值，为0。
第九位的next 值为4，那么将第九位和第四位进行比较，相同，第四位的next 值为2，则继续将第四位与第二位进行比较，相同，则第八位的nextval 值为第二位的next 值，为1。
nextval为0,1,0,1,0,4,1,0,1
（ 7）设有数组A[i,j] ，数组的每个元素长度为3 字节， i 的值为1 ~ 8，j 的值为1 ~ 10，数组从内存首地址BA 开始顺序存放， 当用以列为主存放时， 元素A[5,8] 的存储首地址为（ ）。
A． BA+141 B ． BA+180
C． BA+222 D． BA+225
答案：B
解析：先画出i行j列的数组，根据元素的 [ i , j ] 坐标确定元素位置，最后判断是以行序为主还是以列序为主存放，以行序为主则一行一行存放，以列序为主同理。
LOC[5,8]=[ （ 8-1 ） *8+ （ 5-1 ） ]*3+BA=BA+180
（14）广义表((a,b,c,d)) 的表头是（C） ，表尾是（B） 。
A． a B ． ( ) C ． (a,b,c,d) D ． (b,c,d)
表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表，((a,b,c,d)) 的表头为一个子表(a,b,c,d) ； 表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表， ((a,b,c,d)) 的表尾为空表( ) 。
（3）数组A 中，每个元素A[i,j] 的长度均为32 个二进位, 行下标从-1 到9，列下标从1到11 ，从首地址S 开始连续存放主存储器中，主存储器字长为16 位。求：
①存放该数组所需多少单元？
②存放数组第4 列所有元素至少需多少单元？
③数组按行存放时，元素A[7,4] 的起始地址是多少？
④数组按列存放时，元素A[4,7] 的起始地址是多少？
答案：
（ 1） 242 （ 2）22 （ 3） s+182 （ 4） s+142
解析：
首先，数组所能存放的元素有11x11=121个，每个元素的长度为32位，
要将整个数组存入主存储器中，而主存储器的每个单元长度为16位，
所以存放该数组需要121x(32/16)=242个单元。
第二题，因为数组每一列有11个元素，所以将这些元素都存进主存储器中，
需要11x2=22个单元。
第三小题和第四小题，要 注意这里的元素索引是A[7,4]，首先画数组图时，
要 注意行下标是从-1到9，这样才能正确得到其地址。
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
