拓扑排序...求大神指正
刚才不小心发到C语言那里去了...情况是这样的:课程设计和期末考试编排在一起了所以各种仓促,代码写的可烂了但是老师那关至少是通过了
有几个问题希望请教一下大神们:
1.将源程序的顶点名称改成任意输入的,就说可以输字符什么的,甚至是中文;
2.是不是代码写的太累赘了...
3.可不可以把显而易见的环直接跳过,比如顶点数和边数都是2的情况,省去输入各条边的过程?
程序代码：#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 50 //设图的最大顶点数为50
#define STACK_SIZE 50 //栈存储空间初始分配量
typedef struct ArcNode //弧结点
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode; //对表节点的定义
typedef struct VNode//顶点结构
{
int data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM]; //头结点
typedef struct //图结构
{
AdjList vertices; //应包含邻接表
int vexnum,arcnum; //图中当前的顶点数与弧数
}ALGraph; //邻接图的信息
typedef struct
{
int *base; //栈构造之前的指针
int *top; //定义栈顶指针
int stacksize; //定义栈所分配的存储空间
}SqStack; //堆栈结构体
void InitStack( SqStack *S) //初始化堆栈
{
S->base=(SqStack *)malloc(STACK_SIZE *sizeof(SqStack));
if(!S->base) //如果出现存储空间分配失败的情况
exit(1);
S->top=S->base; //栈空
S->stacksize=STACK_SIZE; //把栈的空间设为STACK_SIZE
}
void Push(SqStack *S,int e) //这里是进行进栈操作,插入元素e为新的栈顶元素
{
if(S->top-S->base>=S->stacksize) //如果存储空间分配失败
exit(1);
*(S->top++)=e;
}
void Pop(SqStack *S,int *e) //出栈
{
if(S->top==S->base)
exit(1);
*e=*(--S->top);
}
int StackEmpty(SqStack *S) //判断栈是否为空
{
if(S->base==S->top) //栈不为空,则删除S的栈顶元素,并返回1
return 1;
else
return 0;
}
void CreatGraph(ALGraph *G) //建立有向图的邻接表
{
int i,n,m;
ArcNode *p;
printf("请输入顶点数和边数:"); //输入顶点数和边数
scanf("%d %d",&G->vexnum,&G->arcnum);
for(i=1;i<=G->vexnum;i++) //初始图的表头结点
{
G->vertices[i].data=i;//输入顶点的值
G->vertices[i].firstarc=NULL; //初始化指针
}
for(i=1;i<=G->arcnum;i++)
{ //把弧存入邻接表
printf("\n请输入第%d条弧:",i);
scanf("%d %d",&n,&m); //输入两个定点之间的弧
while(n<0||n>G->vexnum||m<0||m>G->vexnum)
{
printf("\n错误,请重新输入:");
scanf("%d %d",&n,&m); //满足条件的顶点 ,n,m之间有边
}
p=(ArcNode *)malloc(sizeof(ArcNode)); //为邻接表结点申请空间
if(!p)
exit(1);
p->adjvex=m;
p->nextarc = G->vertices[n].firstarc; //链表的操作
G->vertices[n].firstarc=p;
}
printf("邻接表为:\n");
for(i=1;i<=G->vexnum;i++) //输出此邻接表
{
printf("%d",G->vertices[i].data); //头结点
for(p=G->vertices[i].firstarc;p;p=p->nextarc)
printf("%3d",p->adjvex); //表结点
printf("\n");
}
}
void FindInDegree(ALGraph G,int indegree[]) //求入度
{
int i;
for(i=1;i<=G.vexnum;i++)
indegree[i]=0; //初始为0
for(i=1;i<=G.vexnum;i++)
{ //遍历邻接表，求入度
while(G.vertices[i].firstarc)
{
indegree[G.vertices[i].firstarc->adjvex]++; //弧头元素入度加一
G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort(ALGraph G) //拓扑排序
{
int indegree[MAX_VERTEX_NUM];
int i,k,n;
int count=0;
ArcNode *p;
SqStack S;
FindInDegree(G,indegree); //用数组名
InitStack(&S);
for(i=1;i<=G.vexnum;i++)
{
if(!indegree[i]) //入度为0，进栈
Push(&S,i);
}
printf("拓扑排序为 \n");
while(!StackEmpty(&S)) //栈不空，出栈并输出结果
{
Pop(&S,&n);
printf("%d ",G.vertices[n].data);
count++; //累加输出点个数
for(p=G.vertices[n].firstarc;p!=NULL;p=p->nextarc)
{ //邻接表的优点，计算入度的改变
k=p->adjvex;
if(!(--indegree[k])) /////入度自减的过程
Push(&S,k); //入度为0，进栈
}
}
if(count<G.vexnum) //count充当计数器
printf("该图有环\n");
else
printf("\n排序成功!");
}
int main()
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
getchar();
getch();
return 0;
}
[ 本帖最后由 马群 于 2012-12-19 21:57 编辑 ]
