数据结构-图(邻接多重表)(c++实现)

#include
using namespace std;

//图的邻接多重表表示法

//邻接多重表在两个顶点有同一个边的情况下只会存储一个边结点	析构时每个节点只能释放一次



class node					//边结点
{
public:
	node(int _x,int _y);
	
	node();
	
	~node();

	node* one, *two;
	
	int x, y;
};

node::node(int _x,int _y) { one = nullptr; two = nullptr; x = _x; y = _y; }

node::node() { one = nullptr; two = nullptr; x = 0; y = 0; }

node::~node() { one = nullptr; two = nullptr; x = 0; y = 0; }



template	//顶点结点
class table
{
public:
	table();
	table(T _data);
	~table();

	T data;

	node* next;
};

template
table::table() { data = NULL; next = nullptr;}

template
table::table(T _data) { data = _data; next = nullptr; }

template
table::~table() { data = NULL; next = nullptr; }


template
class map
{
public:
	map(T _data[],int _len);
	~map();

	void print();

private:

	void remove(table* M);		//清空边结点

	table* M;					//顶点表

	int len;						//表长

	int side;						//边的数量

};


template						//邻接多重表构建图
map::map(T _data[], int _len)
{
	//开辟空间
	
	len = _len - 1;

	M = new table[len];

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

	//添加边
	int num;
	cout << "输入边的数量：";
	cin >> num;

	side = num;

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

	for (int _i = 0; _i < num; _i++)
	{
		int i, j;
		cout << "输入边在数组中的起始位置：";
		cin >> i;
		cout << "输入边在数组中的结束位置：";
		cin >> j;

		//判断下标是否在数组中存在 -- 此处省略

		node* p = new node(i, j);

		if (M[i].next == nullptr) { M[i].next = p; }
		else
		{
			node* temp = M[i].next;
			bool flag = true;
			while (flag)
			{
				if (temp->x == i)							//边的起始位置为当前结点
				{
					if (temp->one != nullptr) { temp = temp->one; }
					else { flag = false; }
				}
				else										//边的结束位置为当前结点
				{
					if (temp->two != nullptr) { temp = temp->two; }
					else { flag = false; }
				}
			}
			if (temp->x == i) { temp->one = p; }			//建立的边以此结点为起始位置
			else { temp->two = p; }							//建立的边以此结点为结束位置
										
		}

		if (M[j].next == nullptr) { M[j].next = p; }
		else
		{
			node* temp = M[j].next;
			bool flag = true;
			while (flag)
			{
				if (temp->y == j)							//边的起始位置为当前结点
				{
					if (temp->two != nullptr) { temp = temp->two; }
					else { flag = false; }
				}
				else										//边的结束位置为当前结点
				{
					if (temp->one != nullptr) { temp = temp->one; }
					else { flag = false; }
				}
			}
			if (temp->x == i) { temp->one = p; }			//建立的边以此结点为起始位置
			else { temp->two = p; }							//建立的边以此节点为结束位置
		}
	}
}

template
void map::print()
{
	for (int i = 0; i < len; i++)
	{
		cout << M[i].data << "tt";
		
		if (M[i].next != nullptr) 
		{ 
			node* temp = M[i].next; 
			bool flag = true;

			while (flag)
			{
				if (temp->x == i)
				{
					cout << temp->x << " " << temp->y << " - ";
					if (temp->one != nullptr) { temp = temp->one; }
					else { flag = false; }
				}
				else 
				{
					cout << temp->x << " " << temp->y << " - ";
					if (temp->two != nullptr) { temp = temp->two; }
					else { flag = false; }
				}
			}
			cout << endl;
		}
	}
}

template			//析构
map::~map() 
{
	remove(M);
	delete[]M;
	M = nullptr;
	len = 0;
	side = 0;
}

template										//清空边结点
void map::remove(table* M)
{
	node** arr = new node*[side];								//存储边结点指针的数组

	int num = 0;

	for (int i = 0; i < len; i++)		
	{
		if (M[i].next != nullptr)
		{
			node* temp = M[i].next;
			bool flag = true;
			while (flag)
			{
				if (temp->x == i)							//x == i 时 该边结点为访问元素所发出的边
				{											//因为边结点是共用的 只记录结点发出的或者接收的即可 -- 此处记录发出的
															//遍历数组中是否存在该边	--	存在则不置入数组 反之置入
					bool ret = true;
					for (int j = 0; j < num; j++) 
					{ 
						if (arr[j]->x == temp->x && arr[j]->y == temp->y) { ret = false; }//该边在数组中存在标志置为false
					}

					if (ret == true) { arr[num] = temp; num++; }				//边不存在 存入数组中数组元素个数+1

					if (temp->one != nullptr) { temp = temp->one; }				//表结点有后继边 继续深入
					else { flag = false; }										//此边结点无后继边 循环结束
				}
				else 
				{
					if (temp->two != nullptr) { temp = temp->two; }				//不为此结点发出的边 进入下一边结点
					else { flag = false; }										//此边结点无后后继边 循环结束
				}
			}
		}
	}

	//测试代码 查看数组中的结点是否为为需要释放的边结点

	

	delete[]arr;
	arr = nullptr;
}