数据结构2009级chapter单击此处编辑母版标题

1、1 Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURESn多维数组的概念与存储多维数组的概念与存储n 特殊矩阵特殊矩阵 n 稀疏矩阵稀疏矩阵n 字符串字符串n 广义表广义表第第4 4章章 数组、串与广义表数组、串与广义表4.1 多维数组的概念与存储一维数组一维数组:数组是数组是相同类型的数据元素的集合相同类型的数据元素的集合而一维数组的每个而一维数组的每个数组元素是一个序对，由下标（数组元素是一个序对，由下标（index）和值（）和值（value）组成。组成。n在高级语言

2、中的一维数组只能按元素的下标直接存取数在高级语言中的一维数组只能按元素的下标直接存取数组元素的值。组元素的值。一维数组的特点：一维数组的特点： 连续存储的线性聚集（别名连续存储的线性聚集（别名 向量）向量） 除第一个元素外，其他每一个元素有一除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。一个且仅有一个直接后继。多维数组 多维数组是一维数组的推广。二维数组：二维数组：“数组元素为一维数组数组元素为一维数组”的一维数的一维数组组三维数组：三维数组：“数组元素为二维数组数组元

3、素为二维数组”的一维数的一维数组组多维数组实际上是用一维数组实现的多维数组实际上是用一维数组实现的 多维数组的存储表示时时 0 0, ,) )( (时时 0 0, ,) )( (iliLOCiiLOC1LOC ( i ) = LOC ( i - -1 ) + l =+ i*lm列列n n行行|111101121202111101101000mnananamaaamaaamaaaa. m1, m2, m3。LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前前i i1 1页总页总元素个数元素个数第第i i1 1页的页的前前i i

4、2 2行总行总元素个数元素个数第第 i i2 2 行前行前 i i3 3 列元素个数列元素个数-各维元素个数为 m1, m2, m3, , mn-下标为 i1, i2, i3, , in 的数组元素的存储地址： （第一维优先的顺序）limianjnjknkj*111LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 4.2 特殊矩阵 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。u对称矩阵u三对角矩阵压缩存储压缩存储对称矩阵的压缩存储

5、设有一个 nn 的对称矩阵 A11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaan对称矩阵中的元素关于主对角线对称对称矩阵中的元素关于主对角线对称naij = aji， 0i, jn-1为节约存储，只存对角线及对角线以上的元素，或者为节约存储，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素只存对角线及对角线以下的元素11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa上三角矩阵上三角矩阵11121110122221201112111010020100nnn

6、nnnnnaaaaaaaaaaaaaaaa下三角矩阵下三角矩阵11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa 把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。 数组 B 共有 ？ 个元素。n*(n+1)2对称矩阵元素的存储表示（下三角矩阵）11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩阵 aij=a00+ ? ( i j)B0 1 2 3 4 5 6 7 8 n(n+1)/2-1a00 a10 a11 a20 a21 a22 a3

7、0 a31 a32 an-1n-1(i + 1)* i / 2 + jaji= ? j *(j +1) / 2 + i若已知某矩阵元素位于数组若已知某矩阵元素位于数组 B 的第的第 k个位置个位置（k0) i,j是是 ?对称矩阵元素的存储表示（下三角矩阵）11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩阵i (i + 1) / 2 k (i + 1)*(i + 2) / 2先求行：先求行：j = k - - i * (i + 1) / 2再求列：再求列：33323130232221201312111003020100aaa

8、aaaaaaaaaaaaa上三角矩阵B a00 a01 a02 a03 a11 a12 a13 a22 a23 a33 0 1 2 3 4 5 6 7 8 9若若i j，数组元素，数组元素Aij在数组在数组B中的存放位置为：中的存放位置为：a00+ ? n = 4对称矩阵元素的存储表示（上三角矩阵）对称矩阵元素的存储表示（上三角矩阵）(2*n- -i- -1) * i / 2 + j 如何计算：如何计算：n + (n- -1) + (n- -2) + + (n- -i+1) + j- -i = = (2*n- -i+1) * i / 2 + j- -i = = (2*n- -i- -1) *

9、i / 2 + j1121122232232221121110010000000000000000000AnnnnnnnnnnaaaaaaaaaaaaaB a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 10除主对角线及在主对角线、上下最临近的两条对角线上的元素外，除主对角线及在主对角线、上下最临近的两条对角线上的元素外，所有其它元素均为所有其它元素均为0 0000280000000091039000000006000017000110150022000A764.3 稀疏矩阵 (Sparse Matrix)

10、n设矩阵设矩阵 A 中有中有 s 个非零元素，若个非零元素，若 s 远远小于矩远远小于矩阵元素的总数（即阵元素的总数（即smn），则称），则称 A 为稀疏为稀疏矩阵。矩阵。 0000280000000091039000000006000017000110150022000A76 稀疏因子稀疏因子e: 设矩阵设矩阵 A 中有中有 s 个非零元素个非零元素, e = s/(m*n)n为节省存储空间，应只存储非零元素。为节省存储空间，应只存储非零元素。n非零元素的分布一般没有规律，应在存储非零非零元素的分布一般没有规律，应在存储非零元素时，同时存储该非零元素的行下标元素时，同时存储该非零元素的行下标

11、 row、列下标列下标 col、值、值 value。n每一个非零元素由一个每一个非零元素由一个三元组三元组唯一确定：唯一确定： ( 行号行号 row, 列号列号 col, 值值 value )稀疏矩阵及其三元组数组表示三元组三元组 (Trituple) 类的定义类的定义 template class SparseMatrix; template class Trituple friend class SparseMatrix private: int row, col; /非零元素所在行号非零元素所在行号/列号列号 Type value; /非零元素的值非零元素的值 template clas

12、s SparseMatrix int Rows, Cols, Terms; /行行/列列/非零元素数非零元素数 Trituple smArrayMaxTerms; public: /三元组表三元组表 SparseMatrix ( int MaxRow, int Maxcol ); SparseMatrix Transpose ( ); /转置转置 SparseMatrix /相加相加 Add ( SparseMatrix b ); SparseMatrix /相乘相乘 Multiply ( SparseMatrix b ); 行行行行( (r ro ow w) ) 列列列列( (c co ol

13、 l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8 0000280000000091039000000006000017000110150022000A76稀疏矩阵的转置0000015003901700000000006022280000000001100910000B 000028000000009103

14、9000000006000017000110150022000A6776A用三元组表表示的稀疏矩阵及其转置用三元组表表示的稀疏矩阵及其转置: 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2

15、28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 - - - -6 6 4 3 3 2 2 - - - -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 66 7A7 6A 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值

16、值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 - - - -6 6 4 3 3 2 2 - - - -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16

17、 6A A6 7A7 6A 设矩阵列数为设矩阵列数为 Cols，对矩阵三元组表扫描，对矩阵三元组表扫描Cols 次。次。第第 k 次检测列号为次检测列号为 k 的项。的项。 第第 k 次扫描找寻所有列号为次扫描找寻所有列号为 k 的项，将其行号变的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表列号、列号变行号，顺次存于转置矩阵三元组表template SparseMatrix SparseMatrix: Transpose ( ) SparseMatrix b ( Cols, Rows ); b.Rows = Cols; b.Cols = Rows; b.Terms = Terms;

18、 /转置矩阵的列数转置矩阵的列数,行数和非零元素个数行数和非零元素个数 if ( Terms 0 ) int CurrentB = 0; /转置三元组表存放指针转置三元组表存放指针 for ( int k = 0; k Cols; k+ ) for ( int i = 0; i Terms; i+ ) if ( smArrayi.col = k ) b.smArrayCurrentB.row = k; b.smArrayCurrentB.col = smArrayi.row; b.smArrayCurrentB.value= smArrayi.value; CurrentB+; return

19、b; 算法分析：算法分析：只适合于只适合于TermsCols*Rows稀疏矩阵转置算法(2):快速转置法 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 1

20、7 7 3 3 3 0 0 2 22 2 4 2 2 3 3 - - - -6 6 4 3 3 2 2 - - - -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 6 A A基本思想： 建立辅助数组 rowSize 和 rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。 扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查 rowStart 表，按查到的位置直接将该项存入转置三元组表中。for

21、 (int i = 0; i Cols; i+) rowSizei = 0;for ( i = 0; i Terms; i+ ) rowSizesmArrayi.col+; /rowSize的计算的计算如何计算如何计算rowSize 和和 rowStart？rowStart0 = 0; for ( i = 1; i Cols; i+ ) rowStarti = rowStarti-1+rowSizei-1;/rowStart的计算的计算 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 2

22、2 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8AA 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0

23、 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 - - - -6 6 4 3 3 2 2 - - - -6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 6A Atemplate SparseMatrixSparseMatrix:FastTranspos ( ) int *r

24、owSize = new intCols; int *rowStart = new intCols; SparseMatrix b ( Cols, Rows ); b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; if ( Terms 0 ) for (int i = 0; i Cols; i+) rowSizei = 0; for ( i = 0; i Terms; i+ ) rowSizesmArrayi.col+; /每一列非零元个数每一列非零元个数rowStart0 = 0; for ( i = 1; i Cols; i+ ) rowStar

25、ti = rowStarti-1+rowSizei-1;for ( i = 0; i Terms; i+ ) int j = rowStartsmArrayi.col; b.smArrayj.row = smArrayi.col; b.smArrayj.col = smArrayi.row; b.smArrayj.value = smArrayi.value; rowStartsmArrayi.col+; delete rowSize; delete rowStart; return b; 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va

26、al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8算法分析：算法分析：时间复杂度：时间复杂度：空间复杂性：空间复杂性：增加两个体积为增加两个体积为Cols的辅助数组的辅助数组O ( max(Cols, Terms )Terms ( istream &, Matrix & ); /矩阵输入重载函数private: MatrixN

27、ode *down, *right;/列/行链指针 Boolean head; /结点类型 Union Trituple triple; MatrixNode *next; /表头结点T, 矩阵元素结点或链头结点(False) MatrixNode ( Boolean, Trituple* ); /结点构造函数MatrixNode:MatrixNode ( Boolean b, Trituple *t ) /矩阵结点构造函数 head = b; /结点类型 if ( b ) right = next = this; else triple = *t;typedef MatrixNode *Ma

28、trixNodePtr;/一个指针数组, 用于建立稀疏矩阵class Matrix friend istream operator ( istream &, Matrix & ); /矩阵输入矩阵输入public: Matrix ( ); /析构函数析构函数private: MatrixNode *headnode; /稀疏矩阵的链头稀疏矩阵的链头;读入三元组读入三元组: (6,7,7),(0,2,11),(0,5,13),(1,0,12)基本思想：基本思想： 建立链头结点建立链头结点 初始化行链表和列链表的头指针数组初始化行链表和列链表的头指针数组 将输入的非零元链入行链表；

29、如果行结束，将输入的非零元链入行链表；如果行结束，接闭合该行接闭合该行 将输入的非零元链入列链表；将输入的非零元链入列链表； 闭合所有列；闭合所有列； 所有行所有行/列表头结点链接在一起列表头结点链接在一起istream operator ( istream & is, Matrix & matrix ) Trituple s; int p; is s.row s.col s.value; /输入矩阵的行数, 列数和非零元素个数 if ( s.row s.col ) p = s.row; else p = s.col; /取行、列数大者 matrix.headnode = /整

30、个矩阵链头结点整个矩阵链头结点 new MatrixNode ( False, &s ); if ( !p ) /零矩阵时 matrix.headnode-right = matrix.headnode; return is; MatrixNodePtr *H = new MatrixNodePtr ( p ); /建立表头指针数组, 指向各链表的表头 for ( int i = 0; i p; i+ ) Hi = new MatrixNode ( True, 0 ); int CurrentRow = 0; MatrixNode *last = H0; /lastlast为为当前行最

31、后结点 for ( i = 0; i t.row t.col t.value; /输入非零元素的三元组 if ( t.row CurrentRow ) /如果行号大于当前行,闭合当前行 last-right = HCurrentRow; CurrentRow = t.row; last = HCurrentRow; last = last-right =new MatrixNode ( False, &t ); /链入当前行 Ht.col-next = Ht.col-next-down = last; /链入列链表，初始为0，依次连接列 last-right = HCurrentRow

32、; /闭合最后一行 /闭合各列链表 for ( i = 0; i next-down = Hi; /链接所有表头结点 for ( i = 0; i next =Hi+1; Hp-1-next = matrix.headnode; matrix.headnode-right = H0; delete H; return is;算法分析：算法分析：建立表头结点：建立表头结点：O(maxn,m);链入新结点：链入新结点： O(1)链入链入t个非零元结点：个非零元结点：O(max(t, n,m)4.4 字符串0 若一个字符串不为空，从这个串中连续取出若若一个字符串不为空，从这个串中连续取出若干个字符组

33、成的串叫做原串的干个字符组成的串叫做原串的子串子串。 称子串的第称子串的第0个字符在串中的位置为个字符在串中的位置为子串在串中子串在串中的位置的位置。空串是任意串的子串；任一串是它自身的子串。空串是任意串的子串；任一串是它自身的子串。除本身外，一个串的其它子串都是他的真子串。除本身外，一个串的其它子串都是他的真子串。 const int maxLen = 128; class String int curLen; /串的当前长度串的当前长度 char *ch; /串的存储数组串的存储数组 public: String ( const String & ob ); String ( co

34、nst char *init ); String ( ); String ( ) delete ch; int Length ( ) const return curLen; String &operator ( ) ( int pos, int len ); int operator = ( const String &ob ) const return strcmp (ch, ob.ch) = 0; int operator != ( const String &ob ) const return strcmp (ch, ob.ch) != 0; String &a

35、mp;operator = ( const String &ob ); String &operator += ( const String &ob ); char &operator ( int i ); int Find ( String& pat ) const;字符串重载操作的使用示例字符串重载操作的使用示例 序号重载操作操作使用示例 (设使用操作的当前串为S：tsinghua) 1( ) (int pos, int len)取子串取子串S1 = S(3, 2), /S1结果为结果为 ng 2= (const AString& ob)判两

36、串判两串相等相等S = S1 , /若若S与与S1相等相等, 结果为结果为true，否则为，否则为false 3!= (const AString& ob)判两串判两串不等不等S != S1 , /若若S与与S1不等，不等， 结果为结果为true，否则为，否则为false 4! ()判串空判串空否否!S , /若串若串S为空，结果为为空，结果为 true，否则为，否则为false序序号号重载操作重载操作操作操作使用示例使用示例 (设使用操作的当前设使用操作的当前串为串为S：tsinghua) 5= (const AString& ob)串赋值串赋值S1 = S, /S1结果为结

37、果为tsinghua 6+= (const AString& ob)串连接串连接若设若设S1为为 university, 执行执行S += S1, /S结果为结果为tsinghua university 7 (int i)取第取第 i个字符个字符S5, /取出字符为取出字符为h String:String ( const String &ob ) /复制构造函数：从已有串复制构造函数：从已有串ob复制复制 ch = new charmaxLen+1; if ( !ch ) cerr “Alocation Error n”; exit(1); curLen = ob.curLen

38、; strcpy ( ch, ob.ch ); String:String ( const char *init ) /串构造函数串构造函数 ch = new charmaxLen+1; if ( !ch ) cerr =0;len=0;pos+len maxLen,i.e. pos+len-1= maxLen String &String: operator ( ) ( int pos, int len ) String *temp = new String; /动态分配动态分配 if ( pos = maxLen | len = curLen ) len = curLen - po

39、s; tempcurLen = len; /子串长度子串长度 for ( int i = 0, j = pos; i len; i+, j+ ) tempchi = chj; /传送串数组传送串数组 tempchlen = 0; /子串结束子串结束 return *temp; char &String:operator ( int i ) /按串名提取串中第按串名提取串中第i个字符个字符 if ( i = curLen ) cout “字符串下标超界字符串下标超界!n ”; exit (1) ; return chi;例：串例：串 st = “university”, 使用示例使用示例

40、 newSt = st；newChar = st1;数组赋值数组赋值 newSt = “university”提取字符提取字符 newChar = nString &String:operator += ( const String &ob ) /串连接串连接 char * temp =ch; /暂存原串数组暂存原串数组 curLen += ob.curLen; /串长度累加串长度累加 ch = new char maxLen+1; if ( ! ch ) cerr “字符串下标超界字符串下标超界!n ”; exit (1) ; strcpy ( ch, temp ); /拷贝

41、原串数组拷贝原串数组 strcat ( ch, ob.ch ); /连接连接ob串数组串数组 delete temp; return *this;例：串例：串 st1 = “Nanjing ”, st2 = “university”, st1 += st2;st1 = “Nanjing university”st2 = “university”字符串的模式匹配 Tt0 t1 t2 tm-1 tn-1 pat p0 p1 p2 pm-1模式匹配算法1:朴素的模式匹配算法基本思想：基本思想： 分别用指针指示目标串分别用指针指示目标串T和模式串和模式串pat; 用用pat的字符依次与的字符依次与T中

42、的字符做比较中的字符做比较 如果模式如果模式pat中的每个字符和目标中的每个字符和目标T的一个的一个连续的字符序列相等，则称模式匹配成功，连续的字符序列相等，则称模式匹配成功，返回模式第返回模式第0个字符在目标中匹配的位置；个字符在目标中匹配的位置； 否则从目标否则从目标T的下一个字符起重新和模式的下一个字符起重新和模式pat 的字符比较的字符比较匹配失败，匹配失败， 函数返回函数返回-1 T t0 t1 t2 tm-1 tn-1 p p0 p1 p2 pm-1 Tt0 t1 t2 tm-1 tn-1 pat p0 p1 p2 pm-1 Tt0 t1 t2 tm-1 tn-1 pat p0 p

43、1 p2 pm-1curLen - pat.curLen int String:Find ( String &pat ) const /朴素的模式匹配朴素的模式匹配(带回溯的模式匹配带回溯的模式匹配) char * p = pat.ch, * s = ch; int i = 0; if ( *p & *s )/当两串未检测完当两串未检测完 while ( i = curLen - pat.curLen ) if ( *p+ = *s+ ) /比较串字符比较串字符 if ( !*p ) return i; /串扫描完串扫描完 else i+; s = ch + i; p = pa

44、t.ch; /对应字符不相等对应字符不相等 return -1; 算法分析：设目标算法分析：设目标T的长度为的长度为n,模式模式P的的长度为长度为m。时间复杂度：时间复杂度：最坏情况比较最坏情况比较n-m+1趟，每趟，每趟比较趟比较m次，次，总比较次数达总比较次数达(n-m+1)*m一般，一般，m 0，那么在下一趟比较时模式串，那么在下一趟比较时模式串 P的的起始比较位置是起始比较位置是 pnext(j)，目标串，目标串 T 的指针不回的指针不回溯，仍指向上一趟失配的字符；溯，仍指向上一趟失配的字符； 如果如果 j = 0，则目标串指针，则目标串指针 T 进一，模式串指进一，模式串指针针 P

45、回到回到 p0，继续进行下一趟匹配比较。，继续进行下一趟匹配比较。 a a b a a b a a b c a c a a b c a a a b c a c a a b a a b a a b c a c a a b c b a a b c a c a c a b a a b a b c a c a a b c a b a a b a c a c a b a a b a b c a c a a b c (a b) a b c a c int String : fastFind ( String pat ) const /KMP匹配算法匹配算法 int posP = 0, posT = 0;

46、int lengthP = pat.curLen, lengthT = curLen; while ( posP lengthP & posT lengthT ) if ( pat.chposP = chposT ) posP+; posT+; /相等继续比较相等继续比较 else if ( posP = 0 ) posT+; /不相等不相等 else posP = pat.next posP; if ( posP lengthP ) return -1; else return posT - lengthP; =nextj (k)+1(最小整数最小整数k)nextj+1P=“abaa

47、bcaba”的的next函数函数 j 0 1 2 3 4 5 6 7 P P a b a a b c a c next ( ( j j ) ) -100112 0 1例子说明：j01234567Pabaabcacnext j-10011201j=4k=1p3 p1k=nk=0p3=p0n4= =k+1 =1j=3k=0n3= =k+1 =1j=2k=0p1 p0k=nk= =-1n2= =k+1 =0j=1k=-1n1=k+1=0j=0n0=-1j=5k=1p4=p1n5= =k+1 =2j=6k=2p5 p2k=nk=0p5 p0k=nk=-1n5=k+1=0j=7k=0p6=p0n7=k+

48、1 =1对当前串计算对当前串计算nextnext特征向量的算法特征向量的算法void AString:getNext(int next) int j = 0, k = -1, lengthP = curLength; next0 = -1; while (j utype, NULL ); switch ( ls-utype ) case 0: q-value.ref = ls-value.ref; break; case 1: grinfo = grinfo; break; case 2: q-value.charinfo = ls-value.c

49、harinfo; break; case 3: q-value.hlink = Copy (ls-value.hlink); q-tlink = Copy (ls-tlink); return q; 0 11 a1 b0 121 e20 11 c1 d20 0ls时间复杂性分析：时间复杂性分析：若共有若共有m个结点，则时间复杂度为：个结点，则时间复杂度为：O（m）（2 2）求广义表的深度）求广义表的深度1111234设非空广义表设非空广义表LS=（a0,a1,an-1）int GenList : depth ( GenListNode *ls ) if ( ls-tlink = NULL ) return 1; /空表 GenListNode * temp = ls-tlink; int m = 0; while ( temp != NULL ) /在表顶层横扫 if ( temp-utype = 3 ) /结点为表结点 int n = d