數(shù)據(jù)結(jié)構(gòu)(java版)劉小晶：第4章-串與數(shù)組-課件

第四章串與數(shù)組第四章串與數(shù)組教學內(nèi)容4.1串的基本概念4.2串的存儲結(jié)構(gòu)4.3順序串的實現(xiàn)4.4串的模式匹配操作4.5串的應用舉例4.6數(shù)組的概念及順序存儲結(jié)構(gòu)4.7特殊矩陣的壓縮存儲4.8稀疏矩陣的壓縮存儲教學內(nèi)容4.1串的基本概念4.2串的存儲結(jié)構(gòu)4.教學重點與難點重點：掌握串類型定義中各基本操作的定義以及串中基本操作的應用。掌握數(shù)組的定義、操作和存儲結(jié)構(gòu)難點：串的基本操作的應用，即如何運用串的基本操作來實現(xiàn)其它串的復雜操作。矩陣的壓縮存儲。教學重點與難點重點：掌握串類型定義中各基本操作的定義以及串中1、串：是由零個或多個字符組成的有限序列。

一般記為s="

a0a1…an-1",其中s為串名，雙引號括起來的字符序列是串值。2、串的長度：串中字符的個數(shù)。3、空串：長度為0的串，即不包含任何字符的串，表示為"

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

"。注意：空串與空白串的區(qū)別串也是一種特殊的線性表。4.1.1串的基本概念1、串：是由零個或多個字符組成的有限序列。一般記為5、子串：

主串：串中任意個連續(xù)字符組成的子序列稱為該串的子串。包含子串的串相應地稱為主串。6、字符在串中的位置：

子串在主串中的位置：如：s1="cdababef",s2="ab"字符在串中的序號值。子串在主串中第一次出現(xiàn)時的第一個字符在主串中的序號值。注意：空串是任意串的子串,任意串是其自身的子串。4.1.1串的基本概念5、子串：串中任意個連續(xù)字符組成的子序列稱為該串的子串。包含7、兩個串相等：長度相等各個字符對應相等串值相等4.1.1串的基本概念7、兩個串相等：長度相等各個字符對應相等串值相等.2串的抽象數(shù)據(jù)類型描述

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

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

length()3）求串的長度操作：4）取字符元素操作：5）截取子串操作：charAT(index)substring(bengin,end)6）插入操作：insert(offset,str)1.基本操作4.1.2串的抽象數(shù)據(jù)類型描述clear()1）4.1.2串的抽象數(shù)據(jù)類型描述

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

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

compareTo(str)9）串的比較操作：10）子串定位操作：indexOf(str,begin)1.基本操作4.1.2串的抽象數(shù)據(jù)類型描述delete(begi4.1.2串的抽象數(shù)據(jù)類型描述charAT(index)讀取并返回串中的第index個字符值,其中:0≤index≤length()-1例如:當前串為"abcdefg"

charAT(0)=?acharAT(3)=?dcharAT(6)=?g4.1.2串的抽象數(shù)據(jù)類型描述charAT(index)4.1.2串的抽象數(shù)據(jù)類型描述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串的抽象數(shù)據(jù)類型描述substring(be4.1.2串的抽象數(shù)據(jù)類型描述將串str插入到當前串中的第offset個字符的前面,并返回操作結(jié)果。其中:

0≤offset≤length()例如:當前串為"chater",則insert(3,"rac"）=?"

character"insert(offset,str)insert(0,"rac")=?"

racchater"

insert(6,"rac")=?"

chaterrac

"

4.1.2串的抽象數(shù)據(jù)類型描述將串str插入到當前4.1.2串的抽象數(shù)據(jù)類型描述delete(bengin,end)刪除當前串中從序號begin開始,到序號end-1為止的子串,并返回操作結(jié)果。其中:

0≤begin≤length()-1,1≤end≤length()例如:當前串為"commander"delete(3,6)=?"comder

"delete(0,9)=?"

"delete(8,9)=?"commande"delete(3,10)=?delete(9,1)=?4.1.2串的抽象數(shù)據(jù)類型描述delete(bengi4.1.2串的抽象數(shù)據(jù)類型描述

concat(str)將串str連接在當前串的后面，并返回其值。例如:當前串為"man",則concat("kind")=

?"mankind"4.1.2串的抽象數(shù)據(jù)類型描述concat(str)4.1.2串的抽象數(shù)據(jù)類型描述

compareTo(str)將當前串與目標串str進行比較,若:當前串str，則返回值

0；

當前串str，則返回值

0；當前串

str，則返回值

0。例如:當前串為"

cat

"

compareTo("

case")?>0

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

cht")?<0

compareTo("

ca")?>0

4.1.2串的抽象數(shù)據(jù)類型描述compareTo(s4.1.2串的抽象數(shù)據(jù)類型描述indexOf(str,begin)在當前串中從begin位置開始去找與非空串str相等的子串,若查找成功則返回在當前串中的位置,否則返回-1,其中:0≤begin≤length()-1例如:當前串為"

bcaabcaaabc",str="

bca"indexOf(str,0)=?0indexOf(str,2)=?4indexOf(str,6)=?-14.1.2串的抽象數(shù)據(jù)類型描述indexOf(str,bepublicinterfaceIString{

publicvoidclear();

publicbooleanisEmpty();publicintlength();

publiccharcharAt(intindex);

publicIStringsubstring(intbegin,intend);

publicIStringinsert(intoffset,IStringstr);

……}4.1.2串的抽象數(shù)據(jù)類型描述2.串的抽象數(shù)據(jù)類型的Java接口描述publicinterfaceIString{4.1.

串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。

但串的基本操作和線性表有很大差別:

在線性表的基本操作中，大多以“單個元素”作為操作對象；在串的基本操作中，通常以“串的整體”作為操作對象。串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的4.2.1串的順序存儲結(jié)構(gòu)

串的順序存儲結(jié)構(gòu)與線性表的順序存儲結(jié)構(gòu)類似，可以采用一組地址連續(xù)的存儲單元來存儲串字符序列。順序存儲的串稱為順序串，順序串的類型描述如下:publicclassSeqStringimplementsIString{privatechar[]strvalue;//存放串值

privateintcurlen;//存放串的長度

…}

4.2.1串的順序存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)與線性表的

其中：strvalue是一個字符數(shù)組，數(shù)組容量是11，該數(shù)組中存放字符串“Iamadog"，串的實際長度curlen的值是10。4.2.1串的順序存儲結(jié)構(gòu)

其中：strvalue是一個字符數(shù)組，數(shù)組容量是11，該4.2.2串的鏈式存儲結(jié)構(gòu)串的鏈式存儲結(jié)構(gòu)和線性表的鏈式存儲結(jié)構(gòu)類似，可以采用單鏈表來存儲串值，串的這種鏈式存儲結(jié)構(gòu)稱為鏈串。如下圖:4.2.2串的鏈式存儲結(jié)構(gòu)串的鏈式存儲結(jié)構(gòu)和線性表的鏈4.3.1順序串的類定義（見教材P113-115）

publicclassSeqStringimplementsISring{ privatechar[]strValue; privateintcurLen;

}

publicSqStack(){//構(gòu)造一個空串

}//以字符串常量構(gòu)造串對象

publicSqStack(Stringstr)

{

}……stingValue=newchar[0];curLen=0;char[]tempchararray=str.toCharArray();strValue=tempchararray;curLen=tempchararray.length;4.3.1順序串的類定義（見教材P113-115）pub4.3.1順序串的類定義（見教材P113-115）

publicclassSeqStringimplementsISring{

……

}

publicSqStack(char[]value){//以字符數(shù)組構(gòu)造串對象

}……this.strValue=newchar[value.length];for(inti=0;i<value.length;i++){//復制數(shù)組

this.strValue[i]=value[i];}curLen=value.length;publicvoidclear(){//順序串的置空函數(shù)

}curLen=0;4.3.1順序串的類定義（見教材P113-115）pub4.3.1順序串的類定義（見教材P113-115）

publicclassSeqStringimplementsISring{

……

}……returncurLen;

//判空函數(shù)

publicbooleanisEmpty()

{

}//求順序串長度函數(shù)

publicintlength(){

}

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

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

thrownewStringIndexOutofBoundsException(index);

returnstrValue[i];4.3.1順序串的類定義（見教材P113-115）pub4.3.1順序串的類定義（見教材P113-115）

publicclassSeqStringimplementsISring{

……

}……//擴充字符串的存儲容量，參數(shù)指定容量

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）pub4.3.1順序串的類定義（見教材P113-115）

publicclassSeqStringimplementsISring{

……

}//串的插入操作publicIStringinsert(intoffset,IStringstr){……}//串的刪除操作publicIStringdelete(intbegin,intend){……}//串的比較操作publicintcompareTo(IStringstr){……}//子串的定位操作publicintindexOf(IStringstr,intbegin){……}4.3.1順序串的類定義（見教材P113-115）pub4.3.2串的基本操作實現(xiàn)截子串操作

subString(begin,end)的實現(xiàn)（P115/算法4.1)2）算法步驟：

a.[檢測參數(shù)begin和end是否合法]

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

拋出異常1）操作要求：

返回當前串中序號從begin至end-1的子串。起始下標begin的范圍是：0≤begin≤length()-1；結(jié)束下標end的范圍是：1≤end≤length()。4.3.2串的基本操作實現(xiàn)截子串操作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{}b.[若要截取整個串，則返回原串；否則返回截取從begin到end-1之間的子串]截子串操作

subString(begin,end)的實現(xiàn)（P115/算法4.1)2）算法步驟：

char[]buffer=newchar[end-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)的實現(xiàn)（P115/算法4.1)3）算法：

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

thrownewStringIndexOutOfBoundsException("參數(shù)不合法");

char[]buffer=newchar[end-4.3.2串的基本操作實現(xiàn)2.串的插入操作

insert(offset,str)的實現(xiàn)（P116/算法4.2)1）操作要求：

在當前串中第offset個字符之前插入串str，并返回結(jié)果串對象。其中：參數(shù)offset的有效范圍是：0≤offset≤length()。當offset=0，表示在當前串的開始處插入串str；當offset=length()，表示在當前串的結(jié)尾處插入串str。4.3.2串的基本操作實現(xiàn)2.串的插入操作1）操作要求a.檢測參數(shù)的合法性2.串的插入操作

insert(offset,str)的實現(xiàn)（P116/算法4.2)2）算法步驟：

if(offset<0||offset>curLen)

拋出異常b.判斷空間是足夠:如果不足,則擴充空間,否則轉(zhuǎn)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];}a.檢測參數(shù)的合法性2.串的插入操作insert(offd.插入：將串str插入到指定的位置（用字符復制的方法）2.串的插入操作

insert(offset,str)的實現(xiàn)（P116/算法4.2)2）算法步驟：

for(inti=0;i<len;i++){strValue[offset+i]=str.charAt(i);}e.修正串長this.curLen=newcount;d.插入：將串str插入到指定的位置（用字符復制的方法）23）算法：

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

)

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

2.串的插入操作

insert(offset,str)的實現(xiàn)（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;3）算法：publicIstringinsert4.3.2串的基本操作實現(xiàn)3.串的刪除操作

delete(begin,end)的實現(xiàn)（P117/算法4.3)1）操作要求：

在當前串中刪除從begin到end-1之間的子串，并返回當前串對象。參數(shù)begin和end的取值范圍分別是：0≤begin≤length()-11≤end≤length()。4.3.2串的基本操作實現(xiàn)3.串的刪除操作1）操作要求a.檢測參數(shù)的合法性3.串的刪除操作

delete(begin,end)的實現(xiàn)（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);a.檢測參數(shù)的合法性3.串的刪除操作delete(beg3）算法：

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

thrownewStringIndexOutOfBoundsException(“參數(shù)位置不合法");

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

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

delete(begin,end)的實現(xiàn)（P117/算法4.3)3）算法：publicIstringdelete4.3.2串的基本操作實現(xiàn)4.串的比較操作

compareTo(str)的實現(xiàn)（P117/算法4.4)1）操作要求：

將當前串與目標串str進行比較,若:當前串str，則返回值

0；

當前串str，則返回值

0；當前串

str，則返回值

0。4.3.2串的基本操作實現(xiàn)4.串的比較操作1）操作要求a.求當前串長度和str串長度的最小值并賦給n3.串的比較操作

compareTo(str)的實現(xiàn)（P117/算法4.4)2）算法步驟：

b.從下標0到n-1依次取出兩個串中對應的字符進行比較，若不等，則返回第一個不相等的字符的數(shù)值差。for(inti=0;i<n;i++){if(strValue[i]!=str.strValuse[i])returnstrValue[i]-str.strValuse[i];}intlen1=this.curlen;intlen2=str.curlen;intn=Math.min(len1,len2);a.求當前串長度和str串長度的最小值并賦給n3.串的比較3.串的比較操作

compareTo(str)的實現(xiàn)（P117/算法4.4)2）算法步驟：

c.若下標從0到n-1對應的字符均相等，則返回兩個串長度的差。

returnlen1-len2;3.串的比較操作compareTo(str)的實現(xiàn)（P113）算法：

publicintcomparTo(IStringstr){}//算法4.4結(jié)束3.串的比較操作

compareTo(str)的實現(xiàn)（P117/算法4.4)intlen1=curlen;intlen2=str.curlen;intn=Math.min(len1,len2);for(inti=0;i<n;i++){if(strValue[i]!=str.strValuse[i])returnstrValue[i]-str.strValuse[i];}returnlen1-len2;3）算法：publicintcomparTo(1.子串的定位操作

indexOf(str,beging)的實現(xiàn)（補充）1）操作要求：在當前串中從begin位置開始去找與非空串str相等的子串,若查找成功則返回在當前串中的位置,否則返回-1,其中:0≤begin≤length()-1補充：串的基本操作的應用1.子串的定位操作indexOf(str,beging)的1.子串的定位操作

indexOf(str,begin)的實現(xiàn)（補充）可利用串比較、求串長和截子串等操作實現(xiàn)子串的定位操作indexOf(str,begin)。compareTo(substring(begin,begin+str.length())?0

this串str串str串ibeginthis.legth()-str.length()+12）算法的基本思想：

1.子串的定位操作indexOf(str,begin)的實1.子串的定位操作

indexOf(str,begin)的實現(xiàn)（補充）3）算法publicintindexOf(IStringStr,intbgein){

}while(i<=n-m+1){

substring(i,m);if(compareTo(substring(i,m),str)

!=0)++i;

elsereturni;}n=this.length();

m=str.length();i=begin;if(begin>=0){

}return-1;

//S中不存在與T相等的子串1.子串的定位操作indexOf(str,begin)的實2.串的置換操作

replace(begin,s1,s2)的實現(xiàn)（補充）1）操作要求：

在當前對象串this中，從下標begin開始，將所有的s1非空子串替換為s2非空串。

例如：假設

this=abcaabcaaabca，s1=bca若

s2=

x，

則經(jīng)置換后得到

this=若

s2=bc，則經(jīng)置換后得到

S=axaxaaxabcabcaabc2.串的置換操作replace(begin,s1,s2)的2）算法的基本思想：

2.串的置換操作

replace(begin,s1,s2)的實現(xiàn)（補充）source串

s1串s2串s2串begin=index+s1.length()

sub1indexss串(初始是一個空串）

sub2beginsource串（初始為this串）2）算法的基本思想：2.串的置換操作replace3）算法2.串的置換操作

replace(begin,s1,s2)的實現(xiàn)（補充）P148/習題三中的第2題，作為學生課后作業(yè)完成。3）算法2.串的置換操作replace(begin,s1,

這是串的一種重要操作，很多軟件，若有“編輯”菜單項的話，則其中必有“查找”子菜單項。4.4串的模式匹配操作這是串的一種重要操作，很多4.4串的模操作條件：當前串this和t串存在，t是非空串，0≤start≤S.Length()-1。操作結(jié)果：若串this中存在和串t值相同的子串返回它在this中第start個字符之后第一次出

現(xiàn)的位置；否則函數(shù)值為0。首先，回憶一下串匹配(查找)的定義:index(t,start)4.4串的模式匹配操作操作條件：當前串this和t串存在，t是非空首先，回憶一一、模式匹配的概念1、什么叫模式匹配

設s,t是兩個串，s="s0s1…sn-1",t="t0t1…tm-1"(0≤m≤<n)在s串中尋找等于t的子串的過程稱為模式匹配。（即，子串的定位操作）其中：s:主串，t：模式串2、用一個函數(shù)實現(xiàn)：匹配成功：返回t在s中start位置后首次出現(xiàn)的序號匹配不成功：返回-1模式匹配是各種串處理系統(tǒng)中最重要的操作之一4.4串的模式匹配操作一、模式匹配的概念1、什么叫模式匹配設s,t是兩

二、模式匹配算法1、簡單算法（Brute-Force模式匹配算法

）2、KMP算法(D.E.Knuth,V.R.Pratt,J.H.Morris)4.4串的模式匹配操作二、模式匹配算法1、簡單算法2、KMP算法4.4串的模1）算法思想：用T串字符依次與S串字符比較，分別引進變量i和j指示主串s和模式串t的初始字符:i=start;j=0;P118算法4.5動畫4-3-1a.若S[i]=T[j],則繼續(xù)往下比較(即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()則匹配成功，函數(shù)返回T串在S串start位置之后首次出現(xiàn)的位序號值,否則匹配失敗,函數(shù)返回-1。4.4串的模式匹配操作-簡單算法（帶回溯）1）算法思想：用T串字符依次與S串字符比較，分別引進變量i和intIndexOf(IStringt,intstart){

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

則函數(shù)值為-1。其中，t非空，0≤start≤S.Length()-1。

}//算法4.5結(jié)束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++;}//繼續(xù)比較后繼字符

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

return

i-tlen;elsereturn-1;時間復雜度：O(slen*tlen)4.4串的模式匹配操作-簡單算法（帶回溯）intIndexOf(IStringt,intst算法4.5模擬演示

因為在最壞情況下，對i的每個值，j++需執(zhí)行n-1次。動畫4-3-24.4串的模式匹配操作-簡單算法（帶回溯）算法4.5模擬演示因為在最壞情況下，對i的每個值，j+

你能否舉出一個使算法4.5運行處最壞情況的例子？例如：S="aaaaaaaaaaab"，

T="aaab"，start=0需要執(zhí)行36次對應位的比較才匹配成功。4.4串的模式匹配操作-簡單算法（帶回溯）你能否舉出一個使算法4.5運行處最壞情況的例子？例如存在問題：

當S[i]<>T[j]時，已經(jīng)得到的結(jié)果：

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串的模式匹配操作-簡單算法（帶回溯）存在問題：當S[i]<>T[j]時，如：S=“KMP算法的時間復雜度可以達到

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

模式匹配的一種改進算法KMP算法(D.E.Knuth,J.H.Morris,V.R.Pratt)見P124/算法4.84.4串的模式匹配操作-KMP算法KMP算法的時間復雜度可以達到模式匹配的一種改進算法見P1定義：模式串的next函數(shù)模式串中，每一個tj都有一個k值對應，這個k值僅與模式串本身有關，而與主串s無關。一般用next[j]函數(shù)來表示tj對應的k值。4.4串的模式匹配操作-KMP算法定義：模式串的next函數(shù)模式串中，每一個tj都有一由定義可推出下列模式串的next函數(shù)值：j012345模式串a(chǎn)bcabcNext[j]-1000124.4串的模式匹配操作-KMP算法由定義可推出下列模式串的next函數(shù)值：j由定義可推出下列模式串的next函數(shù)值：j0123456模式串a(chǎn)babaaaNext[j]-10012314.4串的模式匹配操作-KMP算法由定義可推出下列模式串的next函數(shù)值：jint

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

int[]next=getNext(T);//計算模式串的next[]函數(shù)值

inti=start,j=0;

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

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

{++i;++j;}

//繼續(xù)比較后繼字符else

j=next[j];

//模式串向右移動

}

if(j<t.length())return-1;elsereturni-t.length();//匹配成功}//算法4.8結(jié)束P124/算法4.8intindex_KMP(IStringt,int【例4.3】編制一個字符串測試程序，測試順序串類SeqString的新建串、插入串、刪除串和取子串等操作。4.5串的應用

【例4.4】設計一個類，分別統(tǒng)計模式匹配的BF算法和KMP算法的比較次數(shù)。假設兩個測試例子是：主串S="cdbbacc"，模式串T="abcd"。主串S="aaaaaaaaaa"，模式串T="aaaab"。【例4.3】編制一個字符串測試程序，測試順序串類SeqStr【例4.3】編制一個字符串測試程序，測試順序串類SeqString的新建串、插入串、刪除串和取子串等操作。（教材P125）4.5串的應用【例4.3】編制一個字符串測試程序，測試順序串類SeqStrpublicclassExample4_3{publicstaticvoidmain(Stringargs[]){char[]chararray={'W','o','r','l','d'};SeqStrings1=newSeqString();//構(gòu)造一個空串

SeqStrings2=newSeqString("Hello");//以字符串常量構(gòu)造串對象

SeqStrings3=newSeqString(chararray);//以字符數(shù)組構(gòu)造串對象

System.out.println("串s1="+s1+",s2="+s2+",s3="+s3);s1.insert(0,s2);System.out.println("串s1在第0個字符前插入串s2后,s1="+s1);s1.insert(1,s3);System.out.println("串s1在第1個字符前插入串s3后,s1="+s1);s1.delete(1,4);System.out.println("串s1刪除第1到第3個字符后,s1="+s1);System.out.println(“串s1中從第2到第5個字符組成的子串是:“+s1.substring(2,6));}}書中P125publicclassExample4_3{書中P124.5串的應用

【例4.4】設計一個類，分別統(tǒng)計模式匹配的BF算法和KMP算法的比較次數(shù)。假設兩個測試例子是：（教材P126）主串S="cdbbacc"，模式串T="abcd"。主串S="aaaaaaaaaa"，模式串T="aaaab"。4.5串的應用【例4.4】設計一個類，分別統(tǒng)計模式匹配的【例4.5】編程實現(xiàn)文本文件加密解密程序。該程序一方面可以對指定的文本文件按照指定的密鑰進行加密處理，加密后生成密碼文件；另一方面，程序也可對指定的加密后的密碼文件按照密鑰進行解密處理，還原成明碼文件。（教材P128）4.5串的應用【例4.5】編程實現(xiàn)文本文件加密解密程序。該程序一方面可以對【課前思考】1.在你的認識中，“數(shù)組”是什么？數(shù)組：是一個具有固定數(shù)量的同類型數(shù)據(jù)的有序集特點：數(shù)組的每一個元素由值及下標所確定元素類型一致

數(shù)組也是一種線性的數(shù)據(jù)結(jié)構(gòu)，它可以看成是線性表的一種擴充。例如：（見下一頁）

因為在高級編程語言中實現(xiàn)的一維數(shù)組正是用的這種順序存儲的映象方式。為什么順序表以及其它線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)都可以用"一維數(shù)組"來描述？4.6數(shù)組的概念及順序存儲結(jié)構(gòu)-【課前思考】1.在你的認識中，“數(shù)組”是什么？數(shù)組：是一個例如：一個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…………

可以看成一個二維數(shù)組，也可以看成是由以n個長度為m的線性表為數(shù)據(jù)元素所組成的線性表。

A=（a0,a1,…,an-1)ai=(ai,0,ai,1,…,ai,j,…,ai,m-1)例如：一個n×m矩陣Aa0,0a0數(shù)組是n(n≥1)個具有相同類型的數(shù)據(jù)元素a0,a1,…,an-1構(gòu)成的有限序列，并且這些數(shù)據(jù)元素占用一片地址連續(xù)的內(nèi)存單元。其中：n稱為數(shù)組的長度。4.6.1數(shù)組的基本概念

一維數(shù)組可以看成一個順序存儲結(jié)構(gòu)的線性表。數(shù)組元素是一維數(shù)組的數(shù)組稱為二維數(shù)組。數(shù)組是n(n≥1)個具有相同類型的數(shù)據(jù)元素a0,a14.6.2數(shù)組的抽象數(shù)據(jù)類型描述

length()1）求數(shù)組長度操作：

基本操作

(只有引用型操作，沒有插入和刪除操作）

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

assign(value,index1,index2,…,indexn)3）賦值操作：4.6.2數(shù)組的抽象數(shù)據(jù)類型描述length()數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。有兩種順序映象的方式:1)以行序為主序(行優(yōu)先順序)；2)以列序為主序(列優(yōu)先順序)。

數(shù)組的順序存儲表示要解決的是一個"如何用一維的存儲地址來表示多維的關系"的問題。4.6.3數(shù)組的順序存儲結(jié)構(gòu)數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。有兩種例如：二維數(shù)組

稱為基地址或基址。以“行序為主序”的順序存儲映象二維數(shù)組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數(shù)組的順序存儲結(jié)構(gòu)例如：二維數(shù)組稱為基地址或基址。以“行序為主序”的順序

類似地，假設三維數(shù)組R[p][m][n]

中每個數(shù)據(jù)元素占L個存儲地址，并以LOC(i,j,k)表示下標為(i,j,k)的數(shù)據(jù)元素的存儲地址，則該數(shù)組中任何一對下標(i,j,k)對應的數(shù)據(jù)元素在“以行為主”的順序映象中的存儲地址為：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數(shù)組的順序存儲結(jié)構(gòu)類似地，假設三維數(shù)組R[p][m][n]中每個數(shù)推廣到一般情況，可得到n維數(shù)組A[m1][m2]…[mn]的數(shù)據(jù)元素a[i1][i2]…[in]的存儲位置的映象關系

稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲位置是其下標的線性函數(shù)。(i1×m2×...×mn+

i2

×m3×...×mn+…

+in-1×mn+

in)×L4.6.3數(shù)組的順序存儲結(jié)構(gòu)書中P133推廣到一般情況，可得到n維數(shù)組A[m1[例1]假設按低下標優(yōu)先存儲整數(shù)數(shù)組A9×3×5×8時，第一個元素的字節(jié)地址是100，每個整數(shù)占四個字節(jié)，問元素a3125的地址是什么？LOC（a3125)=？100+(3×3×5×8+1×5×8+2×8+5)×4=17844.6.3數(shù)組的順序存儲結(jié)構(gòu)[例2]

設有數(shù)組A[1..8,1..10]，數(shù)組的每個元素占3字節(jié)，數(shù)組從內(nèi)存首地址BA開始以列序為主序順序存放，求數(shù)組元素a[5，8]的存儲首地址.LOC（a[5,8])=BA+(7×8+4)

×3=BA+180[例1]假設按低下標優(yōu)先存儲整數(shù)數(shù)組A9×3×5×8時，第一

如果在矩陣中有許多值相同的元素或者是零元素。為了節(jié)省存儲空間，可以對這類矩陣進行壓縮存儲。

所謂壓縮存儲是指：為多個值相同的元只分配一個存儲空間；對零元不分配空間。4.7特殊矩陣的壓縮存儲如果在矩陣中有許多值相同的元素或者是零元素。為了節(jié)省什么是特殊矩陣？具有許多相同數(shù)據(jù)元素或零元素，且非零元在矩陣中的分布有一定規(guī)則例如:對稱矩陣三角矩陣對角矩陣4.7特殊矩陣的壓縮存儲什么是特殊矩陣？4.7特殊矩陣的壓縮存儲若n階矩陣A中的元素滿足下述性質(zhì)：

aij=aji

0≤i,j≤

n-1則稱為對稱矩陣。1.空間分配：

每一對對稱元素僅分配一個存儲，則可將n2個元素壓縮到n(n+1)/2個元素空間中去。4.7.1對稱矩陣的壓縮存儲若n階矩陣A中的元素滿足下述性質(zhì)：1.空間2.地址公式：

假設以一維數(shù)組S[n(n+1)/2]作為n階對稱矩陣A的存儲結(jié)構(gòu)

例如，n=4a00a10a11a30a31a32a33a20a21a22a00a10a11a20

a21a22a30a31a32a33S0123456789K4.7.1對稱矩陣的壓縮存儲2.地址公式：假設以一維數(shù)組S[n(

若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)/2-10123456789K

對于任意給定一對行列號(i,j)，均可在S中找到矩陣的元素aij

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

a00a10a11a20

a21a22a30a31a32a33S若aij存儲到S[k]中，則k與i,j對應關1.空間分配：對角線及對角線上（或下）的每一元素分配一個存儲空間，對角線下（或上）的零元素不分配存儲空間。占存儲空間數(shù)：?n*(n+1)/2。4.7.2三角矩陣的壓縮存儲1.空間分配：對角線及對角線上（或下）的每一元2.地址公式：

假設以一維數(shù)組S[n(n+1)/2]作為n階三角矩陣A的存儲結(jié)構(gòu)存儲形式如下：

例如，n=4a00a10a11a30a31a32a33a20a21a2204.7.2三角矩陣的壓縮存儲a00a10a11a20

a21a22a30a31a32a33S012345678910K2.地址公式：假設以一維數(shù)組S[n(n+1)

若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三角矩陣的壓縮存儲若aij存儲到S[k]中，則k與i,j對角矩陣(帶狀矩陣)

只將帶狀區(qū)域內(nèi)的元素進行存儲，而帶狀區(qū)域外的元素，即滿足|i-j|>d的aij不存儲。n(2d+1)-d(d+1)(其中d稱為半帶寬，2d+1稱為帶寬）4.7.3對角矩陣的壓縮存儲1.空間分配：非零元素個數(shù)：?n(2d+1）空間分配數(shù)：?對角矩陣(帶狀矩陣)只將帶狀區(qū)域內(nèi)的元素進行2.地址公式：

假設以一維數(shù)組S[n(2d+1)]作為n階對角矩陣A的存儲結(jié)構(gòu)存儲形式如下：4.7.3對角矩陣的壓縮存儲

例如，n=5書中有誤P1352.地址公式：假設以一維數(shù)組S[n(2d+

若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對角矩陣的壓縮存儲

所以：特殊矩陣中數(shù)組元素的地址計算公式為：Loc(i,j)=Loc(0,0)+K*L其中L為每個數(shù)據(jù)元素所占的存儲單元個數(shù)。若aij存儲到S[k]中，則k與i,j

假設m行n列的矩陣含t個非零元素，則稱為稀疏因子。通常認為

0.05的矩陣為稀疏矩陣且零值元素分布是隨機的。何謂稀疏矩陣？4.8稀疏矩陣的壓縮存儲

有較多零元素且非零元素分布無規(guī)律的矩陣為稀疏矩陣。假設m行n列的矩陣含t個非零元素，則

以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時產(chǎn)生的問題:1)零值元素占了很大空間;2)計算中進行了很多和零值的運算，遇除法，還需判別除數(shù)是否為零。即計算效率不高。4.8稀疏矩陣的壓縮存儲以常規(guī)方法，即以二維數(shù)組表示1)零值元素1)盡可能少存或不存零值元素；解決問題的原則:2)盡可能減少沒有實際意義的運算；3)操作方便。即：能盡可能快地找到與下標值(i，j)對應的元素，能盡可能快地找到同一行或同一列的非零值元。4.8稀疏矩陣的壓縮存儲1)盡可能少存或不存零值元素；解決問題的原則:2)盡可能稀疏矩陣的壓縮存儲方法:1、三元組順序表2、十字鏈表4.8稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲方法:1、三元組順序表2、十字鏈表4.8011404-511-720362328rowcolumnvalue355datarowscolsnumsM=M4.8.1稀疏矩陣的三元組表存儲—定義011404-511-7203

classTripleNode{}三元組順序表存儲結(jié)構(gòu)描述：4.8.1稀疏矩陣的三元組表存儲—定義privateintrow;//行號

privateintcolumn;//列號

privateintvalue;//元素值……三元組表中的結(jié)點類（見教材P136）classTripleNode{三元組順序表存儲publicclass

SparseMatrix

{}三元組順序表存儲結(jié)構(gòu)描述：4.8.1稀疏矩陣的三元組表存儲—定義

privateTripleNodedata[];//三元組表

privateintrows;//行數(shù)

privateintcols;//列數(shù)

privateintnums;//非零元素個數(shù)……稀疏矩陣三元組順序表類（見教材P137）publicclassSparseMatrix{4.8.1稀疏矩陣的三元組表存儲—基本操作1.初始化三元組順序表操作

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

按行序優(yōu)先的原則依次掃描已知稀疏矩陣的所有元素，并把非零元素插入到三元組順序表中。2）操作方法：

根據(jù)已知的一個稀疏矩陣mat（二維數(shù)組），構(gòu)造一個與其對應的三元組順序表。4.8.1稀疏矩陣的三元組表存儲—基本操作1.初始化三a.統(tǒng)計出稀疏矩陣mat中非零元素的個數(shù)(只要按行優(yōu)先的順序?qū)at掃描一遍即可完成）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;//行數(shù)cols=mat[0].length;//列數(shù)nums=count;//非零元素的個數(shù)1.初始化三元組順序表操作

（P138/算法4.9)a.統(tǒng)計出稀疏矩陣mat中非零元素的個數(shù)3）算法步驟：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)3）算法步驟：d.將mat中的非零元素依次存放到三4）算法：(P138/算法4.9)

publicSparseMatrix

(intmat[][])

{

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

//統(tǒng)計非零元素的個數(shù)

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

}

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

count++;rows=mat.length;//行數(shù)cols=mat[0].length;//列數(shù)nums=count;//非零元素的個數(shù)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++;}4）算法：(P138/算法4.9)publicSpM矩陣T矩陣2.矩陣的轉(zhuǎn)置操作

（P139/算法4.10)如何求轉(zhuǎn)置矩陣？4.8.1稀疏矩陣的三元組表存儲—基本操作M矩陣T矩陣2.矩陣的轉(zhuǎn)置操作（P139/算法4.10用常規(guī)的二維數(shù)組表示時的算法

其時間復雜度為:O(rows×cols)for(col=0;col=<rows;++col)

for(row=0;row<cols;++row)T[row][col]=M[col][row];2.矩陣的轉(zhuǎn)置操作（P139/算法4.10)用常規(guī)的二維數(shù)組表示時的算法其時間復雜度為:O(ro用“三元組”表示時如何實現(xiàn)？方法一：(算法4.10)思想：按this.data的列序進行