私の C++ データ構造クラスでは、ダイヤルアップ モデム シミュレータを実装しています。私たちの教授は、STL プライオリティ キューを使用する作業用ソース ファイルを提供してくれましたが、私たちの仕事は、バイナリ ヒープを実装することによってそれを置き換えることです。私は今日彼女に会いに行き、バイナリヒープとは何かについて助けてもらいましたが、彼女は基本的に私と私の友人にITに異動するように言いました:(.彼女は月曜日にプライオリティキューとバイナリヒープの両方について話し始めました。彼女は 1 時間で駆けつけました。今日はスライドが終わっていないので、新しい話題について話し始めたので、プログラムの期限である金曜日にバイナリ ヒープで再開する予定です。
ここまでは理解できましたが、バイナリヒープはプライオリティキューのバックエンドです。しかし、要素が挿入されているときやポップされているときにソートする必要がありますか? そして彼女はベクトルやリストを使用すると言いましたが、ツリーを構築しているとき、それはどこで機能しますか? また、このコードが彼女のコードで機能する理由もわかりません:
typedef priority_queue<Event,vector<Event>,greater<Event> > PQ;
それが STL プライオリティ キューを宣言する方法ですか? プログラムは説明が難しいので、一番下に貼り付けておきます。ソースファイルは 1 つだけです。
注: Random.h には、統計分布に従って乱数を返す関数しかありません。
modemSimu.cpp:
#include <queue>
#include <vector>
#include <functional> // for greater()
#include <climits> // for INT_MAX
#include <iostream>
#include "random.h"
using namespace std;
class Event{
enum { DIAL_IN = 1, HANGUP = 2 };
public:
Event( int name = 0, int tm = 0, int type = DIAL_IN )
: time( tm ), who( name ), what( type ) { }
bool operator> ( const Event & rhs ) const
{ return time > rhs.time; }
friend class ModemSim;
private:
int who; // the number of the user
int time; // when the event will occur
int what; // DIAL_IN or HANGUP
};
typedef priority_queue<Event,vector<Event>,greater<Event> > PQ;
class ModemSim{
public:
ModemSim( int modems, double avgLen, int callIntrvl );
// Add a call to eventSet at the current time,
// and schedule one for delta in the future.
void nextCall( int delta );
// Run the simulation
void runSim( int stoppingTime = INT_MAX );
private:
Random r; // A random source
PQ eventSet; // Pending events
// Basic parameters of the simulation
int freeModems; // Number of modems unused
const double avgCallLen; // Length of a call
const int freqOfCalls; // Interval between calls
};
// Constructor for ModemSim.
ModemSim::ModemSim( int modems, double avgLen, int callIntrvl )
: freeModems( modems ), avgCallLen( avgLen ),
freqOfCalls( callIntrvl ), r( (int) time( 0 ) )
{
nextCall( freqOfCalls ); // Schedule first call
}
// Place a new DIAL_IN event into the event queue.
// Then advance the time when next DIAL_IN event will occur.
// In practice, we would use a random number to set the time.
void ModemSim::nextCall( int delta ){
static int nextCallTime = 0;
static int userNum = 0;
eventSet.push( Event( userNum++, nextCallTime ) );
nextCallTime += delta;
}
// Run the simulation until stopping time occurs.
void ModemSim::runSim( int stoppingTime ){
static Event e;
int howLong;
while( !eventSet.empty( ) ){
e = eventSet.top( );
eventSet.pop( );
if( e.time > stoppingTime )
break;
if( e.what == Event::HANGUP ) // HANGUP
{
freeModems++;
cout << "User " << e.who << " hangs up at time "
<< e.time << endl;
}
else // DIAL_IN
{
cout << "User " << e.who << " dials in at time "
<< e.time << " ";
if( freeModems > 0 )
{
freeModems--;
howLong = r.negExp( avgCallLen );
cout << "and connects for "
<< howLong << " minutes" << endl;
e.time += howLong;
e.what = Event::HANGUP;
eventSet.push( e ); // insert HANGUP
}
else
cout << "but gets busy signal" << endl;
nextCall( freqOfCalls );
}
}
}
// Simple main to test ModemSim class.
int main( )
{
int numModems;
int totalTime;
double avgConnectTime;
int dialInFrequency;
cout << "Enter number of modems, length of simulation,\n"
<< " average connect time, how often calls occur: ";
cin >> numModems >> totalTime >>
avgConnectTime >> dialInFrequency;
ModemSim s( numModems, avgConnectTime, dialInFrequency );
s.runSim( totalTime );
return 0;
}