第四章串
一、選擇題
注：子串的定義是：串中任意個連續的字元組成的子串行，並規定空串是任意串的子串，任意串是其自身的子串。
若字串長度為n（n>0），長為n的子串有1個，長為n-1的子串有2個，長為n-2的子串有3個，……，長為1的子串有n個。由於空串是任何串的子串，所以本題的答案為：8*（8+1）/2+1=37。
故選b。但某些教科書上認為「空串是任意串的子串」無意義，所以認為選c。為避免考試中的二意性，編者認為第9題出得好。
二、判斷題
三．填空題
1．(1) 由空格字元（ascii值32）所組成的字串 (2)空格個數 2．字元
3．任意個連續的字元組成的子串行4．55.o(m+n)
6．01122312 7．01010421 8．(1)模式匹配 (2)模式串
9．(1)其資料元素都是字元(2)順序儲存(3)和鏈式儲存(4)串的長度相等且兩串中對應位置的字元也相等
10．兩串的長度相等且兩串中對應位置的字元也相等。
11．』xyxyxywwy』 12．*s++=*t++ 或（*s++=*t++）!=『\0』
13．（1）char s2) j3) i >= j
14．[題目分析]本題演算法採用順序儲存結構求串s和串t的最大公共子串。串s用i指標（1<=i<=s.len）。
t串用j指標（1<=j<=t.len）。演算法思想是對每個i（1<=i<=s.
len，即程式中第乙個while迴圈），來求從i開始的連續字串與從j（1<=j<=t.len，即程式中第二個ｗhile迴圈）開始的連續字串的最大匹配。程式中第三個（即最內層）的while迴圈，是當s中某字元（s［i］）與t中某字元（t［j］）相等時，求出區域性公共子串。
若該子串長度大於已求出的最長公共子串（初始為０），則最長公共子串的長度要修改。
程式（a）：（1）（i+k<=s.len）and(j+k<=t.len) and(s[i+k]=t[j+k])
如果在s和t的長度內，對應字元相等，則指標k 後移（加1）。
2）con:=false //s和t對應字元不等時置標記退出
3）j:=j+k //在t串中，從第j+k字元再與s[i]比較
4）j:=j+1 //t串取下一字元
（5）i：=i+1 //s串指標i後移（加1）。
程式（b）：(1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] //所有注釋同上（a）
2) con=0 (3) j+=k (4) j++ (5) i++
15．（1）0 （2）next[k]
16．（1）i：=i+1 （2）j:=j+1 (3)i:=i-j+2 (4)j:=1; (5)i-mt（或i:=i-j+1） (6)0
17.程式中遞迴呼叫
（1）ch1<>midch //當讀入不是分隔符&和輸入結束符$時，繼續讀入字元
（2）ch1=ch2 //讀入分隔符&後，判ch1是否等於ch2，得出真假結論。
（3）answer：=true
（4）answer：=false
（5）read（ch）
（6）ch=endch
18．（1）initstack（s） /／棧s初始化為空棧。
(2) setnull (exp) //串exp初始化為空串。
(3) ch in opset //判取出字元是否是操作符。
(4) push (s,ch如ch是運算子，則入運算子棧s。
(5) sempty (s判棧s是否為空。
(6) succ := false //若讀出ch是運算元且棧為空，則按出錯處理。
(7) exp8)ch //若ch是運算元且棧非空，則形成部分中綴表示式。
(9) exp10) gettop(s) //取棧頂操作符。
(11) pop(s操作符取出後，退棧。
(12) sempty(s將pre的最後乙個字元（運算元）加入到中綴式exp的最後。
四．應用題
１．串是零個至多個字元組成的有限序列。從資料結構角度講，串屬於線性結構。與線性表的特殊性在於串的元素是字元。
２．空格是乙個字元，其ascii碼值是32。空格串是由空格組成的串，其長度等於空格的個數。空串是不含任何字元的串，即空串的長度是零。
３．最優的t(m,n)是o（n）。串s2是串s1的子串，且在s1中的位置是1。開始求出最大公共子串的長度恰是串s2的長度，一般情況下，t(m,n) =o(m*n)。
４．樸素的模式匹配（brute－force）時間複雜度是ｏ（m＊n），kmp演算法有一定改進，時間複雜度達到ｏ（m＋n）。本題也可採用從後面匹配的方法，即從右向左掃瞄，比較６次成功。另一種匹配方式是從左往右掃瞄，但是先比較模式串的最後乙個字元，若不等，則模式串後移；若相等，再比較模式串的第乙個字元，若第乙個字元也相等，則從模式串的第二個字元開始，向右比較，直至相等或失敗。
若失敗，模式串後移，再重複以上過程。按這種方法，本題比較18次成功。
５．kmp演算法主要優點是主串指標不回溯。當主串很大不能一次讀入記憶體且經常發生部分匹配時，kmp演算法的優點更為突出．
６．模式串的next函式定義如下：
next［j］=
根據此定義，可求解模式串t的next和nextval值如下：
7．解法同上題6，其next和nextval值分別為***和010*******。
8．解法同題6，t串的next和nextval函式值分別為0111232和0110132。
9．解法同題6，其next和nextval 值分別為***和011013020131。
10．p1的next和nextval值分別為：0112234和0102102；p2的next和nextval值分別為：0121123和0021002。
11．next陣列值為011234567 改進後的next陣列資訊值為010101017。
12．011122312。
13．next定義見題上面6和下面題20。串p的next函式值為：01212345634。
14．（1）s的next與nextval值分別為***和002002002009，p的next與nextval值分別為012123和002003。
（2）利用bf演算法的匹配過程利用kmp演算法的匹配過程：
第一趟匹配： aabaabaabaac第一趟匹配：aabaabaabaac
aabaac(i=6,j=6aabaac(i=6,j=6)
第二趟匹配： aabaabaabaac第二趟匹配：aabaabaabaac
aa(i=3,j=2aa)baac
第三趟匹配： aabaabaabaac第三趟匹配：aabaabaabaac
a(i=3,j=1成功) (aa)baac
第四趟匹配： aabaabaabaac
aabaac(i=9,j=6)
第五趟匹配： aabaabaabaac
aa(i=6,j=2)
第六趟匹配： aabaabaabaac
a(i=6,j=1)
第七趟匹配： aabaabaabaac
(成功aabaac(i=13,j=7)
15．（1）p的nextval函式值為0110132。（p的next函式值為0111232）。
（2）利用kmp(改進的nextval)演算法，每趟匹配過程如下：
第一趟匹配： abcaabbabcabaacbacba
abcab(i=5,j=5)
第二趟匹配： abcaabbabcabaacbacba
abc(i=7,j=3)
第三趟匹配： abcaabbabcabaacbacba
a(i=7,j=1)
第四趟匹配： abcaabbabcabaac bacba
(成功abcabaa(i=15,j=8)
16．kmp演算法的時間複雜性是o（m+n）。
p的next和nextval值分別為***和01102201320。
17．（1）p的nextval函式值為01010。（next函式值為01123）
（2）利用所得nextval數值，手工模擬對s的匹配過程，與上面16題類似，為節省篇幅，故略去。
18．模式串t的next和nextval值分別為0121123和0021002。
資料結構第四章串習題及答案
一 單項選擇題 1 下面關於串的的敘述中，哪乙個是不正確的？a 串是字元的有限序列b 空串是由空格構成的串 c 模式匹配是串的一種重要運算 d 串既可以採用順序儲存，也可以採用鏈式儲存 2 串是一種特殊的線性表，其特殊性體現在 a 可以順序儲存b 資料元素是乙個字元 c 可以鏈結儲存d 資料元素可以...
資料結構複習第四章串
第四章串 string 重點 掌握串的基本概念，掌握串的基本操作 掌握串的三種不同的儲存方式。難點 掌握串的三種不同的儲存方式。學習提要 1.熟悉串的七種基本操作的定義，並能利用這些基本操作來實現串的其它各種操作的方法。2.熟練掌握在串的定長順序儲存結構上實現串的各種操作的方法。3.掌握串的堆儲存結...
資料結構第四章
第四章串 4.1 串及其運算 1.串的基本概念 串 string 串是大於等於零個字元的有限序列，記為s a1a2 an 其中s為串名，ai可以是字母 數字或其它字元，n為長度，當n 0時稱為空串。例如 a this is a string b is 主串，子串，串常量，串變數。2.串的基本運算 運...