《数据结构与算法分析》课程教学课件（PPT讲稿）第四章 串

第四章串

串即字符串，几乎所有的语言都把它定 义为固有的数据类型，不用我们自己去定 义，我们直接可以利用系统提供给我们的 字符串类型以及有关于字符串的基本操作， 所以这一章只讲关于串的一些基本概念和 JAVA语言给我们设计好的字符串类型。 同学们如果发现JAVA系统提供给我们 的字符串类型中的基本操作不够用、或不 好用，再考虑自己去定义

串即字符串，几乎所有的语言都把它定 义为固有的数据类型，不用我们自己去定 义，我们直接可以利用系统提供给我们的 字符串类型以及有关于字符串的基本操作. 所以这一章只讲关于串的一些基本概念和 JAVA语言给我们设计好的字符串类型。 同学们如果发现JAVA系统提供给我们 的字符串类型中的基本操作不够用、或不 好用，再考虑自己去定义

串的基本概念 1、串定义：n(n≥0)个字符组成的有限序列。一般 记为s=“a1,a2,a3,.( n为 线性表是由n(n≥0)个类型相同的数据元素组成 的有限序列。 串也是线性表，只不过限定它的数据元素类型是 字符型。 2、串长度：串中包含的字符个数。 a=LIMING” 字符串a的长度为？。 b=“DATA STRUCTURE”字符串b的长度 为？。 3、空串：不包含任何字符的串。“” 空串的长度为？

一、串的基本概念 1、串定义：n（n≥0）个字符组成的有限序列。一般 记为s = “a1,a2, a3, . an” 线性表是由n（n≥0）个类型相同的数据元素组成 的有限序列。 串也是线性表，只不过限定它的数据元素类型是 字符型。 2、串长度：串中包含的字符个数。 a =“LIMING” 字符串a的长度为？。 b = “ DATA STRUCTURE” 字符串b的长度 为？。 3、空串：不包含任何字符的串。“” 空串的长度为？

4、空格串：有一个或多个空格组成的串。“” 空格串的长度是串中空格字符的个数。 5、串相等： 当且仅当两个串长度相同，并且各个对应 位置的字符都相同； “abc”？“abc “abc”？“abc” 6、子串：串中任意个连续的字符组成的子序列 称为该串的子串。 “DATA STRUCTURE

4、空格串：有一个或多个空格组成的串。“ ” 空格串的长度是串中空格字符的个数。 5、串相等： 当且仅当两个串长度相同，并且各个对应 位置的字符都相同； “abc” ？“abc” “abc” ？“ab c” 6、子串：串中任意个连续的字符组成的子序列 称为该串的子串。 “DATA STRUCTURE

二、串的存储方式 1、顺序存储把字符串中的数据元素存储在 组编号连续的的存储单元中，在JAVA语言中 把字符串放在一维数组中

二、串的存储方式 1、顺序存储 把字符串中的数据元素存储在一 组编号连续的的存储单元中，在JAVA语言中 把字符串放在一维数组中

。 2链式存储 把字符串中的数据元素存储在一组 编号不连续的的存储单元中，并在每个 数据元素后附设一个引用（指针）指示 其后继的地址。 串“ABCDEFGHI的链式存储结构 (请同学们自画)

• 2链式存储 把字符串中的数据元素存储在一组 编号不连续的的存储单元中，并在每个 数据元素后附设一个引用（指针）指示 其后继的地址。 串 “ABCDEFGHI”的链式存储结构 （请同学们自画）

因为字符型元素占用空间较小，也可以一个 结点存放好几个数据元素。由于串长并不一 定是结点中存放元素个数的整数倍，链表中 最后一个节点不一定全被占满，此时通常补 上“#“或其它的非串值字符

A B C D E F G H I J # # ^ A B C . I ^ 因为字符型元素占用空间较小，也可以一个 结点存放好几个数据元素。由于串长并不一 定是结点中存放元素个数的整数倍，链表中 最后一个节点不一定全被占满，此时通常补 上“#”或其它的非串值字符

三、JAVA语言中的字符串类型 Java为String类定义了许多方法。可以通过 下述格式调用Java定义的方法： .〈方法名>： 下表列出了Stringa类的常用方法

三、 JAVA语言中的字符串类型 Java为String类定义了许多方法。可以通过 下述格式调用Java定义的方法： .； 下表列出了String类的常用方法

String类的常用方法 方法 说明 public int length() 返回字符串的长度。 public boolean 将给定字符串与当前字符串相比较， equals(Object anObject) 若两字符串相等，则返回true,否则 返回false. public String 返回字符串中从beginIndex开始的子 substring(int beginIndex) 串。 public String 返回从beginIndex开始到endIndex-I的 substring(int beginIndex,int 子串。 endIndex) public char charAt(int index) 返回index指定位置的字符。 public int indexOf(String str) 返回str在字符串中第一次出现的位置。 public String 以newChar2字符替换串中所有oldChar replace(char oldChar, 字符。 char newChar) public String trim( 去掉字符串的首尾空格

String类的常用方法 方 法 说 明 public int length() 返回字符串的长度。 public boolean equals(Object anObject) 将给定字符串与当前字符串相比较， 若两字符串相等，则返回true，否则 返回false。 public String substring(int beginIndex) 返回字符串中从beginIndex开始的子 串。 public String substring(int beginIndex, int endIndex) 返回从beginIndex开始到endIndex-1的 子串。 public char charAt(int index) 返回index指定位置的字符。 public int indexOf(String str) 返回str在字符串中第一次出现的位置。 public String replace(char oldChar, char newChar) 以newChar字符替换串中所有oldChar 字符。 public String trim() 去掉字符串的首尾空格

■ int length():返回当前字符串长 ■例如： String s2 "hello world"; System.out.println(s2.1ength())j 结果为： 口11

◼ int length() ：返回当前字符串长 ◼ 例如: ◼ String s2 = "hello world" ; ◼ System.out.println(s2.length()); 结果为: ❑ 11