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所示存放顺序。
图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所示。
图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所示存放顺序。
图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所示。
图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所示。
图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所示。
图3-24 矩阵A带行指针向量的单链表表示
若矩阵的行数为m，非零元素个数为N，则它的存储量为3N＋m；若每一行中的非零元素个数为s，则存取元素的时间复杂度为O（s）。
2）十字链表结构。在十字链表中，存放表头结点和非零元素结点的结构相似，如图3-25所示。
图3-25 十字链表结构
例如，对上述矩阵建立十字链表
建立链表表头，如图3-26所示。
图3-26 十字链表表头
插入非零结点，行、列构成循环链表，如图3-27所示。
图3-27 插入非零结点后的十字链表
增加附加头结点，头结点中row、col分别存放稀疏矩阵的行数和列数，并将所有表头构成循环链表，如图3-28所示。
图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语言源程序如下：
