文章目錄
- 前言
- 一、各部分代碼展示
- 1.鄰接矩陣的構造
- 2.鄰接表的構造
- 3.十字鏈表的構造
- 4.鄰接多重表的構造
- 二、 完整代碼
前言
新人菜鳥的第一篇博客，有問題歡迎大家交流指正
一、各部分代碼展示
1.鄰接矩陣的構造
Graph::Graph(int *vertexarray, int *nameofvertex, int numberofvertex)//鄰接矩陣的建構式
{
vertexnum2 = numberofvertex;
for (int i = 0; i < vertexnum2; i++)
{
vertexname.push_back(nameofvertex[i]);
}
adjacencyMatrix.resize(vertexnum2, vector<int>(vertexnum2));
for (int i = 0; i < vertexnum2; i++)
for (int j = 0; j < vertexnum2; j++)
adjacencyMatrix[i][j] = *(vertexarray + i * vertexnum2 + j);
}
2.鄰接表的構造
Graph::Graph(int *arcarray, char *arcofname, int numofvertex, int numberofarc)//鄰接表的建構式
{
this->arcnum1 = numberofarc;
this->vertexnum1 = numofvertex;
vertexNode tempvernode;
for (int i = 0; i < vertexnum1; i++)
{
tempvernode.vertexname = arcofname[i];
tempvernode.firstedge = NULL;
tempvernode.visited = false;
adjacencylist.push_back(tempvernode);
}
for (int i = 0; i < arcnum1*3; i+=3)
{
ArcNode *parcnode = new ArcNode;
int arctailindex;
arctailindex = *(arcarray + i+0);
parcnode->adjvex = *(arcarray +i+1);
parcnode->weight = *(arcarray + i+2);
parcnode->next = adjacencylist[arctailindex].firstedge;
adjacencylist[arctailindex].firstedge = parcnode;
}
}
3.十字鏈表的構造
Graph::Graph(int *matrix, char *nameofvertex, int numberofvertex, int numberofarc,int sigh)//十字鏈表的構造
{
ortharcnode* ptemp;
orthvertexnode tempvexnode;
if (!orthgrapharray.empty())
vector<orthvertexnode>().swap(orthgrapharray);//建立并初始化表頭向量
for (int i = 0; i < numberofvertex; i++)
{
tempvexnode.data = nameofvertex[i];
tempvexnode.firstin = NULL;
tempvexnode.firstout = NULL;
orthgrapharray.push_back(tempvexnode);
}
for(int i = 0 ; i < numberofvertex ; i++)
for(int j = 0 ; j < numberofvertex ; j++)
if (matrix[i*numberofvertex + j] != 0)//如果i行j列非零
{
ortharcnode* portharcnode = new ortharcnode;//生成十字鏈表弧結點
portharcnode->tailvex = i;
portharcnode->headvex = j;
portharcnode->headlink = NULL;
portharcnode->taillink = NULL;
//插入行鏈表
if (orthgrapharray[i].firstout == NULL || orthgrapharray[i].firstout->headvex > j)
{
portharcnode->taillink = orthgrapharray[i].firstout;
orthgrapharray[i].firstout = portharcnode;
}
else
{
//尋找行插入的位置
for (ptemp = orthgrapharray[i].firstout; (ptemp->taillink != NULL) && ptemp->taillink->headvex < j; ptemp = ptemp->taillink);
portharcnode->taillink = ptemp->taillink;
ptemp->taillink = portharcnode;
}
//插入列向量
if (orthgrapharray[j].firstin == NULL || orthgrapharray[j].firstin->tailvex > i)
{
portharcnode->headlink = orthgrapharray[j].firstin;
orthgrapharray[j].firstin = portharcnode;
}
else
{
//尋找列插入的位置
for (ptemp = orthgrapharray[j].firstin; (ptemp->headlink != NULL) && ptemp->headlink->tailvex < i; ptemp = ptemp->headlink);
portharcnode->headlink = ptemp->headlink;
ptemp->headlink - portharcnode;
}
}
}
4.鄰接多重表的構造
Graph::Graph(int *matrix, char *nameofvertex, int numberofvertex)//鄰接多重表的構造
{
multilistedgenode* ptemp;
multilistvexnode tempvexnode;
if (!multilistgrapharray.empty())
vector<multilistvexnode>().swap(multilistgrapharray);//建立并初始化表頭向量
for (int i = 0; i < numberofvertex; i++)
{
tempvexnode.data = nameofvertex[i];
tempvexnode.firstedge = NULL;
multilistgrapharray.push_back(tempvexnode);
}
for (int i = 0; i < numberofvertex; i++)
{
for (int j = i + 1; j < numberofvertex; j++)
{
if (matrix[i*numberofvertex + j] != 0)
{
//生成鄰接多重表節點
multilistedgenode* pmultilistedgenode = new multilistedgenode;
pmultilistedgenode->ivex = i;
pmultilistedgenode->jvex = j;
pmultilistedgenode->ilink = NULL;
pmultilistedgenode->jlink = NULL;
//插入行鏈表
pmultilistedgenode->ilink = multilistgrapharray[i].firstedge;
multilistgrapharray[i].firstedge = pmultilistedgenode;
//插入列鏈表
pmultilistedgenode->jlink = multilistgrapharray[j].firstedge;
multilistgrapharray[j].firstedge = pmultilistedgenode;
}
}
}
}
二、 完整代碼
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<stdio.h>
using namespace std;
struct ArcNode//定義弧標節點
{
int adjvex;
int weight;
ArcNode *next;
};
struct vertexNode//定義頂點表節點
{
char vertexname;
bool visited;
int inDegree;
ArcNode *firstedge;
};
struct ortharcnode//十字鏈表弧節點結構體定義
{
int tailvex, headvex;//弧尾和弧頭的編號
ortharcnode *headlink;//弧頭相同的下一潭訓
ortharcnode *taillink;//弧尾相同的下一潭訓
};
struct orthvertexnode//十字鏈表頭節點結構體定義
{
char data;//頂點資訊
ortharcnode *firstin;//頂點的第一條入邊
ortharcnode *firstout;//弧尾相同的下一潭訓
};
struct multilistedgenode//鄰接多重表邊結構體定義
{
int ivex, jvex;//弧尾和弧頭的編號
multilistedgenode *ilink;//弧頭相同的下一潭訓
multilistedgenode *jlink;//弧尾相同的下一潭訓
};
struct multilistvexnode//鄰接多重表頂點結構體定義
{
char data;//頂點資訊
multilistedgenode *firstedge;//第一條依附頂點的邊
};
class Graph
{
public:
Graph(int *arcarray, char *arcofname, int numofvertex, int numberofarc);//構造鄰接表
Graph(int *vertexarray, int *nameofvertex, int numberofvertex);//構造鄰接矩陣
Graph(int *matrix, char *nameofvertex, int numberofvertex, int numberofarc,int sign);//構造十字鏈表(sigh的作用是與鄰接表的構造區分開）
Graph(int *matrix, char *nameofvertex, int numberofvertex);//構造鄰接多重表
void printadjacencylist();//鄰接表的輸出
void printmatrix();//鄰接矩陣的輸出
void printorthlistgraph();//十字鏈表的輸出
void printmultilistgraph();//鄰接多重表的輸出
private:
vector<char> vertexname;//鄰接矩陣頂點表
vector<vector<int>> adjacencyMatrix;//鄰接矩陣
vector <vertexNode> adjacencylist;//存放圖中的頂點和陣列
vector<orthvertexnode> orthgrapharray;//十字鏈表表頭向量
vector<multilistvexnode> multilistgrapharray;//鄰接多重表表頭向量
int vertexnum1, arcnum1;//圖的頂點數和弧度
int vertexnum2, arcnum2;//圖的頂點數和邊數
int rows, cols, numbers;//稀疏矩陣行數，列數，非零元素個數
};
Graph::Graph(int *arcarray, char *arcofname, int numofvertex, int numberofarc)//鄰接表的建構式
{
this->arcnum1 = numberofarc;
this->vertexnum1 = numofvertex;
vertexNode tempvernode;
for (int i = 0; i < vertexnum1; i++)
{
tempvernode.vertexname = arcofname[i];
tempvernode.firstedge = NULL;
tempvernode.visited = false;
adjacencylist.push_back(tempvernode);
}
for (int i = 0; i < arcnum1*3; i+=3)
{
ArcNode *parcnode = new ArcNode;
int arctailindex;
arctailindex = *(arcarray + i+0);
parcnode->adjvex = *(arcarray +i+1);
parcnode->weight = *(arcarray + i+2);
parcnode->next = adjacencylist[arctailindex].firstedge;
adjacencylist[arctailindex].firstedge = parcnode;
}
}
Graph::Graph(int *vertexarray, int *nameofvertex, int numberofvertex)//鄰接矩陣的建構式
{
vertexnum2 = numberofvertex;
for (int i = 0; i < vertexnum2; i++)
{
vertexname.push_back(nameofvertex[i]);
}
adjacencyMatrix.resize(vertexnum2, vector<int>(vertexnum2));
for (int i = 0; i < vertexnum2; i++)
for (int j = 0; j < vertexnum2; j++)
adjacencyMatrix[i][j] = *(vertexarray + i * vertexnum2 + j);
}
Graph::Graph(int *matrix, char *nameofvertex, int numberofvertex, int numberofarc,int sigh)//十字鏈表的構造
{
ortharcnode* ptemp;
orthvertexnode tempvexnode;
if (!orthgrapharray.empty())
vector<orthvertexnode>().swap(orthgrapharray);//建立并初始化表頭向量
for (int i = 0; i < numberofvertex; i++)
{
tempvexnode.data = nameofvertex[i];
tempvexnode.firstin = NULL;
tempvexnode.firstout = NULL;
orthgrapharray.push_back(tempvexnode);
}
for(int i = 0 ; i < numberofvertex ; i++)
for(int j = 0 ; j < numberofvertex ; j++)
if (matrix[i*numberofvertex + j] != 0)//如果i行j列非零
{
ortharcnode* portharcnode = new ortharcnode;//生成十字鏈表弧結點
portharcnode->tailvex = i;
portharcnode->headvex = j;
portharcnode->headlink = NULL;
portharcnode->taillink = NULL;
//插入行鏈表
if (orthgrapharray[i].firstout == NULL || orthgrapharray[i].firstout->headvex > j)
{
portharcnode->taillink = orthgrapharray[i].firstout;
orthgrapharray[i].firstout = portharcnode;
}
else
{
//尋找行插入的位置
for (ptemp = orthgrapharray[i].firstout; (ptemp->taillink != NULL) && ptemp->taillink->headvex < j; ptemp = ptemp->taillink);
portharcnode->taillink = ptemp->taillink;
ptemp->taillink = portharcnode;
}
//插入列向量
if (orthgrapharray[j].firstin == NULL || orthgrapharray[j].firstin->tailvex > i)
{
portharcnode->headlink = orthgrapharray[j].firstin;
orthgrapharray[j].firstin = portharcnode;
}
else
{
//尋找列插入的位置
for (ptemp = orthgrapharray[j].firstin; (ptemp->headlink != NULL) && ptemp->headlink->tailvex < i; ptemp = ptemp->headlink);
portharcnode->headlink = ptemp->headlink;
ptemp->headlink - portharcnode;
}
}
}
Graph::Graph(int *matrix, char *nameofvertex, int numberofvertex)//鄰接多重表的構造
{
multilistedgenode* ptemp;
multilistvexnode tempvexnode;
if (!multilistgrapharray.empty())
vector<multilistvexnode>().swap(multilistgrapharray);//建立并初始化表頭向量
for (int i = 0; i < numberofvertex; i++)
{
tempvexnode.data = nameofvertex[i];
tempvexnode.firstedge = NULL;
multilistgrapharray.push_back(tempvexnode);
}
for (int i = 0; i < numberofvertex; i++)
{
for (int j = i + 1; j < numberofvertex; j++)
{
if (matrix[i*numberofvertex + j] != 0)
{
//生成鄰接多重表節點
multilistedgenode* pmultilistedgenode = new multilistedgenode;
pmultilistedgenode->ivex = i;
pmultilistedgenode->jvex = j;
pmultilistedgenode->ilink = NULL;
pmultilistedgenode->jlink = NULL;
//插入行鏈表
pmultilistedgenode->ilink = multilistgrapharray[i].firstedge;
multilistgrapharray[i].firstedge = pmultilistedgenode;
//插入列鏈表
pmultilistedgenode->jlink = multilistgrapharray[j].firstedge;
multilistgrapharray[j].firstedge = pmultilistedgenode;
}
}
}
}
void Graph::printadjacencylist()//鄰接表的輸出
{
cout << "圖的鄰接表表示為:" << endl;
int index;
ArcNode *curarcnode;
for (int i = 0; i < adjacencylist.size(); i++)
{
cout << adjacencylist[i].vertexname;
curarcnode = adjacencylist[i].firstedge;
if (curarcnode != NULL)
{
while (curarcnode != NULL)
{
cout << "--->" << "(" << adjacencylist[curarcnode->adjvex].vertexname << "權值為:" << curarcnode->weight << ")";
curarcnode = curarcnode->next;
}
}
else
cout << "--->" << "空";
cout << endl;
}
}
void Graph::printmatrix()//鄰接矩陣的輸出
{
cout << "圖的鄰接矩陣表示為：" << endl;
for (int i = 0; i < vertexnum2; i++)//遍歷輸出所有數值
{
for (int j = 0; j < vertexnum2; j++)
{
if (adjacencyMatrix[i][j] != 1001)
cout << adjacencyMatrix[i][j] << " ";
else
cout << "oo" << " ";
}
cout << endl;
}
}
void Graph::printorthlistgraph()//十字鏈表的輸出
{
cout << "圖十字鏈表的為:" << endl;
cout << "按行輸出為:" << endl;
for (int i = 0; i < orthgrapharray.size(); i++)
{
for (ortharcnode* ptemp = orthgrapharray[i].firstout; ptemp != NULL; ptemp = ptemp->taillink)
cout << orthgrapharray[ptemp->tailvex].data << "--->" << orthgrapharray[ptemp->headvex].data << " ";
cout << endl;
}
cout << "按列輸出為:" << endl;
for (int i = 0; i < orthgrapharray.size(); i++)
{
for (ortharcnode* ptemp = orthgrapharray[i].firstin; ptemp != NULL; ptemp = ptemp->headlink)
cout << orthgrapharray[ptemp->tailvex].data << "--->" << orthgrapharray[ptemp->headvex].data << " ";
cout << endl;
}
cout << endl;
}
void Graph::printmultilistgraph()//鄰接多重表的輸出
{
cout << "圖的鄰接多重表輸出為:" << endl;
for (int i = 0; i < multilistgrapharray.size(); i++)
{
cout << multilistgrapharray[i].data << "的鄰接點有:";
multilistedgenode* pmultilistedgenode = multilistgrapharray[i].firstedge;
while (pmultilistedgenode != NULL)
{
int index = pmultilistedgenode->ivex == i ? pmultilistedgenode->jvex : pmultilistedgenode->ivex;
cout << multilistgrapharray[index].data << " ";
pmultilistedgenode = pmultilistedgenode->ivex == i ? pmultilistedgenode->ilink : pmultilistedgenode->jlink;
}
cout << endl;
}
}
int main()
{
int G[1000], name1[10], m, n,i;
char name2[10];
cout << "請輸入指令：" << endl;
cout << "1:構造鄰接矩陣" << endl << "2:構造鄰接表" << endl << "3:構造十字鏈表" << endl << "4:構造鄰接重表" << endl<<"5:結束構造"<<endl;
while (scanf_s("%d", &i) != EOF)
{
if (i == 1)
{
cout << "請輸入節點個數" << endl;
cin >> m;
cout << "請輸入節點的名字（int型）" << endl;
for (int i = 0; i < m; i++)
cin >> name1[i];
cout << "請以"<<m<<"維矩陣的形式輸入" << endl;
for (int x = 0; x < m; x++)
for (int y = 0; y < m; y++)
cin >> G[x*m + y];
Graph A(G, name1, m);
A.printmatrix();
cout << endl;
}
else if (i == 2)
{
cout << "請輸入節點個數" << endl;
cin >> m;
cout << "請輸入弧的個數" << endl;
cin >> n;
cout << "請輸入節點的名字（char型）" << endl;
for (int j = 0; j < m; j++)
cin >> name2[j];
getchar();
cout << "請依次輸入弧的資訊（弧頭，弧尾，權重:弧頭弧尾要以int型輸入表示第幾個點）" << endl;
for (int j = 0; j < n*3; j += 3)
cin >> G[j] >> G[j + 1] >> G[j + 2];
Graph A(G, name2, m, n);
A.printadjacencylist();
cout << endl;
}
else if (i == 3)
{
cout << "請輸入節點個數" << endl;
cin >> m;
cout << "請輸入節點的名字（char型）" << endl;
for (int j = 0; j < m; j++)
cin >> name2[j];
getchar();
cout << "請以" << m << "維矩陣的形式輸入" << endl;
for (int x = 0; x < m; x++)
for (int y = 0; y < m; y++)
cin >> G[x*m + y];
Graph A(G, name2, m, m, 0);
A.printorthlistgraph();
}
else if (i == 4)
{
cout << "請輸入節點個數" << endl;
cin >> m;
cout << "請輸入節點的名字（char型）" << endl;
for (int j = 0; j < m; j++)
cin >> name2[j];
getchar();
cout << "請以" << m << "維矩陣的形式輸入" << endl;
for (int x = 0; x < m; x++)
for (int y = 0; y < m; y++)
cin >> G[x*m + y];
Graph A(G, name2, m);
A.printmultilistgraph();
}
else
return 0;
cout << "請輸入指令：" << endl;
cout << "1:構造鄰接矩陣" << endl << "2:構造鄰接表" << endl << "3:構造十字鏈表" << endl << "4:構造鄰接重表" << endl << "5:結束構造" << endl;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/246953.html
標籤：AI
上一篇：【學習筆記】專案中用到的概念名詞