实用标准
拓扑排序
[基本要求] 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。 [编程思路]
首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（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 \
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) //返回数组的位置
文案大全