문자열이 문자열 배열에 할당되지 않습니다

Question

저는 정말 바보 같은 짓을 한 것 같아요.하지만 enqueue의 문자열 "elem"은 문자열 배열 "heap"에 할당하지 않습니다. 이것은 참조로 전달 된 const라는 사실과 관련이 있습니까?

#include "pqueue-heap.h" 
using namespace std; 

HeapPQueue::HeapPQueue() { 
    heap = new string[1000]; 
} 
HeapPQueue::~HeapPQueue() { 
    delete[] heap; 

} 

string HeapPQueue::peek() const { 
    // placeholder so method compiles.. 
    // replace with your own implementation 
    return ""; 
} 

string HeapPQueue::extractMin() { 

    // placeholder so method compiles.. 
    // replace with your own implementation 
    return peek(); 
} 

void HeapPQueue::enqueue(const string& elem) { 

    logSize++; 

    heap[logSize] = elem; 
    bubbleUp(logSize); 
} 

void HeapPQueue::bubbleUp(int i) { 
    if (i/2 == 0) return; 
    string insert = heap[i]; 
    string node = heap[i/2]; 
    if (insert >= node) return; 

    heap[i] = node; 
    heap[i/2] = insert; 
    bubbleUp(i/2); 
} 

HeapPQueue *HeapPQueue::merge(HeapPQueue *one, HeapPQueue *two) { 
    // placeholder so method compiles.. 
    // replace with your own implementation 
    return new HeapPQueue(); 
} 

logSize는 여기에서 pqueue 헤더 파일에 언급되어 있습니다.

/** 
* File: pqueue.h 
* -------------- 
* Defines the interface that all PQueues must implement. VectorPQueue, 
* HeapPQueue, and BinomialHeapPQueue all subclass PQueue so that they 
* all agree on the same interface. 
*/ 

#ifndef _pqueue_ 
#define _pqueue_ 

#include <string> 

/** 
* Defines the PQueue container type for strings. The priority queue 
* holds all enqueued strings, but rather than making them accessible 
* in a FIFO manner, extractMin produces the alphabetically smaller strings 
* before the alphabetically larger ones, regardless of insertion order. 
* 
* The generalization of this would be a templated priority queue, useful 
* in a large number of algorithmic settings (optimization problems, simulations, 
* shortest path problems, network routing, etc.) 
*/ 

class PQueue { 
public: 

/** 
* Defines a small set of constants that can be used to identify 
* the particular implementation of interest. They're most vital to 
* the construction of a PQueue using the factory method, as with 
* 
*  PQueue *pq = PQueue::createPQueue(PQueue::BinomialHeap); 
*  
* Enumerated constants are programmatically easier to manage than 
* type names, and it's easy to internally dispatch on enumerated 
* type constants than it is to on type names. 
*/ 

    enum PQueueType { 
     UnsortedVector, LinkedList, Heap, BinomialHeap 
    }; 

/** 
* Convenience function that gives us a string name for the 
* PQueue represented by type. 
*/ 

    static std::string typeToName(PQueueType type); 

public: 

/** 
* Manages the initialization of the material managed at the PQueue, 
* base class, level. We assume that all subclasses, regardless of 
* implementation, track their logical size using the logSize 
* parameter held at the PQueue class level. By doing so, we can 
* rely on a single implementation of the isEmpty() and size() methods 
* that never have to be overridden. Construction at this level is 
* so obvious that we just inline the implementation. 
*/ 

    PQueue() { logSize = 0; } 

/** 
* Disposes of any external resources held at the PQueue level. 
* Nothing, save for an internal int, is managed at the PQueue level, 
* so the destructor is inlined here. 
*/ 

    virtual ~PQueue() {} 

    static PQueue *createPQueue(PQueueType type); 
    static PQueue *merge(PQueue *one, PQueue *two); 

/** 
* Returns the number of elements inside the PQueue. This 
* method should not be overridden, and subclasses properly 
* maintain the value of logSize so that the implementation 
* provided here is always correct. 
*/ 

    int size() const { return logSize; } 

/** 
* Returns true if and only if the PQueue is empty. Self-explanatory, 
* save for the fact that isEmpty should not be overridden. 
*/ 

    bool isEmpty() const { return size() == 0; } 

/** 
* Inserts the provided string into the priority queue as the 
* implementation sees fit. The virtual keyword, paired with the 
* = 0, is C++ notation stating that no sensible implementation 
* exists at this level, and that concrete subclasses should 
* provide one. 
*/ 

    virtual void enqueue(const std::string& elem) = 0; 

/** 
* Identifies, removes, and returns the lowest-priority element currently 
* in the priority queue. The behavior is undefined if called against 
* an empty queue. The virtual keyword, paired with the 
* = 0, is C++ notation stating that no sensible implementation 
* exists at this level, and that concrete subclasses should 
* provide one. 
*/ 

    virtual std::string extractMin() = 0; 

/** 
* Returns a copy of the lowest-priority item currently within 
* the queue. The virtual keyword, paired with the 
* = 0, is C++ notation stating that no sensible implementation 
* exists at this level, and that concrete subclasses should 
* provide one. 
*/ 

    virtual std::string peek() const = 0; 

protected: 

/** 
* Maintains a copy of the size of the priority queue, regardless of the 
* subclass's implementation. Care much be taken to ++ and -- this 
* field (visible to all suclasses because of the protected access modifier) 
* with each call to enqueue and extractMin, and that the logSize is properly 
* updated with each merge. 
*/ 

    int logSize; 
}; 

#endif 

heappqueue의 헤더 파일입니다.

#ifndef _binary_heap_pqueue_ 
#define _binary_heap_pqueue_ 

#include "pqueue.h" 
#include <string> 

class HeapPQueue : public PQueue { 
public: 
    HeapPQueue(); 
    ~HeapPQueue(); 

    static HeapPQueue *merge(HeapPQueue *one, HeapPQueue *two); 

    void enqueue(const std::string& elem); 
    std::string extractMin(); 
    std::string peek() const; 

private: 

    std::string *heap; 
    void bubbleUp(int logSize); 
    // provide data methods and helper methods to 
    // help realize the binary heap-backed PQueue 
}; 

#endif 

다음은 클래스를 대기열에 넣는 방법입니다.

template <typename Iterable> 
static PQueue *buildPQueue(PQueue::PQueueType pqtype, Iterable iter, int size) { 
    PQueue *pq = PQueue::createPQueue(pqtype); 
    int count = 0; 
    foreach (string key in iter) { 
     pq->enqueue(key); 
     count++; 
     if (count == size) break; 
    } 

    cout << "+ Inserted " << pq->size() << " words." << endl; 
    return pq; 
} 

다음은 구조체의 구조입니다.

static const struct { 
    PQueue::PQueueType type; 
    int reasonableTestSize; 
} testParameters[] = { 
    { PQueue::UnsortedVector, 10000}, 
    { PQueue::LinkedList, 10000}, 
    { PQueue::Heap, INT_MAX}, 
    { PQueue::BinomialHeap, INT_MAX} 
}; 

Answer 1

당신이 logSize를 초기화하지 않습니다 보여 생성자. 이것은 적어도 문제의 일부일 수 있습니다.

또한 heap은 고정 크기이며 enqueue()은 오버플로를 확인하지 않습니다.

Answer 2

의 슬롯 0을 사용하지 않습니다. 대신 postSize를 증가 시키십시오. 또한 배열 힙에 액세스하기 전에 어떤 종류의 경계 검사가 있어야합니다.

void HeapPQueue::enqueue(const string& elem) { 
     heap[logSize] = elem; 
     bubbleUp(logSize); 
     logSize++; 
    }