【正文】 53，編寫分塊查找的算法進行查找。 18 i++。k++) printf(%5d,r[k].key)。 }//將最大的量進行“下沉” for(int k=1。 r[j]=r[j+1]。j++)//最多進行 n2i+1 趟的排序 if(r[j].keyr[j+1].key) { noswap=1。 }//將最大的量進行“下沉” for(j=i+1。 r[j]=r[j1]。j)//最多進行 n1 趟的排序 if(r[j].keyr[j1].key) { noswap=1。//交換標(biāo)志設(shè)為假 for(j=ni+1。 sequenlist temp。 算法分析 Step1：先設(shè)置交換標(biāo)志為假，進行 n1 趟的排序?qū)⒆畲蟮牧窟M行“下沉”； Step2：再后移一個數(shù)，重復(fù) Step1，直到得到的結(jié)果為從小到大排好序的結(jié)果，結(jié)束。 } 運行結(jié)果 17 存在的問題 希爾排序要注意設(shè)置適當(dāng)?shù)脑黾拥某Ａ?，從而減少時間的復(fù)雜度。//輸出一趟的排序結(jié)果 k++。 } r[j+h]=temp。 while(r[j].key) { r[j+h]=r[j]。i++) { temp=r[i]。//取一趟的增量 for(i=h+D1。//設(shè)置 T 個監(jiān)視哨 k=0。iD1。 int maxint=32767。 問題的程序代碼 //希爾排序 void shellsort(rectype r[],int d[]) { int i,j,k,h。 實驗十二、希爾排序 問題的提出 采用希爾排序方法對順序表中的證型數(shù)據(jù)進行排序，設(shè)計希爾排序算法并顯示每趟排序的結(jié)果。(visited[j]==0)) dfsa(j)。j++) if((garcs[i][j]==1)amp。 //標(biāo)記 iv 已被訪問 for(j=0。 printf(出發(fā)點 %c\n,gvexs[i])。 算法分析 Step1：確定出發(fā)點為 iv ，開始進行深度優(yōu) 先搜索； Step2：當(dāng)被訪問過時，利用 visited[i]=1 進行標(biāo)記； Step3：并從未被訪問的鄰接點 jv 出發(fā)進行深度優(yōu)先搜索遍歷即可。 } 運行結(jié)果 存在的問題 統(tǒng)計結(jié)點總數(shù)時 要確定遍歷完全部的結(jié)點，并且 統(tǒng)計葉子結(jié)點總數(shù)要確定左右葉子個子樹的完全統(tǒng)計。 leaf=countleaf(prchild)。amp。 if(p!=NULL) { leaf = countleaf( plchild )。} //遍歷根結(jié)點及子樹的左、右子樹 return n。 //每遍歷一個結(jié)點， n 加 1 countnode(plchild)。 問題的程序代碼 //統(tǒng)計結(jié)點總數(shù) int countleaf(bitree *p) { static int n=0。 實驗十、統(tǒng)計二叉樹的結(jié)點 問題的提出 采用二叉鏈表結(jié)構(gòu)存儲一棵二叉樹，編寫一個算法統(tǒng)計該二叉樹中結(jié)點總數(shù)及葉子結(jié)點總數(shù)。 swap(prchild)。 prchild=t。plchilddataprchilddata) //遍歷根結(jié)點及子樹的左、右子樹 { t=plchild。prchild!=NULL amp。 if(p!=NULL) { if(plchild!=NULLamp。 12 算法分析 Step1：先判斷是否遍歷根結(jié)點及子樹的左、右子樹，是，轉(zhuǎn) Step2； Step2：交換根結(jié)點及子樹的左、右子樹，并得出左、右子樹的標(biāo)志變量。 實驗九、交換 左右二叉子樹 問題的提出 已知二叉樹采用二叉鏈表存儲結(jié)構(gòu)，如果左、右子樹非空，且左子樹根結(jié)點大于右子樹根結(jié)點，則交換根結(jié)點的左、右子樹。 } pC[i][j]=s。 else t2=j*(j+1)/2+k。 else t1=k*(k+1)/2+i。kn。j++) { s=0。i++) for(j=0。 for(i=0。 11 問題的程序代碼 //對稱矩陣相乘 void mult(array*p) { int i,j,k,t1,t2。 實驗八、對稱矩陣相乘 問題的提出 A 和 B 是兩個 n n階的對稱矩陣，以行為主序輸入對稱矩陣的下三角元素，壓縮存儲存入一維數(shù)組 A 和 B，編寫一個算法計算對稱矩陣 A 和 B 的乘積，結(jié)果存入二維數(shù)組 C。 } if(!have) printf(矩陣中沒有馬鞍點 !)。j++) if(pmin[i]==pmax[j])//若相等，則是一個馬鞍點 10 { printf(\n 馬鞍點為： %d\n 位置為： (%d,%d)\n,pA[i][j],i,j)。i++) for(j=1。 }//分別找出 n行的最大值 for(i=1。i=m。j++) { pmax[j]=pA[1][j]。 }//分別找出 m行的最小值 for(j=1。j=n。i++) { pmin[i]=pA[i][1]。 for (i=1。 算法分析 Step1：先分別找出 m行的最小值； Step2：再分別找出 n 行的最大值； Step3：若 Step1 和 Step2 存在相等的位置，則是一個馬鞍點；否則不存在馬鞍點。 實驗七、找 馬鞍點 問題的提出 若在矩陣 Amn 中存在一個元素 A[i][j]，其滿足 A[i][j]是第 i行元素中最小值，且又是第 j 列元素中最大值，則稱此元素為該矩陣的一個馬鞍點。 else Slen=Sleni+1。 //串 S 中除要刪除的 m個字符，把后面的字符連接到 temp 中 strcpy(Sstr,temp)。 //建立存儲數(shù)組 if(i=Slen){ strncpy(temp,Sstr,i1)。 算法分析 Step1：先建立一個存儲數(shù)組，并將串中的前 i個字符進行復(fù)制到 temp 中； Step2：串 S 中除去要求刪除的 m 個字符，把后面的字符連接到 temp 中； Step3： 將 temp 中的字符 復(fù)制到 S 中，并修改字符串長度加 1。 實驗六、刪除子串 問題的提出 若 S 是一個采用順序結(jié)構(gòu) 存儲的串，利用 C 的庫函數(shù) strlen 和 strcpy（或strncpy）編寫一算法 void SteDelete(char*S,int I,int m)，要求從 S 中刪除從第 i個字符開始的連續(xù) m個字符。 //匹配成功 else return(1)。 j=1。 j++。amp。 問題的程序代碼 //順序串的樸素模式匹配 int Index(seqstring*S, seqstring*T) { int i=1,j=1。 7 實驗五、模式匹配 問題的提出 串采用順序存儲結(jié)構(gòu)，編寫樸素模式匹配算法，查找在串中是否存在 給定的子串。 return (temp)。 sqquelen。 return NULL。//隊列未滿時，將 x入隊尾 } } //出隊 datatype *dequeue(qu *sq) { datatype *temp。 sqrear=(sqrear+1)%m。 問題的程序代碼 //入隊 void enqueue(qu *sq, datatype x) { if(sqquelen==m) printf(queue is full\n)。提示：隊空的條件： sqquelen==0；隊滿的條件： sqquelen==m。 實驗四、循環(huán)隊列 問題的提出 假設(shè)以數(shù)組 sequ[m]存放 循環(huán)隊列的元素，同時設(shè)變量 rea