大数据结构拓扑排序实验报告材料.docx
- 文档编号:11563815
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:11
- 大小:85.36KB
大数据结构拓扑排序实验报告材料.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"); } [实验数据与结果] 测试数据: 实验结果
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 拓扑 排序 实验 报告 材料