C#,双向链表(Doubly Linked List)归并排序(Merge Sort)算法与源代码
1 双向链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
2 循环链表
循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。
3 归并排序
归并排序法(Merge Sort,以下简称MS)是分治法思想运用的一个典范。
其主要算法操作可以分为以下步骤:
- 将n个元素分成两个含n/2元素的子序列;
- 用MS将两个子序列递归排序(最后可以将整个原序列分解成n个子序列);
- 合并两个已排序好的序列;
易知,MS的关键在于Merge过程。对于这一过程的理解,算法导论中给出了一个形象的模型。
即假设桌面上有两堆已排序好的的牌,且每一堆都正面朝下放置。然后我们分别从两堆牌中选取顶上的一张牌(选取之后,堆顶端又会露出新的顶牌),选取较小的一张,放入输出堆,另一张放回。
重复这一步骤,最后直到一堆牌为空。由于两堆牌都是已排序,所以可知,只要将剩下的那堆牌盖到输出堆即完成整个排序过程。
4 源程序
using System.Text; using System.Collections; using System.Collections.Generic; namespace Legalsoft.Truffer.Algorithm { public class DoublyLinkNode { public int Data { get; set; } = 0; public DoublyLinkNode Next { get; set; } = null; public DoublyLinkNode Prev { get; set; } = null; public DoublyLinkNode(int d) { Data = d; } } public partial class DoublyLinkedList { public DoublyLinkNode Head { get; set; } = null; private DoublyLinkNode Split(DoublyLinkNode head) { DoublyLinkNode fast = head; DoublyLinkNode slow = head; while (fast.Next != null && fast.Next.Next != null) { fast = fast.Next.Next; slow = slow.Next; } DoublyLinkNode temp = slow.Next; slow.Next = null; return temp; } private DoublyLinkNode Merge_Utility(DoublyLinkNode first, DoublyLinkNode second) { if (first == null) { return second; } if (second == null) { return first; } if (first.Data <--"); } head = head.Next; } return sb.ToString(); } } }
POWER BY 315SOFT.COM
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。