graph.cpp

此文件夹中共包括十二个小程序 AVL创建平衡二叉树,通过加入一个个的结点创建,并实现了平衡二叉树中的结点删除 Boyer_Moore算法的串模式匹配 Horspool算法的串模式匹配 Grap

#include<stdio.h>
#include <stdlib.h>
#include "Graph.h"
#include <malloc.h>
#define INF 32767
int visited[MAXV];//全局数组

//输出邻接矩阵g
void DispMat(MGraph g)
{
	int i,j;
	for(i=0;i<g.vexnum;i++)
	{
		for(j=0;j<g.vexnum;j++)
			if(g.edges[i][j]==INF)
				printf("%3s","large");
			else
				printf("%3d",g.edges[i][j]);
			printf("\n");
	}
}
//输出邻接表G
void DispAdj(ALGraph *G)
{
	int i;
	ArcNode *p;
	for(i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		if(p!=NULL) printf("%3d: ",i);
		while(p!=NULL)
		{
			printf("%3d",p->adjvex);
			p=p->nextarc;
		}
		printf("\n");
	}
}

//将邻接矩阵g转换成邻接表G
void MatToList(MGraph g,ALGraph *&G)
{
	int i,j,n=g.vexnum;  //n为顶点数
	ArcNode *p;
	G=(ALGraph *)malloc(sizeof(ALGraph));
	for(i=0;i<n;i++)
		G->adjlist[i].firstarc=NULL;

	for(i=0;i<n;i++)
		for(j=n-1;j>=0;j--)
			if(g.edges[i][j]!=0)   //邻接矩阵中当前元素不为0时
			{
				p=(ArcNode *)malloc(sizeof(ArcNode));  //创建一个结点*p
				p->adjvex=j;
				p->info=g.edges[i][j];  //存放边的权值

				p->nextarc=G->adjlist[i].firstarc; //将*p链到链表后
				G->adjlist[i].firstarc=p;
			}
			G->n=n; G->e=g.arcnum;
}

//对用邻接表表示的图，非递归深度优先遍历
void DFS(ALGraph *G,int v)
{
	int i,visited[MAXV],st[MAXV],top=-1;
	ArcNode *p;
	for(i=0;i<G->n;i++)
		visited[i]=0;   //结点访问标记均置为0
	printf("%3d",v);
	top++;
	st[top]=v;   //v入栈
	visited[v]=1;

	while(top>=-1)  //栈不空时循环
	{
		v=st[top];top--;  //取栈顶顶点
		p=G->adjlist[v].firstarc;		

		while(p!=NULL&&visited[p->adjvex]==1)
			p=p->nextarc;
		if(p==NULL)
			top--;
		else
		{
			v=p->adjvex;
			printf("%3d",v);  //访问顶点
			visited[v]=1;
			top++;
			st[top]=v;   //v入栈
		}
	}
	printf("\n");
}
//对邻接表表示的图，进行广度优先非递归遍历
void BFS(ALGraph *G,int v)
{
	ArcNode *p;
	int queue[MAXV],front=0,rear=0;
	int visited[MAXV];
	int w,i;
	for(i=0;i<G->n;i++) visited[i]=0;
	printf("%3d",v);  //输出被访问顶点的编号
	visited[v]=1;
	rear=(rear+1)%MAXV;
	queue[rear]=v;    //v进队

	while(front!=rear)  //若队列不空时循环
	{
		front=(front+1)%MAXV;
		w=queue[front];  //出队并赋给w
		p=G->adjlist[w].firstarc; //找与顶点w邻接的第一个顶点
		while(p!=NULL)
		{
			if(visited[p->adjvex]==0)
			{
				printf("%3d",p->adjvex);
				visited[p->adjvex]=1;
				rear=(rear+1)%MAXV;  //该顶点进队
	            queue[rear]=p->adjvex; 
			}
			p=p->nextarc;  //找下一个邻接顶点
		}
	}
		printf("\n");
}


void main()
{
	int i,j;
	MGraph g;
	ALGraph *G;
	int A[MAXV][6]={
		{0,3,0,7,0,0},
		{0,0,4,0,6,0},
		{8,0,0,0,0,9},
		{0,0,5,0,0,6},
		{0,0,0,5,0,0},
		{3,0,0,0,1,0}};

	g.vexnum=6; g.arcnum=10;
	for(i=0;i<g.vexnum;i++)   //建立图的邻接矩阵
		for(j=0;j<g.vexnum;j++)
			g.edges[i][j]=A[i][j];

	printf("\n");
    printf("有向图邻接矩阵为:\n");
	DispMat(g);

	G=(ALGraph *)malloc(sizeof(ALGraph));
	 printf("图G的邻接矩阵转换为邻接表:\n");
	MatToList(g,G); 
	DispAdj(G);

	printf("从顶点0开始的DFS(非递归遍历):\n");
	DFS(G,0);

	printf("从顶点0开始的BFS(非递归遍历):\n");
	BFS(G,0);
	printf("\n");
	
	system("PAUSE");
	
}