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

1、山东建筑大学计算机科学与技术学院课程设计说明书题目：基于逆邻接表的有向图基本操作的实现课程：数据结构院（部）：计算机学院专业：计科班级：133学生姓名：潘含笑学号：20131111092指导教师：李盛恩完成日期：2015.07.03山东建筑大学计算机学院课程设计说明书目 录课程设计任务书I课程设计任务书II逆邻接链表实现有向图3一、问题描述3二、数据结构3三、逻辑设计3四、编码5五、测试数据14六、 测试情况16逆邻接链表实现有向图17一、问题描述17二、数据结构17三、逻辑设计17四、编码18五、测试数据24七、 测试情况24结 论26课程设计指导教师评语28山东建筑大学计算机学院课程设计说

2、明书山东建筑大学计算机科学与技术学院课程设计任务书设计题目基于逆邻接表的有向图基本操作的实现题目三、实现类 NetWork，实现 BFS、DFS、拓扑排序，并实现采用已 知 技 术 逆邻接表作为存储结构的有向图，要继承 NetWork。逆邻接表要使参 数 和 设用 STL提供的 List和 Vector 等实现。计要求1、设计存储结构设 计 内2、设计算法容 与 步骤3、编写程序，进行调试4、总结并进行演示、讲解设计工作2015.6.172015.6.23 ，实现基类 Network 和有向图 Graph，实现逆邻接链表的存储结构。计划与进2015.6.232015.7.1，编写测试代码。度安

3、排2015.7.12015.7.3，改正一些错误，完成实验。1、考勤 20%设计考核2、课程设计说明书50%要求3、成果展示 30%指导教师（签字）：教研室主任（签字）I山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院课程设计任务书设计题目双向循环链表已 知 技 术实现双向循环链表。参数和设计要求5、设计存储结构设 计 内6、设计算法容 与 步骤7、编写程序，进行调试8、总结并进行演示、讲解设 计 工 作 2015.4.222015.4.35 ，实现双向循环链表计 划 与 进 2015.4.252015.4.29 ，编写测试代码。度安排设计考核4、考勤 20%5、课程设计说

4、明书50%要求6、成果展示 30%指导教师（签字）：教研室主任（签字）II山东建筑大学计算机学院课程设计说明书逆邻接链表实现有向图一、问题描述215436二、数据结构12314123526345三、逻辑设计1、总体思路先实现 Network 类，通过队列实现 BFS，通过堆栈实现 DFS和拓扑排序。再构建 Graph 类，并继承 Network 类实现以逆邻接链表为存储结构的有向图。2、模块划分（以图示的方法给出各个函数的调用关系）3山东建筑大学计算机学院课程设计说明书Network 类BeginNextvertexEdgesVerticesInitializeposDeactivatepos

5、BFSDFSTopological虚函数虚函数虚函数虚函数虚函数虚函数函数函数函数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;/确定边virtua

6、l 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);/入度i

7、nt 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(in

8、t i)ali.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;5山东建筑大学计算机学院课程设计说明书virtual int Nextvertex(int i) = 0;virtual int Edges()=0;virtua

9、l 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.h&quo

10、t;void Network:BFS(int v,int reach,int label,int a)int n=Vertices();/获取 n 的值 , 有几个顶点queue<int> 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

11、+)/寻找 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);reachi=label;ak+=i;for(int i=v;i<n;i+)/输出 BFS的运行结果if(reachi=label)cout<<"执行完 BFS后第 "<<i<<&

12、quot; 个元素被标记 "<<endl;elsecout<<"执行完 BFS后第 "<<i<<" 个元素没有被标记"<<endl;cout<<"从节点 "<<v<<" 开始 BFS遍历的顺序是 "for(int i=1;i<n;i+)/输出 BFS的遍历顺序7山东建筑大学计算机学院课程设计说明书cout<<ai-1<<" "cout<<endl;v

13、oid 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(!reachx)/如果元素没被标记，就把元素标记reachx=label;ak+=x;S.pop();/把堆栈的栈顶弹出for(inti=1;i<=n;i+)/获取节点的下一个元素int u=Begin(i);if(u=x)&&(!re

14、achi)S.push(i);/把元素加入堆栈while(u)u=Nextvertex(i);if(u=x)&&(!reachi)S.push(i);8山东建筑大学计算机学院课程设计说明书elseS.pop();/如果被标记元素就弹出for(int i=v;i<n;i+)/输出 DFS的运行结果if(reachi=label)cout<<"执行完 DFS后第 "<<i<<" 个元素被标记 "<<endl;elsecout<<"执行完 DFS后第 "<

15、;<i<<" 个元素没有被标记"<<endl;cout<<"从节点 1 开始 DFS遍历的顺序是 "for(inti=1;i<n;i+)/输出 DFS的遍历顺序cout<<ai-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+

16、)/初始化数组 a，使每个点的 a 等于 0，用来记录点的入度ai=0;for(int i=1;i<=n;i+)/遍历整个邻接链表，有入度的节点增加a 的值9山东建筑大学计算机学院课程设计说明书int x=Begin(i);while(x)ai+;x=Nextvertex(i);/ 后面有元素，则入度加1for( int i=1;i<=n;i+)/如果 a=0，把元素加入堆栈if(ai=0) S.push(i);int k=1;while(!S.empty()int y;y=S.top();/拿出第一个元素S.pop();vk+=y;/弹出获取值的元素for(int i=1;i&l

17、t;=n;i+)/遍历整个邻接链表，使有 y 的元素的入度减一int u=Begin(i);if(u=y&&ai!=0)ai-;if(ai=0) S.push(i);/如果有入度等于 0 的元素，把元素加入堆栈while(u)u=Nextvertex(i);if(u=y&&ai!=0)ai-;10山东建筑大学计算机学院课程设计说明书if(ai=0) S.push(i);if(k=n+1)return true;elsereturn false;Network:Network() /Graph.h#include <iostream>#include

18、<vector>#include <list>#include <algorithm>#include"Network.h"using namespace std;class Graph:public Networkpublic:Graph(int);virtual Graph();int InDegree(int node);int OutDegree(int node);11山东建筑大学计算机学院课程设计说明书Graph& Add(int node1, int node2);Graph& Delete(int node

19、1, int node2);int Begin(int i);int Nextvertex(int i);int Edges() return e;int Vertices() return n;void Initializepos(int i)pos=ali.begin(); void Deactivatepos(int i)ali.erase(pos);void Out();private:int n;int e;vector<list<int> > al;list<int>:iterator pos;/Graph.cpp#include "G

20、raph.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)12山东建筑大学计算机学院课程设计说明书list<int>:iterator q;/开链表的迭代器int i=0;for(int p=1;p<=n;p+)q=find(alp.begin(),alp.end(),node);if(q!=alp.end() i

21、+;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(alnode2.begin(), alnode2.end(), node1);/寻找有没有 node1if (p != alnode2.end() return *this;/如果有，返回elsealnode2.push_back(node1);e+;return *th

22、is;Graph& Graph:Delete(int node1, int node2)if(node1 < 1 | node1 > n | node2 < 1 | node2 > n) return *this;list<int>:iterator p;p = find(alnode2.begin(), alnode2.end(), node1);if (p =alnode2.end() return *this;elsealnode2.erase(p);/删除要删除的元素e-;return *this;void Graph:Out()for(in

23、t i = 1; i <=n; i+)list<int>:iterator p;cout<<" 逆邻接链表中第 "<<i<<" 行元素有 "13山东建筑大学计算机学院课程设计说明书for(p = ali.begin(); p != ali.end(); p+) cout << *p << ' ' cout <<endl;return;int Graph:Begin(int i)if(i<1|i>n) cout<<"无

24、该点 "Initializepos(i);if(pos=ali.end()return 0;elsereturn *pos;int Graph:Nextvertex(int i)if(i<1|i>n) cout<<"无该点 "pos+;if(pos!=ali.end()return *pos;elsereturn 0;五、测试数据#include"Graph.h"#include"Network.h"int b20;int b120;14山东建筑大学计算机学院课程设计说明书int c20;int a2

25、0;int a120;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

26、.InDegree(i)<<","cout<<"节点 "<<i<<" 的出度为： "cout<<g.OutDegree(i)<<endl;g.Topological(c);/ 执行拓扑排序for(int i=1;i<=n;i+)cout<<"拓扑排序的第 "<<i<<" 个元素是 "<<ci<<endl;cout<<endl;g.Delete(4,

27、6);g.Out();15山东建筑大学计算机学院课程设计说明书六、测试情况16山东建筑大学计算机学院课程设计说明书双向循环链表一、问题描述实现双向循环链表。二、数据结构a1a2a3a3三、逻辑设计1、总体思路先构造双向循环链表的节点类，再逐步实现双向循环链表的基本函数。2、模块划分（以图示的方法给出各个函数的调用关系）DoubleCircularNode节点类DoubleCircular类DoubleCiDoubleCircDoubleCircDoubleCircuDoubleCircuDoubleCirDoubleCrcular 类ular 类ular 类lar 类lar 类cular 类i

28、rcular类17山东建筑大学计算机学院课程设计说明书3、函数或类的具体定义和功能template<class T>class DoubleCircularpublic:DoubleCircular();/构造函数DoubleCircular();/析构函数bool IsEmpty() const;/判断是否为空int length() const;/计算长度bool Find(int k,T& x) const;/判断节点是否存在int Search(const T& x) const;/查找节点DoubleCircular<T>& Inser

29、t(int k,const T& x);/插入节点DoubleCircular<T>& Delete(int k, T& x);/删除节点void Output(ostream & out) const;/输出函数private:DoubleCircularNode<T> *first;四、编码/DoubleCircular.htemplate<class T>class DoubleCircularNode;#include<iostream>using namespace std;template<cla

30、ss T>class DoubleCircularpublic:DoubleCircular();DoubleCircular();bool IsEmpty() const;int length() const;bool Find(int k,T& x) const;int Search(const T& x) const;DoubleCircular<T>& Insert(int k,const T& x);DoubleCircular<T>& Delete(int k, T& x);void Output(ost

31、ream & out) const;18山东建筑大学计算机学院课程设计说明书private:DoubleCircularNode<T> *first;template<class T>class DoubleCircularNode friend class DoubleCircular<T>private:T data;DoubleCircularNode<T> *left, *right;template<class T>class DoubleCircularIteratorpublic:T *Intialize(con

32、st DoubleCircular<T>& c)location = c.first->right;if(location)return &location->data;return 0;T *Next(const DoubleCircular<T>& c)if(!location) return 0;location =location->right;if (location->right!=c.first->right)return &location->data;return 0;private:

33、DoubleCircularNode<T> *location;19山东建筑大学计算机学院课程设计说明书class OutOfBounds public:OutOfBounds();virtual OutOfBounds();/DoubleCircular.cpp#include"DoubleCircular.h"#include<iostream>using namespace std;template <class T>DoubleCircular<T>:DoubleCircular()first = new Double

34、CircularNode<T>first->left = first;first->right = first;first=0;template <class T>DoubleCircular<T>:DoubleCircular()DoubleCircularNode<T> *next = first;/first->left->right = NULL;while(first)next = first->right;delete first;first = next;template <class T>

35、bool DoubleCircular<T>:IsEmpty() constif(first->right = first)return 1;20山东建筑大学计算机学院课程设计说明书return 0;template <class T>int DoubleCircular<T>:length() constint len = 0;DoubleCircularNode<T> *current = first->right;while(current != first)len+;current = current->right;re

36、turn len;template <class T>DoubleCircular<T>& DoubleCircular<T>:Insert(int k, const T& x)int max=length();if(k < 0|k > max) throw OutOfBounds();DoubleCircularNode<T> *p = first;for(int index = 1; index < k && p; index+)p = p->right;if(!p) throw Out

37、OfBounds();/ 插入DoubleCircularNode<T> *y = new DoubleCircularNode<T>if(k)y->data = x;y->right = p->right;21山东建筑大学计算机学院课程设计说明书p->right = y;y->left = p;y->right->left = y;else/作为第一个元素插入y->right=y;y->left=y;return *this;template <class T>DoubleCircular<T&g

38、t;& DoubleCircular<T>:Delete(int k, T& x)int max = length();if(k < 1 | k > max)throw OutOfBounds();DoubleCircularNode<T> *q = first;for(int index=1; index <k-1 && q; index+)q = q->right;if(!q) throw OutOfBounds();q->left->right = q->right;q->right-

39、>left = q->left;x = q->data;delete q;return *this;22山东建筑大学计算机学院课程设计说明书template <class T>bool DoubleCircular<T>:Find(int k, T& x) constint max=length();if(k < 0) throw OutOfBounds();if(k > max) throw OutOfBounds();DoubleCircularNode<T> *current = first;int index =

40、 1;/current的索引while(index < k-1 && current)current = current->right;index+;if(current)x = current->data;return true;return true;template <class T>int DoubleCircular<T>:Search(const T& x) constDoubleCircularNode<T> *current = first;/first->left->right = NULL;int index = 1;while (current && current->data != x)current = current->rig