C实现有向图的拓扑排序出现问题

C语言 码拜 4年前 (2015-11-27) 193次浏览

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 20
typedef char VertexType;
typedef struct node  //边表节点
{
int adjvex;
struct node *next;
}EdgeNode;
typedef struct  //顶点表节点
{
int in;     //入度值
VertexType vertex;
EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxSize];
typedef struct
{
AdjList adjlist;
int n,e;
}ALGraph;
//链队列
typedef struct Node{
int data;
struct Node *next;
} QNode;
typedef struct {
QNode *front;
QNode *rear;
}LQueue;
LQueue *Creat_LQueue(){             //创建一个链队列
QNode *r=(QNode *)malloc(sizeof(QNode));
LQueue *s=(LQueue *)malloc(sizeof(LQueue));
r->next=NULL;
s->front=s->rear=r;
return s;
}
void InQueue(LQueue *s,int x){           //入队列
QNode *r;
r=(QNode *)malloc(sizeof(QNode));
r->data=x;
r->next=NULL;
s->rear->next=r;
s->rear=r;
}
int Empty_LQueue(LQueue *s){           //判断队列能否为空
if(s->front==s->rear)
return 1;
else
return 0;
}
int Out_LQueue(LQueue *s){              //出队列
int x;
QNode *r;
if(Empty_LQueue(s)==1)
return 0;
else{
r=s->front->next;
s->front->next=r->next;
x=r->data;
free(r);
if(s->front->next==NULL)
s->rear=s->front;
return x;
}
}
void Creat(ALGraph *G){                         //以邻接表的形式创建有向图
int i,j,k;
EdgeNode *s;
printf(“读入定点数和边数”);
scanf(“%d,%d”,&G->n,&G->e);
for(i=0;i<G->n;i++)
{
fflush(stdin);
printf(“建立顶点表”);
G->adjlist[i].vertex=getchar();
G->adjlist[i].firstedge=NULL;
}
printf(“建立边表\n”);
for(k=0;k<G->e;k++)
{
printf(“读入(vi-vj)顶点对应序号”);
scanf(“%d,%d”,&i,&j);
s=(EdgeNode* )malloc(sizeof(EdgeNode));
s->adjvex=j;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
}
for(i=0;i<G->n;i++){
printf(“请输入%d入度数:”,i);
scanf(“%d”,&G->adjlist[i].in);
}
}
void print(ALGraph *G){                     //以邻接表的形式输出有向图
int i;
for(i=0;i<G->n;i++){
printf(“%d->”,i);
while(G->adjlist[i].firstedge!=NULL){
printf(“%d->”,G->adjlist[i].firstedge->adjvex);
G->adjlist[i].firstedge=G->adjlist[i].firstedge->next;
}
printf(“\n”);
}
}
void TopoSort(ALGraph *G){
LQueue *Q;
int i,j;
EdgeNode *p;
Q=Creat_LQueue();
for(i=0;i<G->n;i++){
if(G->adjlist[i].in==0){
InQueue(Q,i);
}
}
while(Empty_LQueue(Q)!=1){
printf(“%d “,Out_LQueue(Q));
for(i=0;i<G->n;i++){
p=G->adjlist[i].firstedge;
while(p!=NULL){
j=p->adjvex;
G->adjlist[j].in–;
if(G->adjlist[j].in==0)
InQueue(Q,j);
p=p->next;
}
}
}
}
void main(){
ALGraph *G;
printf(“–开始创建图–\n”);
G=(ALGraph* )malloc(sizeof(ALGraph));
Creat(G);
printf(“–以邻接表的形式输出图–\n”);
print(G);
printf(“–实现拓扑排序–\n”);
TopoSort(G);
}

解决方案:60分
将复杂数据结构的整个内容在处理它的每一步使用一小段代码按本人很容易理解的格式输出,非常有助于调试!或可以说是“基础设施”.
代码功能归根结底不是别人帮本人看或讲解或注释出来的;而是被本人静下心来花足够长的时间和精力亲自动手单步或设断点或对执行到某步获得的中间结果显示或写到日志文件中一步一步分析出来的。
提醒:再牛×的老师也无法代替学生本人领悟和上厕所!
单步调试和设断点调试(VS IDE中编译连接通过以后,按F10或F11键单步执行,按Shift+F11退出当前函数;在某行按F9设断点后按F5执行停在该断点处。)是程序员必须掌握的技能之一。
解决方案:40分
建议学会本人调试,逐步运行程序,通过各种窗口观察分析

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明C实现有向图的拓扑排序出现问题
喜欢 (0)
[1034331897@qq.com]
分享 (0)