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

山东建筑大学计算机科学与技术学院课程设计说明书题目：基于逆邻接表的有向图基本操作的实现课程：数据结构院（部）：计算机学院专业：计科班级：133学生姓名：潘含笑学号：20131111092指导教师：李盛恩完成日期：2015.07.03山东建筑大学计算机学院课程设计说明书目录课程设计任务书..................................................I课程设计任务书.................................................II逆邻接链表实现有向图............................................3一、问题描述................................................3二、数据结构................................................3三、逻辑设计................................................3四、编码....................................................5五、测试数据...............................................14六、测试情况..............................................16逆邻接链表实现有向图...........................................17一、问题描述...............................................17二、数据结构...............................................17三、逻辑设计...............................................17四、编码...................................................18五、测试数据...............................................24七、测试情况..............................................24结论..........................................................26课程设计指导教师评语...........................................28山东建筑大学计算机学院课程设计说明书I山东建筑大学计算机科学与技术学院课程设计任务书指导教师（签字）：教研室主任（签字）设计题目基于逆邻接表的有向图基本操作的实现已知技术参数和设计要求题目三、实现类NetWork，实现BFS、DFS、拓扑排序，并实现采用逆邻接表作为存储结构的有向图，要继承NetWork。逆邻接表要使用STL提供的List和Vector等实现。设计内容与步骤1、设计存储结构2、设计算法3、编写程序，进行调试4、总结并进行演示、讲解设计工作计划与进度安排2015.6.17~2015.6.23，实现基类Network和有向图Graph，实现逆邻接链表的存储结构。2015.6.23~2015.7.1，编写测试代码。2015.7.1~2015.7.3，改正一些错误，完成实验。设计考核要求1、考勤20%2、课程设计说明书50%3、成果展示30%山东建筑大学计算机学院课程设计说明书II山东建筑大学计算机科学与技术学院课程设计任务书指导教师（签字）：教研室主任（签字）设计题目双向循环链表已知技术参数和设计要求实现双向循环链表。设计内容与步骤5、设计存储结构6、设计算法7、编写程序，进行调试8、总结并进行演示、讲解设计工作计划与进度安排2015.4.22~2015.4.35，实现双向循环链表2015.4.25~2015.4.29，编写测试代码。设计考核要求4、考勤20%5、课程设计说明书50%6、成果展示30%山东建筑大学计算机学院课程设计说明书3逆邻接链表实现有向图一、问题描述二、数据结构三、逻辑设计1、总体思路先实现Network类，通过队列实现BFS，通过堆栈实现DFS和拓扑排序。再构建Graph类，并继承Network类实现以逆邻接链表为存储结构的有向图。2、模块划分（以图示的方法给出各个函数的调用关系）21543612345611232345山东建筑大学计算机学院课程设计说明书43、函数或类的具体定义和功能Network类：Network类Graph类Begin虚函数Nextvertex虚函数Edges虚函数Vertices虚函数Initializepos虚函数Deactivatepos虚函数BFS函数DFS函数Topological函数Begin函数Nextvertex函数Edges函数Vertices函数Initializepos函数Deactivatepos函数Out函数山东建筑大学计算机学院课程设计说明书5virtualintBegin(inti)=0;//确定起始顶点virtualintNextvertex(inti)=0;//下一个顶点virtualintEdges()=0;//确定点virtualintVertices()=0;//确定边virtualvoidInitializepos(inti)=0;//让迭代器等于链表的第i个顶点的第一个元素virtualvoidDeactivatepos(inti)=0;//删除迭代器指的元素voidBFS(intv,intreach[],intlabel,inta[]);//宽度遍历voidDFS(intv,intreach[],intlabel,inta[]);//深度遍历boolTopological(intv[]);//拓扑排序virtual~Network();//析构函数Graph类：virtual~Graph();//析构函数intInDegree(intnode);//入度intOutDegree(intnode);//出度Graph&Add(intnode1,intnode2);//添加点Graph&Delete(intnode1,intnode2);//删除点intBegin(inti);//确定起始顶点intNextvertex(inti);//下一个顶点intEdges(){returne;}//确定点intVertices(){returnn;}//确定边voidInitializepos(inti){pos=al[i].begin();}////让迭代器等于链表的第i个顶点的第一个元素voidDeactivatepos(inti){al[i].erase(pos);}//删除迭代器指的元素voidOut();//输出函数四、编码//Network.h#includeiostream#includequeue#includestack#includevectorusingnamespacestd;classNetwork{public:virtualintBegin(inti)=0;山东建筑大学计算机学院课程设计说明书6virtualintNextvertex(inti)=0;virtualintEdges()=0;virtualintVertices()=0;virtualvoidInitializepos(inti)=0;//让迭代器等于链表的第i点的第一个元素virtualvoidDeactivatepos(inti)=0;//删除迭代器指的元素voidBFS(intv,intreach[],intlabel,inta[]);//宽度遍历voidDFS(intv,intreach[],intlabel,inta[]);//深度遍历boolTopological(intv[]);//拓扑排序virtual~Network();};//Network.cpp#includeNetwork.hvoidNetwork::BFS(intv,intreach[],intlabel,inta[]){intn=Vertices();//获取n的值,有几个顶点queueintQ;//创建一个队列intk=0;//定义一个k来使元素得到保存reach[v]=label;//标记点a[k++]=v;//用数组记录BFS的遍历顺序Q.push(v);//把一个元素加入队列while(!Q.empty()){intx;x=Q.front();//获取队列中的第一个元素Q.pop();//让队列中的第一个元山东建筑大学计算机学院课程设计说明书7素出队for(inti=1;i=n;i++)//寻找x的下一个节点{intu=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(inti=v;in;i++)//输出BFS的运行结果{if(reach[i]==label)cout执行完BFS后第i个元素被标记endl;elsecout执行完BFS后第i个元素没有被标记endl;}cout从节点v开始BFS遍历的顺序是;for(inti=1;in;i++)//输出BFS的遍历顺序{山东建筑大学计算机学院课程设计说明书8couta[i-1];};coutendl;}voidNetwork::DFS(intv,intreach[],intlabel,inta[]){stackintS;///创建一个堆栈intn=Vertices();//获取n的值intk=0;S.push(v);//把元素v加入堆栈while(!S.empty()){intx=S.top();//获取堆栈的栈顶元素if(!reach[x])//如果元素没被标记，就把元素标记{reach[x]=label;a[k++]=x;S.pop();//把堆栈的栈顶弹出for(inti=1;i=n;i++)//获取节点的下一个元素{intu=Begin(i);if((u==x)&&(!reach[i])){S.push(i);//把元素加入堆栈}while(u){u=Nextvertex(i);if((u==x)&&(!reach[i])){S.push(i);}}山东建筑大学计算机学院课程设计说明书9}}elseS.pop();//如果被标记元素就弹出}for(inti=v;in;i++)//输出DFS的运行结果{if(reach[i]==label)cout执行完DFS后第i个元素被标记endl;elsecout执行完DFS后第i个元素没有被标记endl;}cout从节点1开始DFS遍历的顺序是;for(inti=1;in;i++)//输出DFS的遍历顺序{couta[i-1]ends;};coutendl;}boolNetwork::Topological(intv[]){intn=Vertices();//获取n的值vectorinta(n+1);stackintS;//创建一个堆栈for(inti=1;i=n;i++)//初始化数组a，使每个点的a等于0，用来记录点的入度a[i]=0;for(inti=1;i=n;i++)//遍历整个邻接链表，有入度的节点增加a的值山东建筑