這篇文章主要介紹了C語言數據結構中鏈表與歸并排序的示例分析，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
C語言數據結構 鏈表與歸并排序實例詳解
歸并排序適合于對鏈表進行原址排序，即只改變指針的連接方式，不交換鏈表結點的內容。
歸并排序的基本思想是分治法：先把一個鏈表分割成只有一個節(jié)點的鏈表，然后按照一定順序、自底向上合并相鄰的兩個鏈表。
只要保證各種大小的子鏈表是有序的，那么最后返回的鏈表就一定是有序的.
歸并排序分為分割和合并兩個子過程。分割是用遞歸的方法，把鏈表對半分割成兩個子鏈表；合并是在遞歸返回（回朔）的時候，把兩個有序鏈表合并成一個有序鏈表。
(注意：只有一個節(jié)點的鏈表一定是有序的)
這里sort過程就是分割過程；merge過程就是合并且排序的過程
說到分割鏈表，那么問題來了：鏈表不是隨機訪問的，我怎么知道分割點在哪里？一個寶貴的經驗就是：維護兩個指針，一快一慢?？熘羔樏看魏笠苾蓚€單位，慢指針每次只移動一個單位。當快指針移動到tail或者最后一個有效節(jié)點時，慢指針就指向了中間的節(jié)點。
sort過程:
重慶分公司
重慶分公司
Node* sort (Node* beg)
{
if(beg==tail || beg->next==tail) return beg;
Node* a = beg; Node* b = beg->next;
while(b!=tail && b->next != tail)
{
a = a->next; b = b->next->next;
}
b = a->next; //the beginning of right part
a->next = tail; //the end of left part
return merge(sort(beg), sort(b));
}把鏈表分割之后就要合并。merge操作傳入的參數是兩個有序鏈表，返回的是合并后的有序的鏈表。兩個有序鏈表簡單拼接之后不一定是有序的，需要對每一個元素重排。這個重排的過程是從兩個鏈表各自最?。ù螅┰亻_始，誰?。ù螅┚桶颜l放到新的鏈表里。
Node* LinkedList::merge(Node* a, Node* b) { Node dummy = Node(); Node* head = &dummy; // temp是正在合并的表的節(jié)點 Node* temp = head; while(a!=tail && b!=tail) //逐個比較鏈表a和鏈表b的每個元素 { if(a->data <= b->data) { // 如果a比b小, 那么當前結點的后繼就是a temp->next = a; // 把當前節(jié)點移向后繼 temp = a; // a后移 a = a->next; } else { temp->next = b; temp = b; b = b->next; } // 如果原表a已經排完,那么新表后面就放b的剩余元素 // 否則仍然以a為標準和b進行比較 temp->next = (a==tail) ? b : a; } return head->next; }
感謝你能夠認真閱讀完這篇文章，希望小編分享的“C語言數據結構中鏈表與歸并排序的示例分析”這篇文章對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯(lián)建站，關注創(chuàng)新互聯(lián)網站建設公司行業(yè)資訊頻道，更多相關知識等著你來學習!
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
