数据算法与拓扑

A. 数据结构拓扑排序序列

拓扑排序序列有6种。先找到第一个没有被指的，就是C1，加入序列。然后擦掉跟C1有关的边，此时C2和C3都满足没有被指，选一个，比如选C2，加入序列，擦掉和C2有关的边，这个时候可以选C3,C4,C5或C6，如此而已。

B. 拓扑排序

1、堆栈

栈是一种特殊的线性表，插入或删除栈元素的运算只能在表的一端进行，称运算的一端为栈顶，另一端称为栈底。队列也是一种特殊的线性表（基本操作都是线性操作的子集）。

特点：后进先出

栈又称为“后进先出”的线性表，简称LIFO表。

栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈。

2、有向无环图

描述含有公共子式的表达式的有效工具；

描述一项工程或系统的进行过程的有效工具。

3、一些概念

通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。

我们用一种有向图来表示这些工程、计划等，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种用顶点表示活动，用弧来表示活动间的优先关系的有向图叫做顶点表示活动的网络(ActireOnVertices)简称为AOV网。

拓扑排序：

假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…，vn称做一个拓扑序列(TopologicalOrder)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序掘亏(TopologicalSort)。

在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。

判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。

4、拓扑排序的算法思想

输入AOV网络。令n为顶点个数。

（1）在AOV网络中选一个没有直接前驱的顶点，并输出之；

（2）从图中删去该顶点,同时删去所有它发出的有向边；

重复以上步骤，直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。

5、拓扑排序算法的C语言描述

在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组。

为了避免重复检测入度为0的点，另设一栈存放所有入度为0的点。

对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O（n）；若在拓扑排序过程中不出现有向环，则判扰神每个顶点出栈、入栈和入度减1的操作在while循环语句中均执行e次，因此拓扑排序总的时间花费为O(n+e)。

6、拓扑排序算法的C语言实现

#include"stdio.h"

#defineMAX_VERTEX_NUM20

#include"conio.h"

#include"stdlib.h"

#defineSTACK_INIT_SIZE16

#defineSTACKINCREMENT5

typedef intSElemType;

typedefcharVertexType;

typedefstruct

{

SElemType*base;

SElemType*top;

intstacksize;

}SqStack;

//我们依然用邻接表来作图的存储结构

typedefstructArcNode{

intadjvex;

struct李历ArcNode*nextarc;

intinfo;

}ArcNode; //表结点类型

typedefstructVNode{

VertexTypedata;

intcount;

ArcNode*firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];//头结点

typedefstruct{

AdjListvertices; //邻接表

intvexnum,arcnum;

}ALGraph;

intInitStack(SqStack&S)

{

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(-1);

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return1;

}//InitStack

intPush(SqStack&S,SElemTypee)

{

if((S.top-S.base)>=S.stacksize)

{

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)exit(-1);

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}//if

*(S.top)=e;

S.top++;

return1;

}//Push

intPop(SqStack&S,SElemType&e)

{

if(S.top==S.base)return0;

--S.top;

e=*S.top;

return1;

}//Pop

intStackEmpty(SqStack&S)

{

if(S.top==S.base)return1;

elsereturn0;

}//StackEmpty

intLocateVex(ALGraphG,charu)

{

inti;

for(i=0;i<G.vexnum;i++)

{if(u==G.vertices[i].data)returni;}

if(i==G.vexnum){printf("Erroru! ");exit(1);}

return0;

}

voidCreateALGraph_adjlist(ALGraph&G)

{

inti,j,k,w;

charv1,v2,enter;

ArcNode*p;

printf("Inputvexnum&arcnum: ");

scanf("%d",&G.vexnum);

scanf("%d",&G.arcnum);

printf("InputVertices(以回车隔开各个数据): ");

for(i=0;i<G.vexnum;i++)

{ scanf("%c%c",&enter,&G.vertices[i].data);//注意点，解说

G.vertices[i].firstarc=NULL;

}//for

printf("InputArcs(v1,v2,w)以回车分开各个数据: ");

for(k=0;k<G.arcnum;k++)

{

scanf("%c%c",&enter,&v1);

scanf("%c%c",&enter,&v2);

//scanf("%d",&w);

i=LocateVex(G,v1);

j=LocateVex(G,v2);

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

//p->info=w;

p->nextarc=G.vertices[i].firstarc;//前插法,即每次都插入到头结点的后面

G.vertices[i].firstarc=p;

printf("Next ");

}//for

return;

}//CreateALGraph_adjlist

voidFindInDegree(ALGraph&G)

{

inti,j;

for(i=0;i<G.vexnum;i++)

{

G.vertices[i].count=0;

}//for

for(j=0;j<G.vexnum;j++)

{

//G.vertices[i].count++;

for(ArcNode*p=G.vertices[j].firstarc;p;p=p->nextarc)

G.vertices[p->adjvex].count++;

}//for

}//FindInDegree

intTopoSort(ALGraph&G)

{

SqStackS;

FindInDegree(G);

InitStack(S);

for(inti=0;i<G.vexnum;i++)

if(G.vertices[i].count==0)Push(S,i);

intcountt=0;

while(!StackEmpty(S))

{

inti,m;

m=Pop(S,i);

printf("%c",G.vertices[i].data);++countt;

for(ArcNode*p=G.vertices[i].firstarc;p;p=p->nextarc)

{ intk;

k=p->adjvex;

if(!(--G.vertices[k].count))Push(S,k);

}//for

}//while

if(countt<G.vexnum)return0;

elsereturn1;

}//TopoSort

intmain()

{

ALGraphG;

CreateALGraph_adjlist(G);

TopoSort(G);

return1;

}

7、malloc函数和realloc函数

realloc:void*realloc(void*block,size_tsize)，将block所指存储块调整为大小size，返回新块的地址。如能满足要求，新块的内容与原块一致；不能满足要求时返回NULL，此时原块不变。

C. 数据结构与算法分析

本文出自：

www点54manong点com

请尊重原创，转载请注明出处，谢谢！

什么是数据结构，为什么要学习数据结构？数据结构是否是一门纯数学课程？它在专业课程体系中起什么样的作用？我们要怎么才能学好数据结构？… 相信同学们在刚开始《数据结构》这门课的学习时，心里有着类似前面几个问题的这样那样的疑问。希望下面的内容能帮助大家消除疑惑，下定决心坚持学好这门课：

1 学习数据数据结构的意义

数据结构是计算机科学与技术专业、计算机信息管理与应用专业，电子商务等专业的基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付当前众多复杂的课题。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程、编译原理、人工智能、图视学等都是十分有益的。

2 为什么要学习数据结构

在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。例如，求解梁架结构中应力的数学模型的线性方程组，可以使用迭代算法来求解。

由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了85%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。下面所列举的就是属于这一类的具体问题。

例1：图书馆信息检索系统。当我们根据书名查找某本书有关情况的时候；或者根据作者或某个出版社查找有关书籍的时候，或根据书刊号查找作者和出版社等有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在图书馆信息检索系统中建立一张按书刊号顺序排列的图书信息表和分别按作者、书名、出版社顺序排列的索引表，如图1.1所示。由这四张表构成的文件便是图书信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定书名）对图书馆藏书信息文件进行查询。

诸如此类的还有学生信息查询系统、商场商品管理系统、仓库物资管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关系，这类数学模型可称为线性的数据结构。

例2：八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如图1.2所示（为了描述方便，将八皇后问题简化为四皇后问题）。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。

例3：教学计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边<vi，vj>，则表示课程i必须先于课程j进行。由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。

学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。

3数据结构课程的内容

数据结构与数学、计算机硬件和软件有十分密切的关系，它是介于数学、计算机硬件和计算机软件之间的一门计算机专业的核心课程，是高级程序设计语言、操作系统、编译原理、数据库、人工智能、图视学等课程的基础。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。

数据结构课程重在讨论软件开发过程中的方案设计阶段、同时设计编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”，如图1.3所示。

数据结构的核心技术是分解与抽象。通过分解可以划分出数据的三个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合使我们将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。熟练地掌握这两个过程是数据结构课程在专业技能培养方面的基本目标。

结束语：数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。20世纪60年代中期，美国的一些大学开始设立有关课程，但当时的课程名称并不叫数据结构。1968年美国唐.欧.克努特教授开创了数据结构的最初体系，他所着的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的着作。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从70年代中期到80年代，各种版本的数据结构着作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。

D. 数据结构拓扑排序序列

对一个有向无环图简称G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u，v>∈E(G)，则u在线性序列中出现在v之前。通丛友常，这样的线性序列称为满足拓扑次序的序列，简称野友拓扑序列。

由拓扑序列的生成方法的出图中三种不同拓扑排序的序列：第一种：c1、c2、c4、c3、c5、c6，第二种：c1、c2、c4、c3、c6、c5，第三种：c1、c3、c2、c4、c5、c6。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

参考资料来源：网络-拓扑排序

E. 什么是拓扑关系怎样理解拓扑关系也是一种数据，拓扑关系对空间数据库建设有何帮助

英文
topology
的音译.
拓扑学就是以空间几何的形式来表现事物内部的结构,原理,工作状况等.
比如你的计算机吧,学过搜索算法吧(广度优先(breath-first)和深度优先(depth-first,
不知道中文译的对不对)算法).你在分析的时候不是把所有的状态画败前成一个树状表,然后来看一步步怎御枯薯样查找的么.这就是运用拓扑逻辑的方法.
当然,从这里你就可以看到,拓扑都在处理离散的状态.
说白了,系统逻辑流程图也是拓扑图.
听起镇者很深奥,很玄,其实常常用到

F. 数据结构中有关拓扑排序的相关知识

将入度为0的结点入队，删除后同时将所有相邻顶点的先决条件减一。当某个顶点的计数为0时，将它入队。这是关键思想。

G. 算法与数据结构，C语言版本的拓扑排序问题求助。

如果可以,你能把程序写上来.我可以给你讲.

H. 数据结构中 关于图拓扑排序算法 有个地方不太明白 希望能得到解答

我知道你哪里不明白了，你没看见上面的for循环，1，如果不为0，则不执行if了，但执行for循环。2，执行for循环的目的就是把所有的入度减1，减为0的入栈。

I. 数据结构课设 题目：拓扑排序算法

//首先是用邻接表表视图,下面是邻接表的数据结构定义
const int MaxVertexNum = {图的最大顶点数，要大于等于具体图的顶点数n};
const int MaxEdgetNum = {图的最大边数，要大于等于具体图的边数e};

typedef VertexType vexlist[MaxVertexNum]; //定义vexlist为存储顶点信息的数组类型

struct edgenode //定义邻接表中的边结点类型
{
int adjvex; //邻接点域
int weight; //权值域
edgenode* next;//指向下一个边结点的链域
};

typedef edgenode* adjlist[MaxVertexNum]; //定义adjlist为存储n个表头指针的数组类型

//通过从键盘上输入的n个顶点信息和e条有向边信息建立顶点数组GV和邻接表GL
void Create2(vexlist GV, adjlist GL, int n, int e)
{
int i,j,k;
//建立顶点数组
cout<<"输入"<<n<<"个顶点的值："<<endl;
four(i = 0; i<n; i++)
cin>>GV[i];
//初始化邻接表
for(i=0; i<n; i++)
GL[i] = NULL;
//建立邻接表
cout<<"输入"<<e<<"条边："<<endl;
for(k=1; k<=e; k++)
{
//输入一条边<i,j>
cin>>i>>j;
//分配新结点
edgenode* p = new edgenode;
//将j值赋给新结点的邻接点域
p->adjvex = j;
//将新结点插入到邻接表表头
p->next = GL[i];
GL[i] = p;
}
}

//对邻接表GL表示的有n个顶点的有向图拓扑排序
void TopoSort(adjlist GL, int n)
{
int i,j,k,top,m=0; //m统计拓扑排序中的顶点数
edgenode* p;
//定义存储图中每个顶点入度的一维整型数组d
int* d = new int[n];
//初始化数组d中每个元素值为0
for(i=0; i<n; i++)
d[i] = 0;
//利用数组d记录每个顶点的入度
for(i = 0; i < n; i++)
{
p = GL[i];
while(p != NULL)
{
j = p->adjvex;
d[j]++;
p = p->next;
}
}
//初始化用于链接入度为0的栈顶指针top为-1
top = -1;
//建立初始栈
for(i = 0; i < n; i++)
if(d[i] == 0)
{
d[i] = top;
top = i;
}
//每循环一次删除一个顶点及所有出边
while(top != -1)
{
j = top; //j的值为一个入度为0的顶点序号
top = d[top]; //删除栈顶元素
cout<<j<<' '; //输出一个入度为0的顶点
m++; //输出顶点个数加1
p = GL[j]; //p指向邻接点表的第一个结点
while(p != NULL)
{
k = p->adjvex;
d[k]--;
if( d[k] == 0) //把入度为0的元素进栈
{
d[k] = top;
top = k;
}
p = p->next;
}
}
cout<<endl;
if(m<n)
cout<<"存在回路！"<<endl;
delete []d;
}

J. 在拓扑排列算法中,要用到那些基本的数据结构

拓扑排序吗，这是图论里面的一个基础的算法，具体说要用到什知卖么数据结构，我会告诉你没有吗？

如果硬要说的话，可能包括图的存储，也就是邻接矩阵或者邻接表搭型逗。

然后实现拓扑排序有两种方法：

1. 不断找到租旅入度为0的点，然后输出。

2. 深搜。

如果你感兴趣的话，我可以帮上述两种方法的代码都给你。