数据结构3第四章串

第四章 串和数组4.1串的定义及运算4.2

串的存储结构4.3

串的运算的实现结束放演4.1

串及其操作4.1.1

基本概念串的定义串(string)是由零个或多个字符组成的有限序列，记作s=“a0a1…an-1”，其中s为串的名字，用成对的双引号括起来的字符序列为串的值，但两边的引号不算串值，不包含在串中。ai(0≤i≤n-1)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。空串不含任何字符的串称为空串，它的长度n=0，记为s=“”。通常用￠表示3．空格串含有一个或多个空格的串，称为空格串，它的长度是空格的个数，记为s=“”。子串、主串若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。子串的位置子串的第一个字符在主串中的序号。例如，a=“guo”d=zhong

guo

guo

a是b的子串，a在b中的位置是7特别地，空串是任意串的子串，任意串是其自身的子串。4.1.2

串的运算1.

复制

strcopy(s,t)将串t的值复制到s串中例如：strcpy(s3,s1);

//s3=“dirtreeformat”2.

求串长度

strlen(s)求串中字符的个数。例如：printf(“%d”,strlen(s1));

输出13char

s1[20]=“dirtreeformat”,s2[20]=“file.mem”;char

s3[30],*p;int

result;3

联接

strcat(s,t)表示将s串和t串联接起来，使t串接入s串的后面。例如：strcat(s3,”/”)；strcat(s3,s2);

//s3=“dirtreeformat/file.mem”4

串比较（compare)int

strcmp(chars1,char

s2);该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1<s2\s1=s2或s1>s2例如：result=strcmp(“baker”,”Baker”)

result>0result=strcmp(“12”,”12”);

result=0result=strcmp(“Joe”,”Joseph”);

result<0substr(s,start,len)5.

子串表示截取s串中从第start个字符开始连续len个字符。求子串位置

index(s,t)求t子串在s主串中首次出现的位置，若t串不是s串的子串，则位置为零。串替换

replace

(s,t,v)将s串中所有的子串t用串v代替。串插入

insert

(s,i,t)在S串的第i个位置插入t串。串删除

delete(s,i,j)删除串S中从第i个字符开始连续j个字符。4.2串的存储结构4.2.1

顺序存储串的顺序存储结构，也称为顺序串，与第二章介绍的顺序表类似。但由于串中元素全部为字符,故存放形式与顺序表有所区别。一．串的非紧缩存储一个存储单元中只存储一个字符，和顺序表中一个元素占用一个存储单元类似。具体形式见图4-1,设串S=“How

do

youdo”。二．串的紧缩存储根据各机器字的长度，尽可能将多个字符存放在一个字中。假设一个字可存储4个字符，则紧缩存储具体形式见图4-2。Howdoyoudo图4-1S

串的非紧缩存储Howdoyoudo图4-2S

串的紧缩存储三．顺序串的数据类型描述在C语言中只有紧缩格式没有非紧缩格式。其形式定义为：maxlen 200

/*串允许的最大字符个数*/struct#definetypedef{charintstring

[maxlen]；len；/*串的长度*/}orderstring如图4.1所示的串s=“abcdef”。abcdef\0下标：

0

1

2

3

4

5图4.1 串的顺序表示算法4.1

实现两个串的联接orderstring Concat（orderstring

s1，orderstring

s2）/*将串s1和s2联接成新串，放到s中由s返回*/{orderstring

s；if（（s1.len+s2.len）>＝maxlen）printf（”联接后的串太长”）；else{for

（i=0；i<s1.len；i++）s.string[i]=s1.string

[i]；for（i=0；i<s2.len；i++）{s.string[s1.len+i]=s2.string[i]；s.len=s1.len+s2.len；s.string[s.len]=‘\0’；}return

（s）；}算法4.2

求一个串的子串orderstring Substring（orderstring

s，int

i，intlen）/*从串s中把第i个字符开始的连续len个字符组成的子串赋给

sub

*/{

orderstring

sub；{if（（i+len-1）>s.len

）printf（“超界！”）else{

for（k=0；k<len；k++）sub.string[k]=s.string[i+k-1]；sub.len=len；sub.string[len]=‘\0’}return（sub）}注意：在串的静态存储结构中必须预先定义允许存放的最大字符个数，这容易造成系统空间浪费或运行错误。在C语言中有这样一个规定，程序员使用串的长度一旦超过允许存放串的最大字符数，系统将自动减去超出字符。4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式堆式存储结构的形式定义为：typedef

struct{char

*str；int

len；}heapstring；下面给出字符串在堆式存储时，串的基本操作的实现方法。算法4.3heapstring实现两个串的联接*Concat（heapsting

*s1，heapstring*s2）/*将串s1和s2联接成新串，放到s中由s返回*/{ heapstring

*s；n=s1->len+s2->len；if（！（s->str=（char*）malloc（n*sizeof

（char））））printf

（“可分配空间不足！”）；else{ strcpy（s->str，s1->str）；

/* C语言中的串拷贝命令*/C语言中的串联接命令*/strcat（s->str，s2->str）；

/*s->len=n；free（s1->str）；free（s2->str）；return

（s）}}4.2.2

链式存储顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。一．结点大小为1的链式存储和前面介绍到的单链表一样，每个结点为一个字符，链表也可以带头结点。S=‘abcdef’的存储结构具体形式见图4-3。aSbcdef

^图4-3S

串的链式存储示意图typedef

struct

node{char

data;struct

node

*next;}lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。二．结点大小为K的链式存储为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。a

b

c

d

e

f

\0

\0

^S头结点图

4-4 S

串的结点大小为

4

的链式存储串的块链式存储形式定义如下：blocksize

10/*用户自定义块的大小*/struct

Blocknode#definetypedef{

charstructch[blocksize]；Blocknode

*next；}Blocknode；typedef

struct{

Blocknode

*head；/*串的头指针*//*串的当前长度*/int

curlen；}Blstring；下面给出字符串在链式存储时，串的基本操作的实现方法。算法4.4

实现两个串的联接。Blstring *concat

（Blstring*s1，Blstring*s2）{Blstring

*p，*q；p=s1->head

；while（!p->next）p=p->next；q=s2->head；p->next=q；free（s2->head）；free（s2->tail）；return（s1）；}四、子串定位顺序串上的子串定位运算index(S，T)子串的定位运算通常称为串的模式匹配，是串处理中最重要的运算之一。设串s=‘a1a2…an’，串T=‘b1b2…bm’(m≤n)，子串定位是要在主串S中找出一个与子串T相同的子串。通常把主串S称为目标，把子串T称为模式，把从目标S中查找模式为T的子串的过程称为“模式匹配”。匹配有两种结果出现：若S中有模式为T的子串，就返回该子串在S中的位置，当S中有多个模式为T的子串，通常只要找出第一个子串即可，这种情况称为匹配成功，若S中无模式为T的子串，返回值为零，称为匹配失败。模式匹配过程如图4-10所示，假设S=“abababac”，T=“abac”。a

b

a

b

a

b

a

ca

b

a

c(

a

)

第

一

趟a

b

a

b

a

b

a

ca

b

a

b

a

b

a

ca

b

a

c(

b

)

第

二

趟

匹

配a

b

a

b

a

b

a

c匹

配

s

4

„

t

4s

2

„

t1a

b

a

c(c)

第a

b

a

c(

d

)

第

四

趟

匹

配

s

4

„

t1三

趟

匹

配

s

6

„

t

4a

b

a

b

a

b

a

ca

b

a

c(

e

)

第

五

趟

匹

配

成

功图

4

-

1

0

模

式

匹

配

过

程int Index（orderstring

s，orderstring

t，int

p）/*在主串s中寻找在第p个字符后模式串t第一次出现的位置*/{

int

i=p

，j=0；while

（（i<s.len）&&（j<t.len））{if

（s.string[i]=t.string[j]{

i++；j++；}else{i=i-j+1；j=0；}if

（j=

=t.len）return（i-t.len）；return（-1）；}}4.4

数组的定义及基本操作一、数组的定义数组是一种“同构”的数据元素的集合，它的每个数据元素类型相同，结构一致。而且存储在一块地址连续的存储单元中。它是线性表在维数上的扩张，也就是线性表中的元素又是一个线性表。例如，二维数组：可看成一个线性表A=（a0，a1，……，ap）（p=m-1或n-1）a00

a01

…a10

a11

……

…

…am-1,0

am-1,1

…a0,n-1a1,n-1…am-1,n-1Amn=4.4

数组的定义及基本操作二、数组的基本操作数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作，通常数组的运算不包括插入和删除这样的操作。4.5

数组的顺序存储结构由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。通常有两种顺序存储方式：⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a00,a01,…,a0,n-1,a10,a11,…a1,n-1,……,am-1,0,

…,am-1,n-1在PASCAL、C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a00,a10,…,am-1,0,a01,a11,…am-1,1,……,am-1,1,

…,an-1,m-1在FORTRAN语言中，数组就是按列优先顺序存储的。在以行序为主序的存储结构中，设每个数组元素占L个单元，元素a的地址用

loc（a）表示。设数组元素的起始地址为base：二维数组的地址计算公式：loc（aij）=base+（i×n+j）×L4.6

矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种

规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。4.6

矩阵的压缩存储一、特殊矩阵的压缩存储1、对称矩阵若n阶矩阵A中的数据元素满足下述性质aij=aji

（0≤i，j≤n-1）则称A为n阶对称称矩阵；因aij与aji相等，二者只需分配一个存储单元。这样，可将n*n个存储单元压缩到n（n+1）/2个单元。a0,n-1a1,n-1…an-1,0a00

a01a10

a11…

…an-1,1…………an-1,n-1Amn=说明：按行序为主序：a00a10a11a20a21…...an-1,0…...an-1,n-1n(n+1)/2-1

k=0

1

2

3

4

i(i

+1)/2

+j，i

‡

jk

=

j(j

+1)/2

+i,i

<

j若i≧j，则ai

j在下三角形中。ai

j之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，ai

j之前恰有j个元素，因此有：k=i*(i+1)/2+j若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：k=j*(j+1)/2+i4.6

矩阵的压缩存储一、特殊矩阵的压缩存储2、对角矩阵如果矩阵中的所有的非零元素都集中在以主对角线为中心的带状区域则称为对角矩阵，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。如常见的三对角矩阵。a00

a01

0a10

a11

a120

…

an-2,n-3

an-2,n-200

0

…an-2,n-1an-1,n-1…an-1,n-20a21

a22

a230

……………………

.

00

……………

00……………说明：a00a01a10a11a12…...…...an-1,n-13(n-1)按行序为主序：非零元素仅出现在主对角(aii,0≦i≦n-1）上，以及紧邻主对角线上面的那条对角线上(ai,i+1,0≦i≦n-2)和紧邻主对角线下面的那条对角线上

(ai+1,

i,0≦i≦n-2)。显然，当∣i-j∣>1时，元素aij=0。k=0

1

2

3

43i-1

当i=j+1时k=

3i

当i=j时3i+1

当i=j-1时4.6

矩阵的压缩存储素的三元，若s远远小于矩阵元素的总数(即s的存储方法；省存储单元，很自然地想到使用压般是没有规律的，因此在存储非零行和列的位置（i,j）。一个三元组(因此，稀疏矩阵可由表示非零元二、稀疏矩阵的压缩存储设矩阵Amn中有s个非零元素，则称A为稀疏矩阵。下面讨论它（1）三元组表示法在存储稀疏矩阵时，为了节方法。但由于非零元素的分布一同时，还必须同时记下它所在的一确定了矩阵A的一个非零元素。组及其行列数唯一确定。

i,j,aij)唯

0

0

元素的

2

00

缩存储

00

0

<<m×n)

0

00

800400000000500070000000609000

0

M

=

M由{(0,1,8),

(0,4,4),

(2,3,5),

(3,2,7),(4,0,2), (4,5,6),

(5,2,9))

}

和矩阵维数（6,7）唯一确定

0

0

2

00

00

0

0

00

800400000000500070000000609000

0

M

=

018044235327402456529i

jv0123456三元组表三元组表示法描述三元组表表示描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合。比如在执行将矩阵B相加到矩阵A上的运算时，某位置上的结果可能会由非零元变为零元，但也可能由零元变为非零元，这就会引起在A的三元组表中进行删除和插人操作，从而导致大量结点的移动。三元组表存储的定义：#

define

maxsize256/*

最大非零元素个数*/typedef

struct/*

三元组类型*/{

int

i，j；/*

该非零元素的行下标和列下标*/datatype

v；}

triple；typedef

struct{

triple

data[maxsize+1]；int

mu，nu，tu；}

Tsmatrix；/*

三元组表类型*//*

三元组表存储空间*//*

矩阵的行数，列数和非零元素个数*/一个m×n的矩阵A，它的转置B是一个n×m的矩阵，那么a[i][j]=b[j][i]，0≦i≦m-1，0≦j≦n-1，即A的行是B的列，A的列是B的行。将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，假设A是按行优先顺序存储，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。方法一：按列序转置由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表A，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人B中，即可得到B的按行优先的压缩存贮表示。矩阵的转置：矩阵的转置：方法二：快速转置即按ma中三元组次序转置，转置结果放入mb中恰当位置，此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数。实现：设两个数组num[col]：表示矩阵M中第col列中非零元个数

pos[col]：指示M中第col列第一个非零元在mb中位置显然有：pos[0]=1;pos[col]=pos[col-1]+num[col-1]; (1£col

£a.nu-1)8

0

0

4

0

0

0

0

0

0

0

0

col0123456num[col]1121110cpot[col]1235678作业：P81第一、二题直接填在课本中

P81第三题3，4写在作业本上通常有两种顺序存储方式：⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：

a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN语言中，数组就是按列优先顺序存储的。以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，

先排最左下标，从左向右，最后排最右下

标。按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元

素所占用的单元数，就可以将数组元素的

存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存

取，即顺序存储的数组是一个随机存取结

构。例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1)×n个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1)×n+j-1个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(

j-1)*p+(k-1)]*d上述讨论均是假设数组各维的下界是不是1，更一般的二维数组是A[c1..d1,c2..d2]，这里

c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d5.3矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。5.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：1513750800189263025170613a00a10

a

11a20

a21

a23………………..an-1

0

a

n-11

a

n-12

…a

n-1n-1图5.1对称矩阵在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：(i+1)=n(n+1)/2因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j

0≦k<n(n+1)/2若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：k=j*(j+1)/2+i 0≦

k<n(n+1)/2令I=max(i,j)，J=min(i,j)，则k和i,j的对应关系可统一为：k=I*(I+1)/2+J 0≦

k<n(n+1)/2因此，aij的地址可用下列式计算：LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i,j)。由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储，见下图：例如a21和a12均存储在sa[4]中，这是因为

k=I*(I+1)/2+J=2*(2+1)/2+1=4a00k=0a101a112a203……an-1

0n(n-1)/2……an-1,n-1n(n-1)/2-12、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对

角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。a00

a01

… a

0

n-1c

a11

… a

1

n-1a00a10c

…

ca11

…

c…..……………..an-1

0

an-11

… an-1

n-1c

c…

a

n-1

n-1(a)上三角矩阵图5.2三角矩阵(b)下三角矩阵三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第p行(0≦p<n)恰有n-p个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有(n-p)=i(2n-i+1)/2个元素，在第i行上，aij前恰好有j-i个元素：

aij,aij+1,…aij-1。因此，sa[k]和aij的对应关系是：i(2n-i+1)/2+j-i 当i≦jn(n+1)/2 当i>jk=下三角矩阵的存储和对称矩阵类似，sa[k]和aij对应关系是：i(i+1)/2+j

i≧jk=n(n+1)/2

i>j3、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，a00

a01a10

a11

a12a21

a22

a23….…..….

图5.3

对角矩阵an-2

n-3

an-2

n-2

an-2

n-1an-1

n-2

an-1

n-1非零元素仅出现在主对角(aii,0≦i≦n-1上，紧邻主对角线上面的那条对角线上

(aii+1,0≦i≦n-2)和紧邻主对角线下面的那条对角线上(ai+1

i,0≦i≦n-2)。显然，当∣i-j∣>1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若∣i-j∣>(k-1)/2，则元素aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。在三对角矩阵里附满足条件i=0，j=0、1，或

i=n-1j=n-2、n-1或1<i<n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元

素都要是3个，因此，需存储的元素个数为3n-2。a00a01a10a11a12a21……a

n-1n-2a

n-1n-1K=0

1

2

3

4

5

…

… 3n-2 3n-1数组sa中的元素sa[k]与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d上例中，a34对应着sa[10]。k=2*i+j=2*3+4=10a21对应着sa[5]k=2*2+1=5由此，我们称sa[0..3*n-2]是阶三对角带状矩阵A的压缩存储表示。上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。5.3.2稀疏矩阵什么是稀疏矩阵？简单说，设矩阵A中有

s个非零元素，若s远远小于矩阵元素的

总数（即s≦m×n），则称A为稀疏矩阵。精确点，设在的矩阵A中，有s个非零元素。令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵。在

存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如，下列三元组表((1,2,12)(1,3,9),(3,1,-

3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。0 12

9 0

0

0

00

0

0 0

0

0

00 0

-30 0

1512

0

0

0 18

09 0

0 24

0

00

0 24

0

0

0

00 18

0 0

0

0

015

0 0

–7

0

0

00 0

14

0

0

00 0

0

0

0

00 0

0

0

0

0图5.4稀疏矩阵M和TM=-3

0

0 0

0

14

00 0

0T0=0

–7一、三元组顺序表假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元顺序表。#define

maxsize

10000typedef

int

datatype;typedef

struct{int

i,j;datatype

v;}triple;typedef

struct{triple

data[maxsize];int

m,n,t;}tripletable;设A为tripletable型的结构变量，图5.4中所示的稀疏矩阵的三元组的表示如下：i

jv121213931-3361443245218611564-7下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][

j]=b[

j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。将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中的每一列col(0≦col≦n-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入

b.data中，即可得到B的按行优先的压缩存储表示。ijv13-3161521122518319342446-76314Void

transmatrix(tripletable

a,tripletable

b){intp

qcol;b.m=a.n;b.n=a.m;b.t=a.t;if(b.t<=0)printf(“A=0\n”);q=0;for(col=1;col<=a.n;col++)for(p=0;p<=a.t;p++)if(a.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;q++;}}分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为

O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：for(col=0;col<=n-1;++col)for(row=0;row<=m;++row)t[col][row]=m[row][col];其时间复杂度为O(n*m)。当非零元素的个数

t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t<=m*n的情况。下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确

定三元组的位置关系，二次扫描由位置

关系装入三元组。可见，位置关系是此

种算法的关键。为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。为此，需要设置两个一维数组

num[0..n]和cpot[0..n]num[0..n]：统计M中每列非零元素的个数，

num[col]的值可以由A的第二列求得。ccpot[0..n]：由递推关系得出M中的每列第一个非零元素在B中的位置。算法通过cpot数组建立位置对应关系：

cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]2<=cpl<=a.n例如：图5.4中的矩阵M和相应的三元组A可以求得num[col]和cpot[col]的值如下：col1234567num[col]2221010pot[col]

135788912vq…A

i

j

v第一列元素个数第二列元素个数第三列元素个数pnumcpotq=cpot[col]p21v快速转置算法如下：void

fasttranstri(tritupletable

b,tritupletable

a){int

p,q,col,k;int

num[0..a.n],copt[0..a.n];b.m=a.n;

b.n=a.m;

b.t=a.t;if(b.t<=0)printf(“a=0”\n);for(col=1;col<=a.u;++col)num[col]=0;for(k=1;k<=a.t;++k)++num[a.data[k].j];cpot[0]=1;for(col=2;col<=a.t;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=a.t;++p){col=a.data[p].j;

q=cpot[col];b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;

++cpot[col];}}}二、带行表的三元组有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵