活动选择问题.cpp

算法设计与分析的实验

//活动选择问题

#include "iostream"
using namespace std;

typedef struct act  //定义一种新类型act
{
	int start;
	int finish;
}act;

class Activity //定义一个Activity类 
{
public:
    void Init_Activity();   //输入数据
    void Activity_Select();  //活动选择输出
    void Sort_Activity();    //比较排序
protected:
    act *a;
    int num;
    int *sorted;
};

void Activity::Init_Activity()
{
	cout<<"请输入活动个数:";    
	cin>>num;                     //输入活动的个数
	a=new act[num];
	sorted=new int[num];
	int i;
	for(i=0;i<num;i++)
	{
		cout<<"请输入活动"<<i+1<<"的开始时间:";
		cin>>a[i].start;  //输入活动i+1的开始时间
		cout<<"请输入活动"<<i+1<<"的结束时间:";
		cin>>a[i].finish; //输入活动i+1的结束时间
		if(a[i].finish<a[i].start)  //结束时间不能小于开始时间
		{
			cout<<"活动时间错误!"<<endl; 
			i--;
		}
		sorted[i]=i;
	}
	Sort_Activity();
}

void Activity::Sort_Activity()  
{
	int i,j,h=0;
	for(i=0;i<num;i++)
		for(j=0;j<num-i-1;j++)
		{
			if(a[j].finish>a[j+1].finish)
			{//如果j的结束时间大于j+1的结束时间就执行下面语句
				act b;
				int  c;
				c=sorted[j];
				sorted[j]=sorted[j+1];
				sorted[j+1]=c;
				b.finish=a[j].finish;
				b.start=a[j].start;
				a[j].finish=a[j+1].finish;
				a[j].start=a[j+1].start;
				a[j+1].finish=b.finish;
				a[j+1].start=b.start;
			}
		h++;}
		cout<<"关键语句执行次数:";
		cout<<h<<endl;
}


void Activity::Activity_Select()
{
	int i,finish=a[0].finish;
	cout<<sorted[0]+1;    //输出第一个活动序号
	for(i=1;i<num;i++)
	{
		if(a[i].start>=finish)
		{
			finish=a[i].finish;
			cout<<"->"<<sorted[i]+1;   //输出其它符合条件的活动序号
		}
	}
	cout<<endl;
}

int main(int argc, char* argv[]) //主函数
{
	Activity a;
	a.Init_Activity();
	a.Activity_Select();
	return 0;
}