问题描述 :
目的：使用C++模板设计并逐步完善图的邻接表抽象数据类型（ADT）。
内容：（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接表ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）
（2）设计并实现一个算法，在已存在的图中查找指定元素值的结点，如查找成功，则删除之（包括与之相关的边）；否则，返回。图的存储结构采用邻接表。将其加入到ADT中。
注意：DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）
参考函数原型：
//往G中删除一个顶点
template<class TypeOfVer, class TypeOfEdge>
bool adjlist_graph<TypeOfVer, TypeOfEdge>::DeleteVer(const int u);
图的邻接表模板类原型参考如下：
/* 边表的结点定义 */
template<class TypeOfEdge>
struct edgeNode
{
int data;
TypeOfEdge weight;
edgeNode<TypeOfEdge> *next;
edgeNode(const int &d, edgeNode<TypeOfEdge> *ptr = NULL) //构造函数，用于构造其他结点（无权图）
//函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
{
next = ptr;
data = d;
}
edgeNode(const int &d, const TypeOfEdge &w, edgeNode<TypeOfEdge> *ptr = NULL) //构造函数，用于构造其他结点（带权图）
//函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
{
next = ptr;
data = d;
weight = w;
}
int getData(){ return data;} //取得结点的序号（顶点集）
TypeOfEdge getWeight(){ return weight;} //取得边集中对应边的权值
void SetLink( edgeNode<TypeOfEdge> *link ){ next = link; } //修改结点的next域
void SetData( int value ){ data = value; } //修改结点的序号（顶点集）
void SetWeight(TypeOfEdge value ){ weight = value; } //修改边集中对应边的权值
};
//图的邻接表类
template<class TypeOfVer, class TypeOfEdge>
struct verNode
{
TypeOfVer ver;
edgeNode<TypeOfEdge> *head;
verNode(edgeNode<TypeOfEdge> *h = NULL){head = h;}
TypeOfVer getVer(){ return ver;} //取得结点值（顶点集）
edgeNode<TypeOfEdge> *getHead(){ return head;} //取得对应的边表的头指针
void setVer(TypeOfVer value){ ver = value;} //设置结点值（顶点集）
void setHead(edgeNode<TypeOfEdge> *value){ head = value;} //设置对应的边表的头指针
};
template <class TypeOfVer, class TypeOfEdge>
class adjlist_graph{
private:
int Vers; //顶点数
int Edges; //边数
verNode<TypeOfVer,TypeOfEdge> *verList;
string GraphKind; //图的种类标志
bool Delete_Edge( int u, int v );
bool DFS(int u, int &num, int visited[]); //DFS遍历（递归部分）
public:
adjlist_graph( const string &kd, int vSize, const TypeOfVer d[]); //构造函数构造一个只有结点没有边的图。
adjlist_graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e); 构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集
adjlist_graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e, const TypeOfEdge w[]); //构造函数构造一个有权图。
bool GraphisEmpty() { return Vers == 0; } //判断图空否
string GetGraphKind(){ return GraphKind; }
bool GetVer(int u, TypeOfVer &data); //取得G中指定顶点的值
int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
int GetNextAdjVex(int u, int v, int &w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回false
bool PutVer(int u, TypeOfVer data); //对G中指定顶点赋值
bool InsertVer(const TypeOfVer &data); //往G中添加一个顶点
int LocateVer(TypeOfVer data); //返回G中指定顶点的位置
bool ExistEdge(int u, int v);
bool PrintVer(); //输出顶点集
bool PrintAdjList(); //输出邻接矩阵
int GetVerNum(){ return Vers;} //取得当前顶点数
int GetEdgeNum(){ return Edges;} //取得当前边数
bool Insert_Edge(int u, int v); //无权图插入一条边
bool Insert_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边
bool DeleteVer(const int u); //往G中删除一个顶点
bool DeleteEdge( int u, int v ); //删除边 (外壳：有向（删除1条边）， 无向（删除2条边））
void DFS_Traverse(int u); //DFS遍历（外壳部分）
void BFS_Traverse(int u); //BFS遍历
~adjlist_graph(); //析构函数
};
输入说明 :
建图的输入数据格式参见建图的算法说明。
第一行：图的类型
第二行：结点数
第三行：结点集
第四行：边数
第五行：边集
第六行：待删除的顶点的位序
输出说明 :
第一行：图的类型
第三行：删除前的顶点数
第四行：删除前的边数
第五行：删除前的邻接表
空行
第六行：删除后的顶点集
第七行：删除后的顶点数
第八行：删除后的边数
第九行：删除后的邻接表
输入范例 :
DG
6
A B C D E F
8
0 1
0 2
0 3
1 4
2 4
3 5
4 1
5 1
1
输出范例 :
DG
A B C D E F
6
8
A->3->2->1
B->4
C->4
D->5
E->1
F->1A C D E F
5
4
A->2->1
C->3
D->4
E
F
解题代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <stack>
#include <map>
#include <ctime>
#include <array>
#include <set>
#include <list>
using namespace std;
//边的定义
template<class TypeOfEdge>
struct Edge_pair
{
int point=0;
TypeOfEdge length=0;
//=================
};
//顶点的定义
template<class TypeOfVer, class TypeOfEdge>
struct verNode
{
TypeOfVer ver_data;
list<Edge_pair<TypeOfEdge> > group;
//构造函数，默认会讲头指针设为空.
verNode()
{
group.clear();
ver_data = 0;
}
//取得结点值（顶点） 估计是为了安全吧？？？
TypeOfVer getVer()
{
return ver_data;
}
//取得对应的边表
list<Edge_pair<TypeOfEdge> > getHead()
{
return group;
}
//设置结点值（顶点集） 估计是为了安全吧？？？
void setdata(TypeOfVer value)
{
ver_data = value;
return;
}
//=====================================================
void creat_Point(int new_point,TypeOfEdge new_length)
{
Edge_pair<TypeOfEdge> Next_p;
Next_p.point = new_point;
Next_p.length = new_length;
group.insert(group.begin(),Next_p);
return;
}
//删除指定位置顶点
void del_Point(int n)
{
return;
}
};
template <class TypeOfVer, class TypeOfEdge>//顶点元素类型，边权值类型
class adjlist_graph {
private:
int Vers;//顶点数
int Edges;//边数
vector<verNode<TypeOfVer, TypeOfEdge> >ver;//顶点存储
string GraphKind;//图的种类标志
bool have_dir = false, have_w = false;//图类型参数
//======================================================================
bool Delete_Edge(int u, int v)//删除一条边
{
return false;
}
bool DFS(int u, int& num, int visited[])//DFS遍历（递归部分）
{
return false;
}
public:
//一个空的构造函数
adjlist_graph()
{
Edges = 0;
Vers = 0;
}
//假的析构函数
~adjlist_graph()
{
;//你电脑内存就640K吗？
}
//判断图空否
bool GraphisEmpty()
{
return Vers == 0;
}
//获取图的类型
string GetGraphKind()
{
return GraphKind;
}
//取得当前顶点数
int GetVerNum()
{
return Vers;
}
//取得当前边数
int GetEdgeNum()
{
return Edges;
}
//自动建立临接表
bool Auto_build(void)
{
//DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）
/*第一行：图的类型 DN UDN
第二行：结点数
第三行：结点集
第四行：无边标记
第五行：边数
第六行：边集
第七行：权集*/
/*第一行：图的类型 DG UDG
第二行：结点数
第三行：结点集
第四行：边数
第五行：边集*/
cin >> GraphKind;//图的类型
cin >> Vers;//结点数
ver.resize(Vers);//开辟节点空间
for (int i = 0; i < Vers; i++)//结点集
{
TypeOfVer now;
cin >> now;
ver[i].setdata(now);
}
cin >> Edges;//边数
vector<int> x_p, y_p, w_p;
for (int i = 0; i < Edges; i++)
{
int c_x, c_y;
cin >> c_x >> c_y;
x_p.push_back(c_x);
y_p.push_back(c_y);
}
//图的类型识别
if (GraphKind == "DG")//DG（有向图）
have_dir = true, have_w = false;
if (GraphKind == "DN")//DN（有向网）
have_dir = true, have_w = true;
if (GraphKind == "UDG")//UDG（无向图）
have_dir = false, have_w = false;
if (GraphKind == "UDN")//UDN（无向网）
have_dir = false, have_w = true;
if (have_w)
for (int i = 0; i < Edges; i++)
{
int c_w;
cin >> c_w;
w_p.push_back(c_w);
}
for (int i = 0; i < Edges; i++)
{
if (have_dir)
if (have_w)
ver[x_p[i]].creat_Point(y_p[i], w_p[i]);
else
ver[x_p[i]].creat_Point(y_p[i], 0);
else
if (have_w)
ver[x_p[i]].creat_Point(y_p[i], w_p[i]), ver[y_p[i]].creat_Point(x_p[i], w_p[i]);
else
ver[x_p[i]].creat_Point(y_p[i], 0), ver[y_p[i]].creat_Point(x_p[i], 0);
}
return 1;
}
//取得G顶点的组
vector<TypeOfVer> GetVer(void)
{
vector<TypeOfVer> head_group;
for (int i = 0; i < Vers; i++)
{
head_group.push_back(ver[i].getVer());
}
return head_group;
}
//输出邻接表
bool Print_photo()
{
int i;
for (i = 0; i < Vers; i++)
{
cout << ver[i].getVer();
if (ver[i].group.size() != 0)
cout << "->";
else
{
cout << endl;
continue;
}
vector<Edge_pair<TypeOfEdge> > out_lis;
out_lis.clear();
for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
{
out_lis.push_back(*j);
}
int j;
for (j = 0; j < out_lis.size() - 1; j++)
if (have_w)
cout << out_lis[j].point << "(" << out_lis[j].length << ")" << "->";
else
cout << out_lis[j].point << "->";
if (have_w)
cout << out_lis[j].point << "(" << out_lis[j].length << ")" << endl;
else
cout << out_lis[j].point << endl;
}
return 1;
}
//往G中添加一个顶点
bool InsertVer(const TypeOfVer& data)
{
verNode<TypeOfVer, TypeOfEdge> new_e;
new_e.setdata(data);
ver.push_back(new_e);
Vers++;
return true;
}
//寻找顶点位置
int Look_Ver(const TypeOfVer& data)
{
int i;
for (i = 0; i < Vers; i++)
if (ver[i].ver_data == data)
return i;
return -1;
}
//删除一个顶点
bool del_Point(int place)
{
int need_del=0;
if (!(0 <= place && place < Vers))
return false;
int i;
for (i = 0; i < Vers; i++)
{
for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
{
if (j->point == place)
{
need_del++;
ver[i].group.erase(j);
break;
}
}
for (auto j = ver[i].group.begin(); j != ver[i].group.end(); j++)
{
if (j->point > place)
j->point--;
}
}
need_del += ver[place].group.size();
ver.erase(ver.begin() + place);
Vers--;
if (have_dir)
Edges -= need_del;
else
Edges -= (need_del / 2);
return true;
}
/*+++++++++++====分割线====++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
//返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
int GetFirstAdjVex(int u, int& v)
{
return 0;
}
//返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回false
int GetNextAdjVex(int u, int v, int& w)
{
return 0;
}
//对G中指定顶点赋值
bool PutVer(int u, TypeOfVer data)
{
return false;
}
//返回G中指定顶点的位置
int LocateVer(TypeOfVer data)
{
return -1;
}
//存在边
bool ExistEdge(int u, int v)
{
return 0;
}
//输出邻接矩阵
bool PrintAdjList()
{
return 1;
}
//无权图插入一条边
bool Insert_Edge(int u, int v)
{
return false;
}
//有权图插入一条边
bool Insert_Edge(int u, int v, TypeOfEdge w)
{
return false;
}
//往G中删除一个顶点
bool DeleteVer(const TypeOfVer& data)
{
return false;
}
//删除边 (外壳：有向（删除1条边）， 无向（删除2条边））
bool DeleteEdge(int u, int v)
{
return false;
}
//DFS遍历（外壳部分）
void DFS_Traverse(int u)
{
return;
}
//BFS遍历
void BFS_Traverse(int u)
{
return;
}
};
int main()
{
int i;
adjlist_graph<char, int> a;
a.Auto_build();
int del_p;
cin >> del_p;
cout << a.GetGraphKind() << endl;
vector <char> ans;
ans = a.GetVer();
for (i = 0; i < ans.size() - 1; i++)
cout << ans[i] << " ";
cout << ans[i] << endl;
cout << a.GetVerNum() << endl;
cout << a.GetEdgeNum() << endl;
a.Print_photo();
cout << endl;
a.del_Point(del_p);
ans = a.GetVer();
for (i = 0; i < ans.size() - 1; i++)
cout << ans[i] << " ";
cout << ans[i] << endl;
cout << a.GetVerNum() << endl;
cout << a.GetEdgeNum() << endl;
a.Print_photo();
return 0;
}