大数据结构拓扑排序实验报告材料.docx
《大数据结构拓扑排序实验报告材料.docx》由会员分享，可在线阅读，更多相关《大数据结构拓扑排序实验报告材料.docx（11页珍藏版）》请在冰点文库上搜索。
大数据结构拓扑排序实验报告材料
拓扑排序
[基本要求]用邻接表建立一个有向图的存储结构。
利用拓扑排序算法输出该图的拓扑排序序列。
[编程思路]
首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex（GraphG,char*name），以便后来的遍历操作，几乎和图的创建一样，图的顶点定义时加入intindegree，关键在于indegree的计算，而最好的就是在创建的时候就算出入度，（没有采用书上的indegree【】数组的方法，那样会增加一个indegree算法，而是在创建的时候假如一句计数的代码（G.vertices[j].indegree）++;）最后调用拓扑排序的算法，得出拓扑序列。
[程序代码]
头文件：
#defineMAX_VERTEX_NUM30
#defineSTACKSIZE30
#defineSTACKINCREMENT10
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
#defineTRUE1
#defineFALSE0
typedefintStatus;
typedefintInfoType;
typedefintStatus;
typedefintSElemType;
/*定义弧的结构*/
typedefstructArcNode{
intadjvex;/*该边所指向的顶点的位置*/
structArcNode*nextarc;/*指向下一条边的指针*/
InfoTypeinfo;/*该弧相关信息的指针*/
}ArcNode;
/*定义顶点的结构*/
typedefstructVNode{
intindegree;
chardata[10];/*顶点信息*/
ArcNode*firstarc;/*指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM];
/*定义图的结构*/
typedefstruct{
AdjListvertices;
intvexnum,arcnum;/*图的当前顶点数和弧数*/
intkind;/*图的类型标志*/
}Graph;
/*定义栈的结构*/
typedefstruct
{
SElemType*base;
SElemType*top;
intstacksize;
}Stack;
/*顶点定位*/
intLocateVex（GraphG,char*name）;
/*创建有向图*/
voidCreateGraph（Graph&G）;
/*拓扑排序*/
StatusTopologicalSort（GraphG）;
/*初始化栈*/
StatusInitStack（Stack&s）;
/*判断空*/
StatusEmptyStack（Stacks）;
/*压栈*/
StatusPush（Stack&s,inte）;
/*出栈*/
StatusPop（Stack&s,int&e）;
实现文件：
#include
#include"malloc.h"
#include"tuopupaixuhead.h"
#include"stdlib.h"
#include"string.h"
boolvisited[MAX_VERTEX_NUM];
/***********************************************************
*顶点定位，返回位序*
***********************************************************/
intLocateVex（GraphG,char*name）
{
inti;
for（i=1;i<=G.vexnum;i++）
if（strcmp（name,G.vertices[i].data）==0）//返回数组的位置
returni;
return-1;
}
/***********************************************************
*创建有向图*
***********************************************************/
voidCreateGraph（Graph&G）
{
ArcNode*p;
charname1[10],name2[10];
inti,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.vertices[i].data）;
G.vertices[i].firstarc=NULL;
G.vertices[i].indegree=0;//度数均初始化为0
}
printf（"\n\n\n\n"）;
printf（"………………………………………输入小提示………………………………………\n"）;
printf（"&&&&1为避免输入遗漏，最好从选择任意一点，输入所有相邻边\n"）;
printf（"&&&&2输入边时格式（用空格分开，即格式为顶点（空格）顶点（空格））\n"）;
printf（"………………………………………输入小提示………………………………………\n\n\n\n"）;
for（k=0;k{
printf（"请输入相邻的两个顶点，按回车键结束：
"）;
scanf（"%s%s",name1,name2）;
i=LocateVex（G,name1）;
j=LocateVex（G,name2）;
（G.vertices[j].indegree）++;//每次作为弧的邻接点，则度数加1
p=（ArcNode*）malloc（sizeof（ArcNode））;//申请边节点
p->adjvex=j;//插入到邻接表中，注意此处为逆向插入到单链表中
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}
}
/***********************************************************
*初始化栈*
***********************************************************/
StatusInitStack（Stack&s）//创建一个空栈
{
s.base=（int*）malloc（STACKSIZE*sizeof（int））;
if（!
s.base）
return（OVERFLOW）;
s.top=s.base;
s.stacksize=STACKSIZE;
returnOK;
}
/***********************************************************
*判空*
***********************************************************/
StatusEmptyStack（Stacks）
{
if（s.base==s.top）
return1;
else
return0;
}
/***********************************************************
*压栈*
***********************************************************/
StatusPush（Stack&s,inte）
{
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;
returnOK;
}
/***********************************************************
*出栈*
***********************************************************/
StatusPop（Stack&s,int&e）
{
e=*--s.top;
returnOK;
}
/***********************************************************
*拓扑排序*
***********************************************************/
StatusTopologicalSort（GraphG）//拓扑排序函数
{
inti,j,k,e;
intcount=0;//用来统计顶点的个数
StackS;//定义一个栈，用来保存入度为0的顶点
InitStack（S）;//初始化栈
for（i=1;i<=G.vexnum;++i）
if（G.vertices[i].indegree==0）//若第i个顶点的入度为0，i表示顶点在图中的位置
Push（S,i）;//将第i个顶点入栈
while（!
EmptyStack（S））
{
Pop（S,e）;//将为入度0的顶点位置出栈
j=e;
count++;//统计顶点的个数
printf（"%s",G.vertices[j].data）;//输出入度为0的顶点
ArcNode*p;
for（p=G.vertices[j].firstarc;p;p=p->nextarc）//找与第j个顶点的邻接顶点，并将其入度减1
{
k=p->adjvex;
--（G.vertices[k].indegree）;
if（G.vertices[k].indegree==0）//如果入度为0,就入栈
Push（S,k）;
}
}
returnOK;
if（count{
printf（"\n不是有向无环图!
\n"）;
returnERROR;//退出
}
}
主文件：
#include
#include"malloc.h"
#include"tuopupaixuhead.h"
#include"stdlib.h"
#include"string.h"
/***********************************************************
*界面控制*
***********************************************************/
voidmain（）{
GraphG;
printf（"\n#################################拓扑排序#################################\n"）;
printf（"\n$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n"）;
printf（"\n"）;
CreateGraph（G）;
printf（"各点入度分布如下：
\n\n"）;
for（inti=1;i<=G.vexnum;i++）{//输出顶点的度数
printf（"第%d个顶点%s的度数是%d\n",i,G.vertices[i].data,G.vertices[i].indegree）;}
printf（"\n\n\n"）;
printf（"有向图所有顶点的拓扑排序:
\n"）;
TopologicalSort（G）;
printf（"\n"）;
}
[实验数据与结果]
测试数据：
实验结果
升级会员 