数据结构第02章(清华殷人昆版)学习教案.pptx

《数据结构第02章(清华殷人昆版)学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构第02章(清华殷人昆版)学习教案.pptx（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)第第02章章(清华清华 殷人昆版殷人昆版)第一页，共66页。作为作为(zuwi)抽象数据类型抽象数据类型的数组的数组n n一维数组一维数组n n 一维数组的示例一维数组的示例(shl)35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9第1页/共66页第二页，共66页。一维数组的特点一维数组的特点(tdin)n n连续连续(linx)存储的线性表（别名存储的线性表（别名 向量）向量）第2页/共66页第三页，共66页。数组的定义数组的定义数组的定义数组的定义(dngy)(dngy)(dngy)(dngy)和

2、初和初和初和初始化始化始化始化#include class szcl int e;public:szcl()e=0;szcl(int value)e=value;int get_value()return e;第3页/共66页第四页，共66页。main()szcl a13=3,5,7,*elem;for(int i=0;i 3;i+)cout a1i.get_value()“n”;/静静态态(jngti)elem=a1;for(int i=0;i 3;i+)cout get_value()“n”;/动态动态 elem+;return 0;第4页/共66页第五页，共66页。一维数组一维数组一维数

3、组一维数组(Array)(Array)类的定义类的定义类的定义类的定义(dngy)(dngy)#include#include template class Array Type*elements;/数组存放数组存放(cnfng)空间空间 int ArraySize;/当前长度当前长度 void getArray();/建立数组建立数组空间空间 public:Array(int Size=DefaultSize);Array(const Array&x);第5页/共66页第六页，共66页。Array()delete elements;Array&operator=/数组复制 (const Ar

4、ray&A);Type&operator (int i);/取元素(yun s)值 int Length()const return ArraySize;/取数组长度 void ReSize(int sz);/扩充数组 第6页/共66页第七页，共66页。template void Array:getArray()/私有函数：创建数组存储私有函数：创建数组存储(cn ch)空间空间 elements=new TypeArraySize;if(elements=NULL)arraySize=0;cerr “存储存储(cn ch)分配错！分配错！endl;return;一维数组公共一维数组公共一维数

5、组公共一维数组公共(gnggng)(gnggng)操作操作操作操作的实现的实现的实现的实现第7页/共66页第八页，共66页。template Array:Array(int sz)/构造函数构造函数 if(sz=0)arraySize=0;cerr “非法非法(fif)数组大小数组大小”endl;return;ArraySize=sz;getArray();第8页/共66页第九页，共66页。template Array:Array(Array&x)/复制复制(fzh)构造函数构造函数 int n=ArraySize=x.ArraySize;elements=new Typen;if(eleme

6、nts=NULL)arraySize=0;cerr “存储分配错存储分配错”endl;return;Type*srcptr=x.elements;Type*destptr=elements;while(n-)*destptr+=*srcptr+;第9页/共66页第十页，共66页。template Type&Array:operator (int i)/按数组名及下标按数组名及下标 i，取数组元素的值，取数组元素的值 if(i ArraySize-1)cerr “数组下标超界数组下标超界”endl;return NULL;return elementi;使用使用(shyng)该函数于赋值语句该函

7、数于赋值语句 Pos=Positioni-1+Numberi-1第10页/共66页第十一页，共66页。template void Array:Resize(int sz)if(sz=0&sz!=ArraySize)Type*newarray=new Typesz;/创建新数组创建新数组 if(newarray=NULL)cerr “存储存储(cn ch)分配错分配错”endl;return;int n=(sz 0 a,i=0 a+i*la第14页/共66页第十五页，共66页。n n 二维数组二维数组二维数组二维数组行优先行优先(yuxin)LOC(j,k)=a+(j*m+k)*l第15页/共6

8、6页第十六页，共66页。n n 三维数组三维数组FF 各维元素个数为各维元素个数为各维元素个数为各维元素个数为 m1,m2,m3 m1,m2,m3FF 下标为下标为下标为下标为 i1,i2,i3 i1,i2,i3的数组元素的存储地址的数组元素的存储地址的数组元素的存储地址的数组元素的存储地址(dzh(dzh)：FF （按页（按页（按页（按页/行行行行/列存放）列存放）列存放）列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l 前前i1页总页总元素元素(yun s)个数个数第第i1页的页的前前i2行总行总元素元素(yun s)个数个数第16页/共66页第十七页，共

9、66页。n n n n 维数组维数组维数组维数组FF 各维元素个数为各维元素个数为各维元素个数为各维元素个数为 m1,m2,m3,mn m1,m2,m3,mnFF 下标下标下标下标(xi bio)(xi bio)为为为为 i1,i2,i3,in i1,i2,i3,in 的数组的数组的数组的数组元素的存储地址：元素的存储地址：元素的存储地址：元素的存储地址：LOC(i1,i2,in)=a+(i1*m2*m3*mn+i2*m3*m4*mn+in-1*mn+in)*l 第17页/共66页第十八页，共66页。线性表线性表(Linear List)n n线性表的定义和特点线性表的定义和特点线性表的定义和

10、特点线性表的定义和特点n n 定义定义定义定义 n n（0 0）个数据元素的有限序列）个数据元素的有限序列）个数据元素的有限序列）个数据元素的有限序列(xli)(xli)，记作，记作，记作，记作n n （a1,a2,ana1,a2,an）n n ai ai 是表中数据元素，是表中数据元素，是表中数据元素，是表中数据元素，n n 是表长度。是表长度。是表长度。是表长度。n n 遍历遍历遍历遍历 逐项访问：逐项访问：逐项访问：逐项访问：n n 从前向后从前向后从前向后从前向后 从后向前从后向前从后向前从后向前 第18页/共66页第十九页，共66页。线性表的特点线性表的特点(tdin)n n除第一个

11、元素外，其他每一个元素有一除第一个元素外，其他每一个元素有一除第一个元素外，其他每一个元素有一除第一个元素外，其他每一个元素有一个且仅有一个直接个且仅有一个直接个且仅有一个直接个且仅有一个直接(zhji)(zhji)前驱。前驱。前驱。前驱。n n除最后一个元素外，其他每一个元素有除最后一个元素外，其他每一个元素有除最后一个元素外，其他每一个元素有除最后一个元素外，其他每一个元素有一个且仅有一个直接一个且仅有一个直接一个且仅有一个直接一个且仅有一个直接(zhji)(zhji)后继。后继。后继。后继。第19页/共66页第二十页，共66页。顺序顺序(shnx)表表(Sequential List)n

12、 n顺序表的定义和特点顺序表的定义和特点顺序表的定义和特点顺序表的定义和特点n n 定义定义定义定义 将线性表中的元素相继存放在一个将线性表中的元素相继存放在一个将线性表中的元素相继存放在一个将线性表中的元素相继存放在一个连续的存储空间中。连续的存储空间中。连续的存储空间中。连续的存储空间中。n n 可利用一维数组描述存储结构可利用一维数组描述存储结构可利用一维数组描述存储结构可利用一维数组描述存储结构n n 特点特点特点特点 线性表的顺序存储方式线性表的顺序存储方式线性表的顺序存储方式线性表的顺序存储方式(fngsh)(fngsh)n n 遍历遍历遍历遍历 顺序访问顺序访问顺序访问顺序访问

13、25 34 57 16 48 09 0 1 2 3 4 5 data第20页/共66页第二十一页，共66页。顺序顺序顺序顺序(shnx)(shnx)表表表表(SeqList)(SeqList)类的类的类的类的定义定义定义定义template template class SeqList class SeqList Type*data;/Type*data;/顺序表存储数组顺序表存储数组顺序表存储数组顺序表存储数组 int MaxSize;int MaxSize;/最大允许长度最大允许长度最大允许长度最大允许长度 int last;int last;/当前最后元素当前最后元素当前最后元素当前最后

14、元素(yun s)(yun s)下标下标下标下标public:public:SeqList(int MaxSize=defaultSize);SeqList(int MaxSize=defaultSize);SeqList()delete data;SeqList()delete data;int Length()const return last+1;int Length()const return last+1;第21页/共66页第二十二页，共66页。int Find(Type&x)const;/查找查找(ch zho)int Locate(int i)const;/定位定位 int In

15、sert(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 last？NULL:datai;第22页/共66页第二十三页，共66页。顺序表部分公共顺序表部分公共顺序表部分公共顺序表部分公共(gnggng)(gnggng)操作的实现操作的实现操作的实现操作的实现 template /

16、构造函数 SeqList:SeqList(int sz)if(sz 0)MaxSize=sz;last=-1;data=new TypeMaxSize;if(data=NULL)MaxSize=0;last=-1;return;第23页/共66页第二十四页，共66页。template int SeqList:Find(Type&x)const /搜索函数：在表中从前搜索函数：在表中从前(cngqin)向后顺序查找向后顺序查找 x int i=0;while(i last)return-1;else return i;第24页/共66页第二十五页，共66页。顺序搜索图示顺序搜索图示25 34 5

17、7 16 48 09 0 1 2 3 4 5 data搜索搜索(su su)16i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48 09 i搜索搜索(su su)成功成功第25页/共66页第二十六页，共66页。25 34 57 16 48 0 1 2 3 4data搜索(su su)50i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i25 34 57 16 48 i搜索搜索(su su)失败失败第26页/共66页第二十七页，共66页。搜索成功搜索成功 若搜索概率相等，则若搜索概率相等，则搜

18、索不成功搜索不成功 数据数据(shj)比较比较 n 次次第27页/共66页第二十八页，共66页。表项的插入表项的插入(ch r)25 34 57 16 48 09 63 0 1 2 3 4 5 6 7data50插入(ch r)x25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data50i第28页/共66页第二十九页，共66页。template int SeqList:Insert(Type&x,int i)/在表中第在表中第 i 个位置插入个位置插入(ch r)新元素新元素 x if(i last+1|last=MaxSize-1)return 0;/插入插入

19、(ch r)不成功不成功 else last+;for(int j=last;j i;j-)dataj=dataj-1;datai=x;return 1;/插入插入(ch r)成功成功 第29页/共66页第三十页，共66页。表项的删除表项的删除(shnch)25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7data16删除(shnch)x25 34 57 50 48 09 63 0 1 2 3 4 5 6 7data第30页/共66页第三十一页，共66页。template int SeqList:Remove(Type&x)/在表中删除在表中删除(shnch)已有元

20、素已有元素 x int i=Find(x);/在表中搜在表中搜索索 x if(i=0)last-;for(int j=i;j=last;j+)dataj=dataj+1;return 1;/成功删除成功删除(shnch)return 0;/表中没有表中没有 x 第31页/共66页第三十二页，共66页。顺序顺序(shnx)表的应用：集合的表的应用：集合的“并并”运算运算void Union(SeqList&A,SeqList&B)int n=A.Length();int m=B.Length();for(int i=1;i=m;i+)int x=B.Get(i);/在在B中取一元中取一元素素 i

21、nt k=A.Find(x);/在在A中搜索中搜索(su su)它它 if(k=-1)/若未找到插入若未找到插入它它 A.Insert(n,x);n+;第32页/共66页第三十三页，共66页。void Intersection(SeqList&A,SeqList&B)int n=A.Length();int m=B.Length();int i=0;while(i n)int x=A.Get(i);/在在A中取一元素中取一元素(yun s)int k=B.Find(x);/在在B中搜索它中搜索它if(k=-1)A.Remove(i);n-;else i+;/未找到在未找到在A中删除它中删除它

22、顺序表的应用顺序表的应用顺序表的应用顺序表的应用(yngyng)(yngyng)：集合的：集合的：集合的：集合的“交交交交”运算运算运算运算第33页/共66页第三十四页，共66页。稀疏稀疏(xsh)矩阵矩阵(Sparse Matrix)非零元素非零元素非零元素非零元素(yun s)(yun s)个数远远少于矩阵元素个数远远少于矩阵元素个数远远少于矩阵元素个数远远少于矩阵元素(yun s)(yun s)个数个数个数个数第34页/共66页第三十五页，共66页。稀疏矩阵的抽象数据类型稀疏矩阵的抽象数据类型稀疏矩阵的抽象数据类型稀疏矩阵的抽象数据类型template class template cl

23、ass SparseMatrix;SparseMatrix;template class Trituple template class Trituple /三元组三元组三元组三元组friend class SparseMatrix friend class SparseMatrix private:private:int row,col;int row,col;/非零元素非零元素非零元素非零元素(yun(yun s)s)行号行号行号行号/列号列号列号列号 Type value;/Type value;/非零元素非零元素非零元素非零元素(yun s)(yun s)的的的的值值值值 templa

24、te class template class SparseMatrix SparseMatrix/稀疏矩阵类定义稀疏矩阵类定义稀疏矩阵类定义稀疏矩阵类定义 第35页/共66页第三十六页，共66页。int Rows,Cols,Terms;/行行/列列/非零元素非零元素(yun s)数数 Trituple smArrayMaxTerms;public:/三元组表三元组表 SparseMatrix(int MaxRow,int Maxcol);SparseMatrix&Transpose (SparseMatrix&);/转置转置 SparseMatrix&Add(SparseMatrix a,S

25、parseMatrix b);/相加相加 SparseMatrix&Multiply(SparseMatrix a,SparseMatrix b);/相乘相乘 第36页/共66页第三十七页，共66页。稀疏稀疏稀疏稀疏(xsh)(xsh)矩矩矩矩阵阵阵阵第37页/共66页第三十八页，共66页。转置转置转置转置(zhun(zhun zh)zh)矩阵矩阵矩阵矩阵第38页/共66页第三十九页，共66页。用三元组表表示的稀疏用三元组表表示的稀疏用三元组表表示的稀疏用三元组表表示的稀疏(xsh)(xsh)矩阵及其转矩阵及其转矩阵及其转矩阵及其转置置置置第39页/共66页第四十页，共66页。稀疏矩阵稀疏矩阵

26、稀疏矩阵稀疏矩阵(j(j zhn)zhn)转置算法转置算法转置算法转置算法思想思想思想思想n n设矩阵列数为设矩阵列数为设矩阵列数为设矩阵列数为 Cols Cols，对矩阵三元组表，对矩阵三元组表，对矩阵三元组表，对矩阵三元组表扫描扫描扫描扫描Cols Cols 次。第次。第次。第次。第 k k 次检测列号为次检测列号为次检测列号为次检测列号为 k k 的的的的项。项。项。项。n n第第第第 k k 次扫描找寻所有列号为次扫描找寻所有列号为次扫描找寻所有列号为次扫描找寻所有列号为 k k 的项，的项，的项，的项，将其行号变列号、列号变行号，顺次将其行号变列号、列号变行号，顺次将其行号变列号、列

27、号变行号，顺次将其行号变列号、列号变行号，顺次(shnc)(shnc)存于转置矩阵三元组表。存于转置矩阵三元组表。存于转置矩阵三元组表。存于转置矩阵三元组表。第40页/共66页第四十一页，共66页。稀疏矩阵稀疏矩阵(j zhn)的转置的转置 template SparseMatrix&SparseMatrix:Transpose (SparseMatrix&a)SparseMatrix b(a.Cols,a.Rows);b.Rows=a.Cols;b.Cols=a.Rows;b.Terms=a.Terms;/转置矩阵转置矩阵(j zhn)的列数的列数,行数和行数和非零元素个数非零元素个数 if

28、(a.Terms 0)int CurrentB=0;/转置三元组表存放指针转置三元组表存放指针第41页/共66页第四十二页，共66页。for(int k=0;k a.Cols;k+)/对所有对所有(suyu)列号处理一遍列号处理一遍 for(int i=0;i a.Terms;i+)if(a.smArrayi.col=k)b.smArrayCurrentB.row=k;b.smArrayCurrentB.col=a.smArrayi.row;b.smArrayCurrentB.value=a.smArrayi.value;CurrentB+;第42页/共66页第四十三页，共66页。return

29、 b;快速转置快速转置快速转置快速转置(zhun(zhun zh)zh)算法算法算法算法n n建立辅助数组建立辅助数组 rowSize 和和 rowStart，记录矩阵转置后各行非，记录矩阵转置后各行非零元素个数和各行元素在转置三元零元素个数和各行元素在转置三元组表中开始组表中开始(kish)存放位置。存放位置。第43页/共66页第四十四页，共66页。n n扫描矩阵三元组表，根据某项的列号，扫描矩阵三元组表，根据某项的列号，扫描矩阵三元组表，根据某项的列号，扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查确定它转置后的行号，查确定它转置后的行号，查确定它转置后的行号，查 rowStar

30、t rowStart 表，表，表，表，按查到的位置按查到的位置按查到的位置按查到的位置(wi zhi)(wi zhi)直接将该项存直接将该项存直接将该项存直接将该项存入转置三元组表中。入转置三元组表中。入转置三元组表中。入转置三元组表中。第44页/共66页第四十五页，共66页。for(int i=0;i a.Cols;i+)rowSizei=0;for(i=0;i a.Terms;i+)rowSizea.smArrayi.col+;rowStart0=0;for(i=1;i Cols;i+)rowStarti=rowStarti-1+rowSizei-1;第45页/共66页第四十六页，共66页

31、。稀疏矩阵的快速稀疏矩阵的快速稀疏矩阵的快速稀疏矩阵的快速(kui s)(kui s)转置转置转置转置template template SparseMatrix&SparseMatrix&SparseMatrix:FastTransposSparseMatrix:FastTranspos (SparseMatrix&a)(SparseMatrix&a)int*rowSize=new inta.Cols;int*rowSize=new inta.Cols;int*rowStart=new inta.Cols;int*rowStart=new inta.Cols;SparseMatrix b(a

32、.Cols,a.Rows SparseMatrix b(a.Cols,a.Rows););b.Rows=a.Cols;b.Cols=a.Rows;b.Rows=a.Cols;b.Cols=a.Rows;b.Terms=a.Terms;b.Terms=a.Terms;if(a.Terms 0)if(a.Terms 0)for(int i=0;i Cols;i+)rowSizei for(int i=0;i Cols;i+)rowSizei=0;=0;第46页/共66页第四十七页，共66页。for(i=0;i Terms;i+)rowSizesmArrayi.col+;rowStart0=0;fo

33、r(i=1;i a.Cols;i+)rowStarti=rowStarti-1+rowSizei-1;for(i=0;i a.Terms;i+)int j=rowStarta.smArrayi.col;b.smArrayj.row=a.smArrayi.col;b.smArrayj.col=a.smArrayi.row;b.smArrayj.value=a.smArrayi.value;rowStarta.smArrayi.col+;第47页/共66页第四十八页，共66页。delete rowSize;delete rowStart;return b;第48页/共66页第四十九页，共66页。字

34、符串字符串(String)字符串是字符串是字符串是字符串是 n(n(0)0)个字符的有限序列，个字符的有限序列，个字符的有限序列，个字符的有限序列，记作记作记作记作 S:“c1c2c3cn”S:“c1c2c3cn”其中其中其中其中(qzhng)(qzhng)，S S 是串名字是串名字是串名字是串名字 “c1c2c3cn”“c1c2c3cn”是串值是串值是串值是串值 ci ci 是串中字符是串中字符是串中字符是串中字符 n n 是串的长度。是串的长度。是串的长度。是串的长度。例如例如例如例如,S=“Tsinghua University”,S=“Tsinghua University”第49页/

35、共66页第五十页，共66页。const int maxLen=128;class String int curLen;/串的当前长度串的当前长度(chngd)char*ch;/串的存储数组串的存储数组 public:String(const String&ob);String(const char*init);String();String()delete ch;字符串抽象数据类型和类定义字符串抽象数据类型和类定义字符串抽象数据类型和类定义字符串抽象数据类型和类定义(dngy)(dngy)第50页/共66页第五十一页，共66页。int Length()const return curLen;/

36、求当前串*this的实际长度(chngd)String&operator()(int pos,int len);/取*this从pos开始len个字符组成的子串 int operator=(const String&ob)return strcmp(ch,ob.ch)=0;/判当前串*this与对象串ob是否相等 int operator!=(const String&ob)const return strcmp(ch,ob.ch)!=0;/判当前串*this与对象串ob是否不等 第51页/共66页第五十二页，共66页。int operator!()const return curLen=0;

37、/判当前串判当前串*this是否是否(sh fu)空串空串 String&operator=(String&ob);/将串将串ob赋给当前串赋给当前串*this String&operator+=(String&ob);/将串将串ob连接到当前串连接到当前串*this之后之后 char&operator (int i);/取当前串取当前串*this的第的第 i 个字符个字符 int Find(String&pat)const;第52页/共66页第五十三页，共66页。String:String(const String&ob)/复制(fzh)构造函数：从已有串ob复制(fzh)ch=new ch

38、armaxLen+1;/创建串数组 if(ch=NULL)cerr “存储分配错!n”;exit(1);curLen=ob.curLen;/复制(fzh)串长度 strcpy(ch,ob.ch);/复制(fzh)串值 字符串部分字符串部分字符串部分字符串部分(b fen)(b fen)操作的实现操作的实现操作的实现操作的实现第53页/共66页第五十四页，共66页。String:String(const char*init)/复制构造函数:从已有字符数组*init复制 ch=new charmaxLen+1;/创建(chungjin)串数组 if(ch=NULL)cerr “存储分配错!n”;e

39、xit(1);curLen=strlen(init);/复制串长度 strcpy(ch,init);/复制串值 第54页/共66页第五十五页，共66页。String:String()/构造函数：创建一个(y)空串 ch=new charmaxLen+1;/创建串数组 if(ch=NULL)cerr “存储分配错!n”;exit(1);curLen=0;ch0=0;第55页/共66页第五十六页，共66页。提取子串的算法提取子串的算法提取子串的算法提取子串的算法(sun f(sun f)示示示示例例例例pos+len-1 pos+len-1 curLen-1 curLeni n f i n i t

40、 yi n f i n i t ypos=2,len=3pos=5,len=4f i ni t y超出超出超出超出(choch)(choch)第56页/共66页第五十七页，共66页。String&String:operator()(int pos,int len)/从串中第 pos 个位置起连续提取 len 个字符/形成(xngchng)子串返回 String*temp=new String;/动态分配 if(pos=maxLen|lencurLen=0;/返回空串 temp-ch0=0;else /提取子串if(pos+len-1=curLen)len=curLen-pos;第57页/共66

41、页第五十八页，共66页。temp-curLen=len;/子串长度(chngd)for(int i=0,j=pos;i chi=chj;/传送串数组 temp-chlen=0;/子串结束 return*temp;例：串 st=“university”,pos=3,len=4使用(shyng)示例 subSt=st(3,4)提取子串 subSt=“vers”第58页/共66页第五十九页，共66页。String&String:operator=(String&ob)/串赋值：从已有串ob复制 if(&ob!=this)delete ch;ch=new char maxLen+1;/重新分配 if(

42、ch=NULL)cerr “内存不足!n”;exit(1);curLen=ob.curLen;/串复制 strcpy(ch,ob.ch);else cout “字符串自身(zshn)赋值出错!n”;return*this;第59页/共66页第六十页，共66页。char&String:operator (int i)/按串名提取串中第按串名提取串中第 i 个字符个字符 if(i=curLen)cout “串下标串下标(xi bio)超界超界!n”;exit(1);return chi;例：串例：串 st=“university”,使用示例使用示例 newSt=st；newChar=st1;数组赋

43、值数组赋值 newSt=“university”提取字符提取字符 newChar=n第60页/共66页第六十一页，共66页。String&String:operator+=(String&ob)/串连接 char*temp=ch;/暂存原串数组 curLen+=ob.curLen;/串长度累加 ch=new char maxLen+1;if(ch=NULL)cerr “存储(cn ch)分配错!n”;exit(1);strcpy(ch,temp);/拷贝原串数组 strcat(ch,ob.ch);/连接ob串数组 delete temp;return*this;第61页/共66页第六十二页，共

44、66页。例：串例：串 st1=“beijing”,st2=“university”,使用示例使用示例(shl)st1+=st2;连接结果连接结果 st1=“beijing university”st2=“university”第62页/共66页第六十三页，共66页。串的模式匹配串的模式匹配n n定义定义定义定义 在串中寻找子串（第一个字符在串中寻找子串（第一个字符在串中寻找子串（第一个字符在串中寻找子串（第一个字符(z f)(z f)）在串中的位置）在串中的位置）在串中的位置）在串中的位置n n词汇词汇词汇词汇 在模式匹配中，子串称为模式，在模式匹配中，子串称为模式，在模式匹配中，子串称为模式

45、，在模式匹配中，子串称为模式，串称为目标。串称为目标。串称为目标。串称为目标。n n示例示例示例示例 目标目标目标目标 T:“Beijing”T:“Beijing”n n 模式模式模式模式 P:“jin”P:“jin”n n 匹配结果匹配结果匹配结果匹配结果=3 =3 第63页/共66页第六十四页，共66页。第第第第1 1趟趟趟趟 T T a b b a b a a b b a b a 穷举的模式穷举的模式穷举的模式穷举的模式(msh)(msh)P P a b a a b a 匹配过程匹配过程匹配过程匹配过程 第第第第2 2趟趟趟趟 T T a b b a b a a b b a b a P

46、P a b a a b a 第第第第3 3趟趟趟趟 T T a b b a b a a b b a b a P P a b a a b a第第第第4 4趟趟趟趟 T T a b b a b a a b b a b a P a b a P a b a 第64页/共66页第六十五页，共66页。int String:Find(String&pat)const /穷举的模式匹配穷举的模式匹配 for(int i=0;i=curLen-pat.curLen;i+)/逐趟比较逐趟比较 int j=0;/从从chi与模式与模式pat.ch比比较较 while(j pat.curLen)if(chi+j=pat.chj)j+;else break;if(j=pat.curLen)return i;/pat扫描扫描(somio)完完,匹配匹配成功成功 第65页/共66页第六十六页，共66页。