?? testoftopologysort.c
字號(hào):
#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);
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -