queue.cpp

BFS、DFS、有向图、无向图中的各种算法的实现

#include "stdafx.h"
#include "queue.h"
VerQueue::VerQueue()
{
	m_phead = NULL;
	m_prear = NULL;
	m_nnum = 0;
}
void VerQueue::EnQueue(CRect q)
{
	VerNode *pnew = new VerNode;
	pnew->m_pnextver = NULL;
	pnew->m_rect = q;
	pnew->m_pfirstarc = NULL;
	pnew->m_strname = "NONE";
	pnew->m_bvisit = FALSE;
	pnew->m_nvisit = 0;

	if(m_phead == NULL){
		m_phead = m_prear = pnew;
		m_nnum++;
	}
	else{
		m_prear->m_pnextver = pnew;
		m_prear = pnew;
		m_nnum++;
	}
}
void VerQueue::DeQueue(CRect& q)
{	
	if(m_nnum != 0){
			q = m_phead->m_rect;
			VerNode* p = m_phead;
			if(m_nnum != 1){
				m_phead = p->m_pnextver;
				m_nnum--;
				delete p;
			}
			else{
				m_phead = m_prear = NULL;
				m_nnum = 0;
				delete p;
			}
	}
}
CPoint VerQueue::ChagetoPoint(CRect rect)
{
	CPoint point;
	point.x = (rect.left+rect.right)/2;
	point.y = (rect.bottom+rect.top)/2;
	return point;
}
VerNode* VerQueue::IsInQueue(CPoint p,CPoint& cp)
{	
	for(VerNode* q = m_phead;q;q=q->m_pnextver){
		if(q->m_rect.PtInRect(p)){
			cp = ChagetoPoint(q->m_rect);
			return q;
		}
	}
	return NULL;
}
VerNode* VerQueue::DeleteVer(VerNode* pver)
{
	VerNode* ptemp = m_phead;
	if(pver == m_phead){
		m_phead = m_phead->m_pnextver;
			if(m_phead == NULL)
			m_prear = m_phead;
		m_nnum--;
	}
	else{
		for(;ptemp->m_pnextver != pver;ptemp = ptemp->m_pnextver){}
		ptemp->m_pnextver = pver->m_pnextver;
		m_nnum--;
		if(ptemp->m_pnextver == NULL)
			m_prear = ptemp;
		delete pver;
	}
	return m_phead;
}

void VerQueue::EnQueue(VerNode node)
{
	VerNode *pnew = new VerNode;
	pnew->m_pnextver = node.m_pnextver;
	pnew->m_rect = node.m_rect;
	pnew->m_pfirstarc = node.m_pfirstarc;
	pnew->m_strname = node.m_strname;
	pnew->m_bvisit = node.m_bvisit;
	pnew->m_nvisit = node.m_nvisit;

	if(m_phead == NULL){
		m_phead = m_prear = pnew;
		m_nnum++;
	}
	else{
		m_prear->m_pnextver = pnew;
		m_prear = pnew;
		m_nnum++;
	}
}

void VerQueue::DeQueue(VerNode& node)
{
	if(m_nnum != 0){	//queue is not empty.
			node.m_bvisit = m_phead->m_bvisit;
			node.m_nvisit = m_phead->m_nvisit;
			node.m_pfirstarc = m_phead->m_pfirstarc;
			node.m_pnextver = m_phead->m_pnextver;
			node.m_rect = m_phead->m_rect;
			node.m_strname = m_phead->m_strname;
			VerNode* p = m_phead;
			if(m_nnum != 1){
				m_phead = p->m_pnextver;
				m_nnum--;
				delete p;
			}
			else{
				m_phead = m_prear = NULL;
				m_nnum = 0;
				delete p;
			}
	}
}