像树一样,在链表的最后一个节点添加两个最小值

本文关键字:最后一个 添加 节点 最小值 两个 一样 链表 | 更新日期: 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.freqsecond.freq的总和。

  • AddToEndOfList(Node newNode);:将节点添加到列表的末尾。

请注意,这些只是抽象的占位符方法,你可能应该给它们添加额外的参数,或者把它们变成实例方法,如果你认为它会帮助你。