【正文】 { temp=(datatype*)malloc(sizeof(datatype))。 sqquelen。 *temp=sqsequ[(sqrearsqquelen+m)%m]。 return (temp)。 //隊列非空時，將隊頭元素出隊 } } 運行結果 存在的問題 注意隊空和隊滿時的情況即可。 7 實驗五、模式匹配 問題的提出 串采用順序存儲結構，編寫樸素模式匹配算法，查找在串中是否存在 給定的子串。 算法分析 Step1：從位序為 1 時開始將其與目標串進行匹配； Step2：當一趟的字符串完全匹配時，返回 iTlen，匹配成功；否則返回 1，匹配失敗。 問題的程序代碼 //順序串的樸素模式匹配 int Index(seqstring*S, seqstring*T) { int i=1,j=1。 //位序從 1 開始 while(i=Slenamp。amp。j=Tlen) if(Sstr[i1]==Tstr[j1]) { i++。 j++。 } //繼續(xù)比較后面的字符 else { i=ij+2。 j=1。 } //本趟不匹配，設置下一趟匹配的起始位序 if(jTlen) return(iTlen)。 //匹配成功 else return(1)。 //匹配不成功 } 運行結果 ? 匹配成功時的結果 ? 匹配失敗時的結果 8 存在的問題 未發(fā)現(xiàn)問題的存在。 實驗六、刪除子串 問題的提出 若 S 是一個采用順序結構 存儲的串，利用 C 的庫函數(shù) strlen 和 strcpy（或strncpy）編寫一算法 void SteDelete(char*S,int I,int m)，要求從 S 中刪除從第 i個字符開始的連續(xù) m個字符。若 i≥strlen(S)，則沒有字符被刪除；若 i+m≥strlen(S)，則將 S 中從位置 i開始直至末尾的字符均刪除。 算法分析 Step1：先建立一個存儲數(shù)組，并將串中的前 i個字符進行復制到 temp 中； Step2：串 S 中除去要求刪除的 m 個字符，把后面的字符連接到 temp 中； Step3： 將 temp 中的字符 復制到 S 中，并修改字符串長度加 1。 問題的程序代碼 //刪除子串 void strDelete(seqstring*S,int i,int m) { char temp[maxsize]。 //建立存儲數(shù)組 if(i=Slen){ strncpy(temp,Sstr,i1)。 //把串 S 的前 i個字符復制到 temp 中 strcpy(temp+i1,Sstr+i+m1)。 //串 S 中除要刪除的 m個字符，把后面的字符連接到 temp 中 strcpy(Sstr,temp)。 // temp 中的字符復制到 S 中 if(i=Slen) if(i+m1=Slen) Slen=Slenm。 else Slen=Sleni+1。 //修改字符串長度加 1 } } 運行結果 9 存在的問題 未發(fā)現(xiàn)問題。 實驗七、找 馬鞍點 問題的提出 若在矩陣 Amn 中存在一個元素 A[i][j]，其滿足 A[i][j]是第 i行元素中最小值，且又是第 j 列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。用二維數(shù)組存儲矩陣 Amn ，設計算 法求出矩陣中所有馬鞍點。 算法分析 Step1：先分別找出 m行的最小值； Step2：再分別找出 n 行的最大值； Step3：若 Step1 和 Step2 存在相等的位置，則是一個馬鞍點；否則不存在馬鞍點。 問題的程序代碼 //找馬鞍點 void minmax(array*p) //找馬鞍點 { int i,j,have=0。 for (i=1。i=m。i++) { pmin[i]=pA[i][1]。 for(j=2。j=n。j++) if(pA[i][j]pmin[i]) pmin[i]=pA[i][j]。 }//分別找出 m行的最小值 for(j=1。j=n。j++) { pmax[j]=pA[1][j]。 for(i=2。i=m。i++) if(pA[i][j]pmax[j]) pmax[j]=pA[i][j]。 }//分別找出 n行的最大值 for(i=1。i=m。i++) for(j=1。j=n。j++) if(pmin[i]==pmax[j])//若相等，則是一個馬鞍點 10 { printf(\n 馬鞍點為： %d\n 位置為： (%d,%d)\n,pA[i][j],i,j)。//輸出馬鞍點 have=1。 } if(!have) printf(矩陣中沒有馬鞍點 !)。 } 運行結果 ? 存在 馬鞍點的結果 ? 不存在 馬鞍點的結果 存在的問題 注意不存在馬鞍點的判斷，即不存在列最小值和行最大值共同存在的情況。 實驗八、對稱矩陣相乘 問題的提出 A 和 B 是兩個 n n階的對稱矩陣，以行為主序輸入對稱矩陣的下三角元素，壓縮存儲存入一維數(shù)組 A 和 B，編寫一個算法計算對稱矩陣 A 和 B 的乘積，結果存入二維數(shù)組 C。 算法分析 Step1：對稱存儲 A， B 的下三角矩陣； Step2：將對稱存儲 A， B 的下三角矩陣進行相乘并將其存儲在矩陣 C 中。 11 問題的程序代碼 //對稱矩陣相乘 void mult(array*p) { int i,j,k,t1,t2。 datatype s。 for(i=0。in。i++) for(j=0。jn。j++) { s=0。 for(k=0。kn。k++)//對稱存儲 A， B 的下三角矩陣 { if(i=k)t1=i*(i+1)/2+k。 else t1=k*(k+1)/2+i。 if(k=j)t2=k*(k+1)/2+j。 else t2=j*(j+1)/2+k。 s=s+pA[t1]*pB[t2]。 } pC[i][j]=s。 } } 運行結果 存在的問題 注意如何 存儲對稱的 A， B 的下三角矩陣的方式。 實驗九、交換 左右二叉子樹 問題的提出 已知二叉樹采用二叉鏈表存儲結構，如果左、右子樹非空，且左子樹根結點大于右子樹根結點，則交換根結點的左、右子樹。即按要求交換二叉樹及子樹的左、右子樹。 12 算法分析 Step1：先判斷是否遍歷根結點及子樹的左、右子樹，是，轉 Step2； Step2：交換根結點及子樹的左、右子樹，并得出左、右子樹的標志變量。 問題的程序代碼 //交換左右子樹 void swap(bitree*p) { bitree*t。 if(p!=NULL) { if(plchild!=NULLamp。amp。prchild!=NULL amp。amp。plchilddataprchilddata) //遍歷根結點及子樹的左、右子樹 { t=plchild。 plchild=prchild。 prchild=t。 }//交換根結點及子樹的左、右子樹 swap(plchild)。 swap(prchild)。 //得出左、右子樹的標志變量 } } 運行結果 存在的問題 左右子樹與根結點要確定遍歷，之后交換左 右子樹即可。