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操作传入的参数是两个有序链表,返回的是合并后的有序的链表。两个有序链表简单拼接之后不一定是有序的,需要对每一个元素重排。这个重排的过程是从两个链表各自最小(最大)元素开始,谁小(大)就把谁放到新的链表里。

C语言数据结构中链表与归并排序的示例分析

Node* LinkedList::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;
}

感谢你能够认真阅读完这篇文章,希望小编分享的“C语言数据结构中链表与归并排序的示例分析”这篇文章对大家有帮助,同时也希望大家多多支持创新互联,关注创新互联行业资讯频道,更多相关知识等着你来学习!


网页名称:C语言数据结构中链表与归并排序的示例分析
本文URL:http://myzitong.com/article/ieeocs.html