拓扑排序-数据结构课程设计|数据结构课程设计
T /*Name:拓扑排序Author:wujilinDescription:用邻接表构造图 然后进行拓扑排序注意 今天调试时候出现了一个问题 以前没出现过的就是 用* 与不用 以前我不管有没有返回值 我都用但是没出现问题 今天调试这个程序 就是因为这个小问题 花费很长时间以后一定要主要这一点 不要不管三七二十一 都用* 有时候会造成原数据破坏 利用被破坏的值 在进行运算 结果可想而知 所以 如果没返回值时一般不要用 不要因为图个方便一律用 那样不好 切记Date: 22-07-06 20:25Copyright:wujilin*/
#include#include#define MAX_VEXTEX_NUM 20#define M 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0
typedef int ElemType;typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;
typedef struct VNode{int data;ArcNode *firstarc;}VNode,AdjList[MAX_VEXTEX_NUM];
typedef struct{AdjList vertices;int vexnum, arcnum;}ALGraph;
typedef struct //构件栈{ElemType *base;ElemType *top;int stacksize;}SqStack;
void InitStack(SqStack *); //函数声明int Pop(SqStack *, ElemType *);void Push(SqStack *,ElemType );int StackEmpty(SqStack *);void CreatGraph(ALGraph *);void FindInDegree(ALGraph , int * );void TopologicalSort(ALGraph );
void InitStack(SqStack *S)//初始化栈{S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S->base){printf("memory allocation failed, goodbye");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;}
int Pop(SqStack *S,ElemType *e)//出栈操作{
if(S->top==S->base){return ERROR;}*e=*--S->top;//printf("%d\n",e);// return e;return 0;}
void Push(SqStack *S,ElemType e)//进栈操作{if(S->top-S->base>=S->stacksize){S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S->base){printf("memory allocation failed, goodbye");exit(1);}S->top = S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top++=e;
}
int StackEmpty(SqStack *S)//判断栈是否为空{if(S->top==S->base)return OK;elsereturn ERROR;}
void CreatGraph(ALGraph *G)//构件图{int m, n, i;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请输入存在边的两个顶点的序号:");scanf("%d%d",&n,&m);while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum){printf("输入的顶点序号不正确 请重新输入:");scanf("%d%d",&n,&m);}
p = (ArcNode*)malloc(sizeof(ArcNode));if (p == NULL){printf("memory allocation failed,goodbey");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;}
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[M];int i, k, n;int count = 0;ArcNode *p;SqStack S;
FindInDegree(G, indegree);InitStack(&S);
for (i = 1; i <= G.vexnum; i++){printf("第%d个点的入度为%d \n", i, indegree[i]);}printf("\n");for ( i = 1; i <= G.vexnum; i++){if (!indegree[i])Push(&S,i);}
printf("进行拓扑排序输出顺序为:"); //输出结果while(!StackEmpty(&S)){Pop(&S,&n);printf("%4d",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);}}
}printf("\n");if (count < G.vexnum){printf("出现错误\n");}else{printf("排序成功\n");}}int main(void) //主函数{ALGraph G;
CreatGraph(&G);TopologicalSort(G);
system("pause");return 0;}
