C++繼承實現(xiàn)鄰接矩陣和鄰接表
1、圖的父類
成都創(chuàng)新互聯(lián)公司專注于綏江網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供綏江營銷型網(wǎng)站建設(shè)，綏江網(wǎng)站制作、綏江網(wǎng)頁設(shè)計、綏江網(wǎng)站官網(wǎng)定制、小程序設(shè)計服務(wù)，打造綏江網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供綏江網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。
是一個抽象類，不能實類化對象，應(yīng)具有的是抽象方法，提供一個接口，在由子類繼承，實現(xiàn)自己的方法，
應(yīng)提供的共有抽象方法和保護的數(shù)據(jù)：
public: virtual bool insertVertex(const Type &v) = 0; //插入頂點 virtual bool insertEdge(const Type &v1, const Type &v2) = 0; //插入邊 virtual bool removeVertex(const Type &v) = 0; //刪除頂點 virtual bool removeEdge(const Type &v1, const Type &v2) = 0; //刪除邊 virtual int getFirstNeighbor(const Type &v) = 0; //得到第一個相鄰頂點 virtual int getNextNeighbor(const Type &v, const Type &w) = 0; //得到下一個相鄰頂點 public: virtual int getVertexIndex(const Type &v)const = 0; //得到頂點下標 virtual void showGraph()const = 0; //顯示圖 protected: int maxVertices; //最大頂點數(shù) int curVertices; //當前頂點數(shù) int curEdges; //當前邊數(shù)
2、子類繼承、實現(xiàn)自己的方法
C++實現(xiàn)，繼承的體現(xiàn)，是為了實現(xiàn)多態(tài)
(1)Graph.h
#ifndef _GRAPH_H_
#define _GRAPH_H_
#include<iostream>
using namespace std;
#define VERTEX_DEFAULT_SIZE 10
template<typename Type>
class Graph{
public:
bool isEmpty()const{
return curVertices == 0;
}
bool isFull()const{
if(curVertices >= maxVertices || curEdges >= curVertices*(curVertices-1)/2)
return true; //圖滿有2種情況：(1)、當前頂點數(shù)超過了最大頂點數(shù)，存放頂點的空間已滿
return false; //(2)、當前頂點數(shù)并沒有滿，但是當前頂點所能達到的邊數(shù)已滿
}
int getCurVertex()const{
return curVertices;
}
int getCurEdge()const{
return curEdges;
}
public:
virtual bool insertVertex(const Type &v) = 0; //插入頂點
virtual bool insertEdge(const Type &v1, const Type &v2) = 0; //插入邊
virtual bool removeVertex(const Type &v) = 0; //刪除頂點
virtual bool removeEdge(const Type &v1, const Type &v2) = 0; //刪除邊
virtual int getFirstNeighbor(const Type &v) = 0; //得到第一個相鄰頂點
virtual int getNextNeighbor(const Type &v, const Type &w) = 0; //得到下一個相鄰頂點
public:
virtual int getVertexIndex(const Type &v)const = 0; //得到頂點下標
virtual void showGraph()const = 0; //顯示圖
protected:
int maxVertices; //最大頂點數(shù)
int curVertices; //當前頂點數(shù)
int curEdges; //當前邊數(shù)
};
///////////////////////////////////////////////////下面先是鄰接矩陣
template<typename Type>
class GraphMtx : public Graph<Type>{ //鄰接矩陣繼承父類矩陣
#define maxVertices Graph<Type>::maxVertices //因為是模板，所以用父類的數(shù)據(jù)或方法都得加上作用域限定符
#define curVertices Graph<Type>::curVertices
#define curEdges Graph<Type>::curEdges
public:
GraphMtx(int vertexSize = VERTEX_DEFAULT_SIZE){ //初始化鄰接矩陣
maxVertices = vertexSize > VERTEX_DEFAULT_SIZE ? vertexSize : VERTEX_DEFAULT_SIZE;
vertexList = new Type[maxVertices]; //申請頂點空間
for(int i = 0; i < maxVertices; i++){ //都初始化為0
vertexList[i] = 0;
}
edge = new int*[maxVertices]; //申請邊的行
for(i = 0; i < maxVertices; i++){ //申請列空間
edge[i] = new int[maxVertices];
}
for(i = 0; i < maxVertices; i++){ //賦初值為0
for(int j = 0; j < maxVertices; j++){
edge[i][j] = 0;
}
}
curVertices = curEdges = 0; //當前頂點和當前邊數(shù)
}
GraphMtx(Type (*mt)[4], int sz){ //通過已有矩陣的初始化
int e = 0; //統(tǒng)計邊數(shù)
maxVertices = sz > VERTEX_DEFAULT_SIZE ? sz : VERTEX_DEFAULT_SIZE;
vertexList = new Type[maxVertices]; //申請頂點空間
for(int i = 0; i < maxVertices; i++){ //都初始化為0
vertexList[i] = 0;
}
edge = new int*[maxVertices]; //申請邊的行
for(i = 0; i < maxVertices; i++){ //申請列空間
edge[i] = new Type[maxVertices];
}
for(i = 0; i < maxVertices; i++){ //賦初值為矩陣當中的值
for(int j = 0; j < maxVertices; j++){
edge[i][j] = mt[i][j];
if(edge[i][j] != 0){
e++; //統(tǒng)計列的邊數(shù)
}
}
}
curVertices = sz;
curEdges = e/2;
}
~GraphMtx(){}
public:
bool insertVertex(const Type &v){
if(curVertices >= maxVertices){
return false;
}
vertexList[curVertices++] = v;
return true;
}
bool insertEdge(const Type &v1, const Type &v2){
int maxEdges = curVertices*(curVertices-1)/2;
if(curEdges >= maxEdges){
return false;
}
int v = getVertexIndex(v1);
int w = getVertexIndex(v2);
if(v==-1 || w==-1){
cout<<"edge no exit"<<endl; //要插入的頂點不存在，無法插入
return false;
}
if(edge[v][w] != 0){ //當前邊已經(jīng)存在，不能進行插入
return false;
}
edge[v][w] = edge[w][v] = 1; //因為是無向圖，對稱的，存在邊賦為1；
return true;
} //刪除頂點的高效方法
bool removeVertex(const Type &v){
int i = getVertexIndex(v);
if(i == -1){
return false;
}
vertexList[i] = vertexList[curVertices-1];
int edgeCount = 0;
for(int k = 0; k < curVertices; k++){
if(edge[i][k] != 0){ //統(tǒng)計刪除該行的邊數(shù)
edgeCount++;
}
}
//刪除行
for(int j = 0; j < curVertices; j++){
edge[i][j] = edge[curVertices-1][j];
}
//刪除列
for(j = 0; j < curVertices; j++){
edge[j][i] = edge[j][curVertices-1];
}
curVertices--;
curEdges -= edgeCount;
return true;
}
/* //刪除頂點用的是數(shù)組一個一個移動的方法，效率太低。
bool removeVertex(const Type &v){
int i = getVertexIndex(v);
if(i == -1){
return false;
}
for(int k = i; k < curVertices-1; ++k){
vertexList[k] = vertexList[k+1];
}
int edgeCount = 0;
for(int j = 0; j < curVertices; ++j){
if(edge[i][j] != 0)
edgeCount++;
}
for(int k = i; k < curVertices-1; ++k)
{
for(int j = 0; j < curVertices; ++j)
{
edge[k][j] = edge[k+1][j];
}
}
for(int k = i; k < curVertices-1; ++k)
{
for(int j = 0; j < curVertices; ++j)
{
edge[j][k] = edge[j][k+1];
}
}
curVertices--;
curEdges -= edgeCount;
return true;
}
*/
bool removeEdge(const Type &v1, const Type &v2){
int v = getVertexIndex(v1);
int w = getVertexIndex(v2);
if(v==-1 || w==-1){ //判斷要刪除的邊是否在當前頂點內(nèi)
return false; //頂點不存在
}
if(edge[v][w] == 0){ //這個邊根本不存在，沒有必要刪
return false;
}
edge[v][w] = edge[w][v] = 0; //刪除這個邊賦值為0，代表不存在；
curEdges--;
return true;
}
int getFirstNeighbor(const Type &v){
int i = getVertexIndex(v);
if(i == -1){
return -1;
}
for(int col = 0; col < curVertices; col++){
if(edge[i][col] != 0){
return col;
}
}
return -1;
}
int getNextNeighbor(const Type &v, const Type &w){
int i = getVertexIndex(v);
int j = getVertexIndex(w);
if(i==-1 || j==-1){
return -1;
}
for(int col = j+1; col < curVertices; col++){
if(edge[i][col] != 0){
return col;
}
}
return -1;
}
public:
void showGraph()const{
if(curVertices == 0){
cout<<"Nul Graph"<<endl;
return;
}
for(int i = 0; i < curVertices; i++){
cout<<vertexList[i]<<" ";
}
cout<<endl;
for(i = 0; i < curVertices; i++){
for(int j = 0; j < curVertices; j++){
cout<<edge[i][j]<<" ";
}
cout<<vertexList[i]<<endl;
}
}
int getVertexIndex(const Type &v)const{
for(int i = 0; i < curVertices; i++){
if(vertexList[i] == v){
return i;
}
}
return -1;
}
private:
Type *vertexList; //存放頂點的數(shù)組
int **edge; //存放頂點關(guān)系的矩陣用邊表示
};
///////////////////////////////////////////////////////////////下面是鄰接表
template<typename Type>
class Edge{ //邊的存儲結(jié)構(gòu)
public:
Edge(int num) : dest(num), link(NULL){}
public:
int dest;
Edge *link;
};
template<typename Type>
class Vertex{ //頂點的存儲結(jié)構(gòu)
public:
Type data;
Edge<Type> *adj;
};
template<typename Type>
class GraphLnk : public Graph<Type>{
#define maxVertices Graph<Type>::maxVertices //因為是模板，所以用父類的數(shù)據(jù)或方法都得加上作用域限定符
#define curVertices Graph<Type>::curVertices
#define curEdges Graph<Type>::curEdges
public:
GraphLnk(int sz = VERTEX_DEFAULT_SIZE){
maxVertices = sz > VERTEX_DEFAULT_SIZE ? sz : VERTEX_DEFAULT_SIZE;
vertexTable = new Vertex<Type>[maxVertices];
for(int i = 0; i < maxVertices; i++){
vertexTable[i].data = 0;
vertexTable[i].adj = NULL;
}
curVertices = curEdges = 0;
}
public:
bool insertVertex(const Type &v){
if(curVertices >= maxVertices){
return false;
}
vertexTable[curVertices++].data = v;
return true;
}
bool insertEdge(const Type &v1, const Type &v2){
int v = getVertexIndex(v1);
int w = getVertexIndex(v2);
if(v==-1 || w==-1){
return false;
}
Edge<Type> *p = vertexTable[v].adj;
while(p != NULL){ //這里主要判斷邊是否已經(jīng)存在
if(p->dest == w){ //無向圖，判斷一邊即可;
return false;
}
p = p->link;
}
//v1-->v2 //采用頭插
Edge<Type> *s = new Edge<Type>(w);
s->link = vertexTable[v].adj;
vertexTable[v].adj = s;
//v2-->v1 //采用頭插
Edge<Type> *q = new Edge<Type>(v);
q->link = vertexTable[w].adj;
vertexTable[w].adj = q;
curEdges++;
return true;
}
bool removeVertex(const Type &v){
int i = getVertexIndex(v);
if(i == -1){
return false;
}
Edge<Type> *p = vertexTable[i].adj;
while(p != NULL){
vertexTable[i].adj = p->link;
int k = p->dest;
Edge<Type> *q = vertexTable[k].adj;
if(q->dest == i){
vertexTable[k].adj = q->link;
delete q;
}else{
while(q->link != NULL && q->link->dest != i){
q = q->link;
}
Edge<Type> *t = q->link;
q->link = t->link;
delete t;
}
delete p;
p = vertexTable[i].adj;
curEdges--;
}
curVertices--; //下面實行覆蓋
vertexTable[i].data = vertexTable[curVertices].data;
vertexTable[i].adj = vertexTable[curVertices].adj;
vertexTable[curVertices].adj = NULL;
int k = curVertices;
p = vertexTable[i].adj;
while(p != NULL){
Edge<Type> *s = vertexTable[p->dest].adj;
while(s != NULL){
if(s->dest == k){
s->dest = i;
break;
}
s = s->link;
}
p = p->link;
}
return true;
}
bool removeEdge(const Type &v1, const Type &v2){
int i = getVertexIndex(v1);
int j = getVertexIndex(v2);
if(i==-1 || j==-1){ //保證頂點的保存在
return false;
}
//v1-->v2
Edge<Type> *p = vertexTable[i].adj;
if(p == NULL){ //判斷有沒有邊
return false;
}
if(p->link == NULL && p->dest == j){ //刪除的是第一個邊，其后沒有邊了；
vertexTable[i].adj = NULL;
delete p;
}else if(p->dest == j){ //刪除的是第一個邊,并且其后還有邊
vertexTable[i].adj = p->link;
delete p;
}else{
while(p->link != NULL){
if(p->link->dest == j){
Edge<Type> *q = p->link;
p->link = q->link;
delete q;
}
p = p->link;
}
}
//v2-->v1
Edge<Type> *s = vertexTable[j].adj;
if(s == NULL){ //判斷有沒有邊
return false;
}
if(s->link == NULL && s->dest == i){ //刪除的是第一個邊，其后沒有邊了；
vertexTable[j].adj = NULL;
delete s;
curEdges--;
return false;
}else if(s->dest == i){ //刪除的是第一個邊,并且其后還有邊
vertexTable[j].adj = s->link;
delete s;
curEdges--;
return true;
}else{
while(s->link != NULL){
if(s->link->dest == i){
Edge<Type> *q = s->link;
s->link = q->link;
delete q;
curEdges--;
return true;
}
s = s->link;
}
}
return true;
}
int getFirstNeighbor(const Type &v){
int i = getVertexIndex(v);
if(i != -1){
Edge<Type> *p = vertexTable[i].adj;
if(p != NULL){
return p->dest;
}
}
return -1;
}
int getNextNeighbor(const Type &v, const Type &w){
int i = getVertexIndex(v);
int j = getVertexIndex(w);
if(i==-1 || j==-1){
return -1;
}
Edge<Type> *p = vertexTable[i].adj;
while(p != NULL){
if(p->dest == j && p->link != NULL){
return p->link->dest;
}
p = p->link;
}
return -1;
}
public:
int getVertexIndex(const Type &v)const{
for(int i = 0; i < curVertices; i++){
if(vertexTable[i].data == v){
return i;
}
}
return -1;
}
void showGraph()const{
for(int i = 0; i < curVertices; i++){
cout<<vertexTable[i].data<<":-->";
Edge<Type> *p = vertexTable[i].adj;
while(p != NULL){
cout<<p->dest<<"-->";
p = p->link;
}
cout<<"Nul. "<<endl;
}
}
private:
Vertex<Type> *vertexTable; //指向頂點的指針，是申請數(shù)組用的
};
#endif(2)、Graph.cpp
#include"Graph.h"
int main(void){
GraphMtx<char> gm; //鄰接矩陣
gm.insertVertex('A'); //插入頂點
gm.insertVertex('B');
gm.insertVertex('C');
gm.insertVertex('D');
gm.insertEdge('A','B'); //插入邊
gm.insertEdge('A','D');
gm.insertEdge('B','C');
gm.insertEdge('C','D');
cout<<gm.getFirstNeighbor('A')<<endl; //B
cout<<gm.getNextNeighbor('A','B')<<endl;//D
gm.showGraph();
gm.removeEdge('A','B');
gm.removeVertex('B');
cout<<"-----------------------------------------------------------------"<<endl;
gm.showGraph();
///////////////////////////////////////////////////////////////////////////////////////////
GraphLnk<char> gl; //鄰接表
gl.insertVertex('A');
gl.insertVertex('B');
gl.insertVertex('C');
gl.insertVertex('D');
gl.insertEdge('A','B');
gl.insertEdge('A','D');
gl.insertEdge('B','C');
gl.insertEdge('C','D');
gl.showGraph();
cout<<gl.getFirstNeighbor('A')<<endl;
cout<<gl.getNextNeighbor('A','B')<<endl;
gl.removeEdge('B','C');
cout<<"---------------------"<<endl;
gl.removeVertex('B');
gl.showGraph();
return 0;
}3、鄰接多重表
是一個十字交叉鏈的形式；在很大程度上節(jié)省了空間，還是要對鏈表的操作很熟悉；
當前標題：C++繼承實現(xiàn)鄰接矩陣和鄰接表
文章源于：http://muchs.cn/article16/jojegg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、做網(wǎng)站、移動網(wǎng)站建設(shè)、、網(wǎng)站排名、網(wǎng)站改版
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
- 深圳網(wǎng)站建設(shè)公司的規(guī)模多大比較好 2015-10-30
- 成都HTML5網(wǎng)站建設(shè)中的優(yōu)勢 2017-11-04
- 網(wǎng)站建設(shè)中字體的搭配遵循的原則 2022-06-21
- 企業(yè)網(wǎng)站建設(shè)過程中有問題出現(xiàn)不一定非得要面對面溝通 2022-05-24
- 上海網(wǎng)站建設(shè)成本剖析之 人力成本 2022-09-18
- 廣東網(wǎng)站建設(shè)流程繁瑣嗎?如何選擇網(wǎng)站建設(shè)公司 2022-08-29
- 成都網(wǎng)站建設(shè)-面向搜索引擎的網(wǎng)站建設(shè)怎么做 2016-11-06
- 為成都網(wǎng)站建設(shè)添加網(wǎng)站外鏈的十五個方法 2016-08-12
- 濱州網(wǎng)站建設(shè)-網(wǎng)站設(shè)計的版式要求 2021-11-13
- 網(wǎng)上商城網(wǎng)站建設(shè)需要注意哪些東西呢？ 2016-01-07
- 金華網(wǎng)站制作_網(wǎng)站建設(shè)_制作網(wǎng)站_網(wǎng)站優(yōu)化 2023-03-28
- 【網(wǎng)站建設(shè)】域名詐騙手法之“中文域名”過期續(xù)費 2022-05-03