top_sort.c

该文件夹中包含了大部分经典的算法的源程序代码

/* file name: top_sort.c */
/*拓扑排序*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX_V 100  /*最大节点数*/
#define TRUE 1
#define FALSE 0

/*定义数据结构*/
typedef struct node_tag {
	int vertex;
	struct node_tag *link;
} Node;

Node *adjlist[MAX_V+1];  /*宣告邻接表*/
int visited[MAX_V+1];  /*记录顶点是否已访问*/
int Top_order[MAX_V+1];
int N;
int place;


void build_adjlist();
void show_adjlist();
void topological();
void top_sort(int);
Node *searchlast(Node *);

void main()
{
	int i;

	build_adjlist(); /*以邻接表表示图*/
	show_adjlist();   /*显示表之数据*/
	topological();      /*图之踪向优先搜索，以顶点1为启始顶点*/
	puts("\n------Toplogical order sort------");
	for ( i = 0; i < N; i++ )
		printf("V%d ",Top_order[i]);
}

void build_adjlist()
{
	FILE *fptr;
	Node *node,*lastnode;
	int vi,vj;

	fptr = fopen("top_sort.dat","r");
	if ( fptr == NULL )
	{
		perror("top_sort.dat");
		exit(0);
	}

	/*读取节点总数*/
	fscanf(fptr,"%d",&N);
	for ( vi = 1; vi <= N; vi++)
	{
		/*设定数组及各表启始值*/
		adjlist[vi] = (Node *)malloc(sizeof(Node));
		adjlist[vi]->vertex = vi;
		adjlist[vi]->link = NULL;
	}

	/*读取节点数据*/
	while( fscanf(fptr,"%d %d",&vi,&vj) != EOF)
	{
		node = (Node *)malloc(sizeof(Node));
		node->vertex = vj;
		node->link = NULL;
		if ( adjlist[vi]->link == NULL)
			adjlist[vi]->link = node;
		else
		{
			lastnode = searchlast(adjlist[vi]);
			lastnode->link = node;
		}
	}
	fclose(fptr);
}

/*显示各邻接表之数据*/
void show_adjlist()
{
	int v;
	Node *ptr;

	puts("Head    adjacency nodes");
	puts("------------------------------");
	for (v = 1; v <= N; v++)
	{
		printf("V%d ",adjlist[v]->vertex);
		ptr = adjlist[v]->link;
		while ( ptr != NULL )
		{
			printf("--> V%d ",ptr->vertex);
			ptr = ptr->link;
		}
		printf("\n");
	}
}

/*图之踪向优先搜索*/
void topological()
{
	int v;

	for ( v = 1;v <= N; v++)
		visited[v] = FALSE;
	place = N;
	for ( v = 1; v <= N; v++ )
		if ( !visited[v] )
			top_sort(v);
}

void top_sort(int k)
{
	Node *ptr;
	int w;

	visited[k] = TRUE;           /*设定v顶点为已访问过*/
	ptr = adjlist[k]->link;     /*访问v邻接顶点*/
	while ( ptr != NULL )
	{
		w = ptr->vertex; /* w 为v的直接后继 */ 
		if ( !visited[w] )
			top_sort(w);
		ptr = ptr->link;
	}
	Top_order[--place] = k;
}

/*搜索表最后节点函数*/
Node *searchlast( Node *linklist )
{
	Node *ptr;

	ptr = linklist;
	while ( ptr->link != NULL ) ptr = ptr->link;
	return ptr;
}