《山东建筑大学数据结构课程设计报告》由会员分享，可在线阅读，更多相关《山东建筑大学数据结构课程设计报告（31页珍藏版）》请在金锄头文库上搜索。
1、山东建筑大学计算机科学与技术学院山东建筑大学计算机科学与技术学院课程设计说明书课程设计说明书题 目： 基于逆邻接表的有向图基本操作的实现课 程：数据结构院 （部）：计算机学院专 业：计科班 级：133学生姓名：潘含笑学 号：20131111092指导教师：李盛恩完成日期：2015.07.03山东建筑大学计算机学院课程设计说明书目目 录录课程设计任务书I 课程设计任务书.II 逆邻接链表实现有向图3 一、问题描述3 二、数据结构3 三、逻辑设计3 四、编码5 五、测试数据.14 六、 测试情况16 逆邻接链表实现有向图.17 一、问题描述.17 二、数据结构.17 三、逻辑设计.17 四、编码.
2、19 五、测试数据.27 七、 测试情况29 结 论30 课程设计指导教师评语.32山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院山东建筑大学计算机科学与技术学院课程设计任务书课程设计任务书指导教师（签字）： 教研室主任（签字）设计题目基于逆邻接表的有向图基本操作的实现已知技术 参数和设 计要求题目三、实现类 NetWork，实现 BFS、DFS、拓扑排序，并实现采 用逆邻接表作为存储结构的有向图，要继承 NetWork。逆邻接表 要使用 STL 提供的 List 和 Vector 等实现。设计内 容与步 骤1、设计存储结构2、设计算法3、编写程序，进行调试4、总结并进行
3、演示、讲解设计工作计划与进度安排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、设
4、计算法7、编写程序，进行调试8、总结并进行演示、讲解设计工作计划与进度安排2015.4.222015.4.35，实现双向循环链表2015.4.252015.4.29，编写测试代码。设计考核要求4、考勤 20%5、课程设计说明书 50%6、成果展示 30%山东建筑大学计算机学院课程设计说明书2逆邻接链表实现有向图逆邻接链表实现有向图一、问题描述一、问题描述二、数据结构二、数据结构三、逻辑设计三、逻辑设计1、总体思路 先实现 Network 类，通过队列实现 BFS，通过堆栈实现 DFS 和拓扑排序。再 构建 Graph 类，并继承 Network 类实现以逆邻接链表为存储结构的有向图。2、模块划
5、分（以图示的方法给出各个函数的调用关系）21543612345611232345山东建筑大学计算机学院课程设计说明书33、函数或类的具体定义和功能 Network 类：Network 类Graph 类Begin虚函数Nextvertex虚函数Edges虚函数Vertices虚函数Initializepos虚函数Deactivatepos虚函数BFS函数DFS函数Topological函数Begin函数Nextvertex函数Edges函数Vertices函数Initializepos函数Deactivatepos函数Out 函数山东建筑大学计算机学院课程设计说明书4virtual int Be
6、gin(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 reac
7、h,int label,int a);/深度遍历 bool Topological(int v);/拓扑排序 virtual Network();/析构函数Graph 类： virtual Graph();/析构函数 int InDegree(int node);/入度 int OutDegree(int node);/出度 Graph/添加点 Graph/删除点 int Begin(int i);/确定起始顶点 int Nextvertex(int i);/下一个顶点 int Edges() return e;/确定点 int Vertices() return n;/确定边 void In
8、itializepos(int i)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;山东建筑大学计算机学院课程设计说明书5virtual int Nextvertex(int
9、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(
10、);/Network.cpp#include “Network.h“void Network:BFS(int v,int reach,int label,int a) int n=Vertices(); /获取 n 的值,有几个 顶点 queue Q; /创建一个队列 int k=0; /定义一个 k 来使元 素得到保存reachv=label;/标记点ak+=v;/用数组记录 BFS 的遍 历顺序Q.push(v); /把一个元素加入队列while(!Q.empty()int x;x=Q.front(); /获取队列中的第一个 元素Q.pop(); /让队列中的第一个元山东建筑大学计算机学院
11、课程设计说明书6素出队for(int i=1;i S; /创建一个堆栈 int n=Vertices(); /获取 n 的值 int k=0; S.push(v); /把元素 v 加入堆栈while(!S.empty()int x=S.top(); /获取堆栈的栈顶元素if(!reachx) /如果元素没被标记， 就把元素标记 reachx=label;ak+=x;S.pop(); /把堆栈的栈顶弹出for(int i=1;i a(n+1); stack S; /创建一个堆栈for(int i=1;i #include #include #include #include“Network.h“
12、 using namespace std; class Graph:public Networkpublic: Graph(int); virtual Graph(); int InDegree(int node); int OutDegree(int node);山东建筑大学计算机学院课程设计说明书11Graph Graphint Begin(int i);int Nextvertex(int i);int Edges() return e;int Vertices() return n;void Initializepos(int i)pos=ali.begin(); void Deact
13、ivatepos(int i)ali.erase(pos); void Out(); private: int n; int e; vector al; list: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 alnode.size(); int Graph:OutDegree(int node) 山东建筑大学计算机学院课程设计说明
14、书12list:iterator q; /开链表的迭代器 int i=0; for(int p=1;p n | node2 n) return *this; list:iterator p; p = find(alnode2.begin(), alnode2.end(), node1); /寻找有 没有 node1 if (p != alnode2.end() return *this; /如果有，返回 else alnode2.push_back(node1); e+; return *this; Graphlist:iterator p; p = find(alnode2.begin(), alnode2.end(), node1); if (p =alnode2.end() return *this; else alnode2.erase(p); /删除要删除的元素 e-; retu
