第4章 串

第四章 串

讲课提要

【主要内容】

1．串的有关概念及基本操作 2．串的存储结构 3．串操作应用举例 【教学目标】

1．掌握串的有关概念及基本运算 2．熟悉串的存储结构 3．熟悉串操作应用举例

学习指导

1．概念和术语 ? 串（String）（或字符串）：是由零个或多个字符组成的有限序列。一般记为

s= “a1a2? an” (n≥0)

其中，s是串的名，用双引号括起来的字符序列是串的值。 ? 串的长度：串中字符的个数n。

? 子串和主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。

? 空串：不包含任何字符的串，表示为“Ф”。 ? 空格串：由一个或多个空格字符组成的串。例如：“ ”。 2．串的基本操作

（1）用串变量赋值assign(s,t)和用串常量赋值create(s,ss) （2）判等函数 equal(s, t） （3）求长函数 length(s) （4）连接函数 concat(s,t)

（5）求子串函数 substring(s, pos , len) （6）定位函数 index(s,t)

（7）置换函数 replace(s,t,v) （8）插入子串 insert(s,pos,t) （9）删除子串 delete(s,pos,k) （10）串的复制 copy(s,t)

【例3-1】已知字符串：a=“an apple”，b=“other hero”，c=“her”，求：

（1）concat(substr(a,1,2),b)。 （2）replace(a,substr(a,5,1),c)。 （3）index(a,c)和index(b,c)。 解：

（1）返回值为“another hero”，其中substr(a,1,2)的返回值为“an”。 （2）返回值为“an aherherle”，其中sub(a,5,1)的返回值为“p”。 （3）返回值分别为0和3。

3．串的顺序存储结构（顺序串）

串的顺序存储方式类似于线性表的顺序存储方式，其存储结构用C语言描述为：

typedef struct strnode { char data[maxlen]; int len;

}SeqString; //定义顺序串类型

【例3-2】设定串采用顺序存储结构，写出对串s1和串s2比较大小的算法。串值大小按字典排序（升序）方式，返回值等于-1，0和1分别表示s1s2。

解： 算法思想：

（1）比较s1和s2共同长度范围内的对应字符： 若s1的字符>s2的字符，返回； 若s1的字符

若s1的字符=s2的字符，按上述规则继续比较； （2）当（1）中对应字符均相同时，比较和的长度： 两者相等时，返回0； 前者>后者时，返回1； 前者<后者时，返回-1； 算法描述如下：

#define MAXLEN 256 struct strnode{ char data[MAXLEN]; int len;

}SeqString; //定义顺序串类型

int strcmp(SeqString s1, SeqString s2)//比较串s1和串s2的大小 { int comlen;

if (s1.len

for(i=0;i

if(s1.ch[i]>s2.ch[i]) return (1); //s1>s2

if(s1.ch[i]= =s2.ch[i]) return (0); //s1=s2 else

if(s1.ch[i]s2 }

4．串的链式存储结构（即链串或块链结构）

使用链式存储结构的字符串，只要存储空间足够大，其长度没有任何限制，但逻辑上的连续性不体现为物理上的邻接性。每个字符和一个指针域形成一个结点，结点间的关系由链指针实现，即字符逻辑上的连续性由链指针描述。

其存储结构用C语言描述为：

typedef struct strnode{ //定义字符串的结点类型 char data;

struct strnode *next; }LinkString;

习题3

一、单项选择题

1. 空串与空格字符组成的串的区别在于（ ）。

A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指（ ）。

A.子串的最后那个字符在主串中的位置

B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置

D.子串的第一个字符在主串中首次出现的位置 3. 下面的说法中，只有（ ）是正确的。

A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4. 两个字符串相等的条件是（ ）。

A.两串的长度相等 B.两串包含的字符相同

C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同

5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。

A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N”

6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。

A.2 B.3 C.4 D.5

7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。

A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing” C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”

8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ ）。

A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1

9. 字符串采用结点大小为1的链表作为其存储结构，是指（ ）。

A.链表的长度为1

B.链表中只存放1个字符

C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符

二、填空题

1. 计算机软件系统中，有两种处理字符串长度的方法：一种是__固定长度__，第二种是___设置长度指针___。

2. 两个字符串相等的充要条件是___两个串的长度相等___和_____对应位置的字符相等__。 3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为__ “BCDEDE”__。 4. 串是指___含n个字符的有限序列 （n≥0）___。

5. 空串是指__不含任何字符的串__，空格串是指__仅含空格字符的字符串___。 三、算法设计题

1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m

int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串 char r[ ]; int s,t,m; { int i,j;

for(i=1;i<=m;i++)

r[s+i]=r[i]; for(j=m+t-i;j<=s;j++)

r[s-t+j]=r[j]; return (1); } //delete

2. 设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。 2．算法思想为：

（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；

（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较； （3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。

设单链表类型为LinkList；注意，此时类型 LinkList中的data成分为字符类型。

LinkString find(s,t) LinkString *s, *t; { LinkString *ps, *pt; ps=s;

while(ps!=NULL) { pt=t;

while((pt!=NULL)&&(ps->data!=pt->data)) pt=pt->next; if(pt= =NULL)

ps=NULL;

else

{ ps=ps->next;

s=ps;

} } return s; } //find

一、选择题

1、设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ C ）。

A. 连接 B. 求子串 C. 模式匹配 D. 判断子串

2、已知串S=’aaab’，则next数组值为（ A ）。

A. 0123 B. 1123 C. 1231 D. 1211 3、串与普通的线性表相比较，它的特殊性体现在（ C ）。

A. 顺序的存储结构 B. 链式存储结构 C. 数据元素是一个字符 D. 数据元素任意

4、设串长为n，模式串长为m，则KMP算法所需的附加空间为（ A ）。

A. O(m) B. O(n) C. O(m*n) D. O(nlog2m)

5、空串和空格串（ B ）。

A. 相同 B. 不相同 C. 可能相同 D. 无法确定

6、与线性表相比，串的插入和删除操作的特点是（ B ）。

A. 通常以串整体作为操作对象 B. 需要更多的辅助空间 C. 算法的时间复杂度较高 D. 涉及移动的元素更多 7、设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（ B ）。

A. ‘ijing’ B. ‘jing&’ C. ‘ingNa’ D. ‘ing&N’ 二、判断题

（ × ）1、造成简单模式匹配算法BF算法执行效率低的原因是有回溯存在。 （√ ）2、KMP算法的最大特点是指示主串的指针不需要回溯。 （√ ）3、完全二叉树某结点有右子树，则必然有左子树。 三、填空题

1、求子串在主串中首次出现的位置的运算称为 模式匹配 。 2、设s=’I︺AM︺A︺TEACHER’,其长度是__14__。

3、两个串相等的充分必要条件是两个串的长度相等且 对应位置字符相同 。 四、程序填空题

1、函数kmp实现串的模式匹配，请在空格处将算法补充完整。

int kmp(sqstring *s,sqstring *t,int start,int next[]){ int i=start-1,j=0;

while(ilen&&jlen)

if(j==-1||s->data[i]==t->data[j]){ i++;j++; }

else j= next[j] ; if(j>=t->len)

return( i=t->len+1 ); else

return(-1); }

2、函数实现串的模式匹配算法，请在空格处将算法补充完整。 int index_bf(sqstring*s,sqstring *t,int start){ int i=start-1,j=0;

while(ilen&&jlen)

if(s->data[i]==t->data[j]){ i++;j++; }else{

i= i-j+1 ;j=0; }

if(j>=t->len)

return i-t->len+1 ; else

return -1; }}/*listDelete*/

3、写出下面算法的功能。

int function(SqString *s1,SqString *s2){ int i;

for(i=0;ilength&&ilength;i++) if(s->data[i]!=s2->data[i])

return s1->data[i]-s2->data[i]; return s1->length-s2->length; }

答案：.串比较算法 4、写出算法的功能。

int fun(sqstring *s,sqstring *t,int start){ int i=start-1,j=0;

while(ilen&&jlen)

if(s->data[i]==t->data[j]){ i++;j++; }else{

i=i-j+1;j=0; }

if(j>=t->len)

return i-t->len+1; else

return -1; }

答案：串的模式匹配算法

一、基本概念

1、串的概念

2、空串与空格串的区别 3、子串与主串 4、串相等 5、串比较

6、串的模式匹配

7、串的模式匹配算法（BF、KMP、注意指针i，j的变化，模式串的next值） 二、练习题

1．以下叙述中正确的是 。 A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中无素只能是字母 D.空串就是空白串 3．串是一中特殊的线性表，其特殊性体现在____。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符

本文来源：https://www.bwwdw.com/article/lo5o.html