第三章串1解读.pptx

第三章 串 第二章回顾 线性表的定义 顺序存储结构的特征 顺序存储结构的操作 链式存储结构特征 链式存储结构操作 多项式应用 教学内容 3.1 串抽象数据类型 3.2 串的表示和实现 3.3 串的模式匹配 3.3.1 Brute-Force算法 3.3.2 KMP算法 目的和要求 目的：串作为特殊线性表的实现与应用。 内容：字符串的基本概念，串抽象数据类型，顺序和链式两种存储结构存储串的特点；采用顺序存储结构实现串的各种操作算法；两种串的模式匹配算法及应用：Brute-Force算法和KMP算法。 要求：掌握顺序串类的基本操作实现方法，掌握串的模式匹配算法及应用。 重点：串数据类型的各种操作实现，两种串的模式匹配算法及应用。 难点：KMP模式匹配算法，next数组在KMP算法中的作用及产生过程。 3.1 串抽象数据类型 3.1.1 串的基本概念 串（字符串，String）：是由 0 个或多个字符组成的有限序列。 通常记为：s =“s0s1s2s3…sn-1” ( n≥1 )。 串的名 串的值 串的长度 字母、数字或其他字符 引号””必须有！！！ 串是一种特殊的线性表！ 双引号的作用 例：x = “123” x = 123 test =“test” 作用：避免字符串与变量名或数的常量混淆。 空串：不含任何字符的串，长度 = 0，用符号 ? 表示。 空格串：仅由一个或多个空格组成的串。例如at是data的子串。 子串：由串中任意个连续的字符组成的子序列。 主串：包含子串的串。 位置：字符在序列中的序号。 子串在主串中的位置：子串的首字符在主串中的位置。 例：S=“DALIAN” S1=“” (? ) S2=“LIAN” S3=“DALIAN” —— 均为 S 的子串。 S4=“LAN” —— 非 S 的子串 （非串 S 中的连续字符所组成）。 在 S 中的位置：3 在 S 中的位置：1 串相等的条件：当两个串的长度相等且各个对应位置 的字符都相等时才相等。 例：S=“DALIAN” S1=“DA LIAN” S S1 ? 空串是任意串的子串，任意串是其自身的子串。 双引号与单引号区别！ 1、含义不同。 用单引号引起的一个字符实际上代表一个整数，整数值对应于该字符在编译器采用的字符集中的序列值。而一般我们的编译器采用的都是ASCII字符集。因此s的含义其实和十进制数115的含义是一致的。 而用双引号引起的字符串，代表的是一个指向无名数组起始字符的指针。 2、大小不同。 用单引号引起的一个字符大小就是一个字节。 而用双引号引起的字符串大小是字符的总大小+1，因为用双引号引起的字符串会在字符串末尾添加一个二进制为0的字符\0。 扩展内容—转义 如何输出带引号的字符串？ System.out.println(Jane Campion directed /The Piano/ in 1993.); 输出结果： Jane Campion directed The Piano in 1993. Java转义表 特殊字符 显示 / 单引号 / 双引号 // 反斜线 /t 制表符 /b 回退符 /r 回车符 /f 走纸符 /n 换行符 System.out.println(Music by/nMichael Nyman); Music by Michael Nyman 输出 举例： 串比较 两个串相等的条件是 （1）长度相同 （2）对应位置上的字符也相同 举例：假设有两个字符串“aabb”与“aacb”，如何比较大小？ 3.1.2 串抽象数据类型 public interface SString { int length(); //返回串的长度 char charAt(int i) //返回第i（i≥0）个字符 SString concat(SString str); //返回与str串连接生成串 SString substring(int begin, int end); //返回串中字符序号从begin至end-1的子串 void setCharAt(int i, cha