testoftopologysort.c

功能基本实现

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

#define SIZE 8
#define DEBUG 1
int staticM[SIZE][SIZE]={{1,1,1,0,0,0,1,0},
						{0,1,0,0,0,0,1,0},
						{0,0,1,0,0,1,0,0},
						{0,1,0,1,1,0,1,0},
						{0,0,0,0,1,1,0,1},
						{0,0,0,0,0,1,0,0},
						{0,0,0,0,0,0,1,0},
						{0,0,0,0,0,0,0,1},
						};

void    topologySort(int** inMatrix,int* topSeqArr,int row,int col);

void main()
{
	int** testMatrix;
	int* topSeq;

	int len=SIZE;
	int i,j;

	testMatrix=(int**)malloc(sizeof(int*)*len);
	for(i=0;i<len;i++)
		testMatrix[i]=(int*)malloc(sizeof(int)*len);

	topSeq=(int*)malloc(sizeof(int)*len);

	if(testMatrix==NULL||topSeq==NULL)
	{
		printf("testMatrix==NULL\n");
		return;
	}

	for(i=0;i<len;i++)
		for(j=0;j<len;j++)
			testMatrix[i][j]=staticM[i][j];
	
	topologySort(testMatrix,topSeq,len,len);

}

void    topologySort(int** inMatrix,int* topSeqArr,int row,int col)
{
	int i,j;
	int* labeledRow;
	int labeledNum;
	unsigned noFirstNode;
	
	if(inMatrix==NULL||topSeqArr==NULL)
	{
		printf("in topologySort ,pass in matrix or topSeqArr is null\n");
		return;
	}
	
	labeledRow=(int*)malloc(sizeof(int)*row);
	if(labeledRow==NULL)
	{
		printf("in topologySort, mem apply failure.\n");
		return;
	}
	

	for(i=0;i<row;i++)
		labeledRow[i]=0;

	labeledNum=0;
	while(labeledNum!=row)
	{
		noFirstNode=1;
		
		for(j=0;j<col;j++)
		{
			if(!labeledRow[j])	//forget this line.
			{
				for(i=0;i<row;i++)
				{
					if(!labeledRow[i])
					{	//j is not a first node
						if(i!=j&&inMatrix[i][j]==1)
						{
							break;	
						}
					}
				}
			
				if(i==row)//j is a first node,note it ,del from the graph
				{
					topSeqArr[labeledNum]=j;
					labeledRow[j]=1;	//CORRECT->labeledRow[labeledNum]=1
					labeledNum++;
					noFirstNode=0;
				}
			}
		}

		if(noFirstNode)
		{
			printf("can't arrange a toplogy sort.\n");
			return;
		}
	}
	
	if(DEBUG)
	{
		printf("topsort result:\n");
		for(i=0;i<row;i++)
			printf("%d ",topSeqArr[i]);
		printf("\n");
	}
	free(labeledRow);
}