第四章串 1.教学内容:41串及其基本运算 4.2串的定长顺序存储及基本运算 4.3串的堆存储结构 2教学目的:(1)了解串的定义 (2)理解和领会串的存储方式 (3)掌握常用的串运算。 3.教学重点:(1)串的基本概念、基本运算 (2)串的两种存储方式。 (3)串的模式匹配算法 4.、教学难点:(1)串的模式匹配算法 (2)串的基本运算的综合应用 5学时安排:4学时 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 1 第四章 串 ⒈教学内容：4.1 串及其基本运算 4.2 串的定长顺序存储及基本运算 4.3 串的堆存储结构 ⒉教学目的：⑴了解串的定义； ⑵理解和领会串的存储方式； ⑶掌握常用的串运算。 ⒊教学重点：⑴串的基本概念、基本运算； ⑵串的两种存储方式。 ⑶串的模式匹配算法。 ⒋教学难点：⑴串的模式匹配算法； ⑵串的基本运算的综合应用 ⒌学时安排： 4学时
4.1串及其基本运算 ◆串的基本概念 ◆串的基本运算 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 2 4.1 串及其基本运算 串的基本概念 串的基本运算
4.1.1串的基本概念 串是由零个或多个任意字符组成的字符序列。一般记 S=S 其中s是串名;在本书中,用双引号作为串的定界符, 引号引起来的字符序列为串值,引号本身不属于串的内 a(1<=i<=n)是一个任意字符,它称为串的元素,是 构成串的基本单位,i是它在整个串中的序号 n为串的长度,表示串中所包含的字符个数,当n=0时, 称为空串,通常记为 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 3 4.1.1 串的基本概念 串是由零个或多个任意字符组成的字符序列。一般记 作：s= ”s1 s2 … sn ” 。 其中s 是串名；在本书中，用双引号作为串的定界符， 引号引起来的字符序列为串值，引号本身不属于串的内 容； ai(1<=i<=n)是一个任意字符，它称为串的元素，是 构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时， 称为空串，通常记为Ф
子串与主串: 串中任意连续的字符组成的子序列称为该串的子串。包 含子串的串相应地称为主串。 子串的位置: 子串的第一个字符在主串中的序号称为子串的位置。 串相等: 称两个串是相等的,是指两个串的长度相等且对应字符 都相等。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 4 •子串与主串： 串中任意连续的字符组成的子序列称为该串的子串。包 含子串的串相应地称为主串。 •子串的位置： 子串的第一个字符在主串中的序号称为子串的位置。 •串相等： 称两个串是相等的，是指两个串的长度相等且对应字符 都相等
4.1.2串的基本运算 求串长 StrEngth(s) 操作结果是求出串s的长度。 2串赋值 StrAssign(s,s2) s1是一个串变量,S2或者是一个串常量,或者是一个串变量(通常s2是一个串常量时称为串赋值, 是一个串变量称为串拷贝),操作结果是将52的串值赋值给s1,s原来的值被覆盖掉。 3连接操作 StrConcat(s12,s)或 StrConcat(s1,s2) 两个串的连接就是将一个串的串值紧接着放在另一个串的后面,连接成一个串。前者是产生新串s, s1和s2不改变;后者是在s1的后面联接s2的串值,s1改变,S2不改变。 4求子串 Substr(s,len) 串s存在并且1≤≤ StrEngth(s),0≤len≤ StrEngth(s)-+1。操作结果是求得从串s的第个字符开 始的长度为|en的子串。len=0得到的是空串。 5串比较 Strcmp(s1,s2) 操作结果是若s1=s2,操作返回值为0:若sls2,返回值>0 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 5 4.1.2 串的基本运算 ⒈求串长 StrLength(s) 操作结果是求出串s的长度。 ⒉串赋值 StrAssign(s1,s2) s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2 是一个串常量时称为串赋值， 是一个串变量称为串拷贝），操作结果是将s2的串值赋值给s1， s1原来的值被覆盖掉。 ⒊连接操作 StrConcat (s1,s2,s) 或 StrConcat (s1,s2) 两个串的连接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。前者是产生新串s， s1和s2不改变; 后者是在s1的后面联接s2的串值，s1改变， s2不改变。 ⒋求子串 SubStr (s,i,len) 串s存在并且1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果是求得从串s的第i个字符开 始的长度为 len 的子串。len=0得到的是空串。 ⒌串比较 StrCmp(s1,s2) 操作结果是若s1==s2，操作返回值为0；若s1s2，返回值>0
6.子串定位 StrIndex(s,t) s为主串,t为子串,操作结果是若t∈s,则操作返回t在s中首次出现的位置, 否则返回值为0。 7串插入 StrInsert(s, i, t) 串st存在,且1si≤ Strength(s)+1。操作结果是将串埔插入到串s的第个字符位 置上,s的串值发生改变。 8串删除 StrDelete(s, i, len) 串s存在,并且1≤ StrEngth(s),0≤en≤ StrEngth(s}计+1。操作结果是删除串s 中从第个字符开始的长度为en的子串,s的串值改变。 9.串替换 StrEp(str) 串str存在且t不为空,操作结果是用串r替换串s中出现的所有与串t相等的不 重叠的子串,s的串值改变。 串的基本操作中前5个操作是最为基本的,它们不能用 其他的操作来合成,因此通常将这5个基本操作称为最小 操作集。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 ⒍子串定位 StrIndex(s,t) s为主串，t为子串，操作结果是若t∈s，则操作返回t在s中首次出现的位置， 否则返回值为0。 ⒎串插入 StrInsert(s,i,t) 串s,t存在，且1≤i≤StrLength(s)+1。操作结果是将串t插入到串s 的第i个字符位 置上，s的串值发生改变。 ⒏串删除 StrDelete(s,i,len) 串s存在，并且1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果是删除串s 中从第i个字符开始的长度为len的子串，s的串值改变。 ⒐串替换 StrRep(s,t,r) 串s,t,r存在且t不为空，操作结果是用串r 替换串s中出现的所有与串t相等的不 重叠的子串，s的串值改变。 • 串的基本操作中前５个操作是最为基本的，它们不能用 其他的操作来合成，因此通常将这５个基本操作称为最小 操作集
4.2串的定长顺序存储及基本 运算 ◆串的定长顺序 ◆定长顺序串的基本运 ◆模式匹配 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 4.2 串的定长顺序存储及基本 运算 串的定长顺序存储 定长顺序串的基本运算 模式匹配
4.2.1串的定长顺序存储 ◆用一组地址连续的存储单元存储串值中的字符序列, 所谓定长是指按预定义的大小,为每一个串变量分配 个固定长度的存储区,如: #define maXsize 256 char SIMAXSIZE 则串的最大长度不能超过256 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 4.2.1 串的定长顺序存储 用一组地址连续的存储单元存储串值中的字符序列， 所谓定长是指按预定义的大小，为每一个串变量分配一 个固定长度的存储区，如： #define MAXSIZE 256 char s[MAXSIZE]; 则串的最大长度不能超过256
如何标识实际长度? 类似顺序表,用一个指针来指向最后一个字符,这样表 的串描述如下: typedef struct i char data MAXSIZE int curlen 3 Seqstring 定义一个串变量: SeqString s 这种存储方式可以直接得到串的长度: s curlen+1。如图 所示。[ MAXSIZE a hijk□「 s aren 串的顺序存储方式 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 如何标识实际长度？ 1. 类似顺序表，用一个指针来指向最后一个字符，这样表 示的串描述如下： typedef struct { char data[MAXSIZE]; int curlen; } SeqString; 定义一个串变量：SeqString s; 这种存储方式可以直接得到串的长度：s.curlen+1。如图 所示
2.在串尾存储一个不会在串中出现的特殊字符作为串的终 若符,以此表示串的结尾。比如C语言中处理定长串的方 法就是这样的,它是用’10来表示串的结束。这种存储方 法不能直接得到串的长度,是用判断当前字符是否是0 来确定串是否结束,从而求得串的长度。 char SIMAXSIZE 2345 MAXSIAE I abcdefg ko■ 串的顺序存储方式2 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 2. 在串尾存储一个不会在串中出现的特殊字符作为串的终 结符，以此表示串的结尾。比如C语言中处理定长串的方 法就是这样的，它是用’\0’来表示串的结束。这种存储方 法不能直接得到串的长度，是用判断当前字符是否是’\0’ 来确定串是否结束，从而求得串的长度