3.5 其他线性结构

字符串是一种常见的线性结构。字符串及定义在字符串上的运算是计算机程序进行文字处理的基础。二维数组是数学中的矩阵在程序设计语言中的表示。当矩阵中的绝大部分元素为零时，采用一般的二维数组的存储方式会浪费大量的存储空间，同时也做了大量不必要的运算。因此，本节主要讨论的内容包括：①串的结构特点及其基本操作；②一般二维数据的顺序存储结构，以及当矩阵中大部分为零元素时的表示方法。

3.5.1 串的定义和串的存储方式

1.串的概念

串（String）是零个或多个字符组成的有限序列。一般记为：

S＝′a1 a2…an′（n≥0）其中，S是串的名字，用单引号括起来的字符序列是串的值；ai（1≤i≤n）可以是字母、数字或其他字符；n是串中字符的个数，称为串的长度，n＝0时的串称为空串（Null String）。

串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

假如有字符串A＝‘data elements’，B＝‘elements’，C＝‘data’，则它们的长度分别为13、8和4。B和C是A的子串，B在A中的位置是6，C在A中的位置是1。

当且仅当两个字符串的值相等时，称这两个字符串是相等的。即只有当两个字符串的长度相等，并且每个对应位置的字符都相等时才相等。

需要特别指出的是，字符串值必须用一对单引号括起来（C语言中是双引号），但单引号是界限符，它不属于字符串，其作用是避免与变量名或常量混淆。

由一个或多个称为空格的特殊字符组成的串，称为空格串（Blank String），其长度为字符串中空格字符的个数。请注意空串（Null String）和空格串（Blank String）的区别。

字符串也是线性表的一种，因此字符串的逻辑结构和线性表极为相似，区别仅在于字符串的数据对象限定为字符集。

2.串的抽象数据类型定义

3.串的基本操作

（1）StrAsign（S，chars）

初始条件：chars是字符串常量。

操作结果：生成一个值等于chars的字符串S。

（2）StrLength（S）

初始条件：字符串S存在。

操作结果：返回字符串S的长度，即字符串S中的元素个数。

（3）StrInsert（S，pos，T）

初始条件：字符串S存在，1≤pos≤StrLength（S）＋1。

操作结果：在字符串S的第pos个字符之前插入串T。

（4）StrDelete（S，pos，len）

初始条件：字符串S存在，1≤pos≤StrLength（S）-len＋1。

操作结果：从字符串S中删除第pos个字符起长度为len的子串。

（5）StrCopy（S，T）

初始条件：字符串S存在。

操作结果：由字符串T复制得字符串S。

（6）StrEmpty（S）

初始条件：字符串S存在。

操作结果：若字符串S为空串，则返回TRUE，否则返回FALSE。

（7）StrCompare（S，T）

初始条件：字符串S和T存在。

操作结果：若S＞T，则返回值＞0；如S＝T，则返回值＝0；若S＜T，则返回值＜0。

（8）StrClear（S）

初始条件：字符串S存在。

操作结果：将字符串S清为空串。

（9）StrCat（S，T）

初始条件：字符串S和T存在。

操作结果：将字符串T的值连接在字符串S的后面。

（10）SubString（Sub，S，pos，len）

初始条件：字符串S存在，1≤pos≤StrLength（S）且1≤len≤StrLength（S）-pos＋1。

操作结果：用Sub返回字符串S的第pos个字符起长度为len的子串。

（11）StrIndex（S，pos，T）

初始条件：字符串S和T存在，T是非空串，1≤pos≤StrLength（S）。

操作结果：若字符串S中存在和字符串T相同的子串，则返回它在字符串S中第pos个字符之后第一次出现的位置；否则返回0。

（12）StrReplace（S，T，V）

初始条件：字符串S，T和V存在，且T是非空串。

操作结果：用V替换字符串S中出现的所有与T相等的不重叠的子串。

（13）StrDestroy（S）

初始条件：字符串S存在。

操作结果：销毁字符串S。

3.5.2 定长顺序串运算

1.定长顺序串

定长顺序串是将字符串设计成一种结构类型，字符串的存储分配是在编译时完成的。和前面所讲的线性表的顺序存储结构类似，用一组地址连续的存储单元存储字符串的字符序列。

其中，Maxlen表示串的最大长度；ch是存储字符串的一维数组，每个分量存储一个字符；len是字符串的长度。

在进行串的插入时，插入位置pos将字符串分为两部分（假设为A、B，长度为LA、LB），及待插入部分（假设为C，长度为LC），则字符串由插入前的AB变为ACB，可能有3种情况：

1）插入后字符串长（LA＋LC＋LB）≤Maxlen：则将B后移LC个元素位置，再将C插入。

2）插入后字符串长＞Maxlen且pos＋LC＜Maxlen：则B后移时会有部分字符被舍弃。

3）插入后字符串长＞Maxlen且pos＋LC＞Maxlen：则B的全部字符被舍弃（不需后移），并且C在插入时也有部分字符被舍弃。

在进行串的连接时（假设原来串为A，长度为LA，待连接串为B，长度为LB），也可能有3种情况：

1）连接后字符串长≤Maxlen：则直接将B加在A的后面。

2）连接后字符串长＞Maxlen且LA＜Maxlen：则B会有部分字符被舍弃。

3）连接后字符串长＞Maxlen且LA＝Maxlen：则B的全部字符被舍弃（不需连接）。

置换时的情况较为复杂，假设为原字符串为A、长度为LA，被置换字符串为B、长度为LB，置换字符串为C、长度为LC，每次置换位置为pos，则每次置换有3种可能：

1）LB＝LC：将C复制到A中pos起共LC个字符处。

2）LB＞LC：将A中B后的所有字符前移LB-LC个字符位置，然后将C复制到A中pos起共LC个字符。

3）LB＜LC：将A中B后的所有字符后移LC-LB个字符位置，然后将C复制到A中pos起共LC个字符，此时可能会出现串插入时的3种情况，应按情况作相应处理。

下面是定长顺序串部分基本操作的实现。

2.串插入函数

3.串删除函数

4.串复制函数

5.判空函数

6.串比较函数

7.求串长函数

8.清空串函数

9.联接串函数

10.求子串函数

11.定位函数

3.5.3 二维数组的结构特点和存储方式

数组已广泛应用于各种高级语言中，是比较常用的一种数据结构。从结构上看，它是线性表的推广。这一讲主要介绍数组的逻辑结构定义及存储方式，着重介绍特殊形式的数组——稀疏矩阵的存储结构及相应的运算。

1.数组的定义和运算

一维数组

A=(a1,a2,…an)

二维数组

一般形式二维数组

数组结构具有3个性质：

●数据元素数目固定，即一旦说明了一个数组结构，其元素数目不再有增减变化。

●数据元素具有相同的类型。

●数据元素的下标关系具有上下界的约束并且下标有序。

对于数组，通常只有以下两种运算：

●给定一组下标，存取相应的数据元素。

●给定一组下标，修改相应数据元素中的某个数据项的值。

2.数组的顺序存储结构

由于计算机的存储单元是一维结构，而数组是多维结构，要用一维的连续单元存放数组的元素，就有存放次序的约定问题。根据不同的存放形式可以分为以下几种类型。

（1）按行优先顺序存放

按行优先顺序存放就是按行切分，如上述二维数组A23，按行切分可得如图3-19所示存放顺序。

假设每个元素仅占一个存储单元，则元素aij的存储地址可以通过下面的关系式计算：

Loc（aij）＝Loc（a11）＋（i-1）×n＋（j-1）　（1≤i≤m，1≤j≤n） （3-5）

对应二维数组按行优先顺序存放，在三维数组中是以左下标为主序的存储方式。例如Almp（设l＝2，m＝3，n＝4），如图3-20所示。

元素aijk的存储地址可以通过下面的关系式计算：Loc（aijk）＝Loc（a111）＋（i-1）×m×n＋（j-1）×n＋（k-1）（1≤i≤l，1≤j≤m，1≤k≤n）

（3-6）

在C、BASIC、COBOL和Pascal等语言中，数组的实现采用按行优先的存储方式。利用存储地址、指针，可以提高数据访问的效率。

例如，C语言中，一维数组时：

要访问第5个元素，可以采用下面写法：

二维数组时：

要访问a32＝9，则

（2）按列优先顺序存放

如果数组按列切分，就得到按列优先顺序存放方式，仍以上述二维数组A23为例，按列切分可得如图3-21所示存放顺序。

假设每个元素仅占一个存储单元，则元素aij的存储地址可以通过下面的关系式计算：

Loc（aij）＝Loc（a11）＋（j-1）×m＋（i-1）（1≤i≤m，1≤j≤n）（3-7）

对应二维数组按列优先顺序存放，在三维数组中是以右下标为主序的存储方式。例如，Almn（设l＝2，m＝3，n＝4），如图3-22所示。

元素aijk的存储地址可以通过下面的关系式计算：Loc（aijk）＝Loc（a111）＋（k-1）×l×m＋（j-1）×l＋（i-1）（1≤i≤l，1≤j≤m，1≤k≤n）

（3-8）

在FORTRAN语言中，数组采用按列优先的存储方式。

3.特殊矩阵的存储方式

上述两种数组的顺序存储方式，对于绝大部分元素值不为零的数组是合适的。但是，如果数组中有很多元素的值为零时，上述存储方式会造成大量存储单元的浪费。

（1）下三角阵的存储方式

设下三角阵数组Ann为

若将其中非零元素按行优先顺序存放，则

从第1行至第i-1行的非零元素个数为

求取其中非零元素aij地址的关系式为：

（2）三对角阵的存储方式

设Ann为三对角阵：

若将其中非零元素按行优先顺序存放，则

｛a11，a12，a21，a22，a23，a32，a33，a34，…，an，n-1，ann｝求取其中非零元素aij地址的关系式为：

Loc（aij）＝Loc（a11）＋2（i-1）＋（j-1）

（i＝1，j＝1，2或i＝n，j＝n-1，n或1＜i＜n，j＝i-1，i，i＋1）

（3-10)

（3）对称矩阵的存储方式

类似三对角阵的存储。

4.稀疏矩阵

矩阵在科学计算中应用十分广泛，而且随着计算机应用的发展，大量出现处理高阶矩阵问题，有的甚至达到几十万阶、几千亿个元素，这就远远超过计算机的内存容量。然而，在大量的高阶问题中，绝大部分元素是零值。当非零元素所占比例小于等于25%～30%时，我们称这种含有大量零元素的矩阵为稀疏矩阵。压缩这种零元素占据的空间，不但能节省内存空间，而且能够避免大量零元素进行的无意义运算，大大提高运算效率。

（1）顺序存储结构

1）三元组表。线性表中的每个结点由3个字段组成，分别是该非零元素的行下标、列下标和值，按行优先顺序排列。以下讨论矩阵下标均从1开始。

C语言中数据类型：

稀疏矩阵用三元组表示的例子如图3-23所示。

若行下标、列下标与值均占一个存储单元，非零元素个数为N，那么这种方法需要3N个存储单元，由于是按行优先顺序存放，因此行下标排列是递增有序的，在检索数组元素时若用对半检索方法，则存取一个元素的时间为O（log2N）。

2）伪地址表示法。伪地址是指本元素在矩阵中（包含零元素在内）按行优先顺序的相对位置，上述稀疏矩阵A中非另元素的伪地址为：

｛2，5，6，8，12，16｝

查找元素：伪地址＝n×（i-1）＋j，n为矩阵的列数。

例，查找a23＝3，a23的伪地址＝5×（2-1）＋3＝8。由计算得到的伪地址和伪地址表，即可查到a23的值。

伪地址表示法共需2N个存储单元，但要花费时间计算伪地址。

（2）顺序存储结构稀疏矩阵的转置运算

转置是一种最简单的矩阵运算，一般矩阵的转置算法为：

它的执行时间为O（m×n）。由于稀疏矩阵含有大量的零元素，这种方法显然不经济。以下介绍三元组表的转置算法。

它的执行时间为O（t×n）。由于非零元素个数t远远大于行数，故三元组转置算法虽然节省了空间，但浪费了时间。

（3）链接存储结构

顺序存储结构的缺点是当非零元素的位置或个数经常变动时，即要进行的元素的插入或删除将会带来诸多不便，这时采用链表结构更为恰当。

1）带行指针向量的单链表表示。本方法设置一个行指针向量，向量中每一个元素为一指针类型，指向本行矩阵的第1个非零元素结点，若本行无非零元素，则指针为空。例如，对上述矩阵A的单链表表示如图3-24所示。

若矩阵的行数为m，非零元素个数为N，则它的存储量为3N＋m；若每一行中的非零元素个数为s，则存取元素的时间复杂度为O（s）。

2）十字链表结构。在十字链表中，存放表头结点和非零元素结点的结构相似，如图3-25所示。

例如，对上述矩阵建立十字链表

建立链表表头，如图3-26所示。

插入非零结点，行、列构成循环链表，如图3-27所示。

增加附加头结点，头结点中row、col分别存放稀疏矩阵的行数和列数，并将所有表头构成循环链表，如图3-28所示。

3.5.4 矩阵和特殊矩阵元素的存储结构与应用实例

【问题描述】

设已知一个n×n的上三角矩阵X，其上三角元素已按行序为主序连续存放在数组Y中。

请设计一个tran函数，将数组Y中元素按列为主序连续存放在数组Z中。

Y＝（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15）

Z＝（1，2，6，3，7，10，4，8，1，13，5，9，12，14，15）

【算法分析】

解题思路：用i和j表示矩阵X中元素的行和列下标。用k表示矩阵Y中元素的下标，初始时i＝1，j＝1，k＝1；将y［k］＝x［i，j］元素存放在z［j（j-1）＋i］中，且当一行没有结束时j＋＋，否则i＋＋并修改下一行元素的个数及i和j的值，直到k＝n（n＋1）／2为止。

C语言源程序如下：

3.5.5 稀疏矩阵的压缩存储方式和简单运算实例

【问题描述】

输入一个稀疏矩阵A，①将其转化为三元组的表示形式；②在三元组存储矩阵中查找值为x的结点是否存在于矩阵A中，如果存在，输出其位置，否则输出“不存在”提示信息。

【算法分析】

稀疏矩阵用二维数组A进行存储，三元组用结构体B表示。先将A数组中的非0元素及它所在的行、列位置信息按行优先顺序存储到B中，然后再在B中查找值为x的结点所在位置，如果存在，输出其位置，否则输出“不存在”提示信息。

C语言源程序如下：