Java数据结构和算法：字符串、数组和广义表

ゞ浴缸里的玫瑰 2022-07-13 09:42 221阅读 0赞

数组和广义表是与前述的线性表有所区别的数据结构。它们可以看成是线性表在下述含义上的扩展：线性表中的元素本身也是一个数据结构

# 字符串 #

## 字符串的定义、存储结构 ##

字符串(string)是由n (n≥0) 个字符组成的有限序列。字符串简称为串，一般记为：  
s = “a0 a1 … an-1”

其中s是串名；用双引号括起来的字符序列是串值；ai (0≤i<<n)可以是ASCII码字符中的可打印字符，通常是字母、数字等字符；

i称为字符ai 在串中的位置；n称为串的长度；n =0时，s称为空串。容易与空串相混淆的一种串是空格串，空格串是由一个或多个空格组成的串，如4个空格组成的空格串“ ”，它的长度是4，而空串的长度为0。

串中任意多个连续的字符组成的子序列称为该串的子串。子串在该串中的位置就是子串的首字符在该串中的位置。  
如果两个字符串对应位置的字符都相等，且它们长度相等，则称这两个字符串相等。

在C++中，串值必须用一对双引号括起来，但双引号本身不属于串。而字符用单引号括起来。串“w”和字符‘w’是两个不同的概念，前者是字符串，后者是字符。

串是一种线性结构，因此，串既可以用顺序存储结构来存储，也可以用链表存储结构来存储。由于每个字符占空间很小，只占8位二进制，所以串通常采用顺序存储结构存储，它比用链式存储结构存储效率高，实现起来也方便。

# 模式匹配算法 #

设有两个字符串ob和pat，若要在串ob中查找与串pat相等的子串，则称ob为主串（或称目标串），pat为模式串，并称查找模式串在主串中的匹配位置的运算为模式匹配。

该运算从ob的头1个字符开始查找一个与串pat (称作模式串) 相同的子串。  
如果在串ob中查找到一个与模式串pat相同的子串，则函数返回模式串pat的头一个字符在串ob中的位置；

如在主串中未查找到一个与模式串pat相同的子串，则函数返回－1。  
在类String中的成员函数find ( )就是模式匹配函数。

## Brute-Force算法 ##

Brute-Forc算法的主要思想是：从主串ob = “s0 s1 … sm-1”的第一个字符开始与模式串pat = “t0 t1 … tn-1”的第一个字符比较：

若相等，则继续比较后续字符；

否则，从主串ob的第二个字符开始重新与模式串pat 的第一个字符比较。

如此继续，若在主串ob中有一个与模式串相等的连续字符序列，则匹配成功，函数返回模式串pat的首字符在串ob中的位置；

否则，匹配失败，函数返回－1。

Brute-Force算法是一种带回溯的算法，也叫朴素的模式匹配算法。在最坏情况下，最多要比较m－n＋1趟，每趟比较在最后才出现不等，要做n次比较，总比较次数要达到(m－n＋1)n。通常n会远远小于m，因此，算法的最坏情况下运行时间为O(m\*n)。

## 模式匹配的KMP算法 ##

KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt三人设计的。该算法是Brute-Force算法的改进。

它消除了Brute-Force算法的如下缺点：主串下标i在若干次对应的字符比较相等后，只要有一次对应字符比较不相等便需要回退。

# 数组 #

## 数组的基本概念 ##

通常，一维数组A(array)是n (n≥0)个相同数据类型的数据元素a0, a1, , an-1构成的有限线性序列。其中n叫做数组长度或数组大小，若n＝0就是空数组。当每一个数组元素ai（0≤i≤n-1）本身又是一个一维数组时，则A就是一个二维数组。类似地，我们可以构成一个多维数组,一个m(m≥2)维数组中的每一个数组元素是一个m-1维的数组。

可见在一个m(m≥2)维数组中，每一个数组元素受m个线性关系的约束，如果一个元素在每一维中的序号分别为i1、i2、…、im，则称该元素的下标为：i1、i2、…、im。如果一个数组名为a，则ai1i2…im表示下标为i1、i2、…、im的数组元素。

## 数组的顺序存储结构 ##

采用顺序存储结构存储数组的元素，就是按某种顺序将数组元素依次存放在内存中的一片连续的存储单元中。

数组的每个元素的数据类型都相同，因而占有相同的存储空间。对于一维数组，相邻元素的起始地址之差为一常数。

## 稀疏矩阵 ##

在求解科学和工程计算问题时常常会接触到“矩阵”这类对象。

矩阵本身就是二维数组。对于一个矩阵，如果零元素较多，还是采用上一节所述的存储方式来存储的话，就会使得大量的存储空间存放同一个值零，从而造成事实上的存储空间的浪费。

本节，将讨论这种矩阵如何进行压缩存储，以及基本操作的实现。

像这种零元素非常多的矩阵称为稀疏矩阵。显然，关于“稀疏”的定义是无法精确给出的。因为稀疏矩阵是非零元素很少的矩阵，我们只要存储非零元素就行了。

整个稀疏矩阵的存储结构既可以采用顺序结构存储，也可以采用链式结构存储。

## 三元组顺序表 ##

所有三元组构成了一个三元组表，该三元组表是一个线性表。可以采用顺序存储结构存储的三元组表称为三元组顺序表。在三元组顺序表中，矩阵非零元素的三元组按照其在矩阵中的位置，以行优先的顺序依次存放，并给出行数、列数和非零元素个数。

## 十字链表 ##

当矩阵非零元的位置或个数经常变动时，三元组顺序表就不适合于作稀疏矩阵的存储结构。像作两个矩阵A与B的加法，把结果保存到A中，将会引起非零元的的变化，并导致非零元的插入和删除。此时，采用链式存储结构更好些。

稀疏矩阵的十字链表，由行链表和列链表组成，每一个矩阵元素既处于行链表中，又处于列链表中。这里的行链表是一个不带表头结点的单链表，列链表亦是一个不带表头结点的单链表。

## 广义表 ##

线性表、栈、队列、数组等数据结构都是线性结构，结构中的元素都是同一类型的数据元素。本节所讨论的广义表中元素的数据类型将允许表中元素自身又可以是表。广义表是线性表的推广，也有人称其为列表（lists）。

### 广义表的定义 ###

广义表LS是由n≥0个表元素α1 ,α2 , … , αn 组成的有限序列，其中表元素αi (1≤i≤n) 或者是一个数据元素 (可称为单元素或原子)，或者是一个表(称为子表)。记作  
LS = (α1 ,α2 , … , αn )  
其中LS是表名，表的长度为n。长度为0的广义表为空表。一般用大写字母表示表名，用小写字母表示数据元素。如果n≥1，则称α1 为广义表LS的表头(head)，称(α2 , … , αn )为广义表LS的表尾(tail)。