数据结构-有向图(邻接表)(c++实现)

#include
using namespace std;

//有向图的邻接表表示法

//弧结点
class node
{
public:
	node(int num);
	~node();

	int index;		//在顶点表中的下标

	node* out;		//出度结点

};

//构造
node::node(int num) { index = num; out = nullptr; }

//析构
node::~node() { index = 0; out = nullptr; }


//表元素
template
class table
{
public:
	table();
	table(T _data);
	~table();

	T data;

	node* out;
};

template		//有参构造
table::table(T _data) { data = _data; out = nullptr; }


template		//无参构造
table::table() { data = NULL; out = nullptr; }


template		//析构
table::~table() { data = NULL; out = nullptr; }



//图
template
class map
{
public:
	map(T _data[],int len);
	~map();
	void print();


private:

	table* M;			//顶点表

	int length;				//表长

};


template			//图的邻接表构造
map::map(T data[],int len) 
{
	length = len - 1;

	M = new table[length];

	for(int i = 0; i < length;i++)
	{
		M[i].data = data[i];
	}

	//建立弧
	cout << "请输入弧的数量：";

	int num;
	cin >> num;

	if (num < 0 || num > length * (length - 1)) { cout << "数量有误！" << endl; return; }

	for (int i = 0; i < num; i++)
	{
		cout << "请输入弧尾元素的位置：";
		int k, z;
		cin >> k;
		cout << "请输入弧头元素的位置：";
		cin >> z;

		if (M[k].out == nullptr) 
		{ 
			node* p = new node(z);
			M[k].out = p; 
		}
		else
		{
			node* p = new node(z);
			node* temp = M[k].out;
			bool flag = true;
			while (flag)
			{
				if (temp->out != nullptr) { temp = temp->out; }
				else { flag = false; }
			}
			temp->out = p;
		}
	}
}


template		//析构
map::~map() 
{

	//释放弧结点
	for (int i = 0; i < length; i++)
	{
		if (M[i].out != nullptr)
		{
			node* temp = M[i].out;
			node* _temp = nullptr;
			bool flag = true;
			while (flag)
			{
				if (temp->out != nullptr)
				{
					_temp = temp->out;
					delete temp;
					temp = _temp;
				}
				else
				{
					delete temp;
					temp = nullptr;
					flag = false;
				}
			}
			_temp = nullptr;
		}
	}

	//释放顶点表
	delete[]M;			
	M = nullptr;		
	length = 0;
}


template		//遍历所有元素及它的出度弧
void map::print()
{
	for (int i = 0; i < length; i++)
	{
		cout << "弧尾元素： " << M[i].data << "tt" << "弧头结点下标为：";
		if(M[i].out != nullptr)
		{ 
			node* p = M[i].out; 
		
			bool flag = true;
			while (flag)
			{
				if (p->out != nullptr)
				{
					cout << p->index << "  ";		
					p = p->out;
				}
				else { cout << p->index << "  "; flag = false; }
			}
		}
		cout << endl;
	}
}