数据结构拓扑排序

拓扑排序，判断有向图中是否有环【原创】今天我们来聊聊有向图中环的判断，在数据结构中我们知道，通过拓扑排序可以判断有向图中是否存在环，对于有向图的存储我们采⽤邻接表的形势，这⾥为了简化链表的操作，我们省略了链表，避免了指针的⿇烦，直接采⽤了c++中的vector来模拟链表，操作更加的⽅便；具体详细的使⽤，建议百度⼀下，这⾥不多说，⾄于拓扑排序的具体思想，相信⼤家应该都了解，那么直接上代码，如果有不理解的，建议查阅数据结构书籍，搞懂思想，结合这份代码，很好理解1 #include <stdio.h>2 #include <queue>3 #include<vector>4 #include<stdlib.h>5using namespace std;6//拓扑排序中使⽤的对列和模拟链表的向量7 vector<int> edge[501];//邻接链表8 queue<int> Q;//保存⼊股为0的节点9int main(){10//拓扑排序，判断⼀个有向图中是否存在环11int inDegree[501];//统计每⼀个节点的⼊度；12int n,m;13while (scanf("%d%d",&n,&m)!=EOF) {//多组数据的测试14if (m==0&&n==0) break;15for (int i = 0; i<n; i++) {16 inDegree[i] = 0;//刚开始的节点⼊度均为017 edge[i].clear();//清除前⼀组数据的残留18 }19while(m--!=0){20int a,b;//输⼊m组节点关系21 scanf("%d%d",&a,&b);22 inDegree[b]++;//出现了⼀条边指向b，所以⼊度增加123 edge[a].push_back(b);//24 }25while (Q.empty()==false) {26 Q.pop();//清除之前的数据27 }28for(int i = 0;i<n;i++){29if (inDegree[i]==0) {30 Q.push(i);31 }32 }33int cnt = 0;34while (Q.empty()==false) {//当队列中还有⼊度为0的点35int newP = Q.front();36 Q.pop();//这⾥不需要保留拓扑排序的路径，因⽽不需要保存弹出来的值37 cnt++;38for (int i = 0; i<edge[newP].size(); i++) {39 inDegree[edge[newP][i]]--;//去除⼀条边后，将所指向的后继节点的如度减140if (inDegree[edge[newP][i]]==0) {41 Q.push(edge[newP][i]);42 }43 }44 }45if (cnt==n) {46 puts("YES");47 }else{48 puts("NO");49 }50 }51return0;52 }53/**************************************************************54 Problem: 144855 User: Numen_fan56 Language: C++57 Result: Accepted58 Time:10 ms59 Memory:1064 kb60****************************************************************/注意：这份代码，输⼊两个数字n、m,n表⽰有n个节点，m表⽰有m对关系，即接下来有m⾏，每⼀⾏两个数字a、b，表⽰a到b有边，；同时这⾥可以测试多组数据，这种编程思想是很好的，不⽤测试⼀组数据酒run⼀次，⿇烦，同时，看到代码35-37⾏中，这⾥只计算cnt总数，并没有保存拓扑排序的序列，如果需要求出序列，也很容易吧，将newP节点保存即可，本例⼦中采⽤queue队列来保存⼊度为0 的节点，那么其实也可以⽤stack来保存，原因很简单，因为拓扑排序不唯⼀；。

树的拓扑序列概述树是一种常见的数据结构，它由节点和边组成，具有层次结构。

在树中，每个节点可以有零个或多个子节点，而且每个节点都只有一个父节点（除了根节点）。

树的拓扑序列是根据节点之间的父子关系确定的一种序列，它描述了树中节点的相对位置。

拓扑排序拓扑排序是一种对有向无环图（DAG）的节点进行排序的算法，它可以用来解决一些实际问题，比如任务调度、依赖关系的处理等。

在树中，由于不存在环，所以拓扑排序的结果是唯一的。

树的拓扑序列定义树的拓扑序列定义为树中节点的一种排序方式，满足以下条件： 1. 根节点是序列的第一个节点。

2. 对于任意非叶子节点，它的子节点在序列中出现在它之后。

3. 对于任意节点，它的兄弟节点在序列中相邻。

拓扑排序算法拓扑排序算法可以通过深度优先搜索（DFS）或广度优先搜索（BFS）实现。

下面以DFS为例介绍树的拓扑序列的生成过程。

1. 选择根节点从树中选择一个节点作为根节点，可以根据实际需求选择任意一个节点作为根节点。

2. 遍历子节点从根节点开始，先遍历它的所有子节点。

对于每个子节点，递归地进行步骤3和步骤4。

3. 生成子树的拓扑序列对于每个子节点，按照步骤2的方式生成它的子树的拓扑序列。

4. 合并拓扑序列将当前节点和它的子树的拓扑序列合并，得到当前节点及其子节点的拓扑序列。

5. 返回结果返回根节点及其子节点的拓扑序列作为最终结果。

示例为了更好地理解树的拓扑序列，下面以一个简单的树为例进行说明。

A/ | \B C D/ \ / \E F G H按照上述算法，树的拓扑序列为E, F, B, G, C, H, D, A。

应用树的拓扑序列在实际应用中有很多用途，下面介绍两个常见的应用场景。

1. 任务调度在任务调度中，存在一些任务之间的依赖关系。

比如，任务A依赖任务B和任务C 完成后才能开始。

这时，可以将任务之间的依赖关系表示为一棵树，树的拓扑序列就是任务的执行顺序。

2. 依赖关系处理在处理依赖关系的场景中，需要根据依赖关系确定一组操作的执行顺序。

图的拓扑排序算法图是计算机科学中常用的数据结构之一，它由一些节点（点）和连接这些节点的边（线）组成。

在计算机科学中，图经常被用来解决很多问题，例如计算机网络路由、调度、自然语言处理等等。

其中，图的拓扑排序算法是一个十分重要且广泛应用的算法。

在本文中，我们将详细介绍图的拓扑排序算法的原理及应用。

一、拓扑排序算法简介首先，我们来了解一下什么是拓扑排序算法。

拓扑排序是指将有向无环图(Directed Acyclic Graph, DAG)中节点按照拓扑序列排列的过程。

拓扑序列是指，在排列中，如果存在一条从节点A到节点B的路径，那么在拓扑序列中节点A必须出现在节点B之前。

如果存在环路，则不存在拓扑序列。

拓扑排序算法通常用于任务调度等场景中。

在计算机科学中，拓扑排序算法可以使用两种方法进行实现：基于搜索的算法和基于入度的算法。

二、基于搜索的算法基于搜索的算法是一种比较直接的实现思路，我们可以使用深度优先搜索或者广度优先搜索来实现。

深度优先搜索的方法是，先访问图中入度为0的节点，将其加入拓扑序列中，并将其后继节点的入度减1，直到遍历完整幅图。

基于入度的算法基于入度的算法是另一种有用的实现思路。

首先，我们可以记录每个节点的入度值。

入度是指图中所有指向该节点的边的个数。

对于一个拓扑序列中的节点，它的入度必定为0。

因此，我们可以将入度为0的节点放入队列中，然后对该节点的后继节点的入度减1。

如果减去入度后某个节点的入度为0，则也将其加入队列中。

不断循环这一过程，直到遍历完整幅图。

三、应用场景拓扑排序算法可以在很多场景中应用。

例如，任务调度。

在计算机中，任务调度是指将一些任务分配给不同的处理器进行处理的过程。

我们可以将每个任务看作一个节点，处理器看作边。

拓扑排序算法可以帮助我们找到一个最优的任务调度方案。

另一个应用场景是编译器和依赖管理器。

在编译一个程序时，我们需要按指定顺序编译不同的模块。

如果模块之间存在依赖关系，则需要使用拓扑排序算法来进行模块的编译顺序优化。

图基本算法拓扑排序（基于dfs） 拓扑排序，是对有向⽆回路图进⾏排序，以期找到⼀个线性序列，这个线性序列在⽣活正可以表⽰某些事情完成的相应顺序。

如果说所求的图有回路的话，则不可能找到这个序列。

在⼤学数据结构课上，我们知道求拓扑排序的⼀种⽅法。

⾸先⽤⼀个⼊度数组保存每个顶点的⼊度。

在进⾏拓扑排序时，我们需要找到⼊度为0的点，将其存⼊线性序列中，再将其从图中删除（与它相关的边都删除，相邻的顶点的⼊度均减1），再重复上⾯的操作，直⾄所有的顶点都被找到为⽌。

如果不对每次找⼊度为0的顶点的⽅法进⾏处理，⽽直接去遍历⼊度数组，则该算法的时间复杂度为O(|V|2)，如果使⽤⼀个队列来保存⼊度为0的顶点，则可以将这个算法的复杂度降为O(V+E)。

今天在算法导论上看了⽤dfs来求拓扑排序的算法，才发现其⾼深之处，膜拜之Orz…下⾯是算法导论的叙述： 本节说明了如何运⽤深度优先搜索，对⼀个有向⽆回路图（dag）进⾏拓扑排序。

对有向⽆回路图G=(V,E)进⾏拓扑排序后，结果为该图顶点的⼀个线性序列，满⾜如果G包含边（u, v），则在该序列中，u就出现在v的前⾯（如果图是有回路的，就不可能存在这样的线性序列）。

⼀个图的拓扑排序可以看成是图中所有顶点沿⽔平线排列⽽成的⼀个序列。

使得所有的有向边均从左指向右。

因此，拓扑排序不同于通常意义上的排序。

在很多应⽤中，有向⽆回路图⽤于说明时间发⽣的先后次序，下图1即给出⼀个实例，说明Bumstead教授早晨穿⾐的过程。

他必须先穿好某些⾐服，才能再穿其他⾐服（如先穿袜⼦后穿鞋），其他⼀些⾐服则可以按任意次序穿戴（如袜⼦和裤⼦），在图1中，有向边<u，v>表⽰⾐服u必须先于⾐服v穿戴。

因此，该图的拓扑排序给出了⼀个穿⾐的顺序。

图2说明了对该图进⾏拓扑排序后，将沿⽔平线⽅向形成⼀个顶点序列，使得图中所有有向边均从左指向右。

拓扑排序算法具体步骤如下：1、调⽤dfs_travel()；2、在dfs_travel()每次调⽤dfs()的过程中，都记录了顶点s的完成时间，将顶点s按完成顺序保存在存放拓扑排序顺序的数组topoSort[]中。

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

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

按照惯例，先上代码，注释超详细：#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. 任务调度：在一个任务依赖关系图中，拓扑排序可以确定任务的执行顺序，保证所有任务按照依赖关系正确执行。

拓扑数据结构的名词解释随着科技的快速发展，数据的规模和复杂度急剧增加，大数据和人工智能成为了当今世界的热点话题。

在处理如此庞大和复杂的数据时，拓扑数据结构扮演着重要的角色。

本文将对拓扑数据结构的相关术语进行解释，帮助读者更好地理解这一概念。

一、图 (Graph)图是拓扑数据结构的基础。

它由节点集合和边集合组成。

节点代表实体，边则表示节点之间的关系。

图可以用来描述各种各样的关系网络，如社交网络、交通网络等。

图可以分为有向图和无向图，有向图的边是有方向的，而无向图的边是无方向的。

二、节点 (Node)节点是图的基本元素，也称为顶点。

每个节点可以具有零个或多个关联的边，用来表示节点之间的关系。

节点可以包含数据、属性和其他相关信息。

三、边 (Edge)边是图中节点之间的连接线。

边可以是有向的，表示从一个节点到另一个节点的单向关系；也可以是无向的，表示两个节点之间的双向关系。

边可以具有权重，用来表示节点之间的关联强度或距离。

四、路径 (Path)路径是图中的一条连接序列，由一系列的边组成。

路径可以是闭合的，即起点和终点相同，形成环；也可以是非闭合的，连接不同的节点。

五、连通性 (Connectivity)连通性是指图中节点之间的关联程度。

一个图可以是强连通的，即任意两个节点之间都存在路径；也可以是弱连通的，即只有部分节点之间存在路径。

六、拓扑排序 (Topological Sorting)拓扑排序是对有向无环图进行排序的一种算法。

在一个有向图中，如果存在一条路径从节点 A 到节点 B，那么在排序结果中，节点 A 应该在节点 B 的前面。

拓扑排序可以用来解决任务调度、依赖关系等问题。

七、最短路径 (Shortest Path)最短路径是指在图中找到两个节点之间路径长度最短的路径。

最短路径算法可以用来解决如最优路径规划、网络路由等问题。

常见的最短路径算法包括迪杰斯特拉算法和弗洛伊德算法。

八、网络流 (Network Flow)网络流是指在图中沿着边进行的一种资源分配。

一、实训目的通过本次拓扑排序实训，掌握拓扑排序的基本原理和算法实现方法，能够运用拓扑排序解决实际问题，提高自己在数据结构和算法方面的应用能力。

二、实训内容1. 拓扑排序原理及算法拓扑排序是一种针对有向无环图（DAG）的排序方法，它将图中的顶点按照某种顺序排列，使得图中所有的有向边都满足方向要求。

具体来说，拓扑排序要求在有向边(u,v)中，顶点u必须在顶点v之前。

拓扑排序的基本思想是：从入度为0的顶点开始，将其加入拓扑序列，然后删除该顶点及其所有出边，更新其他顶点的入度。

重复这个过程，直到所有顶点都被加入拓扑序列。

2. 拓扑排序算法实现本次实训中，我们将学习两种拓扑排序算法实现：（1）基于邻接矩阵的拓扑排序首先，我们使用邻接矩阵表示有向图。

然后，遍历邻接矩阵，找出所有入度为0的顶点，将其加入拓扑序列。

接着，删除该顶点及其所有出边，更新其他顶点的入度。

重复这个过程，直到所有顶点都被加入拓扑序列。

（2）基于邻接表的拓扑排序邻接表是一种链式存储结构，它将图中所有顶点存储在一个链表中，每个顶点对应一个链表，链表中存储与该顶点相连的所有顶点。

基于邻接表的拓扑排序算法如下：（1）初始化拓扑序列为空，入度数组为顶点数大小的数组，所有元素的值设为0。

（2）遍历邻接表，找出所有入度为0的顶点，将其加入拓扑序列，并将入度数组中相应元素的值减1。

（3）删除拓扑序列中的顶点及其所有出边，更新入度数组。

（4）重复步骤（2）和（3），直到拓扑序列不为空。

三、实训过程1. 阅读拓扑排序相关资料，了解其原理和算法实现方法。

2. 使用C++编写基于邻接矩阵的拓扑排序程序，实现图数据的构建、拓扑排序和输出拓扑序列。

3. 使用C++编写基于邻接表的拓扑排序程序，实现图数据的构建、拓扑排序和输出拓扑序列。

4. 对比两种算法的优缺点，分析其在实际应用中的适用场景。

5. 运行程序，测试不同图数据的拓扑排序结果，验证程序的正确性。

四、实训总结1. 通过本次实训，我们掌握了拓扑排序的基本原理和算法实现方法，提高了自己在数据结构和算法方面的应用能力。

散列表：存放记录的数组拓扑排序： 将一个 DAG 中所有顶点在不违反前置依赖条件规定的基础上排成线性序列的过程称为拓扑排序(44)最差情况：从一个 n 元一维数组中找出一个给定的 K ，如 果数组的最后一个元素是 K ，运行时间会相当长，因为要检查所有 n 个元素，这是算法的最差情况(15)先进先出：队列元素只能从队尾插入，从队首删除(20) (P82)增长率： 算法的增长率是指当输入的值增长时， 算法代价 的增长速率(14)优先队列：一些按照重要性或者优先级来组织的对象成 为优先队列(26)外排序： 考虑到有一组记录因数量太大而无法存放到主存中的问题， 由于记录必须驻留在外存中， 因此这些排序方法称为 外排序(32)连通分量：无向图的最大连通子图称为连通分量(40)栈：是限定仅在一端进行插入或者删除操作的线性表(19)优先队列：一些按照重要性或者优先级来组织的对象为优先队列(26)广度优先搜索：在进一步深入访问其他顶点之前，检查起点的所有相邻顶点(42) 和两个关键码值 k1 和 k2 ，如果k 1) = β k 2)，其中β 是表中的一个槽，那末就说 k 1 和 k 2对于 β在散列函数下有冲(35)类型：是指一组值的集合数据类型：一个类型和定义在这个类型上的一组操作(ADT)抽象数据类型：指数据结构作为一个软件构件的实现 数据结构：是 ADT 的实现问题：一个需要完成的任务，即对应一组输入，就有一组相应的输出函数：是输入和输出之间的一种映射关系算法：是指解决问题的一种方法或者一个过程它必须把每一次输入转化为正确的输出；一个算法应该由一系列具体步骤组成，下一步应执行 的步骤必须明确；一个算法必须由有限步组成；算法必须可以终 止。

计算机程序：被认为是使用某种程序设计语言对一个算法的具体实现程序：是算法在计算机程序设计语言中的实现或者元素构成的一个整体递归：如果一个算法调用自己来完成它的部份工作，就称这个算法是递归的渐进分析：可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开消增长率：算法的增长率是指当输入的值增长时，算法代价的增长速率P39)(p43)上限：该算法可能有的最高增长率下限：一种算法消耗某种资源的最大值(p44)线性表：是由称为元素的数据项组成的一种有限且有序的序列栈：是限定仅在一端进行插入或者删除操作的线性表队列：也是一种受限制的线性表，队列元素只能从队尾插入，从队首删除二叉检索树：是满足下面所给出条件的二叉树，该条件即二叉检索树性质：对于二叉检索树的任何一个结点，设其值为K，则该结点左子树中任意一个结点的值都小于K；该结点右子树中任意一个结点的值都大于或者等于K深度：结点M 的深度就是从根节点到M 的路径长度高度：树的高度等于最深结点的深度加1满二叉树：的每一个结点或者是一个分支结点，并恰好有两个非空子结点；或者是叶结点彻底二叉树：有严格的形状要求：从根结点起每一层从左到右填充优先队列：一些按照重要性或者优先级来组织的对象成为优先队列堆：堆由两条性质来定义。

目录课题一 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…它都要来回的翻。

拓扑排序在百度百科中的解释是：对⼀个有向⽆环图(Directed Acyclic Graph简称DAG)G进⾏拓扑排序，是将G中所有顶点排成⼀个线性序列，使得图中任意⼀对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。

转换为显⽰中⽐较容易理解的例⼦就是，在⼤学有学过课程需要学习，例如要想学习数据结构，⾸先就需要学习完C语⾔才可以，那么我们就可以将课程看成图中的点，将先学习c语⾔再学习数据结构看成是⼀条C语⾔指向数据结构的有向边。

那么我们只需要找到⼀个线性的排列顺序，使得这个顺序满⾜所有的课程的前置要求（就是要想学习这门课程，需要将该课程的所有前置课程学完）。

那么我们也⽐较容易的知道，拓扑排序并不⼀定是⼀个唯⼀的线性顺序。

在学习拓扑排序的算法之前，我们需要先了解⼏个基本概念出度：以点u为起点的边的数量是u的出度⼊度：以点u为终点的边的数量是u的⼊度对于拓扑排序⽽⾔有BFS和DFS两种算法BFS基于BFS的拓扑排序也可以分为两类：⽆前驱的顶点优先、⽆后继的顶点优先⽆前驱的顶点优先拓扑排序：1：预处理，遍历每个边，计算出所有顶点的出度和⼊度。

复杂度O(V+E)，其中包含每个顶点的初始化2：找到所有⼊度为0的顶点，放进队列，作为起点（这些点的先后顺序⽆所谓）。

如果找不到⼊度为0的点，那么这个图不是DAG，不存在拓扑排序3：弹出队⾸元素，将队⾸的所有直接邻居点（队⾸元素指向的邻居节点）的⼊度减⼀，把⼊度变为0的结点放⼊队列。

4：重复操作3，直到队列为空。

这个时候队列的所有弹出顺序就是⼀个拓扑排序。

拓扑排序⽆解的判定条件：如果队列为空时，仍旧有点没有进⼊过队列，那么这些点的⼊度都不可能为0，⼀定存在⼀个有向环⽆后继的顶点优先拓扑排序：相当于是⽆前驱的反向执⾏1：预处理，计算出所有顶点的出度和⼊度2：找到所有出度为0的顶点，放⼊队列。

如果找不到，则不存在拓扑排序3：弹出队⾸元素，将队⾸的所有直接邻居结点（指向对⼿的邻居节点）的出度减⼀，把出度为0的结点放⼊队列4：重复操作3，直到队列为空。