山东建筑大学计算机科学与技术学院课程设计说明书题目：基于逆邻接表的有向图基本操作的实现课程：数据结构院（部）：计算机学院专业：计科班级：133学生姓名：潘含笑学号：20131111092指导教师：李盛恩完成日期：2015.07.03山东建筑大学计算机学院课程设计说明书目 录课程设计任务书I课程设计任务书II逆邻接链表实现有向图3一、问题描述3二、数据结构3三、逻辑设计3四、编码5五、测试数据14六、 测试情况16逆邻接链表实现有向图17一、问题描述17二、数据结构17三、逻辑设计17四、编码18五、测试数据24七、 测试情况24结 论26课程设计指导教师评语28山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院课程设计任务书设计题目基于逆邻接表的有向图基本操作的实现题目三、实现类 NetWork，实现 BFS、DFS、拓扑排序，并实现采用已 知 技 术 逆邻接表作为存储结构的有向图，要继承 NetWork。逆邻接表要使参 数 和 设用 STL提供的 List和 Vector 等实现。计要求1、设计存储结构设 计 内2、设计算法容 与 步骤3、编写程序，进行调试4、总结并进行演示、讲解设计工作2015.6.172015.6.23 ，实现基类 Network 和有向图 Graph，实现逆邻接链表的存储结构。计划与进2015.6.232015.7.1，编写测试代码。度安排2015.7.12015.7.3，改正一些错误，完成实验。1、考勤 20%设计考核2、课程设计说明书50%要求3、成果展示 30%指导教师（签字）：教研室主任（签字）I山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院课程设计任务书设计题目双向循环链表已 知 技 术实现双向循环链表。参数和设计要求5、设计存储结构设 计 内6、设计算法容 与 步骤7、编写程序，进行调试8、总结并进行演示、讲解设 计 工 作，实现双向循环链表计 划 与 进，编写测试代码。度安排设计考核4、考勤 20%5、课程设计说明书50%要求6、成果展示 30%指导教师（签字）：教研室主任（签字）II山东建筑大学计算机学院课程设计说明书逆邻接链表实现有向图一、问题描述215436二、数据结构12314123526345三、逻辑设计1、总体思路先实现 Network 类，通过队列实现 BFS，通过堆栈实现 DFS和拓扑排序。再构建 Graph 类，并继承 Network 类实现以逆邻接链表为存储结构的有向图。2、模块划分（以图示的方法给出各个函数的调用关系）3山东建筑大学计算机学院课程设计说明书Network 类BeginNextvertexEdgesVerticesInitializeposDeactivateposBFSDFSTopological虚函数虚函数虚函数虚函数虚函数虚函数函数函数函数BeginNextvertexEdgesVerticesInitializeposDeactivateposOut 函数函数函数函数函数函数函数Graph 类3、函数或类的具体定义和功能Network 类：4山东建筑大学计算机学院课程设计说明书virtual int Begin(int i) = 0;/确定起始顶点virtual int Nextvertex(int i) = 0;/下一个顶点virtual int Edges()=0;/确定点virtual int Vertices()=0;/确定边virtual void Initializepos(inti)=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(inti)pos=ali.begin();/ 让迭代器等于链表的第i 个顶点的第一个元素void Deactivatepos(int i)ali.erase(pos);/删除迭代器指的元素void Out();/输出函数四、编码/Network.h#include #include#include#include using namespace std;class Network public:virtual int Begin(int i) = 0;5山东建筑大学计算机学院课程设计说明书virtual int Nextvertex(int i) = 0;virtual int Edges()=0;virtual int Vertices()=0;virtualvoid Initializepos(inti)=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.hvoid Network:BFS(int v,int reach,int label,int a)int n=Vertices();/获取 n 的值 , 有几个顶点queue Q;/创建一个队列intk=0;/定义一个 k 来使元素得到保存reachv=label;/ 标记点ak+=v;/ 用数组记录 BFS的遍历顺序Q.push(v);/把一个元素加入队列while(!Q.empty()int x;x=Q.front();/获取队列中的第一个元素Q.pop();/让队列中的第一个元6山东建筑大学计算机学院课程设计说明书素出队for(int i=1;i=n;i+)/寻找 x 的下一个节点int u=Begin(i);if(u=x)&(!reachi)/ 因为是逆邻接链表Q.push(i);reachi=label;ak+=i;/把标记的元素放入遍历数组while(u)/ 看后面是不是还有节点u=Nextvertex(i);if(u=x)&(!reachi)Q.push(i);re