当前位置：首页 > news >正文

C#，双向链表（Doubly Linked List）归并排序（Merge Sort）算法与源代码

news 来源：原创 2024/5/12 18:30:06

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 < second.Data){first.Next = Merge_Utility(first.Next, second);first.Next.Prev = first;first.Prev = null;return first;}else{second.Next = Merge_Utility(first, second.Next);second.Next.Prev = second;second.Prev = null;return second;}}public DoublyLinkNode Merge_Sort(DoublyLinkNode node){if (node == null || node.Next == null){return node;}DoublyLinkNode second = Split(node);node = Merge_Sort(node);second = Merge_Sort(second);return Merge_Utility(node, second);}public static List<int> ToList(DoublyLinkNode head){List<int> list = new List<int>();while (head != null){list.Add(head.Data);head = head.Next;}return list;}public static string ToHtml(DoublyLinkNode head, DoublyLinkNode cur){StringBuilder sb = new StringBuilder();sb.AppendLine("<style>");sb.AppendLine(".node { float:left;width:45px;height:45px;line-height:45px;font-size:21px;text-align:center;border:solid 1px #DD0000; }");sb.AppendLine(".node_cur { float:left;width:45px;height:45px;line-height:45px;font-size:21px;font-weight:bold;text-align:center;border:solid 1px #FF6701;background-color:#FAFA90; }");sb.AppendLine(".link { float:left;width:45px;height:45px;line-height:21px;font-size:12px;text-align:center;border:solid 0px #DD0000;white-space:nowrap;word-break:keep-all; }");sb.AppendLine("</style>");while (head != null){if (head == cur){sb.AppendLine("<div class='node_cur'>" + head.Data + "</div>");}else{sb.AppendLine("<div class='node'>" + head.Data + "</div>");}if (head.Next != null){sb.AppendLine("<div class='link'>--&gt;<br>&lt;--</div>");}head = head.Next;}return sb.ToString();}}
}

POWER BY 315SOFT.COM