数据结构拓扑排序实验报告.docxVIP

拓扑排序 [基本要求] 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。[编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（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 0typedef 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 stdio.h#includemalloc.h#include tuopupaixuhead.h#include stdlib.h#include string.hbool 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) //返回数组的位置return i;return -1;}/************************************************************创建有向图 ***********************************