【源版】南京郵電大學數(shù)據(jù)結(jié)構(gòu)A第4章

數(shù)據(jù)結(jié)構(gòu)A·第4章數(shù)組與字符串第4章數(shù)組和字符串內(nèi)容提要

1、介紹數(shù)組的概念

2、討論數(shù)組抽象數(shù)據(jù)類型

3、討論特殊矩陣的存儲方法

4、討論稀疏矩陣的順序存儲方法

5、討論稀疏矩陣轉(zhuǎn)置算法

6、討論字符串抽象數(shù)據(jù)類型

7、討論字符串的存儲方法

8、討論字符串的模式匹配算法4.1數(shù)組4.1.1數(shù)組抽象數(shù)據(jù)類型

1.數(shù)組的定義課堂提要第4章數(shù)組和字符串4.1數(shù)組

4.1.1數(shù)組抽象數(shù)據(jù)類型

4.1.2數(shù)組的順序表示

4.1.3一維數(shù)組的C++類4.2特殊矩陣4.3稀疏矩陣4.4字符串

數(shù)組是下標index和值value組成的偶對的集合。每個偶對形如：(index,value)在數(shù)組中，每個有定義的下標都與一個值對應(yīng)，這個值稱做數(shù)組元素。一維數(shù)組：A={(0,15),(1,24),(2,33),(3,21)}

4.1數(shù)組4.1.1數(shù)組抽象數(shù)據(jù)類型2.數(shù)組的抽象數(shù)據(jù)類型ADT4.1數(shù)組抽象數(shù)據(jù)類型ADTArray{

數(shù)據(jù):

下標index和元素值value組成的數(shù)據(jù)對集合，其中任意兩個數(shù)據(jù)對的下標index各不相同。運算:Create():建立一個數(shù)組。

Retrieve(i):返回下標為i的元素值。

Store(i,x):將下標為i的數(shù)據(jù)元素的值置為x。};4.1數(shù)組4.1.2數(shù)組的順序表示課堂提要第4章數(shù)組和字符串4.1數(shù)組

4.1.1數(shù)組抽象數(shù)據(jù)類型

4.1.2數(shù)組的順序表示

4.1.3一維數(shù)組的C++類4.2特殊矩陣4.3稀疏矩陣4.4字符串數(shù)組通常采用順序表示：1.一維數(shù)組的順序表示2.二維數(shù)組的順序表示3.多維數(shù)組的順序表示4.1數(shù)組4.1.2數(shù)組的順序表示設(shè)第一個數(shù)組元素a[0]的地址是loc(a[0])，若已知每個元素占k個存儲單元，則a[i]的地址loc(a[i])為

loc(a[i])=loc(a[0])+i*k(i=0,1,2,…,n-1)。1.一維數(shù)組的順序表示

二維數(shù)組a[m][n]映射到一維的存儲空間時有兩種順序：

行優(yōu)先和列優(yōu)先。多數(shù)語言如PASCAL、BASIC、C、C++等都是按行優(yōu)先順序存儲的，F(xiàn)ORTRAN是按列優(yōu)先順序存儲的。2.二維數(shù)組的順序表示4.1數(shù)組4.1.2數(shù)組的順序表示行優(yōu)先順序的地址計算：若已知每個元素占k個存儲單元，第一個數(shù)組元素a[0][0]的地址是loc(a[0][0]),則數(shù)組元素a[i][j]的地址loc(a[i][j])為loc(a[i][j])=loc(a[0][0])+(i*n+j)*k(0

i<m;0

j<n)

a[0][0]a[0][1]…a[0][n-1]a[1][0]a[1][1]…a[1][n-1]…a[m-1][0]a[m-1][1]…a[m-1][n-1]

下標為0的行下標為1的行…

下標為m-1的行

(a)行優(yōu)先的順序表示4.1數(shù)組4.1.2數(shù)組的順序表示a[0][0]a[1][0]…a[m-1][0]a[0][1]a[1][1]…a[m-1][1]…a[0][n-1]a[1][n-1]…a[m-1][n-1]

下標為0的列下標為1的列…

下標為n-1的列

(a)列優(yōu)先的順序表示列優(yōu)先順序存儲：loc(a[i][j])=loc(a[0][0])+(j*m+i)*k(0

i<m;0

j<n)4.1數(shù)組4.1.2數(shù)組的順序表示行優(yōu)先：loc(a[i][j])=loc(a[0][0])+(i×n+j)×k列優(yōu)先：loc(a[i][j])=loc(a[0][0])+(j×m+i)×k4.1數(shù)組4.1.2數(shù)組的順序表示

3.多維數(shù)組的順序表示課堂提要第4章數(shù)組和字符串4.1數(shù)組

4.1.1數(shù)組抽象數(shù)據(jù)類型

4.1.2數(shù)組的順序表示

4.1.3一維數(shù)組的C++類4.2特殊矩陣4.3稀疏矩陣4.4字符串推廣到多維數(shù)組a[m1][m2]…[mn]，數(shù)組元素a[i1][i2]…[in]的存儲地址為：loc(a[i1][i2]…[in])=loc(a[0]…[0])+(i1*m2*m3*…*mn

+i2*m3*m4*…*mn+…+in-1*mn

+in

)*k=(0

ij<mj,1

j

n)4.1數(shù)組4.1.2數(shù)組的順序表示

3.多維數(shù)組的順序表示10×10的整型數(shù)組A，其每個數(shù)組元素占2個字節(jié)，已知A[0][0]在內(nèi)存中的地址是100，按列主序，A[4][6]的地址是

。A．228B．192C．124D．138如果列優(yōu)先228，如果行優(yōu)先是1924.1數(shù)組4.1.3一維數(shù)組的C++類程序4.1一維數(shù)組的C++類#include<assert.h>template<classT>classArray1D{public: Array1D(intsz=0);//缺省時長度為0 ~Array1D(){delete[]elements;} T&operator[](inti)const;//取元素值

Array1D<T>&operator=(constArray1D<T>&r);//整體賦值

friendistream&operator>>(istream&in, Array1D<T>&r); friendostream&operator<<(ostream&out, constArray1D<T>&r);private: intsize; T*elements;};4.1數(shù)組4.1.3一維數(shù)組的C++類

1.構(gòu)造函數(shù)template<classT>Array1D<T>::Array1D(intsz){//創(chuàng)建動態(tài)一維數(shù)組

assert(sz>=0);//越界檢查

size=sz;elements=newT[sz];}

在函數(shù)的實現(xiàn)中使用了一種斷言函數(shù)assert，若斷言語句的條件滿足，則繼續(xù)執(zhí)行后面的語句；否則出錯處理，程序終止。4.1數(shù)組4.1.3一維數(shù)組的C++類

1.構(gòu)造函數(shù)size=3elements=0x0012FF7C012112333Array<int>A(3);A的結(jié)構(gòu)如圖所示。4.1數(shù)組4.1.3一維數(shù)組的C++類

2.重載下標操作符template<classT>T&Array1D<T>::operator[](inti)const{assert(i>=0&&i<size);//越界檢查

returnelements[i];}（1）函數(shù)返回引用的作用：A[i]可以作為賦值運算的任一邊（2）[]，＝只能作為類的成員函數(shù)重載。4.1數(shù)組4.1.3一維數(shù)組的C++類

3.重載賦值操作符template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&r){if(this!=&r)//防止自我賦值

{ size=r.size;delete[]elements;//釋放原空間

elements=newT[size]; //重新分配空間

for(inti=0;i<size;i++)elements[i]=r.elements[i];//復制元素

}return*this;}4.1數(shù)組4.1.3一維數(shù)組的C++類

4.重載輸入操作符template<classT>istream&operator>>(istream&in,Array1D<T>&r){cout<<"Intputarray\n";for(inti=0;i<r.size;i++)in>>r.elements[i];returnin;}

5.重載輸出操作符template<classT>ostream&operator<<(ostream&out,constArray1D<T>&r){cout<<"Array=";for(inti=0;i<r.size;i++)out<<r.elements[i]<<'';out<<endl;returnout;}4.1數(shù)組4.1.3一維數(shù)組的C++類程序4.2應(yīng)用一維數(shù)組類的主程序#include"array1d.h"voidmain(){Array1D<int>a(5),b(8);Array1D<int>c;//采用缺省長度0cin>>a;cout<<"a"<<a;cin>>b;cout<<"b"<<b;cout<<"c"<<c;cout<<"a[0]="<<a[0]<<";"<<"b[5]="<<b[5]<<endl;c=b;cout<<"c=b,c"<<c;b=a;cout<<"b=a,b"<<b;}4.2特殊矩陣4.2.1對稱矩陣1.對稱矩陣在n×n的矩陣A中，若aij=aji(1≤i,j≤n)，則為n階對稱矩陣。課堂提要第4章數(shù)組和字符串4.1數(shù)組

4.1.1數(shù)組抽象數(shù)據(jù)類型

4.1.2數(shù)組的順序表示

4.1.3一維數(shù)組的C++類4.2特殊矩陣4.3稀疏矩陣4.4字符串

對于對稱矩陣，可以只存儲上三角(或下三角)中的元素(包括對角線上的元素)：n2個元素的對稱矩陣，只需要n(n+1)/2個元素的存儲空間4.2特殊矩陣4.2.1對稱矩陣1.對稱矩陣

若用一維數(shù)組b[num]以行優(yōu)先順序存儲下三角(包括對角線)元素，則矩陣元素aij的下標（i,j）和該元素在數(shù)組b中的存儲位置k之間有如下關(guān)系：a00a10a11a20…aij…an-1n-10123...k...num-1對稱矩陣的存儲表示4.2特殊矩陣4.2.1對稱矩陣2.上（下）三角矩陣

主對角以下元素全為0的方陣稱為上三角矩陣。主對角以上元素全為0的方陣稱為下三角矩陣。上、下三角矩陣也可以采用對稱矩陣的存儲方式:只存儲非0的上（或以下）三角中的元素。課堂提要第4章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣

4.2.1對稱矩陣4.3稀疏矩陣4.4字符串4.3稀疏矩陣定義：大多數(shù)元素為零的矩陣稱為稀疏矩陣。為了節(jié)省空間，對于稀疏矩陣可只存非零元素。課堂提要第4章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣4.3稀疏矩陣

4.3.1抽象數(shù)據(jù)類型

4.3.2稀疏矩陣順序表示

4.3.3稀疏矩陣轉(zhuǎn)置4.4字符串4.3稀疏矩陣4.3.1稀疏矩陣抽象數(shù)據(jù)類型1.稀疏矩陣的操作在稀疏矩陣上執(zhí)行的操作本質(zhì)上與普通矩陣完全相同.標量加法、乘法；矩陣加法、乘法；轉(zhuǎn)置、求逆；…4.3稀疏矩陣4.3.1稀疏矩陣抽象數(shù)據(jù)類型2稀疏矩陣抽象數(shù)據(jù)類型ADT4.2稀疏矩陣抽象數(shù)據(jù)類型ADTSparseMatrix{

數(shù)據(jù):

絕大多數(shù)元素為零的矩陣。運算:Create();建立一個稀疏矩陣。

Destroy()；撤消一個稀疏矩陣。

Add(B,C)：當前矩陣對象與B相加，C中返回相加和。

Multiply(B,C):當前矩陣對象與B相乘，C中返回相乘積。

Transpose(B):B中返回當前矩陣對象的轉(zhuǎn)置矩陣。}

4.3稀疏矩陣4.3.1稀疏矩陣抽象數(shù)據(jù)類型3稀疏矩陣的C++類程序4.3template<classT>classSparseMatrix{public:SparseMatrix(intmaxRowSize,intmaxColSize){};~SparseMatrix(){};virtualvoidAdd(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;virtualvoidMul(constSparseMatrix<T>&B,SparseMatrix<T>&C)const;virtualvoidTranspose(SparseMatrix<T>&B)const;private:intmaxRows,maxCols;};4.3稀疏矩陣4.3.2稀疏矩陣的順序表示1.三元組表示法按照壓縮存儲的思想，稀疏矩陣Am×n中的每一個非零元素aij的行號i、列號j和值v表示為一個三元組，即：課堂提要第4章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣4.3稀疏矩陣

4.3.1抽象數(shù)據(jù)類型

4.3.2稀疏矩陣順序表示

4.3.3稀疏矩陣轉(zhuǎn)置4.4字符串三元組的存儲：按行順序存儲按列順序存儲(i,j,v)4.3稀疏矩陣4.3.2稀疏矩陣的順序表示2.三元組按行順序存儲圖4-3稀疏矩陣及其三元組表示4.3稀疏矩陣4.3.2稀疏矩陣的順序表示2.三元組按行順序存儲(a)稀疏矩陣M(b)M的行三元組(c)M的列三元組4.3稀疏矩陣4.3.2稀疏矩陣的順序表示3.三元組的存儲結(jié)構(gòu)程序4.4Term類template<classT>classTerms{

introw;

intcol;

Tvalue;};4.3稀疏矩陣4.3.2稀疏矩陣的順序表示4.行三元組表示的稀疏矩陣的C++類程序4.3:template<classT>classSeqTriple{public:

SeqTriple(intmaxLengthSize);voidAdd(constSeqTriple<T>&B,SeqTriple<T>&

C)const;voidMul(constSeqTriple<T>&B,SeqTriple<T>&

C)const;SeqTriple<T>Transpose(SeqTriple<T>&B)const;friendistream&operator>>(istream&input,SeqTriple<T>&);friendostream&operator<<(istream&output,constSeqTriple<T>&);private:intmaxSize;//最大個數(shù)

intm,n,

t;//行數(shù)，列數(shù)，非零元素個數(shù)

Terms<T>*trip;//動態(tài)一維數(shù)組的指針};4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置1.矩陣轉(zhuǎn)置4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置2.普通矩陣轉(zhuǎn)置一般矩陣轉(zhuǎn)置的程序：for(inti=0;i<m;i++)

for(intj=0;j<n;j++)

B[j][i]=A[i][j];即將矩陣中的元素A[i][j]賦值給轉(zhuǎn)置矩陣中的元素B[j][i]。時間復雜度為O(m×n)。課堂提要第4章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣4.3稀疏矩陣

4.3.1抽象數(shù)據(jù)類型

4.3.2稀疏矩陣順序表示

4.3.3稀疏矩陣轉(zhuǎn)置4.4字符串4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置如果稀疏矩陣Am×n用行三元組M表示，轉(zhuǎn)置矩陣保存在一維數(shù)組T中，則T應(yīng)仍為行三元組。課堂提要第4章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣4.3稀疏矩陣

4.3.1抽象數(shù)據(jù)類型

4.3.2稀疏矩陣順序表示

4.3.3稀疏矩陣轉(zhuǎn)置4.4字符串4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置三元組表示三元組表示轉(zhuǎn)置轉(zhuǎn)置HOW4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置方法一:將數(shù)組M中的元素的行、列號交換后保存到T數(shù)組中；然后按T中的行號排序。顯然，矩陣轉(zhuǎn)置的時間取決于排序的時間。步驟1：交換行、列號步驟2：按行號排序4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置方法二：對數(shù)組M(矩陣Am

n的三元組）掃描n遍，每遍掃描t次。第i遍掃描，找到M中列號為i的元素（即A中第i列中的非0元素），將該元素轉(zhuǎn)置后依次放入T中。2615213111230220123456701234567rowcolvaluek=0

50-16

32-800160491k=2rowcolvalue0016032205-16111212323-840916215k=3k=5k=7轉(zhuǎn)置后的矩陣4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置方法二：對數(shù)組M(矩陣Am

n的三元組）掃描n遍，每遍掃描t次。第i遍掃描，找到M中列號為i的元素（即A中第i列中的非0元素），將這些元素轉(zhuǎn)置后依次放入T中。k=0;for(i=0;i<n;i++)

for(j=0;j<t;j++)

if(M[j].col==i){

T[k].col=M[j].row;

T[k].row=M[j].col;

T[k++].value=M[j].value;

}時間復雜度為O(n*t)t是T的長度。4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置

分析:方法二需要反復掃描M，效率不高?？紤]：若掃描三元組M的任何元素時，都能夠知道其在轉(zhuǎn)置后的T中的位置，就可以不對M進行反復掃描！方法三:快速轉(zhuǎn)置算法

通過增加適量的存儲空間，達到節(jié)省時間的目的。使用n個指針k[n](n是矩陣的列數(shù))，指向A中每一列的第一個非零元素在T中的存放位置。26152131112302201234567

50-16

32-800160491rowcolvalue0016032205-16111212323-840916215392615213111230220123456701234567rowcolvalue

50-16

32-800160491rowcolvalue0016032205-16111212323-840916215k[0]=0k[3]=5k[5]=7k[1]=2k[2]=3k[3]=6k[0]=1k[4]=5k[3]=5k[5]=7k[1]=2k[2]=3k[4]=5k[0]=040k[2]=42615213111230220123456701234567rowcolvalue

50-16

32-800160491k[0]=0k[3]=5k[5]=7k[1]=2k[2]=3k[3]=6k[0]=1k[2]=3k[4]=5k[3]=5k[1]=2k[4]=5k[0]=0rowcolvalue

0016032205-16111212323-840916215k[5]=741k[2]=42615213111230220123456701234567rowcolvalue

50-16

32-800160491k[0]=0k[3]=5k[5]=7k[1]=2k[2]=3k[3]=6k[0]=1k[4]=5k[3]=5k[5]=7k[1]=2k[4]=5k[0]=0rowcolvalue

0016032205-16

111212323-840916215k[2]=4k[3]=6k[0]=14.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置方法三:快速轉(zhuǎn)置算法計算k[i]：k[0]=0，先考慮計算每一列中非零元素的個數(shù)num[i],得到如下計算公式：k[0]=0k[i]=k[i-1]+num[i-1](1≤i≤n)col012345num[col]212201k[col]023577表4-1num數(shù)組和k數(shù)組4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置方法三:快速轉(zhuǎn)置算法rowcolvalue0016032205-16111212323-84091621501234567num[0]++->1num[3]++->1num[5]++->1num[1]++->1num[2]++->1num[3]++->2num[0]++->2num[2]++->2col012345num[col]212201k[col]023577表4-1num數(shù)組和k數(shù)組計算num[]：(1)初始值為0；(2)順序掃描三元組，

執(zhí)行num[col]++4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置方法三:快速轉(zhuǎn)置算法(a)稀疏矩陣M4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置方法三:快速轉(zhuǎn)置算法(程序4.6)

template<classT>voidSeqTriple<T>::Transpose(SeqTriple<T>&B)const{int*num=newint[n];int*k=newint[n];B.m=n;B.n=m;B.t=t;if(t>0){for(inti=0;i<n;i++)num[i]=0;//初始化num[]for(i=0;i<t;i++)num[trip[i].col]++;//計算num[]k[0]=0;for(i=1;i<n;i++)k[i]=k[i-1]+num[i-1];//計算k[]基本步驟：

(1)計算num[](2)計算k[](3)快速轉(zhuǎn)置4.3稀疏矩陣4.3.3稀疏矩陣轉(zhuǎn)置3.三元組實現(xiàn)矩陣轉(zhuǎn)置方法三:快速轉(zhuǎn)置算法

for(i=0;i<t;i++){intj=k[trip[i].col]++;//掃描this對象的第i項在B中的位置jB.trip[j].row=trip[i].col;B.trip[j].col=trip[i].row;B.trip[j].value=trip[i].value;

//this對象第i項轉(zhuǎn)置后放入B的位置j}}

delete[]num;delete[]k;}O(n+t)4.4字符串4.4.1字符串抽象數(shù)據(jù)類型

字符串的定義字符串(簡稱為串)是由n(n≥

0)個字符組成的有限序列。S=“a0a1…an－1”

(n≥0)課堂提要第4章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣4.3稀疏矩陣4.4字符串

4.4.1字符串抽象數(shù)據(jù)類型

4.4.2字符串的存儲表示

4.4.3簡單模式匹配算法

4.4.4模式匹配的KMP算法例如：“Helloworld!”該串的長度n=124.4字符串4.4.1字符串抽象數(shù)據(jù)類型

串S中任意連續(xù)個字符組成的子序列P稱為該串的子串，S則稱為主串。

子串在主串中的位置一般記為子串的首字符在主串中的位置。主串：S=‘a(chǎn)bcabcaabcbcde’子串：P=‘a(chǎn)bc’P在S中出現(xiàn)的位置：0，3，74.4字符串4.4.1字符串抽象數(shù)據(jù)類型

ADT4.3字符串ADT{數(shù)據(jù):由n(≥0)個字符組成的有限序列S="a0a1…an-1"，0≤i<n。運算:

Create():建立空串Destroy():撤消串Length():返回當前串對象的長度Clear():清空當前串對象4.4字符串4.4.1字符串抽象數(shù)據(jù)類型

Assign(S):串賦值，將S賦值給當前串對象

Concat(S):串連接，將S串連接在當前串對象的尾部

Insert(P,i):子串插入，將P插入當前串對象的i位置

Delete(i,len):子串刪除，在當前串對象中，刪除自i開始的

len個字符。

Substr(i,len):返回子串，返回當前串對象中，從位置i

開始的len個字符組成的子串。

Find(i,P):查找子串位置，查找子串P在當前串對象中

首次出現(xiàn)的位置；若不存在，則返回-1。4.4字符串4.4.2字符串的存儲表示順序存儲表示：利用一維字符數(shù)組進行存儲。課堂提要第4章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣4.3稀疏矩陣4.4字符串

4.4.1字符串抽象數(shù)據(jù)類型

4.4.2字符串的存儲表示

4.4.3簡單模式匹配算法

4.4.4模式匹配的KMP算法例如：chars[20]=“helloworld!”；4.4字符串4.4.2字符串的存儲表示鏈接存儲表示4.4字符串4.4.2字符串的存儲表示#include<string.h>classString{public:String();String(constchar*p);~String(){delete[]str;};

intFind(inti,String&P);private:intn;//當前串長

char*str;//動態(tài)一維字符數(shù)組的指針};String::String(constchar*p){n=strlen(p);str=newchar[n+1];strcpy(str,p);}4.4字符串字符串模式匹配Tieredwirelesssensornetworkisanetworkmodelofflexibilityandrobustness,whichconsistsofthetraditionalresource-limitedsensornodesandtheresource-abundantstoragenodes.Insucharchitecture,collecteddatafromthesensornodesareperiodicallysubmittedtothenearbystoragenodesforarchivepurpose.Whenaqueryisrequested,storagenodesalsoprocessthequeryandreturnqualifieddataastheresulttothebasestation.Theroleofthestoragenodesleadstoanattackpronesituationandleavesthemmorevulnerableinahostileenvironment.Ifanyofthemiscompromised,fakedatamaybeinjectedintoand/orqualifieddatamaybediscarded.Andthebasestationwouldreceiveincorrectanswersincurringmalfunctiontoapplications.Inthispaper,…模式串：sensornetwork主串字符串模式匹配：在主串S中查找模式串P是否出現(xiàn)、出現(xiàn)次數(shù)及位置等匹配算法是研究重點4.4字符串4.4.3簡單模式匹配算法設(shè)有兩個字符串S和P，在串S中找串P的過程被稱為模式匹配。這里S為主串，P為子串，又稱為模式。4.4字符串4.4.3簡單模式匹配算法intString::Find(inti,String&P){//查找是否存在，

//若存在，返回首次出現(xiàn)位置 if(i<0||i>n-1){//越界檢查

cout<<"Outofbounds!"<<endl;return-1;}char*pp=P.str,char*t=str+i;while(*pp!='\0‘&&i<=n-P.n) if(*pp++!=*t++){

pp=P.str;//模式串回到第1個字符

t=str+(++i);//主串回到i+1的位置

}if(*pp=='\0')returni;return-1;}4.4字符串4.4.3簡單模式匹配算法

簡單匹配算法的漸近時間復雜度：設(shè)主串和模式串的長度為n和m，簡單模式匹配算法在最壞情況下的時間復雜度是O(n×m)。平均情況下的時間復雜度也是O(n×m)。高效的模式匹配算法：KMPKnuth,MorrisandPrattO(n+m)4.4字符串4.4.4模式匹配的KMP算法

改進的模式匹配算法(KMP算法)思路：

在主串和子串到達失配點時，主串S不需要回溯，而模式串P也不一定要回溯到第一個字符位置，其算法時間復雜度降為O(m+n)。關(guān)鍵是解決模式串在每個失配點最少需要向前回溯到哪個位置？

簡單模式匹配算法的缺陷：效率不高，原因在于匹配過程中有回溯。一趟匹配失敗時，即S[i+j]≠P[j]，主串回溯到i+1位置，而模式串回溯到第1個字符位置，再重新開始匹配。4.4字符串4.4.4模式匹配的KMP算法改進簡單模式匹配：例1P[1]=S[1]且P[1]≠P[0]P[0]≠S[1]②…③…④…⑤…可省略S串無需回溯4.4字符串4.4.4模式匹配的KMP算法改進簡單模式匹配：例2由例1可知②、③可省略P[0]=P[3]且P[1]=P[4]④、⑤也可省略P串有時也無需回溯4.4字符串4.4.4模式匹配的KMP算法KMP模式匹配算法思想設(shè)主串S=”s0s1s2…sn-1

”，模式串P=“p0p1p2…pm-1

”并設(shè)在S[i]≠P[j]處失配，如果模式串P中有一整數(shù)k<j，使得：p0p1p2…pk-1=pj-kpj-k+1…pj-1是串P中最長的相等的前綴子串和后綴子串。由于在S[i]≠P[j]處失配，故必有：pj-kpj-k+2…pj-1=si-k…si-2si-1

則：p0p1p2…pk-1

=si-k…si-2si-1

所以：下一趟比較可以從si和pk開始。關(guān)鍵在于計算P中每一個字符對應(yīng)的k！4.4字符串4.4.4模式匹配的KMP算法失敗函數(shù)，即計算模式串中每一個字符在發(fā)生失配時的回溯位置k。

設(shè)有長度為m的模式串p＝p0p1…pm-