03 第3章 数组和字符串.pptx

第1页：第三章数组和字符串目录封面

第三章数组和字符串3.1数组3.2矩阵3.3字符串

第2页：本节内容目录

3.1数组3.1.1数组的存储和寻址3.1.2自定义数组类3.1.3动态数组

第3页：一维数组是若干个元素的有限序列

一维数组是若干个元素的有限序列。元素本身就是一个数据结构。一维数组的元素必须具有相同的类型，每个数组元素都占据相同大小的存储空间。

第4页：一维数组采用顺序

一维数组采用顺序存储结构。每个元素都通过一个下标来指定，故一个一维数组对应一个下标函数。一维数组A[n]，每个数组元素占一个存储单元（不妨设为C个连续字节）.数组元素A[0]的首地址Loc(A[0])，则对于0≤i≤n-1，有：Loc(A[i])=Loc(A[0])+i*C

第5页：高维数组可转化为一维数组计算元素的地址

高维数组可转化为一维数组计算元素的地址。高维数组有两种存放次序：按行优先顺序和按列优先顺序。BASIC、PASCAL、C/C++等程序设计语言中，数组按行优先顺序存放；FORTRAN语言、Matlab语言中，数组则按列优先顺序存放。

第6页：按行优先顺序

按行优先顺序，就是将数组元素按行向量的顺序存储，第i+1个行向量存储在第i个行向量之后。二维数组的行优先存储[例]intx[2][3]x[0][0]x[0][1]x[0][2]x[1][0] x[1][1] x[1][2]

第7页：按行优先顺序存放存储分配顺序

按行优先顺序存放存储分配顺序为：x[0][0]→x[0][1]→x[0][2]→x[1][0]→x[1][1]→x[1][2]x[0][0]x[0][1]x[0][2]x[1][0]x[1][1]x[1][2]

第8页：二维数组

二维数组可以看作是一种特殊的一维数组。[例]floata[3][4];b[0]a[0][0]a[0][1]a[0][2]a[0][3]b-b[1]a[1][0]a[1][1]a[1][2]a[1][3]b[2]a[2][0]a[2][1]a[2][2]a[2][3]

第9页：二维数组（续2）

二维数组a[m][n]中元素a[i][j]的地址：Loc(a[i][j])=Loc(b[i])+j×CLoc(b[i])=Loc(b[0])+i×C′//C′=n×CLoc(a[i][j])=Loc(a[0][0])+i×n×C+j×C=Loc(a[0][0])+(i×n+j)×Cb[0]a[0][0] a[0][1] a[0][2] a[0][3]b-b[1] a[1][0] a[1][1] a[1][2] a[1][3]b[2] a[2][0] a[2][1] a[2][2] a[2][3]

第10页：二维数组（续）

[例]floata[3][4]Loc(a[1][2])=Loc(a[0][0])+(i×n+j)×C=Loc(a[0][0])+(1×4+2)×4=Loc(a[0][0])+24

第11页：多维数组元素

多维数组元素在内存中的排序顺序为：第一维的下标变化最慢，最右边的维下标变化最快。[例]floata[2][3][4]三维数组a[0][0][0]→a[0][0][1]→a[0][0][2]→a[0][0][3]→a[0][1][0]→a[0][1][1]→a[0][1][2]→a[0][1][3]→a[0][2][0]→a[0][2][1]→a[0][2][2]→a[0][2][3]→a[1][0][0]→a[1][0][1]→a[1][0][2]→a[1][0][3]a[1][1][0]→a[1][1][1]→a[1][1][2]→a[1][1][3]a[1][2][0]→a[1][2][1]→a[1][2][2]→a[1][2][3]

第12页：三维数组

三维数组a[m][n][p]中元素a[i][j][k]地址计算公式为：Loc(a[i][j][k])=Loc(a[0][0][0])+(i×n×p+j×p+k)×C

第13页：三维数组（续）

[例]floatD[3][3][4]Loc(D[1][2][2])=Loc(D[0][0][0])+(i×n×p+j×p+k)×C= Loc(D[0][0][0])+ (1×3×4+2×4+2)×4= Loc(D[0][0][0])+ 88

第14页：多维数组

多维数组a[m1][m2]…[mn]中a[i1][i2]…[in]的存储地址

第15页：按列优先顺序

按列优先顺序，就是将数组元素按列向量的顺序存储，第i+1个列向量存储在第i个列向量之后。二维数组x[2][3]的按列优先存储x[0][0]x[0][1]x[0][2]x[1][0] x[1][1] x[1][2]x[0][0]x[1][0]x[0][1]x[1][1]x[0][2]x[1][2]

第16页：何计算按列优先顺序存储

如何计算按列优先顺序存储的数组元素地址？请同学们自己推导。

第17页：本节内容目录

3.1数组3.1.1数组的存储和寻址3.1.2自定义一维数组类3.1.3动态数组

第18页：自定义一维数组类型

自定义一维数组类数组类型是高级程序设计语言所提供的基本数据类型之一，可定义一组相同类型的元素。但是直接创建的数组存在着一些问题，诸如：——无法执行一些基本数组运算，如数组加法和数组减法等操作；——越界索引保护问题，即检查数组的下标索引值是否在0到arraysize-1范围内。一些高级程序设计语言对越界索引访问并不一定会产生异常，没有越界索引保护会直接给程序调试带来难以预料的困难。

为了弥补这些缺陷，可以自定义一个数组类。

第19页：一维数组类

一维数组类Array的类定义template <class T>class Array {private:int size ;

第20页：返回数组大小

intArraySize ( ){ return size ; }//返回数组大小T &operator []( int i ) const ;//重载下标符号[]Array <T> &operator =( const Array <T> & v )//重载赋值运算符=Array <T>operator +( ) const ;//重载一元加法运算符+Array <T>operator +( const Array <T> & v ) const ;//重载二元加法运算符+Array <T>operator-( ) const ;//重载一元减法运算符-Array <T>operator-( const Array <T> & v ) const ;//重载二元减法运算符-}；

第21页：本节内容目录

3.1数组3.1.1数组的存储和寻址3.1.2自定义数组类3.1.3动态数组

第22页：动态数组类

动态数组动态数组类Array的定义template <class T>class Array{ private：int FSize;

第23页：复制构造函数

public：Array( int sz=50 );Array( const Array <T>& x );

第24页：修改数组的大小

template <class T>

第25页：保留原数组中元素

int n=(newSize <= Fsize?newSsize:Fsize);for(int i=0;i<n;i++)newArray[i]=alist[i];//保留原数组中元素delete[ ]alist;alist=newArray;FSize=newSize;}}

第26页：编写一个函数

[例]编写一个函数，要求输入一个整数N，用动态数组A来存放2 N之间所有5或7的倍数，输出该数组。#include <iostream.h>#include “array.h”void main( ){Array <int> A(10);int N,count = 0;cin>>N;~

第27页：编写一个函数（续）

for(int i=5;i<=N;i++){ if (i%5= =0||i%7= =0)A[count++]=i;if (count==A.ListSize( ))A.ReSize(count+10);}for(int j=0;j<count;j++){ cout<<A[j]<<“ ”;}}out :5 7 10 14 1520 21 25 28 3035 40 42 45 4950out :N＝？in: 52

第28页：第三章数组和字符串目录

第三章数组和字符串3.1数组3.2矩阵3.3字符串

第29页：本节内容目录

3.2矩阵3.2.1矩阵类3.2.2特殊矩阵3.2.3三元组表3.2.4十字链表

第30页：矩阵是常用的数据组织方式

矩阵矩阵是常用的数据组织方式。计算机工作者关心的是矩阵在计算机中如何存储，以及如何实现矩阵的基本操作。用二维数组存放矩阵，或者利用自定义的二维数组类声明矩阵对象，存在以下问题：–数组的基本操作是数组加减，而矩阵的基本操作还有矩阵相乘、矩阵转置等；–数组的下标从0开始,而矩阵的下标一般从1开始；–数组元素用a[i][j]表示,而矩阵元素通常用a(i,j)表示。

因此，用二维数组类型或者自定义的二维数组类所创建的矩阵实用性不强，鉴于此，有必要自定义一个矩阵类。

第31页：矩阵的类定义和实现

3.2.1矩阵的类定义和实现template<class T>class Matrix{private:int rows, cols;//矩阵的行数和列数T *element;//矩阵的元素public:Matrix(int r = 0, int c = 0);//构造函数Matrix(const Matrix<T>& m);//复制构造函数～Matrix() {delete [] element; }//析构函数intRows() const {return rows; }//返回矩阵行数intColumns() const {return cols; }

第32页：重载下标操作符

T &operator()(int i, int j) const;//重载下标操作符Matrix<T>&operator =(const Matrix<T>& m);

第33页：算法Multi

算法Multi-1(A, B, m, p, n. C)//求矩阵的乘积FOR i=1 TO m DOFOR j=1 TO n DO(cij←0.FOR k=1 TO p DO. )▐重载乘法操作符对于矩阵Am×p和Bp×n的乘积Cm×n，其第i行第j列元素cij的计算公式为

第34页：用一维数组存放矩阵

用一维数组存放矩阵，随着矩阵元素行号或列号的变化，其对应的一维数组的下标也要进行相应变换。设矩阵A和B分别按行优先存放在一维数组s和t中，aik是矩阵A中第i行第k列的元素，bkj是矩阵B中第k行第j列的元素，则ai(k+1)在s中的下标比aik在s中的下标多1，b(k+1)j在t中的下标比bkj在t中的下标多n.

第35页：算法Multi（续2）

算法Multi-2(s, t, m, p, n. w)M1. [初始化]cw←0 .

第36页：算法Multi（续）

FOR j=1 TO n DO

第37页：分析：矩阵乘法算法中包含三层循环

分析：矩阵乘法算法中包含三层循环，所以其时间复杂性为O(m×n×p) .

第38页：本节内容目录

3.2矩阵3.2.1矩阵类3.2.2特殊矩阵3.2.3三元组表3.2.4十字链表

第39页：对角矩阵的压缩存储

1、对角矩阵的压缩存储n×n维方阵M是对角矩阵，则对i≠j(1≤i,j≤n)，都有M(i,j)=0，即非对角线上的元素均为0.对于一个n×n维对角矩阵，至多只有n个非零元素，因此只需存储其n个对角元素的信息。采用一维数组d[n]来压缩存储对角矩阵，其中d[i]存储M[i,i]的值。

第40页：三角矩阵

2、三角矩阵的压缩存储三角矩阵分为上三角矩阵和下三角矩阵。方阵M是上三角矩阵，当且仅当i>j时有M(i,j)=0.方阵M是下三角矩阵，当且仅当i<j时有M(i,j)=0.50 15 35 250 10 20 600 0 30 100 0 0 4050 0 0 015 10 0 035 20 30 025 60 10 40

第41页：以下三角矩阵为例

以下三角矩阵为例，讨论其压缩存储方法。考虑一个n×n维下三角矩阵，其第一行有1个非零元素，第二行有2个非零元素，…，第n行有n个非零元素，非零元素共有(1+2+…+n) =n(n+1)/2个。可以用大小为n(n+1)/2的一维数组来存储下三角矩阵，即把下三角矩阵M的非零元素映射到一个一维数组d中。映射次序可采用按行优先或按列优先。

假设映射采取按行优先，非零元素M(i,j)会映射到一维数组d中的哪个元素？

第42页：元素

设元素M(i,j)前面有k个元素，可以计算出k=1+2+…+(i-1)+(j-1)=i(i-1)/2+(j-1)设一维数组d的下标是从0开始，则M(i,j)映射到d中所对应的元素是d[k].有了k的计算公式，可以很容易实现下三角矩阵的压缩存储。

第43页：对称矩阵

3、对称矩阵的压缩存储方阵Mn×n是对称矩阵，当且仅当对于任何1≤i,j≤n，均有M(i,j)=M(j,i).因为对称矩阵中M(i,j)与M(j,i)的信息相同，所以只需存储M的上三角部分或下三角部分的元素信息。

第44页：参照下三角矩阵

参照下三角矩阵的压缩存储方法，即用大小为n(n+1)/2的一维数组来存储，对于对称矩阵中的下三角矩阵元素M(i,j)(i≥j)，和下三角矩阵压缩存储的映射公式一样，映射到d[k](其中k=i(i-1)/2+(j-1))；对称矩阵中的上三角矩阵元素M(i,j)，因其元素值与下三角中的M(j,i)相同，故映射到d[q](其中q=j(j-1)/2+(i-1)).有了k和q的计算公式，即可实现对称矩阵的压缩存储。

第45页：稀疏矩阵的压缩存储定义

4、稀疏矩阵的压缩存储定义：设矩阵Am×n中非零元素的个数远远小于零元素的个数，则称A为稀疏矩阵。◆特点：零元素的分布没有规律。◆作用：解决空间浪费的问题。

第46页：对于矩阵Am×n的每个元素aij

对于矩阵Am×n的每个元素aij，知道其行号i和列号j，就可以确定该元素在矩阵中的位置。因此，如果用一个结点来存储一个非零元素的话，那么该结点可以设计如下：ijaij

第47页：三个域

由三个域（行号、列号和元素值）构成的结点被称为三元组结点：矩阵的每个非零元素可由一个三元组结点（i，j，aij）唯一确定。如何在三元组结点的基础上实现对整个稀疏矩阵的存储？–用顺序存储方式实现的三元组表–链接存储方式实现的十字链表。

第48页：本节内容目录

3.2矩阵3.2.1矩阵类3.2.2特殊矩阵3.2.3三元组表3.2.4十字链表

第49页：三元组表

三元组表将表示稀疏矩阵的非零元素的三元组结点按行优先的顺序排列，得到一个线性表，将此线性表用顺序存储结构存储起来，称之为三元组表。

第50页：稀疏矩阵三元组表

50 0 0 010 0 20 00 0 0 0－30 0－60 5A＝B[0]B[1]B[2]B[3]B[4]B[5]0021501333-6020-301035020[例]稀疏矩阵三元组表

第51页：三元组的结点类

template <class T>

第52页：SparseMatrix 类的定义

class SparseMatrix{private://稀疏矩阵的行数、列数及非零元素个数int Rows,Cols,Count;int MaxTerm;//存储三元组表的数组Trituple <T> smArray[MaxTerm];template <class T>

第53页：建立一个稀疏矩阵

public://建立一个稀疏矩阵SparseMatrix( int Mrows,int Mcols);//求转置矩阵SparseMatrix <T>Transpose( );//矩阵的其它运算//求矩阵的和SparseMatrix <T>Add(SparseMatrix <T> b);//求矩阵的乘积SparseMatrix <T>Multiply(SparseMatrix <T> b);……};

第54页：稀疏矩阵

50 10 0-300 0 0 00 20 0-600 0 0 5A`＝[例]稀疏矩阵50 0 0 010 0 20 00 0 0 0-30 0-60 5A＝转置矩阵

第55页：稀疏矩阵的三元组表示

50 10 0-300 0 0 00 20 0-600 0 0 5A`＝[例]稀疏矩阵的三元组表示50 0 0 010 0 20 00 0 0 0-30 0-60 5A＝a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30b[0]b[1]b[2]b[3]b[4]b[5]005030-30101033532-601220

第56页：算法Transpose

算法Transpose(a, b)T1. [初始化]j=0.

第57页：元素（续2）

b[0]b[1]b[2]b[3]b[4]b[5]005030-30101033532-601220a[0]a[1]a[2]a[3]a[4]a[5]00502120011033523-6003-30IF (col( a[i] )=k THEN(row(b[j])←k.//该元素在b中的行号为kcol(b[j])←row(a[i]).//在b中的列号为其在a中的行号value( b[j] )←value( a[i] ).)j←j+1. )//考察三元组表b中的下一个结点▐

第58页：对于用三元组表存储的稀疏矩阵Am×n

对于用三元组表存储的稀疏矩阵Am×n，若矩阵非零元素个数为t，求Am×n的转置矩阵的时间复杂性是多少呢？观察Transpose函数不难发现，函数中包含双重循环，第一重循环是对转置矩阵A′按行优先依次确认非零元素，故循环次数为A′的行数n；第二重循环是扫描原矩阵的三元组表，执行次数是矩阵非零元素个数t，显然，求转置矩阵的时间复杂性为O(nt).能否找到时间复杂性为O(n+t)的算法呢？（课后作业）

第59页：本节内容目录

3.2矩阵3.2.1矩阵类3.2.2特殊矩阵3.2.3三元组表3.2.4十字链表

第60页：十字链表矩阵

LEFTUPROWCOLVAL800070900004060043214321十字链表矩阵的元素结构如下：分别表示该元素的左邻非零元素、上邻非零元素、所在的行、所在的列和它的值。例：稀疏矩阵

第61页：矩阵的每一行

矩阵的每一行、每一列都设置为由一个表头结点引导的循环链表，并且各行和各列的表头结点有如下特点：-1 = COL（Loc（BASEROW[i]））< 0-1 = ROW（Loc（BASECOL[j]））< 0

第62页：

第63页：第三章数组和字符串目录

第三章数组和字符串3.1数组3.2矩阵3.3字符串

第64页：本节内容目录

3.3字符串3.3.1字符串的定义和实现3.3.2模式匹配算法

第65页：串的定义

串的定义：串是由零个或多个字符顺序排列组成的有限序列。如字符串S可记作：S="a0a1…an-1"S是串名，引号中的字符序列是串值，字符个数n是串长度。空串：长度为零的串称为空串。空白串：由一个或多个空格组成的串称为空白串。3.3.1字符串的定义和实现

第66页：子串

子串：若把某个串称为主串，则主串中任意个连续的字符组成的子序列被称为子串。子串在主串中第一次出现时，其首字符在主串中的序号被称为该子串在主串中的位置。[例] A ="This is a string"B ="is"子串B ="is"在主串中的位置是

第67页：串的顺序存储

1、串的顺序存储：把一个串所包含的字符序列相继存入连续的字节中(1)非紧缩格式:一个存储单元存放一个字符[例] S＝"a0a1…an-1"a0a1an-1Word[0]Word[1]Word[n-1]…………字符串的存储方式

第68页：紧缩格式

(2)紧缩格式:一个存储单元存放多个字符[例] S="a0a1…an-1"//一个存储单元存放4个字符a1a4an-1Word[0]Word[1]……a0a2a3a5a6a7an-2Word[ n/4 ]-1……

第69页：串的链式存储

2、串的链式存储：串的链接存储是把可用的存储空间分成一系列大小相同的结点，其中每个结点的结构为：（str, link）5china p●结点大小为4的链串Sc5hian ●结点大小为1的链串

第70页：标准字符串采用字符指针

C++标准字符串采用字符指针或字符数组，如：char *s1="good", char s2[]="good";实际的存储空间是串长+1C++标准字符串的库函数，提供了常用操作：1.串长函数intstrlen(char* s);例: result=strlen(s1),此函数值为42.串复制char *strcpy(char * s1, * s2);//将串s2复制到s1,并返回指向s1的首字符的指针;例：strcpy(s3,s1),使s3有值" good ",同时函数返回s3首地址。

第71页：执行机制

执行机制Char *strcpy(char * d, char * s){int i=0;while(s[i] !="\0"){d[i]=s[i];i++;}d[i]="\0"; }//问题：若字符串s比d长,该程序无检查拷贝出界和报告错误的机制,可能丢失字符。

第72页：串拼接

3.串拼接char * strcat(char * s1, * s2);//将串s2拼接到s1的尾部，并返回指向s1的首字符的指针;char * strcat(char * s1, char * s2)与上面的程序存在类似缺欠，在此不再给出其程序。当拼接的目标串s1的最大长度不够，拼接就会因出界而丢失字符，产生错误。

4.串的输入输出cin>>s1和cout<<s2等。5.……

第73页：String 类的定义

class String{private:char *str;

第74页：串拼接运算符重载

//串拼接运算符重载String & operator+(const String & s) const;

第75页：构造函数

(1)构造函数，申请内存并将一个C++串复制给当前对象String::String( char * s){size = strlen(s);//串的长度str = new char [size+1];

第76页：赋值运算符重载

(2)赋值运算符重载——把一个String对象赋值给当前对象String & String::operator =(const String & s){if (s.size != size){delete [] str;str = new char[s.size+1];if (str = = NULL)//若申请空间失败，则退出{ cout<<“outofMemory” <<endl;exit(1); }size = s.size;}strcpy(str, s.str);

第77页：拼接运算符重载

(3)拼接运算符重载——string+stringString String::operator +(const String & s) const{String temp;//创建一个临时串tempdelete [] temp.str;//释放创建temp时所申请的空间int len = size + s.size;temp.str = new char[len+1];//为存放拼接串申请空间if (temp.str = = NULL)

第78页：取子串函数

(4)取子串函数，返回从index开始长度为count的子串String String::Substr( int index, int count ) const{int charleft = size–index;

第79页：令字符指针

char *p = temp.str;//令字符指针p指向暂无内容的字符数组temp.str的首字符处char *q = &str[index];//令字符指针q指向当前对象的str数组下标index处for ( int i =0; i < count; i++)*p++ = *q++;//从当前str的index位置开始复制count个字符到temp.str*p="\0";//用"\0"作为temp.str的结尾temp.size = count;return temp;}

第80页：位置开始找字符

(5)从start位置开始找字符c首次出现的位置，若找到，则返回该位置；否则返回-1.intFind(char c, int start) const{if (start > = size)// start超过串长{ cout<<“start位置无效”<<endl;exit(1); }int i = start;while ( str[i] !=NULL && str[i] != c )i ++;//查找字符c，若当前对象中没有字符c，则循环在串尾结束if ( str[i] = = NULL )//未找到字符c，则返回-1return-1;return i;//否则，返回字符c在当前对象中的位置}

第81页：本节内容目录

3.3字符串3.3.1字符串的定义和实现3.3.2模式匹配算法

第82页：文本编辑器中常用

文本编辑器中常用的“查找”、“替换”和“全部替换”等基本的编辑操作就是最普通的模式匹配问题，即：在文本文件中查找串。模式匹配的查找过程(Find)可简单描述如下:给定两个字符串变量S和P，其中目标S有n个字符，模式P有m个字符，m≤n。从S的给定位置（通常为S的第一个字符）开始，搜索模式P，如果找到，返回模式P的第一个字符在S中的位置；

如果没找到（即S中没有P），则返回-1。模式匹配算法

第83页：朴素模式匹配算法

babaaabaS :babaP:babababababababa朴素模式匹配算法

第84页：算法StringMatchin

算法StringMatching( S, P )// S为目标串，P为模式串，返回S中首个P子串的位置SM1. [初始化]i←0 .SM2. [逐字符匹配]WHILE i≤|S|-|P| DO

第85页：朴素模式匹配算法的优点是过程简单

朴素模式匹配算法的优点是过程简单，缺点是效率比较低。在最坏情况下，该算法要匹配n-m+1次，每次匹配做m次比较，因此最坏情况下的比较次数是m×(n-m+1)次，时间复杂性为O(m×(n-m+1))。通常情况下，m的值远小于n的值，时间复杂性可粗略地记为O(n×m)。

第86页：朴素模式匹配算法效率不高

朴素模式匹配算法效率不高的主要原因是进行了重复的字符比较通过对模式P的结构进行研究，可以发现：在abab中P0=P2 ,P1=P3,P0≠P1模式匹配的改进算法

第87页：比较次数第一次

比较次数第一次babaaabaS :≠===babaP:

第88页：比较次数第二次

比较次数第二次babaaabaS :≠babaP:S1=P1，P1≠ P0第二次比较必然失败

第89页：比较次数第三次

比较次数第三次babaaabaS :≠=babaP:S3≠P3，P3=P1第三次比较必然失败

第90页：比较次数第四次

比较次数第四次babaaabaS :babababaP:第一次比较完成后，直接进行第四次比较即可，即令朴素算法的指针i=3不变，指针j=0；

第91页：比较次数第四次（图）

sn-1…st+j+1st+j…st+2st+1st…s0S :≠=====pj+1pj…p2p1p0Pt+1:…pj-1…p1p0Pt+2:

第92页：比较次数第四次（续2）

sn-1…st+j+1st+j…st+2st+1st…s0S :≠=====pj+1pj…p2p1p0Pt+1:pj-1…p1p0Pt+2:pj-2…p0Pt+3:

第93页：以此类推

sn-1…st+j+1st+j…st+2st+1st…s0S :≠=====pj+1pj…p2p1p0Pt+1:Pk+1pk…p0Pt+j-k+1以此类推，直到存在一个k，使得且这样就可以直接进行第t+j-k+1次比较，即从st+j+1与pk+1开始比较。…

第94页：基于失败函数

基于失败函数的快速模式匹配算法（也称为KMP算法）int String ::FastFind（String pat）const{//整型数组f [ ]表示失败函数，存储各个j所对应的k值int p = 0，s = 0 ;//给出模式和目标的扫描指针的初始位置int m = pat.size，n = size ;//模式和目标的长度while (p<m && s<n)if (pat.str[p]==str[s] ){ p++ ; s ++ ; }else if (p = = 0) s++ ;//若第一个字符匹配失败，则从S的下个字符开始elsep=pat.f[p-1]+1;

第95页：KMP算法的时间

KMP算法的时间复杂性分析•在KMP算法中，字符比较是沿着目标S前进(不返回)的。因此，在已知失败函数的情况下，该算法的时间复杂性为O(n).•计算失败函数算法的时间复杂性为O(m).•KMP算法总的时间复杂性为O(n+m).

第96页：何计算失败函数

如何计算失败函数，即如何求k值？

第97页：使用归纳法计算失败函数

…pj+1pjpj-1pj-2…p3p2p1p0aabaaaba…pj+1pjpj-1pj-2…p3p2p1p0abaaba…pj+1pjpj-1pj-2…p3p2p1p0babaaaba使用归纳法计算失败函数f(j)

第98页：

第99页：

第100页：算法Fail

算法Fail(P.f)F1.[赋初值]m←size(P).f(0)←-1.F2.[循环计算]FORj=1TOm-1DO(i←f(j-1).WHILEpj≠pi+1ANDi>0DOi←f(i).IFpj=pi+1THENf(j)←i+1

第101页：课后作业

课后作业74页3-10