adjtwgraph.h

包含各种测试,查找和算法等代码,如冒泡算法,树的遍历,链表,队列,堆栈等

#include "SeqQueue.h"
const int MaxVertices = 100;

struct EdgeType
{
	int dest;
	DistT weight;
	EdgeType *next;

	EdgeType(){};
	EdgeType(int d, DistT w): dest(d), weight(w), next(NULL){}
};

struct ItemType
{
	VerT data;
	EdgeType *adj;
};

class AdjTWGraph
{
private:
	ItemType Vertices[MaxVertices];
	int numVertices;
	int numOfEdges;

	void DepthFirstSearch(const int v, int visited[], void visit(VerT ItemType));
	void BroadFirstSearch(const int v, int visited[], void visit(VerT ItemType));
public:
	AdjTWGraph(void);
	~AdjTWGraph(void);

	int NumOfVertices(void)
		{return numVertices;}
	int NumOfEdges(void)
		{return numOfEdges;}
	VerT GetValue(const int i);
	int GetWeight(const int v1, const int v2);

	void InsertVertex(const VerT &vertex);
	void InsertEdge(const int v1, const int v2, int weight);
	void DeleteVertex(const int v);
	void DeleteEdge(const int v1, const int v2);

	int GetFirstNeighbor(const int v);
	int GetNextNeighbor(const int v1, const int v2);

	void DepthFirstSearch(void visit(VerT ItemType));
	void BroadFirstSearch(void visit(VerT ItemType));
};

AdjTWGraph::AdjTWGraph(void)
{
	for(int i = 0; i < MaxVertices; i++) Vertices[i].adj = NULL;
	numVertices = 0;		
	numOfEdges = 0;
}

AdjTWGraph::~AdjTWGraph(void)
{
	for(int i = 0; i < numVertices; i++)
	{
		EdgeType *p = Vertices[i].adj, *q;
		while(p != NULL)
		{
			q = p->next;
			delete p;
			p = q;
		}
	}
}

VerT AdjTWGraph::GetValue(const int i)
{
	if(i < 0 || i > numVertices)
	{
		cout << "参数i越界出错!" << endl;
		exit(0);
	}
	return Vertices[i].data;
}

int AdjTWGraph::GetWeight(const int v1, const int v2)
{
	if(v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices)
	{
		cout << "参数v1或v2越界出错!" << endl;
		exit(0);
	}
	EdgeType *p = Vertices[v1].adj;
	while(p != NULL && p->dest < v2) p = p->next;
	if(v2 != p->dest) 
	{
		cout << "边<v1, v2>不存在!" << endl;
		exit(0);
	}
	return p->weight;
}

void AdjTWGraph::InsertVertex(const VerT &vertex)
{
	Vertices[numVertices].data = vertex;
	numVertices++;
}

void AdjTWGraph::InsertEdge(const int v1, const int v2, int weight)
{
	if(v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices)
	{
		cout << "参数v1或v2越界出错!" << endl;
		exit(0);
	}

	EdgeType *q = new EdgeType(v2, weight);
	if(Vertices[v1].adj == NULL)
		Vertices[v1].adj = q;
	else
	{
		EdgeType *curr = Vertices[v1].adj, *pre = NULL;
		while(curr != NULL && curr->dest < v2) 
		{
			pre = curr;
			curr = curr->next;
		}
		if(pre == NULL)
		{
			q->next = Vertices[v1].adj;
			Vertices[v1].adj = q;
		}
		else
		{
			q->next = pre->next;
			pre->next = q;
		}
	}
	numOfEdges++;
}

void AdjTWGraph::DeleteVertex(const int v)
{
	EdgeType *pre, *curr;
	for(int i = 0; i < numVertices; i++)
	{
		pre = NULL;
		curr = Vertices[i].adj;
		while(curr != NULL && curr->dest < v)
		{
			pre = curr; 
			curr = curr->next;
		}

		if(pre == NULL && curr->dest == v)
		{
			Vertices[i].adj = curr->next;
			delete curr;
			numOfEdges--;
		}
		else if(curr != NULL && curr->dest == v) 
		{
			pre->next = curr->next;
			delete curr;
			numOfEdges--;
		}
	}

	EdgeType *p = Vertices[v].adj, *q;
	for(i = v; i < numVertices-1; i++)
		Vertices[i] = Vertices[i+1];
	numVertices--;

	while(p != NULL)
	{
		q = p->next;
		delete p;
		p = q;
		numOfEdges--;
	}
}

void AdjTWGraph::DeleteEdge(const int v1, const int v2)
{
	if(v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices)
	{
		cout << "参数v1或v2越界出错!" << endl;
		exit(0);
	}
	EdgeType *curr = Vertices[v1].adj, *pre = NULL;
	while(curr != NULL && curr->dest < v2)
	{
		pre = curr; 
		curr = curr->next;
	}
	if(pre == NULL && curr->dest == v2) 
	{
		Vertices[v1].adj = curr->next;
		delete curr;
		numOfEdges--;
	}
	else if(pre != NULL && curr->dest == v2)
	{
		pre->next = curr->next;
		delete curr;
		numOfEdges--;
	}
	else
	{
		cout << "边<v1, v2>不存在!" << endl;
		exit(0);	
	}
}

int AdjTWGraph::GetFirstNeighbor(const int v)
{
	if(v < 0 || v > numVertices)
	{
		cout << "参数v1越界出错!" << endl;
		exit(0);
	}
	EdgeType *p = Vertices[v].adj;
	if(p != NULL) return p->dest;
	else return -1;
}

int AdjTWGraph::GetNextNeighbor(const int v1, const int v2)
{
	if(v1 < 0 || v1 > numVertices || v2 < 0 || v2 > numVertices)
	{
		cout << "参数v1或v2越界出错!" << endl;
		exit(0);
	}
	EdgeType *p = Vertices[v1].adj;
	while(p != NULL)
	{
		if(p->next != NULL && p->dest == v2) return p->next->dest;
		else p = p->next;
	}
	return -1;
}

void AdjTWGraph::DepthFirstSearch(void visit(VerT ItemType))
{
	int *visited = new int[NumOfVertices()];
	for(int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
	for(i = 0; i < NumOfVertices(); i++)
		if(! visited[i]) DepthFirstSearch(i, visited, visit);
	delete []visited;
}

void AdjTWGraph::DepthFirstSearch(const int v, int visited[], void visit(VerT ItemType))
{
	visit(GetValue(v));
	visited[v] = 1;

	int w = GetFirstNeighbor(v);
	while(w != -1)
	{
		if(! visited[w]) DepthFirstSearch(w, visited, visit);
		w = GetNextNeighbor(v, w);
	}
}

void AdjTWGraph::BroadFirstSearch(void visit(VerT ItemType))
{
	int *visited = new int[NumOfVertices()];
	for(int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
	for(i = 0; i < NumOfVertices(); i++)
		if(!visited[i]) BroadFirstSearch(i, visited, visit);
	delete []visited;
}

void AdjTWGraph::BroadFirstSearch(const int v, int visited[], void visit(VerT ItemType))
{
	VerT u, w;
	SeqQueue queue;
	visit(GetValue(v));
	visited[v] = 1;
	queue.Append(v);
	while(queue.NotEmpty())
	{
		u = queue.Delete();
		w = GetFirstNeighbor(u);
		while(w != -1)
		{
			if(!visited[w])
			{
				visit(GetValue(w));
				visited[w] = 1;
				queue.Append(w);
			}
			w = GetNextNeighbor(u, w);
		}
	}
}