20xx級算法與數據結構實驗指導書-資料下載頁
2025-08-04 08:41本頁面
【正文】 2. 若結點p只有左子樹，則只需重接p的左子樹； 若結點p只有右子樹，則只需重接p的右子樹； 3. 若結點p的左右子樹均不空，則 查找結點p的右子樹上的最左下結點s以及結點s的雙親結點par； 將結點s數據域替換到被刪結點p的數據域； 若結點p的右孩子無左子樹，則將s的右子樹接到par的右子樹上；否則，將s的右子樹接到結點par的左子樹上； 刪除結點s；實驗四、排序技術綜合應用（九） 排序技術綜合應用實驗目的：（1）熟練掌握常用的排序方法，并掌握用高級語言實現排序算法的方法；（2）深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用；（3）了解各種方法的排序過程及其依據的原則，并掌握各種排序方法的時間復雜度的分析方法。實驗內容：對希爾排序、快速排序、歸并排序任意選擇兩種排序方法進行比較。任意選擇希爾排序、快速排序、歸并排序中兩種排序方法，對任意給定一組數據：單增、單減、亂碼等，對它們進行比較分析。 實驗說明： 希爾排序算法如下：void ShellSort(int r[ ], int n){ for (d=n/2。 d=1。 d=d/2) //以增量為d進行直接插入排序{ for (i=d+1。 i=n。 i++) { r[0]=r[i]。 //暫存被插入記錄 for (j=id。 j0 amp。amp。 r[0]r[j]。 j=jd) r[j+d]=r[j]。 //記錄后移d個位置 r[j+d]=r[0]。}} } 快速排序算法偽碼如下：void QuickSort(int r[ ], int first, int end){ if (firstend) { //遞歸結束 pivot=Partition(r, first, end)。 //一次劃分 QuickSort(r, first, pivot1)。 //遞歸地對左側子序列進行快速排序 QuickSort(r, pivot+1, end)。 //遞歸地對右側子序列進行快速排序 }}int Partition(int r[ ], int first, int end){ i=first。 j=end。 //初始化while (ij) { while (ij amp。amp。 r[i]= r[j]) j。 //右側掃描 if (ij) { r[i]←→r[j]。 //將較小記錄交換到前面 i++。 } while (ij amp。amp。 r[i]= r[j]) i++。 //左側掃描if (ij) { r[j]←→r[i]。 //將較大記錄交換到后面 j。 }}retutn i。 //i為軸值記錄的最終位置}修訂者：蔡瓊2014211
研究報告相關推薦
鄂ICP備17016276號-1