数据结构第四章串

数据结构第四章串Tag内容描述：<p>1、第4章 串 4.1 串的基本概念 4.2 串的存储结构 本章小结 4.3 串的模式匹配 串(或字符串),是由零个或多个字符组成的有穷序 列。含零个字符的串称为空串,用表示。 串中所含字符的个数称为该串的长度(或串长)。 通常将一个串表示成“a1a2an“的形式。其中,最 外边的双引号本身不是串的内容,它们是串的标志,以 便将串与标识符(如变量名等)加以区别。每个 ai(1in)代表一个字符。 4.1 串的基本概念 当且仅当两个串的长度相等并且各个对应位置上 的字符都相同时,这两个串才是相等的。 一个串中任意个连续字符组成的子序列(含空串,但 不含串本身)称。</p><p>2、第四章 串重点难点理解串类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法； 理解串的两种匹配算法。典型例题 1、简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串； 【解】（1）空串是指不包含任何字符的串，它的长度为零。空白串是指包含一个或多个空格的串，空格也是字符。（2）串常量是指在程序中只可引用但不可改变其值的串。串变量是可以在运行中改变其值的。（3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个。</p><p>3、数 据 结 构,李 鑫 辽宁工程技术大学电信学院,2019/5/19,数据结构,2,内 容 安 排,2019/5/19,数据结构,3,第4章 串（String）,4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法,2019/5/19,数据结构,4,记为： s = a1 a2 an (n0 ),串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,4.1 串类型的定义,隐含结束符0 ，即ASCII码NULL,为何要单独讨论“串”类型？ 1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作） 2） 程序设计中，处理对象很多都是串类型。,2019/5/19,数据结构,5,若干术语：。</p><p>4、第4章 串,4.1 串的基本概念及其抽象数据 4.2 串的存储结构 4.3 串类 4.4 串的模式匹配算法,本章主要知识点： 串的基本概念 串的存储结构 串类的设计方法，主要是拷贝、插入子串和删除子串的设计方法 串的模式匹配算法，包括Brute-Force算法和KMP算法,4.1 串的基本概念及其抽象数据类型,4.1.1 串的基本概念 串（也称作字符串）是由n（n0）个字符组成的有限序列。 一个串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串称为该子串的主串。 一个字符在一个串中的位置序号（为大于等于0的正整数）称为该字符在串中的位置。当且。</p><p>5、1,1.令s=aaab,t=abcabaa, u=abcaabbabcabaacbacba 试分别求出它们的next函数值和nextval函数值 2.已知主串s=ADBADABBAABADABBADADA, 模式串pat=ADABBADADA, 写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程,布置第4章作业：,2,第4章 串（String）,4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法,3,算法目的：确定主串中所含子串第一次出现的位置（定位）,4.3 串的模式匹配算法,BF算法 （又称古典的、经典的、朴素的、穷举的） KMP算法,算法种类：,带回溯，速度慢,避免回溯，匹配速度快， 是全课程的亮点之一,定位。</p><p>6、第四章 串,4.1 串的抽象数据类型的定义,4.2 串的表示和实现,4.3 串的模式匹配算法,4.1 串的抽象数据类型的定义如下：,ADT String ,数据对象：,D ai |aiCharacterSet, i=1,2,.,n, n0 ,数据关系：,R1 | ai-1, ai D, i=2,.,n ,串是有限长的字符序列，由一对单引号相括，如: a string,基本操作：,StrAssign (&T, chars),StrCopy (&T, S),DestroyString(&S),StrEmpty (S),StrCompare (S, T),StrLength(S),Concat (&T, S1, S2),SubString (&Sub, S, pos, len),Index (S, T, pos),Replace (&S, T, V),StrInsert (&S, pos, T),StrDelete (&S, pos,。</p>