邻接表实现状态图【大家帮忙看看问题】

StatusGrap.cpp

// StatusGraph.cpp: implementation of the StatusGraph class.
//
//////////////////////////////////////////////////////////////////////
#include "StdAfx.h"
#include "StatusGraph.h"

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

/*
template<typename vertex>
StatusGraph<vertex>::~StatusGraph()
{}*/

template<typename vertex>
void StatusGraph<vertex>::erase_vertex(const vertex& v){
	adj_map::iterator m_iter = adj_map.find(v);
	if(m_iter == adj_map.end() ) return ;
	adj_map.erase(m_iter);

	m_iter =adj_map.begin();
	while (m_iter !=adj_map.end())
	{
		list<dest_vertex<vertex> > & edge_list = (*m_iter).second;
		list<dest_vertex<vertex> >::iterator list_iter = edge_list.begin();

		for (;list_iter != edge_list.end();list_iter ++)
		{
			if ( (*list_iter).dest == v )
			{
				edge_list.erase(list_iter);
				break;
			}
		}
		m_iter++;
	}
}

template<typename vertex>
int StatusGraph<vertex>::edge_count(){
	int count =0;
	graphMap::iterator m_iter = adj_map.begin();
	for (;m_iter != adj_map.end();m_iter ++)
	{
		count += (*m_iter).second.size();
	}
	if (d) return count;
	else return count / 2 ;
}

template<typename vertex>
int StatusGraph<vertex>::get_weight(const vertex &v1,const vertex &v2){
	graphMap::iterator iter =adj_map.find(v1);
	if (iter != adj_map.end() && adj_map.find(v2) != adj_map.end())
	{
		list<dest_vertex<vertex> >& edge_list = (*iter).second;
		list<dest_vertex<vertex> >::iterator list_iter = edge_list.begin();
		while(list_iter != edge_list.end()){
			if ((*list_iter).dest == v2)
			{
				return (*list_iter).weight;
			}
			list_iter++;
		}
	}
	return -1;
}

template<typename vertex>
void StatusGraph<vertex>::insert_edge(const vertex &v1,const vertex &v2,const int& weight){
	if (contains_edge(v1,v2)) return;
	insert_vertex(v1);
	insert_vertex(v2);
	list<dest_vertex<vertex> > & e_list1 = (*(adj_map.find(v1)) ).second;
	e_list1.push_back(dest_vertex<vertex>(v2,weight));
	if (d)
	{
		return ;
	}
	list<dest_vertex< vertex> >& e_list2 = (*(adj_map.find(v2))).second;
	e_list2.push_back(dest_vertex<vertex>(v1,weight));
}

template<typename vertex>
void StatusGraph<vertex>::erase_edge(const vertex& v1,const vertex&v2){
	graphMap::iterator iter = adj_map.find(v1);
	if (iter == adj_map.end() || adj_map.find(v2) == adj_map.end())
	{
		return ;// no node v1\v2
	}
	list<dest_vertex<vertex> >& e_list1 = (*iter).second;
	list<dest_vertex<vertex> >::iterator list_iter = e_list1.begin();
	for (; list_iter != e_list1.end(); list_iter ++)
	{
		if ((*list_iter).dest == v2 )
		{
			found = true;
			e_list1.erase(list_iter);
			break;
		}
	}
	if (d || !found) return;
	iter = adj_map.find(v2);
	list<dest_vertex<vertex> >& e_lsit2 = (*iter).second;
	list_iter = e_lsit2.begin();
	for (; list_iter != e_lsit2.end();list_iter ++)
	{
		if ((*list_iter).dest == v1)
		{
			e_lsit2.erase(list_iter);
			break;
		}
	}
}

template<typename vertex>
bool StatusGraph<vertex>::contains_edge(const vertex &v1,const vertex &v2){
	graphMap::iterator iter = adj_map.find(v1);
	if (iter != adj_map.end() && adj_map.find(v2) ! = adj_map.end())
	{
		list<dest_vertex<vertex> >& edge_list = (*iter).second;
		list<dest_vertex<vertex> >::iterator list_iter = edge_list.begin();
		for (;list_iter != edge_list.end(); list_iter ++)
		{
			if((*list_iter).dest == v2) return true;
		}
	}
	return false;
}

template<typename vertex>
istream& operator>>(istream&istr,StatusGraph<vertex> &g){
	cout << "待实现!" <<endl;
	return istr;
}

template<typename vertex>
ostream& operator<<(ostream&ostr,const StatusGraph<vertex>&g){
	g.output();
	return ostr;
}

template<typename vertex>
void StatusGraph<vertex>::output() const{
	cout << "待实现!" <<endl;
}

StatusGrap.h

#if !defined(AFX_STATUSGRAPH_H__239AC296_43C3_4CD4_A788_91E56564168C__INCLUDED_)
#define AFX_STATUSGRAPH_H__239AC296_43C3_4CD4_A788_91E56564168C__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <map>
#include <list>
#include <string>
#include <iostream>
using namespace std;


enum gkind {undigraph,digraph};

template<typename vertex>
struct dest_vertex 
{
	vertex dest;//顶点
	int weight;//权重
	dest_vertex(const vertex& x,const int& wet)
	{
		dest = x;
		weight =wet;
	}
	bool operator > (const dest_vertex<vertex> &e) const
	{
		return weight > e.weight;
	}
};

template<typename vertex>
class StatusGraph
{
public:
	StatusGraph(gkind t = digraph):d(t){}
	/*
	 *	
	 */
	StatusGraph(const StatusGraph& g){
		adj_map = g.adj_map;
	}
	/*
	 *	
	 */
	~StatusGraph(){};
	/**
	*	return this graph's size.
	*/
	int size(){
		return adj_map.size();
	}
	/**
	*	return this graph is empty or not !
	*/
	bool empty(){
		return adj_map.size() == 0;
	}
	/**
	*  check a vertex is own to the container or not .
	*/
	bool contain_vertex(const vertex &v){
		return adj_map.find(v) != adj_map.end();
	}
	/*
	 *	insert a vertex into the container.	
	 */
	void insert_vertex(const vertex& v)
	{
		if (adj_map.find(v)) == adj_map.end() )
		{
			adj_map[v] = list<dest_vertex<vertex>>();
		}
	}
	/**
	*	@author raojl
	*	@desc: what node you want to delete
	*	@Edit 2010.06.20
	*/
	void erase_vertex(const vertex& v);
	/*
	 *	
	 */
	int edge_count();
	/*
	 *
	 */
	bool contains_edge(const vertex &v1,const vertex &v2);

	/*
	 *	
	 */
	int get_weight(const vertex &v1,const vertex &v2);
	
	/*
	 *	
	 */
	void insert_edge(const vertex &v1,const vertex &v2,const int& weight);

	/*
	 *	
	 */
	void erase_edge(const vertex &v1,const vertex &v2);
	/*
	 *
	 */
	list<dest_vertex<vertex> > get_incident_edges(const vertex & v)const
	{
		return (*adj_map.find(v)).second;
	}
	/*
	 *	
	 */
	vertex first_vertex(){
		return (*adj_map.begin()).first;
	}
public:
	friend istream& operator>>(istream&istr,StatusGraph<vertex>& g);
	friend ostream& operator<<(ostream&ostr,const StatusGraph<vertex> &g);
	//void dfs_traversal();//深度优先搜索
	//void bfs_traversal();//广度优先搜索


private:
	typedef map<vertex,list< dest_vertex<vertex> > > graphMap;

	graphMap adj_map;
	gkind d;

	//list<vertex> dfs(vertex& start,map<vertex,bool>* visited);
	//list<vertex> bfs(vertex& start,map<vertex,bool>* visited);
	void output() const;

};

#endif // !defined(AFX_STATUSGRAPH_H__239AC296_43C3_4CD4_A788_91E56564168C__INCLUDED_)

int main(int argc, char* argv[])
{
	typedef char vertex;
	StatusGraph<vertex> tt(digraph);
    cin>>tt;
	cout << tt;
	return 0;
}

大家帮忙看看 << 和 >>重载有问题呢？

StdStudy.obj : error LNK2001: unresolved external symbol "class std::basic_istream<char,struct std::char_traits<char> > & __cdecl operator>>(class std::basic_istream<char,struct std::char_traits<char> > &,class StatusGraph<char> &)" (??5@YAAAV?$basi
c_istream@DU?$char_traits@D@std@@@std@@AAV01@AAV?$StatusGraph@D@@@Z)

D:\StdStudy\StdStudy.cpp(30) : error C2679: binary '<<' : no operator defined which takes a right-hand operand of type 'class StatusGraph<char>' (or there is no acceptable conversion)
Error executing cl.exe.
Creating browse info file...

评论

2 楼 raojl 2010-06-28  

lijinyan3000 写道

这些代码自己实现的?

厉害!!

水平很高了!

全是迭代，厉害个毛！有空帮我看看问题！

1 楼 lijinyan3000 2010-06-28  

这些代码自己实现的?

厉害!!

水平很高了!