方案将对插入堆中 [英] Scheme Inserting Pairs into Heap

问题描述

这是我似乎无法弄清楚的家庭作业的一部分。我想知道是否有人可以指出我正确的方向？

This is part of a homework assignment that I can't seem to figure out. I was wondering if someone could point me in the right direction?

问题如下：

（插入对列表vw-pair-list堆）评估为插入
产生的 heap 列表 vw-pair-list 中所有 value - weight 对进入堆堆。

(insert-list-of-pairs vw-pair-list heap) evaluates to the heap resulting from inserting all of the value-weight pairs from the list vw-pair-list into the heap heap.

以下功能是在作业的前面创建的，用于解决此问题：

The following functions were created earlier in the homework for use in this problem:

(define (create-heap vw-pair left right)
    (list vw-pair left right))

(define (h-min heap)
    (car heap))

(define (left heap)
    (cadr heap))

(define (right heap)
    (caddr heap))

问题，我能够使用以下代码将一对成功添加到堆中：

In the previous problem I was able to successfully add a pair to the heap using this code:

(define (insert vw-pair heap)
    (if (null? heap)
        (create-heap vw-pair '() '())
        (if (< (weight vw-pair) (weight (h-min heap)))
            (create-heap vw-pair (right heap) (insert (h-min heap) (left heap)))
            (create-heap (h-min heap) (right heap) (insert vw-pair (left heap))))))

我尝试使用以下代码实现类似的过程，但未成功：

I tried to implement a similar procedure using the following code without success:

(define (insert-list-of-pairs vw-pair-list heap)
    (if (null? vw-pair-list)
        heap
        (if (< (car vw-pair-list) (h-min heap))
            (create-heap (car vw-pair-list) (right heap) 
                          (insert-list-of-pairs (cdr vw-pair-list) heap))
            (create-heap (h-min heap) (right heap) 
                          (insert-list-of-pairs vw-pair-list heap)))))

任何帮助都将不胜感激！

Any and all help would be greatly appreciated!

推荐答案

有充分的理由说明您先前的问题是定义插入。< br>
现在，您不仅知道如何实现插入，而且还具有可用于插入的功能，因此您无需再次实现它

There are good reasons that your previous problem was defining insert.
Not only do you now know how to implement insert, but you also have a function that you can use for insertion so you never need to implement it again.

因为这样的对的列表是什么？

Because what is a list of such pairs?

如果不为空，则为一对，然后是一对列表。

您已经有了一个将一对插入堆中的函数。 。

If it's not empty, it's one pair followed by a list of pairs.
And you already have a function that inserts one pair into a heap.

如果只有一个函数可以将成对的列表插入到堆中，则可以使用该函数将列表的其余部分插入到堆中，然后插入您列表的第一个元素到那个堆中，然后就可以完成。

If only you had a function that inserts a list of pairs into a heap, you could use that to insert the rest of your list into your heap, then insert your list's first element into that heap, and then you would be done.

但是-尤里卡！ -将成对的列表插入到堆中函数就是您正在编写的函数。

因此，您需要递归：

But - Eureka! - the "insert a list of pairs into a heap" function is the one you're writing.
So, you recurse:

(define (insert-list-of-pairs vw-pair-list heap)
    (if (null? vw-pair-list)
        heap
        (insert (car vw-pair-list)
                (insert-list-of-pairs (cdr vw-pair-list) heap))))

然后就完成了。

这篇关于方案将对插入堆中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！