1

1.雙向鏈表五、其它形式的鏈表typedefstructDuLNode{ElemTypedata;

//數據域

structDuLNode*prior;

//指向前驅的指針域

structDuLNode*next;

//

指向后繼的指針域}

DuLNode,*DuLinkList;2

最后一個結點的指針域的指針又指回第一個結點的鏈表a1a2…...an2.循環鏈表

和單鏈表的差別僅在于，判別鏈表中最后一個結點的條件不再是“后繼是否為空”，而是“后繼是否為頭結點”。3

在循環鏈表中，頭指針也可以改變到指向尾結點，這樣用一個頭指針就能夠控制首位兩端，可為有些操作帶來便利。a1a2…...an4雙向循環鏈表空表非空表a1a2…...an5雙向鏈表的操作特點：“查詢”和單鏈表相同。“插入”和“刪除”時需要同時修改兩個方向上的指針。

由于前驅指針的設置，如需要前驅的位置信息時，可直接使用，避免了遍歷操作的時間消耗。6ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入7ai-1刪除aiai+1p->next=p->next->next;p->next->prior=p;pai-18第3章排序排序本身涉及的數據結構類型比較單純，所用的存儲結構為順序表。把排序的內容安排在第

2

章的線性表之后，可鞏固第

2

章所學的知識，也有利算法分析能力的提高。其中有些排序的內容需要樹的知識做基礎，這些內容被安排在第

6

章來繼續學習。例如，堆排序的實現放到“二叉樹的應用”一節；歸并排序的跟讀需要借助“二叉樹遍歷”的知識做鋪墊等。講授本章課程大約需6課時。93.1排序的基本概念3.2簡單排序方法3.3先進排序方法3.4基數排序3.5各種排序方法的綜合比較103.1排序的基本概念一、排序的定義二、內部排序和外部排序三、內部排序方法的分類四、內部排序的數據類型定義11一、排序的定義排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。例如：將下列關鍵字序列52,49,80,36,14,58,61,23,97,75調整為14,23,36,49,52,58,61,75,80,9712一般情況下，假設含n個記錄的序列為{R1,R2,…，Rn}其相應的關鍵字序列為{K1,K2,…，Kn}這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系：

Kp1≤Kp2≤…≤Kpn按此固有關系將上式記錄序列重新排列為

{Rp1,Rp2,

…，Rpn}的操作稱作排序。13二、內部排序和外部排序若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序；

反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。

本章只討論內部排序。

14三、內部排序的方法內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。經過一趟排序有序序列區無序序列區有序序列區無序序列區15理解一趟選擇排序voidSelectPass(SqList&L,inti){RcdTypew; j=i; for(k=i+1;k<=L.length;k++)

if(L.r[k].key<L.r[j].key)j=k; if(i!=j){

w=L.r[j];L.r[j]=L.r[i];L.r[i]=w;}//SelectPass16理解選擇排序全過程voidSelectSort(SqList&L,inti){RcdTypew;

for(i=1;i<length;i++){ j=i; for(k=i+1;k<=L.length;k++)

if(L.r[k].key<L.r[j].key)j=k; if(i!=j){

w=L.r[j];L.r[j]=L.r[i];L.r[i]=w;

}//for}//SelectSort17基于不同的“擴大”

有序序列長度的方法，內部排序方法大致可分下列幾種類型：插入類交換類選擇類歸并類其它方法各類排序的主要操作介紹：181.插入類型的排序

將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。因尋找插入位置的方法不同，派生出多種形態的插入排序。192.交換類型的排序

通過“交換”無序序列中的記錄從而得到其中關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。起泡排序、快速排序屬于交換類型的排序。203.選擇類型的排序

從記錄的無序子序列中“選擇”關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。除簡單選擇排序外，堆排序也屬于選擇類型的排序。214.歸并類型的排序

通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。5.其它類型的排序方法22#defineMAXSIZE1000//待排順序表最大長度typedefintKeyType;//關鍵字類型為整數類型typedefstruct{KeyTypekey;//關鍵字項InfoTypeotherinfo;//其它數據項}RcdType;//記錄類型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]閑置

intlength;//順序表長度}SqList;//順序表類型注意：實現時需要定義InfoType如

typedefintInfoType;四、內部排序的數據類型定義233.2簡單排序方法一、插入排序二、起泡排序24有序序列R[1..i-1]R[i]無序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]無序序列R[i+1..n]插入排序25實現“一趟插入排序”可分三步進行：3．將R[i]插入(復制)到R[j+1]的位置上。2．將R[j+1..i-1]中的所有記錄均后移一個位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1..j].keyR[i].key<R[j+1..i-1].key；26插入排序利用“順序查找”實現“在R[1..i-1]中查找R[i]的插入位置”算法的實現要點：27從R[i-1]起向前進行順序查找，監視哨設置在R[0]；R[0]=R[i];//設置“哨兵”循環結束表明R[i]的插入位置為j+1R[0]jR[i]for

(j=i-1;R[0].key<R[j].key;--j);

//從后往前找j=i-1插入位置28對于在查找過程中找到的那些關鍵字不小于R[i].key的記錄，并在查找的同時實現記錄向后移動；for

(j=i-1;R[0].key<R[j].key;--j)

R[j+1]=R[j];R[0]jR[i]j=i-1上述循環結束后可以直接進行“插入”插入位置29令i=2，3，…,n,實現整個序列的排序。for

(i=2;i<=n;++i)

if

(R[i].key<R[i-1].key)

{

在

R[1..i-1]中查找R[i]的插入位置;插入R[i];

}30void

InsertionSort(SqList&L)

{

//對順序表L作直接插入排序。

for(i=2;i<=L.length;++i)

if(L.r[i].key<L.r[i-1].key){

}}//InsertSortL.r[0]=L.r[i];//復制為監視哨for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入到正確位置31內部排序的時間分析：實現內部排序的基本操作有兩個：（2）“移動”記錄。（1）“比較”序列中兩個關鍵字的大小；32對于直接插入排序：最好的情況（關鍵字在記錄序列中順序有序）：“比較”的次數：最壞的情況（關鍵字在記錄序列中逆序有序）：“比較”的次數：0“移動”的次數：“移動”的次數：33二、起泡排序在實現有序性的過程中，使用了交換的操作34

假設在排序過程中，記錄序列R[1..n]的狀態為：第i趟起泡排序無序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1無序序列R[1..n-i]有序序列R[n-i+1..n]比較相鄰記錄，將關鍵字最大的記錄交換到n-i+1的位置上起泡排序35void

BubbleSort(ElemR[],intn)

{

while(i>1){

}

//while}//BubbleSorti=n;i=lastExchangeIndex;//本趟進行過交換的

//最后一個記錄的位置

if

(R[j+1].key<R[j].key)

{

Swap(R[j],R[j+1]);

lastExchangeIndex=j;//記下進行交換的記錄位置

}

//iffor(j=1;j<i;j++)lastExchangeIndex=1;36注意:2.一般情況下，每經過一趟“起泡”，“i減一”，但并不是每趟都如此。例如:2553157989i=7i=6for(j=1;j<i;j++)if

(R[j+1].key<R[j].key)…13i=21.起泡排序的結束條件為，

最后一趟沒有進行“交換記錄”。37時間分析:最好的情況（關鍵字在記錄序列中順序有序）：只需進行一趟起泡“比較”的次數：最壞的情況（關鍵字在記錄序列中逆序有序）：需進行n-1趟起泡“比較”的次數：0“移動”的次數：“移動”的次數：n-1383.3先進排序方法一、快速排序二、歸并排序三、堆排序39一、快速排序在實現有序性的過程中，使用了交換的操作一趟快速排序快速排序快速排序的時間考量40一趟快速排序（一次劃分）

目標：找一個記錄，以它的關鍵字作為“樞軸”，凡其關鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關鍵字大于樞軸的記錄均移動至該記錄之后。致使一趟排序之后，記錄的無序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+1..t]，且

R[j].key≤R[i].key≤R[k].key(s≤j≤i-1)

樞軸

(i+1≤k≤t)41stlowhigh設R[s]=52為樞軸

將R[high].key和樞軸的關鍵字進行比較,要求R[high].key≥

樞軸的關鍵字

將R[low].key和樞軸的關鍵字進行比較,要求R[low].key≤

樞軸的關鍵字high23low80high14low52例如R[0]52lowhighhighhighlow42日后如果不理解一趟快速排序，請再次觀看該動畫！43可見，經過“一次劃分”，將關鍵字序列

52,49,80,36,14,58,61,97,23,75調整為:23,49,14,36,(52)58,61,97,80,75在調整過程中，設立了兩個指針：low和high，它們的初值分別為：s和t，之后逐漸減小high，增加low，并保證

R[high].key≥52，和R[low].key≤52,否則進行記錄的“交換”。44intPartition(RedTypeR[],int

low,int

high){}//Partition

R[0]=R[low];

pivotkey=R[low].key;

//樞軸while(low<high){

}while(low<high&&

R[high].key>=pivotkey)--high;

//從右向左搜索，循環結束說明找到小的R[low]=R[high];//R[low]剛才已送走while

(low<high

&&

R[low].key<=pivotkey)

++low;

//從左向右搜索R[high]=R[low];R[low]=R[0];

//樞軸記錄移到正確位置return

low;//返回樞軸位置“一次劃分”的算法45快速排序首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進行快速排序46void

QSort(RedType&R[],ints,intt)

{

//對記錄序列R[s..t]進行快速排序