这篇文章主要介绍了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::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语言数据结构中链表与归并排序的示例分析”这篇文章对大家有帮助，同时也希望大家多多支持创新互联建站，关注创新互联网站建设公司行业资讯频道，更多相关知识等着你来学习!
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
文章标题：C语言数据结构中链表与归并排序的示例分析-创新互联
浏览路径：
http://cdkjz.cn/article/dijhcd.html
