模板的用法:
在函数或类前
template<class T>在函数体或类体中将需要的数据类型替换成T即可.在main()调用函数时,定义好实参的数据类型即可合法使用该函数.
模板的意义在于不必写若干函数的重载.
其中,模板声明中的"class"用"typename"更合适,'T'也可用任意字符代替
template<typename T>ALGraph.h文件
//邻接表 #include<vector> #include<queue>//STL enum GraphType {undigraph,digraph};//定义图类型:有向图和无向图边类和顶点类
//边类 struct EdgeNode { int adjvex; //将结点用1,2,3...表示位置 EdgeNode *nextnode; //指向下一个节点 /*可有一个数据成员表示权*/ }; //顶点类 struct VexNode { char data; //顶点的值 EdgeNode *firstedge; //指向对应边表的头指针 }; //注意顶点类有EdgeNode定义,所以两个结构体的顺序固定图类
//图类 class ALGrape { public: ALGrape(GraphType k,vector<char> vex, int v, int e);//图类型,储存各顶点值的数组,顶点数,边数 ~ALGrape(); void DFSTraverse(); //一般图 深度优先遍历 void BFSTraverse(); //一般图 广度优先遍历 private: int vexnum; //顶点数 int edgenum; //边数 vector <VexNode> vexlist ; //顶点表 GraphType kind; //图的类型 void DFS(int v, bool *visited); //连通图 深度优先遍历 };
构造函数算法思想:
每条边连接va,vb首尾顶点,将va的序号①链入vb为头节点的链表,再将vb的序号②链入va为头节点的链表.
顶点表中每一个元素都和一个序号对应,代码运行的也是这些序号,要访问时就vexlist[v].data即可
//构造函数 ALGrape::ALGrape(GraphType k , vector<char> vex, int v, int e)//vector定义形参时,不要加[] { EdgeNode *p; kind = k; vexnum = v; edgenum = e; vexlist.resize(vexnum); //意思是:将vexlist的元素个数调整为vexnum个. for (int i = 0; i < vexnum; ++i)//初始化顶点表 { vexlist[i].data = vex[i]; /*当vexlist数据类型 为模板时,显示vexlist无法用点运算符*/ vexlist[i].firstedge = NULL; } int va, vb;//一条边邻接的两个顶点的序号 for (int i = 0; i < edgenum; ++i) { if (kind == undigraph) { cout << "无向图第" << i + 1 << "条边的始顶点" << endl; cin >> va; cout << "无向图第" << i + 1 << "条边的尾顶点" << endl; cin >> vb; } else { cout << "有向图第" << i + 1 << "条边的始顶点" << endl; cin >> va; cout << "有向图第" << i + 1 << "条边的尾顶点" << endl; cin >> vb; } p = new EdgeNode; //头插法,一条边连接两个顶点,为va链上vb,也为vb链上va p->adjvex = vb; p->nextnode=vexlist[va].firstedge; vexlist[va].firstedge = p; p = new EdgeNode; p->adjvex = va; p->nextnode = vexlist[vb].firstedge; vexlist[vb].firstedge = p; } cout << "输入成功!" << endl; }
析构函数
//析构函数 ALGrape::~ALGrape() { EdgeNode *p; for (int j = 0; j < vexnum; j++) { p = vexlist[j].firstedge;//p指向头指针指向的首元结点 while (p) { vexlist[j].firstedge = p->nextnode;//头删法 delete p; p = vexlist[j].firstedge; } } cout << "析构函数运行成功" << endl; }
深度遍历函数:
DFS(v,visited)实现连通图遍历,DFSTraverse()实现一般图(等价于多个连通图)遍历,所以在main()中只调用,DFSTraverse()
//一般图 深度优先遍历 void ALGrape::DFSTraverse()//一个一般图==多个连通图 { bool *visited = new bool[vexnum];//不能使用 "bool visited[vexnum]; ",因为this指针无法用于常量表达式 for (int i = 0; i < vexnum; i++) { visited[i] = false; //初始化 } for (int i = 0; i < vexnum; i++) { if (!visited[i]) //若哪个结点还未访问,就用DFS(); { DFS(i,visited); } } delete[] visited; } //连通图 深度优先遍历 void ALGrape::DFS(int v,bool *visited)//*表示形参可修改 { cout << vexlist[v].data<<" "; visited[v] = true; //为了这一句,才有了bool *visited 这个形参 EdgeNode *p = vexlist[v].firstedge; //工作指针指向第一个边结点 while(p) { if (!visited[p->adjvex]) //若结点未被访问 { DFS(p->adjvex, visited); //递归,不满足条件时返回上一层递归 } p = p->nextnode; } }
广度遍历函数:
DFS()在访问完当前结点所有邻结点后,可以退回上一个结点接着操作.这种回退需要递归.
BFS()没有回退,不能使用递归.
广度遍历算法要保证 先被访问的结点的邻接点 先于 后被访问的结点的邻接点 被访问.
为了实现这种逐层按序访问,需要一个队列(特点:先进先出)存储每次访问的所有邻接点
//一般图 广度遍历 void ALGrape::BFSTraverse() { bool *visited = new bool[vexnum];//建立辅助数组,初始化 for (int i = 0; i < vexnum; i++) { visited[i] = false; } queue<int>q; //建立存储顺序的队列 for (int j = 0; j < vexnum; j++) //该层循环可应对多个联通分量的情况 { if (!visited[j]) { cout << vexlist[j].data<<" "; //输出第一个顶点值 visited[j] = true; q.push(j); while (!q.empty())//队列非空 { int w = q.front(); q.pop();//第一个元素赋给w并出队 for (EdgeNode *p = vexlist[w].firstedge; p; p = p->nextnode)//遍历该点的每一条边 { if (!visited[p->adjvex]) { cout << vexlist[p->adjvex].data<<" "; visited[p->adjvex] = true; q.push(p->adjvex); } } }//end while } } delete[] visited;//有new[] 必有delete[] }
main()函数
using namespace std; #include <iostream> #include"ALGraph.h" int main() { vector<char> a = {'a','b','c','d','e' }; int e1;//边数 g1:cout << "输入边数"<<endl; cin >> e1; if (e1 < 0) { system("cls"); cout << "输入的值非法!" << endl; goto g1; } else { ALGrape alg(undigraph, a, 5, e1); alg.DFSTraverse(); } vector<char> b = { 'a','b','c','d','e','f' }; int e2;//边数 g2:cout << "输入边数"<<endl; cin >> e2; if (e2 < 0) { system("cls"); cout << "输入的值非法!" << endl; goto g2; } else { ALGrape alg(undigraph, b, 6, e2); alg.BFSTraverse(); } system("pause"); return 0; }问题总结:
bug1:边类和结点类行文顺序写反了,系统编译错误
bug2:void ALGrape::DFSTraverse()中 不能使用 "bool visited[vexnum]; ",因为this指针无法用于常量表达式
解决方案是new一个bool数组:
bool *visited = new bool[vexnum];
然后就初始化
for (int i = 0; i < vexnum; i++) { visited[i] = false; }
