当前位置：首页 > news >正文

数据结构--串、数组和广义表

news 2025/7/8 5:58:27

串

定义：串（String）是由零个或多个字符组成的有限序列。
子串：串中任意个连续字符组成的子序列称为该串的子串。
主串：包含子串的串相应地称为主串。
字符位置：字符在该序列中的序号为该字符在串中的位置。
子串位置：子串第一个字符在主串中的位置。
空格串：由一个或多个空格组成的串，与空串不同。
存储结构：
- 顺序存储结构：字符在内存中连续存放。
- 链式存储结构：字符通过指针链接在一起。
模式匹配：在主串中查找子串的过程，称为串的模式匹配或串匹配。常见的算法有Brute-Force（BF）算法和KMP算法。

串的类型定义、存储结构及其运算

串的类型定义

串，又称字符串，是由零个或多个字符组成的有限序列。一般记为S='a1a2…an'，其中S是串名，a1a2…an是串值。由零个字符组成的串称为空串（Null String），其长度为零。仅由一个或多个空格组成的串称为空格串（Blank String），其长度为串中空格字符的个数。

在计算机科学中，串是数据结构中的一种基本类型，用于表示文本数据或其他字符序列。串的每个元素（或称为字符）都来自一个有限的字符集，如ASCII字符集或Unicode字符集。

在Java中，串（String）是一种内置的数据类型，它已经被Java标准库以类的形式实现。虽然Java提供了丰富的String类库来操作字符串，但仍然可以基于面向对象编程的原则，为串定义一个抽象数据类型（ADT），并规定其应支持的基本操作。以下是一个简化的串的抽象类型定义（ADT）及其在Java中的可能实现方式：

ADT String {// 基本操作String concat(String other);        // 串连接int indexOf(String str);            // 查找子串首次出现的位置String substring(int beginIndex);   // 截取子串（从beginIndex开始到末尾）String substring(int beginIndex, int endIndex); // 截取子串（从beginIndex到endIndex-1）boolean contains(String str);       // 判断是否包含子串int length();                       // 返回串的长度char charAt(int index);             // 返回指定位置的字符boolean isEmpty();                  // 判断是否为空串// ... 可以根据需要添加更多操作
}

创建一个自定义的String类（注意，这里的实现仅用于教学目的，并不推荐在实际项目中使用，因为Java内置的String类已经高度优化且功能完善）。

public class MyString {private char[] chars;private int length;// 构造函数public MyString(String str) {this.chars = str.toCharArray();this.length = str.length();}// 串连接public MyString concat(MyString other) {char[] newChars = new char[this.length + other.length];System.arraycopy(this.chars, 0, newChars, 0, this.length);System.arraycopy(other.chars, 0, newChars, this.length, other.length);return new MyString(new String(newChars));}// 查找子串首次出现的位置public int indexOf(MyString str) {// 简单的线性搜索算法，可以优化为KMP等算法for (int i = 0; i <= this.length - str.length; i++) {int j;for (j = 0; j < str.length && this.chars[i + j] == str.chars[j]; j++) {// 无需操作}if (j == str.length) {return i; // 找到匹配}}return -1; // 未找到匹配}// 截取子串（从beginIndex开始到末尾）public MyString substring(int beginIndex) {return new MyString(new String(this.chars, beginIndex, this.length - beginIndex));}// 截取子串（从beginIndex到endIndex-1）public MyString substring(int beginIndex, int endIndex) {return new MyString(new String(this.chars, beginIndex, endIndex - beginIndex));}// 判断是否包含子串public boolean contains(MyString str) {return this.indexOf(str) != -1;}// 返回串的长度public int length() {return this.length;}// 返回指定位置的字符public char charAt(int index) {if (index < 0 || index >= this.length) {throw new IndexOutOfBoundsException("Index: " + index + ", Length: " + this.length);}return this.chars[index];}// 判断是否为空串public boolean isEmpty() {return this.length == 0;}// 为了方便测试，重写toString方法@Overridepublic String toString() {return new String(this.chars);}// ... 可以根据需要添加更多操作
}

串的存储结构

串的存储结构主要有两种：静态存储结构和动态存储结构。

静态存储结构
- 顺序存储结构：将串定义成字符型数组，由串名可以直接访问到串值。这种存储结构的特点是访问速度快，但空间利用率可能不高，因为需要预先分配一个足够大的数组空间。
- 紧缩存储结构：为了节省空间，可以将多个字符存储在一个机器字内（如果机器字足够大）。这种存储结构可以减少空间浪费，但访问速度可能受到影响，因为需要额外的计算来提取字符。
动态存储结构
- 链式存储结构：也称为链串，结构与链表类似。链串中每个结点有两种域，一种是数据域（data），用于存放字符串中的字符；另一种是指针域（next），用于存放后继结点的地址。这种存储结构可以灵活地扩展串的长度，但访问速度相对较慢。

此外，还有串的索引存储结构，其构造方法是：首先开辟一块地址连续的存储空间（又称为堆），用于存放各串本身的值。另外再建立一个索引表，在索引表的项目中存放串的名字、长度和在存储空间中的起始地址。这种存储结构适用于需要频繁查找和访问不同串的场景。

串的运算

串的运算主要包括以下几种：

串的匹配：在主串中查找子串的过程称为串的匹配。常见的串匹配算法有朴素的模式匹配算法（也称为布鲁特-福斯算法）和改进的模式匹配算法（如KMP算法）。这些算法的时间复杂度取决于主串和子串的长度以及匹配过程中的字符比较次数。
串的替换：在主串中查找并替换某个子串为另一个子串的过程。这通常涉及多次串匹配和插入/删除操作。
串的拼接：将两个或多个串连接成一个新的串。这可以通过顺序存储结构中的数组拼接或链式存储结构中的链表合并来实现。
串的截取：从主串中提取一个子串的过程。这通常涉及定位子串的起始和结束位置，并复制相应的字符到新的串中。
串的长度：计算串中字符的个数。这可以通过遍历串并计数字符来实现。
串的比较：比较两个串是否相等或确定它们的字典序大小关系。这通常涉及逐个比较字符的字符编码值。

数组

定义：数组是按一定格式排列起来的具有相同类型的数据元素的集合。
类型：
- 一维数组：如A=(a1,a2,a3,…,an)。
- 二维数组：如矩阵，按行或列优先顺序存储。
- 三维数组：按页/行/列存放，页优先的顺序存储。
特殊矩阵的压缩存储：对于某些具有特定规律的矩阵，如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵，可以采用压缩存储方式来节省存储空间。

一维数组

定义：一维数组是由相同类型的数据元素按一定顺序排列的集合，每个元素都有一个唯一的下标（索引）来标识其在数组中的位置。
存储结构：一维数组在内存中占据一段连续的存储空间，每个元素按线性顺序排列。
访问方式：通过数组名和元素的下标来访问数组中的元素，例如array[i]表示访问一维数组array中第i个位置的元素。
应用：一维数组常用于存储线性数据，如学生的成绩、员工的工资等。

二维数组

定义：二维数组是由多个一维数组组成的数组，每个一维数组称为二维数组的行，而每个一维数组中的元素则称为二维数组的列。因此，二维数组可以看作是一个表格或矩阵。
存储结构：二维数组在内存中也是占据一段连续的存储空间，但它是按行或列的顺序存储的。通常，二维数组的第一维表示行，第二维表示列。
访问方式：通过数组名和两个下标（行号和列号）来访问二维数组中的元素，例如array[i][j]表示访问二维数组array中第i行第j列的元素。
应用：二维数组常用于存储具有行和列关系的数据，如学生的成绩表、矩阵运算等。

一维数组与二维数组的区别

存储结构：一维数组是线性存储的，而二维数组是矩阵（表格）形式存储的。
访问方式：一维数组通过单个下标访问元素，而二维数组通过两个下标（行号和列号）访问元素。
应用场景：一维数组适用于存储线性数据，而二维数组适用于存储具有行和列关系的数据。

广义表

定义：广义表（列表）是由n（n>=0）个表元素组成的有限序列，记作LS=(a0,a1,a2,…,an-1)。其中，LS是表名，ai是表元素，它可以是表（称为子表），也可以是数据元素（称为原子）。
表头：若LS非空（n>=1），则第一个元素a0是表头，记作head(LS)=a0。
表尾：除表头外的其他元素组成的表是表尾，记作tail(LS)=(a1,a2,…,an-1)。注意，表尾不是最后一个元素，而是一个子表。
递归定义：广义表可以递归地定义，即广义表中的元素可以是另一个广义表。
存储结构：
- 链式存储结构：使用链表来表示广义表，每个节点可以是原子节点（存储原子）或表节点（存储子表）。
特点：
- 广义表的结构相当灵活，可以兼容线性表、数组、树和有向图等各种常用的数据结构。
- 广义表可以看成是线性表的推广，线性表是广义表的特例。

串