數(shù)據(jù)結(jié)構(gòu)與算法

1、數(shù)據(jù)結(jié)構(gòu)與算法,2006.9-2007.1,串的模式匹配,定義 在串中尋找子串（第一個字符）在串中的位置詞匯 在模式匹配中，子串稱為模式，串稱為目標(biāo)。示例 目標(biāo) T : “Beijing” 模式 P : “jin” 匹配結(jié)果 = 3,第1趟 T a b b a b a 窮舉的模式 P a b a 匹配過程 第2趟 T a b b a b a

2、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 =

3、ch; int i = 0; if ( *p && *s )//當(dāng)兩串未檢測完 while ( i <= curLen - pat.curLen ) if ( *p++ == *s++ ) //比較串字符 if ( !*p ) return i; //相等 else { i++; s = ch+i; p =

4、pat.ch; } //對應(yīng)字符不相等，對齊目標(biāo)的 //下一位置，繼續(xù)比較 return -1; },目標(biāo) Tt0 t1 t2 …… tm-1 … tn-1? ? ? ? 模式 patp0 p1 p2 …… pm-1 目標(biāo) T t0 t1 t2 …… tm-1 tm … tn-1

5、 ? ? ? ? 模式 pat p0 p1 …… pm-2 pm-1 目標(biāo) T t0 t1 …… ti ti+1…… ti+m-2 ti+m-1… tn-1 ‖ ‖ ‖ ‖ 模式 pat p0 p1 …… pm-2 pm-1,改進(jìn)的模式匹配,窮舉的模式匹配算法時間

6、代價： 最壞情況比較n-m+1趟，每趟比較m次， 總比較次數(shù)達(dá)(n-m+1)*m 原因在于每趟重新比較時，目標(biāo)串的檢 測指針要回退。改進(jìn)的模式匹配算法可 使目標(biāo)串的檢測指針每趟不回退。 改進(jìn)的模式匹配(KMP)算法的時間代價： 若每趟第一個不匹配，比較n-m+1趟，總比較次數(shù)最壞達(dá)(n-m)+m = n 若每趟第m個不匹配，總比較次數(shù)最壞亦達(dá)到 n,T t0 t1 … ts-1 ts ts+

7、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) 為使模

8、式 P 與目標(biāo) 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

9、則再下一趟也不匹配，因?yàn)橛?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

10、 ‖ ‖ ‖ pj-k pj-k+1 … pj,,,k 的確定方法 當(dāng)比較到模式第 j 個字符失配時， k 的值與模式的前 j 個字符有關(guān)，與目標(biāo)無關(guān)。 利用失效函數(shù) f (j)可描述。利用失效函數(shù) f (j) 的匹配處理 如果 j = 0，則目標(biāo)指針加 1，模式指針回到 p0。

11、 如果 j > 0，則目標(biāo)指針不變，模式指針回到 pf(j-1)+1。,若設(shè) 模式 P = p0 p1…pm-2 pm-1,示例 ：確定失效函數(shù) f (j),樸素匹配算法 (Naive),int index_naive(char S[ ], charT[ ]){ i = j = 0; while (i < S_len && j < T_len) {

12、 if (S[ i ] == T[ j ]) { i++; j++;} else {i = i - (j - 1); j = 0;} } if (j == T_len) return (i - T_len); else return -1;},樸素匹配算法效率較低,T,S,總共進(jìn)行了六趟匹配 :-<,模式匹配的改進(jìn),T,S,只需進(jìn)行三趟匹配 :-）,Knuth-Morris-

13、Pratt算法,Demo,當(dāng)主串 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,i = 7,j = 5,k = 2 = next [5 ],KMP 算法分析(I),S[i - k ... i -1] = T[0 ... k -1],

14、,,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,S[i - k ... i -1] = T[ j - k ... j -1],KMP 算法分析(III),S[i - k ... i -1] = T[0 ... next[ j ] -1],,,a,b,c,a,a,

15、a,b,a,a,b,c,a,c,a,b,a,a,b,c,i,next [ j ],k,S,T,KMP 算法分析(IV),T[0 ... k -1] = T[ j - k ... j -1] ＝ T[0 ... next[ j ] -1],因此得到 k = next [ j ] 的定義(注意下標(biāo)范圍)：,由 (I) ，(II)，和 (III) 我們得到：,以上定義也說明 next [ j ]與主串 S 無關(guān)。,next[ j ]函數(shù)舉例,

16、使主串指針 i 前行,KMP算法,int index_kmp(char S[ ], charT[ ]){ i = j = 0; while (i < S_len && j < T_len) { if (j == -1 || S[ i ] == T[ j ]) { i++; j++;} else { j = next[ j ]; }

17、 } if (j == T_len) return (i - T_len); else return -1;},Naive,next[ j ]函數(shù)的求法,根據(jù)定義 next[0] = -1;設(shè) next[j] = k，求 next[j+1]若 T[j] = T[k]，則 next[j+1] = k + 1 = next[j] + 1;否則(T[j] ? T[k])，若T[[j] = T[next[k]]

18、, 則 next[j+1] = next[k] + 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,next[6] = next[5+1]= next[next[next[5]]] + 1= next[next[2]] + 1= next[0] + 1 = -1 +1 = 0,next[ j ]函數(shù),void

19、 get_next(char T[ ], int next[]){ i = 0; j = -1; next[0] = -1; while (i < T_len) { if (j == -1 || T[ i ] == T[ j ]) { i++; j++; next[ i ] = j; else j = next[

20、i ]; }},運(yùn)用KMP算法的匹配過程第1趟 目標(biāo) 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趟 目標(biāo) 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

21、 ? j = 5 ? j = f (j-1)+1= 2第3趟 目標(biāo) 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 )

22、 const { //帶失效函數(shù)的KMP匹配算法 int posP = 0, posT = 0; int lengthP = pat.curLen, lengthT = curLen; while ( posP < lengthP && posT < lengthT ) if ( pat.ch[posP] == ch[posT] ) {

23、 posP++; posT++; //相等繼續(xù)比較 } else if ( posP == 0 ) posT++; //不相等 else posP = pat.f [posP-1]+1; if ( posP < lengthP ) return -1; else return posT

24、 - lengthP; },計算失效函數(shù) 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 =

25、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 ( ) {//計算失效函數(shù) int leng

26、thP = 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; }},字符串操作應(yīng)用舉例,文本編輯建立詞索引表,文本編輯

27、,Microsoft NotePadMicrosoft Word (WYSIWYG)Unix’s VIEmacs and Emacsen who useGNU EmacsXEmacs,文本編輯的基本數(shù)據(jù)結(jié)構(gòu)——“行”,#define MAXLINE 65535typedef struct {char *line[];int length;} Line;Line text[MAXLINE];,100,104,101

28、,102,103,105,i,text [ i ],建立詞索引表,建立詞索引表可以加速信息檢索,,數(shù)據(jù)庫,建立索引程序,,索 引 表,,,用戶接口,,用戶請求,,,檢索結(jié)果,,檢索程序,,,書目檢索舉例(建立書目關(guān)鍵詞索引表),關(guān)鍵詞索引表,書目文件,,關(guān)鍵詞索引表的數(shù)據(jù)結(jié)構(gòu),#define MaxKeyNum 2500typedef struct { HString key; LinkList bnolist;}

29、IdxTermType;typedef struct { IdxTermType item[MaxKeyNum+1]; int last;} IdxListType;,線性結(jié)構(gòu) － 棧、隊(duì)列,棧 ( Stack ),只允許在一端插入和刪除的順序表允許插入和刪除 的一端稱為棧頂 (top)，另一端稱 為棧底(bottom)特點(diǎn) 后進(jìn)先出 (LIFO),template class Stack {

30、public: Stack ( int=10 );//構(gòu)造函數(shù) void Push ( const Type & item); //進(jìn)棧 Type Pop ( ); //出棧 Type GetTop ( ); //取棧頂元素 void MakeEmpty ( ); //置空棧 in

31、t IsEmpty ( ) const; //判?？辗?int IsFull ( ) const; //判棧滿否},棧的抽象數(shù)據(jù)類型,#include template class Stack {public: Stack ( int=10 ); //構(gòu)造函數(shù) ~Stack ( ) { delete [ ] elemen

32、ts; }//析構(gòu)函數(shù) void Push ( const Type & item ); //進(jìn)棧 Type Pop ( ); //出棧 Type GetTop ( ); //取棧頂元素 void MakeEmpty ( ) { top=-1; } //置空棧 int IsEmpty ( )

33、 const { return top == -1; },棧的數(shù)組表示 — 順序棧,int IsFull ( ) const { return top == maxSize-1; }private: int top; //棧頂數(shù)組指針 Type *elements; //棧數(shù)組 int maxSize; //棧最大容量}tem

34、plate Stack::Stack ( int s ) : top (-1), maxSize (s) { elements = new Type[maxSize]; assert ( elements != 0 ); //斷言},進(jìn)棧示例,,退棧示例,template void Stack::Push ( const Type & item ) { assert (

35、 !IsFull ( ) );//先決條件斷言 elements[++top] = item; //加入新元素}template Type Stack::Pop ( ) { assert ( !IsEmpty ( ) ); //先決條件斷言 return elements[top--]; //退出棧頂元素},template Type stack::GetTop ( ) {

36、 assert ( !IsEmpty ( ) );//先決條件斷言 return elements[top]; //取出棧頂元素}雙棧共享一個?？臻g,多棧處理 棧浮動技術(shù),n棧共享一個數(shù)組空間V[m]設(shè)立棧頂指針數(shù)組 t [n+1] 和 棧底指針數(shù)組 b [n+1]t[i]和b[i]分別指示第i個棧的棧頂與棧底 b[n]作為控制量，指到數(shù)組最高下標(biāo)各棧

37、初始分配空間 s = ?m / n?指針初始值 t[0] = b[0] = -1 b[n] = m-1 t[i] = b[i] = b[i-1] + s, i = 1, 2, …, n-1,插入新元素時的棧滿處理 StackFull ( ),,template void Push ( const int i, const Type & item ) { if ( t [i] == b[i+

38、1] ) StackFull (i); else V[++t[i]] = item; //第i 個棧進(jìn)棧}template Type *Pop ( const i) { if ( t[i] == b[i] ) { StackEmpty(i); return 0; } else return & V[t[i]--]; //第i 個棧出棧},棧的鏈接表示 — 鏈

39、式棧,鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作,template class Stack;template class StackNode {friend class Stack;private: Type data; //結(jié)點(diǎn)數(shù)據(jù) StackNode *link; //結(jié)點(diǎn)鏈指針 Stac

40、kNode ( Type d=0, StackNode *l=NULL ) : data (d), link (l) { }};,鏈?zhǔn)綏?(LinkedStack)類的定義,template class Stack {public: Stack ( ) : top ( NULL ) { } ~Stack ( ); void Push ( const Type & item);

41、 Type Pop ( ); Type GetTop ( ); void MakeEmpty ( ) { top=NULL; } int IsEmpty ( ) const { return top == NULL; }private: StackNode *top; //棧頂指針},template void Stack::~Stack ( ) {

42、StackNode *p; while ( top != NULL ) //逐結(jié)點(diǎn)回收 { p = top; top = top→link; delete p; }}template void Stack::Push ( const Type &item ) { top = new StackNode ( item, top ); //新結(jié)點(diǎn)鏈入top之前, 并成為新棧頂

43、},template Type Stack::Pop ( ) { assert ( !IsEmpty ( ) ); StackNode *p = top; Type retvalue = p→data; //暫存棧頂數(shù)據(jù) top = top→link; //修改棧頂指針 delete p; return retvalue; //釋放,返回數(shù)據(jù)}temp

44、late Type Stack::GetTop ( ) { assert ( !IsEmpty ( ) ); return top→data;},,,隊(duì)列 ( Queue ),定義隊(duì)列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性先進(jìn)先出(FIFO, First In First Out),template class Queue {

45、public: Queue ( int=10 );//構(gòu)造函數(shù) void EnQueue ( const Type & item); //進(jìn)隊(duì) Type DeQueue ( );//出隊(duì)列 Type GetFront ( );//取隊(duì)頭元素值 void MakeEmpty ( );//置空隊(duì)列 int IsEmpty ( ) const ;//判隊(duì)列

46、空否 int IsFull ( ) const;//判隊(duì)列滿否},隊(duì)列的抽象數(shù)據(jù)類型,#include template class Queue {public: Queue ( int=10 ); ~Queue ( ) { delete [ ] elements; } void EnQueue ( const Type & item); Type DeQue

47、ue ( ); Type GetFront ( ); void MakeEmpty ( ) { front = rear = 0; },隊(duì)列的數(shù)組表示 ? 循環(huán)隊(duì)列的類定義,int IsEmpty ( ) const { return front == rear; } int IsFull ( ) const { return (rear+1) % m

48、axSize == front; } int Length ( ) const { return (front-rear+maxSize) % maxSize;}private: int rear, front; Type *elements; int maxSize;},隊(duì)列的進(jìn)隊(duì)和出隊(duì),進(jìn)隊(duì)時隊(duì)尾指針先進(jìn)一 rear = rear + 1，再將新 元素

49、按 rear 指示位置加入。 出隊(duì)時隊(duì)頭指針先進(jìn)一 front = front + 1，再將 下標(biāo)為 front 的元素取出。 隊(duì)滿時再進(jìn)隊(duì)將溢出出錯；隊(duì)空時再出隊(duì)將隊(duì) 空處理。,存儲隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)頭、隊(duì)尾指針加1時從maxSize -1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1: front = (front + 1) % maxSize; 隊(duì)尾指針進(jìn)1: rear =

50、(rear + 1) % maxSize;隊(duì)列初始化：front = rear = 0;隊(duì)空條件：front == rear;隊(duì)滿條件：(rear + 1) % maxSize == front,循環(huán)隊(duì)列 (Circular Queue),循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì),循環(huán)隊(duì)列部分成員函數(shù)的實(shí)現(xiàn)template Queue::Queue ( int sz ) : front (0), rear (0), maxSize (sz)

51、{ elements = new Type[maxSize]; assert ( elements != 0 );}template void Queue::EnQueue ( const Type & item ) { assert ( !IsFull ( ) ); rear = (rear+1) % MaxSize; elements[rear] =

52、 item;},template Type Queue::DeQueue ( ) { assert ( !IsEmpty ( ) ); front = ( front+1) % MaxSize; return elements[front];}template Type Queue::GetFront ( ) { assert ( !IsEmpty ( ) );

53、 return elements[front];},隊(duì)列的鏈接表示 — 鏈?zhǔn)疥?duì)列,隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時無隊(duì)滿問題，但有隊(duì)空問題。隊(duì)空條件為 front == NULL,,,鏈?zhǔn)疥?duì)列類的定義template class Queue;template class QueueNode {friend class Queue;private: Type data; //隊(duì)

54、列結(jié)點(diǎn)數(shù)據(jù) QueueNode *link; //結(jié)點(diǎn)鏈指針 QueueNode ( Type d=0, QueueNode *l=NULL ) : data (d), link (l) { }};,template class Queue {public: Queue ( ) : rear ( NULL ), front ( NULL ) { } ~Queue ( );

55、 void EnQueue ( const Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) { front = rear = NULL; } int IsEmpty ( ) const { return front == NULL; }

56、private: QueueNode *front, *rear; //隊(duì)列指針};,,鏈?zhǔn)疥?duì)列成員函數(shù)的實(shí)現(xiàn)template void Queue::~Queue ( ) {//隊(duì)列的析構(gòu)函數(shù) QueueNode *p; while ( front != NULL ) { //逐個結(jié)點(diǎn)釋放 p = front; front = front→link; delete p;

57、 }},template void Queue:: EnQueue ( const Type & item ) {//將新元素item插入到隊(duì)列的隊(duì)尾 if ( front == NULL ) front = rear = new QueueNode ( item, NULL ); else rear = rear→link = new QueueNode ( item, NULL

58、);},template TypeQueue::DeQueue ( ) {//刪去隊(duì)頭結(jié)點(diǎn)，并返回隊(duì)頭元素的值 assert ( !IsEmpty ( ) );//判隊(duì)空的斷言 QueueNode *p = front; Type retvalue = p→data;//保存隊(duì)頭的值 front = front→link; delete p; //新隊(duì)頭 return re

59、tvalue;},template Type Queue::GetFront ( ) {//若隊(duì)不空，則函數(shù)返回隊(duì)頭元素的值; 若////隊(duì)空，則函數(shù)返回0。 assert ( !IsEmpty ( ) ); return front→data;},隊(duì)列的應(yīng)用舉例 — 逐行打印二項(xiàng)展開式 (a + b)i 的系數(shù),楊輝三角形 (Pascal’s triangle),分析第 i 行元素與

60、第 i+1行元素的關(guān)系,目的是從前一行的數(shù)據(jù)可以計算下一行的數(shù)據(jù),從第 i 行數(shù)據(jù)計算并存放第 i+1 行數(shù)據(jù),利用隊(duì)列打印二項(xiàng)展開式系數(shù)的程序#include #include #include "queue.h"void YANGVI ( int n ) { Queue q; //隊(duì)列初始化 q.MakeEmpty ( );

61、 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

62、t = q.DeQueue ( ); q.EnQueue ( s+t ); s = t; if ( j != i+2 ) cout << s << ' '; } }},,優(yōu)先級隊(duì)列 (Priority Queue),優(yōu)先級隊(duì)列 是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出

63、的是具有最高優(yōu)先權(quán)的元素例如下表：任務(wù)的優(yōu)先權(quán)及執(zhí)行順序的關(guān)系,數(shù)字越小，優(yōu)先權(quán)越高,優(yōu)先隊(duì)列的類定義#include #include $include const int maxPQSize = 50; //缺省元素個數(shù)template class PQueue {public: PQueue ( ); ~PQueue ( ) { delete [ ] pqelements;

64、} void PQInsert ( const Type & item ); Type PQRemove ( );,void makeEmpty ( ) { count = -1; } int IsEmpty ( ) const { return count == -1; } int IsFull ( ) const { return count

65、 == maxPQSize; } int Length ( ) const { return count; }private: Type *pqelements;//存放數(shù)組 int count; //隊(duì)列元素計數(shù)},優(yōu)先隊(duì)列部分成員函數(shù)的實(shí)現(xiàn)template PQueue::PQueue ( ) : count (-1) { pqelements =

66、 new Type[maxPQSize]; assert ( pqelements != 0 ); //分配斷言}template void PQueue ::PQInsert ( const Type & item ) { assert ( !IsFull ( ) ); //判隊(duì)滿斷言 count ++； pqelements[count] = item;},templ

67、ate Type PQueue::PQRemove ( ) { assert ( !IsEmpty ( ) ); //判隊(duì)空斷言 Type min = pqelements[0]; int minindex = 0; for ( int i=1; i<count; i++ ) //尋找最小元素 if ( pqelements[i] < min ) //存于mi