graph.cpp

数据结构测试程序

// Graph.cpp: implementation of the Graph class.
//
//////////////////////////////////////////////////////////////////////

#include "Graph.h"
#include "stdio.h"
#include "stdlib.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Graph::Graph()
{
	length=0;

}

Graph::~Graph()
{

}

int Graph::loc_vextex(char v)
{
	int i;
	for (i=0;i<length;i++)
	{
		if (adjlist[i].vexdata==v)
			break;
	}
	if (i<length) return i;
	else	return -1;
}

char Graph::get_vertex(int i)
{
	if (i>=length)	return 0;
	return adjlist[i].vexdata;
}

char Graph::first_adj(char v)
{
	int k;
	k=loc_vextex(v);
	if (k==-1)	return 0;//if not exist then return 0
	else	return adjlist[k].vexdata;

}

char Graph::next_adj(char v,char w)
{
	int k;
	struct arcnode *p;
	k=loc_vextex(v);
	if (k==0) return 0;
	p=adjlist[k].firstarc;
	if (p!=NULL)
		if (adjlist[p->adjvex].vexdata==w)	return	adjlist[p->nextarc->adjvex].vexdata;
		else p=p->nextarc;
	return 0;

}

void Graph::ins_vertex(char u)
{
	if (length>N_g) return;
	adjlist[length].vexdata=u;
	adjlist[length].firstarc=NULL;
}

void Graph::ins_arc(char v, char w)
{
	int k;
	k=loc_vextex(v);
	if (k==0) {printf("no this %c",v);return;}
	struct arcnode *p;
	p=adjlist[k].firstarc;
	p=(arcnode*)malloc(sizeof(arcnode));
	p->nextarc=p;
	adjlist[k].firstarc=p;	

}

void Graph::del_vertex(char v)
{
	int k;
	struct arcnode *p,*q;
	k=loc_vextex(v);
	if (k==0) return;
	int i;
	for (i=k;i<length;i++)
		adjlist[i]=adjlist[i+1];
	length--;
	for (i=0;i<length;i++)
	{
		p=adjlist[i].firstarc;
		while (p)
			if (adjlist[p->adjvex].vexdata==v)
			{
				q=p;
				p=p->nextarc;
				free(q);
			}
			p=p->nextarc;
	}
}

void Graph::del_arc(char v, char w)
{
	int k;
	k=loc_vextex(v);
	if (k==-1)	return;
	struct arcnode *p,*q;
	p=adjlist[k].firstarc;
	while (p)
	{
		if (p->adjvex==w)
		{
			q=p;
			p=p->nextarc;
			free(q);
		}
		p=p->nextarc;
	}	
}

void Graph::outGraph()
{
	int i;
	struct arcnode* p;
	for (i=0;i<length;i++)
	{
		printf("%c",adjlist[i].vexdata);
		p=adjlist[i].firstarc;
		while (p)
		{
			printf("---%c",p->adjvex);
			p=p->nextarc;
		}
		printf("\n");
	}
}