C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀?/h1>

 更新時(shí)間：2017年01月13日 15:12:36   投稿：lqh  

這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀獾南嚓P(guān)資料,需要的朋友可以參考下

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 鏈表與歸并排序?qū)嵗斀?/strong>

歸并排序適合于對(duì)鏈表進(jìn)行原址排序，即只改變指針的連接方式，不交換鏈表結(jié)點(diǎn)的內(nèi)容。

歸并排序的基本思想是分治法：先把一個(gè)鏈表分割成只有一個(gè)節(jié)點(diǎn)的鏈表，然后按照一定順序、自底向上合并相鄰的兩個(gè)鏈表。

只要保證各種大小的子鏈表是有序的，那么最后返回的鏈表就一定是有序的.

歸并排序分為分割和合并兩個(gè)子過(guò)程。分割是用遞歸的方法，把鏈表對(duì)半分割成兩個(gè)子鏈表；合并是在遞歸返回（回朔）的時(shí)候，把兩個(gè)有序鏈表合并成一個(gè)有序鏈表。

(注意：只有一個(gè)節(jié)點(diǎn)的鏈表一定是有序的)

這里sort過(guò)程就是分割過(guò)程；merge過(guò)程就是合并且排序的過(guò)程

說(shuō)到分割鏈表，那么問(wèn)題來(lái)了：鏈表不是隨機(jī)訪(fǎng)問(wèn)的，我怎么知道分割點(diǎn)在哪里？一個(gè)寶貴的經(jīng)驗(yàn)就是：維護(hù)兩個(gè)指針，一快一慢。快指針每次后移兩個(gè)單位，慢指針每次只移動(dòng)一個(gè)單位。當(dāng)快指針移動(dòng)到tail或者最后一個(gè)有效節(jié)點(diǎn)時(shí)，慢指針就指向了中間的節(jié)點(diǎn)。

sort過(guò)程:

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ù)是兩個(gè)有序鏈表，返回的是合并后的有序的鏈表。兩個(gè)有序鏈表簡(jiǎn)單拼接之后不一定是有序的，需要對(duì)每一個(gè)元素重排。這個(gè)重排的過(guò)程是從兩個(gè)鏈表各自最小（最大）元素開(kāi)始，誰(shuí)小（大）就把誰(shuí)放到新的鏈表里。

Node* LinkedList<T>::merge(Node* a, Node* b)
{
	Node dummy = Node();
	Node* head = &dummy;
	// temp是正在合并的表的節(jié)點(diǎn)
	Node* temp = head;
	while(a!=tail && b!=tail) //逐個(gè)比較鏈表a和鏈表b的每個(gè)元素
	{
		if(a->data <= b->data)
		{
			// 如果a比b小, 那么當(dāng)前結(jié)點(diǎn)的后繼就是a
			temp->next = a;
			// 把當(dāng)前節(jié)點(diǎn)移向后繼
			temp = a;
			// a后移
			a = a->next;
		}
		else 
		{
			temp->next = b;
			temp = b; 
			b = b->next;
		}
		// 如果原表a已經(jīng)排完,那么新表后面就放b的剩余元素
		// 否則仍然以a為標(biāo)準(zhǔn)和b進(jìn)行比較
		temp->next = (a==tail) ? b : a;
	}
	return head->next;
}

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章:

• C語(yǔ)言非遞歸算法解決快速排序與歸并排序產(chǎn)生的棧溢出
• C語(yǔ)言遞歸實(shí)現(xiàn)歸并排序詳解
• C語(yǔ)言實(shí)現(xiàn)各種排序算法實(shí)例代碼(選擇,冒泡,插入,歸并,希爾,快排,堆排序,計(jì)數(shù))
• C語(yǔ)言排序方法(冒泡,選擇,插入,歸并,快速)
• C語(yǔ)言分治法實(shí)現(xiàn)歸并排序
• C語(yǔ)言中數(shù)據(jù)結(jié)構(gòu)之鏈表歸并排序?qū)嵗a
• C語(yǔ)言實(shí)現(xiàn)排序算法之歸并排序詳解
• c語(yǔ)言排序之歸并排序(遞歸和非遞歸)

• C語(yǔ)言
• 鏈表
• 歸并排序

相關(guān)文章

• 

  MFC實(shí)現(xiàn)在文件尾追加數(shù)據(jù)的方法

  這篇文章主要介紹了MFC實(shí)現(xiàn)在文件尾追加數(shù)據(jù)的方法,涉及MFC文件操作的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下

  2015-09-09
• 

  C++ std::async的使用總結(jié)

  這篇文章主要介紹了C++ std::async的使用總結(jié),文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

  2021-01-01
• 

  C++ 容器適配器仿函數(shù)與priority_queue的使用

  本文主要介紹了C++ 容器適配器仿函數(shù)與priority_queue的使用,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

  2024-09-09
• 

  c語(yǔ)言壓縮文件詳細(xì)講解

  這篇文章主要從單文件壓縮、多文件壓縮、多文件異步壓縮講訴了c語(yǔ)言壓縮文件,需要的朋友可以參考下面具體的文章內(nèi)容

  2021-09-09
• 

  C/C++ 數(shù)組和指針及引用的區(qū)別

  這篇文章主要介紹了C/C++ 數(shù)組和指針及引用的區(qū)別的相關(guān)資料,這里從匯編的角度來(lái)分析他們之間的區(qū)別，需要的朋友可以參考下

  2017-07-07
• 

  解析C語(yǔ)言中結(jié)構(gòu)體struct的對(duì)齊問(wèn)題

  這篇文章主要介紹了C語(yǔ)言中結(jié)構(gòu)體struct的對(duì)齊問(wèn)題,作者深入到內(nèi)存分配方面來(lái)進(jìn)行解析,需要的朋友可以參考下

  2016-04-04
• 

  C++中的std::nothrow使用

  這篇文章主要介紹了C++中的std::nothrow使用方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

  2023-08-08
• 

  Visual Studio安裝的圖文教程

  這篇文章主要介紹了Visual Studio安裝的圖文教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

  2023-02-02
• 

  一文搞懂c++中的std::move函數(shù)

  這篇文章主要介紹了c++中的std::move函數(shù),在探討c++11中的Move函數(shù)前，先介紹兩個(gè)概念（左值和右值），對(duì)c++?std::move函數(shù)相關(guān)知識(shí)感興趣的朋友一起看看吧

  2022-07-07
• 

  C++實(shí)現(xiàn)多項(xiàng)式相乘

  這篇文章主要介紹了C++實(shí)現(xiàn)多項(xiàng)式相乘方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

  2022-07-07

最新評(píng)論