使用這樣的結構存儲鄰接表：

QVector<QVector<Point>> m_adj;

Point存儲當前頂點號及X軸，Y軸：

struct Point{Point(int vNum, int x, int y) {this->vNum = vNum;this->x = x;this->y = y;}int vNum = -1; //頂點號int x; //x軸int y; //y軸 };

這里棋盤是這樣的，如下：

#define MAX_COLUMN 6 + 2 #define MAX_ROW 6 + 2//棋牌用-1包住，保證處理的統一 int map1[MAX_ROW][MAX_COLUMN] = {-1, -1, -1, -1, -1, -1, -1, -1,-1, 1, 0, -1, -1, -1, -1, -1,-1, -1, 0, -1, -1, -1, -1, -1,-1, -1, 0, -1, -1, -1, -1, -1,-1, -1, 0, -1, -1, -1, -1, -1,-1, 1, 0, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, -1, -1 };

這里的算法很簡單：

//左上 if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y - 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y - 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);} }//正上 if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);} }//右上 if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y + 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y + 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);} }//正右 if (m_map[this->m_adj[i][0].x][this->m_adj[i][0].y + 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x, this->m_adj[i][0].y + 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);} }//右下 if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y + 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y + 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);} }//正下 if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);} }//左下 if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y - 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y - 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);} }//正左 if (m_map[this->m_adj[i][0].x][this->m_adj[i][0].y - 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x, this->m_adj[i][0].y - 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);} }

程序運行截圖如下；

這樣的棋盤：

int map1[MAX_ROW][MAX_COLUMN] = {-1, -1, -1, -1, -1, -1, -1, -1,-1, 1, 0, -1, -1, -1, -1, -1,-1, -1, 0, -1, -1, -1, -1, -1,-1, -1, 0, -1, -1, -1, -1, -1,-1, -1, 0, -1, -1, -1, -1, -1,-1, 1, 0, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, -1, -1 };

下面這種棋盤：

int map1[MAX_ROW][MAX_COLUMN] = {-1, -1, -1, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, 1, -1,-1, -1, -1, -1, -1, -1, 0, -1,-1, -1, -1, -1, -1, -1, 0, -1,-1, -1, -1, -1, -1, -1, 0, -1,-1, -1, -1, -1, 1, 0, 1, -1,-1, -1, -1, -1, -1, -1, -1, -1 };

運行截圖如下：

完整源碼如下：

#include <QDebug> #include <QVector>#define MAX_COLUMN 6 + 2 #define MAX_ROW 6 + 2//棋牌用-1包住，保證處理的統一 int map1[MAX_ROW][MAX_COLUMN] = {-1, -1, -1, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, -1, -1,-1, -1, -1, -1, -1, -1, 1, -1,-1, -1, -1, -1, -1, -1, 0, -1,-1, -1, -1, -1, -1, -1, 0, -1,-1, -1, -1, -1, -1, -1, 0, -1,-1, -1, -1, -1, 1, 0, 1, -1,-1, -1, -1, -1, -1, -1, -1, -1 };struct Point{Point(int vNum, int x, int y) {this->vNum = vNum;this->x = x;this->y = y;}int vNum = -1; //頂點號int x; //x軸int y; //y軸 };class Graph {public:Graph(int map[MAX_ROW][MAX_COLUMN]) {memcpy(m_map, map, sizeof(m_map));//不為-1的都是頂點int vCount = 0;for (int i = 0; i < MAX_ROW; i++) {for (int j = 0; j < MAX_COLUMN; j++) {if (map[i][j] != -1) {Point point(++vCount, i, j);QVector<Point> ve;ve.append(point);m_adj.append(ve);}}}if (vCount == 0) {qDebug() << "退出" << endl;exit(-1);}this->m_v = vCount;analysisEdge();}//打印鄰接表void print() {for (int i = 0; i < this->m_v; ++i) {qDebug() << "頂點:" << this->m_adj[i][0].vNum << " x:" << this->m_adj[i][0].x << " y:" << this->m_adj[i][0].y << " 的鄰接表!";for (int j = 0; j < this->m_adj[i].size(); j++) {qDebug() << "頂點:" << this->m_adj[i][j].vNum << " x:" << this->m_adj[i][j].x << " y:" << this->m_adj[i][j].y;}qDebug() << "------------------------------------";}}protected://通過坐標獲取頂點號Point getPointByPosXAndPosY(int x, int y) {for (int i = 0; i < this->m_v; i++) {if (this->m_adj[i][0].x == x && this->m_adj[i][0].y == y) {return this->m_adj[i][0];}}return Point(-1, -1, -1);}void analysisEdge() {//分析下邊，這個頂點，如果周圍一圈都是非-1的數，說明都可達。for (int i = 0; i < this->m_v; i++) {//左上if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y - 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y - 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);}}//正上if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);}}//右上if (m_map[this->m_adj[i][0].x - 1][this->m_adj[i][0].y + 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x - 1, this->m_adj[i][0].y + 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);}}//正右if (m_map[this->m_adj[i][0].x][this->m_adj[i][0].y + 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x, this->m_adj[i][0].y + 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);}}//右下if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y + 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y + 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);}}//正下if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);}}//左下if (m_map[this->m_adj[i][0].x + 1][this->m_adj[i][0].y - 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x + 1, this->m_adj[i][0].y - 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);}}//正左if (m_map[this->m_adj[i][0].x][this->m_adj[i][0].y - 1] != -1) {Point point = getPointByPosXAndPosY(this->m_adj[i][0].x, this->m_adj[i][0].y - 1);if (point.vNum != -1) {//頂點是從1開始算，但下標是從0開始m_adj[this->m_adj[i][0].vNum - 1].push_back(point);}}}}private:int m_v; //頂點的個數int m_map[MAX_ROW][MAX_COLUMN];QVector<QVector<Point>> m_adj; };int main(int argc, char *argv[]) {Graph g(map1);g.print();getchar();return 0; }

還有一種是用-1包住棋盤，這樣就更加方便了，在下一篇筆記中將會說明！

總結

以上是生活随笔為你收集整理的C++笔记-二维棋盘数组转邻接表（使用QTL）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。