软件技术基础11大为第

串及其运算串的存储结构串的模式匹配算法多维数组矩阵的压缩存储习题55.1.1

串的概念串(String)是由多个或零个字符组成的有限序列，记做S="c1c2c3…cn"(n≥0)。其中，S是串名；由双引号括起来的字符序列称为串值，但双引号本身不属于串；ci(1≤i≤n)是串中字符，i是字符在串中的位置序号；n是串的长度，表示串中字符的个数，不包含任何字符的串称为空串，例如""是长度为0的空串。5.1

串及其运算串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。子串在主串中的序号定义为子串在主串中首次出现的位置序号。例如，设S1和S2分别为S1=“This

is

a

string”

S2=“is”则S2是S1的子串，S1是S2的主串。S2在S1中出现了两次，首次出现在主串的第3个位置上，因此S2在S1中的序号是3。特别需要一提的是，空串是任意串的子串，任意串是其自身的子串。通常，串可以分为串变量和串常量。正如我们所知道的，在程序中常量只能被引用而不能改变其值，但变量的值可以被改变。在C++语言中，串变量可以用字符型数组来表示，串常量可以用双引号括起来的字符序列直接表示或者用符号常量来表示，例如有如下定义：char

str[]="string"; const

char

str_const[]="string";str是串变量，而str_const是串符号常量。5.1.2

串的基本运算串的基本运算和线性表有很大的差别。线性表的插入、删除等运算都是以“单个元素”作为操作对象；而对串的运算，通常是把串作为一个整体进行操作，如串的复制、串的比较、插入和删除子串等。很多高级语言都提供了字符串操作的函数库，下面结合串的基本运算给出C语言有关字符串操作函数的例子。我们先定义几个相关的变量：char

s1[80]=“d:\\user\\wang\\”,

s2[40]=“file.txt”,

s3[80];//字符串中含有转义字符‘\\‘int

result;说明：字符串从字符数组下标为0的元素开始存放。StrLen(S)——求串长度，返回字符串长度。例如：printf("%d",strlen(s1));

//输出

13StrCpy(&T,

S)——复制串，将源串复制给目标串。例如：strcpy(s3,s1); //s3

的值为"d:\\user\\wang\\"StrCmp(S1,S2)——比较串，比较两个串的大小，返回整型值。>

0 S1

>

S2S1

<

S2<

0 S1

<

S2StrCmp(S1,S2)返回值==0例如：result=strcmp(“good”,“Good”);//result>0result=strcmp(“15”,“15”);result=strcmp(“That”,“The”);//result=0//result<0StrCat(&T,S)——串联接，将串S联接到串T的末尾，返回指向串S的指针。例如：printf(“%s”,strcat(s1,s2));//输出：d:\\user\\wang\\file.txtStrStr(S,Sub)——子串定位，查找串Sub在串S中第一次出现的位置，若查找到，则返回该位置信息，否则返回NULL。例如：printf("%d\n",strstr(s1,"user")-s1+1);

//输出4(6)

StrChr(S,C)——字符定位，查找字符C在串S中第一次

出现的位置，若查找到，则返回该位置信息，否则返回NULL。例如：result=strchr(s2,‘t’)-s2+1;

//result的值是6上述操作是最基本的串运算，其余的串运算一般可以由这些基本运算组合而成。【例5.1】取子串运算。取主串中start

起始的length

个字符作为子串。#include<string.h>#include<stdio.h>void

substr(char*,char*,int,int);//字符串中含有转义字符'\\'//输入起始位置和长度void

main(

){char

s1[

]="d:\\user\\wang\\",s2[80];int

start,length;printf("start,length=");scanf("%d,%d",&start,&length);substr(s2,s1,start,length);puts(s2);}void

substr(char*sub,

char*s,int

pos,int

len){if(pos<1||pos>strlen(s)||len<0)

printf(“parameter

error!\n”);else{//复制子串字符//添加子串的串结束符strncpy(sub,s+pos-1,len);strcpy(sub+len,“\0”);}}上述程序是C语言的完整程序。不同的语言对串运算会有差异，因此应以该语言的参考手册为准。5.2.1

串的顺序存储串的顺序存储结构简称为顺序串。与顺序表类似，顺序串是用字符向量来存储，并且在串的末尾用一个特定的字符作为串结束符，例如C语言中以转义字符‘\0’作为串结束符。为了具有一般性，我们仍然把串的类型定义为一个结构类型，其中用一个一维字符型数组存放串值，并用一个整型量表示串的长度。串的类型定义如下：#define

maxsize

256typedef

struct{ char

ch[maxsize];int

length;}SeqString;5.2

串的存储结构【例5.2】编写一个算法void

strdelete(SeqString*S,intpos,int

len)，若满足1≤pos≤S->length-len+1，则从串S中删除第

pos个字符开始长度为len的子串；否则不删除。void

strdelete(SeqString*S,int

pos,intlen){char

temp[maxsize];if(pos>=1&&pos<=S->length-len+1){strncpy(temp,S->ch,pos-1);strcpy(temp+pos-1,S->ch+pos+len-1);strcpy(S->str,temp);S->length=S->length-len;}}5.2.2

串的链式存储和顺序表类似，在顺序串上不方便进行插入、删除操作，需要移动大量的元素。采用链表存储串值可以提高插入、删除的效率，串的链式存储结构简称为链串。链串中的每个结点可以存放一个字符，若结点的指针域占4个字节，那么链串的存储密度只有20%。如果每个结点存放多个字符，例如4个字符，则存储密度可以达到50%，从而有效地提高了存储空间的利用率。通常将每个结点存放字符的个数定义为结点大小，图5.1(a)和(b)中的每个结点大小分别是1和4。一个结点可存放多个字符，而串长度不一定是结点大小的倍数，因此链表中最后一个结点的数据域有可能没有被串值占满，可以用特殊的字符(例如'\0')来填充。图5.1

链串的示意图链串结点的类型定义如下：结点大小为1。typedef

struct

node{ char

data;struct

node*next;}LinkString;结点大小为4。typedef

struct

node{ char

data[4];struct

node*next;}LinkString;子串定位又称为串的模式匹配(PatternMatching)，是串运算中最重要的操作之一。所谓模式匹配，就是在文本中查找是否存在给定的单词及出现的位置，例如实现文本编辑程序中的查找功能。C语言函数库中的子串定位函数strstr可以实现串的模式匹配操作，串的模式匹配算法分朴素的模式匹配和改进的模式匹配两种。5.3

串的模式匹配算法5.3.1

顺序串上的模式匹配朴素的模式匹配算法又称为穷举的模式匹配算法，假设S为目标串(主串)，T为模式串(子串)，S="s1,s2,…,sn"

T="t1,t2,…,tm"

其中0＜m≤n在实际应用中，模式串长度m通常远远小于目标串长度n，即m<<n。下面给出不依赖其他串操作运算的模式匹配算法。算法

5.1

顺序串的模式匹配。int

Index(seqstring*S,

seqstring*T,int

pos)//顺序串的朴素模式匹配，串的位序从1

开始{

i=pos;

j=1;

//

目标串从第pos个字符开始与模式串的第一个字符开始进行比较while(i<=S->length&&j<=T->length)if(S->ch[i-1]==T->ch[j-1])//串从向量的0

元素开始存放{ i++;

j++;}//继续比较后面的字符

else{

i=i-j+2;j=1;

}

//本趟不匹配，设置下一趟匹配的起始位序if(j>T->length)

return(i-T->length);

//匹配成功else return(0);//匹配不成功}分别利用计数指针i和j指示目标串S和模式串T中当前比较

的字符位序。算法的基本思想是：从目标串S的第pos个字符开

始与模式串T的第一个字符进行比较，若相等，则继续比较后

面的字符；否则，从目标串的下一个字符开始与模式串的第一

个字符进行下一趟比较。重复此过程，直至模式串中的每个字

符依次与目标串中的一个连续的字符序列相等，则匹配成功，

函数值为与模式串中第一个字符相等的字符在目标串中的位序；如果各趟比较均不相等，则匹配不成功，函数值为0。从图5.2

可以看出模式串T="abc"与目标串S="abbabca"的匹配过程

(pos=1)。图5.2

朴素的模式匹配过程现在分析算法的时间复杂度。在最坏情况下，假设每一趟都比较了m次才能够确定对应的字符是否均相等，共匹配了n-

m+1趟，比较字符的总次数为m(n-m+1)，由于n>>m，因此时间复杂度是O(m*n)。朴素的模式匹配算法虽简单，但效率较低，这是因为在一趟匹配中目标串内可能存在多个和模式串“部分匹配”的子串，而引起计数指针i的多次回溯。一种改进的模式匹配算法的时间复杂度为O(m+n)。其改进在于：每当一趟过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。具体算法读者可参阅有关资料。5.3.2

链串上的模式匹配我们以结点大小为1的单链表存储串，实现朴素的模式匹配算法。在算法中使用指针shift指向每一趟在目标串中比较的起始位置，若一趟比较中出现不相等的字符，指针shift右移指向下一个结点，继续下一趟的比较。若匹配成功，则返回shift所指向的结点地址；若匹配不成功，则返回空地址值。具体算法如下：算法

5.2

链串的模式匹配。LinkString*Index(LinkString*S,LinkString*T,LinkString*pos)//从pos所指示的位置开始查找模式串T在目标串S中首次出现的位置{LinkString*shift,*sp,*tp;shift=pos;sp=shift;

tp=T;while(sp!=NULL&&tp!=NULL){if(sp->data==tp->data){//继续比较后续结点中的字符

sp=sp->next;tp=tp->next;}else{//本趟匹配不成功，设置下一趟匹配的起始位置

shift=shift->next;sp=shift;

tp=T;}}if(tp==NULL)return

shift;//匹配成功

else

NULL;//匹配不成功}5.4

多维数组数组是一种常用的结构类型。数组中的各元素具有相同的类型，数组元素具有值和确定元素位置的下标。通常可以把一维数组称为向量，多维数组是向量的扩充。例如二维数组a

mn

a

2n

a1n

Amn

=

a

21

a11

a12a

22

a

m1

a

m2

可以看成由m个行向量组成，每个行向量中含有n

个元素；也可以看做具有n

个列向量，每个列向量中含有m

个元素。即Amn

=

{{a11

,

a12

,,

a1n

},{a

21

,

a

22

,,

a

2n

},,{a

m1

,

a

m2

,,

a

mn

}}或Amn

={{a11

,

a

21

,,

a

m1},{a12

,

a

22

,,

a

m2

},,{a1n

,

a

2n

,,

a

mn

}}一维数组中的每个元素ai

属于一个向量，二维数组中的每个元素aij

属于两个向量。一维数组是线性结构，而二维数组不应看做线性结构，因为二维数组元素可能有多个直接前趋和多个直接后继。三维数组以及多维数组的概念与二维数组类似。在计算机中一般采用顺序存储结构来存放数组。而内存结构是一维的，因此存放二维数组或多维数组时，就必须按照某种顺序将数组中的元素形成一个线性序列，然后将这个线性序列存放在内存中。下面讨论二维数组的存储方式。(1)行优先顺序存储：将数组元素按行向量的顺序存储，即第i+1

行的元素存放在第i

行的元素之后。元素存储的线性序列为a11,a12,…,a1n,a21,a22,…,a2n,…,am1,am2,…,amn(2)列优先顺序存储：将数组元素按列向量的顺序存储，即第j+1

列的元素存放在第j

列的元素之后。元素存储的线性序列为a11,a21,…,am1,a12,a22,…am2,…,a1n,a2n,…,amn在多数计算机语言中，二维数组都是按行优先顺序存储的，少数语言采用按列优先顺序存储。按照二维数组的上述两种存储的线性序列，在已知数组存储的起始地址，下标的上、下界，以及每个数组元素所占用的存储单元个数，就可以计算出元素aij

的存储地址，从而对数组元素随机存取。例如，二维数组A[c1..d1,c2..d2]按行优先的顺序存储在内存中，假设每个元素占d

个存储单元，计算元素aij

的地址公式为Loc(aij)=Loc(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d

(5-1)其中Loc(ac1c2)是数组的起始地址，元素aij

前面的i-c1

行中共有

(i-c1)×(d2-c2+1)个元素，第i行上元素aij前面又有j-c2

个元素。类似的，我们可以得出二维数组A[c1..d1,c2..d2]按列优先的顺序存储在内存中，元素aij

的地址计算公式为Loc(aij)=Loc(ac1c2)+[(j-c2)×(d1-c1+1)+i-c1]×d

(5-2)【例

5.3】

假设二维数组按行优先的顺序存储，分别计算数组

A[1..m,1..n]

和

A[0..m-

1,0..n-

1]

中元素

a

ij

的地址。行下标的下界是1，上界是m；列下标的下界是1，上界是n。元素aij的地址是Loc(aij)=Loc(a11)+[(i-1)×n+j-1]×d行下标的下界是0，上界是m-1；列下标的下界是0，上界是n-1。元素aij的地址是：Loc(aij)=Loc(a00)+(i×n+j)×d矩阵广泛用于科学计算与工程应用中，在用高级语言编写

程序时，常常采用二维数组存储矩阵。采用这种存储方法时，

不仅使矩阵运算简单，而且存储密度高。但是，如果阶数很高

的矩阵中非零元素的分布具有一定的规律或者矩阵中有大量的

零元素，则为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储，就是为多个值相同的元素只分配一个存储空间，零元素不分配存储空间。5.5

矩阵的压缩存储5.5.1

特殊矩阵特殊矩阵是指n阶方阵中非零元素或零元素的分布具有一定的规律。下面我们讨论几种特殊矩阵的压缩存储。1．三角矩阵在n阶方阵中，以主对角线划分，如果矩阵的下三角(不包括主对角线)中的元素均为值相同的常数，则称为上三角矩阵，反之称为下三角矩阵。在多数情况下，三角矩阵的常数为零。两种三角矩阵如图5.3所示。图5.3

三角矩阵

2n(n

+1)2可以用向量A[0..n(n+1)/2]压缩存储三角矩阵，其中

A[0]~A[n(n+1)/2-1]存储矩阵的下(上)三角中的元素，向量的最后一个分量A[n(n+1)/2]存储三角矩阵中的常数。下三角矩阵按行优先的顺序存储，A[k]与aij

的对应关系是：i(i

-1)

+

j

-1k

=(5-3)当i≥j当i＜j

2n(n

+1)2上三角矩阵按列优先的顺序存储，A[k]与aij

的对应关系是：

j(j

-1)

+i

-1k

=(5-4)当i≤j当i＞j2．对称矩阵若n阶方阵A中的元素关于主对角线对称，即满足下述性质：aij=aji1≤i，j≤n则称

A

为对称矩阵。如果采用一维数组存储矩阵中的上三角或下三角元素，使对称的两个元素共享同一个存储空间，则可以节省近一半的存储空间。存储

n

阶对称方阵时，一维数组的长度为

n(n+1)/2。图

5.4(a)给出了一个

4

阶对称方阵，图

5.5

是其存储形式。图5.4

一个4阶对称方阵图5.5

一个4阶对称方阵的压缩存储3．对角矩阵所谓对角矩阵，是指方阵中的所有非零元素集中在以主对角线为中心的带状区域内，带状区域之外的元素值均为零。带宽为3的对角矩阵又称为三对角矩阵，如图5.6所示。图5.6

三对角矩阵显然，当|i-j|>1

时，元素aij

为0。一般地，对于k

对角矩阵(k

为奇数)，当|i-j|>(k-1)/2

时，元素aij

为0。n阶三对角矩阵有3n-2个非零元素，采用向量A[0..3n-3]按行优先的顺序压缩存储三对角矩阵。每个非零元素与向量下标的对应关系是：A[2(i-1)+j-1]=aij

1≤i≤n，i-1≤j≤i+1

(5-5)上述各种特殊矩阵的非零元素的分布都具有一定的规律，采用向量压缩存储时，通过元素与向量的对应关系，仍然可以对矩阵中的元素进行随机存取。5.5.2

稀疏矩阵设矩阵Amn

中有t

个非零元素，若t

远远小于矩阵元素的总数(即t<<m×n，1m

·

n≤0.05)，并且非零元素在矩阵中的分布没有规律，则称A

为稀疏矩阵。由于稀疏矩阵中的非零元素的分布没有规律，因此在存储非零元素的同时，还必须存储非零元素的位置信息。通常采用两种方法对稀疏矩阵进行压缩存储：顺序存储结构的三元组表和链式存储结构的十字链表。下面只讨论用三元组表实现对稀疏矩阵的压缩存储。将稀疏矩阵中的非零元素的行号、列号和元素值作为一个三元组(i，j，aij)，所有非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，则得到一个其结点均是三元组的线性表。我们将该线性表的顺序存储结构称为三元组表。在下面的讨论中，三元组均以按行优先的顺序进行排列。在三元组表中除了要表示非零元素之外，还需表示矩阵的行数、列数及非零元素的总数。三元组表的结构类型定义描述为//最大非零元素个数#define

MaxSize

1000typedef

int

datatype;typedefstruct{ inti,j;datatypev;}

Node;typedefstruct{ int

m,n,t;Node

data[MaxSize];}

spmatrix;//非零元素的行、列号//非零元素的元素值//三元组结构类型//行数,列数,非零元素个数//存放三元组表的向量//稀疏矩阵的三元组表结构类型设a为spmattrix型指针变量，图5.7(a)所示的稀疏矩阵A的三元组表如图5.7(b)所示。下面以矩阵的转置为例，说明采用三元组表的形式存储稀疏矩阵时，如何实现矩阵的运算。一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且A[i][j]=B[j][i]，0≤i≤m-1，0≤j≤n，即A的行是B的列，A的列

是B的行。例如，图5.7(a)中的A和图5.8(a)中的B互为转置矩阵。图5.7稀疏矩阵A和它的三元素表*a图5.8

稀疏矩阵B和它的三元素表

*b为了叙述方便，下面将三元组表*a中的成员a->data简称为三元组表，因为相对于其它成员而言，它是主要的。将A转置为B，就是将A的三元组表a->data置换为B的三元组表b->data，如果只是互换a->data中i和j的内容，那么所得到的b->data是按列存放的矩阵B的三元组表，还必须重新排列b->data中各结点的顺序。由于A的列是B的行，故按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先的顺序存放。算法的基本思想是：对a->data按列扫描n趟，在第col趟扫描中，找出所有列号等于col的那些三元组，将它们的行号、列号和元素值分别放入b->data的列号、行号和元素值中，即可得到B的按行优先的压缩存储表示。以图5.7和图5.8为例，设col=0，则扫描a->data找到列号为0的三元组依次是(0，0，3)和(2，0，

2)，存入b->data后为(0，0，3)和(0，2，2)，恰好为B中第0行的两个非零元素，只要依次取col=0，1，2，3，即可得到a->data的转置矩阵b->data。下面给出具体的算法：算法

5.3

矩阵的转置(用三元组表存储矩阵)。void

TransMat(spmatrix

*a,spmayrix

*b)//

返回稀疏矩阵A

的转置，ano

和bno

分别指示a→data

和b→data中结点序号//col

指示*a

的列号(即*b

的行号){ int

ano,bno,col;b->m=a->n; b->n=a->m;//A

和B

的行列数交换b->t=a->t;//非零元素个数if(b->t>0)

//

有非零元素，则转置{

bno=0；for(col=0;col<a->n;col++)//按*a

的列序转置，对a->data扫描n

趟for(ano=0;ano<a->t;

ano++)if(a->data[ano].j==col){//扫描一趟三元组表//

列号为col，则进行置换b->data[bno].i=a->data[ano].j;//a

的列号变为b

的行号//a

的行号变为b

的列号b->data[bno].j=a->data[ano].i;b->data[bno].v=a->data[ano].v;bno++;//b->data

结点序号加1}}}

//

TransMat该算法的时间主要耗费在col和ano的二重循环上，算法的时间复杂度为O(n×t)。而通常用二维数组表示矩阵时，其转置算法的时间复杂度是O(m×n)。如果非零元素个数大于矩阵的行数，则从转置算法的时间复杂度来说，采用三元组表存储就不合适了。一、名词解释串，顺序串，链串，特殊矩阵，稀疏矩阵，对称方阵，上(下)三角矩阵二、填空题含零个字符的串称为

串，用

表示。其他

串称为

串。任何串中所含

的个数称为该串的长度。当且仅当两个串的

相等并且各个对应位置上的字符都

时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的

串，该串称为它所有子串的

串。习题5通常将链串中每个存储结点所存储的字符个数称为。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上

。一般地，一个n维数组可视为其数据元素为

维数组的线性表。数组通常只有

和

两种基本运算。通常采用

存储结构来存放数组。对二维数组可有两种存储方法：一种是以

为主序的存储方式，另一种是以

为主序的存储方式。C语言数组用的是以

序为主序的存储方法。数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。若按行方式存放，则元素M[8][5]的起始地址为

；若按列优先方式存放，则元素M[8][5]的地址为

。二维数组M的成员是6个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要

个字节；M的第8列和第5行共占

个字节；若M按行方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的

元素的起始地址一致。需要压缩存储的矩阵可分为

矩阵和

矩阵两种。对称方阵中有近半的元素重复，若为每一对元素只分配一个存储空间，则可将n2个元素压缩存储到

个元素的存储空间中。假设以一维数组M(1..n(n+1)/2)作为n阶对称矩阵A的

存储结构，以行序为主序存储其下三角(包括对角线)中的元素，数组M和矩阵A间对应的关系为

。11．上三角矩阵中，主对角线上的第t行(1≤t≤n)有

个元素，按行优先顺序在一维数组M中存放上三角矩阵中的元素aij时，aij之前的前i-1行共有

个元素，在第i行上，aij是该行的第

个元素，M[k]和aij的对应关系是

。当i>j时，aij=c(c表示常量)，c存放在M[

]中。三、选择题1．在串的基本运算中，能够改变串值的运算有(

)。A.

EQAL(S,T)

B.

LENGTH(S)C.CONCAT(S,T)D.REPLACE(S,T,R)E.INDEX(S,T)2．在串的基本运算中，不能够改变串值的运算有(

)。B.

INSERT(S1,i,S2)D.

SUBSTR(S,i,j)A.

ASSIGN(S,T)C.

DELETE(S,i,j)E.

REPLACE(S,T,R)对于以行序为主序的存储结构来说，在数组A[c1..d1，c2..d2]中，c1和d1分别为数组A的第一个下标的下界和上界，c2和d2分别为第二个下标的下界和上界，每个数据元素占K个存储单元，二维数组中任一元素a[i,j]的存储位置可由(

)式确定。Loc(i,j)=

Loc(c1,

c2)+[(i-c1)*(d2-c2)

+

(j-c2)]*kLoc(i,j)=Loc(c1,

c2)+[(i-c1)*(d2-c2+1)

+

(j-c2)]*kLoc(i,j)=Loc(c1,

c2)+[(j-c2)*(d1-c1+1)

+

(i-c1)]*kLoc(i,j)=

Loc(c1,

c2)+[(j-c2)*(d1-c1)

+

(i-c1)]*k对于C语言的二维数组DataTypeA[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j]的存储位置可由(

)式确定。Loc(i,j)=Loc(0,0)+[

i*(n+1)

+j]*kLoc(i,j)=Loc(0,0)+[

j*(m+1)

+i]*kLoc(i,j)=Loc(0,0)+(i*n

+j)*kLoc(i,j)=Loc(0,0)+(

j*m

+i)*k5．稀疏矩阵的压缩存储方法是只存储(

)。A.

非零元素

B.

三元组(i,j,

aij)C.

aij

D. i,

j6．基于三元组表的稀