C語言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀?/h1>
更新時間：2017年01月13日 15:12:36 投稿：lqh
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀獾南嚓P(guān)資料,需要的朋友可以參考下
C語言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀?/strong>
歸并排序適合于對鏈表進行原址排序，即只改變指針的連接方式，不交換鏈表結(jié)點的內(nèi)容。
歸并排序的基本思想是分治法：先把一個鏈表分割成只有一個節(jié)點的鏈表，然后按照一定順序、自底向上合并相鄰的兩個鏈表。
只要保證各種大小的子鏈表是有序的，那么最后返回的鏈表就一定是有序的.
歸并排序分為分割和合并兩個子過程。分割是用遞歸的方法，把鏈表對半分割成兩個子鏈表；合并是在遞歸返回（回朔）的時候，把兩個有序鏈表合并成一個有序鏈表。
(注意：只有一個節(jié)點的鏈表一定是有序的)
這里sort過程就是分割過程；merge過程就是合并且排序的過程
說到分割鏈表，那么問題來了：鏈表不是隨機訪問的，我怎么知道分割點在哪里？一個寶貴的經(jīng)驗就是：維護兩個指針，一快一慢?？熘羔樏看魏笠苾蓚€單位，慢指針每次只移動一個單位。當(dāng)快指針移動到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操作傳入的參數(shù)是兩個有序鏈表，返回的是合并后的有序的鏈表。兩個有序鏈表簡單拼接之后不一定是有序的，需要對每一個元素重排。這個重排的過程是從兩個鏈表各自最?。ㄗ畲螅┰亻_始，誰小（大）就把誰放到新的鏈表里。
Node* LinkedList<T>::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小, 那么當(dāng)前結(jié)點的后繼就是a
temp->next = a;
// 把當(dāng)前節(jié)點移向后繼
temp = a;
// a后移
a = a->next;
}
else
{
temp->next = b;
temp = b;
b = b->next;
}
// 如果原表a已經(jīng)排完,那么新表后面就放b的剩余元素
// 否則仍然以a為標準和b進行比較
temp->next = (a==tail) ? b : a;
}
return head->next;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
-
MFC實現(xiàn)在文件尾追加數(shù)據(jù)的方法
這篇文章主要介紹了MFC實現(xiàn)在文件尾追加數(shù)據(jù)的方法,涉及MFC文件操作的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下 2015-09-09
-
這篇文章主要介紹了C++ std::async的使用總結(jié),文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2021-01-01
-
C++ 容器適配器仿函數(shù)與priority_queue的使用
本文主要介紹了C++ 容器適配器仿函數(shù)與priority_queue的使用,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧 2024-09-09
-
這篇文章主要從單文件壓縮、多文件壓縮、多文件異步壓縮講訴了c語言壓縮文件,需要的朋友可以參考下面具體的文章內(nèi)容 2021-09-09
-
這篇文章主要介紹了C/C++ 數(shù)組和指針及引用的區(qū)別的相關(guān)資料,這里從匯編的角度來分析他們之間的區(qū)別，需要的朋友可以參考下 2017-07-07
-
解析C語言中結(jié)構(gòu)體struct的對齊問題
這篇文章主要介紹了C語言中結(jié)構(gòu)體struct的對齊問題,作者深入到內(nèi)存分配方面來進行解析,需要的朋友可以參考下 2016-04-04
-
這篇文章主要介紹了C++中的std::nothrow使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教 2023-08-08
-
這篇文章主要介紹了Visual Studio安裝的圖文教程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教 2023-02-02
-
這篇文章主要介紹了c++中的std::move函數(shù),在探討c++11中的Move函數(shù)前，先介紹兩個概念（左值和右值），對c++?std::move函數(shù)相關(guān)知識感興趣的朋友一起看看吧 2022-07-07
-
這篇文章主要介紹了C++實現(xiàn)多項式相乘方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教 2022-07-07
最新評論
C語言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀?/strong>
歸并排序適合于對鏈表進行原址排序，即只改變指針的連接方式，不交換鏈表結(jié)點的內(nèi)容。
歸并排序的基本思想是分治法：先把一個鏈表分割成只有一個節(jié)點的鏈表，然后按照一定順序、自底向上合并相鄰的兩個鏈表。
只要保證各種大小的子鏈表是有序的，那么最后返回的鏈表就一定是有序的.
歸并排序分為分割和合并兩個子過程。分割是用遞歸的方法，把鏈表對半分割成兩個子鏈表；合并是在遞歸返回（回朔）的時候，把兩個有序鏈表合并成一個有序鏈表。
(注意：只有一個節(jié)點的鏈表一定是有序的)
這里sort過程就是分割過程；merge過程就是合并且排序的過程
說到分割鏈表，那么問題來了：鏈表不是隨機訪問的，我怎么知道分割點在哪里？一個寶貴的經(jīng)驗就是：維護兩個指針，一快一慢?？熘羔樏看魏笠苾蓚€單位，慢指針每次只移動一個單位。當(dāng)快指針移動到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操作傳入的參數(shù)是兩個有序鏈表，返回的是合并后的有序的鏈表。兩個有序鏈表簡單拼接之后不一定是有序的，需要對每一個元素重排。這個重排的過程是從兩個鏈表各自最?。ㄗ畲螅┰亻_始，誰小（大）就把誰放到新的鏈表里。
Node* LinkedList<T>::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小, 那么當(dāng)前結(jié)點的后繼就是a
temp->next = a;
// 把當(dāng)前節(jié)點移向后繼
temp = a;
// a后移
a = a->next;
}
else
{
temp->next = b;
temp = b;
b = b->next;
}
// 如果原表a已經(jīng)排完,那么新表后面就放b的剩余元素
// 否則仍然以a為標準和b進行比較
temp->next = (a==tail) ? b : a;
}
return head->next;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
-
MFC實現(xiàn)在文件尾追加數(shù)據(jù)的方法
這篇文章主要介紹了MFC實現(xiàn)在文件尾追加數(shù)據(jù)的方法,涉及MFC文件操作的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-09-09 - 這篇文章主要介紹了C++ std::async的使用總結(jié),文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
-
C++ 容器適配器仿函數(shù)與priority_queue的使用
本文主要介紹了C++ 容器適配器仿函數(shù)與priority_queue的使用,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-09-09 - 這篇文章主要從單文件壓縮、多文件壓縮、多文件異步壓縮講訴了c語言壓縮文件,需要的朋友可以參考下面具體的文章內(nèi)容2021-09-09
- 這篇文章主要介紹了C/C++ 數(shù)組和指針及引用的區(qū)別的相關(guān)資料,這里從匯編的角度來分析他們之間的區(qū)別，需要的朋友可以參考下2017-07-07
-
解析C語言中結(jié)構(gòu)體struct的對齊問題
這篇文章主要介紹了C語言中結(jié)構(gòu)體struct的對齊問題,作者深入到內(nèi)存分配方面來進行解析,需要的朋友可以參考下2016-04-04 - 這篇文章主要介紹了C++中的std::nothrow使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
- 這篇文章主要介紹了Visual Studio安裝的圖文教程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
- 這篇文章主要介紹了c++中的std::move函數(shù),在探討c++11中的Move函數(shù)前，先介紹兩個概念（左值和右值），對c++?std::move函數(shù)相關(guān)知識感興趣的朋友一起看看吧2022-07-07
- 這篇文章主要介紹了C++實現(xiàn)多項式相乘方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07