1、數據結構數據結構A 第第4章章 數組與字符串第第4章章 數組和字符串數組和字符串4.1 數組數組4.1.1 數組抽象數據類型 1. 數組的定義數組的定義第第4章章 數組和字符串數組和字符串4.1 數組數組 4.1.1 數組抽象數據類型數組抽象數據類型 4.1.2 數組的順序表示數組的順序表示 4.1.3 一維數組的一維數組的C+類類4.2 特殊矩陣特殊矩陣4.3 稀疏矩陣稀疏矩陣4.4 字符串字符串& 數組是下標數組是下標index 和值和值value 組成的偶對的集合。組成的偶對的集合。&每個偶對形如：每個偶對形如： (index,value) &在數組中，每個有定義的下標都與在數組中，每個

2、有定義的下標都與一個值對應，這個值稱做數組元素。一個值對應，這個值稱做數組元素。一維數組：一維數組：A = (0,15),(1,24),(2,33),(3,21)A = (0,15),(1,24),(2,33),(3,21) 4.1 數組數組4.1.1 數組抽象數據類型 2. 數組的抽象數據類型數組的抽象數據類型ADT 4.1 數組抽象數據類型數組抽象數據類型ADT Array 數據數據: 下標下標index和元素值和元素值value組成的數據對集合，組成的數據對集合， 其中任意兩個數據對的下標其中任意兩個數據對的下標index各不相同。各不相同。 運算運算: Create(): 建立一個數組

3、。建立一個數組。 Retrieve(i): 返回下標為返回下標為i的元素值。的元素值。 Store(i,x): 將下標為將下標為i的數據元素的值置為的數據元素的值置為x。;4.1 數組數組4.1.2 數組的順序表示第第4章章 數組和字符串數組和字符串4.1 數組數組 4.1.1 數組抽象數據類型數組抽象數據類型 4.1.2 數組的順序表示數組的順序表示 4.1.3 一維數組的一維數組的C+類類4.2 特殊矩陣特殊矩陣4.3 稀疏矩陣稀疏矩陣4.4 字符串字符串數組通常采用順序表示：數組通常采用順序表示：1. 一維數組的順序表示一維數組的順序表示2. 二維數組的順序表示二維數組的順序表示3. 多

4、維數組的順序表示多維數組的順序表示4.1 數組數組4.1.2 數組的順序表示設第一個數組元素設第一個數組元素a0的地址是的地址是loc(a0)，若已知每個元素，若已知每個元素占占k個存儲單元，則個存儲單元，則ai的地址的地址loc(ai)為為 loc(ai)=loc(a0)+i*k (i=0,1,2,n-1)。1. 一維數組的順序表示一維數組的順序表示& 二維數組二維數組amn映射到一維的存儲空間時有兩種順序：映射到一維的存儲空間時有兩種順序： 行優先行優先和和列優先列優先。& 多數語言如多數語言如PASCAL、BASIC、C、C+等都是按行優等都是按行優先順序存儲的，先順序存儲的，FORTR

5、AN是按列優先順序存儲的。是按列優先順序存儲的。2. 二維數組的順序表示二維數組的順序表示4.1 數組數組4.1.2 數組的順序表示行優先順序的地址計算：行優先順序的地址計算：若已知每個元素占若已知每個元素占k個存儲單元，第一個數組元素個存儲單元，第一個數組元素a00的地址是的地址是loc(a00),則數組元素則數組元素aij的地址的地址loc(aij)為為loc(aij)=loc(a00)+(i*n+j)*k (0 im;0 jn) a00 a01a0n-1 a10 a11a1n-1 am-10 am-11am-1n-1 下標為下標為0的行的行 下標為下標為1的行的行 下標為下標為m-1的行

6、的行 (a)行優先的順序表示行優先的順序表示000101101111 101111aaanaaana ija ma ma mn4.1 數組數組4.1.2 數組的順序表示a00 a10am-10 a01 a11am-11 a0n-1 a1n-1am-1n-1 下標為下標為0的列的列 下標為下標為1的列的列 下標為下標為n-1的列的列 (a)列優先的順序表示列優先的順序表示列優先順序存儲：列優先順序存儲：loc(aij)=loc(a00)+(j*m+i)*k (0 im;0 jn)000101101111 101111aaanaaana ija ma ma mn4.1 數組數組4.1.2 數組的順

7、序表示行優先：行優先：loc(aij)=loc(a00)+(in+j)k列優先：列優先：loc(aij)=loc(a00)+(jm+i)k4.1 數組數組4.1.2 數組的順序表示 3. 多維數組的順序表示多維數組的順序表示第第4章章 數組和字符串數組和字符串4.1 數組數組 4.1.1 數組抽象數據類型數組抽象數據類型 4.1.2 數組的順序表示數組的順序表示 4.1.3 一維數組的一維數組的C+類類4.2 特殊矩陣特殊矩陣4.3 稀疏矩陣稀疏矩陣4.4 字符串字符串推廣到多維數組推廣到多維數組am1m2 mn，數組元素，數組元素ai1i2 in的的存儲地址為存儲地址為 ： loc(ai1i

8、2 in)=loc(a00) + ( i1* m2 * m3 * mn + i2* m3 * m4 * mn + + in-1* mn + in ) * k =(0 ijmj, 1 j n)111( 000)( *)*nnjknjkjLoc aaimik 4.1 數組數組4.1.2 數組的順序表示 3. 多維數組的順序表示多維數組的順序表示1010的整型數組的整型數組A，其每個數組元素占，其每個數組元素占2個字節，已知個字節，已知A00在內在內存中的地址是存中的地址是100，按列主序，按列主序，A46的地址是的地址是 。A228 B192 C124 D138如果列優先如果列優先228 ，如果行

9、優先是，如果行優先是1924.1 數組數組4.1.3 一維數組的C+類 程序程序4.1 一維數組的一維數組的C+類類#includetemplate class Array1D public:Array1D(int sz=0); /缺省時長度為缺省時長度為0 Array1D() delete elements; T& operator (int i)const; /取元素值取元素值 Array1D&operator=(const Array1D &r); /整體賦值整體賦值 friend istream &operator(istream &in, Array1D &r); friend os

10、tream &operator(ostream &out, const Array1D &r);private:int size;T *elements; ;4.1 數組數組4.1.3 一維數組的C+類 1. 構造函數構造函數template Array1D:Array1D(int sz) /創建動態一維數組創建動態一維數組 assert(sz=0); /越界檢查越界檢查 size=sz; elements=new Tsz; 在函數的實現中使用了一種斷言函數在函數的實現中使用了一種斷言函數assert，若斷言語句的條件滿足，則繼續執行后面的語句若斷言語句的條件滿足，則繼續執行后面的語句；否則出

11、錯處理，程序終止。；否則出錯處理，程序終止。4.1 數組數組4.1.3 一維數組的C+類 1. 構造函數構造函數size =3elements =0 x0012FF7C012112333Array A(3);A 的結構如圖所示。的結構如圖所示。4.1 數組數組4.1.3 一維數組的C+類 2. 重載下標操作符重載下標操作符template T& Array1D:operator(int i)const assert(i=0 & isize); /越界檢查越界檢查 return elementsi;（1）函數返回引用的作用：）函數返回引用的作用：Ai可以作為賦值運算可以作為賦值運算 的任一邊的任

12、一邊（2） ，只能作為類的成員函數重載。，只能作為類的成員函數重載。4.1 數組數組4.1.3 一維數組的C+類 3. 重載賦值操作符重載賦值操作符template Array1D& Array1D: operator=(const Array1D & r) if ( this!=&r ) /防止自我賦值防止自我賦值 size=r.size; delete elements; /釋放原空間釋放原空間 elements=new Tsize; /重新分配空間重新分配空間 for (int i=0;isize;i+) elementsi=r.elementsi; /復制元素復制元素 return *

13、this;4.1 數組數組4.1.3 一維數組的C+類 4. 重載輸入操作符重載輸入操作符template istream &operator(istream &in, Array1D &r) coutIntput arrayn; for(int i=0; ir.elementsi; return in; 5. 重載輸出操作符重載輸出操作符template ostream &operator(ostream &out, const Array1D &r) coutArray=; for(int i=0; ir.size; i+) outr.elementsi ; outendl; return

14、 out;4.1 數組數組4.1.3 一維數組的C+類 程序程序4.2 應用一維數組類的主程序應用一維數組類的主程序#include array1d.hvoid main() Array1D a(5), b(8); Array1D c; /采用缺省長度采用缺省長度0 cina; couta b; coutb b; coutc c; couta0=a0; b5=b5endl; c=b; coutc=b, c c; b=a; coutb=a, b b;4.2 特殊矩陣特殊矩陣 4.2.1 對稱矩陣1. 對稱矩陣對稱矩陣在在nn的矩陣的矩陣A中，若中，若aij=aji (1i, jn)，則為，則為n

15、階對稱矩陣。階對稱矩陣。第第4章章 數組和字符串數組和字符串4.1 數組數組 4.1.1 數組抽象數據類型數組抽象數據類型 4.1.2 數組的順序表示數組的順序表示 4.1.3 一維數組的一維數組的C+類類4.2 特殊矩陣特殊矩陣4.3 稀疏矩陣稀疏矩陣4.4 字符串字符串& 對于對稱矩陣，可以只存儲上對于對稱矩陣，可以只存儲上三角三角(或下三角或下三角)中的元素中的元素(包括對角包括對角線上的元素線上的元素)：n2個元素的對稱矩陣，只需要個元素的對稱矩陣，只需要n(n+1)/2個元素的存儲空間個元素的存儲空間4.2 特殊矩陣特殊矩陣 4.2.1 對稱矩陣1. 對稱矩陣對稱矩陣 若用一維數組若

16、用一維數組bnum以行優先順序存儲下三角以行優先順序存儲下三角(包括對角線包括對角線)元素，則矩陣元素元素，則矩陣元素aij的下標（的下標（i,j）和該元素在數組）和該元素在數組b中的存中的存儲位置儲位置k之間有如下關系：之間有如下關系：a a00 00 a a10 10 a a11 11 a a20 20 a aij ij a an-1n-1n-1n-10 1 2 3 . k . num-10 1 2 3 . k . num-1對稱矩陣的存儲表示對稱矩陣的存儲表示(1)2(1)2i ijijkj jiji0010111,01,11,1nnnnaaaaaa4.2 特殊矩陣特殊矩陣 4.2.1

17、對稱矩陣2. 上（下）三角矩陣上（下）三角矩陣 l 主對角以下元素全為主對角以下元素全為0的方陣稱的方陣稱為上三角矩陣。為上三角矩陣。l 主對角以上元素全為主對角以上元素全為0的方陣稱的方陣稱為下三角矩陣。為下三角矩陣。& 上、下三角矩陣也可以采用對上、下三角矩陣也可以采用對稱矩陣的存儲方式稱矩陣的存儲方式:只存儲非只存儲非0的的上（或以下）三角中的元素。上（或以下）三角中的元素。第第4章章 數組和字符串數組和字符串4.1 數組數組4.2 特殊矩陣特殊矩陣 4.2.1 對稱矩陣對稱矩陣4.3 稀疏矩陣稀疏矩陣4.4 字符串字符串4.3 稀疏矩陣稀疏矩陣 定義：大多數元素為零的矩陣稱為稀疏矩陣。

18、定義：大多數元素為零的矩陣稱為稀疏矩陣。& 為了節省空間，對于稀疏矩陣可只存非零元素。為了節省空間，對于稀疏矩陣可只存非零元素。第第4章章 數組和字符串數組和字符串4.1 數組數組4.2 特殊矩陣特殊矩陣4.3 稀疏矩陣稀疏矩陣 4.3.1 抽象數據類型抽象數據類型 4.3.2 稀疏矩陣順序表示稀疏矩陣順序表示 4.3.3 稀疏矩陣轉置稀疏矩陣轉置4.4 字符串字符串M稀疏矩陣稀疏矩陣 00015000000000000091000000008000000312016022001665432105432104.3 稀疏矩陣稀疏矩陣 4.3.1 稀疏矩陣抽象數據類型 1. 稀疏矩陣的操作稀疏矩陣

19、的操作在稀疏矩陣上執行的操作本質上與普通矩陣完全相同在稀疏矩陣上執行的操作本質上與普通矩陣完全相同. 標量加法、乘法；標量加法、乘法； 矩陣加法、乘法；矩陣加法、乘法； 轉置、求逆；轉置、求逆； 4.3 稀疏矩陣稀疏矩陣 4.3.1 稀疏矩陣抽象數據類型 2 稀疏矩陣抽象數據類型稀疏矩陣抽象數據類型ADT 4.2 稀疏矩陣抽象數據類型稀疏矩陣抽象數據類型ADT SparseMatrix 數據數據: 絕大多數元素為零的矩陣。絕大多數元素為零的矩陣。 運算運算: Create(); 建立一個稀疏矩陣。建立一個稀疏矩陣。 Destroy()；撤消一個稀疏矩陣。；撤消一個稀疏矩陣。 Add(B,C)：

20、當前矩陣對象與：當前矩陣對象與B相加，相加，C中返回相加和。中返回相加和。 Multiply(B,C): 當前矩陣對象與當前矩陣對象與B相乘，相乘，C中返回相乘積。中返回相乘積。 Transpose(B): B中返回當前矩陣對象的轉置矩陣。中返回當前矩陣對象的轉置矩陣。 4.3 稀疏矩陣稀疏矩陣 4.3.1 稀疏矩陣抽象數據類型 3 稀疏矩陣的稀疏矩陣的C+類類程序程序4.3 template class SparseMatrix public: SparseMatrix(int maxRowSize, int maxColSize); SparseMatrix(); virtual void

21、 Add(const SparseMatrix &B, SparseMatrix &C) const; virtual void Mul(const SparseMatrix &B, SparseMatrix &C) const; virtual void Transpose(SparseMatrix &B) const; private: int maxRows, maxCols;4.3 稀疏矩陣稀疏矩陣 4.3.2 稀疏矩陣的順序表示 1. 三元組表示法三元組表示法按照壓縮存儲的思想，稀疏矩陣按照壓縮存儲的思想，稀疏矩陣Amn中的每一個非零元素中的每一個非零元素 aij 的行號的行號i、列

22、號、列號j和值和值v表示為一個三元組，即：表示為一個三元組，即：第第4章章 數組和字符串數組和字符串4.1 數組數組4.2 特殊矩陣特殊矩陣4.3 稀疏矩陣稀疏矩陣 4.3.1 抽象數據類型抽象數據類型 4.3.2 稀疏矩陣順序表示稀疏矩陣順序表示 4.3.3 稀疏矩陣轉置稀疏矩陣轉置4.4 字符串字符串三元組的存儲：三元組的存儲：按行順序存儲按行順序存儲按列順序存儲按列順序存儲( i, j, v)4.3 稀疏矩陣稀疏矩陣 4.3.2 稀疏矩陣的順序表示 2. 三元組按行順序存儲三元組按行順序存儲圖圖4-3 稀疏矩陣及其三元組表示稀疏矩陣及其三元組表示0123450 1600220161 01

23、230002 0008003 0000004 91000005 0000006 0015000( )aM稀疏矩陣00016103222051631112412352386409176215( )rowcolvalueb M的行三元組4.3 稀疏矩陣稀疏矩陣 4.3.2 稀疏矩陣的順序表示 2. 三元組按行順序存儲三元組按行順序存儲15918312162216203215306421100076543210valcolrow16-8-22153129116533221000206114076543210valcolrow00015000000000000091000000008000000312

24、01602200166543210543210(a) 稀疏矩陣稀疏矩陣M(b) M的行三元組的行三元組(c) M的列三元組的列三元組4.3 稀疏矩陣稀疏矩陣 4.3.2 稀疏矩陣的順序表示 3. 三元組的存儲結構三元組的存儲結構程序程序4.4 Term類類template class Terms int row; int col; T value;4.3 稀疏矩陣稀疏矩陣 4.3.2 稀疏矩陣的順序表示 4. 行三元組表示的稀疏矩陣的行三元組表示的稀疏矩陣的C+類類程序程序4.3: template class SeqTriple public: SeqTriple(int maxLength

25、Size); void Add(const SeqTriple &B, SeqTriple & C) const; void Mul(const SeqTriple &B, SeqTriple & C) const; SeqTriple Transpose(SeqTriple &B) const; friend istream &operator (istream &input, SeqTriple &); friend ostream &operator (istream &output, const SeqTriple &); private: int maxSize; /最大個數最大個數

26、 int m, n , t; /行數，列數，非零元素個數行數，列數，非零元素個數 Terms * trip; /動態一維數組的指針動態一維數組的指針;4.3 稀疏矩陣稀疏矩陣 4.3.3 稀疏矩陣轉置 1. 矩陣轉置矩陣轉置0123450 1600220161 01230002 0008003 0000004 91000005 0000006 0015000M稀疏矩陣01234560 16000910010120000020300001532208000040000000516000000M轉置矩陣4.3 稀疏矩陣稀疏矩陣 4.3.3 稀疏矩陣轉置 2. 普通矩陣轉置普通矩陣轉置一般一般矩陣轉

27、置的程序：矩陣轉置的程序：for (int i=0; im; i+) for (int j=0; jn; j+) Bji=Aij;即將矩陣中的元素即將矩陣中的元素Aij賦值給賦值給轉置矩陣中的元素轉置矩陣中的元素Bji。時間復雜度為時間復雜度為O(mn)。第第4 4章章 數組和字符串數組和字符串4.1 4.1 數組數組4.2 4.2 特殊矩陣特殊矩陣4.3 4.3 稀疏矩陣稀疏矩陣 4.3.1 4.3.1 抽象數據類型抽象數據類型 4.3.2 4.3.2 稀疏矩陣順序稀疏矩陣順序 表示表示 4.3.3 4.3.3 稀疏矩陣轉置稀疏矩陣轉置4.4 字符串字符串4.3 稀疏矩陣稀疏矩陣 4.3.3

28、 稀疏矩陣轉置 3. 三元組實現矩陣轉置三元組實現矩陣轉置如果稀疏矩陣如果稀疏矩陣Amn用行三元組用行三元組M表示表示，轉置矩陣保存在一維數組轉置矩陣保存在一維數組T中中，則則T應仍為行三元組。應仍為行三元組。第第4 4章章 數組和字符串數組和字符串4.1 4.1 數組數組4.2 4.2 特殊矩陣特殊矩陣4.3 4.3 稀疏矩陣稀疏矩陣 4.3.1 4.3.1 抽象數據類型抽象數據類型 4.3.2 4.3.2 稀疏矩陣順序稀疏矩陣順序 表示表示 4.3.3 4.3.3 稀疏矩陣轉置稀疏矩陣轉置4.4 字符串字符串4.3 稀疏矩陣稀疏矩陣 4.3.3 稀疏矩陣轉置 3. 三元組實現矩陣轉置三元組

29、實現矩陣轉置0123450 1600220161 01230002 0008003 0000004 91000005 0000006 001500000016103222051631112412352386409176215rowcolvalue01234560 1600091001012000002030000153220800004000000051600000000016104912111232134261553022632875016rowcolvalue三元組表示三元組表示轉置轉置HOW4.3 稀疏矩陣稀疏矩陣 4.3.3 稀疏矩陣轉置 3. 三元組實現矩陣轉置三元組實現矩陣轉置方法

30、一方法一: : 將數組將數組 M M 中的元素的行、列號交換后保存到中的元素的行、列號交換后保存到 T T 數組中；然后按數組中；然后按 T T 中的行號排序。中的行號排序。00016103222051631112412352386409176215rowcolvalue00016130222501631112421353286049172615rowcolvalue00016104912111232134261553022632875016rowcolvalue顯然，矩陣轉置的時間取決于排序的時間。顯然，矩陣轉置的時間取決于排序的時間。步驟1：交換行、列號步驟2：按行號排序4.3 稀疏矩陣稀

31、疏矩陣 4.3.3 稀疏矩陣轉置 3. 三元組實現矩陣轉置三元組實現矩陣轉置方法二：對數組方法二：對數組 M(矩陣矩陣Am n的三元組）的三元組） 掃描掃描 n 遍，每遍遍，每遍掃描掃描t次。第次。第 i 遍掃描，找到遍掃描，找到M中列號為中列號為i的元素（即的元素（即A中第中第i列中的非列中的非0元素），將該元素轉置后依次放入元素），將該元素轉置后依次放入T中。中。2 6 152 6 152 1 32 1 31 1 121 1 123 0 223 0 220 01 12 23 34 45 56 67 70 01 12 23 34 45 56 67 7row col valuerow col

32、valuek=0k=0 5 0 -165 0 -16 3 2 -83 2 -80 0 160 0 160 4 910 4 91k=2k=2row col valuerow col value 0 0 16 0 0 16 0 3 22 0 3 22 0 5 -16 0 5 -16 1 1 12 1 1 12 1 2 3 1 2 3 2 3 -8 2 3 -8 4 0 91 4 0 91 6 2 15 6 2 15k=3k=3k=5k=5k=7k=7轉置后的矩陣4.3 稀疏矩陣稀疏矩陣 4.3.3 稀疏矩陣轉置 3. 三元組實現矩陣轉置三元組實現矩陣轉置方法二：對數組方法二：對數組 M (矩陣矩陣

33、Am n的三元組）的三元組） 掃描掃描 n 遍，每遍遍，每遍掃描掃描t次。第次。第 i 遍掃描，找到遍掃描，找到M中列號為中列號為i的元素（即的元素（即A中第中第i列中的非列中的非0元素），將這些元素轉置后依次放入元素），將這些元素轉置后依次放入T中。中。k=0;for(i=0; in; i+) for(j=0; j 1num0+ - 1num3+ - 1num3+ - 1num5+ - 1num5+ - 1num1+ - 1num1+ - 1num2+ - 1num2+ - 1num3+ - 2num3+ - 2num0+ - 2num0+ - 2num2+ - 2num2+ - 2 col

34、 0 1 2 3 4 5 col 0 1 2 3 4 5 numcol 2 1 2 2 0 1numcol 2 1 2 2 0 1 kcol 0 2 3 5 7 7 kcol 0 2 3 5 7 7表表4-1 num4-1 num數組和數組和k k數組數組計算計算numnum：(1) (1) 初始值為初始值為0 0；(2) (2) 順序掃描三元組，順序掃描三元組， 執行執行numnumcol+col+4.3 稀疏矩陣稀疏矩陣 4.3.3 稀疏矩陣轉置 3. 三元組實現矩陣轉置三元組實現矩陣轉置方法三方法三: 快速轉置算法快速轉置算法 數據成員數據成員MaxSize = 10cols = 6ro

35、ws = 7Nonzeros = 8trip0001610322205- 16311124123523- 86409176215rowcolvalue89(a)稀疏矩陣稀疏矩陣M00015000000000000091000000008000000312016022001665432105432104.3 稀疏矩陣稀疏矩陣 4.3.3 稀疏矩陣轉置 3. 三元組實現矩陣轉置三元組實現矩陣轉置方法三方法三: 快速轉置算法快速轉置算法 (程序程序4.6 4.6 ) template void SeqTriple:Transpose(SeqTriple& B)const int *num=new i

36、ntn; int *k=new intn; B.m=n; B.n=m; B.t=t; if(t0) for (int i=0; in; i+) numi=0; /初始化初始化num for (i=0; it; i+) numtripi.col+; /計算計算num k0=0; for (i=1; in; i+) ki=ki-1+numi-1; /計算計算k 基本步驟：基本步驟： (1)(1)計算計算numnum (2) (2)計算計算kk (3) (3)快速轉置快速轉置4.3 稀疏矩陣稀疏矩陣 4.3.3 稀疏矩陣轉置 3. 三元組實現矩陣轉置三元組實現矩陣轉置方法三方法三: 快速轉置算法快速

37、轉置算法 for (i=0; it; i+) int j = ktripi.col+; /掃描掃描this對象的第對象的第i項在項在B中的位置中的位置j B.tripj.row = tripi.col; B.tripj.col = tripi.row; B.tripj.value = tripi.value; /this對象第對象第i項轉置后放入項轉置后放入B的位置的位置j delete num; delete k;O(n+t)4.4 字符串字符串 4.4.1 字符串抽象數據類型 n字符串的定義字符串的定義字符串字符串(簡稱為串簡稱為串)是由是由n(n 0)個字符組成的有限序列。個字符組成的有

38、限序列。 S=“a0 a1 an1” ( n0 )第第4 4章章 數組和字符串數組和字符串4.1 4.1 數組數組4.2 4.2 特殊矩陣特殊矩陣4.3 4.3 稀疏矩陣稀疏矩陣4.4 字符串字符串 4.4.1 字符串抽象數據類型字符串抽象數據類型 4.4.2 字符串的存儲表示字符串的存儲表示 4.4.3 簡單模式匹配算法簡單模式匹配算法 4.4.4 模式匹配的模式匹配的KMP算法算法 例如：例如：“Hello world!”該串的長度該串的長度n=124.4 字符串字符串 4.4.1 字符串抽象數據類型 n 串串S中任意連續個字符組成的子序列P稱為該串的子串子串，S則稱為 主串主串。n 子串

39、子串在主串主串中的位置位置一般記為子串的首字符首字符在主串中的位置位置。主串：主串：S=abcabcaabcbcde子串：子串：P=abcP在在S中出現的位置：中出現的位置：0，3， 74.4 字符串字符串 4.4.1 字符串抽象數據類型 ADT 4.3 字符串字符串ADT數據數據: 由由n(0)個字符組成的有限序列個字符組成的有限序列S=a0a1an-1，0in 。運算運算: Create(): 建立空串建立空串 Destroy(): 撤消串撤消串 Length(): 返回當前串對象的長度返回當前串對象的長度 Clear(): 清空當前串對象清空當前串對象4.4 字符串字符串 4.4.1 字

40、符串抽象數據類型 Assign(S): 串賦值，將串賦值，將S賦值給當前串對象賦值給當前串對象 Concat(S): 串連接，將串連接，將S串連接在當前串對象的尾部串連接在當前串對象的尾部 Insert(P, i): 子串插入，將子串插入，將P插入當前串對象的插入當前串對象的i位置位置 Delete(i, len): 子串刪除，在當前串對象中，刪除自子串刪除，在當前串對象中，刪除自i開始的開始的 len個字符。個字符。 Substr(i, len): 返回子串，返回當前串對象中，從位置返回子串，返回當前串對象中，從位置i 開始的開始的len個字符組成的子串。個字符組成的子串。 Find(i,

41、P): 查找子串位置，查找子串查找子串位置，查找子串P在當前串對象中在當前串對象中 首次出現的位置；若不存在，則返回首次出現的位置；若不存在，則返回-1。4.4 字符串字符串 4.4.2 字符串的存儲表示n順序存儲表示：順序存儲表示：利用一維字符數組進行存儲。利用一維字符數組進行存儲。第第4 4章章 數組和字符串數組和字符串4.1 4.1 數組數組4.2 4.2 特殊矩陣特殊矩陣4.3 4.3 稀疏矩陣稀疏矩陣4.4 字符串字符串 4.4.1 字符串抽象數據類型字符串抽象數據類型 4.4.2 字符串的存儲表示字符串的存儲表示 4.4.3 簡單模式匹配算法簡單模式匹配算法 4.4.4 模式匹配的

42、模式匹配的KMP算法算法 例如：例如：char s20=“hello world!”；4.4 字符串字符串 4.4.2 字符串的存儲表示n鏈接存儲表示鏈接存儲表示4.4 字符串字符串 4.4.2 字符串的存儲表示#include class String public: String(); String(const char *p); String() delete str; ; int Find(int i, String &P);private: int n; /當前串長當前串長 char *str; /動態一維字符數組的指針動態一維字符數組的指針;String:String(const

43、char *p) n=strlen(p); str=new charn+1; strcpy(str, p);4.4 字符串字符串 字符串模式匹配Tiered wireless sensor network is a network model of flexibility and robustness, which consists of the traditional resource-limited sensor nodes and the resource-abundant storage nodes. In such architecture, collected data from

44、the sensor nodes are periodically submitted to the nearby storage nodes for archive purpose. When a query is requested, storage nodes also process the query and return qualified data as the result to the base station. The role of the storage nodes leads to an attack prone situation and leaves them m

45、ore vulnerable in a hostile environment. If any of them is compromised, fake data may be injected into and/or qualified data may be discarded. And the base station would receive incorrect answers incurring malfunction to applications. In this paper, 模式串：sensor network主主 串串字符串模式匹配字符串模式匹配：在主串主串S中查找模式串

46、模式串P是否出現、出現次數及位置等匹配算法是匹配算法是研究重點研究重點4.4 字符串字符串 4.4.3 簡單模式匹配算法n 設有兩個字符串設有兩個字符串S和和P，在串，在串S中找串中找串P的過程被稱為模式匹的過程被稱為模式匹配配 。這里。這里S為主串，為主串，P為子串，又稱為模式。為子串，又稱為模式。4.4 字符串字符串 4.4.3 簡單模式匹配算法int String:Find(int i, String &P) /查找是否存在，查找是否存在， /若存在，返回首次出現位置若存在，返回首次出現位置 if (in-1) /越界檢查越界檢查 coutOut of bounds!endl; retu

47、rn -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) return i; return -1;4.4 字符串字符串 4.4.3 簡單模式匹配算法n 簡單匹配算法的漸近時間復雜度：簡單匹配算法的漸近時間復雜度： 設主串和模式串的長度為設主串和模式串的長度為n和和m，簡單模式匹配算法在，簡單模式匹配算法在 最壞情況下的時間復雜

48、度是最壞情況下的時間復雜度是O(nm)。 平均情況下的時間復雜度也是平均情況下的時間復雜度也是O(nm)。高效的模式匹配算法：KMP Knuth, Morris and PrattO(n+m)4.4 字符串字符串 4.4.4 模式匹配的KMP算法 改進的模式匹配算法改進的模式匹配算法(KMP算法算法)思路：思路： 在主串和子串到達失配點時，主串在主串和子串到達失配點時，主串S不需要回溯，而模不需要回溯，而模式串式串P也不一定要回溯到第一個字符位置，其算法時間復雜也不一定要回溯到第一個字符位置，其算法時間復雜度降為度降為O(m+n)。 關鍵是解決模式串在每個失配點最少需要向前回溯到關鍵是解決模式

49、串在每個失配點最少需要向前回溯到哪個位置？哪個位置？ 簡單模式匹配算法的缺陷簡單模式匹配算法的缺陷：效率不高，原因在于匹配過：效率不高，原因在于匹配過程中有回溯。程中有回溯。 一趟匹配失敗時，即一趟匹配失敗時，即Si+jPj，主串回溯到，主串回溯到i+1位置位置，而模式串回溯到第，而模式串回溯到第1個字符位置，再重新開始匹配。個字符位置，再重新開始匹配。4.4 字符串字符串 4.4.4 模式匹配的KMP算法n 改進簡單模式匹配：例改進簡單模式匹配：例1P1 = S1且P1 P0 P0 S1 可省略可省略S串無需串無需回溯回溯4.4 字符串字符串 4.4.4 模式匹配的KMP算法n 改進簡單模式匹配：例改進簡單模式匹配：例2由例1可知、可省略P0=P3