数据结构实验3 串操作.doc

实验报告3 串操作 一、 实验目的： （1） 掌握串的定义、术语。 （2） 掌握串的基本操作算法。 （3） 掌握串的匹配算法。 二、 实验内容： 1. 在常量串MyString类中，增加以下方法，并求各算法的时间复杂度。 public MyString trim() //删除串中所有空格 public char[] toCharArray() //返回字符数组 public MyString toLowerCase() //返回将大写字母转换成小写字母的字符串 public MyString toUpperCase() //返回将小写字母转换成大写字母的字符串 public MyString replace(char old, char newc) //用字符newc替换串中的字符old public Boolean equals(Object obj) //判断两个串是否相等 public Boolean equalsIgnoreCase(String1 str) //判断两个串是否相等,忽略大小写 public int compareTo(MyString str) // 在本实验中，我们主要关注的是数据结构中的一个重要概念——串（String），以及如何使用Java语言来实现对串的一系列基本操作。实验的目标是理解和掌握串的定义、相关术语，学习串的基本操作算法，以及串的匹配算法。下面我们将详细讨论实验中涉及的知识点。 1. **串的定义**： 在数据结构中，串是由一个或多个字符组成的有限序列，可以看作是一个字符数组。Java中，字符串通常以`String`类的形式存在，但在这个实验中，我们创建了一个名为`MyString`的类来模拟和操作字符串。 2. **基本操作算法**： - `trim()`：这个方法用于移除字符串两侧的空白字符。实现时，遍历字符串，遇到非空格字符时将其复制到新数组中，直到遇到第一个空格，然后跳过空格，继续复制非空格字符。时间复杂度为O(n)，其中n为字符串长度。 - `toCharArray()`：将字符串转换为字符数组。这里只需简单地创建一个新的字符数组，然后通过遍历字符串并复制每个字符到新数组中完成。时间复杂度同样为O(n)。 - `toLowerCase()` 和 `toUpperCase()`：这两个方法分别用于将字符串中的所有大写字母转换为小写，或将小写字母转换为大写。可以通过遍历字符串，根据ASCII码进行转换。时间复杂度为O(n)。 - `replace(old, newc)`：这个方法用于替换字符串中所有出现的旧字符old为新字符newc。同样需要遍历字符串，遇到old时替换，时间复杂度为O(n)。 - `equals(Object obj)` 和 `equalsIgnoreCase(String1 str)`：这两个方法用于比较字符串是否相等。前者是标准的`equals`方法，遵循对象比较规则，后者忽略大小写。它们都需要遍历字符串，时间复杂度为O(n)。 - `compareTo(MyString str)` 和 `compareToIgnoreCase(MyString str)`：这两个方法实现了`Comparable`接口，用于比较两个字符串的顺序。前者考虑大小写，后者忽略大小写。它们通过逐个字符比较ASCII码实现，时间复杂度为O(n)。 - `startsWith(MyString prefix)` 和 `endsWith(MyString suffix)`：这两个方法检查字符串是否以指定的前缀或后缀开头或结尾。可以使用双指针技术，从头或尾开始比较，时间复杂度为O(min(m, n))，其中m和n分别为原字符串和前缀/后缀的长度。 3. **源代码分析**： 源代码中，`MyString`类的构造函数接受字符数组或字符串初始化，`trim`方法通过遍历和复制非空格字符实现，其他方法如`toCharArray`、`toLowerCase`、`toUpperCase`、`replace`、`equals`、`equalsIgnoreCase`、`compareTo`、`compareToIgnoreCase`、`startsWith`和`endsWith`都按照上述逻辑进行实现。 4. **时间复杂度分析**： 大多数方法的时间复杂度都是线性的，因为它们都涉及到对整个字符串的遍历。`trim`、`toCharArray`、`toLowerCase`、`toUpperCase`、`replace`、`equals`、`equalsIgnoreCase`、`compareTo`、`compareToIgnoreCase`、`startsWith`和`endsWith`的方法执行时间与输入字符串的长度成正比。 5. **空间复杂度**： 除了`equals`和`equalsIgnoreCase`方法，其他涉及到字符串转换或处理的方法都可能需要额外的空间来存储结果，例如`trim`、`toCharArray`、`toLowerCase`、`toUpperCase`和`replace`。这些方法的空间复杂度为O(n)。 通过这个实验，学生可以深入理解串的基本操作，掌握其算法实现，同时锻炼了Java编程能力，尤其是对于字符串处理的理解。这些知识在实际编程中非常常见，对于解决文本处理、数据解析等问题至关重要。