C++笔记-二维棋盘数组转邻接表(使用QTL)
2021/6/29 9:20:34
本文主要是介绍C++笔记-二维棋盘数组转邻接表(使用QTL),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
使用这样的结构存储邻接表:
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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享