山东建筑大学计算机科学与技术学院课程设计说明书题目：基于逆邻接表的有向图基本操作的实现课程：数据结构院（部）：计算机学院专业：计科班级：133学生姓名：潘含笑学号：20131111092指导教师：李盛恩完成日期：2015.07.03目录课程设计任务书 (I)课程设计任务书 (II)逆邻接链表实现有向图 (3)一、问题描述 (3)二、数据结构 (3)三、逻辑设计 (3)四、编码 (5)五、测试数据 (14)六、测试情况 (16)逆邻接链表实现有向图 (17)一、问题描述 (17)二、数据结构 (17)三、逻辑设计 (17)四、编码 (18)五、测试数据 (24)七、测试情况 (24)结论 (26)课程设计指导教师评语 (28)山东建筑大学计算机科学与技术学院课程设计任务书指导教师（签字）：教研室主任（签字）山东建筑大学计算机科学与技术学院课程设计任务书指导教师（签字）：教研室主任（签字）逆邻接链表实现有向图二、数据结构三、逻辑设计1、总体思路先实现Network类，通过队列实现BFS，通过堆栈实现DFS和拓扑排序。

再构建Graph类，并继承Network类实现以逆邻接链表为存储结构的有向图。

2、模块划分（以图示的方法给出各个函数的调用关系）3、函数或类的具体定义和功能Network类：virtual int Begin(int i) = 0;//确定起始顶点virtual int Nextvertex(int i) = 0;//下一个顶点virtual int Edges()=0;//确定点virtual int Vertices()=0;//确定边virtual void Initializepos(int i)=0;//让迭代器等于链表的第i个顶点的第一个元素virtual void Deactivatepos(int i)=0;//删除迭代器指的元素void BFS(int v,int reach[],int label,int a[]);//宽度遍历void DFS(int v,int reach[],int label,int a[]);//深度遍历bool Topological(int v[]);//拓扑排序virtual ~Network();//析构函数Graph类：virtual ~Graph();//析构函数int InDegree(int node);//入度int OutDegree(int node);//出度Graph& Add(int node1, int node2);//添加点Graph& Delete(int node1, int node2);//删除点int Begin(int i);//确定起始顶点int Nextvertex(int i);//下一个顶点int Edges() {return e;}//确定点int Vertices() {return n;}//确定边void Initializepos(int i){pos=al[i].begin(); }////让迭代器等于链表的第i个顶点的第一个元素void Deactivatepos(int i){al[i].erase(pos);}//删除迭代器指的元素void Out();//输出函数四、编码//Network.h#include <iostream>#include<queue>#include<stack>#include <vector>using namespace std;class Network {public:virtual int Begin(int i) = 0;virtual int Nextvertex(int i) = 0;virtual int Edges()=0;virtual int Vertices()=0;virtual void Initializepos(int i)=0;//让迭代器等于链表的第i点的第一个元素virtual void Deactivatepos(int i)=0;//删除迭代器指的元素void BFS(int v,int reach[],int label,int a[]);//宽度遍历void DFS(int v,int reach[],int label,int a[]);//深度遍历bool Topological(int v[]);//拓扑排序virtual ~Network();};//Network.cpp#include "Network.h"void Network::BFS(int v,int reach[],int label,int a[]){int n=Vertices(); //获取n的值,有几个顶点queue<int> Q; //创建一个队列int k=0; //定义一个k来使元素得到保存reach[v]=label; //标记点a[k++]=v; //用数组记录BFS的遍历顺序Q.push(v); //把一个元素加入队列 while(!Q.empty()){int x;x=Q.front(); //获取队列中的第一个元素Q.pop(); //让队列中的第一个元素出队for(int i=1;i<=n;i++) //寻找x的下一个节点{int u=Begin(i);if((u==x)&&(!reach[i])) //因为是逆邻接链表{Q.push(i);reach[i]=label;a[k++]=i; //把标记的元素放入遍历数组}while(u) //看后面是不是还有节点 {u=Nextvertex(i);if((u==x)&&(!reach[i])){Q.push(i);reach[i]=label;a[k++]=i;}}}}for(int i=v;i<n;i++) //输出BFS的运行结果 {if(reach[i]==label)cout<<"执行完BFS后第"<<i<<"个元素被标记 "<<endl;elsecout<<"执行完BFS后第"<<i<<"个元素没有被标记 "<<endl;}cout<<"从节点"<<v<<"开始BFS遍历的顺序是";for(int i=1;i<n;i++) //输出BFS的遍历顺序 {cout<<a[i-1]<<" ";};cout<<endl;}void Network::DFS(int v,int reach[],int label,int a[]){stack<int> S; ///创建一个堆栈int n=Vertices(); //获取n的值int k=0;S.push(v); //把元素v加入堆栈 while(!S.empty()){int x=S.top(); //获取堆栈的栈顶元素if(!reach[x]) //如果元素没被标记，就把元素标记{ reach[x]=label;a[k++]=x;S.pop(); //把堆栈的栈顶弹出 for(int i=1;i<=n;i++) //获取节点的下一个元素{int u=Begin(i);if((u==x)&&(!reach[i])){S.push(i); //把元素加入堆栈}while(u){u=Nextvertex(i);if((u==x)&&(!reach[i])){S.push(i);}}}}elseS.pop(); //如果被标记元素就弹出}for(int i=v;i<n;i++) //输出DFS的运行结果 {if(reach[i]==label)cout<<"执行完DFS后第"<<i<<"个元素被标记 "<<endl;elsecout<<"执行完DFS后第"<<i<<"个元素没有被标记"<<endl;}cout<<"从节点1开始DFS遍历的顺序是";for(int i=1;i<n;i++) //输出DFS的遍历顺序{cout<<a[i-1]<<ends;};cout<<endl;}bool Network::Topological(int v[]){int n=Vertices(); //获取n的值vector<int> a(n+1);stack<int> S; //创建一个堆栈for(int i=1;i<=n ;i++) //初始化数组a，使每个点的a等于0，用来记录点的入度a[i]=0;for(int i=1;i<=n;i++) //遍历整个邻接链表，有入度的节点增加a的值{int x=Begin(i);while(x){a[i]++;x=Nextvertex(i); //后面有元素，则入度加1}}for( int i=1;i<=n;i++) //如果a=0，把元素加入堆栈if(a[i]==0) S.push(i);int k=1;while(!S.empty()){int y;y=S.top(); //拿出第一个元素S.pop();v[k++]=y; //弹出获取值的元素for(int i=1;i<=n;i++) //遍历整个邻接链表，使有y的元素的入度减一{int u=Begin(i);if(u==y&&a[i]!=0){a[i]--;if(a[i]==0) S.push(i); //如果有入度等于0的元素，把元素加入堆栈}while(u){u=Nextvertex(i);if(u==y&&a[i]!=0){a[i]--;if(a[i]==0) S.push(i);}}}}if(k==n+1)return true;elsereturn false;}Network::~Network() {}//Graph.h#include <iostream>#include <vector>#include <list>#include <algorithm>#include"Network.h"using namespace std;class Graph:public Network{public:Graph(int);virtual ~Graph();int InDegree(int node);int OutDegree(int node);Graph& Add(int node1, int node2);Graph& Delete(int node1, int node2);int Begin(int i);int Nextvertex(int i);int Edges() {return e;}int Vertices() {return n;}void Initializepos(int i){pos=al[i].begin(); }void Deactivatepos(int i){al[i].erase(pos);}void Out();private:int n;int e;vector<list<int> > al;list<int>::iterator pos;};//Graph.cpp#include "Graph.h"Graph::Graph(int num) {e=0; //初始化边，顶点n=num;al.resize(n+1); //开空间}Graph::~Graph() {}int Graph::InDegree(int node){return al[node].size();}int Graph::OutDegree(int node){list<int>::iterator q; //开链表的迭代器int i=0;for(int p=1;p<=n;p++){q=find(al[p].begin(),al[p].end(),node);if(q!=al[p].end()) i++;}return i;}Graph& Graph::Add(int node1, int node2){if(node1 < 1 || node1 > n || node2 < 1 || node2 > n) return *this;list<int>::iterator p;p = find(al[node2].begin(), al[node2].end(), node1); //寻找有没有node1if (p != al[node2].end()) return *this; //如果有，返回else{al[node2].push_back(node1);e++;}return *this;}Graph& Graph::Delete(int node1, int node2){if(node1 < 1 || node1 > n || node2 < 1 || node2 > n) return *this;list<int>::iterator p;p = find(al[node2].begin(), al[node2].end(), node1);if (p ==al[node2].end()) return *this;else{al[node2].erase(p); //删除要删除的元素e--;}return *this;}void Graph::Out(){for(int i = 1; i <=n; i++){list<int>::iterator p;cout<<"逆邻接链表中第"<<i<<"行元素有";for(p = al[i].begin(); p != al[i].end(); p++) cout << *p << ' ';cout <<endl;}return;}int Graph::Begin(int i){if(i<1||i>n) cout<<"无该点";Initializepos(i);if(pos==al[i].end())return 0;elsereturn *pos;}int Graph::Nextvertex(int i){if(i<1||i>n) cout<<"无该点";pos++;if(pos!=al[i].end())return *pos;elsereturn 0;}五、测试数据#include"Graph.h"#include"Network.h"int b[20];int b1[20];int c[20];int a[20];int a1[20];int main(void){int n=6;int label=2;Graph g(n); //创建对象g.Add(1,4).Add(1,3).Add(2,4).Add(2,5).Add(3,4).Add(3,6).Add(4,6).Add(5,6);g.Out();g.BFS(1,b,label,b1);cout<<endl;g.DFS(1,a,label,a1);for(int i=1;i<=n;i++){cout<<"节点"<<i<<"的入度为：";cout<<g.InDegree(i)<<",";cout<<"节点"<<i<<"的出度为：";cout<<g.OutDegree(i)<<endl;}g.Topological(c); //执行拓扑排序for(int i=1;i<=n;i++)cout<<"拓扑排序的第"<<i<<"个元素是 "<<c[i]<<endl;cout<<endl;g.Delete(4,6);g.Out();}六、测试情况双向循环链表一、问题描述实现双向循环链表。