そこで、私の問題を、このサイトのこのカテゴリから発生した問題の膨大なライブラリと比較しました。コンパイラが不平を言っている理由については、まだ手がかりがありません。
それでは、私のプログラムで何をしたいのかについて簡単に説明させてください。エレベーターのアルゴリズムを研究しています。バイナリ ヒープを使用してプライオリティ キューを実装したいと考えています。
マーク・アレン・ヴィースのウェブサイトからソースコードを入手しました。ヒープ用。
二分木のノードを表す独自の reqnode クラスを構築しています。
reqnode = リクエストノード。
シナリオは次のとおりです。ユーザーがリクエストを行います。リクエストにお応えします。複数のリクエストを処理しています。したがって、どのユーザーが最初に満足するかという優先順位を使用する必要があります。
これは、バイナリ ヒープのヘッダー ファイルです。
#include <vector>
using namespace std;
BinaryHeap class.
CONSTRUCTION: with no parameters or vector containing items.
template <class Comparable>
class BinaryHeap
{
public:
BinaryHeap( );
BinaryHeap( const vector<int> & v );
bool isEmpty( ) const;
const Comparable & findMin( ) const;
void insert( const Comparable & x);
void deleteMin( );
void deleteMin( Comparable & minItem );
void makeEmpty( );
private:
int theSize; // Number of elements in heap
vector<Comparable> Array; // The heap Array
void buildHeap( );
void percolateDown( int hole );
};
これらは、バイナリ ヒープ用に定義された関数です。
#include "binaryHeap.h"
using namespace std;
// Construct the binary heap.
template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap( )
: Array( 11 ), theSize( 0 )
{
}
// Insert item x into the priority queue, maintaining heap order.
// Duplicates are allowed.
template <class Comparable>
void BinaryHeap<Comparable>::insert( const Comparable & x)
{
Array[ 0 ] = x; // initialize sentinel
if( theSize + 1 == Array.size( ) )
Array.resize( Array.size( ) * 2 + 1 );
// Percolate up
int hole = ++theSize;
for( ; x < Array[ hole / 2 ]; hole /= 2 )
Array[ hole ] = Array[ hole / 2 ];
Array[ hole ] = x;
}
// Find the smallest item in the priority queue.
// Return the smallest item, or throw UnderflowException if empty.
template <class Comparable>
const Comparable & BinaryHeap<Comparable>::findMin( ) const
{
if( isEmpty( ) ){
cout << "heap empty" << endl; //throw UnderflowException( );
break;
}
return Array[ 1 ];
}
// Remove the smallest item from the priority queue.
// Throw UnderflowException if empty.
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( )
{
if( isEmpty( ) ){
cout << "heap empty" << endl; //throw UnderflowException( );
break;
}
Array[ 1 ] = Array[ theSize-- ];
percolateDown( 1 );
}
// Remove the smallest item from the priority queue
// and place it in minItem. Throw UnderflowException if empty.
template <class Comparable>
void BinaryHeap<Comparable>::deleteMin( Comparable & minItem )
{
minItem = findMin( );
Array[ 1 ] = Array[ theSize-- ];
percolateDown( 1 );
}
// Establish heap-order property from an arbitrary
// arrangement of items. Runs in linear time.
template <class Comparable>
void BinaryHeap<Comparable>::buildHeap( )
{
for( int i = theSize / 2; i > 0; i-- )
percolateDown( i );
}
// Test if the priority queue is logically empty.
// Return true if empty, false otherwise.
template <class Comparable>
bool BinaryHeap<Comparable>::isEmpty( ) const
{
return theSize == 0;
}
// Make the priority queue logically empty.
template <class Comparable>
void BinaryHeap<Comparable>::makeEmpty( )
{
theSize = 0;
}
// Internal method to percolate down in the heap.
// hole is the index at which the percolate begins.
template <class Comparable>
void BinaryHeap<Comparable>::percolateDown( int hole )
{
int child;
Comparable tmp = Array[ hole ];
for( ; hole * 2 <= theSize; hole = child )
{
child = hole * 2;
if( child != theSize && Array[ child + 1 ] < Array[ child ] )
child++;
if( Array[ child ] < tmp )
Array[ hole ] = Array[ child ];
else
break;
}
Array[ hole ] = tmp;
}
これは、reQnode のヘッダー ファイルです。
class reqNode//create a node that takes in several properties.
{
public:
reqNode(){ //default constructor
static priority = start = destination = timestamp = start_time = finish_time = -1;
}
reqNode(const reqNode ©){ //copy constructor
priority = copy.priority;
start = copy.start;
destination = copy.destination;
timestamp = copy.timestamp;
start_time = copy.start_time;
finish_time = copy.finish_time;
}
reqNode & operator=(const reqNode & copy){
priority = copy.priority;
start = copy.start;
destination = copy.destination;
timestamp = copy.timestamp;
start_time = copy.start_time;
finish_time = copy.finish_time;
return *this;
}
int priority, start, destination, timestamp, start_time, finish_time;
bool direction;
bool operator<(reqNode &rhs){
if(this->priority < rhs.priority)
return true;
else
return false;
}
void setPriority(int x){
priority=x;
}
};
これは私のドライバーの実装です
#include <iostream>
#include <fstream>
#include <string>
#include "binaryHeap.h"
#include "reqnode.h"
#include <algorithm>
using namespace std;
void setNode(reqNode nizzode, int priority)
{
nizzode.priority = priority;
}
int main()
{
int numItems = 10000;
BinaryHeap<reqNode> h;
int i = 37;
reqNode x;
reqNode * temp;
for( i = 37; i != 0; i = ( i + 37 ) % numItems ){
temp = new reqNode;
temp->setPriority(i);
h.insert( *temp );
}
for( i = 1; i < numItems; i++ )
{
h.deleteMin( x );
if( x.priority != i )
cout << "Oops! " << i << endl;
}
for( i = 37; i != 0; i = ( i + 37 ) % numItems ){
temp = new reqNode;
temp->setPriority(i);
h.insert( *temp );
}
temp = new reqNode;
temp->setPriority(i);
h.insert( *temp );
return 0;
}
最後に、これらは私を悩ませているエラーです!
1>Driver2.obj : error LNK2019: unresolved external symbol "public: void __thiscall BinaryHeap<class reqNode>::deleteMin(class reqNode &)" (?deleteMin@?$BinaryHeap@VreqNode@@@@QAEXAAVreqNode@@@Z) referenced in function _main
1>Driver2.obj : error LNK2019: unresolved external symbol "public: void __thiscall BinaryHeap<class reqNode>::insert(class reqNode const &)" (?insert@?$BinaryHeap@VreqNode@@@@QAEXABVreqNode@@@Z) referenced in function _main
1>Driver2.obj : error LNK2019: unresolved external symbol "public: __thiscall BinaryHeap<class reqNode>::BinaryHeap<class reqNode>(void)" (??0?$BinaryHeap@VreqNode@@@@QAE@XZ) referenced in function _main
1>C:\Users\Aaron Artis\Documents\Visual Studio 2010\Projects\Elevator_Algo_Remix1\Debug\Elevator_Algo_Remix1.exe : fatal error LNK1120: 3 unresolved externals
この問題を特定する場所がわかりません。以前のリンカー エラーがありました。解決しました。これはちょうどおかしなことのようです。