像树一样,在链表的最后一个节点添加两个最小值
本文关键字:最后一个 添加 节点 最小值 两个 一样 链表 | 更新日期: 2023-09-27 17:52:37
我已经从c++切换到c#了。我在使用链表的情况下,其中包含如下节点:(按递增顺序排序)
1->1->1->44->46->48->49->50->null
我要做的是:
(1)添加前两个节点。(2)将得到的some放到最后一个节点。因此,在第一次添加之后,LList将是:(1+1=2)
1->1->1->44->46->48->49->50->2->null
(3)再次将两个最小节点相加,并将和放在最后一个节点(但不添加已添加的节点)。
(4)这次两个最小值是1和2,因为"1"answers"1"(前两个)已经加在一起了。LList现在变成:
1->1->1->44->46->48->49->50->2->3->null
(5)现在两个最小值是3和44,所以
1->1->1->44->46->48->49->50->2->3->47->null
(6)现在两个最小值是46和47(最后我们有了第二个最小值47),所以1 -> 1 -> 1 -> 44 -> 46 - 48 - 49>>> 50 -> 2 -> 3 -> 47 -> 93 -> null(7)现在是48和49,所以
1->1->1->44->46->48->49->50->2->3->47->93->97->null
(8)下一个最小值是"50"answers"93",因此,
1->1->1->44->46->48->49->50->2->3->47->93->97->143->null
(9)最后:剩下97和143,所以
1->1->1->44->46->48->49->50->2->3->47->93->97->143->240->null
只剩下一个元素(240),所以到此为止。
有谁能帮我做算法吗?由于
我的想法:实现这个算法是:这里"freq"包含值,左和右就像树的左和右。
while (front != rear)
{
if (counter == 0)
{
Console.WriteLine("check1");
temp = new Node();
temp.freq = front.freq + front.next.freq;
front.is_processed = 1;
front.next.is_processed = 1;
temp.is_processed = 0;
temp.left = front;
temp.right = front.next;
temp.next = null;
rear.next = temp;
front = front.next.next;
rear = rear.next;
remaining = count_remaining();
if (remaining == 1)
{
break;
}
}
if (rear.freq.Equals(front.freq))
{
Console.WriteLine("check2");
temp = new Node();
temp.freq = front.freq + rear.freq;
rear.is_processed = 1;
front.is_processed = 1;
temp.is_processed = 0;
temp.left = front;
temp.right = rear;
temp.next = null;
rear.next = temp;
rear = rear.next;
remaining = count_remaining();
if (remaining == 1)
{
break;
}
}
if (rear.freq < front.freq)
{
Console.WriteLine("check3");
Node pmin1 = null;
Node pmin2 = null;
front_rear(ref pmin1, ref pmin2);
temp = new Node();
temp.freq = pmin1.freq + pmin2.freq;
pmin1.is_processed = 1;
pmin2.is_processed = 1;
temp.is_processed = 0;
temp.left = pmin2;
temp.right = pmin1;
temp.next = null;
rear.next = temp;
rear = rear.next;
remaining = count_remaining();
if (remaining == 1)
{
break;
}
}
if (rear.freq > front.freq)
{
Console.WriteLine("check4");
Node pmin1 = null;
Node pmin2 = null;
front_rear(ref pmin1, ref pmin2);
temp = new Node();
temp.freq = pmin1.freq + pmin2.freq;
pmin1.is_processed = 1;
pmin2.is_processed = 1;
temp.is_processed = 0;
temp.left = pmin2;
temp.right = pmin1;
temp.next = null;
rear.next = temp;
rear = rear.next;
remaining = count_remaining();
if (remaining == 1)
{
break;
}
}
counter++;
}
但令人惊讶的是,它打印:(它根本没有去"check3",即if (rear.freq < front.freq)
,你可以看到上面的step5是在这个条件下,但不打印check3
)
check1
check4
check4
check4
check4
check4
check4
为什么它只是在条件if (rear.freq > front.freq)
?(它实际上是一个使用链表的树),其中父节点是两个最小节点的和
你的代码太潦草了,所以我给你一个使用
的基本框架Node first = FindLowestUnprocessedNode();
Node second = FindLowestUnprocessedNode();
while(first != null && second != null)
{
Node sumNode = new Node(first, second)
AddToEndOfList(sumNode);
Node first = FindLowestUnprocessedNode();
Node second = FindLowestUnprocessedNode();
}
这里有一些函数供你自己编写。这些不应该太难
FindLowestUnprocessedNode(...)
:查找最低的未处理节点并将其标记为已处理。如果处理了所有节点,则返回null
。您可能会发现需要向该方法添加额外的参数。Node(Node first, Node second)
:将此构造函数添加到Node
类中。它应该初始化节点,使first
在左侧,second
在右侧,freq
应该是first.freq
和second.freq
的总和。AddToEndOfList(Node newNode);
:将节点添加到列表的末尾。
请注意,这些只是抽象的占位符方法,你可能应该给它们添加额外的参数,或者把它们变成实例方法,如果你认为它会帮助你。