|
除最后一个节点 { int edge_count = 0; int index = get_vertex_index(vert); if(index == -1) return false; for(int i=0; i
bool graph_mtx
::remove_edge(const T& vert1, const T& vert2) { int index_v1 = get_vertex_index(vert1); int index_v2 = get_vertex_index(vert2); if(index_v1 == -1 || index_v2 == -1) return false; edge[index_v1][index_v2] = edge[index_v2][index_v1] = 0; --num_edges; return true; } template
int graph_mtx
::get_firstneighbor(const T& vert)const { int index = get_vertex_index(vert); if(index != -1){ for(int i=0; i
int graph_mtx
::get_nextneighbor(const T& vert1, const T& vert2)const { int index_v1 = get_vertex_index(vert1); int index_v2 = get_vertex_index(vert2); if(index_v1 != -1 && index_v2 != -1){ for(int i=index_v2+1; i
int graph_mtx
::get_vertex_index(const T& vert)const { for(int i=0; i
void graph_mtx
::print_graph()const { if(this->is_empty()){ cout << "nil graph" << endl; //空图输出nil return; } for(int i=0; i
struct node{ //节点用来存储与它相连接的顶点 int dest; struct node* link; node(int d) : dest(d), link(nullptr) {} }; template
struct vertex{ //顶点结构体 T vert; //顶点 struct node
* adj; //指向描述其他节点的链表 vertex() : vert(T()), adj(nullptr) {} }; template
class graph_lnk : public graph
{ public: graph_lnk(int); ~graph_lnk(); public: bool insert_vertex(const T& vert); bool insert_edge(const T& vert1, const T& vert2); bool remove_vertex(const T& vert); bool remove_edge(const T& vert1, const T& vert2); int get_firstneighbor(const T& vert)const; int get_nextneighbor(const T& vert1, const T& vert2)const; void print_graph()const; int get_vertex_index(const T& vert)const; protected: void remove_point_self(const int, const int); void modify_point_self(const int, const int, const int); private: vertex
* vertices_table; }; template
graph_lnk
::graph_lnk(int sz = VERTICES_DEFAULT_SIZE) { max_vertices = sz > max_vertices sz : VERTICES_DEFAULT_SIZE; vertices_table = new vertex
[max_vertices]; //不用再清空，结构体构造函数已清空 num_vertices = 0; num_edges = 0; } template
graph_lnk
::~graph_lnk() { for(int i=0; i
link; delete tmp; tmp = next_tmp; } } delete []vertices_table; //删除表 } template
bool graph_lnk
::insert_vertex(const T& vert) { if(this->is_full()) return false; vertices_table[num_vertices++].vert = vert; return true; } template
bool graph_lnk
::insert_edge(const T& vert1, const T& vert2) { if(this->is_full()) return false; int index_v1 = get_vertex_index(vert1); int index_v2 = get_vertex_index(vert2); if(index_v1 == -1 || index_v2 == -1) return false; auto tmp = vertices_table[index_v1].adj; while(tmp != nullptr){ if(tmp->dest == index_v2) return false; tmp = tmp->link; } tmp = new node
(index_v2); //采用前插法，比尾插法效率高，省事 tmp->link = vertices_table[index_v1].adj; vertices_table[index_v1].adj = tmp; tmp = new node
(index_v1); tmp->link = vertices_table[index_v2].adj; vertices_table[index_v2].adj = tmp; ++num_edges; return true; } template
bool graph_lnk
::remove_vertex(const T& vert) { int index = get_vertex_index(vert); int edge_count = 0; if(index == -1) return false; auto tmp = vertices_table[index].adj; auto next_tmp = tmp; while(tmp != nullptr){ remove_point_self(index, tmp->dest); //删除目标顶点指向自己的节点 ++edge_count; //记录边数 next_tmp = tmp->link; delete tmp; tmp = next_tmp; } if(index != num_vertices-1){ vertices_table[index].adj = vertices_table[num_vertices-1].adj; //用最后一个顶点覆盖要删除的顶点 vertices_table[index].vert = vertices_table[num_vertices-1].vert; } tmp = vertices_table[index].adj; w |