數(shù)據結構(嚴蔚敏)課件第4章.ppt
《數(shù)據結構(嚴蔚敏)課件第4章.ppt》由會員分享,可在線閱讀,更多相關《數(shù)據結構(嚴蔚敏)課件第4章.ppt(90頁珍藏版)》請在裝配圖網上搜索。
第四章 串,【課前思考】,從數(shù)據結構的觀點來說,串是一種特殊的線性表;但就數(shù)據類型而言,串不是線性表。,,希望你帶著這個問題開始這一章的學習,并能在學完這一章的內容之后能得出正確的結論。,,【學習目標】,1. 理解“串”類型定義中各基本操作的特點,并能正確利用它們進行串的其它操作。 2. 理解串類型的各種存儲表示方法。 3. 理解串匹配的各種算法。,【重點和難點】,相對于其它各個知識點而言,本章非整個課程的重點,鑒于串已是多數(shù)高級語言中已經實現(xiàn)的數(shù)據類型,因此本章重點僅在于了解串類型定義中各基本操作的定義以及串的實現(xiàn)方法,并學會利用這些基本操作來實現(xiàn)串的其它操作。本章的難點是理解實現(xiàn)串匹配的KMP算法的思想,但它不屬本章學習的基本要求,更不是重點學習內容。,【知識點】,串的類型定義、串的存儲表示、串匹配、KMP算法,【學習指南】,雖然目前各常用的高級語言中都已經實現(xiàn)了串類型,但由于它是通過軟件實現(xiàn)的,因此作為一個軟件工作者還是應該了解串的實現(xiàn)方法。本章沒有必須完成的算法設計題,如果有興趣可以試試以下幾個題:4.10,4.11,4.13,4.17,4.18,4.23,4.28,4.30。其中前6個是練習串的基本操作的應用,后2個是和KMP算法相關的練習。,4.1 串類型的定義,4.2 串的表示和實現(xiàn),4.3 串的模式匹配算法,,,4.1串的類型定義,一、 基本概念,1.串的定義 串( string) 是由零個或多個字符組成的有限序列,記作s='a1a2…an',其中s為串的名字,用成對的單引號括起來的字符序列為串的值,但兩邊的引號不算串值,不包含在串中。ai(1≤i≤n)可以是字母、數(shù)字或其它字符。 n為串中字符的個數(shù),稱為串的長度。,2.空串 不含任何字符的串稱為空串,它的長度n=0,記為s=''。,,,3.空格串 含有一個或多個空格的串,稱為空格串,它的長度n為空格的個數(shù),一般用符號“ ?”表示空串。,,串是有限長的字符序列,由一對單引號相括,如: ?a string?,,4.子串、主串 通常將字符在串中的序號稱為該字符在串中的位置。子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。 若一個串是另一個串中連續(xù)的一段,則這個串稱為另一個串的子串,而另一個串相對于該串稱為主串。例如,串s1=“abcdefg”,s2=“fabcdefghxyz”,則s1為s2的子串,s2相對于s1為主串。,另外,空串是任意串的子串,任意串是自身的子串。若一個串的長度為n,則它的子串數(shù)目為 +1,真子串個數(shù)為 (除串本身以外的子串都稱為真子串)。 當且僅當兩個串的值相等時,稱這兩個串是相等的,即只有當兩個串的長度相等, 并且每個對應位置的字符都相等時才相等。,,二、串的抽象數(shù)據類型的定義如下:,ADT String {,數(shù)據對象:,D={ ai |ai∈CharacterSet, i=1,2,.,n, n≥0 },數(shù)據關系:,R1={ | ai-1, ai ∈D, i=2,.,n },基本操作:,,StrAssign (&T, chars),StrCopy (&T, S),DestroyString(&S),StrEmpty (S),StrCompare (S, T),StrLength(S),Concat (&T, S1, S2),SubString (&Sub, S, pos, len),Index (S, T, pos),Replace (&S, T, V),StrInsert (&S, pos, T),StrDelete (&S, pos, len),ClearString (&S),} ADT String,,StrAssign (&T, chars) 初始條件:chars 是字符串常量。 操作結果:把 chars 賦為 T 的值。,,,StrCopy (&T, S) 初始條件:串 S 存在。 操作結果:由串 S 復制得串 T。,,DestroyString (&S) 初始條件:串 S 存在。 操作結果:串 S 被銷毀。,,StrEmpty(S) 初始條件:串S存在。 操作結果:若 S 為空串,則返回TRUE, 否則返回 FALSE。,?? 表示空串,空串的長度為零。,,StrCompare(S,T) 初始條件:串 S 和 T 存在。 操作結果:若S ? T,則返回值 ? 0; 若S ? T,則返回值 ? 0; 若S ? T,則返回值 ? 0。,例如:StrCompare(?data?, ?state?) 0,,StrLength(S) 初始條件:串 S 存在。 操作結果:返回 S 的元素個數(shù), 稱為串的長度。,,Concat(&T,S1,S2) 初始條件:串 S1 和 S2 存在。 操作結果:用 T 返回由 S1 和 S2 聯(lián)接而成的新串。,例如: Concate( T, ?man?, ?kind?) 求得 T = ?mankind?,,,SubString (&Sub, S, pos, len) 初始條件: 串 S 存在,1≤pos≤StrLength(S) 且0≤len≤StrLength(S)-pos+1。 操作結果: 用 Sub 返回串 S 的第 pos 個字符起 長度為 len 的子串。,例如: SubString( sub, ?commander?, 4, 3) 求得 sub = ?man? ; SubString( sub, ?commander?, 1, 9) 求得 sub = ?commander?; SubString( sub, ?commander?, 9, 1) 求得 sub = ?r?;,子串為“串” 中的一個字符子序列,SubString(sub, ?commander?, 4, 7) sub = ?,SubString(sub, ?beijing?, 7, 2) = ? sub = ?,SubString(?student?, 5, 0) = ??,起始位置和子串長度之間存在約束關系,長度為 0 的子串為“合法”串,,Index(S,T,pos) 初始條件:串S和T存在,T是非空串, 1≤pos≤StrLength(S)。 操作結果: 若主串 S 中存在和串 T 值相同 的子串, 則返回它在主串 S 中第pos個字符之后第一次出現(xiàn)的位置;否則函數(shù)值為0。,假設 S = ?abcaabcaaabc?, T = ?bca?,Index(S, T, 1) = 2;,Index(S, T, 2) = 6;,Index(S, T, 8) = 0;,“子串在主串中的位置”意指子串 中的第一個字符在主串中的位序。,,Replace(&S,T,V) 初始條件:串S, T和 V 均已存在, 且 T 是非空串。 操作結果:用V替換主串S中出現(xiàn) 的所有與(模式串)T 相等的不重疊的子串。,例如:,假設 S = ?abcaabcaaabca?,T = ?bca?,若 V = ?x?, 則經置換后得到 S = ?axaxaax?,若 V = ?bc?, 則經置換后得到 S = ?abcabcaabc?,,StrInsert (&S, pos, T) 初始條件:串S和T存在, 1≤pos≤StrLength(S)+1。 操作結果:在串S的第pos個字符之前 插入串T。,例如:S = ?chater?,T = ?rac?, 則執(zhí)行 StrInsert(S, 4, T)之后得到 S = ?character?,,StrDelete (&S, pos, len) 初始條件:串S存在 1≤pos≤StrLength(S)-len+1。 操作結果:從串S中刪除第pos個字符 起長度為len的子串。,,ClearString(&S) 初始條件:串S存在。 操作結果:將S清為空串。,,,對于串的基本操作集可以有不同的定義方法,在使用高級程序設計語言中的串類型時,應以該語言的參考手冊為準。,gets(str) 輸入一個串; puts(str) 輸出一個串; strcat(str1, str2) 串聯(lián)接函數(shù); strcpy(str1, str2, k) 串復制函數(shù); strcmp(str1, str2) 串比較函數(shù); strlen(str) 求串長函數(shù);,例如:C語言函數(shù)庫中提供下列串處理函數(shù):,在上述抽象數(shù)據類型定義的13種操作中, 串賦值StrAssign、串復制Strcopy、 串比較StrCompare、求串長StrLength、 串聯(lián)接Concat以及求子串SubString 等六種操作構成串類型的最小操作子集。 即:這些操作不可能利用其他串操作來實現(xiàn), 反之,其他串操作(除串清除ClearString和串 銷毀DestroyString外)可在這個最小操作子 集上實現(xiàn)。,例如,可利用串比較、求串長和求子串等操作實現(xiàn)定位函數(shù)Index(S,T,pos)。,StrCompare(SubString(S, i, StrLength(T)),T ) ? 0,,,S 串,T 串,,,,T 串,,,i,pos,,n-m+1,算法的基本思想為:,int Index (String S, String T, int pos) { // T為非空串。若主串S中第pos個字符之后存在與 T相等的子串,則返回第一個 這樣的子串在S中的位置,否則返回0 if (pos 0) { n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) { SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) ++i ; else return i ; } // while } // if return 0; // S中不存在與T相等的子串 } // Index,又如串的置換函數(shù): Replace(&S,T,V),S 串,T 串,V 串,,,,,V 串,,pos,,pos,sub,,i,news 串,sub,串的邏輯結構和線性表極為相似,區(qū)別 僅在于串的數(shù)據對象約束為字符集。,串的基本操作和線性表有很大差別。,,在線性表的基本操作中,大多以“單個元素”作為操作對象; 在串的基本操作中,通常以“串的整體”作為操作對象。,在程序設計語言中,串只是作為輸入或輸出的常量出現(xiàn),則只需存儲此串的串值,即字符序列即可。但在多數(shù)非數(shù)值處理的程序中,串也以變量的形式出現(xiàn)。,4.2 串的表示和實現(xiàn),一、串的定長順序存儲表示,二、串的堆分配存儲表示,三、串的塊鏈存儲表示,,一、串的定長順序存儲表示,與前面所講的線性表的順序存儲結構類似, 用一組地址連續(xù)的存儲單元存儲串的字符序列。常常將定長順序串設計成一種結構類型, 串的存儲分配是在編譯時完成的。,#define MAXSTRLEN 255 // 用戶可在255以內定義最大串長 typedef unsigned char Sstring [MAXSTRLEN + 1]; // 0號單元存放串的長度,或: typedef struct { /* 串結構定義 */ char ch[MAXLEN]; int len; } SString;,按這種串的表示方法實現(xiàn)的串的運算時,其基本操作為 “字符序列的復制”。,串的實際長度可在這個予定義長度的范圍內隨意設定,超過予定義長度的串值則被舍去,稱之為 “截斷” 。,特點:,,,Status Concat(SString S1, SString S2, SString } // Concat,例如:串的聯(lián)接算法中需分三種情況處理:,T[1S1[0]] = S1[1S1[0]]; T[S1[0]+1S1[0]+S2[0]] = S2[1S2[0]]; T[0] = S1[0]+S2[0]; uncut = TRUE; },if (S1[0]+S2[0] = MAXSTRLEN) {// 未截斷,else if (S1[0] MAXSTRSIZE) { // 截斷,else { // 截斷(僅取S1),T[1S1[0]] = S1[1S1[0]]; T[S1[0]+1MAXSTRLEN] = S2[1MAXSTRLEN-S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; },T[0MAXSTRLEN] = S1[0MAXSTRLEN]; // T[0] == S1[0] == MAXSTRLEN uncut = FALSE; },,(1) 串插入函數(shù)。 StrInsert(s, pos, t) /*在串s中序號為pos的字符之前插入串t */ SString *s, t; int pos; { int i; if (poss-len) return(0); /* 插入位置不合法 */ if (s-len + t.lenlen + t.len-1;i=t.len + pos;i--) s-ch[i]=s-ch[i-t.len]; for (i=0;ich[i+pos]=t.ch[i]; s-len=s-len+t.len; },定長順序存儲的操作實施:,【算法 串插入函數(shù)】,else if (pos+t.lenMAXLEN, 但串t的字符序列可以全部插入 */ for (i=MAXSTRLEN-1;it.len+pos-1;i--) s-ch[i]=s-ch[i-t.len]; for (i=0;ich[i+pos]=t.ch[i]; s-len=MAXLEN; } else { /* 串t的部分字符序列要舍棄 */ for (i=0;ich[i+pos]=t.ch[i]; s-len=MAXSTRLEN; } return(1); },(2) 串刪除函數(shù)。 StrDelete(s, pos, len) /* 在串s中刪除從序號pos起len個字符 */ SString *s; int pos, len; { int i; if (pos(s-len-len)) return(0); for (i=pos+len;ilen;i++) s-ch[i-len]=s-ch[i]; s-len=s-len - len; return(1); },【算法 串刪除函數(shù)】,(3) 串復制函數(shù)。 StrCopy(s, t) /* 將串t的值復制到串s中 */ SString *s, t; { int i; for (i=0;ich[i]=t.ch[i]; s-len=t.len; },【算法 串復制函數(shù)】,(4) 判空函數(shù)。 StrEmpty(s) /* 若串s為空(即串長為0), 則返回1, 否則返回0 */ SString s; { if (s.len==0) return(1); else return(0); },【算法 判空函數(shù)】,(5) 串比較函數(shù)。 StrCompare(s, t) /* 若串s和t相等, 則返回0;若st,則返回1;若st,則返 回-1 */ SString s, t; { int i; for (i=0;is.len },【算法 串比較函數(shù)】,(6) 求串長函數(shù)。 StrLength(s)/* 返回串s的長度 */ SString s; { return(s.len); },【算法 求串長函數(shù)】,(7) 清空函數(shù)。 StrClear(s) /* 將串s置為空串 */ SString *s; { s-len=0; return(1); },【算法 清空函數(shù)】,(8) 連接函數(shù)。 Concat(s, t) /* 將串t連接在串s的后面 */ SString *s, t; { int i, flag; if (s-len + t.lenlen; ilen + t.len; i++) s-ch[i]=t.ch[i-s-len]; s-len+=t.len;flag=1; },else if (s-lenlen;ich[i]=t.ch[i-s-len]; s-len=MAXSTRLEN;flag=0; } else flag=0;/* 串s的長度等于MAXLEN, 串t不被連接 */ return(flag); },【算法 連接函數(shù)】,(9) 求子串函數(shù)。 SubString(sub, s, pos, len) /* 將串s中序號pos起len個字符復制到sub中 */ SString *sub, s; int pos, len; { int i; if (poss.len || lens.len-pos) { sub-len=0;return(0);} else { for (i=0;ich[i]=s.ch[i+pos]; sub-len=len;return(1); } },【算法 求子串函數(shù)】,(10) 定位函數(shù)。 StrIndex(s, pos, t) /* 求串t在串s中的位置 */ SString s, t; int pos; { int i, j; if (t.len==0) return(0); i=pos;j=0; while (i=t.len) return(i-t.len); else return(0); },【算法 定位函數(shù)】,,,,typedef struct { char *ch; // 若是非空串,則按串長分配存儲區(qū), // 否則ch為NULL int length; // 串長度 } HString;,二、串的堆分配存儲表示,特點:仍用一組地址連續(xù)的存儲單元存儲串的字符序列,但其存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。,通常,C語言中提供的串類型就是以這種存儲方式實現(xiàn)的。系統(tǒng)利用函數(shù)malloc( )和free( )進行串值空間的動態(tài)管理,為每一個新產生的串分配一個存儲區(qū),稱串值共享的存儲空間為“堆”。 C語言中的串以一個空字符為結束符, 串長是一個隱含值。,這類串操作實現(xiàn)的算法為: 先為新生成的串分配一個存儲空間,然后 進行串值的復制。,Status Concat(HString } // Concat,Status SubString(HString } // SubString,… …,,Sub.ch = (char *)malloc(len*sizeof(char)); Sub.ch[0len-1] = S[pos-1pos+len-2]; Sub.length = len;,,三、串的塊鏈存儲表示,也可用鏈表來存儲串值,由于串的數(shù)據元素是一個字符,它只有 8 位二進制數(shù),因此用鏈表存儲時,通常一個結點中存放的不是一個字符,而是一個子串。,存儲密度 =,,數(shù)據元素所占存儲位,實際分配的存儲位,#define CHUNKSIZE 80 // 可由用戶定義的塊大小 typedef struct Chunk { // 結點結構 char ch[CHUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的鏈表結構 Chunk *head, *tail; // 串的頭和尾指針 int curlen; // 串的當前長度 } LString;,例如: 在編輯系統(tǒng)中,整個文本編輯區(qū)可以看成是一個串,每一行是一個子串,構成一個結點。即: 同一行的串用定長結構(80個字符), 行和行之間用指針相聯(lián)接。,實際應用時,可以根據問題所需來設置結點的大小。,,這是串的一種重要操作,很多 軟件,若有“編輯”菜單項的話, 則其中必有“查找”子菜單項。,4.3 串的模式匹配算法,子串的定位操作通常稱為串的模式匹配,是各種串處理系統(tǒng)中最重要的操作之一。,初始條件:串S和T存在,T是非空串, 1≤pos≤StrLength(S)。 操作結果:若主串S中存在和串T值相 同的子串返回它在主串S中 第pos個字符之后第一次出 現(xiàn)的位置;否則函數(shù)值為0。,首先,回憶一下串匹配(查找)的定義:,INDEX (S, T, pos),下面討論以定長順序結構 表示串時的幾種算法。,一、簡單算法,二、首尾匹配算法,三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法,,一、簡單算法Brute-Force算法,,例如,設目標串s=“cddcdc”,模式串t=“cdc”。s的長度為n(n=6),t的長度為m(m=3)。用指針i指示目標串s的當前比較字符位置,用指針j指示模式串t的當前比較字符位置。BF模式匹配過程如下所示。,,這個算法簡單,易于理解,但效率不高,主要原因是:主串指針i在若干個字符序列比較相等后,若有一個字符比較不相等,仍需回溯(即i=i-j+1)。該算法在最好情況下的時間復雜度為O(m),即主串的前m個字符正好等于模式串的m個字符。在最壞情況下的時間復雜度為O(n*m)。,,int index(SqString s,SqString t) { int i=0,j=0,k; while (i=t.len) k=i-t.len; /*返回匹配的第一個字符的下標*/ else k=-1; /*模式匹配不成功*/ return k; },先比較模式串的第一個字符, 再比較模式串的最后一個字符, 最后比較模式串中從第二個到 第n-1個字符。,二、首尾匹配算法,int Index_FL(SString S, SString T, int pos) { sLength = S[0]; tLength = T[0]; i = pos; patStartChar = T[1]; patEndChar = T[tLength]; while (i = sLength – tLength + 1) { if (S[i] != patStartChar) ++i; //重新查找匹配起始點 else if (S[i+tLength-1] != patEndChar) ++i; // 模式串的“尾字符”不匹配 else { } } return 0; },,// 檢查中間字符的匹配情況,,k = 1; j = 2; while ( j tLength // 重新開始下一次的匹配檢測,,三、模式匹配的改進算法(KMP算法),此方法由克努特(D.E.Knuth)-莫里斯(J.H.Morris)-普拉特(V.R.Pratt)同時發(fā)現(xiàn)。,1.基本思想:每當一趟匹配過程中出現(xiàn)字符不等時,不需回溯i指針,而是利用已得到的部分匹配結果,將模式串向右滑動盡可能遠的一段距離后繼續(xù)進行比較。 避免多余的、不必要的比較,從而提高算法性能。算法總在0(n+m)的時間數(shù)量級上完成匹配操作。,2.KMP算法匹配實例:,(1)模式串t中沒有真子串 真子串是指模式串t存在某個k(0<k<j),使得“t0t1…tk”=“tj-ktj-k+1…tj”成立。 例如t=“cdc“就是這樣的模式串。在圖4.6中的第一次回溯,當s0=t0,s1=t1,s2≠t2時,算法中取i=1,j=0,使主串指針回溯一個位置,比較s1和t0。因t0≠t1,所以一定有s1≠t0。另外,因有t0=t2,s0=t0,s2≠t2,則一定可推出s2≠t0,所以也不必取i=2,j=0去比較s2和t0??芍苯釉诘诙伪容^時取i=3,j=0,比較s3和t0。這樣,模式匹配過程主串指針i就可不必回溯。,(2)模式串中存在真子串 例如t=“abab”,由于“t0t1”=“t2t3”(這里k=1,j=3),則存在真子串。設s=“abacabab”,t=“abab”,第一次匹配過程如下所示。,,此時不必從i=1(i=i-j+1=1),j=0重新開始第二次匹配。因t0≠t1,s1=t1,必有s1≠t0,又因t0 =t2,s2=t2,所以必有s2=t0。因此,第二次匹配可直接從i=3,j=1開始。,現(xiàn)在我們討論一般情況。 設s=“s0s1…sn-1“,t=“t0t1…tm-1“,當si≠tj (0≤i≤n-m,0≤j<m)時,存在: “t0t1…tj-1“=“si-jsi-j+1…si-1“ (4.1) 若模式串中存在的真子串滿足: “t0t1…tk“=“tj-ktj-k+1…tj“ (0<k<j) (4.2) 由(4.1)式說明模式串中的子串“t0t1…tk-1“已和主串“si-ksi-k+1…si-1“匹配,下一次可直接比較si和tk,若不存在(4.2)式,則結合(4.1)式說明在“t0t1…tj-1“中不存在任何以t0為首字符子串與“si-j+1si-j+2…si-1“中以si-1為末字符的匹配子串,下一次可直接比較si和t0。,為此,定義next[j]函數(shù)如下: max{k|0kj,且“t0t1…tk-1”=“tj-ktj-k+1…tj-1” } 當此集合非空時 -1 當j=0時 0 其他情況,,,next[j]=,t=“abab”對應的next數(shù)組如下:,由模式串t求出next值的算法如下: void GetNext(SqString t,int next[]) { int j,k; j=0;k=-1;next[0]=-1; while (jt.len-1) { if (k==-1 || t.ch[j]==t.ch[k]) /*k為-1或比較的字符相等時*/ { j++;k++; next[j]=k; } else k=next[k]; } },int KMPIndex(SqString s,SqString t) /*KMP算法*/ { int next[MaxSize],i=0,j=0,v; GetNext(t,next); while (i=t.len) v=i-t.len; /*返回匹配模式串的首字符下標*/ else v=-1; /*返回不匹配標志*/ return v; },設主串s的長度為n,子串t長度為m,在KMP算法中求next數(shù)組的時間復雜度為O(m),在后面的匹配中因主串s的下標不減即不回溯,比較次數(shù)可記為n,所以KMP算法總的時間復雜度為O(n+m)。,例如,設目標串s=“aaabaaaab”,模式串t=“aaaab”。s的長度為n(n=9),t的長度為m(m=5)。用指針i指示目標串s的當前比較字符位置,用指針j指示模式串t的當前比較字符位置。KMP模式匹配過程如下所示。,上述定義的next[]在某些情況下尚有缺陷。例如,模式“aaaab”在和主串“aaabaaaab”匹配時,當i=3,j=3時,s.ch[3]≠t.ch[3],由next[j]的指示還需進行i=3、j=2,i=3、j=1,i=3、j=0等三次比較。實際上,因為模式中的第1、2、3個字符和第4個字符都相等,因此,不需要再和主串中第4個字符相比較,而可以將模式一次向右滑動4個字符的位置直接進行i=4,j=0時的字符比較。,KMP算法的改進:,這就是說,若按上述定義得到next[j]=k,而模式中pj=pk,則為主串中字符si和pj比較不等時,不需要再和pk進行比較,而直接和pnext[k]進行比較,換句話說,此時的next[j]應和next[k]相同。為此將next[j]修正為nextval[j]。,由模式串t求出nextval值: void GetNextval(SqString t,int nextval[]) { int j=0,k=-1; nextval[0]=-1; while (jt.len) { if (k==-1 || t.ch[j]==t.ch[k]) { j++;k++; if (t.ch[j]!=t.ch[k]) nextval[j]=k; else nextval[j]=nextval[k]; } else k=nextval[k]; } },【本章小結】,在這一章介紹了串類型的定義及其實現(xiàn)方法,并重點討論了串操作中最常用的“串定位操作(又稱模式匹配)“的兩個算法。 串的兩個顯著特點是,其一、它的數(shù)據元素都是字符,因此它的存儲結構和線性表有很大不同,例如多數(shù)情況下,實現(xiàn)串類型采用的是“堆分配“的存儲結構,而當用鏈表存儲串值時,結點中數(shù)據域的類型不是“字符“,而是“串“,這種塊鏈結構通常只在應用程序中使用;其二、串的基本操作通常以“串的整體“作為操作對象,而不像線性表是以“數(shù)據元素“作為操作對象,“串匹配”的簡單算法,其算法思想直截了當,簡單易懂,適用于在一般的文檔編輯中應用,但在某些特殊情況,例如只有0和1兩種字符構成的文本串中應用時效率就很低。KMP算法是它的一種改進方法,其特點是利用匹配過程中已經得到的主串和模式串對應字符之間“等與不等“的信息以及T串本身具有的特性來決定之后進行的匹配過程,從而減少了簡單算法中進行的“本不必要再進行的“字符比較。 此外應學會善于利用高級語言中提供的串操作(如C語言中的串函數(shù)庫和C++語言中的串類)進行編程,只是在應用前必須詳細閱讀語言所提供的使用手冊。,一、基礎知識題 二、算法設計題 4.10,4.11,4.13,4.17,4.18,4.23,4.28,4.30,作業(yè),實驗五 鏈隊列的建立及入隊出隊操作,一、實驗目的 了解鏈隊列的結構特點和有關概念,掌握鏈隊列的建立及入隊出隊操作算法。 二、實驗內容 建立鏈隊列,并實現(xiàn)元素的入隊出隊的基本操作。 三、實驗要點及說明 隊列的鏈式存儲結構簡稱為鏈隊列,符合先進先出的原則。與鏈表一樣,鏈隊列大多采用帶頭結點的鏈對,設頭指針為h,則對頭結點為h-next,再設一個對尾指針q-rear指向鏈隊列尾部。 隊列的鏈式存儲結構可定義如下: typedef struct node typedef struct {char data; {slnode *h; struct node *next; }slnode ; slnode *rear;}lqtype; 四、思考題 1、 比較鏈隊列與鏈棧的相同點與不同點。 2、在鏈隊列中, q-rear指針能否省去?若能,怎樣才能找到隊尾?,實驗六 串的模式匹配,一、實驗目的 熟悉串的有關概念,掌握串的存儲結構及串的模式匹配算法。 二、實驗內容 由用戶隨意輸入兩個串:主串S和模式串T,設S=‘s1s2…sn’,T=‘t1t2…tm’,且0m=n。用簡單和KMP模式匹配算法判斷模式串T是否在主串S中,若在,則輸出模式串在主串的第一匹配位置,否則,匹配失敗,返回零值。 三、實驗要點及說明 簡單模式匹配算法和KMP模式匹配算法的主要區(qū)別在于后者將有效利用已有的匹配結果,省去不必要的匹配過程,提高匹配性能。 利用串的順序存儲結構實現(xiàn)實驗內容。 四、思考題 能否用串的塊鏈存儲結構實現(xiàn)KMP算法?,- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- 數(shù)據結構 嚴蔚敏 課件
裝配圖網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
鏈接地址:http://www.szxfmmzy.com/p-1980018.html