程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C言語數據構造 鏈表與歸並排序實例詳解

C言語數據構造 鏈表與歸並排序實例詳解

編輯:關於C++

C言語數據構造 鏈表與歸並排序實例詳解。本站提示廣大學習愛好者:(C言語數據構造 鏈表與歸並排序實例詳解)文章只能為提供參考,不一定能成為您想要的結果。以下是C言語數據構造 鏈表與歸並排序實例詳解正文


C言語數據構造 鏈表與歸並排序實例詳解

歸並排序合適於對鏈表停止舊址排序,即只改動指針的銜接方式,不交流鏈表結點的內容。

歸並排序的根本思想是分治法:先把一個鏈表聯系成只要一個節點的鏈表,然後依照一定順序、自底向上兼並相鄰的兩個鏈表。

只需保證各種大小的子鏈表是有序的,那麼最後前往的鏈表就一定是有序的.

歸並排序分為聯系和兼並兩個子進程。聯系是用遞歸的辦法,把鏈表對半聯系成兩個子鏈表;兼並是在遞歸前往(回朔)的時分,把兩個有序鏈表兼並成一個有序鏈表。

(留意:只要一個節點的鏈表一定是有序的)

這裡sort進程就是聯系進程;merge進程就是兼並且排序的進程

說到聯系鏈表,那麼問題來了:鏈表不是隨機訪問的,我怎樣知道聯系點在哪裡?一個珍貴的經歷就是:維護兩個指針,一快一慢。快指針每次後移兩個單位,慢指針每次只挪動一個單位。當快指針挪動到tail或許最後一個無效節點時,慢指針就指向了兩頭的節點。

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操作傳入的參數是兩個有序鏈表,前往的是兼並後的有序的鏈表。兩個有序鏈表復雜拼接之後不一定是有序的,需求對每一個元素重排。這個重排的進程是從兩個鏈表各自最小(最大)元素開端,誰小(大)就把誰放到新的鏈表裡。

Node* LinkedList<T>::merge(Node* a, Node* b)
{
	Node dummy = Node();
	Node* head = &dummy;
	// temp是正在兼並的表的節點
	Node* temp = head;
	while(a!=tail && b!=tail) //逐一比擬鏈表a和鏈表b的每個元素
	{
		if(a->data <= b->data)
		{
			// 假如a比b小, 那麼以後結點的後繼就是a
			temp->next = a;
			// 把以後節點移向後繼
			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;
}

感激閱讀,希望能協助到大家,謝謝大家對本站的支持!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved