【正文】 (6) succ := false //若讀出ch是操作數且棧為空，則按出錯處理?！　?12) sempty(s)　 //將pre的最后一個字符（操作數）加入到中綴式exp的最后。與線性表的特殊性在于串的元素是字符?！。常顑?yōu)的T(m,n)是O（n）。本題也可采用從后面匹配的方法，即從右向左掃描，比較６次成功?！。担甂MP算法主要優(yōu)點是主串指針不回溯。10．p1的next和nextval值分別為：0112234和0102102；p2的next和nextval值分別為：0121123和0021002。串p的next函數值為：01212345634。（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）。18．模式串T的next和nextval值分別為0121123和0021002。20．（1）當模式串中第一個字符與主串中某字符比較不等（失配）時，next[1]=0表示模式串中已沒有字符可與主串中當前字符s[i]比較，主串當前指針應后移至下一字符，再和模式串中第一字符進行比較。進行模式匹配時，若主串第i個字符與模式串第j個字符發(fā)生失配，主串指針i不回溯，和主串第i個字符進行比較的是模式串的第next[j]個字符。22．失敗函數（即next）的值只取決于模式串自身，若第j個字符與主串第i個字符失配時，假定主串不回溯，模式串用第k（即next[j]）個字符與第i個相比，有‘ p1…pk1’=‘pjk+1…pj1’，為了不因模式串右移與主串第i個字符比較而丟失可能的匹配，對于上式中存在的多個k值，應取其中最大的一個。（4）兩串中一個串長是另一個串長（包括串長為1僅有一個字符的情況）的數倍，而且長串就好象是由數個短串經過連接操作得到的。模式匹配從s0和t0開始，若s0=t0，則i和j指針增加1，若在某個位置si!=tj，則主串指針i回溯到i=ij+1，j仍從0開始，進行下一輪的比較，直到匹配成功（jn1），返回子串在主串的位置（ij）。{int i=0,j=0。j++。} //對應字符不相等，I回溯，j仍為0。return(in+1)。 scanf(“%d%d”,amp。 //輸入主串 scanf(“%s”,t)。失敗的情況是s串的第mn個字符比t串某字符比較失敗，時間復雜度為o（m*n）。2.［問題分析］在一個字符串內，統計含多少整數的問題，核心是如何將數從字符串中分離出來。｛int i=0，a[]； // 整數存儲到數組a，i記整數個數　scanf（“％c”，amp。ch）；　　　 ｝　　　a[i]=num；i++；　　　if（ch!=‘’）scanf（“%c”，amp。{int index=0,max=0。} else //上一個重復子串結束 {if(maxlength) {max=length。length=1。子串長度的初值數為1，表示一個字符自然等于其身。因為已經給定順序存儲結構，我們可將s串從第（i+j1）到串尾（）（以便將t串插入）：若j，則向左移；若j，則向右移動；若j=，則不必移動。{if(i1 || j0 || +maxlen) {printf(“參數錯誤\n”)。k=i+j1。k=。k++) [i1+k]=[k]。最后將s1串復制到s。 //將s1第i個字符前的子串復制到s1，這時k=i1for(k=0。ki1+j。k++) [k]=[k]。本算法不指定存儲結構，只使用串的基本運算。 //creat操作是將串常量（此處為空串）賦值給temp。//用串v替換t形成部分結果 assign(s,substr(s,i+m,nim+1))。 //將串temp和剩余的串s連接后再賦值給s}//if結束}//算法結束[題目分析]本題是字符串的插入問題，要求在字符串s的pos位置，插入字符串t。{int i=1,x=0。}while(*p!=’\0’amp。} //查pos位置 //若pos小于串s長度，則查到pos位置時，i=pos。exit(0)。 i++。) {q++。 for(j=i。}//串s的pos后的子串右移，空出串t的位置。j++) *p=*q。6.[題目分析]本題屬于查找，待查找元素是字符串（長4），將查找元素存放在一維數組中。非遞歸過程如下：int binsearch(node string []。{int low = 0,high = n 1。 //到右半部分檢索else high=mid1。39。long atoi(char X[]) //一數字字符串存于字符數組X中，本算法將其轉換成數{long num=0。) num=10*num+(X[i++]39。39。)*10+num)。039。算法從左到右掃描字符串s1，找到第一個非空格字符，計數到n，第n個拷入字符串s2的字符不得為空格，然后將余下字符復制到字符串s3中。\039。 39。) {printf(字符串s1為空串或空格串\n)。 amp。 p++。){ printf(字符串s1沒有%d個有效字符\n,n)。 ) //若最后一個字符為空格，則需向后找到第一個非空格字符 {p 。amp。//往后查找一個非空格字符作串s2的尾字符 if(*p==39。 } *q=*p。p++。) {*q=*p。\039。for (i=0。 //兩串相等}//算法結束10.［問題分析］由于字母共26個，加上數字符號10個共36個，所以設一長36的整型數組，前10個分量存放數字字符出現的次數，余下存放字母出現的次數。｛int i，num[36]；char ch；　for（i＝0；i36；i++）num[i]＝０；// 初始化　while（（ch＝getchar（））!=‘’） //‘’表示輸入字符串結束。11.[題目分析]實現字符串的逆置并不難，但本題“要求不另設串存儲空間”來實現字符串逆序存儲，即第一個輸入的字符最后存儲，最后輸入的字符先存儲，使用遞歸可容易做到。//需要使用靜態(tài)變量scanf (%c,amp。) //規(guī)定39。//字符串逆序存儲 }A[i] = 39。39。和 39。39。 。求串s1在串s中的起始位置s1=substr(s,i,length(s) i + 1)。 //求串s39。后是39。13．[題目分析]對讀入的字符串的第奇數個字符，直接放在數組前面，對第偶數個字符，先入棧，到讀字符串結束，再將棧中字符出棧，送入數組中。 //s和stk是字符數組（表示字符串）和字符棧 int i=1,j。j=1。 }//while i。算法思想是從左到右掃描表達式，對讀出的字符，先查出其符號類碼：若是變量或常量，就到變量名表和常量表中去查是否已有，若無，則在相應表中增加之，并返回該字符在變量名表或常量表中的下標；若是操作符，則去查其符號類碼。struct // 定義符號類別數據結構 {char data[7]。 while（ch！=‘’） /