【正文】 ) { temp=r[i]。//設(shè)置 T 個(gè)監(jiān)視哨 k=0。 int maxint=32767。 實(shí)驗(yàn)十二、希爾排序 問題的提出 采用希爾排序方法對(duì)順序表中的證型數(shù)據(jù)進(jìn)行排序，設(shè)計(jì)希爾排序算法并顯示每趟排序的結(jié)果。j++) if((garcs[i][j]==1)amp。 printf(出發(fā)點(diǎn) %c\n,gvexs[i])。 } 運(yùn)行結(jié)果 存在的問題 統(tǒng)計(jì)結(jié)點(diǎn)總數(shù)時(shí) 要確定遍歷完全部的結(jié)點(diǎn)，并且 統(tǒng)計(jì)葉子結(jié)點(diǎn)總數(shù)要確定左右葉子個(gè)子樹的完全統(tǒng)計(jì)。amp。} //遍歷根結(jié)點(diǎn)及子樹的左、右子樹 return n。 問題的程序代碼 //統(tǒng)計(jì)結(jié)點(diǎn)總數(shù) int countleaf(bitree *p) { static int n=0。 swap(prchild)。plchilddataprchilddata) //遍歷根結(jié)點(diǎn)及子樹的左、右子樹 { t=plchild。 if(p!=NULL) { if(plchild!=NULLamp。 實(shí)驗(yàn)九、交換 左右二叉子樹 問題的提出 已知二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，如果左、右子樹非空，且左子樹根結(jié)點(diǎn)大于右子樹根結(jié)點(diǎn)，則交換根結(jié)點(diǎn)的左、右子樹。 else t2=j*(j+1)/2+k。kn。i++) for(j=0。 11 問題的程序代碼 //對(duì)稱矩陣相乘 void mult(array*p) { int i,j,k,t1,t2。 } if(!have) printf(矩陣中沒有馬鞍點(diǎn) !)。i++) for(j=1。i=m。 }//分別找出 m行的最小值 for(j=1。i++) { pmin[i]=pA[i][1]。 算法分析 Step1：先分別找出 m行的最小值； Step2：再分別找出 n 行的最大值； Step3：若 Step1 和 Step2 存在相等的位置，則是一個(gè)馬鞍點(diǎn)；否則不存在馬鞍點(diǎn)。 else Slen=Sleni+1。 //建立存儲(chǔ)數(shù)組 if(i=Slen){ strncpy(temp,Sstr,i1)。 實(shí)驗(yàn)六、刪除子串 問題的提出 若 S 是一個(gè)采用順序結(jié)構(gòu) 存儲(chǔ)的串，利用 C 的庫函數(shù) strlen 和 strcpy（或strncpy）編寫一算法 void SteDelete(char*S,int I,int m)，要求從 S 中刪除從第 i個(gè)字符開始的連續(xù) m個(gè)字符。 j=1。amp。 7 實(shí)驗(yàn)五、模式匹配 問題的提出 串采用順序存儲(chǔ)結(jié)構(gòu)，編寫樸素模式匹配算法，查找在串中是否存在 給定的子串。 sqquelen。//隊(duì)列未滿時(shí)，將 x入隊(duì)尾 } } //出隊(duì) datatype *dequeue(qu *sq) { datatype *temp。 問題的程序代碼 //入隊(duì) void enqueue(qu *sq, datatype x) { if(sqquelen==m) printf(queue is full\n)。 實(shí)驗(yàn)四、循環(huán)隊(duì)列 問題的提出 假設(shè)以數(shù)組 sequ[m]存放 循環(huán)隊(duì)列的元素，同時(shí)設(shè)變量 rear 和 quelen 分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。 if(j!=pdata) //j 與 p 中的元素不相等時(shí)返回 1 return 1。i++) //當(dāng) p 非空時(shí)，將一半字符串入棧 {push(s,pdata)。 n=length(head)。（提示：將單鏈表中的一半字符先依次進(jìn)棧，然后依次出棧與單鏈表中的另一半字符進(jìn)行比較。939。039。pdata=39。)||(pdata=39。amp。 while(headnext!=NULL) { p=headnext。//原鏈表的第一個(gè)結(jié)點(diǎn)指針置空，變?yōu)樾骆湵淼奈步Y(jié)點(diǎn) headnext=p。 qnext=p。 問題的程序代碼 //單鏈表逆置 void invert(linklist *head) { linklist *p,*q,*r。i++)//for 循環(huán)語句，其中的 Llast/2 當(dāng) Llast 為奇數(shù)時(shí)，相當(dāng)于向下取整 {temp=Ldata[i]。 問題的程序代碼 //順序表逆置 void invert(sequenlist*L) { int i。 ? 順序表逆置 算法分析 Step1： 將順序表位置 i的元素與位置 Llasti+1 的元素進(jìn)行互換； Step2： 重復(fù) Step1，直到 i=Llast/2，結(jié)束 。i=Llast/2。//將位置 i和位置 Llasti+1 的元素進(jìn)行互換 } } 運(yùn)行結(jié)果 存在的問題 逆置表中的元素只能是單個(gè)元素，不能進(jìn)行多位數(shù)的逆置，如下圖所示 2 ? 單鏈表逆置 算法分析 Step1： 將 p 指針指向頭結(jié)點(diǎn)， q 指針指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)； Step2：將 p 和 q 逆置，并將它們分別后移一個(gè)結(jié)點(diǎn)； Step3：重復(fù) Step1~ Step2，直到指針 r 指向空域，結(jié)束。 //q 指針指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) while(q!=NULL)//當(dāng) q 指針非空時(shí)，進(jìn)行 while 循環(huán) {r=qnext。//將 p 指針指向 q， q 指針指向 r，實(shí)現(xiàn) p 和 q 的逆置 } headnextnext=NULL。 問題的程序代 碼 //按字母、數(shù)字、其它字符分解單鏈表 void resolve(linklist*head,linklist*letter,linklist*digit,linklist*other) { linklist *p。A39。Z39。amp。 //判斷字符是否在 [A,Z]或者 [a,z]之間，是，插入第一個(gè)單鏈表中 else if(pdata=39。pdata=39。 //判斷字符是否在 [0,9]，是，插入第二個(gè)單鏈表中；否，插入第三個(gè)單鏈表中 } } 4 運(yùn)行結(jié)果 存在的問題 此處的其他字符還包括了子母和數(shù)字以外的一切 字符，且此處的數(shù)字不能為多位數(shù)或者字符串，本程序不能識(shí)別 10 以上的數(shù)字及一個(gè)單詞的字符串，如下圖所示 實(shí)驗(yàn)三、判斷字符串是否中心對(duì)稱 問題的提出 設(shè)單鏈表中存放有 n個(gè)字符，試編寫算法，判斷該字符串是否有中心對(duì)稱的關(guān)系，例如 xyzzyx 是中心對(duì)稱的字符串。 linklist*p=headnext。in/2。 //若字符串長度是奇 數(shù)，指針 p 從向后移一位 while(p!=NULL) //判斷字符串出棧與另外一半字符串比較是否相等，相等返回 1，否則返回 0 {j=pop(s)。 } 運(yùn)行結(jié)果 ? 字符串不是中心對(duì)稱時(shí)結(jié)果 ? 字符串是中心對(duì)稱時(shí)結(jié)果 存在的問題 注意字符串長度為奇數(shù)時(shí)的判定即可。 算法分析 Step1：先進(jìn)行入隊(duì)操作，判斷是否隊(duì)滿，隊(duì)未滿時(shí)將 x 入隊(duì)尾； 6 Step2：再進(jìn)行出隊(duì)操作，判斷是否隊(duì)空，隊(duì)列非空時(shí)將隊(duì)頭元素出隊(duì) 。 sqsequ[sqrear]=x。} //隊(duì)列 為空 else { temp=(datatype*)malloc(sizeof(datatype))。 //隊(duì)列非空時(shí)，將隊(duì)頭元素出隊(duì) } } 運(yùn)行結(jié)果 存在的問題 注意隊(duì)空和隊(duì)滿時(shí)的情況即可。 //位序從 1 開始 while(i=Slenamp。 } //繼續(xù)比較后面的字符 else { i=ij+2。 //匹配不成功 } 運(yùn)行結(jié)果 ? 匹配成功時(shí)的結(jié)果 ? 匹配失敗時(shí)的結(jié)果 8 存在的問題 未發(fā)現(xiàn)問題的存在。