注册 登录
编程论坛 数据结构与算法

拓扑排序...求大神指正

马群 发布于 2012-12-19 13:57, 422 次点击
刚才不小心发到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 编辑 ]
3 回复
#2
Ayiis2012-12-23 15:47
不明帮顶
#3
马群2012-12-23 16:10
回复 2楼 Ayiis
不知道为什么真心问个问题木有人理我...
#4
Ayiis2012-12-23 21:33
回复 3楼 马群
程序猿没时间是出了名的。。除非是能引起他们兴趣的话题,或者爱好,而且这个区人气明显不如C区,但是C区又长时间被ACM和菜鸟霸占,所以。。。

[ 本帖最后由 Ayiis 于 2012-12-23 21:34 编辑 ]
1