郑礼明.cpp

清化大学的数据结构（C语言版本）上所有例子的代码实现

#include<stdlib.h>
#include<string.h>
 #include<ctype.h>
 #include<malloc.h> // malloc()等
 #include<limits.h> // INT_MAX等
 #include<stdio.h> // EOF(=^Z或F6),NULL
 #include<stdlib.h> // atoi()
 #include<io.h> // eof()
 #include<math.h> // floor(),ceil(),abs()
 #include<process.h> // exit()
 #include<iostream.h> // cout,cin
#include<conio.h>
#include"stdio.h"
#define ERROR 0
#define OK 1

typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
	char str[4];
	int score;
	ArcNode *firstarc;
}VNode,*AdjList;
typedef struct
{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;
void CreateDG(ALGraph &G)
{
	int i,j,k;
	ArcNode *s;
	printf("请输入课程数和边数:");
	scanf("%d",&G.vexnum);
	scanf("%d",&G.arcnum);
	G.vertices=(AdjList)malloc(G.vexnum*sizeof(VNode));
	for(i=0;i<G.vexnum;i++)
	{
		printf("请输入课程号:");
		gets(G.vertices[i].str);
		printf("请输入学分:");
		scanf("%d",&G.vertices[i].score);
		G.vertices[i].firstarc=NULL;
	}
	for(k=0;k<G.arcnum;k++)
	{
		printf("输入关系:\n");
		scanf("%d%d",&i,&j);
		s=(ArcNode *)malloc(sizeof(ArcNode));
		s->adjvex=i;
		s->nextarc=G.vertices[j].firstarc;
		G.vertices[j].firstarc=s;
	}
}
void Enterstring(char *str)
{
	FILE *fp;
	if((fp=fopen("file2.txt","w"))==NULL)
	{
		printf("can't open file");
		exit(0);
	}
	fputs(str,fp);
	fputs("\n",fp);
	fclose(fp);
}
int Topologicalsort1(ALGraph &G,int sl)
{
	int indegree[20];
	int i,k,count,T,a;
	ArcNode *p;
	T=0;
	for(i=0;i<G.vexnum;i++)
	{
		indegree[i]=0;
	}
	for(i=0;i<G.vexnum;i++)
	{
		p=G.vertices[i].firstarc;
		while(p!=NULL)
		{
			indegree[i]++;
			p=p->nextarc;
		}
	if(indegree[i]==0)
		T++;
	}
	count=0;
	while(T!=0)
	{
		a=0;
		for(i=0;i<G.vexnum;i++)
		{
			if(indegree[i]==0)
			{
				if((a=+G.vertices[i].score)<=sl)
				{
					indegree[i]--;
					T--;
					count++;
					puts(G.vertices[i].str);
					Enterstring(G.vertices[i].str);
				}
				for(p=G.vertices[i].firstarc;p;p=p->nextarc)
				{
					k=p->adjvex;
					if(!(--indegree[k]))
						T++;
				}
			}
		}
		printf("\n");
	}
	if(count<G.vexnum)
		return ERROR;
	else
		return OK;
}
int Topologicalsort2(ALGraph &G,int s)
{
	int indegree[20];
	int i,count,k,a;
	int T;
	ArcNode *p;
	for(i=0;i<G.vexnum;i++)
	{
		indegree[i]=0;
	}
	for(i=0;i<G.vexnum;i++)
	{
		p=G.vertices[i].firstarc;
		while(p!=NULL)
		{
			indegree[i]++;
			p=p->nextarc;
		}
		if(indegree[i]==0)
			T++;
	}
	count=0;
	while(T!=0)
	{
		a=0;
		for(i=0;i<G.vexnum;i++)
		{
			if(indegree[i]==0)
			{
				if(a<=(G.vexnum/s))
				{
					indegree[i]--;
					T--;
					a++;
					count++;
					puts(G.vertices[i].str);
					Enterstring(G.vertices[i].str);
				}
				for(p=G.vertices[i].firstarc;p;p=p->nextarc)
				{
					k=p->adjvex;
					if(!(--indegree[k]))
						T++;
				}
			}
		}
		printf("\n");
	}
	if(count<G.vexnum)
		return ERROR;
	else
		return OK;
}
void main()
{
	int m,s,sl;
	ALGraph G;
	CreateDG(G);
	printf("方法一(1);\t");
	printf("方法二(2);\n");
	printf("请输入选择 学期数及学分上限:");
	scanf("%d%d%d",&m,&s,&sl);
	switch(m)
	{
	case 1:Topologicalsort1(G,sl);
		break;
	case 2:Topologicalsort2(G,s);
		break;
	}
}