第5章 其他线性数据结构

第5章 其他线性数据结构 5.1 串 5.2 多维数组 5.3 应用举例及分析 习题

5.1 串 5.1.1 串的定义及基本操作 串是由零个或多个字符组成的有限序列。用线性表表示，标记为： S=‘a1,a2,a3,……an’ (n>=0) 串长度：串中的字符个数。引号不是串的内容。 空串：长度为0的串。空格串不是空串。 子串：串中连续字符组成的子序列。 子串在主串中的位置：以第一个字符出现位置标识。 空串是任何串的子串，任何串是自身的子串。 子串相等：两串的长度相等，并且对应字符都相等。

5.1.2 串的存储结构 定长顺序存储表示（静态数组结构） 堆分配存储表示（动态数组结构） 串的链式存储表结构 串的操作对象：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。 串的存储结构：可分为顺序存储、链式存储。此处仅介绍顺序存储。 定长顺序存储表示（静态数组结构） ——用一组地址连续的存储单元存储串值的字符序列，属静态存储方式。 堆分配存储表示（动态数组结构） ——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的链式存储表结构 顺序存储 链式存储

5.1.3 串的基本操作的实现 1、在串的顺序定长存储结构上实现CONCAT(S,T1,T2) 在操作时需考虑可能出现的三种情况： 串T1和串T2的长度之和小于MAXSIZE，即两串联接得到的S串是T1串和T2串联接的正常结果，S串的长度等于T1串和T2串的长度之和。 串T1的长度小于MAXSIZE，而串T1和串T2的长度之和大于MAXSIZE，则两串联接得到的S串是T1串和T2串的一个子串的联接，串T2 的后面部分被截断。 S串的长度等于MAXSIZE。 串T1的长度等于MAXSIZE，则两串联接得到的S串是T1串的拷贝，串T2 全部被截断。S串的长度等于MAXSIZE。

2、在串的堆分配结构上实现CONCAT(S,T1,T2)操作 算法如下： void concat_h(HSTRING s, HSTRING t1, HSTRING t2) { int I; s.ch=malloc((t1.len+t2.len)*sizeof(char)); for(i=1;i<=t1.len;i++) s.ch[i]=t1.ch[i]; for(i=1;i<=t2.len;i++) s.ch[i+t1.ch]=t2.ch[i]; s.len=t1.len+t2.len; }

3、在串的顺序定长存储结构上实现子串的定位操作INDEX(S,T) 定位操作：子串的定位操作通常称作串的模式匹配，用于得到子串在主串中的位置。 定位函数的算法思路：在主串S中从i=1开始取一长度和串T长度相等的子串与串T进行比较，若相等，则函数返回i;否则i增加1，从i=2开始取一长度和串T长度相等的子串与串T进行比较，重复上述的过程，直至确定在串S中取不到和串T长度相等的子串为止，函数返回0。或在S中取到一个和串T相等的子串，函数返回i。

串小结 串是一种特殊的线性表，由有限的字符序列组成。串的应用非常广泛，凡是涉及到字符处理的领域都要用到串。很多高级语言和字符处理软件都具有较强的串处理的功能。 对串的处理可以是对整个串本身，也可以是对串的一部分(即子串)进行加工处理。串的基本运算有：串的连接、求子串、求串的长度、求子串在串中的序号和串的置换等。

5.2 多维数组 5.2.1 二维数组的定义及操作 数组：数组（array）是由下标（index）和值（value）组成的序对的集合。 数组元素：在数组中，对每组有定义的下标，都存在一个与其对应的值，称为数组元素。数组中的数据元素均属于同一数据类型。 例如，二维数组： Amn= a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn

元素与位置的对应关系：在二维数组中，每个元素都受行关系和列关系的约束。如A[m][n]，对第i行第j列元素A[i][j]，A[i][j+1]是行关系中的直接后继元素，而a[i+1][j]是该元素在列关系中的直接后继元素。 二维数组可以看成是一个一维数组，它有row个数据元素，每个数据元素又是一个有col个数据元素的一维数组。 数组的运算： 给定下标，存取相应的数据元素 给定一组下标，修改相应数据元素的值 数组一旦被定义，其维数和维界就不再改变，即数据元素的个数和元素之间的关系就不再发生变动。数组一般不做插入或删除操作。

5.2.2 二维数组的向量存储结构 一、二维数组的顺序存储规则通常有两种： 5.2.2 二维数组的向量存储结构 一、二维数组的顺序存储规则通常有两种： 1、行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。 A的m*n个元素按行优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。 2、列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。按列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。

二、数组元素存储地址、序号的运算： 设二维数组A(m×n)按行优先顺序存储，数组中第一个元素的序号为1，每个数据元素占用的存储单元数b。 求数组元素在向量中的序号： index(ai,j)=n(i-1)+j 求某个数据元素（下标i，j）的存储起地址： loc(ai,j)=loc(a1,1)+[n(i-1)+(j-1)]b 计算数组中每个元素的存储起地址所花的时间是一样的，即存取数组中任以元素耗时相同，因此，称数组的这种顺序存储结构是随机存储结构。

5.2.3 稀疏矩阵的压缩存储 引言 矩阵是很多科学与工程计算问题中研究的数学对象。如何存储矩阵的元，从而使矩阵的各种运算能有效进行是我们需要研究的问题。 在此，我们将对稀疏矩阵的压缩存储和转置两个问题进行讨论。本小结介绍稀疏矩阵的定义及压缩存储。

稀疏矩阵的定义：当矩阵中非常元素个数远小于元素总数时，称为稀疏矩阵。 压缩存储：为多个值相同的原只分配一个存储空间；对零元不分配存储空间。 稀疏矩阵压缩存储的实现：每个非零元素用一个三元组(i,j,v)表示，其中，i，j为非零元素的行号与列号，v为元素值。把三元组按行优先顺序存储为一个线性结构，称三元组表。三元组表是稀疏矩阵的一种顺序存储结构，其数据类型描述如下。

稀疏矩阵的三元组表数据类型： #define MAXLEN 40 #define DATATYPE1 int typedef struct {int i,j ; DATATYPE v; }NODE ; {int m, n, t NODE data [MAXLEN] }SPMATRZX ;

例1：写出下图所示稀疏矩阵的压缩存储形式。 1 2 3 4 5 6 1 1 2 3 4 5 6 1 2 3 4 5 6 0 12 9 0 0 0 0 0 0 0 0 0 -3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0 解：用三元组线性表表示： {{1,2,12},{1,3,9},{3,1,-3},{3,5,14}, {4,3,24},{5,2,18},{6,1,15},{6,4,-7}} 说明：稀疏矩阵的压缩存储结构主要有三元组顺序表和三元组链表两大类型。

例2：下面的三元组表表示一个稀疏矩阵，试还原出它的稀疏矩阵。 i j d 1 2 3 4 md 5 nd 6 td 1 2 3 4 5 6 16 0 2 0 0 1 0 0 0 3 0 0 0 0 0 0 4 0 0 6 0 16 0 0 0 6 4

5.2.4 稀疏矩阵的转置算法 概念：矩阵的转置是指按一定规律变换元素的位置，一个m行n列的矩阵转置以后变成一个n行m列的矩阵。如将M（m*n）的矩阵转换为N（n*m）的矩阵，M的第（i，j）元素转置后变为N的第（j,i）元素。 转置算法：稀疏矩阵的两种转置算法：一般插入算法，transpose算法。下面分别予以介绍。

1、一般插入算法 其基本思想是：对a.data扫描一遍，扫描过程中依次取出a.data中的每一个三元组元素，将它们的行号和列号互换后依次放入b.data中，即可得到转置B的压缩存储表示。 2、 transpose算法 其基本思路是：考虑到b.data中的行就是a.data中的列，要想得到b.data中行号为1的三元组元素，可对a.data扫描一遍，找出a.data中列号为1的元素即可。算法如下。

transpose算法 void transpose(SPMATRIX b, SPMATRIX a) { int p,q,col; b.m=a.n; b.n=a.m; b.t=a.t; if(a.t!=0) {q=1; for(col=1;col<=a.u; col++) for(p=1;p<=a.t;p++) if(a.data[p].j= =col) {b.data[q].j=a.data[p].i; b.data[q].i=a.data[p].j; b.data[q].v=a.data[p].v; q++; }} }

5.3 应用举例及分析 SEQSTRING substr(SEQSTRING s, int i, int j) 5.3 应用举例及分析 例5.1在串的顺序定长存储结构上实现求子串函数SUBSTR(S,i,j)。此操作不会发生字串截断的情况,算法中,对给定的参数作合法性判断，当参数非法时，函数返回空串。 SEQSTRING substr(SEQSTRING s, int i, int j) //返回s串中的第i个字符起长度为j的子串 {SEQSTRING sub; int n; if(i<1|| i>s.len || j<0 || j>s.len – i +1) sub.len = 0； else {for(n = 1 ; n<= j ; n++) sub.ch[n] = s.ch[i+ n - 1]； sub.len = j；} return sub; }

例5.2 在串的堆分配存储结构上实现求子串函数SUBSTR（S，i, j） 前面讨论了在串的顺序定长存储结构上实现SUBSTR（S，i，j）函数的算法。下面是在串的堆分配存储结构上实现SUBSTR（S, i, j）函数的算法。此算法中，对给定的参数须作合法性判断，当参数非法时，函数返回空串。读者可和上面的算法作比较，进一步掌握串的两种存储结构。

HSTRING substr_h(HSTRING s, int i, int j) //返回s串中的第i个字符起长度为j的子串 { HSTRING sub; int n; if(i< 1 || i > s.len || j < 0 || j > s.len –i + 1) { sub.ch = NULL； sub.len = 0;} else { sub.ch = malloc(j * sizeof(char)); for(n = 1; n <= j; n++) sub.ch[n] = s.ch[n + i -1]; sub.len = j;} return sub; }

例5.3已知一个二维数组A，行下标0≤i≤7,列下标0≤j≤9，每个元素的长度为3字节，从首地址200开始连续存放在内存中，该数组元素按行优先存放，问：元素A7，4的起地址是多少？ 该二维数级是用顺序存储结构存放元素，可用前面介绍的计算公试进行计算。A数组的行号数是8，列号数是10。题中给出的存放形式和C语言中一致，数组下标的下界是0，因此地址的计算公式是：LOC（ai,j） = LOC(a0,0)+(i n + j)b,套用此公式，求得结果：200+（7×10+4）×3=422

例5.4设矩阵A（6 * 6），A中元素满足下列条件 aij ≠ 0 (i≥j,1≤i,j≤6) aij = 0 (i < j,1≤i,j≤6) 现将所有非0元素以行优先顺序存放在首地址为2000的内存中，每个元素占4个单元，计算元素A5，2的首地址。 首先看到矩阵A是一个行号和列号相等的矩阵。我们又称这种的矩阵为n阶方阵。A为6阶方阵（n = 6）。从元素满足的条件看，矩阵A中的下三角部分（包括对角线）存放了非0元素，而上三角部分（不包括对角线）全为0，如图5.8图所示。

1 11 12 3 5 31 4 6 2 7 8 82 -5 A(6*6) = (a)6阶方阵A的上半角部分全为零

基于这样的特殊性，可压缩存放矩阵元素，压缩的基本思想是：非0元素按行优先顺序存放，只分配一个单元存放0元素。所以只要存储矩阵中包括对角线在内的下三角中的元素，加上一个存放0的单元。包括对角线在内的下三角部分共有n（n+1）/2+1个存储单元。存放结构如图5.8（b）所示。 2000 A5,2元素的起始地址 = 2044 1 11 2 3 4 50 5 6 7 8 12 2 31 -5 8 31 7 82 5 4 3 … n(n+1) 2 + 1 n(n+1) 2 (b)A的压缩存储

这些元素存放在一个向量中，设定下标从1开始，每个元素占b个单元，方阵A中每一个元素ai,j(1≤i,j≤6)的首地址的计算公式如下： LOC（ai,j）= LOC(a1,1) + (i(i-1)/2+(j-1))b (i≥j) LOC(ai,j) = LOC(a1,1) + (n(n+1)/2)b (i<j) 推导原则是：对第I个行中的元素而言，前面i-1行中包含一个（i-1）阶方阵，其下三角中的元素个数是（i-1）i/2个。用上面的公式可计算得A5,2元素的首地址是： 2000+（5（5-1）/2+（2-1））×4=2044

习题 P65 5.3, 5.4, 5.6

1、定长顺序串：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。 顺序串的数据类型可描述为： Type struct {char ch[MAXSIZE]; int len; }SEQSIRING; 返 回

2、堆分配串：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。内存区域的空间块称堆。 顺序串的数据类型可描述为： typedef struct {char *ch; int len; }HSTRING 返 回