1 
public class Link {
public int weight;
public int loc;
public Link next;
public boolean visited;
public Link parent;

public Link(int d, int loc){
    this.weight = d;
    this.loc = loc;
    this.visited = false;
}
public Link(Link p, int d, int loc){
    this.parent = p;
    this.weight = d;
    this.loc = loc;
}

public void printLink(){
    System.out.println(weight);
}
}

class LinkList{


public Link first;

public LinkList(){
    first = null;
}
public void add(int d, int loc){
    Link link = new Link(d, loc);
    if (first == null){
        first = link;
    }
    else{
        Link curr = first;
        while (curr.next!=null){
            curr = curr.next;
        }
        curr.next = link;
    }

}
public void printList(){
    Link currentLink = first;
    System.out.println("List: ");
    while(currentLink != null) {
        currentLink.printLink();
        currentLink = currentLink.next;
    }
    System.out.println("");
}
public boolean isEmpty(){
    return first == null;
}
public Link delete(){
    Link temp = first;
    first = first.next;
    return temp;
}

}

 public class MinHeap {
    public Link[] Heap;
    public int size;
    public int maxsize;

    private static final int FRONT = 0;

    public MinHeap(int maxsize, Link x)
    {
        this.maxsize = maxsize;
        this.size = 0;
        Heap = new Link[this.maxsize + 1];
        Heap[0] = x;
    }

    private int parent(int pos)
    {
        return pos / 2;
    }

    private int leftChild(int pos)
    {
        return (2 * pos);
    }

    private int rightChild(int pos)
    {
        return (2 * pos) + 1;
    }

    private boolean isLeaf(int pos)
    {
        if (pos >=  (size / 2)  &&  pos <= size)
        { 
            return true;
        }
        return false;
    }

    private void swap(int fpos, int spos)
    {
        Link tmp;
        tmp = Heap[fpos];
        Heap[fpos] = Heap[spos];
        Heap[spos] = tmp;
    }

    private void minHeapify(int pos)
    {
        if (!isLeaf(pos))
        { 
            if ( Heap[pos].weight > Heap[leftChild(pos)].weight  || Heap[pos].weight > Heap[rightChild(pos)].weight)
            {
                if (Heap[leftChild(pos)].weight < Heap[rightChild(pos)].weight)
                {
                    swap(pos, leftChild(pos));
                    minHeapify(leftChild(pos));
                }else
                {
                    swap(pos, rightChild(pos));
                    minHeapify(rightChild(pos));
                }
            }
        }
    }

    public void add(Link element)
    {
        Heap[++size] = element;
        int current = size;

        while (Heap[current].weight < Heap[parent(current)].weight)
        {
            swap(current,parent(current));
            current = parent(current);
        }   
    }

    public void print()
    {
        for (int i = 1; i <= size / 2; i++ )
        {
            System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i] 
                + " RIGHT CHILD :" + Heap[2 * i  + 1]);
            System.out.println();
        } 
    }

    public void minHeap()
    {
        for (int pos = (size / 2); pos >= 1 ; pos--)
        {
            minHeapify(pos);
        }
    }
    public boolean inQ(Link d){
        int x = d.weight;
        for (int i = 0; i<size;i++){
            if (Heap[i].weight == x){
                return true;
            }
        }
        return false;
    }

    public Link remove()
    {
        Link popped = Heap[FRONT];
        Heap[FRONT] = Heap[size--]; 
        minHeapify(FRONT);
        return popped;
    }
}

ここには、重み属性に基づいて Link オブジェクトを格納する最小ヒープ クラスがあります。私の目的は、最小ヒープに格納されているオブジェクトの属性に直接アクセスして変更できるようにすることです。「loc」属性のみに基づいてこれらのオブジェクトにアクセスできる必要があります。
たとえば、loc 値が 6 の Link オブジェクトにアクセスして、その親属性または重み属性を変更したい場合があります。ただし、アクセス時の loc 属性値しかわかりません。
私の理解では、これらのオブジェクトへのポインターの配列を使用する必要がありますが、これをどのように実装するかはわかりません。

ありがとう！

4

1 に答える 1

0

あなたのコードによると、すべてのリンクはその親とリスト内の次の要素を知っています。

以下のアルゴリズムに従って、必要なフィールドを更新する必要があります。

  1. まず、リンク オブジェクトと loc 値を、重み/親を更新するメソッドに渡します。1 つは重みを更新し、もう 1 つは重みを更新する 2 つのメソッドを記述できます。または、アクティビティを分離するフラグを使用して 1 つのメソッドを使用することもできます。

  2. 重みを更新したい場合は、簡単です。

  3. 親を更新する場合は、親の next も更新する必要があるため、新しい親オブジェクトもメソッドに渡す必要がありますが、親の既存の next を失う可能性があるため、コードを適切に処理するようにしてください。

実際のオブジェクトを渡すと、jvm は同じままになります。リストの重み/親の値を渡さないようにしてください。

于 2015-04-04T05:42:20.347 に答える