对于我的 C++ 数据结构类，我们正在实现一个拨号调制解调器模拟器。我们的教授给了我们一个使用 STL 优先级队列的工作源文件，但我们的工作是通过实现二进制堆来替换它。今天我去找她寻求帮助，了解二进制堆到底是什么，但她基本上告诉我和我的朋友转移到 IT :(。她周一才开始谈论它，优先级队列和二进制堆，哪个她在一个小时内冲了过去，她今天开始谈论一个新主题，因为她的幻灯片还没有完成，所以她将在周五恢复二进制堆，这是程序到期的时候。
我明白这一点，二进制堆是优先级队列的后端。但是当元素被插入或弹出时我是否排序？她提到使用向量或列表，当你只是建造一棵树时，它在哪里发挥作用？我也不明白为什么这段代码适用于她：
typedef priority_queue<Event,vector<Event>,greater<Event> > PQ;
这就是您声明 STL 优先级队列的方式吗？该程序很难描述，因此我将其粘贴在底部。它只是一个源文件。
注意：Random.h 仅具有根据某些统计分布返回随机数的函数。
调制解调器Simu.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;
}