【文章內(nèi)容簡介】 實驗十、統(tǒng)計二叉樹的結(jié)點 問題的提出 采用二叉鏈表結(jié)構(gòu)存儲一棵二叉樹，編寫一個算法統(tǒng)計該二叉樹中結(jié)點總數(shù)及葉子結(jié)點總數(shù)。 13 算法分析 Step1：先統(tǒng)計結(jié)點總數(shù)，利用結(jié)點的遍歷使其結(jié)點數(shù)加 1 的方法即可； Step2：再統(tǒng)計葉子結(jié)點總數(shù)，分別統(tǒng)計左、右子樹中葉子結(jié)點個數(shù)，相加即得出葉子結(jié)點總數(shù) leaf。 問題的程序代碼 //統(tǒng)計結(jié)點總數(shù) int countleaf(bitree *p) { static int n=0。 //n 為結(jié)點個數(shù) if(p!=NULL) {n++。 //每遍歷一個結(jié)點， n 加 1 countnode(plchild)。 countnode(prchild)。} //遍歷根結(jié)點及子樹的左、右子樹 return n。 } //統(tǒng)計葉子結(jié)點總數(shù) static int leaf =0。 if(p!=NULL) { leaf = countleaf( plchild )。 //統(tǒng)計左子樹中葉子結(jié)點個數(shù) if ((plchild==NULL)amp。amp。(prchild==NULL)) leaf=leaf+1。 leaf=countleaf(prchild)。 //統(tǒng)計右子樹中葉子結(jié)點個數(shù) } return leaf。 } 運行結(jié)果 存在的問題 統(tǒng)計結(jié)點總數(shù)時 要確定遍歷完全部的結(jié)點，并且 統(tǒng)計葉子結(jié)點總數(shù)要確定左右葉子個子樹的完全統(tǒng)計。 14 實驗十一、無向圖鄰接矩陣 問題的提出 無向圖采用鄰接矩陣存儲，編寫深度優(yōu)先搜索遍歷算法，從不同的頂點出發(fā)對無向圖進行遍歷。 算法分析 Step1：確定出發(fā)點為 iv ，開始進行深度優(yōu) 先搜索； Step2：當(dāng)被訪問過時，利用 visited[i]=1 進行標(biāo)記； Step3：并從未被訪問的鄰接點 jv 出發(fā)進行深度優(yōu)先搜索遍歷即可。 問題的程序代碼 //添加深度優(yōu)先搜索遍歷算法 void dfsa(int i) {int j。 printf(出發(fā)點 %c\n,gvexs[i])。 //從出發(fā)點為 iv 開始進行深度優(yōu)先搜索 visited[i]=1。 //標(biāo)記 iv 已被訪問 for(j=0。jn。j++) if((garcs[i][j]==1)amp。amp。(visited[j]==0)) dfsa(j)。 }//從未被訪問的鄰接點 jv 出發(fā)進行深度優(yōu)先搜索遍歷 15 運行結(jié)果 存在的問題 注意確定開始進行深度優(yōu)先搜索的出發(fā)點為 iv ，并且標(biāo)記 iv 已被訪問和從未被訪問的鄰接點 jv 的確定。 實驗十二、希爾排序 問題的提出 采用希爾排序方法對順序表中的證型數(shù)據(jù)進行排序，設(shè)計希爾排序算法并顯示每趟排序的結(jié)果。 16 算法分析 Step1：先設(shè)置 T 個監(jiān)視哨，并且每一趟增加相應(yīng)的常量； Step2：通過 Step1 設(shè)置不同的常量，可得出輸出一趟的排序結(jié)果，結(jié)束。 問題的程序代碼 //希爾排序 void shellsort(rectype r[],int d[]) { int i,j,k,h。 rectype temp。 int maxint=32767。 for(i=0。iD1。i++) r[i].key=maxint。//設(shè)置 T 個監(jiān)視哨 k=0。 do{ h=d[k]。//取一趟的增量 for(i=h+D1。iN+D1。i++) { temp=r[i]。 j=ih。 while(r[j].key) { r[j+h]=r[j]。 j=jh。 } r[j+h]=temp。 }//組內(nèi)直接插入法排序 print(r,N)。//輸出一趟的排序結(jié)果 k++。 }while(h!=1)。 } 運行結(jié)果 17 存在的問題 希爾排序要注意設(shè)置適當(dāng)?shù)脑黾拥某Ａ浚瑥亩鴾p少時間的復(fù)雜度。 實驗十三、雙向起泡排序 問題的提出 編寫一個雙向起泡的排序算法，即在排序過程中交替改變掃描方向，同時顯示各趟排序的結(jié)果。 算法分析 Step1：先設(shè)置交換標(biāo)志為假，進行 n1 趟的排序?qū)⒆畲蟮牧窟M行“下沉”； Step2：再后移一個數(shù)，重復(fù) Step1，直到得到的結(jié)果為從小到大排好序的結(jié)果，結(jié)束。 問題的 程序代碼 //雙向起泡排序 void dbubblesort(sequenlist r[],int n) { int i=1,j,noswap=1。 sequenlist temp。 while(noswap){ noswap=0。//交換標(biāo)志設(shè)為假 for(j=ni+1。j=i+1。j)//最多進行 n1 趟的排序 if(r[j].keyr[j1].key) { noswap=1。 temp=r[j]。 r[j]=r[j1]。 r[j1]=temp。 }//將最大的量進行“下沉” for(j=i+1。j=ni。j++)//最多進行 n2i+1 趟的排序 if(r[j].keyr[j+1].key) { noswap=1。 temp=r[j]。 r[j]=r[j+1]。 r[j+1]=temp。 }//將最大的量進行“下沉” for(int k=1。k=n。k++) printf(%5d,r[k].key)。 printf(\n)。 18 i++。 }//輸出排序后的結(jié)果 } 運行結(jié)果 存在的問題 一次掃描可以將最重的“氣泡”進行“下沉”，而當(dāng)進行上浮時比較簡單時應(yīng)利用上浮進行排序，這比較難以判定。 實驗十四、分塊查找 問題的提出 18 個記錄的關(guān)鍵字為 2 1 1 3 4 4 3 2 460、 5 7 4 8 53，編寫分塊查找的算法進行查找。 算法分析 Step1：在索引表較大時，應(yīng)先利用折半查找的方法確定關(guān)鍵字所在的塊； Step2：再利用順序查找的方法即可查 找出關(guān)鍵字所在的確定位置即可。 問題的程序代碼 //分塊查找 int blksearch(record r[],index idx[],keytype k,int n) { int i,low=0,high=n1,mid,bh,find=0。 //折半查找索引表 while(low=highamp。amp。!find) { mid=(low+high)/2。 if(kidx[mid].key)high=mid1。 else if(kidx[mid].key)low=mid+1。 else { high=mid1。 19 find=1。 } } if(lown) { i=idx[low].low。//塊的起始地址 bh=idx[low].high。//塊的終止地址 } //塊內(nèi)順序查找 while(ibhamp。amp。r[i].key!=k)i++。 if(r[i].key!=k)i=1。 return i。 } 運行結(jié)果 存在的問題 在索引表較大，分塊查找先利用折半查找方法可大大的簡化步驟 ，之后利用順序查找即可得出，分塊查找結(jié)合了折半查找和順序查找的優(yōu)點，有較廣泛的應(yīng)用。 實驗十五、判斷二叉排序樹 問題的提出 編寫一個判別給定的二叉樹是否為二叉排序樹的算法，設(shè)二叉樹以二叉鏈表存儲表示，結(jié)點的數(shù)據(jù)域只存放正整數(shù)。 20 算法分析 Step1：先判斷二叉樹的左子樹的值是否均小于相應(yīng)的根結(jié)點的值，否，不是二叉排序樹，是，轉(zhuǎn) Step2； St