数据结构与算法.ppt

1、数据结构与算法,2006.9-2007.1,串的模式匹配,定义 在串中寻找子串（第一个字符）在串中的位置词汇 在模式匹配中，子串称为模式，串称为目标。示例 目标 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 ,目标 Tt0 t1 t2 tm-1 tn-1 模式 patp0 p1 p2 pm-1

2、 目标 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个不匹配，总比较次数最

3、坏亦达到 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

4、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 p1p

5、m-2 pm-1,示例 ：确定失效函数 f (j),朴素匹配算法 (Naive),int index_naive(char S , charT ) i = j = 0; while (i S_len ,朴素匹配算法效率较低,T,S,总共进行了六趟匹配 :-,模式匹配的改进,T,S,只需进行三趟匹配 :-）,Knuth-Morris-Pratt算法,Demo,当主串 S i 与子串 T j 失配时，i 不回溯，仅 j 回溯到一个尽量“偏右”的位置 k。因此 KPM 算法的核心问题是寻找确定 k = next j 的方法。,a,b,c,a,a,a,b,a,a,b,c,a,c,a,b,a,a,b,c

6、,i = 7,j = 5,k = 2 = next 5 ,KMP 算法分析(I),Si - k . i -1 = T0 . k -1,a,b,c,a,a,a,b,a,a,b,c,a,c,a,b,a,a,b,c,i,j,k,S,T,KMP 算法分析(II),a,b,c,a,a,a,b,a,a,b,c,a,c,a,b,a,a,b,c,i,j,k,S,T,Si - k . i -1 = T j - k . j -1,KMP 算法分析(III),Si - k . i -1 = T0 . next j -1,a,b,c,a,a,a,b,a,a,b,c,a,c,a,b,a,a,b,c,i,next j ,

7、k,S,T,KMP 算法分析(IV),T0 . k -1 = T j - k . j -1 T0 . next j -1,因此得到 k = next j 的定义(注意下标范围)：,由 (I) ，(II)，和 (III) 我们得到：,以上定义也说明 next j 与主串 S 无关。,next j 函数举例,使主串指针 i 前行,KMP算法,int index_kmp(char S , charT ) i = j = 0; while (i S_len ,Naive,next j 函数的求法,根据定义 next0 = -1;设 nextj = k，求 nextj+1若 Tj = Tk，则 next

8、j+1 = k + 1 = nextj + 1;否则(Tj Tk)，若Tj = Tnextk, 则 nextj+1 = nextk + 1;否则.,a,b,a,a,b,c,T :,a,c,-1,0,0,1,1,2,0,1,0,1,2,3,4,5,6,7,j :,next j :,j=5,next6 = next5+1= nextnextnext5 + 1= nextnext2 + 1= next0 + 1 = -1 +1 = 0,next j 函数,void get_next(char T , int next) i = 0; j = -1; next0 = -1; while (i T_le

9、n) if (j = -1 | T i = T j ) i+; j+; next i = j; else j = next i ; ,运用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

10、c a c ,int String : fastFind ( String pat ) const /带失效函数的KMP匹配算法 int posP = 0, posT = 0; int lengthP = pat.curLen, lengthT = curLen; while ( posP lengthP ,计算失效函数 f j 的方法首先确定f 0 = -1，再利用f j求f j+1。其中, f (1) j = f j , f (m) j = f f (m -1) j ,f 0 = -1; j = 1时, f 0+1 = 0, p0 p1, f 1 = -1;j = 2时, f 1+1 =

11、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= 0 ) i = f i; /递推 if ( *(ch+j) = *(ch+i+1) ) f j = i+1; else f j = -1; ,字符串操作应用举例,

12、文本编辑建立词索引表,文本编辑,Microsoft NotePadMicrosoft Word (WYSIWYG)Unixs VIEmacs and Emacsen who useGNU EmacsXEmacs,文本编辑的基本数据结构“行”,#define MAXLINE 65535typedef struct char *line;int length; Line;Line textMAXLINE;,100,104,101,102,103,105,i,text i ,建立词索引表,建立词索引表可以加速信息检索,数据库,建立索引程序,索 引 表,用户接口,用户请求,检索结果,检索程序,书目检索

13、举例(建立书目关键词索引表),关键词索引表,书目文件,关键词索引表的数据结构,#define MaxKeyNum 2500typedef struct HString key; LinkList bnolist; IdxTermType;typedef struct IdxTermType itemMaxKeyNum+1; int last; IdxListType;,线性结构 栈、队列,栈 ( Stack ),只允许在一端插入和删除的顺序表允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom)特点 后进先出 (LIFO),template class Stack pub

14、lic: Stack ( int=10 );/构造函数 void Push ( const Type /判栈满否,栈的抽象数据类型,#include template class Stack public: Stack ( int=10 ); /构造函数 Stack ( ) delete elements; /析构函数 void Push ( const Type ,栈的数组表示 顺序栈,int IsFull ( ) const return top = maxSize-1; private: int top; /栈顶数组指针 Type *elements; /栈数组 int maxSize;

15、 /栈最大容量template Stack:Stack ( int s ) : top (-1), maxSize (s) elements = new TypemaxSize; assert ( elements != 0 ); /断言,进栈示例,退栈示例,template void Stack:Push ( const Type /退出栈顶元素,template Type stack:GetTop ( ) assert ( !IsEmpty ( ) );/先决条件断言 return elementstop; /取出栈顶元素双栈共享一个栈空间,多栈处理 栈浮动技术,n栈共享一个数组空间Vm设

16、立栈顶指针数组 t n+1 和 栈底指针数组 b n+1ti和bi分别指示第i个栈的栈顶与栈底 bn作为控制量，指到数组最高下标各栈初始分配空间 s = m / n指针初始值 t0 = b0 = -1 bn = m-1 ti = bi = bi-1 + s, i = 1, 2, , n-1,插入新元素时的栈满处理 StackFull ( ),template void Push ( const int i, const Type /第i 个栈出栈,栈的链接表示 链式栈,链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,template class Stack

17、;template class StackNode friend class Stack;private: Type data; /结点数据 StackNode *link; /结点链指针 StackNode ( Type d=0, StackNode *l=NULL ) : data (d), link (l) ;,链式栈 (LinkedStack)类的定义,template class Stack public: Stack ( ) : top ( NULL ) Stack ( ); void Push ( const Type /栈顶指针,template void Stack:Stac

18、k ( ) StackNode *p; while ( top != NULL ) /逐结点回收 p = top; top = toplink; delete p; template void Stack:Push ( const Type /新结点链入top之前, 并成为新栈顶,template Type Stack:Pop ( ) assert ( !IsEmpty ( ) ); StackNode *p = top; Type retvalue = pdata; /暂存栈顶数据 top = toplink; /修改栈顶指针 delete p; return retvalue; /释放,返

19、回数据template Type Stack:GetTop ( ) assert ( !IsEmpty ( ) ); return topdata;,队列 ( Queue ),定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO, First In First Out),template class Queue public: Queue ( int=10 );/构造函数 void EnQueue ( const Type /判队列满否,队列的抽象数据类型,#include template class

20、 Queue public: Queue ( int=10 ); Queue ( ) delete elements; void EnQueue ( const Type ,队列的数组表示 循环队列的类定义,int IsEmpty ( ) const return front = rear; int IsFull ( ) const return (rear+1) % maxSize = front; int Length ( ) const return (front-rear+maxSize) % maxSize;private: int rear, front; Type *elemen

21、ts; int maxSize;,队列的进队和出队,进队时队尾指针先进一 rear = rear + 1，再将新 元素按 rear 指示位置加入。 出队时队头指针先进一 front = front + 1，再将 下标为 front 的元素取出。 队满时再进队将溢出出错；队空时再出队将队 空处理。,存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。队头指针进1: front = (front + 1) % maxSize; 队尾指针进1: rear = (rear + 1) % maxSize;队列初始化：front =

22、rear = 0;队空条件：front = rear;队满条件：(rear + 1) % maxSize = front,循环队列 (Circular Queue),循环队列的进队和出队,循环队列部分成员函数的实现template Queue:Queue ( int sz ) : front (0), rear (0), maxSize (sz) elements = new TypemaxSize; assert ( elements != 0 );template void Queue:EnQueue ( const Type ,template Type Queue:DeQueue (

23、) assert ( !IsEmpty ( ) ); front = ( front+1) % MaxSize; return elementsfront;template Type Queue:GetFront ( ) assert ( !IsEmpty ( ) ); return elementsfront;,队列的链接表示 链式队列,队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 front = NULL,链式队列类的定义template class Queue;template class QueueNode friend class Queue;priv

24、ate: Type data; /队列结点数据 QueueNode *link; /结点链指针 QueueNode ( Type d=0, QueueNode *l=NULL ) : data (d), link (l) ;,template class Queue public: Queue ( ) : rear ( NULL ), front ( NULL ) Queue ( ); void EnQueue ( const Type ,链式队列成员函数的实现template void Queue:Queue ( ) /队列的析构函数 QueueNode *p; while ( front

25、!= NULL ) /逐个结点释放 p = front; front = frontlink; delete p; ,template void Queue: EnQueue ( const Type ,template TypeQueue:DeQueue ( ) /删去队头结点，并返回队头元素的值 assert ( !IsEmpty ( ) );/判队空的断言 QueueNode *p = front; Type retvalue = pdata;/保存队头的值 front = frontlink; delete p; /新队头 return retvalue;,template Type

26、Queue:GetFront ( ) /若队不空，则函数返回队头元素的值; 若/队空，则函数返回0。 assert ( !IsEmpty ( ) ); return frontdata;,队列的应用举例 逐行打印二项展开式 (a + b)i 的系数,杨辉三角形 (Pascals triangle),分析第 i 行元素与第 i+1行元素的关系,目的是从前一行的数据可以计算下一行的数据,从第 i 行数据计算并存放第 i+1 行数据,利用队列打印二项展开式系数的程序#include #include #include queue.hvoid YANGVI ( int n ) Queue q; /队列

27、初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1); int s = 0;,for ( int i=1; i=n; i+ ) /逐行计算 cout endl; q.EnQueue (0); for ( int j=1; j=i+2; j+ ) /下一行 int t = q.DeQueue ( ); q.EnQueue ( s+t ); s = t; if ( j != i+2 ) cout s ; ,优先级队列 (Priority Queue),优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素例如下表：任务的

28、优先权及执行顺序的关系,数字越小，优先权越高,优先队列的类定义#include #include $include const int maxPQSize = 50; /缺省元素个数template class PQueue public: PQueue ( ); PQueue ( ) delete pqelements; void PQInsert ( const Type ,void makeEmpty ( ) count = -1; int IsEmpty ( ) const return count = -1; int IsFull ( ) const return count = m

29、axPQSize; int Length ( ) const return count; private: Type *pqelements;/存放数组 int count; /队列元素计数,优先队列部分成员函数的实现template PQueue:PQueue ( ) : count (-1) pqelements = new TypemaxPQSize; assert ( pqelements != 0 ); /分配断言template void PQueue :PQInsert ( const Type ,template Type PQueue:PQRemove ( ) assert ( !IsEmpty ( ) ); /判队空断言 Type min = pqelements0; int minindex = 0; for ( int i=1; icount; i+ ) /寻找最小元素 if ( pqelementsi min ) /存于min min = pqelementsi; minindex = i; pqelementsminindex = pqelementscount-1; count- ; /删除 return min;,