数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.13M 资料格式：docx 举报版权申诉

第1页 / 共10页

weixin_42795141-11290586-数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx.pdf-第2页.png

第2页 / 共10页

weixin_42795141-11290586-数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx.pdf-第3页.png

第3页 / 共10页

weixin_42795141-11290586-数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx.pdf-第4页.png

第4页 / 共10页

weixin_42795141-11290586-数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx.pdf-第5页.png

第5页 / 共10页

weixin_42795141-11290586-数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx.pdf-第6页.png

第6页 / 共10页

weixin_42795141-11290586-数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx.pdf-第7页.png

第7页 / 共10页

weixin_42795141-11290586-数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx.pdf-第8页.png

第8页 / 共10页

文本预览

数据结构课程设计报告题目：输出 DAG 的所有拓扑排序序列学号： xxxxxxxxxxx 姓名： xxxxxx 专业：计算机科学与技术提交日期： 2019 年 5 月 27 日课程培养目标打分项目得分 1. 培养学生通过分析程序设计问题描述来选择合适的数据结构，运用所学基本算法，熟练编写 C/C++代码，完成程序调试与测试的能力，使学生具备一定的较复杂算法程序的设计、开发与分析能力，能够分析、查找算法代码的缺陷或错误，能够基于算法时间、空间复杂度分析结果来改进或优化算法（对应毕业要求指标点 2.1） 2. 培养学生撰写实验报告以及课程设计报告、通过文字、图表、公式、设计测试用例等方式方法来描述算法数据结构、算法设计思想、算法程序流程，总结算法空间与时间复杂度，以及描述程序测试结果的能力(对应毕业要求指标点 4.1) 项目运行验收 (5 分) 算法复杂度分析 (2 分) 源程序及程序注释 (3 分) 数据结构描述（2 分）算法设计描述（5 分）程序测试报告（3 分）总分 20 分报告目录 1. 课程设计内容与要求(第 2 页) 2. 程序设计报告 2.1 概述(第 2 页) 2.2 数据结构设计与说明(第 2 页) 2.3 算法设计与说明(第 3 页) 2.4 算法复杂度分析(第 3 页) 3. 程序测试报告与结论(第 3-5 页) 4. 源程序附录(第 5-10 页) 1 / 10

1.课程设计内容与要求用字符文件提供数据建立 DAG（有向无环图）合适的存储结构。编写程序，输出所有可能的拓扑排序序列。要求输出的拓扑排序结果用顶点序号或字母表示。输出结果需存于字符文件。输出结果中应显示全部拓扑排序序列的数目。如果 DAG 存在环（即拓扑排序失败），输出结果中应显示拓扑排序序列的数目为 0。课程设计报告要求给出详细算法描述，在结论部分应分析算法的时间复杂度和空间复杂度，并给出分析的结果。 2. 程序设计报告 2.1 概述程序的目的是输出 DAG 所有可能的拓扑排序序列，如果不是 DAG 则输出提示信息。输入的 DAG 信息在字符文件中，包括顶点序号，顶点的出度和入度以及前驱节点；输出的拓扑排序用顶点序号表示，输出结果保存在字符文件中，并且输出信息中显示全部拓扑排序序列的数目。 2.2 数据结构设计与说明 DAG 使用邻接表的存储方式。 // 邻接表节点数据结构 typedef struct node{ int code; // 节点下标 struct node *next; // 节点指针域，指向邻接表的下一个节点 }ArcNode; // 邻接表头结点数据结构 typedef struct{ int info; // 顶点入度 // 顶点出度 int k; int i; // 顶点下标 ArcNode *firstarc; // 节点指针域，指向指向头结点出度节点 }HNode; // DAG 数据结构 typedef struct{ int n; // 实际顶点数目 HNode h[MAX_N]; // 头结点数组 }DAGGraph; 2 / 10

2.3 算法设计与说明算法的思想是递归。在图中搜索入度为零的节点进栈，当节点被存到拓扑排序序列数组中时，此节点的下一节点入度减一。如果入度减一之后为零，则此节点入栈。每次栈中入度为零的节点分别进行递归，递归结束退栈，直到栈中所有的节点都递归结束。递归的结果存放在一维数组中，并且产生一个 DAG 拓扑排序的时候写入文件。栈中其他元素开始递归都是从上一元素递归的位置开始将拓扑排序序列刷新。 2.4 算法复杂度分析算法的空间复杂度为 n（n 为顶点数量）；算法的时间复杂度为 O(n²) （n 为顶点数量）。 3. 程序测试报告与结论（1）测试一（2）测试二 3 / 10

（3）测试三 4 / 10

4. 源程序附录 // Predefine.h #ifndef PREDEFINE_H_ #define PREDEFINE_H_ #include #define MAX_N 20 // 最大节点数 // 邻接表节点数据结构 typedef struct node{ int code; // 节点下标 struct node *next; }ArcNode; // 邻接表头结点数据结构 typedef struct{ int info; // 顶点入度 // 顶点出度 int k; int i; // 顶点下标 ArcNode *firstarc; }HNode; // DAG 图数据结构 typedef struct{ int n; // 实际顶点数目 HNode h[MAX_N]; // 头结点数组 }DAGGraph; #endif // PREDEFINE_H_ // main.cpp #include #include "Predefine.h" extern int InitGraph(DAGGraph &graph); extern bool TopoSort(DAGGraph &graph); int main() { DAGGraph graph; 5 / 10

InitGraph(graph); // 初始化 DAG bool result = TopoSort(graph); if(result==false) { // 拓扑排序 std::cout << "Not DAG." << std::endl; } return 0; } // init_graph.cpp #include "Predefine.h" #include #include int InitGraph(DAGGraph &graph) { /** \brief 初始化 DAG * * \param DAG * \param DAGGraph 的指针 * \return 无返回值 * */ std::ifstream file; file.open("graph.txt",std::ios::in); if(!file.is_open()) { std::cout << "Can not open graph.txt!" << std::endl; exit(-1); // 异常退出 } file >> graph.n; for(int it=0;it> graph.h[it].i; // 读入顶点下标 file >> graph.h[it].info; // 读入顶点入度 file >> graph.h[it].k; // 读入顶点出度 graph.h[it].firstarc = NULL; // 邻接表头结点指针域置空 ArcNode *p; // 读入每个顶点的邻接表 for(int j=0;j> Node->code; Node->next = NULL; // 每个节点的指针域都置空 if(j==0) { 6 / 10

graph.h[it].firstarc = Node; p = graph.h[it].firstarc; continue; } p->next = Node; p = Node; } } file.close(); return 0; // 初始化 DAG 成功 } // topological_sort.cpp #include "Predefine.h" #include #include void test(DAGGraph graph, int k, int a[], int num); int flag; // 标志变量，为假舍弃递归结果 int count = 0; // 标志变量，count>=graph.n 时，证明 graph 是 DAG std::ofstream file; bool TopoSort(DAGGraph &graph) { /** \brief DAG 拓扑排序 * * \param DAG * \return if(DAG) return true; else return false; * */ // ArcNode *p; std::vector S; file.open("result.txt",std::ios::out); // DAG 入度为零的节点入栈 for(int i=0;i

while(S.size()) { // 输出该节点并且退栈 i = S.back(); std::cout << i << " count++; S.pop_back(); for(p=graph.h[i].firstarc;p;p=p->next) { "; // i 节点关联的节点入度-1 为 0 之后入栈 if((--graph.h[p->code].info)==0) { S.push_back(p->code); } } } file.close(); // 如果一次都没有排序成功，返回 false，否则返回 true if(count=graph.n) { return true; } return false; } void test(DAGGraph graph, int k, int a[], int num) { 8 / 10

分享到：

赞收藏

资料库

数据结构课程设计-输出DAG的所有拓扑排序序列-内容与要求.docx

相关推荐

课程资源

热门标签

最新资料