0-1開課

數據結構與算法DATASTRUCTURE&ALGORITHM天津理工大學計算機科學與工程學院第四章字符串與數組1字符串2多維數組的定義、存儲及操作3特殊矩陣的壓縮存儲4稀疏矩陣的壓縮存儲5應用舉例4.1字符串將元素類型限制為字符線性表（表）：具有相同類型的數據元素的有限序列（a1,

a2,…,ai,…,an）串名定界符S="

s1

s2……sn"字符串（串）：零個或多個字符組成的有限序列串的基本概念串長：串中所包含的字符個數空串：長度為0的串子串：串中任意個連續的字符組成的子序列主串：包含子串的串子串的位置：子串的第一個字符在主串中的序號S1="ab12cd"S2="ab12"S3="ab12"S4="ab13"S5=""S6="

"串的抽象數據類型定義ADTStringDataModel

串中的數據元素僅由一個字符組成，相鄰元素具有前驅和后繼關系Operation

StrAssign：串賦值

StrLength

：求串S的長度

Strcat

：串連接

StrSub

：求子串

StrCmp

：串比較

StrIndex

：子串定位

StrInsert：串插入

StrDelete

：串刪除endADT通常以串整體作為操作對象程序語言大都實現了串的基本操作字符串的基本操作有什么特點？？串的存儲方案1：用一個變量來表示串的實際長度

方案2：在串尾存儲一個不會在串中出現的特殊字符作為串的終結符，表示串的結尾

方案3：用數組的0號單元存放串的長度，從1號單元開始存放串值

abcdefg\0空閑

abcdefg9空閑如何表示串的長度？串的模式匹配模式匹配：在主串S中尋找子串T

的過程，T也稱為模式S="s1s2…sn"

T="t1t2…tm"如果匹配成功，返回T

在S

中的位置；否則返回0（2）

算法改進所取得的積累效益：模式匹配操作經常被調用，執行頻率高（1）算法的一次執行時間：問題規模通常很大，常常在大量信息中進行匹配模式匹配問題有什么特點？BF算法——基本思想1.在串S和串T中設比較的起始下標i和j；2.循環直到S或T的所有字符均比較完2.1如果S[i]等于T[j]，繼續比較S和T的下一個字符；2.2否則，將i和j回溯，準備下一趟比較；3.如果T中所有字符均比較完，則返回匹配的起始比較下標；否則返回0；ji…ij

主串Ss1s2si

sn模式T

t1t2tjijBF算法——算法實現intMatch_BF(chars[],chart[]){//在目標串s中匹配模式串t,匹配成功返回匹配的開始位置；匹配失敗，返回0。inti,j;i=0;j=0;//設置比較的起始下標while((s[i]!='\0')&&(t[j]!='\0')) {if(s[i]==t[j])//當前字符匹配成功，繼續匹配下一個字符 {i++;j++;}else//當前字符匹配失敗，回溯 {i=i-j+1;//主串s從下一個字符開始匹配j=0;//模式串t從頭開始匹配}}if(t[j]=='\0')returni-j+1;//匹配成功返回匹配成功的起始位置（不是下標）elsereturn0;//匹配失敗，返回0}BF算法——性能分析設匹配成功發生在si處，則：在匹配成功的情況下，考慮兩種極端情況：最好情況：不成功的匹配都發生在串T

的第1個字符設匹配成功發生在si處，則：最壞情況：不成功的匹配都發生在串T

的最后一個字符改進著眼點ji…ij

主串Ss1s2si

sn模式T

t1t2tj在每趟匹配不成功時存在大量回溯，沒有利用已經部分匹配的結果為什么BF算法的性能較低？改進著眼點i…

主串Ss1s2si

sn模式T

t1t2tj如何在匹配不成功時主串不回溯？如何確定模式的滑動距離？主串不回溯，模式就需要向右滑動一段距離KMP算法ababcab…abcac

ija

bcac

ababcab…ik下一趟（1）T[0]~T[k-1]=S[i-k]~S[i-1]（2）T[j-k]~T[j-1]=S[i-k]~S[i-1]T[0]~T[k-1]=T[j-k]~T[j-1]如何由當前部分匹配結果確定模式向右滑動的新比較起點k？KMP算法max{k|1≤k＜j

且T[0]…T[k-1]=T[j-k]…T[j-1]}abababacijababacabababacijababacabababacababacijk=1:k=3:模式應該向右滑多遠才能保證算法的正確性?4.2多維數組數組：由一組類型相同的數據元素構成的有序集合，每個數據元素稱為一個數組元素（簡稱為元素），每個元素受n(n≥1)個線性關系的約束，每個元素在n個線性關系中的序號i1、i2、…、in稱為該元素的下標，并稱該數組為n維數組

a11…a1n

…………

am1…amnA=a21

a22…a2na12am2數組的特點

a11…a1n

…………

am1…amnA=a21

a22…a2na12am2（1）元素本身可以具有某種結構，屬于同一數據類型；

A=(A1，A2，…，An)其中：Aj=(a1j，a2i，…，amj)(1≤j≤n)

A=(A1，A2，…，Am)其中：Ai=(ai1，ai2，…，ain)(1≤i≤m)二維數組是數據元素為線性表的線性表數組有什么特點呢？（1）元素本身可以具有某種結構，屬于同一數據類型；（2）數組中的數據元素數目固定；

a11…a1n

…………

am1…amnA=a21

a22…a2na12am2在數組上一般不能執行插入或刪除某個數組元素的操作數組的特點數組有什么特點呢？（1）元素本身可以具有某種結構，屬于同一數據類型；（2）數組中的數據元素數目固定；(3)數組中的每個數據元素都有一組唯一的下標;x

a11…a1n

…………

am1…amnA=a21

a22…a2na12am2數組的特點數組有什么特點呢？

a11…a1n

…………

am1…amnA=a21

a22…a2na12am2數組是一種隨機存儲結構。可隨機存取數組中的任意數據元素。（1）存取：給定一組下標，讀出對應的數組元素（2）修改：給定一組下標，存儲或修改與其相對應的數組元素尋址數組的特點數組有什么基本操作？數組的存儲結構數組沒有插入和刪除操作，所以，不用預留空間，適合采用順序存儲二維數組內存二維結構一維結構按行優先：先存儲行號較小的元素，行號相同者先存儲列號較小的元素按列優先：先存儲列號較小的元素，列號相同者先存儲行號較小的元素如何存儲（多維）數組？數組的存儲結構按行優先：先存儲行號較小的元素，行號相同者先存儲列號較小的元素l2h2

l1h1aij第l1行第l1+1行如何得到元素aij的存儲地址？

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*d

按行序為主序存放amn

……..

am2

am1

……….a2n

……..

a22a21a1n

…….a12

a1101n-1m*n-1n21l2h2

l1h1aijaij前面的元素個數=整行數×每行元素個數+本行中aij前面的元素個數=(i

-l1)×(h2

-l2＋1)＋(j

-l2)Loc(aij)Loc(al1l2)(i

-l1)×(h2

-l2+1)＋(j

-l2)個元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按列優先此類似，請自行給出

按列序為主序存放01m-1m*n-1mamn

……..

a2n

a1n

……….am2

……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..

amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*d數組的存儲結構推廣到n維數組將其中的每一個元素映射到一維數組的某一個位置，各維元素個數為m1,m2,m3,…,mn，下標為

i1,i2,i3,…,in

的數組元素的存儲地址：數組的存儲結構4.3特殊矩陣的壓縮存儲

特殊矩陣：矩陣中很多值相同的元素并且它們的分布有一定的規律為值相同的元素分配一個存儲空間保證隨機存取，即在O(1)時間內尋址什么是特殊矩陣？特殊矩陣如何壓縮存儲？特殊矩陣壓縮存儲后有什么要求？對稱矩陣3647862842481697460582957A＝對稱矩陣特點：aij=aji只存儲下三角部分的元素如何壓縮存儲對稱矩陣？前i-1行共有元素個數：

1+2+…+i-1=

i×(i-1)/2第i行aij前元素個數：j-1∴aij在一維數組中的下標k=i×(i-1)/2+j-1

1…

i

n1…j…n

aij第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2-1對稱矩陣第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2-1對于下三角中的元素aij（i≥j）：k＝i×(i-1)/2＋j-1對稱矩陣壓縮存儲后的尋址方法對于上三角中的元素aij（i＜j），因為aij＝aji，則

k＝j×(j-1)/2＋i

-1對稱矩陣三角矩陣3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣相同的常數只存儲一個下（上）三角部分的元素如何壓縮存儲三角矩陣？下三角矩陣的壓縮存儲第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2c對于下三角中的元素aij（i≥j）：k＝i×(i

-1)/2+j-1對于上三角中的元素aij（i＜j）：k＝n×(n+1)/2下三角矩陣壓縮存儲后的尋址方法三角矩陣上三角矩陣的壓縮存儲

下三角矩陣壓縮存儲后的尋址方法第2行第n行第1行第n-1行

a11

a12

…

a1n

a22

…

aij…

an-1,n-1

an-1,nannc

a2n01n-1

n

kn(n+1)/2…常數項對于下三角中的元素aij（i>j）：k＝n×(n+1)/2三角矩陣對角矩陣對角矩陣：所有非零元素都集中在以主對角線為中心的帶狀區域中，所有其他元素都為零

a11a12000a21a22

a23000a32

a33

a34000

a43

a44

a45000a54

a55A=只存儲非零元素如何壓縮存儲對角矩陣？

元素aij在一維數組中的序號=2+3(i-2)+(j-i+2）=2i+j-2∵一維數組下標從0開始∴元素aij在一維數組中的下標=

2i+j-3a11a12000a21a22

a23000a32a33

a34000

a43a44

a45

000a54a55A=

a11a12a21a22a23a32a33a34a43a44a45a54a550123456789101112第1行第2行第3行對角矩陣4.4稀疏矩陣的壓縮存儲

稀疏矩陣：矩陣中有很多零元素，并且分布沒有規律只存儲非零元素，零元素不分配存儲空間300700

10200000000008A=

三元組：（行號，列號，非零元素值）什么是稀疏矩陣？稀疏矩陣如何壓縮存儲？如何只存儲非零元素？稀疏矩陣300700

10200000000008A=三元組表：將稀疏矩陣的非零元素對應的三元組所構成的集合，按行優先的順序排列成一個線性表((1,1,3),(1,4,7),(2,3,1),(3,1,2),(5,4,8))typedefintDataType;typedefstruct{introw,col;

DataTypeitem;}Element;

三元組：（行號，列號，非零元素值）如何存儲三元組表？三元組順序表

三元組順序表：采用順序存儲結構存儲三元組表300700

10200000000008A=稀疏矩陣的修改操作三元組表的插入/刪除操作((1,1,3),(1,4,7),(2,3,1),(3,1,2),(5,4,8))三元組順序表需要預留存儲單元嗎？三元組順序表3007000

100200000000000080

113147231312548

空空空閑閑閑rowcolitem01234MaxTerm-1

5（非零元個數）300700

10200000000008是否對應惟一的稀疏矩陣？#defineMaxTerm100typedefstruct{Elementdata[MaxTerm];intmu,nu,tu;}SPMatrix;

113147231312548

空空空閑閑閑rowcolitem01234MaxTerm-15（非零元個數）5（矩陣的行數）6（矩陣的列數）三元組順序表是否對應惟一的稀疏矩陣？矩陣轉置運算以矩陣的轉置為例說明這種壓縮存儲結構是如何實現矩陣運算的121213931-3361443245218611564-7ijaij01234567

67813-3161521122518319342446-7631401234567ijaij

768?1）矩陣行、列值互換，即三元組中每個i,j互換2)重新安排轉置矩陣元素的位置，使轉置矩陣中元素以B的行(A的列)為主序13-316152112251801234567rowcolitem

76812213931-3361443245218611564-7rowcolitem01234567

678pk319342446-76314設矩陣三元組表總共有tu項，其時間代價為O(mu*tu)

當非0元素個數-->mu*nu時，接近O(tu*nu2)矩陣轉置運算思路：1）為找到A中每一列所有非零元素，需對其三元組表從第一行起掃描一遍。矩陣A有幾列，對矩陣三元組表掃描幾次。2)第k次掃描A.data[]找尋所有列號為k的項，將其行號變列號、列號變行號，順次存于轉置矩陣三元組表B.data[]。由于A.data[]中以A行序為主序,所以由此得到的恰是B.data[]中應有的順序方法：按A的列序轉置思路：按A.data[]中三元組次序轉置，轉置結果放入B.data[]中恰當位置。此法關鍵是要預先確定A中每一列第一個非零元在B.data[]中位置，為確定這些位置，轉置前應先求得A的每一列中非零元個數。增設輔助數組num

和cpotnum[i]:表示矩陣A第i列中非0元素的個數cpot[i]:表示第i列第一個非0元素在B中位cpot[1]=0cpot[i]=cpot[i-1]+num[i-1]2<=i<=A.nu矩陣轉置運算改進算法：inum[i]cpot[i]1022223424615706717803518642121213931-3