第4章 串与数组(Java版)

第四章串与数组教学内容4.1串的基本概念4.2串的存储结构4.3顺序串的实现4.4串的模式匹配操作4.5串的应用举例4.6数组的概念及顺序存储结构4.7特殊矩阵的压缩存储4.8稀疏矩阵的压缩存储教学重点与难点重点：掌握串类型定义中各基本操作的定义以及串的存储实现方法。掌握数组的定义、操作和存储结构难点：利用串的基本操作来实现串的其它操作问题，矩阵的压缩存储。1、串：是由零个或多个字符组成的有限序列。

一般记为s="a1a2…an",其中s为串名，单引号括起来的字符序列是串值。2、串的长度：串中字符的个数。3、空串：长度为0的串，即不包含任何字符的串，表示为"

"。4、空白串：由一个或多个空白字符组成的串，如："

"。注意：空串与空白串的区别串也是一种特殊的线性表。4.1.1串的基本概念5、子串：

主串：串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。6、字符在串中的位置：

子串在主串中的位置：如：s1="cdababef",s2="ab"字符在串中的序号值。子串在主串中出现时第一个字符在主串中的序号值。注意：空串是任意串的子串,任意串是其自身的子串。4.1.1串的基本概念8、串在程序作用中可分为：串常量:串变量:具有固定值，用常量来表示。如："abcdef",如：Strings;其值在程序中需要变化的串。7、两个串相等：长度相等各个字符对应相等串值相等4.1.1串的基本概念4.1.2串的抽象数据类型描述

clear()1）串的置空操作：

isEmpty()2）串的判空操作：

length()3）求串的长度操作：4）取字符元素操作：5）截取子串操作：charAT(index)substring(bengin,end)6）插入操作：insert(offset,str)1.基本操作4.1.2串的抽象数据类型描述

delete(begin,end)7）删除操作：

concat(str)8）串的连接操作：

compareTo(str)9）串的比较操作：10）子串定位操作：indexOf(str,begin)1.基本操作4.1.2串的抽象数据类型描述charAT(index)读取并返回串中的第index个字符值,其中:0≤index≤length()-1例如:当前串为"abcdefg"

charAT(0)=?acharAT(3)=?dcharAT(6)=?g4.1.2串的抽象数据类型描述substring(bengin,end)截取当前串中从序号begin开始,到序号end-1为止的子串并返回其值,其中:

0≤begin≤length()-1,1≤end≤length()例如:当前串为"commander"

substring(3,6)=?"

man"

substring(0,9)=?"commander"substring(8,9)=?"

r"substring(3,10)=?substring(9,1)=?4.1.2串的抽象数据类型描述将串str插入到当前串中的第offset个字符的前面,并返回操作结果。其中:0≤offset≤length()例如:当前串为"chater",则insert(3,"rac"）=?"charcter"insert(offset,str)insert(0,"rac")=?"

racchater"

insert(6,"rac")=?"

chaterrac

"

4.1.2串的抽象数据类型描述delete(bengin,end)删除当前串中从序号begin开始,到序号end-1为止的子串,并返回操作结果。其中:

0≤begin≤length()-1,1≤end≤length()例如:当前串为"commander"delete(3,6)=?"comd

"delete(0,9)=?"

"delete(8,9)=?"commande"delete(3,10)=?delete(9,1)=?4.1.2串的抽象数据类型描述

concat(str)将串str连接在当前串的后面，并返回其值。例如:当前串为"man",则concat("kind")=

?"mankink"4.1.2串的抽象数据类型描述

compareTo(str)将当前串与目标串str进行比较,若:当前串str，则返回值

0；

当前串str，则返回值

0；当前串

str，则返回值

0。例如:当前串为"

cat

"

compareTo("

case")?>0

compareTo("cate")?<0compareTo("

cht")?<0

compareTo("

ca")?>0

4.1.2串的抽象数据类型描述indexOf(str,begin)在当前串中从begin位置开始去找与非空串str相等的子串,若查找成功则返回当前串中的位置,否则返回-1,其中:0≤begin≤length()-1例如:当前串为"

bcaabcaaabc",str="

bca"indexOf(str,0)=?0indexOf(str,2)=?4indexOf(str,6)=?-1publicinterfaceIString{

publicvoidclear();

publicbooleanisEmpty();publicintlength();

publiccharcharAt(intindex);

publicIStringsubstring(intbegin,intend);

publicIStringinsert(intoffset,IStringstr);

……}4.1.2串的抽象数据类型描述2.串的抽象数据类型的Java接口描述

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

串的基本操作和线性表有很大差别:

在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。4.2.1串的顺序存储结构

串的顺序存储结构与线性表的顺序存储结构类似，可以采用一组地址连续的存储单元来存储串字符序列。顺序存储的串称为顺序串，顺序串的类型描述如下:publicclassSeqStringimplementsIString{privatechar[]strvalue;//存放串值

privateintcurlen;//存放串的长度

…}

其中：strvalue是一个字符数组，数组容量是11，该数组中存放字符串“Iamadog"，串的实际长度curlen的值是10。4.2.1串的顺序存储结构

4.2.2串的链式存储结构串的链式存储结构和线性表的链式存储结构类似，可以采用单链表来存储串值，串的这种链式存储结构称为链串。如下图:4.3.1顺序串的类定义（见教材P113-115）

publicclassSeqStringimplementsISring{ privatechar[]strValue; privateintcurLen;

}

publicSqStack(){//构造一个空串

}//以字符串常量构造串对象

publicSqStack(Stringstr)

{

}……stingValue=newchar[0];curLen=0;char[]tempchararray=str.toCharArray();strValue=tempchararray;curLen=tempchararray.length;4.3.1顺序串的类定义（见教材P113-115）

publicclassSeqStringimplementsISring{

……

}

publicSqStack(char[]value){//以字符数组构造串对象

}……this.strValue=newchar[value.length];for(inti=0;i<value.length;i++){//复制数组

this.strValue[i]=value[i];}curLen=value.length;publicvoidclear(){//顺序串的置空函数

}curLen=0;4.3.1顺序串的类定义（见教材P113-115）

publicclassSeqStringimplementsISring{

……

}……returncurLen;

//判空函数

publicbooleanisEmpty()

{

}//求顺序串长度函数

publicintlength(){

}

//返回顺序串中第index个字符publiccharcharAt(intindex){}

returncurLen==0;if(index<0||i>=curLen)

thrownewStringIndexOutofBoundsException(index);

returnstrValue[i];4.3.1顺序串的类定义（见教材P113-115）

publicclassSeqStringimplementsISring{

……

}……//扩充字符串的存储容量，参数指定容量

publicvoidallocate(intnewCapacity))

{

}char[]temp=srtValue;strValue=newchar[newCapacity];for(inti=0;i<temp.length;i++)strValue[i]=temp[i];//截子串操作publicIStringsubString(intbegin,intend){……}4.3.1顺序串的类定义（见教材P113-115）

publicclassSeqStringimplementsISring{

……

}//串的插入操作publicIStringinsert(intoffset,IStringstr){……}//串的删除操作publicIStringdelete(intbegin,intend){……}//串的比较操作publicintcompareTo(IStringstr){……}//子串的定位操作publicintindexOf(IStringstr,intbegin){……}4.3.2串的基本操作实现截子串操作

subString(begin,end)的实现（P115/算法4.1)2）算法步骤：

a.[检测参数begin和end是否合法]

if(begin<0||end>curLen||begin>end)

抛出异常1）操作要求：

返回当前串中序号从begin至end-1的子串。起始下标begin的范围是：0≤begin≤length()-1；结束下标end的范围是：1≤end≤length()。char[]buffer=newchar[end-begin];

for(inti=0;i<buffer.length;i++)//复制子串buffer[i]=this.strvalue[i+begin];returnnewSeqString(buffer);if(begin==0&&end==curLen)

returnthis;else{}b.[若要截取整个串，则返回原串；否则截取从begin到end-1之间的子串]截子串操作

subString(begin,end)的实现（P115/算法4.1)2）算法步骤：

char[]buffer=newchar[end-begin];

for(inti=0;i<buffer.length;i++)//复制子串buffer[i]=this.strvalue[i+begin];returnnewSeqString(buffer);if(begin==0&&end==curLen)

returnthis;else{}截子串操作

subString(begin,end)的实现（P115/算法4.1)3）算法：

publicIstringsubstring(intbegin,intend){}//算法4.1结束if(begin>0||end<curLen||begin>end)

thrownewStringIndexOutOfBoundsException(“参数不合法");

4.3.2串的基本操作实现2.串的插入操作

insert(offset,str)的实现（P116/算法4.2)1）操作要求：

在当前串中第offset个字符之前插入串str，并返回结果串对象。其中：参数offset的有效范围是：0≤offset≤length()。当offset=0，表示在当前串的开始处插入串str；当offset=length()，表示在当前串的结尾处插入串str。a.检测参数的合法性2.串的插入操作

insert(offset,str)的实现（P116/算法4.2)2）算法步骤：

if(offset<0||offset>curLen)

抛出异常b.判断空间是足够:如果不足,则扩充空间,否则转cintlen=str.length();//str串的长度intnewcount=this.curLen+len;//插入后串的长度if(newcount>strValue.length)allocate(newcount);c.后移：将strvalue中从offset开始的字符向后移动len个位置（注意：要从后往前移动）for(inti=this.curLen-1;i>=offset;i--){strValue[i+len]=strValue[i];}d.将串str插入到指定的位置（用字符复制的方法）2.串的插入操作

insert(offset,str)的实现（P116/算法4.2)2）算法步骤：

for(inti=0;i<len;i++){strValue[offset+i]=str.charAt(i);}e.修正表长this.curLen=newcount;3）算法：

publicIstringinsert(intoffset,IStingstr){}//算法4.2结束if(offset<0)||(offset>this.curlen

)

thrownewStringIndexOutOfBoundsException(“插入位置不合法");

2.串的插入操作

insert(offset,str)的实现（P116/算法4.2)intintlen=str.length();//str串的长度intnewcount=this.curLen+len;//插入后串的长度if(newcount>strValue.length)allocate(newcount);for(inti=this.curLen-1;i>=offset;i--){strValue[len+i]=strvalue[i];}for(inti=0;i<len;i++){strValue[offset+i]=str.charAt(i);}this.curLen=newcount;returnthis;4.3.2串的基本操作实现3.串的删除操作

delete(begin,end)的实现（P117/算法4.3)1）操作要求：

在当前串中删除从begin到end-1之间的子串，并返回当前串对象。参数begin和end的取值范围分别是：0≤begin≤length()-11≤end≤length()。a.检测参数的合法性3.串的删除操作

delete(begin,end)的实现（P117/算法4.3)2）算法步骤：

b.前移：将strvalue中从end开始到串尾的子串向前移动到从begin开始的位置for(inti=0;i<curlen-end;i++){strValue[begin

+i]=strValue[end+i];}if(begin<0||end>curLen||begin>end)

抛出异常c.修正表长this.curLen=curLen-(end-begin);3）算法：

publicIstringdelete(intbegin,intend){}//算法4.3结束if(begin<0||end>curLen||begin>end)

thrownewStringIndexOutOfBoundsException(“参数位置不合法");

for(inti=0;i<curlen-end;i++){strValue[begin

+i]=strValue[end+i];}this.curLen=curLen-(end-begin);returnthis;3.串的删除操作

delete(begin,end)的实现（P117/算法4.3)4.3.2串的基本操作实现4.串的比较操作

compareTo(str)的实现（P117/算法4.4)1）操作要求：

将当前串与目标串str进行比较,若:当前串str，则返回值

0；

当前串str，则返回值

0；当前串

str，则返回值

0。a.求当前串长度和str串长度的最小值并赋给n3.串的比较操作

compareTo(str)的实现（P117/算法4.4)2）算法步骤：

b.从下标0到n-1依次取出两个串中对应的字符进行比较，若不等，则返回第一个不相等的字符的数值差。for(intk=0;k<n;k++){if(strValue[i]!=str.strValuse[i])returnstrValue[i]-str.strValuse[i];}intlen1=this.curlen;intlen2=str.curlen;intn=Math.min(len1,len2);3.串的比较操作

compareTo(str)的实现（P117/算法4.4)2）算法步骤：

c.若下标从0到n-1对应的字符均相等，则返回两个串长度的差。

returnlen1-len2;3）算法：

publicintcomparTo(IStringstr){}//算法4.4结束3.串的比较操作

compareTo(str)的实现（P117/算法4.4)intlen1=curlen;intlen2=str.curlen;intn=Math.min(len1,len2);for(intk=0;k<n;k++){if(strValue[i]!=str.strValuse[i])returnstrValue[i]-str.strValuse[i];}returnlen1-len2;

这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。4.4串的模式匹配操作初始条件：串S和T存在，T是非空串，

0≤start≤S.Length()-1。操作结果：若主串S中存在和串T值相同的子串返回它在主串S中第start个字符之后第一次出

现的位置；否则函数值为0。首先，回忆一下串匹配(查找)的定义:S.

index(T,start)4.4串的模式匹配操作一、模式匹配的概念1、什么叫模式匹配

设s,t是两个串，s="s1s2…sn",t="t1t2…tm"(0≤m≤<n)在s串中寻找等于t的子串的过程称为模式匹配。（即，子串的定位操作）其中：s:主串，t：模式串2、用一个函数实现：匹配成功：返回t在s中start位置后首次出现的序号匹配不成功：返回-1模式匹配是各种串处理系统中最重要的操作之一4.4串的模式匹配操作

二、模式匹配算法1、简单算法（Brute-Force模式匹配算法

）2、KMP算法(D.E.Knuth,V.R.Pratt,J.H.Morris)4.4串的模式匹配操作1）算法思想：用T串字符依次与S串字符比较，分别引进变量i和j指示主串s和模式串t的初始字符:i=start;j=0;P118算法4.5动画4-3-1a.若S[i]=T[j],则继续往下比较(即i++;j++;)b.若S[i]≠T[j],则从主串的下一个字符起再重新和模式串T依次从头开始与S中字符依次比较；（即，重新置i=i-j+1,j=0)c.重复a、b直到i>=S.length()或j>=T.length(),若j>=T.length()则匹配成功，函数返回T串在S串start位置之后首次出现的位序号值,否则匹配失败,函数返回-1。4.4串的模式匹配操作-简单算法（带回溯）intIndexOf(IStringt,intstart){

//返回子串t在主串（当前串）中第start个字符之后的位置。若不存在，

则函数值为-1。其中，t非空，0≤start≤S.Length()-1。

}//算法4.5结束2）算法：inti=start,j=0,slen=this.length(),tlen=t.length();while(i<slen&&j<tlen){if(this.charAt[i]==t.charAt[i]{i++;j++;}//继续比较后继字符

else{i=i-j+1;j=0;}//指针后退重新开始匹配if(j>=tlen)

return

i-tlen;elsereturn-1;时间复杂度：O(slen*tlen)4.4串的模式匹配操作-简单算法（带回溯）算法4.5模拟演示

因为在最坏情况下，对i的每个值，j++需执行n-1次。动画4-3-24.4串的模式匹配操作-简单算法（带回溯）

你能否举出一个使算法4.5运行处最坏情况的例子？例如：S="aaaaaaaaaaab"，

T="aaab"，start=0需要执行36次对应位的比较才匹配成功。4.4串的模式匹配操作-简单算法（带回溯）存在问题：

当S[i]<>T[j]时，已经得到的结果：

S[i-j+1..i-1]==T[1..j-1]

若已知T[1..k-1]==T[j-k+1..j-1]

则有S[i-k+1..i-1]==T[1..k-1]所以只需将模式向右滑动至模式中第k个字符与主串中第i个字符对齐。如：S=“ababcabcacbab”与T=“abcac”

的匹配过程动画4-3-34.4串的模式匹配操作-简单算法（带回溯）KMP算法的时间复杂度可以达到

O(s.length()+t.length())

模式匹配的一种改进算法KMP算法(D.E.Knuth,J.H.Morris,V.R.Pratt)见P124/算法4.84.4串的模式匹配操作-KMP算法定义：模式串的next函数模式串中，每一个tj都有一个k值对应，这个k值仅与模式串本身有关，而与主串s无关。一般用next[j]函数来表示tj对应的k值。4.4串的模式匹配操作-KMP算法由定义可推出下列模式串的next函数值：j012345模式串abcabcNext[j]-1000124.4串的模式匹配操作-KMP算法由定义可推出下列模式串的next函数值：j0123456模式串ababaaaNext[j]-10012314.4串的模式匹配操作-KMP算法int

index_KMP(IStringt,intstart){//0≤start≤this.length()-1

int[]next=getNext(T);//计算模式串的next[]函数值

inti=start,j=0;

while(i<this.length()&&j<t.length){if

(j==-1||this.charAt[i]==t.charAt[j])

{++i;++j;}

//继续比较后继字符else

j=next[j];

//模式串向右移动

}

if(j<t.length())return-1;elsereturni-t.length();//匹配成功}//算法4.8结束P124/算法4.8【例4.3】编制一个字符串测试程序，测试顺序串类SeqString的新建串、插入串、删除串和取子串等操作。4.5串的应用

【例4.4】设计一个类，分别统计模式匹配的BF算法和KMP算法的比较次数。假设两个测试例子是：主串S="cdbbacc"，模式串T="abcd"。主串S="aaaaaaaaaa"，模式串T="aaaab"。【例4.3】编制一个字符串测试程序，测试顺序串类SeqString的新建串、插入串、删除串和取子串等操作。（教材P125）4.5串的应用

【例4.4】设计一个类，分别统计模式匹配的BF算法和KMP算法的比较次数。假设两个测试例子是：（教材P126）主串S="cdbbacc"，模式串T="abcd"。主串S="aaaaaaaaaa"，模式串T="aaaab"。【例4.5】编程实现文本文件加密解密程序。该程序一方面可以对指定的文本文件按照指定的密钥进行加密处理，加密后生成密码文件；另一方面，程序也可对指定的加密后的密码文件按照密钥进行解密处理，还原成明码文件。（教材P128）4.5串的应用【课前思考】1.在你的认识中，“数组”是什么？数组：是一个具有固定数量的同类型数据的有序集特点：数组的每一个元素由值及下标所确定元素类型一致

数组也是一种线性的数据结构，它可以看成是线性表的一种扩充。例如：（见下一页）

因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式。为什么顺序表以及其它线性结构的顺序存储结构都可以用"一维数组"来描述？4.6数组的概念及顺序存储结构-例如：一个n×m矩阵Aa0,0a0,1……a0,j……a0,m-1a1,0a1,1……a1,j……a1,m-1an-1,1an-1,2……an-1,j……an-1,m-1…………ai,1ai,2……ai,j……ai,m-1…………

可以看成一个二维数组，也可以看成是由以n个长度为m的线性表为数据元素所组成的线性表。

A=（a0,a1,…,an-1)ai=(ai,0,ai,1,…,ai,j,…,ai,m-1)数组是n(n≥1)个具有相同类型的数据元素a0,a1,…,an-1构成的有限序列，并且这些数据元素占用一片地址连续的内存单元。其中：n称为数组的长度。4.6.1数组的基本概念

一维数组可以看成一个顺序存储结构的线性表。数组元素是一维数组的数组称为二维数组。4.6.2数组的抽象数据类型描述

length()1）求数组长度操作：

基本操作

getValue(index1,index2,…,indexn)2）取值操作：

assign(value,index1,index2,…,indexn)3）赋值操作：类型特点:1)只有引用型操作，没有插入和删除操作；

2)数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(行优先顺序)；2)以列序为主序(列优先顺序)。

数组的顺序存储表示要解决的是一个"如何用一维的存储地址来表示多维的关系"的问题。4.6.3数组的顺序存储结构例如：二维数组

称为基地址或基址。以“行序为主序”的顺序存储映象二维数组A[m][n]中任一元素ai,j

的存储位置

LOC(i,j)=LOC(0,0)+(n×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

a2,0a2,1a2,2a2,0a2,1a2,24.6.3数组的顺序存储结构

类似地，假设三维数组R[p][m][n]中每个数据元素占L个存储地址，并以LOC(i,j,k)表示下标为(i,j,k)的数据元素的存储地址，则该数组中任何一对下标(i,j,k)对应的数据元素在“以行为主”的顺序映象中的存储地址为：LOC(i,j,k)=LOC(0,0,0)+(i×m×n+j×n+k)×L同理，在"以列为主"的顺序映象中的存储地址为：

LOC(i,j)=LOC(0,0)+(m×j+i)×L

4.6.3数组的顺序存储结构推广到一般情况，可得到n维数组A[m1][m2]…[mn]的数据元素a[i1][i2]…[in]的存储位置的映象关系

称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。(i1×m2×...×mn+i2×m3×...×mn+…+in-1×mn+

in)×L4.6.3数组的顺序存储结构[例1]假设按低下标优先存储整数数组A9×3×5×8时，第一个元素的字节地址是100，每个整数占四个字节，问元素a3125的地址是什么？LOC（a3125)=？100+(3×3×5×8+1×5×8+2×8+5)×4=17844.6.3数组的顺序存储结构[例2]

设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始以列序为主序顺序存放，求数组元素a[5，8]的存储首地址.LOC（a[5,8])=BA+(7×8+4)

×3=BA+180

如果在矩阵中有许多值相同的元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。

所谓压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配空间。4.7特殊矩阵的压缩存储什么是特殊矩阵？具有许多相同数据元素或零元素，且非零元在矩阵中的分布有一定规则例如:对称矩阵三角矩阵对角矩阵4.7特殊矩阵的压缩存储若n阶矩阵A中的元素满足下述性质：

aij=aji

0≤i,j≤

n-1则称为对称矩阵。1.空间分配：

每一对对称元素仅分配一个存储，则可将n2个元素压缩到n(n+1)/2个元素空间中去。4.7.1对称矩阵的压缩存储2.地址公式：

假设以一维数组S[n(n+1)/2]作为n阶对称矩阵A的存储结构

例如，n=4a00a10a11a30a31a32a33a20a21a22a00a10a11a20

a21a22a30a31a32a33S0123456789K4.7.1对称矩阵的压缩存储

若aij

存储到S[k]中，则k

与i,j对应关系为:(其中(0≤i,j

≤n-1))i*(i+1)/2+j(i>=j)K=j*(j+1)/2+i(i<j)K=0,1,…,n(n+1)/20123456789K

对于任意给定一对行列号(i,j)，均可在S中找到矩阵的元素aij

，反之，对于所有的k=0,1,…,n(n+1)/2-1，都能确定s[k]中的元素在矩阵中的位置(i,j)。

a00a10a11a20

a21a22a30a31a32a33S1.空间分配：对角线及对角线上（或下）的每一元素分配一个存储空间，对角线下（或上）的重复元素分配一个存储空间。占存储空间数：?n*(n+1)/2。4.7.2三角矩阵的压缩存储2.地址公式：

假设以一维数组S[n(n+1)/2]作为n阶三角矩阵A的存储结构存储形式如下：

例如，n=4a00a10a11a30a31a32a33a20a21a2204.7.2三角矩阵的压缩存储a00a10a11a20

a21a22a30a31a32a33S012345678910K

若aij

存储到S[k]中，则k

与i,j

对应关系为:i*(i+1)/2+j(i>=j,0≤i,j≤n-1)K=空(i<j,0≤i,j≤n-1)(下三角矩阵）

K=0,1,…,n(n+1)/2-14.7.2三角矩阵的压缩存储对角矩阵(带状矩阵)

只将带状区域内的元素进行存储，而带状区域外的元素，即满足|i-j|>d的aij不存储。n(2d+1)-d(d+1)）(其中d称为半带宽，2d+1称为带宽）4.7.3对角矩阵的压缩存储1.空间分配：非零元素个数：?n(2d+1）空间分配数：?2.地址公式：

假设以一维数组S[n(2d+1)]作为n阶对角矩阵A的存储结构存储形式如下：4.7.3对角矩阵的压缩存储

例如，n=5

若aij

存储到S[k]中，则k

与i,j

对应关系为:i*(2d+1)+d+(j-i)K=

其中：K=0~n(2d+1)i,j=0~n-14.7.3对角矩阵的压缩存储

所以：地址计算公式为：

Loc(I,j)=Loc(0,0)+K*L其中L为每个数据元素所占的存储单元个数

假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为

0.05的矩阵为稀疏矩阵且零值元素分布是随机的。何谓稀疏矩阵？4.8稀疏矩阵的压缩存储

有较多零元素且非零元素分布无规律的矩阵为稀疏矩阵。

以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。即计算效率不高。4.8稀疏矩阵的压缩存储1)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。4.8稀疏矩阵的压缩存储稀疏矩阵的压缩存储方法:1、三元组顺序表2、十字链表4.8稀疏矩阵的压缩存储011404-511-720362328rowcolumnvalue355datarowscolsnumsM=M4.8.1稀疏矩阵的三元组表存储—定义

classTripleNode{}三元组顺序表存储结构描述：4.8.1稀疏矩阵的三元组表存储—定义privateintrow;//行号

privateintcolumn;//列号

privateintvalue;//元素值……三元组表中的结点类（见教材P136）publicclass

SparseMatrix

{}三元组顺序表存储结构描述：4.8.1稀疏矩阵的三元组表存储—定义

privateTripleNodedata[];//三元组表

privateintrows;//行数

privateintcols;//列数

privateintnums;//非零元素个数……稀疏矩阵三元组顺序表类（见教材P137）4.8.1稀疏矩阵的三元组表存储—基本操作1.初始化三元组顺序表操作

（P138/算法4.9)1）操作要求：

按行序优先的原则依次扫描已知稀疏矩阵的所有元素，并把非零元素插入到三元组顺序表中。2）操作方法：

根据已知的一个稀疏矩阵mat（二维数组），构造一个与其对应的三元组顺序表。a.统计出稀疏矩阵mat中非零元素的个数(只要按行优先的顺序对mat扫描一遍即可完成）3）算法步骤：

for(i=0;i<mat.length;i++){}for(j=0;j<mat[i].length;j++){

}

if(mat[i][j]!=0)

count++;b.完成对rows,cols,nums的赋值rows=mat.length;//行数cols=mat[0].length;//列数nums=count;//非零元素的个数1.初始化三元组顺序表操作

（P138/算法4.9)3）算法步骤：

d.将mat中的非零元素依次存放到三元组顺序表中（即建立三元组表）。for(i=0;i<mat.length;i++){}for(j=0;j<mat[i].length;j++){

}

if(mat[i][j]!=0)

data[k]=newTripleNode(i,j,mat[i][j]);k++;c.申请三元组顺序表的存储空间data=newTripleNode[nums];1.初始化三元组顺序表操作

（P138/算法4.9)4）算法：(P138/算法4.9)

publicSparseMatrix

(intmat[][])

{

inti,j,k=0,count=0;}//算法4.9结束for(i=0;i<mat.length;i++){

//统计非零元素的个数

}for(j=0;j<mat[i].length;j++){

}

if(mat[i][j]!=0)

count++;rows=mat.length;//行数cols=mat[0].length;//列数nums=count;//非零元素的个数data=newTripleNode[nums];//申请空间for(i=0;i<mat.length;i++){//建立三元组表}for(j=0;j<mat[i].length;j++){

}

if(mat[i][j]!=0){

data[k]=newTripleNode(i,j,mat[i][j]);k++;}M矩阵T矩阵2.矩阵的转置操作

（P139/算法4.10)如何求转置矩阵？4.8.1稀疏矩阵的三元组表存储—基本操作用常规的二维数组表示时的算法

其时间复杂度为:O(rows×cols)for(col=0;col=<rows;++col)

for(row=0;row<cols;++row)T[row][col]=M[col][row];2.矩阵的转置操作（P139/算法4.10)用“三元组”表示时如何实现？方法一：(算法4.10)思想：按this.data的列序进行转置，然后存放在连续的存储空间tm.data中。2.矩阵的转置操作（P139/算法4.10)操作要求：

将用三元组顺序表存储的当前矩阵转达置为用三元组顺序表存储的矩阵tm,并返回其值。

要创造矩阵对象tm.101440-511-702363228011404-511-720362328this.datatm.data355datarowscolsnumsthis535datarowscolsnumstm2.矩阵的转置操作（P139/算法4.10)矩阵转置的实现算法：(P139/算法4.10)

publicSparseMatrixtranspose()

{

}//算法4.10结束

SparseMatrixtm=newSparseMatrix(nums);//创建矩阵对象

tm.cols=rows;//行数变为列数tm.rows=cols;//列数变为行数tm.nums=nums;//非零元素个数不变intq=0;

for(intcol=0;col<cols;col++){for(intp=0;p<nums;p++){if(data[p].getColumn()==col){tm.data[q].setRow(data[p].getColumn());tm.data[q].setColumn(data[p].getRow());tm.data[q].setValue(data[p].getValue());q++;}}}returntm;

这种方法当前矩阵有多少列就要对它扫描多少遍，每扫描一遍只得到tm中的一行非零元素。时间复杂度并没得到改观，原因是：2.矩阵的转置操作（P139/算法4.10)

其时间复杂度为:O(cols×nums)方法二：（快速排序）思想：按this.data的行序进行转置，并将转置后的三元组置入