1

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

//數(shù)據(jù)域

structDuLNode*prior;

//指向前驅(qū)的指針域

structDuLNode*next;

//

指向后繼的指針域}

DuLNode,*DuLinkList;2

最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表a1a2…...an2.循環(huán)鏈表

和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。3

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

由于前驅(qū)指針的設(shè)置，如需要前驅(qū)的位置信息時(shí)，可直接使用，避免了遍歷操作的時(shí)間消耗。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章排序排序本身涉及的數(shù)據(jù)結(jié)構(gòu)類型比較單純，所用的存儲(chǔ)結(jié)構(gòu)為順序表。把排序的內(nèi)容安排在第

2

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

2

章所學(xué)的知識(shí)，也有利算法分析能力的提高。其中有些排序的內(nèi)容需要樹的知識(shí)做基礎(chǔ)，這些內(nèi)容被安排在第

6

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

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

{Rp1,Rp2,

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

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

本章只討論內(nèi)部排序。

14三、內(nèi)部排序的方法內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長度的過程。經(jīng)過一趟排序有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)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基于不同的“擴(kuò)大”

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

將無序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。因?qū)ふ也迦胛恢玫姆椒ú煌缮龆喾N形態(tài)的插入排序。192.交換類型的排序

通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。起泡排序、快速排序?qū)儆诮粨Q類型的排序。203.選擇類型的排序

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

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

intlength;//順序表長度}SqList;//順序表類型注意：實(shí)現(xiàn)時(shí)需要定義InfoType如

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

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

//從后往前找j=i-1插入位置28對(duì)于在查找過程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；for

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

R[j+1]=R[j];R[0]jR[i]j=i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置29令i=2，3，…,n,實(shí)現(xiàn)整個(gè)序列的排序。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)

{

//對(duì)順序表L作直接插入排序。

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

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

}}//InsertSortL.r[0]=L.r[i];//復(fù)制為監(jiān)視哨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內(nèi)部排序的時(shí)間分析：實(shí)現(xiàn)內(nèi)部排序的基本操作有兩個(gè)：（2）“移動(dòng)”記錄。（1）“比較”序列中兩個(gè)關(guān)鍵字的大小；32對(duì)于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：33二、起泡排序在實(shí)現(xiàn)有序性的過程中，使用了交換的操作34

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

BubbleSort(ElemR[],intn)

{

while(i>1){

}

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

//最后一個(gè)記錄的位置

if

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

{

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

lastExchangeIndex=j;//記下進(jìn)行交換的記錄位置

}

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

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

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

目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后。致使一趟排序之后，記錄的無序序列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設(shè)R[s]=52為樞軸

將R[high].key和樞軸的關(guān)鍵字進(jìn)行比較,要求R[high].key≥

樞軸的關(guān)鍵字

將R[low].key和樞軸的關(guān)鍵字進(jìn)行比較,要求R[low].key≤

樞軸的關(guān)鍵字high23low80high14low52例如R[0]52lowhighhighhighlow42日后如果不理解一趟快速排序，請(qǐng)?jiān)俅斡^看該動(dòng)畫！43可見，經(jīng)過“一次劃分”，將關(guān)鍵字序列

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

R[high].key≥52，和R[low].key≤52,否則進(jìn)行記錄的“交換”。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;

//從右向左搜索，循環(huán)結(jié)束說明找到小的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快速排序首先對(duì)無序的記錄序列進(jìn)行“一次劃分”，之后分別對(duì)分割所得兩個(gè)子序列“遞歸”進(jìn)行快速排序。無序的記錄序列無序記錄子序列(1)無序子序列(2)樞軸一次劃分分別進(jìn)行快速排序46void

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

{

//對(duì)記錄序列R[s..t]進(jìn)行快速排序