邻接多重表、十字链表、边集数组

关于数据结构的一个整理：

1、链式有序表的合并

2、栈

3、队列

4、二叉树、哈夫曼报文

5、图论

6、十大排序

7、校园导航系统

1、邻接多重表

1、顶点头文件：VertexNode.h

#pragma once
#include"ArcNode.h"
template<class T>
class VertexNode
{
private:
	T data;
	ArcNode<T>* firstedge;
public:
	VertexNode() :firstedge(nullptr) {}
	void set_data(T ata) {
		this->data = ata;
	}
	T get_data() {
		return data;
	}
	void set_firstedge(ArcNode<T>* ik) {
		this->firstedge = ik;
	}
	ArcNode<T>* get_firstedge() {
		return firstedge;
	}
};

2、弧结点头文件：ArcNode.h

#pragma once
template<class T>
class ArcNode
{
private:
	int mark;					//访问标记   0 代表未访问
	int ivex, jvex;				//该边依附两个顶点的的位置
	ArcNode<T>* ilink, * jlink;	//分别指向依附这2个顶点的下一条边
public:
	ArcNode() :ivex(0), jvex(0), ilink(nullptr), jlink(nullptr), mark(0) {}
	void set_mark(int i) {
		this->mark = i;
	}
	int get_mark() {
		return mark;
	}
	void set_ivex(int i1) {
		this->ivex = i1;
	}
	int get_ivex() {
		return ivex;
	}
	void set_jvex(int i2) {
		this->jvex = i2;
	}
	int get_jvex() {
		return jvex;
	}
	void set_ilink(ArcNode<T>* it) {
		this->ilink = it;
	}
	ArcNode<T>* get_ilink() {
		return ilink;
	}
	void set_jlink(ArcNode<T>* ik) {
		this->jlink = ik;
	}
	ArcNode<T>* get_jlink() {
		return jlink;
	}
};

3、cpp文件：UNGraphList.cpp

#include<iostream>
#include"ArcNode.h"
#include"VertexNode.h"
#include<Windows.h>
#include<string>
#include<queue>
using namespace std;
const int MAXNUM = 20;//常量表示数组的空间及顶点数组的空间
bool visited[MAXNUM] = { 0 };//初值设为0
typedef string type;//初始类型设为string
template<class T>
class ListGraph
{
private:
	int vernum, arcnum;//顶点数，弧数
	VertexNode<type>* vertex_arr[MAXNUM];//顶点指针数组
public:
	ListGraph();//构造函数
	~ListGraph();//析构函数
	void run();
	int GetIndexByVertexVal(T data);//得到顶点下标
	bool DestoryGraph();//销毁图
	bool DeleteArc(int i, int j);//删除弧
	void DeleteVex(T data);//删除顶点
	void CreateGraphs();//创建图
	void Display();//输出图
	int ComputeDegree(int i);//计算度
};

template<class T>
ListGraph<T>::ListGraph()
{
	vernum = 0;//顶点个数
	arcnum = 0;//弧个数
	for (int i = 0; i < MAXNUM; i++) {
		vertex_arr[i] = nullptr;//顶点指针数组置空
	}
}

template<class T>
ListGraph<T>::~ListGraph()
{
	DestoryGraph();//调用销毁函数
}

template<class T>
int ListGraph<T>::GetIndexByVertexVal(T data)//获得数据data的下标
{
	for (int i = 0; i < vernum; ++i)
	{
		if (data == vertex_arr[i]->get_data())
			return i;
	}
	return -1;
}

template<class T>
bool ListGraph<T>::DestoryGraph()//销毁函数
{
	for (int i = vernum - 1; i >= 0; i--) { 
		DeleteVex(vertex_arr[i]->get_data());
	}
	return true;
}

template<class T>
bool ListGraph<T>::DeleteArc(int i, int j)//删除边
{
	//i和j是要两个顶点的下标
	ArcNode<T>* p = nullptr, * q = nullptr;
	//以i下标为起点的顶点开始遍历
	p = vertex_arr[i]->get_firstedge();//p指向顶点i的第1条边
	if (p && p->get_jvex() == j) {//i的临边要是j，因为邻接表有两个下标都要进行判断所以比较i和j
		vertex_arr[i]->set_firstedge(p->get_ilink());
	}//如果是第一条边则直接连接顶点
	else if (p && p->get_ivex() == j) {
		vertex_arr[i]->set_firstedge(p->get_jlink());
	}
	else//第1条边不是待删除边
	{
		while (p)//向后查找弧<i，j>
		{//ivex确保是此顶点下标，jvex找待删除边
			if (p->get_ivex() == i && p->get_jvex() != j)//不是待删除边
			{
				q = p;
				p = p->get_ilink();//找下一个邻接顶点
			}
			else if (p->get_jvex() == i && p->get_ivex() != j)//不是待删除边
			{
				q = p;
				p = p->get_jlink();//找下一个邻接顶点
			}
			else
			{
				break;//是邻接顶点w
			}
		}
		if (!p) { return 1; }//p为空则表示没有此边，直接退出
		if (p->get_ivex() == i && p->get_jvex() == j)//找到弧<i,j>(判断是否按ilink遍历的)
		{//q是p的前驱
			if (q->get_ivex() == i)
			{//p的前驱连接q的下一个
				q->set_ilink(p->get_ilink());
			}
			else
			{
				q->set_jlink(p->get_ilink());
			}
		}
		else if (p->get_ivex() == j && p->get_jvex() == i)//找到弧<i,j>(按jlink遍历)
		{
			if (q->get_ivex() == i)
			{
				q->set_ilink(p->get_jlink());
			}
			else
			{
				q->set_jlink(p->get_jlink());
			}
		}
	}
	//以j下标为起点的顶点开始遍历
	p = vertex_arr[j]->get_firstedge();//p指向顶点w的第1条边
	if (p->get_jvex() == i) {// 第1条边即为待删除边(情况1)
		vertex_arr[j]->set_firstedge(p->get_ilink());
	}
	else if (p->get_ivex() == i) {// 第1条边即为待删除边(情况2)
		vertex_arr[j]->set_firstedge(p->get_jlink());
	}
	else // 第1条边不是待删除边
	{
		while (p)//向后查找弧<i，j>
		{
			if (p->get_ivex() == j && p->get_jvex() != i)//不是待删除边
			{
				q = p;
				p = p->get_ilink();//找下一个邻接顶点
			}
			else if (p->get_jvex() == j && p->get_ivex() != i)//不是待删除边
			{
				q = p;
				p = p->get_jlink();//找下一个邻接顶点
			}
			else
			{
				break;//是邻接顶点w
			}
		}
		if (!p) { return 1; }
		if (p->get_ivex() == i && p->get_jvex() == j)//找到弧<i,j>(情况1)
		{
			if (q->get_ivex() == j)
			{
				q->set_ilink(p->get_jlink());
			}
			else
			{
				q->set_jlink(p->get_jlink());
			}
		}
		else if (p->get_ivex() == j && p->get_jvex() == i)//找到弧<i,j>(情况2)
		{
			if (q->get_ivex() == j)
			{
				q->set_ilink(p->get_ilink());
			}
			else
			{
				q->set_jlink(p->get_ilink());
			}
		}
	}
	delete p;//释放结点
	p = nullptr;
	arcnum--;//边数-1
	return 0;
}

template<class T>
void ListGraph<T>::DeleteVex(T data)
{
	int i = GetIndexByVertexVal(data);// i为待删除顶点的序号
	if (i == -1) {
		cout << "未找到此数据。" << endl;
		return;
	}
	for (int j = 0; j < vernum; j++)//删除与顶点i相连的边(如果有的话)
	{
		if (i != j) {
			DeleteArc(i, j);//如果存在此弧，则删除
		}
	}
	for (int j = i + 1; j < vernum; j++)//排在顶点v后面的顶点的序号减1
	{
		vertex_arr[j - 1] = vertex_arr[j];
	}
	vernum--; // 顶点数减1

	ArcNode<T>* p = nullptr, * q = nullptr;
	for (int j = i; j < vernum; j++) // 修改序号大于i的顶点在表结点中的序号
	{
		p = vertex_arr[j]->get_firstedge();
		if (p)
			if (p->get_ivex() == j + 1)//ivxe是此顶点的下标与j+1进行判断
			{
				p->set_ivex(p->get_ivex() - 1);
				p = p->get_ilink();
			}
			else
			{
				p->set_jvex(p->get_jvex() - 1);
				p = p->get_jlink();
			}
	}
}

template<class T>
void ListGraph<T>::CreateGraphs()//创造无向图
{
	int ding = 0, hu = 0;
	cout << "输入顶点个数和边数：";
	cin >> ding >> hu;
	if (hu == 0 && ding == 0)return;
	//判断越界
	int sss = vernum;//避免改动vernum
	if (sss + ding > MAXNUM) {
		cout << "StackOverflow！" << endl;
		return;
	}
	//无向图顶点与弧的最多个数是Cn2：n(n-1)/2
	if (!(arcnum + hu <= (sss + ding) * (sss + ding - 1) / 2)) {//判断弧的数
		cout << "你输入的弧的数量达到上限，强制退出，下次再输入。" << endl; system("pause"); 
		return;
	}
	//顶点数据输入
	for (int i = vernum; i < vernum + ding; i++) {
		vertex_arr[i] = new VertexNode<T>;//先开辟空间，不然无法使用get_data()
	}
	cout << "请输入" << ding << "个顶点" << endl;
	for (int i = vernum; i < vernum + ding; ++i)
	{
		cout << i + 1 << " :";
		T val;
		while (1) {
			bool f = false;
			cin >> val;
			for (int j = 0; j < vernum + ding; j++) {
				if (val == vertex_arr[j]->get_data()) {
					cout << "数据重复。重新输入：";
					f = true;
					break;
				}
			}
			if (!f)break;
		}
		vertex_arr[i]->set_data(val);
		vertex_arr[i]->set_firstedge(nullptr);
	}
	vernum += ding;//更新顶点个数

	//弧节点选择
	cout << "请输入由两个顶点构成的边" << arcnum + hu << "条" << endl;
	for (int i = arcnum; i < arcnum + hu; ++i)
	{
		int m = 0, n = 0;
		while (1) {
			bool f = false;
			T one, two;
			cout << "顶点one：";
			cin >> one;
			cout << "顶点two：";
			cin >> two;
			m = GetIndexByVertexVal(one);//查找顶点one和two的下标
			n = GetIndexByVertexVal(two);
			if (m == -1 || n == -1) {
				cout << "访问越界，不存在此弧，请再次输入" << endl;
				f = true;
			}
			else {//判断两个节点之间是否存在相同的边
				ArcNode<T>* p, * q;
				int max = 0, min = 0;
				if (m > n) {//确保顶点下标位置不反过来
					max = m;
					min = n;
				}
				else {
					max = n;
					min = m;
				}
				//过一遍ilink这个链表
				p = vertex_arr[min]->get_firstedge();//min就是自己的位置，max就是临边的下标
				while (p) {
					if (p->get_jvex() == max) {
						cout << "弧重复。重新输入*" << endl;
						f = true;
					}
					p = p->get_ilink();
				}
				//过一遍jlink这个链表
				q = vertex_arr[min]->get_firstedge();
				while (q) {
					if (q->get_ivex() == max) {
						cout << "弧重复。重新输入*" << endl;
						f = true;
					}
					q = q->get_jlink();
				}
			}
			if (!f)break;
		}
		//顶点下标，弧节点连接
		ArcNode<T>* arc = new ArcNode<T>;
		arc->set_ivex(m);
		arc->set_jvex(n);
		//表头连接m
		arc->set_ilink(vertex_arr[m]->get_firstedge());//表头插入法
		vertex_arr[m]->set_firstedge(arc);
		//表头连接n
		arc->set_jlink(vertex_arr[n]->get_firstedge());//表头插入法
		vertex_arr[n]->set_firstedge(arc);
		cout << "-----------------" << endl;
	}
	arcnum += hu;//更新弧的个数

	system("pause");
}

template<class T>
void ListGraph<T>::Display()
{	//输出无向图的邻接多重表
	//置边的访问标记为未被访问
	if (vernum > 0) {
		int i;
		ArcNode<T>* p = nullptr;
		for (i = 0; i < vernum; i++)
		{//从所有的顶点处开始遍历，将所有mark设为0
			p = vertex_arr[i]->get_firstedge();
			while (p)
			{
				p->set_mark(0);//0 未访问，1 已访问
				if (p->get_ivex() == i) {
					p = p->get_ilink();//若ivex不再是下标i是则表明在别的顶点中亦含有这条边，故跳到jlink中
				}
				else {
					p = p->get_jlink();
				}
			}
		}
		cout << vernum << "个顶点:" << endl;
		for (i = 0; i < vernum; ++i) { cout << vertex_arr[i]->get_data() << " "; }
		cout << endl << arcnum << "条边:" << endl;
		for (i = 0; i < vernum; i++)
		{
			p = vertex_arr[i]->get_firstedge();
			while (p)
				if (p->get_ivex() == i)//边的i端与该顶点有关
				{
					if (!p->get_mark())//只输出一次
					{
						cout << vertex_arr[i]->get_data() << "—" << vertex_arr[p->get_jvex()]->get_data() << endl;
						p->set_mark(1);
					}
					p = p->get_ilink();
				}
				else // 边的j端与该顶点有关
				{
					if (!p->get_mark())//只输出一次
					{
						cout << vertex_arr[p->get_ivex()]->get_data() << "—" << vertex_arr[i]->get_data() << endl;
						p->set_mark(1);
					}
					p = p->get_jlink();
				}
		}
	}
	else {
		cout << "图中无数据。" << endl;
	}
	cout << endl;
	system("pause");
}

template<class T>
int ListGraph<T>::ComputeDegree(int i)//计算下标为i的顶点的度
{
	int degree = 0;
	ArcNode<T>* p = vertex_arr[i]->get_firstedge();
	while (p) {
		if (p->get_ivex() == i || p->get_jvex() == i) {
			degree++;//度
		}
		if (p->get_ivex() == i) {//如果在自己这层则ilink遍历，否则指向jlink
			p = p->get_ilink();
		}
		else {
			p = p->get_jlink();
		}
	}
	return degree;
}

void menu()
{
	cout << "**********" << endl;
	cout << "-1.增加" << endl;
	cout << "-2.打印" << endl;
	cout << "-3.顶点的度" << endl;
	cout << "-4.销毁" << endl;
	cout << "-5.删除弧" << endl;
	cout << "-6.删除顶点" << endl;
	cout << "-0.退出  请选择：";
}

template<class T>
void ListGraph<T>::run()
{
	while (1)
	{
		system("cls");
		menu();
		string f1 = "";
		cin >> f1;
		cout << endl;
		if (f1 == "1") {
			CreateGraphs();
		}
		else if (f1 == "2") {
			Display();
		}
		else if (f1 == "3") {
			cout << "请输入顶点：";
			T data;
			cin >> data;
			int index = GetIndexByVertexVal(data);
			if (index == -1)
			{
				cout << "查找失败。" << endl;
			}
			else
			{
				cout << "该顶点的度是：" << ComputeDegree(index) << endl;
			}
			system("pause");
		}
		else if (f1 == "4") {
			if (vernum > 0) {
				cout << "销毁 " << vernum << " 个顶点。" << endl;
				DestoryGraph();
				cout << "销毁完成。" << endl;
			}
			else {
				cout << "图中没数据。" << endl;
			}
			system("pause");
		}
		else if (f1 == "5") {
			if (vernum > 0) {
				cout << "请输入两个顶点,删除它们的连线。" << endl;
				int i = 0, j = 0;
				while (1) {
					T one, two;
					cout << "顶点one：";
					cin >> one;
					cout << "顶点two：";
					cin >> two;
					i = GetIndexByVertexVal(one);
					j = GetIndexByVertexVal(two);
					if (i == -1 || j == -1) {
						cout << "访问越界，不存在此弧，请再次输入" << endl;
					}
					else if (i == j) {
						cout << "输入格式错误" << endl;
					}
					else {
						if (DeleteArc(i, j)) {
							cout << "不存在此弧。" << endl;
						}
						else {
							cout << "删除成功。" << endl;
						}
						break;
					}
				}
			}
			else {
				cout << "图中无数据。" << endl;
			}
			system("pause");
		}
		else if (f1 == "6") {
			if (vernum > 0) {
				cout << "请输入顶点,并删除它。" << endl;
				T data;
				cin >> data;
				DeleteVex(data);
				cout << "删除成功。" << endl;
			}
			else {
				cout << "图中无数据。" << endl;
			}
			system("pause");
		}
		else if (f1 == "0") {
			system("cls");
			cout << "\n\t\t期待您的再次使用！" << endl;
			break;
		}
	}
}

int main()
{
	ListGraph<type> graph;
	graph.run();
	return 0;
}

2、十字链表泛型

1、顶点节点文件：VertexNode.h

#pragma once
// 定义顶点结点
#include"ArcNode.h"
template<class T>
class VertexNode
{
private:
    T data;                 //存储有关顶点的信息
    ArcNode<T>* firstInarc; //链接到以该顶点为终点的第一条弧
    ArcNode<T>* firstOutarc;//链接到以该顶点为起点的第一条弧
public:
    // 构造函数
    VertexNode() : firstInarc(nullptr), firstOutarc(nullptr) {}
public:
    T get_data() {
        return data;
    }
    void set_data(T data) {
        this->data = data;
    }
    ArcNode<T>* get_firstInarc() {
        return firstInarc;
    }
    ArcNode<T>* get_firstOutarc() {
        return firstOutarc;
    }
    void set_firstInarc(ArcNode<T>* f) {
        this->firstInarc = f;
    }
    void set_firstOutarc(ArcNode<T>* t) {
        this->firstOutarc = t;
    }
};

2、弧结点文件：ArcNode.h

#pragma once
//定义弧结点
template<class T>
class ArcNode
{
private:
    int tailvex;            //弧尾
    int headvex;            //弧头
    //int weight;             //弧的权值
    ArcNode<T>* tailnextarc;//出弧
    ArcNode<T>* headnextarc;//入弧
    int tag = 0;            //标记域，标记该弧是否被处理或被搜索过 1表示删除
public:
    // 构造函数
    ArcNode(int tv, int hv) :tailvex(tv), headvex(hv),
        tailnextarc(nullptr), headnextarc(nullptr) {}
public:
    int get_tailvex() {
        return tailvex;
    }
    int get_headvex() {
        return headvex;
    }
    void set_tailvex(int t) {
        this->tailvex = t;
    }
    void set_headvex(int h) {
        this->headvex = h;
    }
    int get_tag() {
        return tag;
    }
    void set_tag(int flag) {
        this->tag = flag;
    }
    ArcNode<T>* get_tailnextarc() {
        return tailnextarc;
    }
    ArcNode<T>* get_headnextarc() {
        return headnextarc;
    }
    void set_tailnextarc(ArcNode<T>* f) {
        this->tailnextarc = f;
    }
    void set_headnextarc(ArcNode<T>* t) {
        this->headnextarc = t;
    }
};

3、GraphList.cpp：程序启动文件

#include <iostream>
#include<Windows.h>
#include"ArcNode.h"
#include"VertexNode.h"
using namespace std;
const int MAXNUM = 20;//顶点最大容量
typedef string type;
template<class T>
class ListGraph
{
private:
	int vernum, arcnum;//顶点数，弧数
	VertexNode<type>* vertex_arr[MAXNUM];//顶点指针数组
public:
	ListGraph();
	~ListGraph();
	bool DestoryGraph();//销毁图
	void use_InsertNode();//调用增加顶点的函数	
	void InsertNode(T value);//增加顶点
	void use_DeleteNode();//调用删除顶点的函数
	void DeleteNode(int pos_index);
	void use_InsertEdge();//调用增加弧的函数
	bool InsertEdge(int tail, int head);//添加弧
	void use_DeleteEdge();//调用删除弧的函数
	void DeleteEdge(int tail_index, int head_index);//删除弧
	void Print();//图的遍历
	void ComputeDegree();//计算度
};

template<class T>
ListGraph<T>::ListGraph()//构造函数
{
	vernum = 0;//顶点个数
	arcnum = 0;//弧个数
	for (int i = 0; i < MAXNUM; i++) {
		vertex_arr[i] = nullptr;
	}
}

template<class T>
ListGraph<T>::~ListGraph()//析构函数
{
	DestoryGraph();
}

template<class T>
bool ListGraph<T>::DestoryGraph()//销毁函数
{
	if (vernum <= 0)return false;
	for (int i = 0; i < vernum; i++) { // 释放所有顶点的内存空间
		ArcNode<T>* p = vertex_arr[i]->get_firstOutarc(), * q = NULL;
		while (p != NULL) { // 释放所有出弧节点的内存空间
			q = p;
			p = p->get_tailnextarc();
			delete q;
			q = nullptr;
		}
	}
	vernum = 0;
	arcnum = 0;
	return true;
}

template<class T>
void ListGraph<T>::use_InsertNode()//调用增加节点的函数
{
	if (vernum >= MAXNUM) {//顶点空间不够的话
		cout << "空间不够。" << endl; Sleep(3500); return;
	}
	int n;
	cout << "添加顶点个数：";
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cout << "第" << i << "个：";
		T data;
		while (1) {
			cin >> data;
			bool f = false;//为true则表明数据重复
			for (int i = 0; i < vernum; i++) {
				if (vertex_arr[i]->get_data() == data) {
					cout << "输入的顶点数据重复。重新输入：";
					f = true;
					break;
				}
			}
			if (!f)break;
		}
		InsertNode(data);//插入数据
	}
	cout << "添加顶点数据过程结束。" << endl;
	Sleep(350);
}

template<class T>
void ListGraph<T>::InsertNode(T value)//顶点数据的插入
{
	if (vernum >= MAXNUM) {
		cout << "顶点已经达到上限，不可添加了。" << endl;
		return;
	}
	cout << "将数据 " << value << " 存放到顶点为 " << vernum + 1 << " 的位置。" << endl;
	//添加新顶点到顶点数组
	vertex_arr[vernum] = new VertexNode<T>;
	vertex_arr[vernum]->set_data(value);
	vertex_arr[vernum]->set_firstInarc(NULL);
	vertex_arr[vernum]->set_firstOutarc(NULL);
	++vernum;//顶点自增
	cout << "Insert successful!" << endl;
}

template<class T>
void ListGraph<T>::use_DeleteNode()
{
	if (vernum > 0) {
		cout << "共有顶点数量：" << vernum << endl;
		cout << "请输入要删除的顶点结点数据：";
		T data;
		cin >> data;
		bool f = false;
		for (int i = 0; i < vernum; i++) {
			if (vertex_arr[i]->get_data() == data) {
				DeleteNode(i);
				f = true;
				break;
			}
		}
		if (f) {
			cout << "成功删除此节点的所有相关信息。" << endl;
		}
		else {
			cout << "未找到此数据的信息。" << endl;
		}
	}
	else {
		cout << "没有顶点数据。" << endl;
	}
	system("pause");
}

template<class T>
void ListGraph<T>::DeleteNode(int pos_index)
{
	//删除顶点的所有出度
	for (int j = 0; j < vernum; j++)
	{
		if (pos_index != j) {
			DeleteEdge(pos_index, j);//删除每个顶点与pos_index相关的边
		}
	}
	//删除所有顶点的入度
	for (int j = 0; j < vernum; j++)
	{
		if (pos_index != j) {
			DeleteEdge(j, pos_index);//删除每个顶点与pos_index相关的边
		}
	}
	for (int j = pos_index + 1; j < vernum; j++)//排在顶点v后面的顶点的序号减1
	{
		vertex_arr[j - 1] = vertex_arr[j];
	}
	vernum--; // 顶点数减1
	//标志
	ArcNode<T>* pq = nullptr;
	for (int i = 0; i < vernum; i++) {
		pq = vertex_arr[i]->get_firstOutarc();
		while (pq != NULL)
		{
			pq->set_tag(0);
			pq = pq->get_tailnextarc();
		}
	}
	//修改下标
	ArcNode<T>* p = nullptr;
	for (int j = 0; j < vernum; j++)//修改序号大于i的顶点在表结点中的序号
	{
		p = vertex_arr[j]->get_firstOutarc();//出度开始遍历
		while (p != NULL)
		{
			if (!p->get_tag()) {
				if (p->get_tailvex() > pos_index) {
					p->set_tailvex(p->get_tailvex() - 1);
				}
				if (p->get_headvex() > pos_index) {
					p->set_headvex(p->get_headvex() - 1);
				}
				p->set_tag(1);
			}
			p = p->get_tailnextarc();
		}
	}
}

template<class T>
void ListGraph<T>::use_InsertEdge()//调用增加边的函数
{
	cout << "共有顶点数量：" << vernum << endl;
	if (vernum < 2) {
		cout << "顶点不够，不能添加弧。" << endl; system("pause"); return;
	}
	int n = 0, max = 0;
	cout << "请输入添加边的数量：";
	cin >> n;
	max = vernum * (vernum - 1);//最多边数
	if (max < arcnum + n) {
		cout << "边数已经满了" << endl;
		system("pause");
		return;
	}
	while (n--) {
		int vh, vt;
		cout << "****" << endl;
		while (1)
		{
			cout << "出发点：";
			cin >> vt;
			cout << "终点：";
			cin >> vh;
			if (vt == vh) {
				cout << "输入错误。重新输入：" << endl;
			}
			else if (vt - 1 < vernum && vh - 1 < vernum) {
				InsertEdge(vt - 1, vh - 1);//数组下标从0开始
				break;
			}
			else {
				cout << "弧的位置越界。重新添加：" << endl;
			}
		}
	}
	Sleep(350);
}

template<class T>
bool ListGraph<T>::InsertEdge(int tail, int head)//添加边<tail,head>
{
	//添加新的弧 arc，这需要两部分连接出弧和入弧
	ArcNode<T>* arc = new ArcNode<T>(tail, head);
	//先检查是否已经存在该弧
	ArcNode<T>* arc1 = vertex_arr[tail]->get_firstOutarc();//出弧顶点
	while (arc1 != nullptr) {
		if (arc1->get_headvex() == head) {
			cout << "不可重复添加相同的弧。" << endl;
			return 0;
		}
		arc1 = arc1->get_tailnextarc();//出弧那么每个节点都是尾部
	}
	bool flag = false;
	//在起点的出弧中添加该弧
	if (vertex_arr[tail]->get_firstOutarc() == nullptr)
	{//顶点的下个为空的话，让出弧指向它
		vertex_arr[tail]->set_firstOutarc(arc);
		flag = true;
	}
	else {//尾插
		ArcNode<T>* next_arc = vertex_arr[tail]->get_firstOutarc();
		while (next_arc->get_tailnextarc() != nullptr) {//同一个起点的下一条弧
			next_arc = next_arc->get_tailnextarc();//找到一个空的弧头
		}
		next_arc->set_tailnextarc(arc);
		flag = true;
	}
	// 在终点的入弧中添加该弧
	if (vertex_arr[head]->get_firstInarc() == nullptr)
	{//被指向的顶点，也是入弧
		vertex_arr[head]->set_firstInarc(arc);
		flag = true;
	}
	else {
		ArcNode<T>* in_arc = vertex_arr[head]->get_firstInarc();
		while (in_arc->get_headnextarc() != nullptr) {//对到达同一终点的入弧遍历找空
			in_arc = in_arc->get_headnextarc();
		}
		in_arc->set_headnextarc(arc);
		flag = true;
	}
	if (flag) {
		arcnum++;//弧个数增加
		cout << "Arc insertion successful!" << endl;
		return 1;
	}
	else {
		cout << "Arc insertion failed!" << endl;
		return 0;
	}
}

template<class T>
void ListGraph<T>::use_DeleteEdge()//调用删除边的操作
{
	if (vernum < 2) {
		cout << "没有弧。" << endl; system("pause"); return;
	}
	int vh, vt;
	cout << "*每次只能删除一条弧。" << endl;
	while (1)
	{
		cout << "起点：";
		cin >> vt;
		cout << "终点：";
		cin >> vh;
		if (vt == vh) {
			cout << "输入错误。重新输入：" << endl;
		}
		else if (vt - 1 < vernum && vh - 1 < vernum) {
			//检查此弧是否存在
			bool f = false;
			ArcNode<T>* arc = vertex_arr[vt-1]->get_firstOutarc();//出弧顶点
			while (arc != nullptr) {
				if (arc->get_headvex() == vh-1) {
					f = true;
					DeleteEdge(vt-1, vh-1);
					break;
				}
				arc = arc->get_tailnextarc();//出弧那么每个节点都是尾部
			}
			if (f) {
				cout << "您已经成功删除了一条弧。" << endl;
			}
			else {
				cout << "该弧删除失败。" << endl;
			}
			break;
		}
		else {
			cout << "弧的位置越界。重新输入：" << endl;
		}
	}
	Sleep(350);
}

template<class T>
void ListGraph<T>::DeleteEdge(int tail_index, int head_index)//删除边<tail,head>
{
	ArcNode<T>* p = vertex_arr[tail_index]->get_firstOutarc(), * q = NULL;
	while (p != NULL && p->get_headvex() != head_index) { // 寻找待删除的弧节点
		q = p;
		p = p->get_tailnextarc();//找到待删除节点p
	}
	//未找到待删除的弧节点则返回
	if (p == NULL) {
		//cout << "未找到此弧节点。" << endl;
		return;
	}
	//出弧
	//待删除的是第一个出弧，则更新firstout指针
	if (q == NULL) {
		vertex_arr[tail_index]->set_firstOutarc(p->get_tailnextarc());
	}
	else
	{//待删除的不是第一个出弧，则修改前驱弧节点的next指针
		q->set_tailnextarc(p->get_tailnextarc());
	}
	//入弧
	//待删除的是第一个入弧，则更新firstin指针
	if (vertex_arr[head_index]->get_firstInarc() == p) {
		vertex_arr[head_index]->set_firstInarc(p->get_headnextarc());
	}
	else
	{//待删除的不是第一个入弧，则修改前驱弧节点的hlink指针
		q = vertex_arr[head_index]->get_firstInarc();
		while (q->get_headnextarc() != p) {
			q = q->get_headnextarc();//从入弧开始找节点p
		}
		q->set_headnextarc(p->get_headnextarc());//入弧的跳跃
	}
	delete p;//释放待删除的弧节点的内存空间
	p = nullptr;
}

template<class T>
void ListGraph<T>::Print()//打印我的图
{
	for (int i = 0; i < vernum; i++)
	{
		cout << "----------------------------------------" << endl;
		VertexNode<T>* ver = vertex_arr[i];//起初表示方法
		cout << "顶点位置：" << i + 1 << " 顶点数据:" << ver->get_data() << endl;//第一个顶点的数据
		ArcNode<T>* out_arc = ver->get_firstOutarc();//顶点出弧指针
		if (out_arc == nullptr)cout << "没有出弧。";//为空
		else {//各个顶点的出弧情况
			cout << "出:";
			while (out_arc != nullptr) {
				cout << out_arc->get_tailvex() + 1 << "->" << out_arc->get_headvex() + 1 << "  ";
				out_arc = out_arc->get_tailnextarc();
			}
		}
		cout << endl;
		ArcNode<T>* in_arc = ver->get_firstInarc();
		if (in_arc == nullptr)cout << "没有入弧。";
		else {//各个顶点的入弧情况
			cout << "入:";
			while (in_arc != nullptr) {
				cout << in_arc->get_tailvex() + 1 << "->" << in_arc->get_headvex() + 1 << "  ";
				in_arc = in_arc->get_headnextarc();
			}
		}
		cout << endl;
	}
	if (vernum == 0) { cout << "无数据。" << endl; }
	system("pause");
}

template<class T>
void ListGraph<T>::ComputeDegree()//计算出入度
{
	if (vernum > 0) {
		cout << "共有顶点数量：" << vernum << endl;
		cout << "请输入要看的顶点结点的出度和入度：";
		T data;
		cin >> data;
		bool f = false;
		for (int i = 0; i < vernum; i++) {
			if (vertex_arr[i]->get_data() == data) 
			{
				f = true;
				ArcNode<T>* q = NULL;
				int outDegree = 0, inDegree = 0;
				//计算顶点Vertex[i]的出度
				q = vertex_arr[i]->get_firstOutarc();
				while (q != NULL)
				{
					outDegree++;
					q = q->get_tailnextarc();
				}
				//计算顶点Vertex[i]的入度
				q = vertex_arr[i]->get_firstInarc();
				while (q != NULL)
				{
					inDegree++;
					q = q->get_headnextarc();
				}
				cout << "顶点" << vertex_arr[i]->get_data() << "的出度为" << outDegree << endl;
				cout << "顶点" << vertex_arr[i]->get_data() << "的入度为" << inDegree << endl;
				break;
			}
		}
		if (!f) { cout << "未查到此顶点数据。" << endl; }
	}
	else {
		cout << "没有顶点数据。" << endl;
	}
	system("pause");
}

void menu()
{
	cout << "**********" << endl;
	cout << "-1.增加顶点" << endl;
	cout << "-2.删除顶点" << endl;
	cout << "-3.增加弧" << endl;
	cout << "-4.删除弧" << endl;
	cout << "-5.打印" << endl;
	cout << "-6.顶点的度" << endl;
	cout << "-7.销毁" << endl;
	cout << "-0.退出  请选择：";
}

void run()
{
	ListGraph<type> graph;
	while (1)
	{
		system("cls");
		menu();
		string f1 = "";
		cin >> f1;
		cout << endl;
		if (f1 == "1") {
			graph.use_InsertNode();
		}
		else if (f1 == "2") {
			graph.use_DeleteNode();
		}
		else if (f1 == "3") {
			graph.use_InsertEdge();
		}
		else if (f1 == "4") {
			graph.use_DeleteEdge();
		}
		else if (f1 == "5") {
			graph.Print();
		}
		else if (f1 == "6") {
			graph.ComputeDegree();
		}
		else if (f1 == "7") {
			bool f = graph.DestoryGraph();
			if (f) {
				cout << "销毁完成。" << endl;
			}else{
				cout << "无顶点数据。" << endl;
			}
			system("pause");
		}
		else if (f1 == "0") {
			system("cls");
			cout << "\n\t\t期待您的再次使用！" << endl;
			break;
		}
	}
}

int main()
{
	run();
	return 0;
}

3、边集数组

头文件

EdgeNode.h

#pragma once
template<class T>
class EdgeNode 
{
private:
    int begin;
    int end;
public:
    bool operator==(const EdgeNode& obj) const {
        if (begin == obj.begin && end == obj.end)return true;
        return false;
    }
    EdgeNode& operator=(const EdgeNode& obj) {
        this->begin = obj.begin;
        this->end = obj.end;
        return *this;
    }
    EdgeNode() {
        begin = 0;
        end = 0;
    }
    int get_begin() {
        return begin;
    }
    int get_end() {
        return end;
    }
    void set_begin(int b) {
        this->begin = b;
    }
    void set_end(int e) {
        this->end = e;
    }
};

cpp文件

Array.cpp

#include<iostream>
#include"EdgeNode.h"
#include<string>
#include<vector>
using namespace std;
template<class T>
class Arrary//边集数组类
{
private:
	vector<EdgeNode<T>> arr;//动态数组
public:
	~Arrary();
	void run();
	void CreateEdges();//添加边
	void Display();//打印
	void DeleteArc();//删除边
	void Destroy();//销毁
	bool IsConnected();//是否连通
	void ChangeDirecton();//改变连通方向
};
template<class T>
void Arrary<T>::CreateEdges()//添加边
{
	int hu = 0;
	cout << "请输入边的数量：";
	cin >> hu;
	if (hu <= 0)return;//如果数量小于0则输入错误
	//弧节点选择
	cout << "请输入由两个顶点构成的边" << hu << "条" << endl;
	while (hu)
	{	
		int one = 0, two = 0;
		while (1) {
			cout << "起点：";
			cin >> one;
			cout << "终点：";
			cin >> two;
			if (one > 0 && two > 0 && one != two)break;//起点和终点不能相同
			else {
				cout << "格式错误。重新输入" << endl;
			}
		}
		EdgeNode<T> a;//定义边的对象
		a.set_begin(one);
		a.set_end(two);
		//查重函数,重载==运算符
		if (find(arr.begin(), arr.end(), a) == arr.end()) {//find函数从头迭代，如果没有返回最后的对象
			arr.push_back(a);//如果不重复，则插入在数组最后
			hu--;
		}
		else {
			cout << "已经存在此弧了，请再次输入" << endl;
		}
		cout << "-----------------" << endl;
	}
	system("pause");
}
template<class T>
void Arrary<T>::Display()//遍历打印
{
	cout << "共有" << arr.size() << "条边" << endl;
	for (int i = 0; i < arr.size(); i++) {//外层循环表示边的数量
		EdgeNode<T> a1 = arr[i];//a1对象暂时指代arr[i]
		cout << a1.get_begin() << "->" << a1.get_end() << endl;
	}
	system("pause");
}
template<class T>
void Arrary<T>::DeleteArc()//删除边
{
	if (arr.size() == 0) {
		cout << "没有边" << endl;
		system("pause");
		return;
	}
	int sa, sb;
	cout << "请输入你要删除边的起点和终点" << endl;
	while (1) {
		cout << "起点：";
		cin >> sa;
		cout << "终点：";
		cin >> sb;
		if (sa > 0 && sb > 0 && sa != sb)break;//不能相同
		else {
			cout << "格式错误。重新输入" << endl;
		}
	}
	bool f = false;//用来判断是否被删除
	for (int i = 0; i < arr.size(); i++) {
		EdgeNode<T> aa = arr[i];
		if (aa.get_begin() == sa && aa.get_end() == sb) {
			//arr.begin() + i为指定被删除元素位置的迭代器
			arr.erase(arr.begin() + i);//删除元素，个数减1，capicity不变
			f = true;
			break;
		}
	}
	if (f) {
		cout << "删除成功" << endl;
	}
	else {
		cout << "未查到此数据" << endl;
	}
	system("pause");
}
template<class T>
void Arrary<T>::Destroy()//销毁
{
	int num = arr.size();//数据个数
	if (num <= 0) {
		cout << "未查找到边" << endl;
	}
	else {
		cout << "销毁" << num << "个数据" << endl;
		for (int i = 0; i < num; i++) {
			arr.pop_back();//删除最后一个元素，并且释放空间
		}
		arr.shrink_to_fit();//清除多于空间
		cout << "销毁完成" << endl;
	}
	system("pause");
}
template<class T>
bool Arrary<T>::IsConnected()//判断是否连通
{
	int sa, sb;
	cout << "请输入你要查找边的起点和终点" << endl;
	while (1) {
		cout << "起点：";
		cin >> sa;
		cout << "终点：";
		cin >> sb;
		if (sa > 0 && sb > 0 && sa != sb)break;
		else {
			cout << "格式错误。重新输入" << endl;
		}
	}
	bool f = false;
	for (int i = 0; i < arr.size(); i++) {
		EdgeNode<T> aa = arr[i];
		if (aa.get_begin() == sa && aa.get_end() == sb) {
			return true;
		}
	}
	return false;
}

template<class T>
void Arrary<T>::ChangeDirecton()//改变起点或终点
{
	if (arr.size() <= 0) {
		cout << "没有数据" << endl;
		system("pause");
		return;
	}
	int sa, sb;
	cout << "请输入要改变的边的起点和终点" << endl;
	while (1) {
		cout << "起点：";
		cin >> sa;
		cout << "终点：";
		cin >> sb;
		if (sa > 0 && sb > 0 && sa != sb)break;
		else {
			cout << "格式错误。重新输入" << endl;
		}
	}
	//找到位置
	int index = -1;
	for (int i = 0; i < arr.size(); i++) {
		EdgeNode<T> aa = arr[i];
		if (aa.get_begin() == sa && aa.get_end() == sb) {
			index = i;
			break;
		}
	}
	int ch = 0, one = 0, two = 0;
	cout << "选择1.更换起点2.更换终点\n选择：" << endl;
	cin >> ch;
	if (ch == 1) {
		EdgeNode<T> ac;//临时对象存放新数据
		while (1) {
			cout << "新起点：";
			cin >> one;
			
			ac.set_begin(one);
			ac.set_end(sb);	
			if (one != sa) {
				//查重函数,重载==运算符
				if (!(find(arr.begin(), arr.end(), ac) == arr.end())) {
					cout << "已经存在此弧了，请再次输入" << endl;
					continue;
				}
			}
			bool f = false;
			for (int i = 0; i < arr.size(); i++) {//检查是否存在one的值
					EdgeNode<T> abcd = arr[i];
					if (abcd.get_begin() == one) {
						f = true;
						break;
					}
			}
			if (f && one != sb)break;
			else {
				cout << "数据不存在或格式错误,退出。" << endl;
				system("pause");
				return;
			}
		}
		arr[index] = ac;//修改数值
		cout << "更改成功" << endl;
		system("pause");
	}
	if (ch == 2) {
		EdgeNode<T> aw;
		while (1) {
			cout << "新终点：";
			cin >> two;
			aw.set_begin(sa);
			aw.set_end(two);
			if (two != sb) {
				//查重函数,重载==运算符
				if (!(find(arr.begin(), arr.end(), aw) == arr.end())) {
					cout << "已经存在此弧了，请再次输入" << endl;
					continue;
				}
			}
			bool f = false;
			for (int i = 0; i < arr.size(); i++) {
				EdgeNode<T> abcd = arr[i];
				if (abcd.get_end() == two) {
					f = true; break;
				}
			}
			if (f && two != sa)break;
			else {
				cout << "数据不存在或格式错误,退出。" << endl;
				system("pause");
				return;
			}
		}
		arr[index] = aw;//修改数值
		cout << "更改成功" << endl;
		system("pause");
	}
}
void menu()
{
	cout << "**********" << endl;
	cout << "-1.添加边" << endl;
	cout << "-2.打印" << endl;
	cout << "-3.销毁" << endl;
	cout << "-4.删除边" << endl;
	cout << "-5.检查是否连通" << endl;
	cout << "-6.改变连接方向" << endl;
	cout << "-0.退出  请选择：";
}

template<class T>
Arrary<T>::~Arrary()
{
	int num = arr.size();
	for (int i = 0; i < num; i++) {
		arr.pop_back();//删除最后一个元素，并且释放空间
	}
	arr.shrink_to_fit();//清除多于空间
}

template<class T>
void Arrary<T>::run()
{
	while (1)
	{
		system("cls");
		menu();
		string f1 = "";
		cin >> f1;
		cout << endl;
		if (f1 == "1") {
			CreateEdges();
		}
		else if (f1 == "2") {
			Display();
		}
		else if (f1 == "3") {
			Destroy();
		}
		else if (f1 == "4") {
			DeleteArc();
		}
		else if (f1 == "5") {
			if (arr.size() == 0) {
				cout << "没有边" << endl;
			}
			else {
				bool f = IsConnected();
				if (f) {
					cout << "此边已经连通" << endl;
				}
				else {
					cout << "没连通" << endl;
				}
			}
			system("pause");
		}
		else if (f1 == "6") {
			ChangeDirecton();
		}
		else if (f1 == "0") {
			system("cls");
			cout << "\n\t\t期待您的再次使用！" << endl;
			break;
		}
	}
}
int main()
{
	Arrary<string> graph;
	graph.run();
	return 0;
}