1、1数据结构（用面向对象方法与C+语言描述）第二版2清华大学计算机系清华大学计算机系殷人昆殷人昆2第四章 数组、串与广义表数据结构电子教案数据结构电子教案殷人昆殷人昆 王王 宏宏3 3第四章第四章 数组、串与广义表数组、串与广义表4 4一维数组一维数组数组是数组是相同类型的数据元素的集合相同类型的数据元素的集合而一维而一维数组的每个数组元素是一个序对，由数组的每个数组元素是一个序对，由下标下标（index）和值（）和值（value）组成。）组成。n一维数组的示例一维数组的示例n在高级语言中的一维数组只能按元素的下标在高级语言中的一维数组只能按元素的下标直接存取数组元素的值。直接存取数组元素的值。
2、35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 95 5一维数组的定义和初始化一维数组的定义和初始化#include main()int a3=3,5,7,*elem,i;/静态数组 for(i=0;i 3;i+)cout ai endl;elem=new int3;/动态数组 for(i=0;i elemi;while(elem)cout *elem 0 a,i=0 35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9l l l l l l l l l l a+i*la9 9二维数组二维数组n一维数组常
3、被称为向量（一维数组常被称为向量（Vector）。）。n二维数组二维数组 Amn 可看成是由可看成是由 m 个行向量个行向量组成的向量，也可看成是由组成的向量，也可看成是由 n 个列向量组成个列向量组成的向量。的向量。n一个二维数组类型可以定义为其分量类型为一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型一维数组类型的一维数组类型:typedef T array2mn;/T为元素类型 等价于：等价于：typedef T array1n;/列向量类型 typedef array1 array2m;/二维数组类型1010n同理，一个三维数组类型可以定义为其数据同理，一个三维数组类型
4、可以定义为其数据元素为二维数组类型的一维数组类型。元素为二维数组类型的一维数组类型。n静态定义的数组，其维数和维界不再改变，静态定义的数组，其维数和维界不再改变，在编译时静态分配存储空间。一旦数组空间在编译时静态分配存储空间。一旦数组空间用完则不能扩充。用完则不能扩充。n动态定义的数组，其维界不在说明语句中显动态定义的数组，其维界不在说明语句中显式定义，而是在程序运行中创建数组对象时式定义，而是在程序运行中创建数组对象时通过通过 new 动态分配和初始化，在对象销毁动态分配和初始化，在对象销毁时通过时通过 delete 动态释放。动态释放。n用一维内存来表示多维数组，就必须按某种用一维内存来表
5、示多维数组，就必须按某种次序将数组元素排列到一个序列中。次序将数组元素排列到一个序列中。11 11二维数组的动态定义和初始化二维数组的动态定义和初始化#include int*A;int row=3,col=3;int i,j;A=new int*row;for(i=0;i row;i+)Ai=new int col;for(i=0;i row;i+)for(j=0;j Aij;1212二维数组中数组元素的顺序存放二维数组中数组元素的顺序存放111101121202111101101000mnananamaaamaaamaaaan行优先存放：行优先存放：设数组开始存放位置设数组开始存放位置 L
6、OC(0,0)=a,每个每个元素占用元素占用 l 个存储单元个存储单元LOC(j,k)=a+(j*m+k)*l1313111101121202111101101000mnananamaaamaaamaaaa列优先存放：列优先存放：设数组开始存放位置设数组开始存放位置 LOC(0,0)=a,每个每个元素占用元素占用 l 个存储单元个存储单元 LOC(j,k)=a+(k*n+j)*l1414三维数组三维数组n各维元素个数为各维元素个数为 m1,m2,m3n下标为下标为 i1,i2,i3的数组元素的存储地址：的数组元素的存储地址：（按页行列存放）（按页行列存放）LOC(i1,i2,i3)=a+(i1
7、*m2*m3+i2*m3+i3)*l前前i1页页总元素总元素个数个数第第i1页页前前i2行行总元素总元素个数个数第第 i2 行行前前 i3 列列元素个元素个数数1515n n 维数组维数组n各维元素个数为各维元素个数为 m1,m2,m3,mnn下标为下标为 i1,i2,i3,in 的数组元素的存储地的数组元素的存储地址：址：LOC(i1,i2,in)=a+(i1*m2*m3*mn+i2*m3*m4*mn+in-1*mn+in)*llimianjnjknkj*1111616特殊矩阵特殊矩阵n特殊矩阵是指非零元素或零元素的分布有特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。一定规律的矩阵。n
8、特殊矩阵的压缩存储主要是针对阶数很高特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储的元素，如零元素或对称元素，不再存储。存储。u对称矩阵对称矩阵u三对角矩阵三对角矩阵1717对称矩阵的压缩存储对称矩阵的压缩存储n设有一个设有一个 n n 的对称矩阵的对称矩阵 A。11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaan对称矩阵中的元素关于主对角线对称对称矩阵中的元素关于主对角线对称，aij=aji，0i,jn-118181112111
9、0122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaan为节约存储，只存对角线及对角线以上的元为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。素，或者只存对角线或对角线以下的元素。前者称为前者称为上三角矩阵上三角矩阵，后者称为，后者称为下三角矩阵下三角矩阵。下三角矩阵191911121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa上三角矩阵n把它们按行存放于一个一维数组把它们按行存放于一个一维数组 B 中，称之中，称之为对称矩阵为对称矩阵 A 的压缩存储方式。的压缩存
10、储方式。n数组数组 B 共有共有 n+(n-1)+1=n*(n+1)2 个元素。个元素。202011121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩阵若若 i j,数组元素数组元素Aij在数组在数组B中的存放位置中的存放位置为为 1+2+i+j=(i+1)*i/2+jB a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1 0 1 2 3 4 5 6 7 8 n(n+1)/2-1前i行元素总数 第i行第j个元素前元素个数2121n若若 i j，数组元素，数组元素 Aij 在矩阵的上三角部在矩阵
11、的上三角部分分,在数组在数组 B 中没有存放，可以找它的对称中没有存放，可以找它的对称元素元素Aji：=j*(j+1)/2+i n若已知某矩阵元素位于数组若已知某矩阵元素位于数组 B 的第的第 k个位置个位置（k0），可寻找满足，可寻找满足 i(i+1)/2 k (i+1)*(i+2)/2的的 i,此即为此即为该元素的行号。该元素的行号。j=k-i*(i+1)/2 此即为该元素的列号。此即为该元素的列号。n例，当例，当 k=8,3*4/2=6 k j，数组元素，数组元素Aij在矩阵的下三角部在矩阵的下三角部分，在数组分，在数组 B 中没有存放。因此，找它的中没有存放。因此，找它的对称元素对称元
12、素Aji。Aji在数组在数组 B 的第的第(2*n-j-1)*j/2+i 的位置中找到。的位置中找到。24241121122232232221121110010000000000000000000AnnnnnnnnnnaaaaaaaaaaaaaB a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 102525n三对角矩阵中除主对角线及在主对角线上三对角矩阵中除主对角线及在主对角线上 下下最临近的两条对角线上的元素外，所有其它最临近的两条对角线上的元素外，所有其它元素均为元素均为0。总共有。总共有3n-2个非零
13、元素。个非零元素。n将三对角矩阵将三对角矩阵A中三条对角线上的元素按行存中三条对角线上的元素按行存放在一维数组放在一维数组 B 中，且中，且a00存放于存放于B0。n在三条对角线上的元素在三条对角线上的元素aij 满足满足 0 i n-1,i-1 j i+1n在一维数组在一维数组 B 中中 Aij 在第在第 i 行，它前面有行，它前面有 3*i-1 个非零元素个非零元素,在本行中第在本行中第 j 列前面有列前面有 j-i+1 个，所以元素个，所以元素 Aij 在在 B 中位置为中位置为 k=2*i+j。2626n若已知三对角矩阵中某元素若已知三对角矩阵中某元素 Aij 在数组在数组 B 存放于
14、第存放于第 k 个位置，则有个位置，则有 i=(k+1)/3 j=k-2*in例如，当例如，当 k=8 时，时，i=(8+1)/3 =3,j=8-2*3=2 当当 k=10 时，时，i=(10+1)/3 =3,j=10-2*3=42727 0000280000000091039000000006000017000110150022000A76稀疏矩阵稀疏矩阵 (Sparse Matrix)(Sparse Matrix)n设矩阵设矩阵 A 中有中有 s 个非零元素，若个非零元素，若 s 远远小于远远小于矩阵元素的总数（即矩阵元素的总数（即smn），则称），则称 A 为为稀疏矩阵。稀疏矩阵。282
15、8n设矩阵设矩阵 A 中有中有 s 个非零元素。令个非零元素。令 e=s/(m*n),称称 e 为矩阵的稀疏因子。为矩阵的稀疏因子。n有人认为有人认为 e0.05 时称之为稀疏矩阵。时称之为稀疏矩阵。n在存储稀疏矩阵时，为节省存储空间，应只在存储稀疏矩阵时，为节省存储空间，应只存储非零元素。但由于非零元素的分布一般存储非零元素。但由于非零元素的分布一般没有规律，故在存储非零元素时，必须记下没有规律，故在存储非零元素时，必须记下它所在的行和列的位置它所在的行和列的位置(i,j)。n每一个三元组每一个三元组(i,j,aij)唯一确定了矩阵唯一确定了矩阵A的一的一个非零元素。因此，稀疏矩阵可由表示非
16、零个非零元素。因此，稀疏矩阵可由表示非零元的一系列三元组及其行列数唯一确定。元的一系列三元组及其行列数唯一确定。2929稀疏矩阵的定义稀疏矩阵的定义const int drows=6,dcols=7,dterms=9;templatestruct Triple /三元组 int row,col;/非零元素行号/列号 E value;/非零元素的值 void operator=(Triple&R)/赋值 row=R.row;col=R.col;value=R.value;template class SparseMatrix 3030public:SparseMatrix(int Rw=drow
17、s,int Cl=dcols,int Tm=dterms);/构造函数 void Transpose(SparseMatrix&b);/转置 void Add(SparseMatrix&a,SparseMatrix&b);/a=a+b void Multiply(SparseMatrix&a,SparseMatrix&b);/a=a*bpvivate:int Rows,Cols,Terms;/行列非零元素数 Triple*smArray;/三元组表;3131稀疏矩阵的构造函数稀疏矩阵的构造函数template SparseMatrix:SparseMatrix(int Rw,int Cl,in
18、t Tm)Rows=Rw;Cols=Cl;Terms=Tm;smArray=new TripleTerms;/三元组表 if(smArray=NULL)cerr “存储分配失败！”endl;exit(1);3232稀疏矩阵的转置稀疏矩阵的转置n一个一个 m n 的矩阵的矩阵 A，它的转置矩阵，它的转置矩阵 B 是一是一个个 n m 的矩阵，且的矩阵，且 Aij=Bji。即即u矩阵矩阵 A 的行成为矩阵的行成为矩阵 B 的列的列u矩阵矩阵 A 的列成为矩阵的列成为矩阵 B 的行。的行。n在稀疏矩阵的三元组表中，非零矩阵元素按在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列号递增的
19、顺序行存放。当行号相同时，按列号递增的顺序存放。存放。n稀疏矩阵的转置运算要转化为对应三元组表稀疏矩阵的转置运算要转化为对应三元组表的转置。的转置。3333 0000280000000091039000000006000017000110150022000稀疏矩阵稀疏矩阵 行行行行(r ro ow w)列列列列(c co ol 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
20、91 1 7 5 5 2 2 2 28 834340000015003901700000000006022280000000001100910000 行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)0 0 0 4 4 9 91 1 1 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 3 3 0 0 2 22 2 4 3 3 2 2 -6 6 5 5 5 1 1 1 17 7 6 5 5 3 3 3 39 9 7 6 6 0 0 1 16 63535用三元组表表示的稀疏矩阵及其转置用三元组表表示的稀疏矩阵及其转置原矩阵三元
21、组表原矩阵三元组表 转置矩阵三元组表转置矩阵三元组表3636稀疏矩阵转置算法思想稀疏矩阵转置算法思想n设矩阵列数为设矩阵列数为 Cols，对矩阵三元组表扫描，对矩阵三元组表扫描Cols 次。第次。第 k 次检测列号为次检测列号为 k 的项。的项。n第第 k 次扫描找寻所有列号为次扫描找寻所有列号为 k 的项，将其行的项，将其行号变列号、列号变行号，顺次存于转置矩阵号变列号、列号变行号，顺次存于转置矩阵三元组表。三元组表。3737稀疏矩阵的转置稀疏矩阵的转置template void SparseMatrix:Transpose(SparseMatrix&B)/转置this矩阵，转置结果由B返回
22、 B.Rows=Cols;B.Cols=Rows;B.Terms=Terms;/转置矩阵的列数,行数和非零元素个数 if(Terms 0)int CurrentB=0;/转置三元组表存放指针 int i,k;3838 for(k=0;k Cols;k+)/处理所有列号 for(i=0;i Terms;i+)if(smArrayi.col=k)B.smArrayCurrentB.row=k;B.smArrayCurrentB.col=smArrayi.row;B.smArrayCurrentB.value=smArrayi.value;CurrentB+;3939n设矩阵三元组表总共有设矩阵三元
23、组表总共有 t 项，上述算法的时项，上述算法的时间代价为间代价为 O(n*t)。当非零元素的个数当非零元素的个数 t 和和 m*n 同数量级时，算法同数量级时，算法transmatrix的时间复的时间复杂度为杂度为O(m*n2)。n若矩阵有若矩阵有 200 行，行，200 列，列，10,000 个非零元个非零元素，总共有素，总共有 2,000,000 次处理。次处理。n快速转置算法的思想为：对快速转置算法的思想为：对 原矩阵原矩阵A 扫描一扫描一遍，按遍，按 A 中每一元素的列号，立即确定在转中每一元素的列号，立即确定在转置矩阵置矩阵 B 三元组表中的位置，并装入它。三元组表中的位置，并装入它
24、。4040n为加速转置速度，建立辅助数组为加速转置速度，建立辅助数组 rowSize 和和 rowStart：urowSize记录矩阵转置前各列，即转置矩记录矩阵转置前各列，即转置矩阵各行非零元素个数；阵各行非零元素个数；urowStart记录各行非零元素在转置三元组记录各行非零元素在转置三元组表中开始存放位置。表中开始存放位置。n扫描矩阵三元组表，根据某项列号，确定扫描矩阵三元组表，根据某项列号，确定它转置后的行号它转置后的行号,查查 rowStart 表表,按查按查到到的位置直接将该项存入转置三元组表中的位置直接将该项存入转置三元组表中4141A三元组三元组(0)(1)(2)(3)(4)(
25、5)(6)(7)行行row00112345列列col36153502值值value22151117-63991284242稀疏矩阵的快速转置算法稀疏矩阵的快速转置算法template void SparseMatrix:FastTranspos(SparseMatrix&B)int*rowSize=new intCols;/列元素数数组 int*rowStart=new intCols;/转置位置数组 B.Rows=Cols;B.Cols=Rows;B.Terms=Terms;if(Terms 0)int i,j;for(i=0;i Cols;i+)rowSizei=0;4343 for(i=
26、0;i Terms;i+)rowSizesmArrayi.col+;rowStart0=0;for(i=1;i Cols;i+)rowStarti=rowStarti-1+rowSizei-1;for(i=0;i Terms;i+)j=rowStart smArrayi.col;B.smArrayj.row=smArrayi.col;B.smArrayj.col=smArrayi.row;B.smArrayj.value=smArrayi.value;rowStart smArrayi.col+;4444 delete rowSize;delete rowStart;带行指针数组的二元组表带行
27、指针数组的二元组表n稀疏矩阵的三元组表可以用带行指针数组的稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。二元组表代替。n在行指针数组中元素个数与矩阵行数相等。在行指针数组中元素个数与矩阵行数相等。第第 i 个元素的下标个元素的下标 i 代表矩阵的第代表矩阵的第 i 行，元素行，元素的内容即为稀疏矩阵第的内容即为稀疏矩阵第 i 行的第一个非零元行的第一个非零元素在二元组表中的存放位置素在二元组表中的存放位置。4545n二元组表中每个二元组只记录非零元素的列二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序号和元素值，且各二元组按行号递增的顺序排列。排列。00200
28、90000000000080000300040140000000130011012 行指针数组行指针数组 row 0 0 1 3 2 4 3 6 4 7 5 7 二元组表二元组表 data col value 0 0 12 1 2 11 2 5 13 3 6 14 4 1-4 5 5 3 6 3 8 7 1-9 8 4 2 4646字符串字符串 (String)(String)n字符串是字符串是 n(0)个字符的有限序列，个字符的有限序列，记作记作 S:“c1c2c3cn”其中，其中，S 是串名字是串名字 “c1c2c3cn”是串值是串值 ci 是串中字符是串中字符 n 是串的长度，是串的长度
29、，n=0 称为称为空串空串。n注意：注意：空串空串和和空白串空白串不同，例如不同，例如“”和和“”“”分别表示长度为分别表示长度为1的空白串和长度为的空白串和长度为0的空串。的空串。4747n串中任意个连续字符组成的子序列称为该串串中任意个连续字符组成的子序列称为该串的的子串子串，包含子串的串相应地称为主，包含子串的串相应地称为主串串。n通常将子串在主串中首次出现时，该子串首通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号，定义为子串在主字符对应的主串中的序号，定义为子串在主串中的位置。例如，设串中的位置。例如，设A和和B分别为分别为 A=“This is a string”B=“
30、is”则则 B 是是 A 的子串，的子串，A 为主串。为主串。B 在在 A 中出现中出现了两次，首次出现所对应的主串位置是了两次，首次出现所对应的主串位置是2（从（从0开始）。因此，称开始）。因此，称 B 在在 A 中的位置为中的位置为2。n特别地，空串是任意串的子串，任意串是其特别地，空串是任意串的子串，任意串是其自身的子串。自身的子串。4848n通常在程序中使用的串可分为两种：串变量通常在程序中使用的串可分为两种：串变量和串常量。和串常量。n串常量在程序中只能被引用但不能改变它的串常量在程序中只能被引用但不能改变它的值，即只能读不能写。通常串常量是由直接值，即只能读不能写。通常串常量是由直
31、接量来表示的，例如语句量来表示的，例如语句 Error(“overflow”)中中“overflow”是直接量。但有的语言允许对串是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如常量命名，以使程序易读、易写。如C+中，中，可定义可定义 const char path=“dir/bin/appl”;n这里这里path是一个串常量。串变量和其它类型是一个串常量。串变量和其它类型的变量一样，其取值可以改变。的变量一样，其取值可以改变。4949字符串的类定义字符串的类定义#ifndef ASTRING_H/定义在文件“Astring.h”中#define ASTRING_H#define
32、defaultSize=128;/字符串的最大长度class AString/对象:零个或多个字符的一个有限序列。private:char*ch;/串存放数组 int curLength;/串的实际长度int maxSize;/存放数组的最大长度public:5050 AString(int sz=defaultSize);/构造函数 AString(const char*init);/构造函数 AString(const AString&ob);/复制构造函数 AString()delete ch;/析构函数 int Length()const return curLength;/求长度 A
33、string&operator()(int pos,int len);/求子串 bool operator=(AString&ob)const return strcmp(ch,ob.ch)=0;/判串相等.若串相等,则函数返回true bool operator!=(AString&ob)const return strcmp(ch,ob.ch)!=0;/判串不等.若串不相等,则函数返回true 5151 bool operator!()const return curLength=0;/判串空否。若串空,则函数返回true AString&operator=(AString&ob);/串赋
34、值 AString&operator+=(AString&ob);/串连接 char&operator (int i);/取第 i 个字符 int Find(AString&pat,int k)const;/串匹配;5252字符串的构造函数字符串的构造函数AString:AString(int sz)/构造函数：创建一个空串 maxSize=sz;ch=new charmaxSize+1;/创建串数组 if(ch=NULL)cerr defaultSize)?len:defaultSize;ch=new charmaxSize+1;/创建串数组 if(ch=NULL)cerr “存储分配错!n
35、”;exit(1);curLength=len;/复制串长度 strcpy(ch,init);/复制串值；5454字符串的复制构造函数字符串的复制构造函数AString:AString(const AString&ob)/复制构造函数：从已有串ob复制 maxSize=ob.maxSize;/复制串最大长度 ch=new charcurLength+1;/创建串数组 if(ch=NULL)cerr=0&pos+len-1 0)/提取子串 if(pos+len-1=curLength)len=curLength-pos;/调整提取字符数 temp.curLength=len;/子串长度5959
36、for(int i=0,j=pos;i len;i+,j+)temp.chi=chj;/传送串数组 temp.chlen=0;/子串结束 return temp;n例：串例：串 st=“university”,pos=3,len=4使用示例使用示例 subSt=st(3,4)提取子串提取子串 subSt=“vers”6060串重载操作串重载操作:串赋值串赋值AString&AString:operator=(const AString&ob)if(&ob!=this)/若两个串相等为自我赋值 delete ch;ch=new charmaxSize+1;/重新分配 if(ch=NULL)cer
37、r “存储分配失败!n”;exit(1);curLength=ob.curLength;strcpy(ch,ob.ch);else cout “字符串自身赋值出错!n”;return this;6161串重载操作：取串的第串重载操作：取串的第i i个字符个字符char AString:operator (int i)/串重载操作：取当前串*this的第i个字符 if(i=curLength)cout=n)?maxSize:n;/新空间大小 ch=new charm;if(ch=NULL)cerr “存储分配错!n”;exit(1);maxSize=m;curLength=n;strcpy(ch
38、,temp);/拷贝原串数组 strcat(ch,ob.ch);/连接ob串数组 6363 delete temp;return this;n例：串例：串 st1=“beijing”,st2=“university”,使用示例使用示例 st1+=st2;连接结果连接结果 st1=“beijing university”st2=“university”6464串的模式匹配串的模式匹配n定义定义 在主串中寻找子串（第一个字符）在在主串中寻找子串（第一个字符）在串中的位置串中的位置n词汇词汇 在模式匹配中，子串称为模式，主串在模式匹配中，子串称为模式，主串称为目标。称为目标。n示例示例 目标目标 T
39、:“Beijing”模式模式 P:“jin”匹配结果匹配结果=3 6565朴素的模式匹配朴素的模式匹配（B-FB-F算法）算法）第第1趟趟 T a b b a b a P a b a 第第2趟趟 T a b b a b a P a b ai=2j=2i=1j=0第第3趟趟 T a b b a b a P a b a 第第4趟趟 T a b b a b a P a b ai=2j=0i=6j=36666朴素的模式匹配算法朴素的模式匹配算法int AString:Find(AString&pat,int k)const/在当前串中从第 k 个字符开始寻找模式 pat 在当/前串中匹配的位置。若匹配
40、成功,则函数返回首/次匹配的位置,否则返回-1。int i,j,n=curLength,m=pat.curLength;for(i=k;i=n-m;i+)for(j=0;j 0，那么在下一趟比较时模式串，那么在下一趟比较时模式串 P的起始比较位置是的起始比较位置是 pnext(j)，目标串，目标串 T 的指的指针不回溯，仍指向上一趟失配的字符；针不回溯，仍指向上一趟失配的字符；u如果如果 j=0，则目标串指针，则目标串指针 T 进一，模式进一，模式串指针串指针 P 回到回到 p0，继续进行下一趟匹配比，继续进行下一趟匹配比较。较。7575 运用运用KMP算法的匹配过程算法的匹配过程第第1趟趟
41、目标目标 a c a b a a b a a b c a c a a b c 模式模式 a b a a b c a c j=1 next(1)=0，下次下次p0第第2趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式 a b a a b c a c j=0 下次下次p0,目标指针进目标指针进 1 第第3趟趟 目标目标 a c a b a a b a a b c a c a a b c 模式模式 a b a a b c a c j=5 next(5)=2,下次下次p2第第4趟趟 目标目标 a c a b a a b a a b c a c a a b c
42、 模式模式 (a b)a a b c a c 7676用用KMPKMP算法实现的快速匹配算法算法实现的快速匹配算法int AString:fastFind(AString&pat,int k,int next)const/从 k 开始寻找 pat 在 this 串中匹配的位置。若找/到，函数返回 pat 在 this 串中开始位置，否则函/数返回-1。数组next 存放 pat 的nextj 值。int posP=0,posT=k;/两个串的扫描指针 int lengthP=pat.curLength;/模式串长度 int lengthT=curLength;/目标串长度 while(posP
43、 lengthP&posT lengthT)if(posP=-1|pat.chposP=chposT)posP+;posT+;/对应字符匹配7777else posP=nextposP;/求pat下趟比较位置 if(posP 0 时时 nj-1=k:当当 k=-1或或 j 0且且 pj-1=pk，则，则 nj=k+1。当当 pj-1 pk 且且 k -1，令，令 k=nk，并让，并让循循环直到条件不满足。环直到条件不满足。当当 pj-1 pk 且且 k=-1，则，则 nj=0。7979n以前面的例子说明：以前面的例子说明：j01234567Pabaabcacnext j-10011201j=4
44、k=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+1=18080对当前串计算对当前串计算nextnext特征向量的算法特征向量的算法void AString:getNext(int next)int j=0,k=-1,lengthP=curLength;next0=-1;while(j 0时，时，表的第一个表元素称为广义表表
45、的第一个表元素称为广义表 的的表头（表头（head），除此之外，其它表元素组），除此之外，其它表元素组成的表称为广义表的表尾（成的表称为广义表的表尾（tail）。）。8282广义表的特性广义表的特性n有次序性有次序性n有长度有长度n有深度有深度n可共享可共享n可递归可递归A()A长度为长度为0，深度为，深度为1B(6,2)B长度为长度为2，深度为，深度为1C(a,(5,3,x)C长度为长度为2，深度为，深度为2D(B,C,A)D长度为长度为3，深度为，深度为3E(B,D)E长度为？长度为？深度为？深度为？F(4,F)F长度为？长度为？深度为？深度为？8383广义表的表头与表尾广义表的表头与表尾
46、n广义表的第一个表元素即为该表的广义表的第一个表元素即为该表的表头表头，除，除表头元素外其他表元素组成的表即为该表的表头元素外其他表元素组成的表即为该表的表尾表尾。A()head(A)和和 tail(A)不存在不存在B(6,2)head(B)=6,tail(B)=(2)C(a,(5,3,x)head(C)=aD(B,C,A)tail(C)=(5,3,x)E(B,D)head(5,3,x)=(5,3,x)F(4,F)tail(5,3,x)=()8484u vax y zu vax y zu vax y zd8585广义表的表示广义表的表示list1=(a,b,c,d,e)list2=(a,(b,
47、c,(d,e,f),(),g),h,(r,s,t)ahbcgsrtfed list2alist1bdec 8686广义表结点定义广义表结点定义n结点类型结点类型 utype：=0,表头；表头；=1,原子数据；原子数据；=2,子表子表n信息信息info：utype=0时时,存放引用计数存放引用计数(ref)；utype=1时时,存放数据值存放数据值(value)；utype=2时时,存放指向子表表头的指针存放指向子表表头的指针(hlink)n尾指针尾指针tlink：utype=0时时,指向该表第一个指向该表第一个结点；结点；utype 0时时,指向同一层下一个结点指向同一层下一个结点 utype
48、 info tlink 8787广义表的存储表示广义表的存储表示B0 11 h20 022D 0 11 d1 e1 f 0 11 c2 0 12220 21 aBCA1 b 0 1 8888广义表的类定义广义表的类定义#include#include template struct Items/返回值的类结构定义 int utype;/结点类型0/1/2 union/联合int ref;/utype=0,存放引用计数T value;/utype=1,存放数值GenListNode*hlink;/utype=2,存放指向子表的指针 info;8989 Items():utype(0),info.
49、ref(0)/构造函数 Items(Items&R)/复制构造函数 utype=R.utype;info=R.info;template struct GenListNode /广义表结点类定义 int utype;/0/1/2 GenListNode*tlink;/同层下一结点指针 union/等价变量 int ref;/存放引用计数T value;/存放数值GenListNode*hlink;/存放子表指针9090 info;GenListNode()/构造函数 :utype(0),tlink(NULL),info.ref(0)GenListNode(GenListNode&R)/复制构造
50、函数 utype=R.utype;tlink=R.tlink;info=R.info;template class GenList /广义表类定义public:9191 Genlist();/构造函数 GenList();/析构函数 bool Head(Items&x);/x 返回表头元素 bool Tail(GenList<);/lt 返回表尾 GenListNode*First();/返回第一个元素 GenListNode*Next(GenListNode*elem);/返回表元素elem的直接后继元素 void Copy(const GenList&R);/广义表的复制 int Le
