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

拓扑排序 基本要求 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。编程思路 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，几乎和图的创建一样，图的顶点定义时加入int indegree，关键在于indegree的计算，而最好的就是在创建的时候就算出入度，（没有采用书上的indegree【】数组的方法，那样会增加一个indegree算法，而是在创建的时候假如一句计数的代码(G.verticesj.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 VNodeint indegree; char data10; /*顶点信息*/ ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针*/VNode,AdjListMAX_VERTEX_NUM;/*定义图的结构*/typedef struct AdjList vertices; int vexnum,arcnum; /*图的当前顶点数和弧数*/ int kind; /*图的类型标志*/Graph;/*定义栈的结构*/typedef structSElemType *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 #includemalloc.h#include tuopupaixuhead.h#include stdlib.h#include string.hbool visitedMAX_VERTEX_NUM;/* 顶点定位，返回位序 */int LocateVex(Graph G,char *name)int i;for(i=1;i=G.vexnum;i+)if(strcmp(name,G.verticesi.data)=0) /返回数组的位置return i;return -1;/* 创建有向图 */void CreateGraph(Graph &G)ArcNode *p;char name110,name210;int i,j,k;printf( 请输入顶点数,按回车键结束：);scanf(%d,&G.vexnum); printf( 请输入弧数,按回车键结束：);scanf(%d,&G.arcnum);printf( 请依次输入顶点名（用空格分开且字符小于10）,按回车键结束：n); printf( );for(i=1;i=G.vexnum;i+) /初始化 scanf(%s,G.verticesi.data); G.verticesi.firstarc=NULL; G.verticesi.indegree=0; /度数均初始化为0 printf(nnnn); printf( 输入小提示n); printf( &1 为避免输入遗漏，最好从选择任意一点，输入所有相邻边n); printf( &2 输入边时格式(用空格分开，即格式为顶点（空格）顶点（空格）n); printf( 输入小提示nnnn);for(k=0;kadjvex=j; /插入到邻接表中，注意此处为逆向插入到单链表中 p-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p; /* 初始化栈 */Status InitStack(Stack &s) /创建一个空栈s.base=(int*)malloc(STACKSIZE*sizeof(int);if(!s.base) return (OVERFLOW);s.top=s.base;s.stacksize=STACKSIZE;return OK;/* 判空 */Status EmptyStack(Stack s)if(s.base=s.top) return 1;else return 0;/* 压栈 */Status Push(Stack &s,int e)if(s.top-s.base)s.stacksize) s.base=(SElemType*)realloc(s.base,(STACKSIZE+STACKINCREMENT)*sizeof(SElemType); if(!s.base) return(OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;/* 出栈 */Status Pop(Stack &s,int &e) e=*-s.top; return OK;/* 拓扑排序 */Status TopologicalSort(Graph G) /拓扑排序函数int i,j,k,e;int count=0; /用来统计顶点的个数Stack S; /定义一个栈，用来保存入度为0的顶点InitStack(S); /初始化栈for(i=1;inextarc) /找与第j个顶点的邻接顶点，并将其入度减1 k=p-adjvex; -(G.verticesk.indegree); if(G.verticesk.indegree=0) /如果入度为0,就入栈 Push(S,k); return OK;if(countG.vexnum) /count小于顶点的个数时候，说明有环，不符合拓扑排序的要求 printf(n不是有向无环图!n); return ERROR; /退出 主文件：#include #includemalloc.h#include tuopupaixuhead.h#include stdlib.h#include string.h/* 界面控制 */void main()Graph G; printf(n# 拓扑排序 #n); printf(n $n); printf(n); CreateGraph(G); printf(各点入度分布如下：nn); for(int i=1;i=G