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

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

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和jvertex_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--;//边数-1return 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--; // 顶点数减1ArcNode<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;//避免改动vernumif (sss + ding > MAXNUM) {cout << "StackOverflow！" << endl;return;}//无向图顶点与弧的最多个数是Cn2：n(n-1)/2if (!(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);//表头连接marc->set_ilink(vertex_arr[m]->get_firstedge());//表头插入法vertex_arr[m]->set_firstedge(arc);//表头连接narc->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设为0p = 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遍历，否则指向jlinkp = 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;
}