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

 更新時(shí)間：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>

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

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

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

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

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

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

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

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ù)是兩個(gè)有序鏈表，返回的是合并后的有序的鏈表。兩個(gè)有序鏈表簡單拼接之后不一定是有序的，需要對每一個(gè)元素重排。這個(gè)重排的過程是從兩個(gè)鏈表各自最小（最大）元素開始，誰?。ù螅┚桶颜l放到新的鏈表里。

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;
}

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

您可能感興趣的文章:

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

• C語言
• 鏈表
• 歸并排序

相關(guān)文章

• 

  C語言 sockaddr和sockaddr_in案例詳解

  這篇文章主要介紹了C語言 sockaddr和sockaddr_in案例詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

  2021-08-08
• 

  詳解C++中的inline用法

  在c/c++中，為了解決一些頻繁調(diào)用的小函數(shù)大量消耗棧空間（棧內(nèi)存）的問題，特別的引入了inline修飾符，表示為內(nèi)聯(lián)函數(shù)。 ?？臻g就是指放置程序的局部數(shù)據(jù)（也就是函數(shù)內(nèi)數(shù)據(jù)）的內(nèi)存空間

  2017-09-09
• 

  OpenCV4 實(shí)現(xiàn)背景分離的詳細(xì)步驟(背景減法模型)

  背景分離（BS）是一種通過使用靜態(tài)相機(jī)來生成前景掩碼（即包含屬于場景中的移動對象像素的二進(jìn)制圖像）的常用技術(shù)，本文給大家介紹OpenCV4 實(shí)現(xiàn)背景分離的詳細(xì)步驟，需要的朋友可以參考下

  2021-09-09
• 

  C利用語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)之隊(duì)列

  隊(duì)列 (Queue)：簡稱隊(duì)，是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素。q=(a1, a2, a3, … an),其中a1為隊(duì)頭，an為隊(duì)尾，下面文章小編將為大家詳細(xì)介紹,需要的下伙伴可以參考一下

  2021-10-10
• 

  C++中的類模板詳解及示例

  我們在定義函數(shù)時(shí)，可以通過定義函數(shù)模板，來簡化一些功能相同而數(shù)據(jù)類型不同的函數(shù)的定義和調(diào)用過程

  2013-10-10
• 

  C語言形參和實(shí)參傳值和傳址詳解刨析

  形參出現(xiàn)在函數(shù)定義中，在整個(gè)函數(shù)體內(nèi)都可以使用， 離開該函數(shù)則不能使用。實(shí)參出現(xiàn)在主調(diào)函數(shù)中，進(jìn)入被調(diào)函數(shù)后，實(shí)參變量也不能使用，形參和實(shí)參的功能是作數(shù)據(jù)傳送。發(fā)生函數(shù)調(diào)用時(shí)， 主調(diào)函數(shù)把實(shí)參的值傳送給被調(diào)函數(shù)的形參從而實(shí)現(xiàn)主調(diào)函數(shù)向被調(diào)函數(shù)的數(shù)據(jù)傳送

  2021-11-11
• 

  C++語言pow函數(shù)的具體使用

  本文主要介紹了C++語言pow函數(shù)的具體使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

  2023-03-03
• 

  用C語言實(shí)現(xiàn)圣誕樹(簡易版+進(jìn)階版)

  大家好，本篇文章主要講的是用C語言實(shí)現(xiàn)圣誕樹（簡易版+進(jìn)階版），感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽

  2021-12-12
• 

  C++中NULL與nullptr的區(qū)別對比

  nullptr是c++11中的關(guān)鍵字，下面這篇文章主要介紹了C++中NULL與nullptr區(qū)別的相關(guān)資料，對大家來說還是挺實(shí)用的，需要的朋友可以參考下

  2021-05-05
• 

  匯編語言常見錯(cuò)誤信息中文注解

  這篇文章主要介紹了匯編語言常見錯(cuò)誤信息中文注解,本文收集大部分匯編中常見錯(cuò)誤信息及對應(yīng)的中文注解,需要的朋友可以參考下

  2014-09-09

最新評論