当前位置：文档之家 › 第四章 串

第四章 串

  • 格式：doc
  • 大小：31.00 KB
  • 文档页数：2

下载文档原格式

  / 2

合集下载

严蔚敏数据结构-第四章 串

严蔚敏数据结构-第四章 串
S1 4 a b c d S2 2 e f T 6 a b c d e f
15
(2)S1串长 最大串长 串长<最大串长 串长 最大串长; S1,S2串长和 最大串长 串长和>最大串长 串长和 最大串长;
S1 6 a b c d e f S2 6 g h i j k l T 8 a b c d e f g h
3
串的抽象数据类型的定义： 串的抽象数据类型的定义： ADT String{ 数据对象： 数据对象：D={ai|ai∈CharacterSet, i=1,2,...,n, n>=0} 数据关系： 数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=2,...,n} 基本操作： 基本操作： StrAssign(&T, chars)
11
作业： 作业： 1.用5种串的基本操作（StrAssign、StrCompare、StrLen Concat、SubString）来逻辑实现StrInsert(&S, pos, T)操作 、 操作. ）
Status StrInsert(String S, int pos , String T) { if ……….. return error; , , ); ); ); );
chars是字符串常量。生成一个其值等于chars的串 。 是字符串常量。生成一个其值等于 的串T。 是字符串常量 的串
StrCopy(&T, S)
存在则由串S复制得串 串S存在则由串 复制得串 存在则由串 复制得串T
StrEmpty(S)
存在则若S为空串 串S存在则若 为空串 返回真否则返回假 存在则若 为空串,返回真否则返回假
Sub返回串 的第pos个字符起长度为 返回串S的第 个字符起长度为len的子串 用Sub返回串S的第pos个字符起长度为len的子串

第四章串A

第四章串A

（1）初始化ClearString（S）：初始化串S(串S存 在，将S清为空串)。 （2）StrAssign（&T，char）：生成串。
（3）StrCopy(&T，S)：串复制(将串S复制到串T)。5
第4 章 串
（4）Concat（&T，s1，s2）:串联接(用T返回S1,S2 联接而成的新串)。 （5）求串长StrLength（S）：返回S串的元素个数， 即S串的长度。 （6）串比较StrCompare（S，T） （7）求子串SubString（&Sub，S，pos，len）： 返回s串的第pos个字符起始的长度为len的子串。 （8）插入运算SetInsert（&S，T，pos）：把串t的 值插入到串s的第pos个字符之后。 （9）删除运算StrDelte（&S，pos，len）：将串s
可能出现如下三种情况： a. S1长度+S2长度<=T长度，则S1+S2可以完整放入T中； b. S1长度+S2长度>T长度，则S1完整放入，S2放入一部 分； c. S1长度=T长度，则S1完整放入，S2不能放入。 注意：各串长度数据放入该串的 0 单中。（如图4.1示）
11
第4 章 串
两串联结的C语言程序 (算法4.2)
{ int i; orderstribg *r ;
printf(“ r1=%s,r2=%s\n”,r1.vec,r2.vec);
if (r1.len+r2.len>m0) printf(“上溢出\n”) ; /* 若两串长度之和大于m0，则进行溢出处理*/
12
第4 章 串
else { for (i=0; i<r1.len; i++) r.vec[i]=r1.vec[i]; for (i=0; i<r2.len;i++) /*将串r2传r */ r.vec[r1.len+ i ]= r2.vec[i]; r.vec[r1.len+ i ]=“\0” ; /*最后一个位置赋给\0 */ r.len=r1.len+r2.len; } return(r); } /*r串长度等于两串长度之和*/ /*将串r1传给r */

《数据结构与算法(C++语言版)》第4章_串

《数据结构与算法(C++语言版)》第4章_串

串函数与串的类定义
• 常用的 常用的C++串函数 串函数 • C++的串库（string.h）中提供了许多字符串的操作函数，几 个常用的C++字符串函数及其使用方法如下。 •假设已有以下定义语句：
串函数与串的类定义
• （1）串拷贝函数 • char *strcpy(char *s1, const char *s2)，将字符串s2复制到字 符串数组s1中，返回s1的值。 • char *strncpy(char *s1, const char *s2, size_tn)将字符串s2中最 多n个字符复制到字符串数组s1中，返回s1的值。 • 例如：
串函数与串的类定义
• （3）串比较函数 • int strcmp(const char *s1, const char *s2)，比较字符串s1和字 符串s2。函数在s1等于、小于或大于s2时，分别返回0、小 于0或者大于0的值。 • int strncmp(const char *s1, const char *s2, size_tn)比较字符串 s1中的n个字符和字符串s2。函数在s1等于、小于或大于s2 时，分别返回0、小于0或者大于0的值。 • 例如：
串模式匹配
• 无回溯的匹配算法 • 在上面介绍的匹配算法中，某趟匹配失败时，下一趟的匹 配相当于将子串P后移1位再从头与主串中对应字符进行比 较，即相当于i指示器回溯到上趟（最近失败的一趟）匹配 的起点的下一个位置，这样，主串中每个字符都要与子串 中的第1个字符对应一次，再向后比较。因此，主串中每个 字符参加比较的次数最多可达n次（n为子串长度），因此 时间复杂度为O(nm)。那么，能否使目标串中每个字符只参 加一次比较呢？也就是说，能否不回溯i指示器？回答是肯 定的。这个问题是由D.E.Knoth与V.R.Pratt和J.H.Morris同时 解决的，所以有的文献也称这种思想的串匹配算法为KMP 算法。

数据结构——第4章 串(C#)

数据结构——第4章 串(C#)
将当前链串的所有结点?nstr将q结点插入到尾部将q结点插入到尾部将链串t的所有结点?nstr将q结点插入到尾部尾结点的next置为null返回新建的链串5求子串substrij返回当前串中从第i个字符开始的连续j个字符组成的子串ຫໍສະໝຸດ 第4章 串4.1 串的基本概念
4.1.1 什么是串 串（或字符串）是由零个或多个字符组成的有限序列。 记作str="a1a2…an"（n≥0），其中str是串名，用双引号括 起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一 个任意字符（字母、数字或其他字符），它称为串的元素， 是构成串的基本单位，串中所包含的字符个数n称为串的 长度，当n=0时，称为空串。
4.2 串的存储结构
4.2.1 串的顺序存储结构－顺序串
和顺序表一样，用一个data数组（大小为MaxSize）和 一个整型变量length来表示一个顺序串，length表示data数 组中实际字符的个数。 定义顺序串类SqStringClass如下：
class SqStringClass { const int MaxSize=100; public char[] data; //存放串中字符 public int length; //存放串长 public SqStringClass() //构造函数,用于顺序串的初始化 { data=new char[MaxSize]; length=0; } //顺序串的基本运算 }
（9）串输出DispStr() 将当前串s的所有字符构成一个字符串并输出。对应的算 法如下：
public string DispStr() { int i; string mystr=""; if (length==0) mystr = "空串"; else { for (i=0;i<length;i++) mystr+=data[i].ToString(); } return mystr; }

第4章 字符串v

第4章 字符串v

空串： 空串： 长度为0的字符串 的字符串； 长度为 的字符串； 空格串： 空格串： 由空格字符组成的字符串，长度>1 由空格字符组成的字符串，长度 主串： 主串： 包含该子串的字符串; 包含该子串的字符串; 字符的位置： 字符的位置： 从1开始 开始 子串的位置： 子串的位置： 该子串第一个字符的位置
定长顺序存储标识串的实际长度时可有三种方式： 定长顺序存储标识串的实际长度时可有三种方式：
（1）用一个指针指向最后一个字符，串描述类似顺序表 用一个指针指向最后一个字符， 用一个指针指向最后一个字符 #define MAXSIZE 256 typedef struct { char data[MAXSIZE]; int curlen; }SeqString; 定义一个串变量：SeqString s; 定义一个串变量
1.串的 定长 顺序存储 串的（定长 串的 定长）顺序存储
（定长 顺序存储结构类似于C语言的字符数组，以一 定长）顺序存储结构类似于 语言的字符数组， 定长 顺序存储结构类似于 语言的字符数组 组地址连续的存储单元存放串值中的字符序列， 组地址连续的存储单元存放串值中的字符序列，定长即是预 先为每一个串变量分配一个固定长度的存储区，例如： 先为每一个串变量分配一个固定长度的存储区，例如： #define MAXSIZE 256 char s[MAXSIZE] 那么，串的最大长度就不能超过 那么，串的最大长度就不能超过256。 。
第4章 串 章
4.1 字符串的基本概念
4. 2 串的存储结构
4.3 模式匹配
（1） 串的基本概念
串(string)是由零个或多个任意字符组成的字符序列， )是由零个或多个任意字符组成的字符序列， 又称为字符串( 又称为字符串(character string)，一般记为: ) 一般记为: s=〝a1 a2 a3 … an〞

数据结构第4章 串

数据结构第4章 串
ring s, SString t)
/*若串s和t相等则返回0；若s>t则返回正数；若s<t则返 回负数*/
{ int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]);
初 始 条 件 : 串 S 存 在 ,1≤pos≤StrLength(S) 且 1≤len≤StrLength(S)-pos+1
操作结果:用Sub返回串S的第pos个字符起长度为len的子串
返回主目录
（11）StrIndex(S,T,pos)
初始条件: 串S和T存在,T是非空串, 1≤pos≤StrLength(S)
return(s.len); }
返回主目录
（7）清空函数
StrClear(SString *s) /*将串s置为空串*/ {
s->len=0; }
返回主目录
（8）连接函数
(1) 连接后串长≤MAXLEN，则直接将B加在A的 后面。 (2) 连接后串长>MAXLEN且LA<MAXLEN，则B 会有部分字符被舍弃。 (3) 连接后串长>MAXLEN且LA=MAXLEN，则B 的全部字符被舍弃（不需连接）。
for (i=s->len + t.len-1;i>=t.len + pos;i--)
s->ch[i]=s->ch[i-t.len];
for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i];
s->len=s->len+t.len;

数据结构-第4章 串

真子串是指不包含自身的所有子串。
4.1 串的类型定义
子串的序号：将子串在主串中首次出现时的该 子串的首字符对应在主串中的序号，称为子串 在主串中的序号（或位置）。 【例】 A=“abcdefbbcd”，B=“bcd”，B在A中的 序号为2。 特别地，空串是任意串的子串，任意串是其自 身的子串。
4.1.2 串的抽象数据类型定义
//查找ab子串
if (p->data==‘ a’ && p->next->data==‘b’)
{ p->data=‘x’; p->next->data=‘z’;
q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data=‘y’;
q->next=p->next; p->next=q;
s: a a a a b c d
t: a ab bac acb bc c ✓ 匹配成功 算法的思路是从s的每一个字符开始依次与t的 字符进行匹配。
4.2.1 Brute-Force算法
int BFIndex(SqString s,SqString t)
{ int i=0, j=0,k;
while (i<s.length && j<t.length)
4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法
本章要求
理解： 1、串的基本概念、类型定义 2、串的存储表示和实现 3、串的KMP算法
掌握： 4、串的简单模式匹配算法(BF)
第4章 串的基本概念
串（或字符串）：是由零个或多个字符组成 的有限序列。
串的逻辑表示： S=“a1a2…ai…an”，其中S为 串名，ai (1≤i≤n)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。

《数据结构与算法》第四章-学习指导材料

《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。

4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。

一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。

２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。

包含子串的串相应地称为主串。

子串的位置：子串的第一个字符在主串中的序号称为子串的位置。

串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。

4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。

4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。

如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。

如图4.1所示。

s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。

第四章 串

主串S首次出现的位置；否则返回0
– 例如
• 主串S = • 子串T = CD • 则index(S,T)，返回子串T在S中，第一次出现的位置3
19
串的模式匹配
Brute-Force算法基本思想： • 从目标串s 的第一个字符起和模式串t的第一个字符进行比较 • 若相等，则继续逐个比较后续字符，否则从串s 的第二个字 符起再重新和串t进行比较。 • 依此类推，直至串t 中的每个字符依次和串s的一个连续的字 符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。
两式联立可得：“T0…Tk-1”= “Tj-k…Tj-1”
注意：j为当前已知的失配位置，我们的目标是计算新起点k。式中仅剩 一个未知数k，理论上已可解！
奇妙的结果：k仅与模式串T有关！
27
新起点k怎么求？
根据模式串T的规律：“T0…Tk-1”=“Tj-k …Tj-1” 由当前失配位置j(已知)，归纳计算新起点k的表达式。
j=next[j]的位置(即模式串继续向右移动)，再比较 si 和 tj 。
依次类推，直到下列两种情况之一： 1)j退回到某个j=next[j]时有 si = tj，则指针各增1，继续匹配； 2)j退回至j=0，此时令指针各增1，即下一次比较 si+1和 t0 。
30
串的模式匹配：KMP算法
• 模式串的next函数
6
串的基本概念
4.两个字符串相等的充分必要条件为两个字符串的长度相等，并 且对应位置上的字符相等。
例如：‘abcd’ ≠ ‘bacd’ ‘abcd’ = ‘abcd’
7
串的基本操作
1.给串变量赋值 ASSIGN(S1,S2)

数据结构第四章串


(2) 置换操作：用联接算法来实现。用在求子串序号（a,b，h）中得到的 ind 将a分成3部分：第一部分是b在a中的第一个位置前的子串substr （a,1,ind－1）;第二部分是b（以c来代替）；第三部分是b在a中的最后一个 位置后的子串substr（a,ind+m,n）。 即 a substr(a,I,ind-1)||c||substr(a,ind+m,n)
4. 2 串的基本运算
对于串的基本操作，许多高级语言均提供了相应的运算或标准 库函数来实现。下面仅介绍几种常用的串运算。 (1)联接(concatenation) 联接是串的最基本，最重要的运算。两个串的联接是将一个串 紧接着放在另一个串的末尾。联接用符号“||”表示。 例如：a＝”bei” b=“jing” a || b=“beijing” (2)求子串(substr) SUBSTR(a，m，n)功能: 从a 中截取子串，从第m个字符到第n个 字符的子串（m<n)。子串应是将串a中取出从标号m开始的连续n －m＋1个字符。 例：SUBSTR(“ABCDEFG”,2,3)＝”BC” 利用求子串及联接两种运算可以完成对串的插入、删除和修改。 例如： a＝“bejing” b=“iy” ，将b插入到a的第二个字符之后 得到新的串s，则 s=substr(a,1,2) || b || substr(a,3,6) =“beiyjing”
（5）置换(repleace) 置换运算repleace(a,b,c)表示在a中搜索b，若b是a的 子串，就以c代替b，若不是，则经置换后，a不变。 例如：a=“monday”, b=“mon”, c=“thurs” repleace(a,b,c)=“thursday” 置换运算是将串a中所有的子串b用c来代替。 在一部分程序设计语言中没有实现，仍可用前三种运 算来完成。 置换算法过程：实现置换运算repleace（a,b,c），同 样也是在a中搜索是否与b相同的子串，若有，以c来代 替，再继续向下搜，直到在a中找不到和b相同的子串 为止。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第四章串
一．选择题
1.如下陈述中正确的是________。

A．串是一种特殊的线性表 B．串的长度必须大于零
C．串中元素只能是字母 D．空串就是空白串
2.字符串的长度是指________。

A．串中不同字符的个数 B．串中不同字母的个数
C．串中所含字符的个数 D．串中不同数字的个数
3.两个字符串相等的充要条件是________。

A．两个字符串的长度相等 B．两个字符串中对应位置上的字符相等
C．同时具备A和B两个条件 D．以上答案都不对
4.串是________。

A．不少于一个字母的序列 B．任意个字母的序列
C．不少于一个字符的序列 D．有限个字符的序列
5.下列关于串的叙述中，正确的是________。

A．串长度是指串中不同字符的个数
B．串是n个字母的有限序列
C．如果两个串含有相同的字符，则它们相等
D．只有当两个串的长度相等，并且各个对应位置的字符都相符时才相等
6.串是一种特殊的线性表，其特殊性体现在________。

A．可以顺序存储 B．数据元素是一个字符
C．可以链接存储 D．数据元素可以是多个字符
7.设有两个串p和q，求q在p中首次出现的位置的运算称作________。

A．连接 B．模式匹配 C．求子串 D．求串长
8.设串s1="ABCDEFG",s2="PQRST",函数con(x,y)返回x 和y串的连接串。

subs(s，i,j)返回串s 的从序号 i 的字符开始的j个字符组成的子串，len(s) 返回串s的长度，则con(subs(s1,2,1en(s2))，subs(sl,len(s2)，2)) 的结果串是________。

A．BCDEF B．BCDEFG C．BCPQRST D.BCDEFEF
9．函数substr("DATASTRUCTURE"，5，9)的返回值为________。

A．"STRUCTURE" B．"DATA"
C．"ASTRUCTUR" D. "DATASTRUCTURE"
10．设串S="I AM A TEACHER",其长度是________。

A. 16
B. 11
C.14
D. 15
11.设字符串s1="abcdefg",s2="pqrst"，则运算
s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为________。

A. "bcdef"
B. "bcdefg"
C."bcpqrst"
D."bcdefef"13
12.设有一个字符串S= "windows"，求子串的数目是________。

A．25 B．26 C．27 D. 28
二. 填空题
1. _______________称为空串；_______________________称为空白串。

2. 一个串的任意个连续的字符组成的子序列称为该串的______，包含该子串的串称为____。

三．简答题
1．空串与空格串有什么区别？字符串中的空格有什么意思？空串在串的处理中有什么作用？
2．串是由字符组成的，长度为1的串和字符是否相同？为什么？
3．简述串的静态顺序存储结构与动态顺序存储结构有什么区别，分别写出它们的结构体定义。

4．字符串采用静态顺序存储结构。

编写一个算法删除S中第i个字符到第j个字符。

5．编写一个算法判断s2是否是s1的子串。

6.下列程序段的功能实现子串t 在主串s 中位置的算法，要求在下划线处填上正确语句。

int index(char s[], char t[])
{
int i=0,j=0;
while(i<strlen(s)&& j<strlen(t))
if(s[i]==t[j])
{
i=i+l;
j=j+l;
}
else
{
i=_______;
j=______;
}
if (j==strlen(t))
return(i-strlen(t));
else
return (-1);
}。