内容发布更新时间 : 2024/5/18 9:56:54星期一 下面是文章的全部内容请认真阅读。

实用标准

拓扑排序

[基本要求] 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。 [编程思路]

首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，几乎和图的创建一样，图的顶点定义时加入int indegree，关键在于indegree的计算，而最好的就是在创建的时候就算出入度，（没有采用书上的indegree【】数组的方法，那样会增加一个indegree算法，而是在创建的时候假如一句计数的代码(G.vertices[j].indegree)++;）最后调用拓扑排序的算法，得出拓扑序列。

[程序代码]

头文件：

#define MAX_VERTEX_NUM 30 #define STACKSIZE 30 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int InfoType; typedef int Status; typedef int SElemType;

/* 定义弧的结构*/

typedef struct ArcNode{

int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边的指针*/ InfoType info; /*该弧相关信息的指针*/

文案大全

实用标准

}ArcNode;

/*定义顶点的结构*/ typedef struct VNode{

int indegree;

char data[10]; /*顶点信息*/

ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针*/ }VNode,AdjList[MAX_VERTEX_NUM];

/*定义图的结构*/ typedef struct { AdjList vertices;

int vexnum,arcnum; /*图的当前顶点数和弧数*/ int kind; /*图的类型标志*/ }Graph;

/*定义栈的结构*/ typedef struct {

SElemType *base; SElemType *top; int stacksize; }Stack;

/*顶点定位*/

int LocateVex(Graph G,char *name);

/*创建有向图*/

void CreateGraph(Graph &G);

文案大全

实用标准

/*拓扑排序*/

StatusTopologicalSort(Graph G);

/*初始化栈*/

Status InitStack(Stack &s) ;

/*判断空*/

Status EmptyStack(Stack s); /*压栈*/

Status Push(Stack &s,int e); /*出栈*/

Status Pop(Stack &s,int &e);

实现文件：

#include #include\

#include \#include \#include \

bool visited[MAX_VERTEX_NUM];

/*********************************************************** * 顶点定位，返回位序 * ***********************************************************/ int LocateVex(Graph G,char *name) {

int i;

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

if(strcmp(name,G.vertices[i].data)==0) //返回数组的位置

文案大全