数据结构查找排序问题

数据结构查找排序问题

按照你的要求下的程序，自己也复习了一遍，这学期我们也学数据结构，有问题可以继续问哦
#define MAX 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int ElemType;
typedef struct biaoNode
{
   int xiabiao;//数据域
   struct biaoNode *nextbiao;//指针域
}biaoNode;//表结点的定义

typedef struct touNode //头结点
{
   int data;//数据域
   int indegree;//度数
   biaoNode *firstarc;//指针
}touNode,AdjList[MAX];//AdjList[MAX]邻接表存储方式

typedef struct
{
   AdjList shuzu;//数组邻接表
   int dingdianshu,bianshu;//dingdianshu定点数，bianshu边数
}tu;//图的定义

typedef struct
{
   ElemType *base;
   ElemType *top;
   int stacksize;
}SqStack;//栈，这个你应该很熟悉了~
void creattu(tu *G)//此函数创建图
{
int m, n, i;
biaoNode *p;//表结点指针
printf("input dingdianshu and bianshu:");
scanf("%d%d",&G->dingdianshu,&G->bianshu);//输入节点数和边数
for (i = 1; i <= G->dingdianshu; i++)//for循环是初始化一个图，数据域为i，度数为0，第一个相邻的弧为空
{
 G->shuzu[i].data = i;
 G->shuzu[i].indegree=0;
 G->shuzu[i].firstarc = 0;
}
for (i = 1; i <= G->bianshu; i++)
{

 scanf("%d%d",&n,&m);//输入一个从n到m的弧，注意是有向的，顺序不能相反
 while (n < 0 || n > G->dingdianshu || m < 0 || m > G->dingdianshu)//若下标或者第一个相邻的点不符合要求泽输出错误，要求重新输入
 {
  printf("input error:");
  scanf("%d%d",&n,&m);
 }
 p = (biaoNode*)malloc(sizeof(biaoNode));//分配一个节点用来存储刚才下标为m信息
 if (p == 0)//没有分配成功，则输出错误
 {
  printf("error");
  exit(0);
 }
 p->xiabiao = m;//p下标m
 p->nextbiao = G->shuzu[n].firstarc;//p的nextbiao指针指向n
 G->shuzu[n].firstarc = p;//同理n的第一个邻接点是m也就是p（刚刚赋值了嘛）
 G->shuzu[m].indegree++;//m的入度+1，因为相邻n嘛，因为是有向图，
}
printf("outpu G:\n");          

for(i = 1; i <= G->dingdianshu; i++)//输出各节点的信息，包括数据和度数，和与它相邻的点的下标
{
 printf("%2d",G->shuzu[i].data);
 printf("%7d",G->shuzu[i].indegree);
 for(p = G->shuzu[i].firstarc; p; p = p->nextbiao)
 {
  printf("%7d",p->xiabiao);
 }
 printf("\n");
}
}

int Pop(SqStack *S)//从栈中弹出，这个你也很熟悉吧，数据结构课本上可是有哦
{
int e;
if(S->top==S->base)
{
 printf("zhan kong\n");
}
S->top=S->top-1;
e=*S->top;
printf("%3d",e);
return(e);
}
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("zhan fen pei shi bai\n");
  exit(0);
 }
 S->top = S->base+S->stacksize;
 S->stacksize+=STACKINCREMENT;
}
*S->top=e;
S->top++;
}
int StackEmpty(SqStack *S)//栈置空
{
if(S->top==S->base)
 return 1;
else
 return 0;
}
void InitStack(SqStack *S)//初始化栈
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
 printf("zhan chu shi hua shi bai\n");
 exit(0);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
void paixu(tu G)//排序，这个可是重点哦，其思想是1）在有向图中查找一个没有后继（或前驱）的顶点并添加到顶点表中。（2）从图中删除该顶点和所有以该顶点为头（尾）的弧。重复上述两步，当图为空时，顶点表将以拓扑次序出现。

{
int count=0;
int i;
biaoNode *p;
SqStack S;
InitStack(&S);
for(i=1;i<=G.dingdianshu;i++)//找出入度为0的节点，入栈
{
 if(G.shuzu[i].indegree==0)
  Push(&S,i);
}
printf("G input:");
while(!StackEmpty(&S))//如果栈不空，也就是有入度为0的节点
{
 i=Pop(&S);//弹出
 count++;//计数器+1
 for(p=G.shuzu[i].firstarc;p!=0;p=p->nextbiao)//与i相邻的节点度数减1
 {
  G.shuzu[p->xiabiao].indegree--;
  if(G.shuzu[p->xiabiao].indegree==0)
   Push(&S,p->xiabiao);//如果减1后，其入度为0，则入栈
 }
}
printf("\n");
if(count!=G.dingdianshu)//如果呢，整个一个大排序下来我们技术器的度数不是这个图的节点数，那么，就是出现错误了，否则排序成功。
 printf("chu xian cuo wu\n");
else
 printf("pai xu cheng gong\n");
}
main()//main函数条例很清晰，我就不废话啦~          
{
   tu G;
   creattu(&G);
paixu(G);
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息！