? 作为抽象数据类型的数组
顺序表 (Sequential List)
多项式抽象数据类型
(Polynomial ADT)
稀疏矩阵 (Sparse Matrix)
字符串 (String)
作为抽象数据类型的数组
一维数组
一维数组的示例一维数组的特点
连续存储的线性聚集（别名 向量 ）
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
数组的定义和初始化
#include <iostream.h>
class szcl {
int e;
public:
szcl ( ) { e = 0; }
szcl ( int value ) { e = value; }
int get_value ( ) { return e; }
}
main ( ) {
szcl a1[3] = { 3,5,7 },*elem;
for ( int i=0,i<3,i++ )
cout << a1[i].get_value ( ) <<,\n”;
//打印静态数组
elem = &a1;
for ( int i=0,i<3,i++ ) {
cout << elem→ get_value( ) <<,\n”;
//打印动态数组
elem++;
}
return 0;
}
一维数组 (Array)类的定义
#include <iostream.h>
#include <stdlib.h>
template <class Type>
class Array {
Type *elements; //数组存放空间
int ArraySize; //当前长度
void getArray ( ); //建立数组空间
public:
Array(int Size=DefaultSize );
Array(const Array<Type>& x );
~Array( ) { delete [ ]elements;}
Array<Type> & operator =
( const Array<Type> & A );
Type& operato [ ] ( int i );
Array<Type> operator Type * ( ) const
{ return elements; }
int Length ( ) const
{ return ArraySize; }
void ReSize ( int sz );
}
template <class Type>
void Array<Type>::getArray ( ) {
//私有函数：创建数组存储空间
elements = new Type[ArraySize];
if ( elements == 0 )
cerr << "Memory Allocation Error"
<<endl;
}
一维数组公共操作的实现
template <class Type>
void Array<Type>::Array ( int sz ) {
//构造函数
if ( sz <= 0 ) {
cerr << "Invalid Array Size" << endl;
return;
}
ArraySize = sz;
getArray ( );
}
template <class Type> Array<Type>::
Array ( const Array<Type> & x ) {
//复制构造函数
int n = ArraySize = x.ArraySize;
elements = new Type[n];
if ( elements == 0 )
cerr << "Memory Allocation Error"
<< endl;
Type *srcptr = x.elements;
Type *destptr = elements;
while ( n-- ) * destptr++ = * srcptr++;
}
template <class Type>
Type & Array<Type>::operator [ ] ( int i ) {
//按数组名及下标 i，取数组元素的值
if ( i < 0 || i > ArraySize-1 )
cerr << "Index out of Range" << endl;
return element[i];
}
使用该函数于赋值语句
Position[i] = Position[i -1] + Number[i -1]
template <class Type>
void Array<Type>::Resize (int sz) {
if ( sz >= 0 && sz != ArraySize ) {
Type * newarray = new Type[sz];
if ( newarray == 0 )
cerr << "Memory Allocation Error" << endl;
int n = ( sz <= ArraySize )? sz,ArraySize;
Type *srcptr = elements;
Type *destptr = newarray;
while ( n-- ) * destptr++ = * srcptr++;
delete [ ] elements;
elements = newarray; ArraySize = sz;
}
}
二维数组 三维数组行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
数组的连续存储方式
一维数组
时 0,)(
时 0α,
)(
iliL O C
i
iL O C
1
LOC ( i ) = LOC ( i -1 ) + l =α+ i*l
二维数组
]][[]][[]][[]][[
]][[]][[]][[]][[
]][[]][[]][[]][[
]][[]][[]][[]][[
11211101
12221202
11211101
10201000
mnananana
maaaa
maaaa
maaaa
a
行优先 LOC ( j,k ) = j * m + k
n维数组
各维元素个数为 m1,m2,m3,…,m n
下标为 i1,i2,i3,…,i n 的数组元素的存储地址：
n
n
j
n
jk
kj
nnnn
nn
imi
imimmmi
mmmiiiiL O C
1
1 1
1432
32121
),,,(
顺序表 (Sequential List)
顺序表的定义和特点
定义 n（? 0） 个表项的有限序列
（ a1,a2,…,an）
ai是表项,n是表长度。
特点 顺序存取
遍历 逐项访问从前向后 从后向前 从两端向中间顺序表 (SeqList)类的定义
template <class Type> class SeqList {
Type *data; //顺序表存储数组
int MaxSize; //最大允许长度
int last; //当前最后元素下标
public:
SeqList ( int MaxSize = defaultSize );
~SeqList ( ) { delete [ ] data; }
int Length ( ) const { return last+1; }
int Find ( Type & x ) const;
int IsIn ( Type & x );
int Insert ( Type & x,int i );
int Remove ( Type & x );
int Next ( Type & x ) ;
int Prior ( Type & x ) ;
int IsEmpty ( ) { return last ==-1; }
int IsFull ( ) { return last == MaxSize-1; }
Type & Get ( int i ) {
return i < 0 || i > last？ NULL,data[i];
}
}
顺序表部分公共操作的实现
template <class Type>
SeqList<Type>::SeqList ( int sz ) {
//构造函数
if ( sz > 0 ) {
MaxSize = sz; last = -1;
data = new Type[MaxSize];
}
}
template <class Type>
int SeqList<Type>::Find ( Type & x ) const
{
//搜索函数：在表中从前向后顺序查找 x
int i = 0;
while ( i <= last && data[i] != x )
i++;
if ( i > last ) return -1;
else return i;
}
顺序搜索图示
x = 48 x = 50
搜索成功若搜索概率相等，则搜索不成功 数据比较 n 次
i
n
i
i cpACN
1
0
=
2
1
2
)(11
)2(1
1
1)(
1
=
1
0
nnn
n
n
n
i
n
ACN
n
i
22
1)(
1)(
1
0)1(
1
1
)(
1
1
=
0
nnn
n
n
n
in
n
AMN
n
i
表项的插入
template <class Type>
int SeqList<Type>::Insert ( Type & x,int i ){
//在表中第 i 个位置插入新元素 x
if ( i < 0 || i > last+1 || last == MaxSize-1 )
return 0; //插入不成功
else {
last++;
for ( int j=last; j>i; j-- )
data[j] = data[j -1];
data[i] = x;
return 1; //插入成功
}
}
表项的删除
1
0 2
1
2
1)(11)(1= n
i
nnn
n
in
n
A M N
template <class Type>
int SeqList<Type>::Remove ( Type & x ) {
//在表中删除已有元素 x
int i = Find (x); //在表中搜索 x
if ( i >= 0 ) {
last-- ;
for ( int j=i; j<=last; j++ )
data[j] = data[j+1];
return 1; //成功删除
}
return 0; //表中没有 x
}
顺序表的应用,集合的“并”运算
template <class Type>
void Union ( SeqList<Type> & LA,
SeqList<Type> & LB ) {
int n = LA.Length ( );
int m = LB.Length ( );
for ( int i=1; i<=m; i++ ) {
Type x = LB.Get(i); //在 LB中取一元素
int k = LA.Find (x); //在 LA中搜索它
if ( k == -1 ) //若未找到插入它
{ LA.Insert (n+1,x); n++; }
}
}
template <class Type>
void Intersection ( SeqList<Type> & LA,
SeqList<Type> & LB ) {
int n = LA.Length ( );
int m = LB.Length ( ); int i=1;
while ( i < n ) {
Type x = LA.Get(i); //在 LA中取一元素
int k = LB.Find (x); //在 LB中搜索它
if ( k == -1 ) { LA.Remove (i); n--; }
else i++; //未找到在 LA中删除它
}
}
顺序表的应用,集合的“交”运算
i
n
i
i
n
nn
xa
xaxaxaaxP
0
2
210
)(?
多项式 (Polynomial)
n阶多项式 Pn(x)有 n+1项。
系数 a0,a1,a2,…,an
指数 0,1,2,…,n。按升幂排列
class Polynomial {
public,
Polynomial ( ); //构造函数
int operator ! ( ); //判是否零多项式
Coefficient Coef (Exponent e);
Exponent LeadExp ( ); //返回最大指数
Polynomial Add (Polynomial poly);
Polynomial Mult (Polynomial poly);
float Eval ( float x); //求值
}
多项式 (Polynomial)的抽象数据类型
#include <iostream.h>
class power {
double x;
int e;
double mul;
public:
power (double val,int exp);
double get_power ( ) { return mul; }
};
创建 power类，计算 x的幂
power::power (double val,int exp) {
//按 val值计算乘幂
x = val; e = exp; mul = 1.0;
if (exp == 0 ) return;
for ( ; exp>0; exp--) mul = mul * x;
}
main ( ) {
power pwr ( 1.5,2 );
cout << pwr.get_power ( ) <<,\n”;
}
多项式的存储表示第一种,private,
(静态数 int degree;
组表示 ) float coef [maxDegree+1];
Pn(x)可以表示为,
pl.degree = n
pl.coef[i] = ai,0? i? n
第二种,private:
(动态数 int degree;
组表示 ) float * coef;
Polynomial::Polynomial (int sz) {
degree = sz;
coef = new float [degree + 1];
}
以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如
P101(x) = 3 + 5x50 - 14x101,不经济。
第三种,
class Polynomial;
class term { //多项式的项定义
friend Polynomial;
private,
float coef; //系数
int exp; //指数
};
class Polynomial { //多项式定义
public:
……
private:
static term termArray[MaxTerms]; //项数组
static int free; //当前空闲位置指针
// term Polynomial::termArray[MaxTerms];
// int Polynomial::free = 0;
int start,finish; //多项式始末位置
}
A(x) = 2.0x1000+1.8
B(x) = 1.2 + 51.3x50 + 3.7x101
两个多项式存放在 termArray中两个多项式的相加
结果多项式另存
扫描两个相加多项式，若都未检测完：
若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。
若当前被检测项指数不等，将指数小者加到结果多项式。
若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。
Polynomial Polynomial::Add ( Polynomial B ) {
Polynomial C;
int a = start; int b = B.start; C.start = free;
float c;
while ( a <= finish && b <= B.finish )
Switch ( compare ( termArray[a].exp,
termArray[b].exp) ) { //比较对应项指数
case?=?,//指数相等
c = termArray[a].coef +
termArray[b].coef;
if ( c ) NewTerm ( c,termArray[a].exp );
a++; b++; break;
case '>',
NewTerm ( termArray[b].coef,
termArray[b].exp );
b++; break;
case '<':
NewTerm ( termArray[a].coef,
termArray[a].exp );
a++;
}
for ( ; a<=finish; a++ ) //a未检测完时
NewTerm ( termArray[a].coef,
termArray[a].exp );
for ( ; b<=B.finish; b++ ) //b未检测完时
NewTerm ( termArray[b].coef,
termArray[b].exp );
C.finish = free-1;
return C;
}
在多项式中加入新的项
void Polynomial::NewTerm ( float c,int e ) {
//把一个新的项加到多项式 C(x)中
if ( free >= maxTerms ) {
cout << "Too many terms in polynomials”
<< endl;
return;
}
termArray[free].coef = c;
termArray[free].exp = e;
free++;
}
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
6776
稀疏矩阵 (Sparse Matrix)
行数 m = 6,列数 n = 7,非零元素个数 t = 6
稀疏矩阵 (SparseMatrix)的抽象数据类型
template <class Type>
class SparseMatrix {
int Rows,Cols,Terms; //行 /列 /非零元素数
Trituple<Type> smArray[MaxTerms];
public,//三元组表
SparseMatrix ( int MaxRow,int Maxcol );
SparseMatrix<Type> Transpose ( ); //转置
SparseMatrix<Type> //相加
Add ( SparseMatrix<Type> b );
SparseMatrix<Type> //相乘
Multiply ( SparseMatrix<Type> b );
}
三元组 (Trituple) 类的定义
template <class Type> class SparseMatrix;
template <class Type> class Trituple {
friend class SparseMatrix
private:
int row,col; //非零元素所在行号 /列号
Type value; //非零元素的值
}
rr aa ww cc oo ll vv aa ll uu ee
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
67
76
稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 00 33 22 22 [0] 00 44 99 11
[1] 00 66 11 55 [1] 11 11 11 11
[2] 11 11 11 11 [2] 22 55 22 88
[3] 11 55 11 77 [3] 33 00 22 22
[4] 22 33 -- 66 [4] 33 22 -- 66
[5] 33 55 33 99 [5] 55 11 11 77
[6] 44 00 99 11 [6] 55 33 33 99
[7] 55 22 22 88 [7] 66 00 11 66
稀疏矩阵转置算法思想
设矩阵列数为 Cols，对矩阵三元组表扫描 Cols次。第 k次检测列号为 k的项。
第 k次扫描找寻所有列号为 k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
设矩阵三元组表总共有 Terms项，其时间代价为 O ( Cols* Terms )。
若矩阵有 200行,200列,10,000个非零元素，总共有 2,000,000次处理。
稀疏矩阵的转置
template <class Type>
SparseMatrix<Type> SparseMatrix<Type>::
Transpose ( ) {
SparseMatrix<Type> b;
b.Rows = Cols; b.Cols = Rows;
b.Terms = Terms;
//转置矩阵的列数,行数和非零元素个数
if ( Terms > 0 ) {
int CurrentB = 0;
//转置三元组表存放指针
for ( int k=0; k<Cols; k++ )
for ( int i=0; i<Terms; i++ )
if ( smArray[i].col == k ) {
b.smArray[CurrentB].row = k;
b.smArray[CurrentB].col =
smArray[i].row;
b.smArray[CurrentB].value=
smArray[i].value;
CurrentB++;
}
}
return b;
}
快速转置算法
建立辅助数组 rowSize和 rowStart，记录矩阵转置后 各行非零元素个数 和 各行元素在转置三元组表中开始存放位置 。
扫描矩阵三元组表，根据某项的列号，
确定它转置后的行号，查 rowStart表，
按查到的位置直接将该项存入转置三元组表中。
转置时间代价为 O(max(Terms,Cols))。
若矩阵有 200列,10000个非零元素，总共需 10000次处理。
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] 语 义
r o w
S i z e
1 1 1 2 0 2 1 矩阵 A 各列非零元素个数
r o w
S t a r t
0 1 2 3 5 5 7 矩阵 B 各行开始存放位置
for ( int i=0; i<Cols; i++ ) rowSize[i] = 0;
for ( i=0; i<Terms; i++ )
rowSize[smArray[i].col]++;
rowStart[0] = 0;
for ( i=1; i <Cols; i++ )
rowStart[i] = rowStart[i-1]+rowSize[i-1];
稀疏矩阵的快速转置
template <class Type> SparseMatrix<Type>
SparseMatrix<Type>::FastTranspos ( ) {
int *rowSize = new int[Cols];
int *rowStart = new int[Cols];
SparseMatrix<Type> b;
b.Rows = Cols; b.Cols = Rows;
b.Terms = Terms;
if ( Terms > 0 ) {
for (int i=0; i<Cols; i++) rowSize[i] = 0;
for ( i=0; i<Terms; i++ )
rowSize[smArray[i].col]++;
rowStart[0] = 0;
for ( i=1; i <Cols; i++ )
rowStart[i] = rowStart[i-1]+rowSize[i-1];
for ( i=0; i<Terms; i++ ) {
int j = rowStart[smArray[i].col];
b.smArray[j].row = smArray[i].col;
b.smArray[j].col = smArray[i].row;
b.smArray[j].value = smArray[i].value;
rowStart[smArray[i].col]++;
}
}
delete [ ] rowSize; delete [ ] rowStart;
return b;
}
字符串 (String)
字符串是 n (? 0 ) 个字符的有限序列，
记作 S,,c1c2c3…c n”
其中,S是串名字
,c1c2c3…c n”是串值
ci是串中字符
n是串的长度。
const int maxLen = 128;
class String {
int curLen; //串的当前长度
char *ch; //串的存储数组
public:
String ( const String & ob);
String ( const 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; }
int operator ! ( )
const { return curLen == 0; }
String &operator = ( const String &ob );
String &operator += ( const String &ob );
char &operator [ ] ( int i );
int Find ( String pat ) const;
}
String::String ( const String &ob ) {
//复制构造函数,从已有串 ob复制
ch = new char[maxLen+1];
if ( !ch ) {
cout <<,Allocation Error\n”;
exit(1);
}
curLen = ob.curLen;
strcpy ( ch,ob.ch );
}
字符串部分操作的实现
String::String ( const char *init ) {
//复制构造函数,从已有字符数组 *init复制
ch = new char[maxLen+1];
if ( !ch ){
cout <<,Allocation Error\n”;
exit(1);
}
curLen = strlen (init);
strcpy ( ch,init );
}
String::String ( ) {
//构造函数：创建一个空串
ch = new char[maxLen+1];
if ( !ch ) {
cout <<,Allocation Error\n”;
exit(1);
}
curLen = 0;
ch[0] =?\0?;
}
提取子串的算法示例
pos+len -1 pos+len -1
curLen-1? curLen
String &String::
operator ( ) ( int pos,int len ) {
//从串中第 pos个位置起连续提取 len个字符
//形成子串返回
if ( pos < 0 || pos+len -1 >= maxLen
|| len < 0 ) {
temp.curLen = 0; //返回空串
temp.ch[0] = '\0';
}
else { //提取子串
String *temp = new String; //动态分配
if ( pos+len -1 >= curLen )
len = curLen - pos;
temp→ curLen = len; //子串长度
for ( int i=0,j=pos; i<len; i++,j++ )
temp→ ch[i] = ch[j]; //传送串数组
temp→ ch[len] =?\0?; //子串结束
}
return temp;
}
String &String::
operator = ( const String &ob ) {
//串赋值：从已有串 ob复制
if ( &ob != this ) {
delete [ ] ch;
ch = new char [maxLen+1]; //重新分配
if ( ! ch ) {
cerr <<,Out Of Memory!\n,; exit (1);
}
curLen = ob.curLen; //串复制
strcpy ( ch,ob.ch );
}
else cout <<,Attempted assignment of
a String to itself!\n”;
return *this;
}
char &String::operator [ ] ( int i ) {
//按串名提取串中第 i个字符
if ( i < 0 && i >= curLen ) {
cout <<,Out Of Boundary!\n,; exit (1) ;
}
return ch[i];
}
String &String:,//串连接
operator += ( const String &ob ) {
char * temp =ch; //暂存原串数组
curLen += ob.curLen; //串长度累加
ch = new char [maxLen+1];
if ( ! ch ) {
cerr <<,Out Of Memory!\n,; exit (1) ;
}
strcpy ( ch,temp ); //拷贝原串数组
strcat ( ch,ob.ch ); //连接 ob串数组
delete [ ] temp; return *this;
}
串的模式匹配
定义 在串中寻找子串（第一个字符）在串中的位置
词汇 在模式匹配中，子串称为 模式,串称为 目标 。
示例 目标 T,,Beijing”
模式 P,,jin”
匹配结果 = 3
第 1趟 T a b b a b a 穷举的模 式
P a b a 匹配过程第 2趟 T a b b a b a
P a b a
第 3趟 T a b b a b a
P a b a
第 4趟 T a b b a b a
P a b a
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 = pat.ch; }
//对应字符不相等，对齐目标的
//下一位置，继续比较
return -1;
}
目标 T t0 t1 t2 …… tm-1 … tn-1
模式 pat p0 p1 p2 …… pm-1
目标 T t0 t1 t2 …… tm-1 tm … tn-1
模式 pat p0 p1 …… pm-2 pm-1
目标 T t0 t1 …… ti ti+1…… ti+m-2 ti+m-1… tn-1
‖ ‖ ‖ ‖
模式 pat p0 p1 …… pm-2 pm-1
改进的模式匹配
穷举的模式匹配算法时间代价：
最坏情况比较 n-m+1趟，每 趟比较 m次，
总比较次数达 (n-m+1)*m
原因在于 每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。
改进的模式匹配 (KMP)算法的时间代价：
若每趟第一个不匹配，比较 n-m+1趟，
总比较次数最坏达 (n-m)+m = n
若每趟第 m个不匹配，总比较次数最坏亦达到 n
T t0 t1 … ts-1 ts ts+1 ts+2 … ts+j-1 ts+j ts+j+1 … tn-1
‖ ‖ ‖ ‖ ‖?
P p0 p1 p2 … pj-1 pj pj+1
则有 ts ts+1 ts+2 … ts+j = p0 p1 p2 … pj (1)
为使模式 P 与目标 T 匹配，必须满足
p0 p1 p2 … pj-1 … pm-1 = ts+1 ts+2 ts+3 … ts+j … ts+m
如果 p0 p1 … pj-1? p1 p2 … pj (2)
则立刻可以断定
p0 p1 … pj-1? ts+1 ts+2 … ts+j
下一趟必不匹配同样，若 p0 p1 … pj-2? p2 p3 … pj
则再下一趟也不匹配，因为有
p0 p1 … pj-2? ts+2 ts+3 … ts+j
直到对于某一个,k”值，使得
p0 p1 … pk+1? pj-k-1 pj-k … pj
且 p0 p1 … pk = pj-k pj-k+1 … pj
则 p0 p1 … pk = ts+j-k ts+j-k+1 … ts+j
‖ ‖ ‖
pj-k pj-k+1 … pj
k 的确定方法当比较到模式第 j 个字符失配时,k 的值 与模式的前 j 个字符有关，与目标无关。
利用失效函数 f (j)可描述。
利用失效函数 f (j) 的匹配处理如果 j = 0，则目标指针加 1，模式指针回到 p0。
如果 j > 0，则目标指针不变，模式指针回到 pf(j-1)+1。
若设 模式 P = p0 p1… pm-2 pm-1
1,-
,
,<0
,
=)(
1
10
.其它情况的最大整数且使得当
jkjkj
k
ppp
pppjk
k
jf?
j 0 1 2 3 4 5 6 7
PP a b a a b c a c
ff (( jj )) -- 11 -- 11 00 00 11 -- 11 00 -- 11
示例,确定失效函数 f (j)
运用 KMP算法的匹配过程第 1趟 目标 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? j = f (j-1)+1 = 0
第 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 = 5? j = f (j-1)+1= 2
第 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
int String,,fastFind ( String pat ) const {
//带失效函数的 KMP匹配算法
int posP = 0,posT = 0;
int lengthP = pat.curLen,lengthT = curLen;
while ( posP < lengthP && posT < lengthT )
if ( pat.ch[posP] == ch[posT] ) {
posP++; posT++; //相等继续比较
}
else if ( posP == 0 ) posT++; //不相等
else posP = pat.f [posP-1]+1;
if ( posP < lengthP ) return -1;
else return posT - lengthP;
}
计算失效函数 f [ j ] 的方法首先确定 f [0] = -1，再利用 f [ j]求 f [ j+1]。
其中,f (1)[ j ] = f [ j ],
f (m)[ j ] = f [f (m -1)[ j ]]
,
,][
][
01
1
1
1][)(
j
k
pp
jf
jf
j
( k )
jfm
否则或的最小正整数可找到令
j 0 1 2 3 4 5 6 7 8
PP a b a a b c a b a
ff [[ jj ]] - 1 - 1 0 0 1 - 1 0 1 2
f [0] = -1;
j = 1时,f [0]+1 = 0,p0? p1,f [1] = -1;
j = 2时,f [1]+1 = 0,p0 = p2,f [2] = f [1]+1 = 0;
j = 3时,f [2]+1 = 1,p1? p3,
f [1]+1= 0,p0 = p3,f [3] = f [1]+1 = 0;
j = 4时,f [3]+1 = 1,p1 = p4,f [4] = f [3]+1 = 1;
void String::fail ( ) {
//计算失效函数
int lengthP = curLen;
f [0] = -1; //直接赋值
for ( int j=1; j<lengthP; j++ ) { //依次求 f [j]
int i = f [j-1];
while ( *(ch+j) != *(ch+i+1) && i >= 0 )
i = f [i]; //递推
if ( *(ch+j) == *(ch+i+1) ) f [j] = i+1;
else f [j] = -1;
}
}
顺序表 (Sequential List)
多项式抽象数据类型
(Polynomial ADT)
稀疏矩阵 (Sparse Matrix)
字符串 (String)
作为抽象数据类型的数组
一维数组
一维数组的示例一维数组的特点
连续存储的线性聚集（别名 向量 ）
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
数组的定义和初始化
#include <iostream.h>
class szcl {
int e;
public:
szcl ( ) { e = 0; }
szcl ( int value ) { e = value; }
int get_value ( ) { return e; }
}
main ( ) {
szcl a1[3] = { 3,5,7 },*elem;
for ( int i=0,i<3,i++ )
cout << a1[i].get_value ( ) <<,\n”;
//打印静态数组
elem = &a1;
for ( int i=0,i<3,i++ ) {
cout << elem→ get_value( ) <<,\n”;
//打印动态数组
elem++;
}
return 0;
}
一维数组 (Array)类的定义
#include <iostream.h>
#include <stdlib.h>
template <class Type>
class Array {
Type *elements; //数组存放空间
int ArraySize; //当前长度
void getArray ( ); //建立数组空间
public:
Array(int Size=DefaultSize );
Array(const Array<Type>& x );
~Array( ) { delete [ ]elements;}
Array<Type> & operator =
( const Array<Type> & A );
Type& operato [ ] ( int i );
Array<Type> operator Type * ( ) const
{ return elements; }
int Length ( ) const
{ return ArraySize; }
void ReSize ( int sz );
}
template <class Type>
void Array<Type>::getArray ( ) {
//私有函数：创建数组存储空间
elements = new Type[ArraySize];
if ( elements == 0 )
cerr << "Memory Allocation Error"
<<endl;
}
一维数组公共操作的实现
template <class Type>
void Array<Type>::Array ( int sz ) {
//构造函数
if ( sz <= 0 ) {
cerr << "Invalid Array Size" << endl;
return;
}
ArraySize = sz;
getArray ( );
}
template <class Type> Array<Type>::
Array ( const Array<Type> & x ) {
//复制构造函数
int n = ArraySize = x.ArraySize;
elements = new Type[n];
if ( elements == 0 )
cerr << "Memory Allocation Error"
<< endl;
Type *srcptr = x.elements;
Type *destptr = elements;
while ( n-- ) * destptr++ = * srcptr++;
}
template <class Type>
Type & Array<Type>::operator [ ] ( int i ) {
//按数组名及下标 i，取数组元素的值
if ( i < 0 || i > ArraySize-1 )
cerr << "Index out of Range" << endl;
return element[i];
}
使用该函数于赋值语句
Position[i] = Position[i -1] + Number[i -1]
template <class Type>
void Array<Type>::Resize (int sz) {
if ( sz >= 0 && sz != ArraySize ) {
Type * newarray = new Type[sz];
if ( newarray == 0 )
cerr << "Memory Allocation Error" << endl;
int n = ( sz <= ArraySize )? sz,ArraySize;
Type *srcptr = elements;
Type *destptr = newarray;
while ( n-- ) * destptr++ = * srcptr++;
delete [ ] elements;
elements = newarray; ArraySize = sz;
}
}
二维数组 三维数组行向量 下标 i 页向量 下标 i
列向量 下标 j 行向量 下标 j
列向量 下标 k
数组的连续存储方式
一维数组
时 0,)(
时 0α,
)(
iliL O C
i
iL O C
1
LOC ( i ) = LOC ( i -1 ) + l =α+ i*l
二维数组
]][[]][[]][[]][[
]][[]][[]][[]][[
]][[]][[]][[]][[
]][[]][[]][[]][[
11211101
12221202
11211101
10201000
mnananana
maaaa
maaaa
maaaa
a
行优先 LOC ( j,k ) = j * m + k
n维数组
各维元素个数为 m1,m2,m3,…,m n
下标为 i1,i2,i3,…,i n 的数组元素的存储地址：
n
n
j
n
jk
kj
nnnn
nn
imi
imimmmi
mmmiiiiL O C
1
1 1
1432
32121
),,,(
顺序表 (Sequential List)
顺序表的定义和特点
定义 n（? 0） 个表项的有限序列
（ a1,a2,…,an）
ai是表项,n是表长度。
特点 顺序存取
遍历 逐项访问从前向后 从后向前 从两端向中间顺序表 (SeqList)类的定义
template <class Type> class SeqList {
Type *data; //顺序表存储数组
int MaxSize; //最大允许长度
int last; //当前最后元素下标
public:
SeqList ( int MaxSize = defaultSize );
~SeqList ( ) { delete [ ] data; }
int Length ( ) const { return last+1; }
int Find ( Type & x ) const;
int IsIn ( Type & x );
int Insert ( Type & x,int i );
int Remove ( Type & x );
int Next ( Type & x ) ;
int Prior ( Type & x ) ;
int IsEmpty ( ) { return last ==-1; }
int IsFull ( ) { return last == MaxSize-1; }
Type & Get ( int i ) {
return i < 0 || i > last？ NULL,data[i];
}
}
顺序表部分公共操作的实现
template <class Type>
SeqList<Type>::SeqList ( int sz ) {
//构造函数
if ( sz > 0 ) {
MaxSize = sz; last = -1;
data = new Type[MaxSize];
}
}
template <class Type>
int SeqList<Type>::Find ( Type & x ) const
{
//搜索函数：在表中从前向后顺序查找 x
int i = 0;
while ( i <= last && data[i] != x )
i++;
if ( i > last ) return -1;
else return i;
}
顺序搜索图示
x = 48 x = 50
搜索成功若搜索概率相等，则搜索不成功 数据比较 n 次
i
n
i
i cpACN
1
0
=
2
1
2
)(11
)2(1
1
1)(
1
=
1
0
nnn
n
n
n
i
n
ACN
n
i
22
1)(
1)(
1
0)1(
1
1
)(
1
1
=
0
nnn
n
n
n
in
n
AMN
n
i
表项的插入
template <class Type>
int SeqList<Type>::Insert ( Type & x,int i ){
//在表中第 i 个位置插入新元素 x
if ( i < 0 || i > last+1 || last == MaxSize-1 )
return 0; //插入不成功
else {
last++;
for ( int j=last; j>i; j-- )
data[j] = data[j -1];
data[i] = x;
return 1; //插入成功
}
}
表项的删除
1
0 2
1
2
1)(11)(1= n
i
nnn
n
in
n
A M N
template <class Type>
int SeqList<Type>::Remove ( Type & x ) {
//在表中删除已有元素 x
int i = Find (x); //在表中搜索 x
if ( i >= 0 ) {
last-- ;
for ( int j=i; j<=last; j++ )
data[j] = data[j+1];
return 1; //成功删除
}
return 0; //表中没有 x
}
顺序表的应用,集合的“并”运算
template <class Type>
void Union ( SeqList<Type> & LA,
SeqList<Type> & LB ) {
int n = LA.Length ( );
int m = LB.Length ( );
for ( int i=1; i<=m; i++ ) {
Type x = LB.Get(i); //在 LB中取一元素
int k = LA.Find (x); //在 LA中搜索它
if ( k == -1 ) //若未找到插入它
{ LA.Insert (n+1,x); n++; }
}
}
template <class Type>
void Intersection ( SeqList<Type> & LA,
SeqList<Type> & LB ) {
int n = LA.Length ( );
int m = LB.Length ( ); int i=1;
while ( i < n ) {
Type x = LA.Get(i); //在 LA中取一元素
int k = LB.Find (x); //在 LB中搜索它
if ( k == -1 ) { LA.Remove (i); n--; }
else i++; //未找到在 LA中删除它
}
}
顺序表的应用,集合的“交”运算
i
n
i
i
n
nn
xa
xaxaxaaxP
0
2
210
)(?
多项式 (Polynomial)
n阶多项式 Pn(x)有 n+1项。
系数 a0,a1,a2,…,an
指数 0,1,2,…,n。按升幂排列
class Polynomial {
public,
Polynomial ( ); //构造函数
int operator ! ( ); //判是否零多项式
Coefficient Coef (Exponent e);
Exponent LeadExp ( ); //返回最大指数
Polynomial Add (Polynomial poly);
Polynomial Mult (Polynomial poly);
float Eval ( float x); //求值
}
多项式 (Polynomial)的抽象数据类型
#include <iostream.h>
class power {
double x;
int e;
double mul;
public:
power (double val,int exp);
double get_power ( ) { return mul; }
};
创建 power类，计算 x的幂
power::power (double val,int exp) {
//按 val值计算乘幂
x = val; e = exp; mul = 1.0;
if (exp == 0 ) return;
for ( ; exp>0; exp--) mul = mul * x;
}
main ( ) {
power pwr ( 1.5,2 );
cout << pwr.get_power ( ) <<,\n”;
}
多项式的存储表示第一种,private,
(静态数 int degree;
组表示 ) float coef [maxDegree+1];
Pn(x)可以表示为,
pl.degree = n
pl.coef[i] = ai,0? i? n
第二种,private:
(动态数 int degree;
组表示 ) float * coef;
Polynomial::Polynomial (int sz) {
degree = sz;
coef = new float [degree + 1];
}
以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如
P101(x) = 3 + 5x50 - 14x101,不经济。
第三种,
class Polynomial;
class term { //多项式的项定义
friend Polynomial;
private,
float coef; //系数
int exp; //指数
};
class Polynomial { //多项式定义
public:
……
private:
static term termArray[MaxTerms]; //项数组
static int free; //当前空闲位置指针
// term Polynomial::termArray[MaxTerms];
// int Polynomial::free = 0;
int start,finish; //多项式始末位置
}
A(x) = 2.0x1000+1.8
B(x) = 1.2 + 51.3x50 + 3.7x101
两个多项式存放在 termArray中两个多项式的相加
结果多项式另存
扫描两个相加多项式，若都未检测完：
若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。
若当前被检测项指数不等，将指数小者加到结果多项式。
若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。
Polynomial Polynomial::Add ( Polynomial B ) {
Polynomial C;
int a = start; int b = B.start; C.start = free;
float c;
while ( a <= finish && b <= B.finish )
Switch ( compare ( termArray[a].exp,
termArray[b].exp) ) { //比较对应项指数
case?=?,//指数相等
c = termArray[a].coef +
termArray[b].coef;
if ( c ) NewTerm ( c,termArray[a].exp );
a++; b++; break;
case '>',
NewTerm ( termArray[b].coef,
termArray[b].exp );
b++; break;
case '<':
NewTerm ( termArray[a].coef,
termArray[a].exp );
a++;
}
for ( ; a<=finish; a++ ) //a未检测完时
NewTerm ( termArray[a].coef,
termArray[a].exp );
for ( ; b<=B.finish; b++ ) //b未检测完时
NewTerm ( termArray[b].coef,
termArray[b].exp );
C.finish = free-1;
return C;
}
在多项式中加入新的项
void Polynomial::NewTerm ( float c,int e ) {
//把一个新的项加到多项式 C(x)中
if ( free >= maxTerms ) {
cout << "Too many terms in polynomials”
<< endl;
return;
}
termArray[free].coef = c;
termArray[free].exp = e;
free++;
}
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
6776
稀疏矩阵 (Sparse Matrix)
行数 m = 6,列数 n = 7,非零元素个数 t = 6
稀疏矩阵 (SparseMatrix)的抽象数据类型
template <class Type>
class SparseMatrix {
int Rows,Cols,Terms; //行 /列 /非零元素数
Trituple<Type> smArray[MaxTerms];
public,//三元组表
SparseMatrix ( int MaxRow,int Maxcol );
SparseMatrix<Type> Transpose ( ); //转置
SparseMatrix<Type> //相加
Add ( SparseMatrix<Type> b );
SparseMatrix<Type> //相乘
Multiply ( SparseMatrix<Type> b );
}
三元组 (Trituple) 类的定义
template <class Type> class SparseMatrix;
template <class Type> class Trituple {
friend class SparseMatrix
private:
int row,col; //非零元素所在行号 /列号
Type value; //非零元素的值
}
rr aa ww cc oo ll vv aa ll uu ee
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
67
76
稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 00 33 22 22 [0] 00 44 99 11
[1] 00 66 11 55 [1] 11 11 11 11
[2] 11 11 11 11 [2] 22 55 22 88
[3] 11 55 11 77 [3] 33 00 22 22
[4] 22 33 -- 66 [4] 33 22 -- 66
[5] 33 55 33 99 [5] 55 11 11 77
[6] 44 00 99 11 [6] 55 33 33 99
[7] 55 22 22 88 [7] 66 00 11 66
稀疏矩阵转置算法思想
设矩阵列数为 Cols，对矩阵三元组表扫描 Cols次。第 k次检测列号为 k的项。
第 k次扫描找寻所有列号为 k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
设矩阵三元组表总共有 Terms项，其时间代价为 O ( Cols* Terms )。
若矩阵有 200行,200列,10,000个非零元素，总共有 2,000,000次处理。
稀疏矩阵的转置
template <class Type>
SparseMatrix<Type> SparseMatrix<Type>::
Transpose ( ) {
SparseMatrix<Type> b;
b.Rows = Cols; b.Cols = Rows;
b.Terms = Terms;
//转置矩阵的列数,行数和非零元素个数
if ( Terms > 0 ) {
int CurrentB = 0;
//转置三元组表存放指针
for ( int k=0; k<Cols; k++ )
for ( int i=0; i<Terms; i++ )
if ( smArray[i].col == k ) {
b.smArray[CurrentB].row = k;
b.smArray[CurrentB].col =
smArray[i].row;
b.smArray[CurrentB].value=
smArray[i].value;
CurrentB++;
}
}
return b;
}
快速转置算法
建立辅助数组 rowSize和 rowStart，记录矩阵转置后 各行非零元素个数 和 各行元素在转置三元组表中开始存放位置 。
扫描矩阵三元组表，根据某项的列号，
确定它转置后的行号，查 rowStart表，
按查到的位置直接将该项存入转置三元组表中。
转置时间代价为 O(max(Terms,Cols))。
若矩阵有 200列,10000个非零元素，总共需 10000次处理。
[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] 语 义
r o w
S i z e
1 1 1 2 0 2 1 矩阵 A 各列非零元素个数
r o w
S t a r t
0 1 2 3 5 5 7 矩阵 B 各行开始存放位置
for ( int i=0; i<Cols; i++ ) rowSize[i] = 0;
for ( i=0; i<Terms; i++ )
rowSize[smArray[i].col]++;
rowStart[0] = 0;
for ( i=1; i <Cols; i++ )
rowStart[i] = rowStart[i-1]+rowSize[i-1];
稀疏矩阵的快速转置
template <class Type> SparseMatrix<Type>
SparseMatrix<Type>::FastTranspos ( ) {
int *rowSize = new int[Cols];
int *rowStart = new int[Cols];
SparseMatrix<Type> b;
b.Rows = Cols; b.Cols = Rows;
b.Terms = Terms;
if ( Terms > 0 ) {
for (int i=0; i<Cols; i++) rowSize[i] = 0;
for ( i=0; i<Terms; i++ )
rowSize[smArray[i].col]++;
rowStart[0] = 0;
for ( i=1; i <Cols; i++ )
rowStart[i] = rowStart[i-1]+rowSize[i-1];
for ( i=0; i<Terms; i++ ) {
int j = rowStart[smArray[i].col];
b.smArray[j].row = smArray[i].col;
b.smArray[j].col = smArray[i].row;
b.smArray[j].value = smArray[i].value;
rowStart[smArray[i].col]++;
}
}
delete [ ] rowSize; delete [ ] rowStart;
return b;
}
字符串 (String)
字符串是 n (? 0 ) 个字符的有限序列，
记作 S,,c1c2c3…c n”
其中,S是串名字
,c1c2c3…c n”是串值
ci是串中字符
n是串的长度。
const int maxLen = 128;
class String {
int curLen; //串的当前长度
char *ch; //串的存储数组
public:
String ( const String & ob);
String ( const 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; }
int operator ! ( )
const { return curLen == 0; }
String &operator = ( const String &ob );
String &operator += ( const String &ob );
char &operator [ ] ( int i );
int Find ( String pat ) const;
}
String::String ( const String &ob ) {
//复制构造函数,从已有串 ob复制
ch = new char[maxLen+1];
if ( !ch ) {
cout <<,Allocation Error\n”;
exit(1);
}
curLen = ob.curLen;
strcpy ( ch,ob.ch );
}
字符串部分操作的实现
String::String ( const char *init ) {
//复制构造函数,从已有字符数组 *init复制
ch = new char[maxLen+1];
if ( !ch ){
cout <<,Allocation Error\n”;
exit(1);
}
curLen = strlen (init);
strcpy ( ch,init );
}
String::String ( ) {
//构造函数：创建一个空串
ch = new char[maxLen+1];
if ( !ch ) {
cout <<,Allocation Error\n”;
exit(1);
}
curLen = 0;
ch[0] =?\0?;
}
提取子串的算法示例
pos+len -1 pos+len -1
curLen-1? curLen
String &String::
operator ( ) ( int pos,int len ) {
//从串中第 pos个位置起连续提取 len个字符
//形成子串返回
if ( pos < 0 || pos+len -1 >= maxLen
|| len < 0 ) {
temp.curLen = 0; //返回空串
temp.ch[0] = '\0';
}
else { //提取子串
String *temp = new String; //动态分配
if ( pos+len -1 >= curLen )
len = curLen - pos;
temp→ curLen = len; //子串长度
for ( int i=0,j=pos; i<len; i++,j++ )
temp→ ch[i] = ch[j]; //传送串数组
temp→ ch[len] =?\0?; //子串结束
}
return temp;
}
String &String::
operator = ( const String &ob ) {
//串赋值：从已有串 ob复制
if ( &ob != this ) {
delete [ ] ch;
ch = new char [maxLen+1]; //重新分配
if ( ! ch ) {
cerr <<,Out Of Memory!\n,; exit (1);
}
curLen = ob.curLen; //串复制
strcpy ( ch,ob.ch );
}
else cout <<,Attempted assignment of
a String to itself!\n”;
return *this;
}
char &String::operator [ ] ( int i ) {
//按串名提取串中第 i个字符
if ( i < 0 && i >= curLen ) {
cout <<,Out Of Boundary!\n,; exit (1) ;
}
return ch[i];
}
String &String:,//串连接
operator += ( const String &ob ) {
char * temp =ch; //暂存原串数组
curLen += ob.curLen; //串长度累加
ch = new char [maxLen+1];
if ( ! ch ) {
cerr <<,Out Of Memory!\n,; exit (1) ;
}
strcpy ( ch,temp ); //拷贝原串数组
strcat ( ch,ob.ch ); //连接 ob串数组
delete [ ] temp; return *this;
}
串的模式匹配
定义 在串中寻找子串（第一个字符）在串中的位置
词汇 在模式匹配中，子串称为 模式,串称为 目标 。
示例 目标 T,,Beijing”
模式 P,,jin”
匹配结果 = 3
第 1趟 T a b b a b a 穷举的模 式
P a b a 匹配过程第 2趟 T a b b a b a
P a b a
第 3趟 T a b b a b a
P a b a
第 4趟 T a b b a b a
P a b a
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 = pat.ch; }
//对应字符不相等，对齐目标的
//下一位置，继续比较
return -1;
}
目标 T t0 t1 t2 …… tm-1 … tn-1
模式 pat p0 p1 p2 …… pm-1
目标 T t0 t1 t2 …… tm-1 tm … tn-1
模式 pat p0 p1 …… pm-2 pm-1
目标 T t0 t1 …… ti ti+1…… ti+m-2 ti+m-1… tn-1
‖ ‖ ‖ ‖
模式 pat p0 p1 …… pm-2 pm-1
改进的模式匹配
穷举的模式匹配算法时间代价：
最坏情况比较 n-m+1趟，每 趟比较 m次，
总比较次数达 (n-m+1)*m
原因在于 每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。
改进的模式匹配 (KMP)算法的时间代价：
若每趟第一个不匹配，比较 n-m+1趟，
总比较次数最坏达 (n-m)+m = n
若每趟第 m个不匹配，总比较次数最坏亦达到 n
T t0 t1 … ts-1 ts ts+1 ts+2 … ts+j-1 ts+j ts+j+1 … tn-1
‖ ‖ ‖ ‖ ‖?
P p0 p1 p2 … pj-1 pj pj+1
则有 ts ts+1 ts+2 … ts+j = p0 p1 p2 … pj (1)
为使模式 P 与目标 T 匹配，必须满足
p0 p1 p2 … pj-1 … pm-1 = ts+1 ts+2 ts+3 … ts+j … ts+m
如果 p0 p1 … pj-1? p1 p2 … pj (2)
则立刻可以断定
p0 p1 … pj-1? ts+1 ts+2 … ts+j
下一趟必不匹配同样，若 p0 p1 … pj-2? p2 p3 … pj
则再下一趟也不匹配，因为有
p0 p1 … pj-2? ts+2 ts+3 … ts+j
直到对于某一个,k”值，使得
p0 p1 … pk+1? pj-k-1 pj-k … pj
且 p0 p1 … pk = pj-k pj-k+1 … pj
则 p0 p1 … pk = ts+j-k ts+j-k+1 … ts+j
‖ ‖ ‖
pj-k pj-k+1 … pj
k 的确定方法当比较到模式第 j 个字符失配时,k 的值 与模式的前 j 个字符有关，与目标无关。
利用失效函数 f (j)可描述。
利用失效函数 f (j) 的匹配处理如果 j = 0，则目标指针加 1，模式指针回到 p0。
如果 j > 0，则目标指针不变，模式指针回到 pf(j-1)+1。
若设 模式 P = p0 p1… pm-2 pm-1
1,-
,
,<0
,
=)(
1
10
.其它情况的最大整数且使得当
jkjkj
k
ppp
pppjk
k
jf?
j 0 1 2 3 4 5 6 7
PP a b a a b c a c
ff (( jj )) -- 11 -- 11 00 00 11 -- 11 00 -- 11
示例,确定失效函数 f (j)
运用 KMP算法的匹配过程第 1趟 目标 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? j = f (j-1)+1 = 0
第 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 = 5? j = f (j-1)+1= 2
第 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
int String,,fastFind ( String pat ) const {
//带失效函数的 KMP匹配算法
int posP = 0,posT = 0;
int lengthP = pat.curLen,lengthT = curLen;
while ( posP < lengthP && posT < lengthT )
if ( pat.ch[posP] == ch[posT] ) {
posP++; posT++; //相等继续比较
}
else if ( posP == 0 ) posT++; //不相等
else posP = pat.f [posP-1]+1;
if ( posP < lengthP ) return -1;
else return posT - lengthP;
}
计算失效函数 f [ j ] 的方法首先确定 f [0] = -1，再利用 f [ j]求 f [ j+1]。
其中,f (1)[ j ] = f [ j ],
f (m)[ j ] = f [f (m -1)[ j ]]
,
,][
][
01
1
1
1][)(
j
k
pp
jf
jf
j
( k )
jfm
否则或的最小正整数可找到令
j 0 1 2 3 4 5 6 7 8
PP a b a a b c a b a
ff [[ jj ]] - 1 - 1 0 0 1 - 1 0 1 2
f [0] = -1;
j = 1时,f [0]+1 = 0,p0? p1,f [1] = -1;
j = 2时,f [1]+1 = 0,p0 = p2,f [2] = f [1]+1 = 0;
j = 3时,f [2]+1 = 1,p1? p3,
f [1]+1= 0,p0 = p3,f [3] = f [1]+1 = 0;
j = 4时,f [3]+1 = 1,p1 = p4,f [4] = f [3]+1 = 1;
void String::fail ( ) {
//计算失效函数
int lengthP = curLen;
f [0] = -1; //直接赋值
for ( int j=1; j<lengthP; j++ ) { //依次求 f [j]
int i = f [j-1];
while ( *(ch+j) != *(ch+i+1) && i >= 0 )
i = f [i]; //递推
if ( *(ch+j) == *(ch+i+1) ) f [j] = i+1;
else f [j] = -1;
}
}
