山东建筑大学数据结构课程设计报告.doc

山东建筑大学题 目：课 程： 院 （部）： 专 业： 班 级： 学生姓名： 学 号： 指导教师： 完成日期：目 录 课程设计任务书 I 课程设计任务书 II 逆邻接链表实现有向图 3 一、问题描述 3 二、数据结构 3 三、逻辑设计 3 四、编码 5 五、测试数据 14 六、 测试情况 16 逆邻接链表实现有向图 17 一、问题描述 17 二、数据结构 17 三、逻辑设计 17 四、编码 19 五、测试数据 27 七、 测试情况 29 结 论 30 课程设计指导教师评语 32 山东建筑大学计算机科学与技术学院 课程设计任务书 设计题目 基于逆邻接表的有向图基本操作的实现 已知技术参数和设计要求 题目三、实现类NetWork，实现BFS、DFS、拓扑排序，并实现采用逆邻接表作为存储结构的有向图，要继承NetWork。逆邻接表要使用STL提供的List和Vector等实现。 设计内容与步骤 设计存储结构 设计算法 编写程序，进行调试 总结并进行演示、讲解 设计工作计划与进度安排 2015.6.17~2015.6.23，实现基类Network和有向图Graph，实现逆邻接链表的存储结构。 2015.6.23~2015.7.1，编写测试代码。 2015.7.1~2015.7.3，改正一些错误，完成实验。 设计考核要求 考勤20% 课程设计说明书50% 成果展示30% 指导教师（签字）： 教研室主任（签字）  山东建筑大学计算机科学与技术学院 课程设计任务书 设计题目 双向循环链表 已知技术参数和设计要求 实现双向循环链表。 设计内容与步骤 设计存储结构 设计算法 编写程序，进行调试 总结并进行演示、讲解 设计工作计划与进度安排 2015.4.22~2015.4.35，实现双向循环链表 2015.4.25~2015.4.29，编写测试代码。 设计考核要求 考勤20% 课程设计说明书50% 成果展示30% 指导教师（签字）： 教研室主任（签字）逆邻接链表实现有向图 一、问题描述 二、数据结构 三、逻辑设计 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 iostr