C语言数据结构 链表与归并排序实例详解
更新时间:2020年4月25日 17:32 点击:1732
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; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
下一篇: String类的写时拷贝实例
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了JavaScript数据结构之双向链表,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-03-07
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要介绍了python无序链表删除重复项的方法,本文给大家介绍的非常详细,具体一定的参考借鉴价值,需要的朋友可以参考下...2020-04-27
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25