第四章串 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:若sl<s2,返回值<0;若s1>s2,返回值>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；若s1<s2，返回值<0；若s1>s2，返回值>0