毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 课程设计 >> 正文

拓扑排序-数据结构课程设计

更新时间:2007-10-20:  来源:毕业论文
拓扑排序-数据结构课程设计|数据结构课程设计

T /*
Name:拓扑排序
Author:wujilin
Description:用邻接表构造图 然后进行拓扑排序
注意  今天调试时候出现了一个问题 以前没出现过的
就是 用* 与不用  以前我不管有没有返回值 我都用
但是没出现问题  今天调试这个程序 就是因为这个小问题 花费很长时间
以后一定要主要这一点 不要不管三七二十一 都用*  有时候会造成原数据
破坏  利用被破坏的值 在进行运算  结果可想而知  所以 如果没返回值时
一般不要用  不要因为图个方便一律用 那样不好 切记
Date: 22-07-06 20:25
Copyright:wujilin
*/

#include<stdio.h>
#include<stdlib.h>
#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;
else
return 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;}

拓扑排序-数据结构课程设计下载如图片无法显示或论文不完整,请联系qq752018766
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©lwfree.cn 六维论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。