shuju.h

本源码配合数据结构（C++版 ）严蔚敏

//stack.h的代码//头文件部分
//函数结果状态代码 
/*#include"stdio.h"
#include "stdlib.h"

#define TRUE 1
#define FALSE 0
#define OK   1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NULL 0
typedef int Status;//函数的类型，其值是函数结果状态代码
*/
//图的 邻接表 存储表示
#define MAX_VERTEX_NUM1  10//顶点最大个数
typedef struct ArcNode{
	int adjvex;//该弧所指的顶点的位置
	struct ArcNode *nextarc;//指向下一条弧的指针
	int weight;//边的权
}ArcNode;//表的结点
typedef char VertexType;//顶点元素的类型 

typedef struct VNode{
	int degree,indegree;//顶点的度 ，入度
	VertexType data;	//顶点信息（如数据 等）
	ArcNode *firstarc;//指向第一条依附该顶点的弧指针
}VNode,AdjList[MAX_VERTEX_NUM1];//头结点
typedef struct{
	AdjList vertices;
	int vexnum,arcnum;//顶点的实际数，边(弧)的实际数
	int kind;//图的种类
}ALGraph;
#include "GraphRect.h"
void creatLink(ALGraph *G){
	//建立邻接链表
	int i,j;
	ArcNode *s;
	printf("输入顶点数，边数:");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	for(i=0;i<G->vexnum;i++){     
		G->vertices[i].data='A'+i;
		G->vertices[i].firstarc=NULL;
	}
	printf("Input the adjvexs of arcs \n");//该弧所指的顶点的位置
	for(int i1=0;i1<G->arcnum;i1++){
		scanf("%d%d",&i,&j);
		s=(ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex=j;//该弧所指的顶点的位置为 j
		s->nextarc=G->vertices[i].firstarc;
		G->vertices[i].firstarc=s;
	}
}

void visit(ALGraph G){
	//输出邻接表
	int i;
	ArcNode *p;
	printf("%4s%6s%18s\n","No","data","adjvexs of arcs");
	for(i=0;i<G.vexnum;i++){
		printf("%4d%5c  ",i,G.vertices[i].data);
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
			printf("%3d",p->adjvex);//弧所指的顶点的位置
		printf("\n");
	}
}
void cacu(ALGraph *G){
	//计算i个顶点的度及入度
	ArcNode*p;
	int i;
	for(i=0;i<G->vexnum;i++){
		G->vertices[i].degree=0;
		G->vertices[i].indegree=0;
	}
	for(i=0;i<G->vexnum;i++)
		for(p=G->vertices[i].firstarc;p;p=p->nextarc){
			G->vertices[i].degree++;
			G->vertices[p->adjvex].degree++;
			G->vertices[p->adjvex].indegree++;
		}
}
void printdegree(ALGraph G){
	int i;
	printf("\n No data deg ind\n");
	for(i=0;i<G.vexnum;i++)
		printf("\n%4d%4c%4d%4d",i,G.vertices[i].data,
		G.vertices[i].degree,G.vertices[i].indegree);
}

Status TopologiSort(ALGraph G){
	//拓扑排序－－有向图G采用邻接表存储结构
	//若G无回路，则输出G的顶点的一个拓扑排序并返回OK，否则ERROR
	int i,count,top=0,stack[50]={0};
	ArcNode *p;
	cacu(&G);
	printdegree(G);
	printf("\n TopologiSort is\n");
	for(i=0;i<G.vexnum;i++){//建零入度顶点栈
		if(!G.vertices[i].indegree) {stack[top++]=i;}//入度为零的顶点入栈
	}
	count=0;				//对输出顶点计数
	while(top!=0){
		i=stack[--top];
		if(count==0)printf("%c",G.vertices[i].data);
		else printf("-->%c",G.vertices[i].data);
		count++;			//输出i号顶点并计数
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
			if(!--G.vertices[p->adjvex].indegree)stack[top++]=p->adjvex;//对i号顶点的每个邻接点的入度减1
										//若入度为零，则入栈												
	}//while
	printf("\n");
	if(count<G.vexnum)return (FALSE);	//该有向图有回路
	else return (TRUE);
}//TopologiSort
///////////////////////////////////////////////////////////////
//深度优先搜索需要的函数:firstAdjVex,NextAdjVex,Vvisit
int FirstAdjVex(ALGraph G,int v){
	//
	ArcNode *p;
	if(p=G.vertices[v].firstarc)
		return p->adjvex;
	else return -1;
}
int NextAdjVex(ALGraph G,int v,int w){
	//
	ArcNode *p=G.vertices[v].firstarc;
	while(p->adjvex!=w){
		p=p->nextarc;
	}
	if(p->nextarc)return p->nextarc->adjvex;
	else return -1;
}
Status Vvisit(ALGraph G,int v){
	//ALGraph G;
	VNode p=G.vertices[v];
	printf("%c  ",p.data);
	return OK;
}
//DFSTraverse和DFS使用的全局变量
bool visited[MAX_VERTEX_NUM1];//访问标志数组
Status (*VisitFunc)(ALGraph G,int v);//函数指针

void DFS(ALGraph G,int v){
	//从第V个顶点出发递归地深度优先遍历图G
	visited[v]=TRUE;
	VisitFunc(G,v);//访问第v个顶点
	for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
		if(!visited[w])DFS(G,w);//对尚未访问的邻接顶点w递归调用DFS
}
void DFSTraverse(ALGraph G,Status(*Visit)(ALGraph G,int v)){
	//对图G进行深度优先遍历
	VisitFunc=Visit;//使用全局变量VisitFunc，使DFS不必设函数指针参数
	for(int v1=0;v1<G.vexnum;++v1)visited[v1]=FALSE;//访问标志数组初始化
	for(int v=0;v<G.vexnum;++v)
		if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS
		printf("\n");
}
/////////////////////////////////////////////////////////////////////////
//广度优先搜索
void BFSTraverse (ALGraph G,Status(*Visit)(ALGraph G,int v)){
	//安广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。
	int u,w;
	for(int v1=0;v1<G.vexnum;++v1)visited[v1]=FALSE;
	LinkQueue Q;
	InitQueue(Q);			//置空的辅助队列Q
	for(int v=0;v<G.vexnum;++v)
		if(!visited[v]){		//v尚未访问
			visited[v]=TRUE;
			(*Visit)(G,v);
			EnQueue(Q,v);		//v入队列
			while(!QueueEmpty(Q)){
				DeQueue(Q,u);		//队头元素出队并置未u
				for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
					if(!visited[w]){	//w为u的尚未访问的邻接顶点
						visited[w]=TRUE;
						(*Visit)(G,w);
						EnQueue(Q,w);
					}//if
			}//while
		}//if
		DestroyQueue(Q);
}//BFSTraverse