数据结构课程设计：拓扑排序和关键路径复习进程

《数据结构》课程标准学时：72学时（其中：讲课学时：36 上机学时：36 ）先修课程：高等数学、C语言程序设计后续课程：软件开发相关的应用性课程（Android应用开发、软件工程等）适用专业：软件技术、移动应用开发、软件与信息服务等开课部门：信息工程与大数据学院一、课程的性质《数据结构》是面向软件技术相关专业的一门专业基础课，课程要求：熟练掌握线性表、栈和队的存储结构及基本操作，并能在相应的应用中正确地选用，培养学生用链式结构编写程序的能力；了解串和广义表的定义和存储结构；掌握数组的存储结构，熟悉稀疏矩阵的两种压缩存储方法的特点及适用范围；了解树的存储结构及特点，掌握二叉树和图的存储结构及其相应算法，培养学生用非线性结构解决实际问题的能力；掌握各种查找、排序方法，培养学生灵活应用已有排序方法的能力，开拓思路编写新的排序算法。

二、课程设计理念数据结构是计算机存储、组织数据的方式。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

精心选择的数据结构可以带来更高的运行或存储效率，数据结构往往同高兴的检索算法和索引技术有关。

1、课程地位理念在许多类型的程序设计中，数据结构的选择是一个基本的设计考虑因素。

许多大型的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。

许多时候，确定了数据结构后，算法就容易得到了。

有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。

不论哪种情况，选择合适的数据结构都是非常重要的。

选择了数据结构，算法随之确定，是数据而不是算法是系统构造的关键因素。

2、课程学情理念本课程开设在嵌入式系统工程专科第一学期，学生在学习本课程前已具备计算机基础、C语言基础等知识，本课程力图让学生学会在C语言环境下，运用面向对象的思想编写规范的代码，实现经典的数据结构和算法。

熟悉常用的数据结构和算法，使学生初步具备一个优秀的软件开发人员所应有的基本能力。

计算机考研各个科目的复习思路计算机考研各个科目的复习思路1、“数据结构”复习思路：“数据结构”的复习应以“线性结构→树型结构→图型结构→查找表→排序算法”为主线进行复习，重点在“线性结构”、“图”和“排序”三个部分，“线性结构”、“树”和“图”侧重基础概念、基础原理和基础方法的掌握，“图”、“查找”和“排序”则侧重具体应用的考核。

2、“计算机组成原理”复习思路：“计算机组成原理”按照冯·诺伊曼计算机5部分组成结构为大块进行复习。

“计算机系统概述”和“数的表示和运算”重点在于基本概念的掌握，没有具体应用。

而“存储器的层次结构”，“指令系统”，“中央处理器”，“总线”和“输入输出系统”部分除了掌握基本原理，基本方法外，重点掌握应用。

3、“操作系统”复习思路操作系统”复习思路：“操作系统”按照操作系统的基本功能为主线进行复习，即“进程管理”，“内存管理”，“文件管理”和“输入输出管理”。

其中重点部分在“进程管理”和“内存管理”。

一、重难点解析和复习建议统考大纲对数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。

当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。

下面我们来解析一下知识点：线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。

链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。

栈、队列和数组可以考查的知识点相比链表来说要多一些。

数据结构课设——有向图的深度、⼴度优先遍历及拓扑排序任务：给定⼀个有向图，实现图的深度优先, ⼴度优先遍历算法，拓扑有序序列，并输出相关结果。

功能要求：输⼊图的基本信息，并建⽴图存储结构（有相应提⽰），输出遍历序列，然后进⾏拓扑排序，并测试该图是否为有向⽆环图，并输出拓扑序列。

按照惯例，先上代码，注释超详细：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#pragma warning(disable:4996)#define Max 20//定义数组元素最⼤个数（顶点最⼤个数）typedef struct node//边表结点{int adjvex;//该边所指向结点对应的下标struct node* next;//该边所指向下⼀个结点的指针}eNode;typedef struct headnode//顶点表结点{int in;//顶点⼊度char vertex;//顶点数据eNode* firstedge;//指向第⼀条边的指针，边表头指针}hNode;typedef struct//邻接表（图）{hNode adjlist[Max];//以数组的形式存储int n, e;//顶点数，边数}linkG;//以邻接表的存储结构创建图linkG* creat(linkG* g){int i, k;eNode* s;//边表结点int n1, e1;char ch;g = (linkG*)malloc(sizeof(linkG));//申请结点空间printf("请输⼊顶点数和边数：");scanf("%d%d", &n1, &e1);g->n = n1;g->e = e1;printf("顶点数：%d 边数：%d\n", g->n, g->e);printf("请输⼊顶点信息（字母）：");getchar();//因为接下来要输⼊字符串，所以getchar⽤于承接上⼀条命令的结束符for (i = 0; i < n1; i++){scanf("%c", &ch);g->adjlist[i].vertex = ch;//获得该顶点数据g->adjlist[i].firstedge = NULL;//第⼀条边设为空}printf("\n打印顶点下标及顶点数据：\n");for (i = 0; i < g->n; i++)//循环打印顶点下标及顶点数据{printf("顶点下标：%d 顶点数据：%c\n", i, g->adjlist[i].vertex);}getchar();int i1, j1;//相连接的两个顶点序号for (k = 0; k < e1; k++)//建⽴边表{printf("请输⼊对<i,j>（空格分隔）：");scanf("%d%d", &i1, &j1);s = (eNode*)malloc(sizeof(eNode));//申请边结点空间s->adjvex = j1;//边所指向结点的位置，下标为j1s->next = g->adjlist[i1].firstedge;//将当前s的指针指向当前顶点上指向的结点g->adjlist[i1].firstedge = s;//将当前顶点的指针指向s}return g;//返回指针g}int visited[Max];//标记是否访问void DFS(linkG* g, int i)//深度优先遍历{eNode* p;printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已访问过的顶点visited值改为1p = g->adjlist[i].firstedge;//p指向顶点i的第⼀条边while (p)//p不为NULL时（边存在）{if (visited[p->adjvex] != 1)//如果没有被访问DFS(g, p->adjvex);//递归}p = p->next;//p指向下⼀个结点}}void DFSTravel(linkG* g)//遍历⾮连通图{int i;printf("深度优先遍历;\n");//printf("%d\n",g->n);for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问{DFS(g, i);//调⽤DFS函数}}}void BFS(linkG* g, int i)//⼴度优先遍历{int j;eNode* p;int q[Max], front = 0, rear = 0;//建⽴顺序队列⽤来存储，并初始化printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已经访问过的改成1rear = (rear + 1) % Max;//普通顺序队列的话，这⾥是rear++q[rear] = i;//当前顶点（下标）队尾进队while (front != rear)//队列⾮空{front = (front + 1) % Max;//循环队列，顶点出队j = q[front];p = g->adjlist[j].firstedge;//p指向出队顶点j的第⼀条边while (p != NULL){if (visited[p->adjvex] == 0)//如果未被访问{printf("%c ", g->adjlist[p->adjvex].vertex);visited[p->adjvex] = 1;//将该顶点标记数组值改为1rear = (rear + 1) % Max;//循环队列q[rear] = p->adjvex;//该顶点进队}p = p->next;//指向下⼀个结点}}}void BFSTravel(linkG* g)//遍历⾮连通图{int i;printf("⼴度优先遍历：\n");for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问过{BFS(g, i);//调⽤BFS函数}}}//因为拓扑排序要求⼊度为0，所以需要先求出每个顶点的⼊度void inDegree(linkG* g)//求图顶点⼊度{eNode* p;int i;for (i = 0; i < g->n; i++)//循环将顶点⼊度初始化为0{g->adjlist[i].in = 0;}for (i = 0; i < g->n; i++)//循环每个顶点{p = g->adjlist[i].firstedge;//获取第i个链表第1个边结点指针while (p != NULL)///当p不为空（边存在）{g->adjlist[p->adjvex].in++;//该边终点结点⼊度+1p = p->next;//p指向下⼀个边结点}printf("顶点%c的⼊度为：%d\n", g->adjlist[i].vertex, g->adjlist[i].in);}void topo_sort(linkG *g)//拓扑排序{eNode* p;int i, k, gettop;int top = 0;//⽤于栈指针的下标索引int count = 0;//⽤于统计输出顶点的个数int* stack=(int *)malloc(g->n*sizeof(int));//⽤于存储⼊度为0的顶点for (i=0;i<g->n;i++)//第⼀次搜索⼊度为0的顶点{if (g->adjlist[i].in==0){stack[++top] = i;//将⼊度为0的顶点进栈}}while (top!=0)//当栈不为空时{gettop = stack[top--];//出栈,并保存栈顶元素（下标）printf("%c ",g->adjlist[gettop].vertex);count++;//统计顶点//接下来是将邻接点的⼊度减⼀，并判断该点⼊度是否为0p = g->adjlist[gettop].firstedge;//p指向该顶点的第⼀条边的指针while (p)//当p不为空时{k = p->adjvex;//相连接的顶点（下标）g->adjlist[k].in--;//该顶点⼊度减⼀if (g->adjlist[k].in==0){stack[++top] = k;//如果⼊度为0，则进栈}p = p->next;//指向下⼀条边}}if (count<g->n)//如果输出的顶点数少于总顶点数，则表⽰有环{printf("\n有回路！\n");}free(stack);//释放空间}void menu()//菜单{system("cls");//清屏函数printf("************************************************\n");printf("* 1.建⽴图 *\n");printf("* 2.深度优先遍历 *\n");printf("* 3.⼴度优先遍历 *\n");printf("* 4.求出顶点⼊度 *\n");printf("* 5.拓扑排序 *\n");printf("* 6.退出 *\n");printf("************************************************\n");}int main(){linkG* g = NULL;int c;while (1){menu();printf("请选择：");scanf("%d", &c);switch (c){case1:g = creat(g); system("pause");break;case2:DFSTravel(g); system("pause");break;case3:BFSTravel(g); system("pause");break;case4:inDegree(g); system("pause");break;case5:topo_sort(g); system("pause");break;case6:exit(0);break;}}return0;}实验⽤图:运⾏结果：关于深度优先遍历 a.从图中某个顶点v 出发，访问v 。

数据结构之拓扑排序算法详解拓扑排序算法是一种常用于有向无环图（DAG）的排序算法，它可以将图中的顶点按照一定的顺序进行排序，使得图中任意一条有向边的起点在排序结果中都排在终点的前面。

在实际应用中，拓扑排序算法常用于解决任务调度、依赖关系分析等问题。

本文将详细介绍拓扑排序算法的原理、实现方法以及应用场景。

### 一、拓扑排序算法原理拓扑排序算法的原理比较简单，主要包括以下几个步骤：1. 从DAG图中选择一个入度为0的顶点并输出。

2. 从图中删除该顶点以及以该顶点为起点的所有有向边。

3. 重复步骤1和步骤2，直到图中所有顶点都被输出。

### 二、拓扑排序算法实现下面以Python语言为例，给出拓扑排序算法的实现代码：```pythondef topological_sort(graph):in_degree = {v: 0 for v in graph}for u in graph:for v in graph[u]:in_degree[v] += 1queue = [v for v in graph if in_degree[v] == 0] result = []while queue:u = queue.pop(0)result.append(u)for v in graph[u]:in_degree[v] -= 1if in_degree[v] == 0:queue.append(v)if len(result) == len(graph):return resultelse:return []# 测试代码graph = {'A': ['B', 'C'],'B': ['D'],'C': ['D'],'D': []}print(topological_sort(graph))```### 三、拓扑排序算法应用场景拓扑排序算法在实际应用中有着广泛的应用场景，其中包括但不限于以下几个方面：1. 任务调度：在一个任务依赖关系图中，拓扑排序可以确定任务的执行顺序，保证所有任务按照依赖关系正确执行。

《数据结构》课程设计指导书沈阳理工大学.信息学院2013.11.1一．目的与意义软件设计能力对计算机专业的学生是很重要。

通过数据结构的学习，使学生对软件编程能力有一定的提高。

数据结构课程设计是锻炼学生在进一步掌握模块化、结构化程序设计的方法的同时，培养学生运用已学知识分析问题、解决问题及编写实用程序的能力，通过对线性化、层次化、网络化数据结构的了解进一步掌握自然数据的结构方式及组织方式，让学生深入体会存储在计算机中的数据及程序中如何运用数据实现编程。

主要目的如下：1．通过本课程设计使学生对面向对象的设计过程有初的认识，并对面向对象的高能语言的学习打下基础，2．通过不同类型的程序设计使学生进一步掌握数据的几种不同的组织和存储方式，为高级编程做准备，3．为专业课的深入学习和毕业设计打基础二．任务和要求分析每一组题目，按要求完成相应的题目：1.题目参照附录中《数据结构课程设计》题目选题。

2. 要求：1)对相应的题目进行算法设计2)编写源代码3)上机调试4)显示调试结果5)写出实验总结3．课程设计说明书设计完成后，将自己选定的题目按上述要求完成课程设计说明书。

课程设计说明书内容包含：题目、要求、初步设计（可以是流程图、功能模块图）、详细设计、程序代码、测试数据、运行结果、遇到的问题及总结几部分。

三．进度安排设计总学时为2周第一周：查阅资料、小组讨论、进行模块划分写出分析报告，画Ｎ－Ｓ结构化框图,编写程序清单，上机调试.第二周周四、五:验收（计算机机房）,并将课程设计报告交上来.四.考核标准与成绩评定方式成绩评定有如下几项参考：1．初步设计内容的考核：是否有查阅资料能力？是否有设计思想？2．程序编码能力调试能力的考核：程序是否清晰、易读？在技算计上是否可独立完成程序的调试，是否熟练？3．说明书质量的考核：设计结构是否合理？叙述是否正确？方案是否可行？4．答辩：设计结果的调试能力，对自己设计是否熟练？5．出勤率极平时表现的考核：出勤超过2次不到者成绩为不及格。

《数据结构》课程教学大纲课程名称：数据结构（Data Structures）课程编号：CX414120A学分：4总学时：64(48+16)适用专业：计算机科学与技术先修课程：离散数学，C语言程序设计一、课程的性质、目的与任务数据结构是计算机科学与技术专业的一门专业基础课程。

通过课堂教学、课外练习和上机实习，使学生了解数据对象的特性及数据组织的基本方法，并初步具备分析和解决现实世界问题在计算机中的表示方法和及其处理的能力，让学生培养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。

二、教学基本要求✧了解线性表、栈、队列、字符串、数组、广义表、树、二叉树、图、查找表等几种数据结构的特性及数据组织的基本方法；✧理解各数据结构上的基础操作方法及复杂度的分析方法；✧掌握各数据结构及查找、排序的基本理论和基本知识，使学生具备从数据结构的角度出发，开发设计出较复杂软件的能力。

三、教学内容第一章绪论（4学时）1.数据，数据类型，数据结构(逻辑结构和存储结构)（1学时）2.数据结构的主要运算与基础知识（1学时）3.算法复杂度分析（2学时）算法的定义、算法的描述、算法设计的要求、算法分析初步第二章线性表（4学时）1.线性表的定义和基本运算（0.5学时）2.线性表的存储结构和实现（3学时）向量(顺序)存储结构、链式存储结构(单链表、双向链表和循环链表)3.链式表的应用(多项式的表示与相加) （0.5学时）第三章栈和队列（4学时）1.栈（2学时）栈的定义和基本运算、存储结构和实现、应用举例及栈与递归过程2.队列（2学时）队列的定义和基本运算、存储结构和实现及双端队列、输入和输出受限队列第四章串（3学时）1.串的定义、运算和存储结构（0.5学时）2.串的基本运算的实现（2.5学时）串的匹配、KMP算法及NEXT函数第五章数组和广义表（3学时）1.数组的定义和运算（0.5学时）2.数组的顺序存储结构及存储地址的计算（1学时）3.矩阵(特殊矩阵、稀疏矩阵)的压缩存储（1学时）4.广义表的定义、基本运算和存储结构（0.5学时）第六章树和二叉树（8学时）1.树的定义、基本运算和存储结构（1学时）2.二叉树的定义、性质和存储结构(顺序、链式) （1.5学时）3.二叉树的遍历和线索二叉树（2学时）4.树、二叉树与森林的转换；树和森林的遍历（1.5学时）5.二叉树的应用（2学时）二叉排序树、Huffman树第七章图（8学时）1.图的定义和术语（1学时）2.图的存储结构（2学时）3.图的遍历（1学时）4.图的连通性问题(连通分量、生成树、最小生成树) （1学时）5.DAG图及其应用（2学时）拓扑排序、关键路径6.最短路径（1学时）单源最短路径、每对顶点间的最短路径第九章查找（8学时）1.概述（0.5学时）2.顺序表的查找(顺序查找、折半查找、分块查找) （2学时）3.树表的查找（3学时）二叉排序树、平衡二叉树、B_树和B+树4.哈希表(Hash) （2.5学时）基本概念、Hash函数与Hash表的构造方法、Hash表的查找和冲突处理方法第十章内部排序（6学时）1.概述（0.5学时）2.插入排序(直接插入排序、折半插入排序、2-路插入排序、Shell排序) （1.5学时）3.选择排序(直接选择排序、树型选择排序、堆排序) （1.5学时）4.交换排序(冒泡排序、快速排序) （1.5学时）5.归并排序(2-路归并排序) （0.5学时）6.基数排序（0.5学时）实验内容：（8学时）实验一、指针与结构体操作实验二、线性表及其应用实验三、栈与队列操作实验四、串及其应用实验五、数组及其应用实验六、二叉树建树与遍历实验七、图的基本操作实验八、查找与排序四、教学参考书［1］严蔚敏等，《数据结构》（第二版）清华大学出版社,1993［2］严蔚敏等，《数据结构题集》,1995［3］ William Ford，William Topp，《Data Structure with C++》清华大学出版社Prentice Hall联合出版,1996五、说明实验内容具体内容及要求见实验指导书。

关键路径（CriticalPath）引⼊拓扑排序主要是为解决⼀个⼯程能否顺序进⾏的问题，但有时还需要解决⼯程完成需要的最短时间问题。

这时仅仅是拓扑排序是不够的。

通过拓扑排序，可以有效地分析出⼀个有向图是否存在环；若不存在，那它的拓扑排序是什么？另⼀⽅⾯，利⽤求关键路径的算法，可以得到完成⼯程的最短⼯期及关键活动有哪些。

（摘⾃《⼤话数据结构》）定义事件：开始XX事情 | 完成XX事情活动：做XX事情源点：某流程的开始汇点：某流程的结束AOE⽹：在⼀个表⽰⼯程的带权有向图中，⽤顶点表⽰事件，⽤有向边表⽰活动，⽤边上的权值表⽰活动的持续时间，这种有向图的边表⽰活动的⽹，我们称之为AOE⽹（Activity On Edge Network）。

把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最⼤长度的路径叫关键路径，在关键路径上的活动叫关键活动。

（摘⾃《⼤话数据结构》）事件是⼀个点，活动是⼀条线。

举例以炒⼀盘⾁作为⽰例：将炒⼀盘⾁⽐作⼀个⼯程。

⼀位⼤⼈负责厨房的事情，⼀位⼩孩负责从院⼦⾥摘菜并送到厨房。

⼩孩从院⼦⾥摘菜并送到厨房需要1.5分钟。

⼤⼈准备⾁需要7分钟；准备菜需要1.5分钟；炒⾁需要2分钟；炒菜需要1分钟。

问题：这项⼯程的最短时间为多少？显然，该⼯程的流程不是这样：摘菜送到厨房（1.5分钟）->准备⾁（7分钟）->准备菜（1.5分钟）->炒⾁（2分钟）->炒菜（1分钟），共13分钟。

因为⼩孩摘菜的同时⼤⼈可以准备⾁；在炒⾁的后⾯阶段可以将菜放⼊锅⾥⼀起炒，这也符合⽇常实践。

⽽准备菜这个活动⼜受到“摘菜并送到厨房”和“准备⾁”这两个活动的制约：先有菜才能对菜进⾏处理！先处理好⾁才能处理菜吧，厨房⾥只有⼀个⼈。

⽤前⾯的“事件”、“活动”、“源点”和“汇点”来表⽰这个⼯程。

源点：开始准备⾁/开始摘菜送到厨房汇点：完成炒菜/完成炒⾁事件：开始摘菜并送到厨房>完成摘菜并送到厨房开始准备⾁>完成准备⾁开始准备菜>完成准备菜开始炒⾁>完成炒⾁开始炒菜>完成炒菜约束条件：“完成准备⾁”和“完成摘菜并送到厨房”才能“开始准备菜”。

目录课题一 joseph环 41．1 问题的提出1.1．问题的提出41.2 概要设计2.1算法思想51．3流程图根据算法思想，画程序流程图如下：661．4 源代码1.3．详细设计 7 输入m 、nm>0且n>0的整数建立含n 个结点的链表且用head 指向第一个元素，结点数据域包含password 、No 、以及指向下一结点的指head=>pn ≥2(m%n)==0?n:m%n=>1=>i i<mp →next=>pi++输出p →Nop →password=>m删除p 所指向结点n--输出p →No结束开始1．5 结果与分析.4 测试及性能分析10课题二拓扑排序 112．1 问题的提出2.1 问题的提出112. 2 概要设计112．3 流程图2.根据算法思想，画流程图如下：1212 开始设辅助数组indegree 记录图的各顶点的入度值，并将indegree 数组各变量赋初值。

输入图的顶点数、边数建立一个栈，存储图的顶点的序号用邻接表法建图，并计算出indegree 数组中各变量值根据indegree 数组将入度为0的顶点入栈count 对输出顶点计数0=>count栈不空删除栈顶元素,赋给i count++将与第i 个顶点链接的各顶点入度减1输出第i 个顶点值 顶点入度为0 顶点序号入栈count<G.vexnum输出“拓扑排序成功” 输出“拓扑排序不成功” 结束2．4 源代码132．5 结果与分析2.4 测试及性能分析17课题三纸牌游戏 193．1 问题的提出.1 问题的提出193. 2 概要设计191.当每个号码每次遇到是某个数的倍数时，都会相应的翻一次，这样，每张牌会翻的次数就各不一样，可能很多次，也可能只有一两次，结果就只是要输出在经过各个不同次数的翻牌后，正面向上的牌都有哪几个。

举例说明一下，比如24，第一次它是2的倍数时要从正面翻到背面，当进行到3时，就又要从背面翻回来，而到4时还要在翻，同理呢，到6.8.12…它都要来回的翻。

. . .. . .课程设计任务书学生：专业班级：指导教师：工作单位：计算机科学系题目: 拓扑排序初始条件：（1）采用邻接表作为有向图的存储结构；（2）给出所有可能的拓扑序列。

（3）测试用例见严蔚敏《数据结构习题集(C语言版)》p48题7.9图要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下容：1. 问题描述简述题目要解决的问题是什么。

2. 设计存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。

4. 经验和体会（包括对算法改进的设想）5. 附源程序清单和运行结果。

源程序要加注释。

如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。

说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。

2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。

时间安排：1．第17周完成，验收时间由指导教师指定2．验收地点：实验中心3．验收容：可执行程序与源代码、课程设计报告书。

指导教师签名：2013年6月14日系主任（或责任教师）签名：年月日拓扑排序目录1问题描述2具体设计2.1存储结构设计2.2主要算法设计2.2.1拓扑排序的算法总体设计2.2.2将有向图表示为邻接表2.2.3拓扑排序函数的设计2.2.4顺序表的运算设计2.3测试用例设计3调试报告3.1设计和编码的分析3.2调试过程问题及解决4经验与体会5用户使用说明6参考文献7附录源代码与运行结果1问题描述题目：拓扑排序如果用有向图表示一个工程，在这种有向图中，用顶点表示活动，用有向边<vi,vj>表示活动vi必须先于活动vj进行，这种有向图叫做顶点表示活动的网络，记作AOV 网络。

对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得AOV网络中的所有应存在前驱和后继的关系都能得到满足，这种构造AOV网络全部顶点的拓扑有序序列的运算叫做拓扑排序。

南信大816数据结构大纲南京信息工程大学（南信大）计算机科学与技术816班的数据结构课程大纲包括以下内容：一、课程概述。

1.1 课程名称和学时安排。

1.2 课程目标和重点。

1.3 教材和参考书目。

二、基本概念和算法分析。

2.1 数据结构的基本概念和术语。

2.2 算法的基本概念和特性。

2.3 算法复杂度分析。

三、线性表。

3.1 线性表的定义和基本操作。

3.2 顺序表和链表的实现。

3.3 线性表的应用，栈和队列。

四、树结构。

4.1 树的基本概念和性质。

4.2 二叉树的存储结构和遍历算法。

4.3 霍夫曼树和哈夫曼编码。

4.4 树的应用，并查集和赫夫曼编码。

五、图结构。

5.1 图的基本概念和表示方法。

5.2 图的遍历算法，深度优先搜索和广度优先搜索。

5.3 最小生成树算法，Prim算法和Kruskal算法。

5.4 最短路径算法，Dijkstra算法和Floyd算法。

5.5 图的应用，拓扑排序和关键路径。

六、排序与查找算法。

6.1 内部排序算法，插入排序、冒泡排序、选择排序、快速排序、归并排序、堆排序。

6.2 外部排序算法，多路归并排序。

6.3 查找算法，顺序查找、二分查找、哈希查找。

七、高级数据结构。

7.1 线索二叉树和平衡二叉树。

7.2 B树和B+树。

7.3 图的存储结构和最短路径算法优化。

7.4 哈希表和散列函数设计。

八、实验和编程实践。

8.1 数据结构实验的设计和实施。

8.2 编程实践，使用数据结构解决实际问题。

以上是南京信息工程大学816班数据结构课程的大纲概述。

在课程中，学生将学习数据结构的基本概念、常用算法的设计与实现，以及数据结构在实际问题中的应用。

通过理论学习和实践操作，培养学生的数据结构分析与解决问题的能力。