关于DFS使用栈，链表处理最短路径问题

关于DFS使用栈，class="superseo">链表处理最短路径问题

文章仅供学习，存在BUG

正常运行没问题
代码很水，不喜勿喷 o.o
第一次,请只运行下方代码，因为还未把数据放入文件中

//把数据写入文件中
	int row = 10, col = 10;
	int GameMap[10][10] =
	{
		{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1 },
		{ 1, 0, 1, 0, 1, 0, 0, 0, 1, 1 },
		{ 1, 0, 1, 0, 1, 0 ,1, 0, 1, 1 },
		{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
		{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 },
		{ 1, 0, 1, 0, 1, 0, 1, 1, 1, 1 },
		{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
	};
	FILE *pchar = fopen("3.Map", "wb");
	fwrite(&row, sizeof(int), 1, pchar);
	fwrite(&col, sizeof(int), 1, pchar);
	for (int i = 0; i < row; i++)
	{
		fwrite(GameMap[i], sizeof(int)*col, 1, pchar);
	}
	fclose(pchar);

Main.cpp

#include
#include 
#include 
#include 
#include "CMyPoint.h"
#include "GameMap.h"

using namespace std;
/*

作业-- - 考虑路径带环
3.找到最短路径.
思路:
找到所有路径然后全部放入MinPathList中

每条路径的有EndPoint区分开来
第一条路径大于第二条路径时候，删除第一条
当第二条路大于第一条路径的时候删除第二条

直到只剩一条路径,输出路径以及size

*/
CMyPoint *Near[4] =
{
	new CMyPoint(1, 0),
	new CMyPoint(-1, 0),
	new CMyPoint(0, -1),
	new CMyPoint(0, 1)
};

//开始的地方
CMyPoint StartPoint = { 0, 1 };//stack上一个节点
CMyPoint LastPathPoint;//记录stack的最后一个节点

CMyPoint EndPoint = { 9, 8 };//胜利点

bool IsDeadEnd = false;//是否是死胡同
bool IsVictory = false;//是否已经胜利

//使用栈来实现DFS
stack<CMyPoint> pathStack;//删节点(正常运行)
list <CMyPoint> MinPathList;//所有路径存放的链表
list <CMyPoint> LastPathList;//每条寻路最后的路径
list<CMyPoint> TempList;//临时链表，存储栈内元素

//从文件中读取数据
CGameMap *gameMap = new CGameMap("3.Map");//地图初始化

void PushStack(CMyPoint pointTemp)
{
	//判断该点周围四个点是否可以过
	for (int i = 0; i < 4; i++)
	{
		int xTemp = pointTemp.x + (*Near[i]).x;
		int yTemp = pointTemp.y + (*Near[i]).y;
		//进入点判断该店是否超过边界
		if (xTemp  < gameMap->Get_Row() && yTemp < gameMap->Get_Col() && xTemp > 0 && yTemp> 0 )
		{
			if (0 == gameMap->Get_GameMap()[pointTemp.x + (*Near[i]).x][pointTemp.y + (*Near[i]).y]
				|| 6 == gameMap->Get_GameMap()[pointTemp.x + (*Near[i]).x][pointTemp.y + (*Near[i]).y])
			{
				//将这个这个节点放入栈中
				CMyPoint pointTempTemp(pointTemp.x + (*Near[i]).x, pointTemp.y + (*Near[i]).y);
				pathStack.push(pointTempTemp);
			}
		}
	}
}
//使LastPathList遇到死胡同能够删除到下一个空地
void DelelteList()
{
	while (!LastPathList.empty())
	{
		//判断该店周围四个点是否可以过
		for (int i = 0; i < 4; i++)
		{
			int xTemp = LastPathList.back().x + (*Near[i]).x;
			int yTemp = LastPathList.back().y + (*Near[i]).y;
			//进入点判断该店是否超过边界
			if (xTemp < gameMap->Get_Row() && yTemp < gameMap->Get_Col() && xTemp > 0 && yTemp> 0)
			{
				if (0 == gameMap->Get_GameMap()[xTemp][yTemp]
					|| 6 == gameMap->Get_GameMap()[xTemp][yTemp])
				{
					return;
				}
			}
		}
		//四次循环后,发现周围没有0
		//直接删除链表最后一个节点
		//gameMap->Get_GameMap()[LastPathList.back().x][LastPathList.back().y] = 0;
		LastPathList.pop_back();
	}
	cout << "这是个死胡同" << endl;
	exit(0);
}

//最后成功的路径转入MinPathList中
void LPathToMList()
{
	list<CMyPoint>::iterator it_List = LastPathList.begin();
	for (; it_List != LastPathList.end(); ++it_List)
	{
		MinPathList.push_back(*it_List);
	}
}
//输出LastPathList路径
void DisplayLastList()
{
	static int i = 1;
	gameMap->InitMap("3.Map");
	//输出最终路径
	list<CMyPoint>::iterator it_list = LastPathList.begin();
	for (; it_list != LastPathList.end(); it_list++)
	{
		StartPoint = *it_list;
		gameMap->Get_GameMap()[StartPoint.x][StartPoint.y] = 3;
		system("CLS");
		gameMap->DisPlayMap();
	}
	cout << "第" << i++ << "条路径" << "已经成功达到胜利点" << endl;
	system("PAUSE");
}


//胜利后，让LastList删到stack最后一个节点的位置的附近
void DelelteLastToStackEnd()
{
	while (true)
	{
		for (int i = 0; i < 4; i++)
		{
			int xTemp = LastPathList.back().x + (*Near[i]).x;
			int yTemp = LastPathList.back().y + (*Near[i]).y;
			//进入点判断该店是否超过边界
			if (xTemp < gameMap->Get_Row() && yTemp < gameMap->Get_Col() && xTemp > 0 && yTemp> 0)
			{
				CMyPoint pointTemp(xTemp, yTemp);
				if (pointTemp == LastPathPoint)
				{
					//加上pathstack最后一个
					LastPathList.push_back(pathStack.top());
					return;
				}
			}
		}
		LastPathList.pop_back();
	}
}
//检查第二条路径之后下Last是否进入死胡同
void CheckDeadEnd()
{
	//看是否是死胡同就看stackTemp里面的第一个节点
	//如果不是死胡同return
	if (pathStack.top() != LastPathPoint)
	{
		return;
	}
	else
	{
		cout << "该路径为死胡同" << endl;
		//如果是死胡同
		//地图初始化
		gameMap->InitMap("3.Map");
		//lastPathlist删除到stack最后一个
		DelelteLastToStackEnd();
		//让last路径全部变成3
		list<CMyPoint>::iterator it_list = LastPathList.begin();
		for (; it_list != LastPathList.end(); it_list++)
		{
			StartPoint = *it_list;
			gameMap->Get_GameMap()[StartPoint.x][StartPoint.y] = 3;
			system("CLS");
			gameMap->DisPlayMap();
		}
	}
}

void FindMinPath()
{
	//开始找最小的路径
	list<CMyPoint>::iterator it_list = MinPathList.begin();
	list<CMyPoint>::iterator it_start1 = MinPathList.begin();
	list<CMyPoint>::iterator it_end1;
	list<CMyPoint>::iterator it_start2;
	list<CMyPoint>::iterator it_end2;
	
	int flag = 1;
	int Maxsize = 0;
	int size = 0;
	bool IsAddIt_list;
	
	while (it_list != MinPathList.end())
	{
		size++;
		IsAddIt_list = false;//是否已经自加
		if ((*it_list) == EndPoint)
		{
			++flag;
	
			if (flag == 2)//分配第一路径
			{
				it_end1 = it_list;
				it_start2 = it_list++;//★★★★这里自加了注意
				Maxsize = size;
				size = 0;
				IsAddIt_list = true;
			}
			else//之后的路径
			{
				//第一步将end2存入
				it_end2 = it_list;
				if (size > Maxsize)//第二个路径大于第一个路径
				{
					size = 0;
					it_start2 = it_list = MinPathList.erase(it_start2, it_end2);
				}
				else//第二个路径小于第一个路径
				{
					Maxsize = size;
					it_start1 = MinPathList.erase(it_start1, it_end1);
					it_end1 = it_end2;
					it_start2 = ++it_list;
					IsAddIt_list = true;
				}
			}
		}
		if (!IsAddIt_list)
		{
			it_list++;
		}
	}
	 
	gameMap->InitMap("3.Map");

	it_list = MinPathList.begin();
	for (; it_list != MinPathList.end(); it_list++)
	{
		gameMap->Get_GameMap()[(*it_list).x][(*it_list).y] = 3;
		system("CLS");
		gameMap->DisPlayMap();
	}
    cout << "最短路径如上" << endl;
	cout << "该路径长度为:" << Maxsize << endl;
}


int main()
{
	//把数据写入文件中
	int row = 10, col = 10;
	int GameMap[10][10] =
	{
		{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1 },
		{ 1, 0, 1, 0, 1, 0, 0, 0, 1, 1 },
		{ 1, 0, 1, 0, 1, 0 ,1, 0, 1, 1 },
		{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
		{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 },
		{ 1, 0, 1, 0, 1, 0, 1, 1, 1, 1 },
		{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
	};
	FILE *pchar = fopen("3.Map", "wb");
	fwrite(&row, sizeof(int), 1, pchar);
	fwrite(&col, sizeof(int), 1, pchar);
	for (int i = 0; i < row; i++)
	{
		fwrite(GameMap[i], sizeof(int)*col, 1, pchar);
	}
	fclose(pchar);
	//gameMap->MemeroyMap();

	LastPathList.push_back(StartPoint);
	while (true)
	{
		system("CLS");
		gameMap->DisPlayMap();
		//入栈
		PushStack(StartPoint);
		if (pathStack.empty())
		{
			//所有路径都被走过
			cout << "所有路径都被走过" << endl;
			system("pause");
			break;
		}
		//检测路径是否是死胡同
		CheckDeadEnd();
	
		//进入胜利点的路径链表 
		LastPathList.push_back(pathStack.top());
												
		StartPoint = pathStack.top();
		gameMap->Get_GameMap()[StartPoint.x][StartPoint.y] = 3;
		
		pathStack.pop();
	
		//该路径到达胜利点
		if (StartPoint == EndPoint)
		{
			pathStack.pop();
			//这里是显示正确
			system("CLS");
			gameMap->DisPlayMap();
			//打印路径
			DisplayLastList();
			//把最终路径放到Min路径里面取
			LPathToMList();
			if (pathStack.empty())
			{
				//所有路径都被走过
				cout << "所有路径都被走过" << endl;
				system("pause");
				break;
			}
			//把LastPath删到stack 的最后一个节点位置
			DelelteLastToStackEnd();
			IsVictory = true;
			
		}
		//记录stack最后一个节点
		if (!pathStack.empty())// 
		{
			LastPathPoint = pathStack.top();
			IsVictory = false;
		}
		//删除list里面的死胡同节点
		DelelteList(); 
	}

    gameMap->InitMap("3.Map");

    FindMinPath();

    return 0;
}

CMyPoint.h文件以及.cpp文件

#ifndef __CMYPOINT_H__
#define __CMYPOINT_H__

class CMyPoint
{
public:
	CMyPoint();
	CMyPoint(int x, int y);
	//重载 ==
	bool operator==(const CMyPoint &point);
	//重载 !=
	bool operator!=(const CMyPoint &point);

	~CMyPoint();

	int x;
	int y;
};

#endif  //__CMYPOINT_H__


#include "CMyPoint.h"
CMyPoint::CMyPoint()
{
	this->x = 0;
	this->y = 0;
}
CMyPoint::CMyPoint(int x, int y)
{
	this->x = x;
	this->y = y;
}

//重载 ==
bool CMyPoint::operator==(const CMyPoint &point)
{
	if (this->x == point.x &&this->y == point.y)
	{
		return true;
	}
	else
	{
		return false;
	}
}
//重载 !=
bool CMyPoint::operator!=(const CMyPoint &point)
{
	if (this->x == point.x &&this->y == point.y)
	{
		return false;
	}
	else
	{
		return true;
	}
}

CMyPoint::~CMyPoint()
{
}

GameMap.h文件

	#ifndef __GAMEMAP_H__
	#define __GAMEMAP_H__
	
	
	class CGameMap
	{
	public:
		CGameMap();
		CGameMap(char *pPositon);
		void MemeroyMap();
		void InitMap(char *pPositon);
		void DisPlayMap();
		~CGameMap();
	int Get_Row() const { return m_Row; }
	void Set_Row(int val) { m_Row = val; }
	
	int Get_Col() const { return m_Col; }
	void Set_Col(int val) { m_Col = val; }
	
	int ** Get_GameMap() const { return m_GameMap; }
	void Set_GameMap(int ** val) { m_GameMap = val; }
	private:
	int m_Row;
	int m_Col;
	int **m_GameMap;
	};
	#endif  //__GAMEMAP_H__

GameMap.Cpp文件

析构函数没有写的哈

#include "GameMap.h"
#include 
using namespace std;

CGameMap::CGameMap()
{
	this->Set_GameMap(nullptr);
	this->m_Row = 0;
	this->Set_Col(0);
}
CGameMap::CGameMap(char *pPositon)
{
	//从文件中得到数据
	FILE *pfile = fopen(pPositon, "rb");
	fread(&this->m_Row, sizeof(int), 1, pfile);
	fread(&this->m_Col, sizeof(int), 1, pfile);

	fclose(pfile);//关闭文件，光标重置

	//申请动态内存
	this->Set_GameMap(new int*[m_Row]);
	for (int i = 0; i < m_Row; i++)
	{
		this->Get_GameMap()[i] = new int[Get_Col()];
	}

	pfile = fopen(pPositon, "rb");
	fseek(pfile, sizeof(int) * 2, SEEK_SET);
	for (int i = 0; i < m_Row; i++)
	{
		fread(Get_GameMap()[i], sizeof(int)*m_Col, 1, pfile);
	}
	fclose(pfile);
}
void CGameMap::InitMap(char *pPositon)
{
	//从文件中得到数据
	FILE *pfile = fopen(pPositon, "rb");
	fread(&this->m_Row, sizeof(int), 1, pfile);
	fread(&this->m_Col, sizeof(int), 1, pfile);

	fclose(pfile);//关闭文件，光标重置

	//申请动态内存
	this->Set_GameMap(new int*[m_Row]);
	for (int i = 0; i < m_Row; i++)
	{
		this->Get_GameMap()[i] = new int[Get_Col()];
	}

	pfile = fopen(pPositon, "rb");
	fseek(pfile, sizeof(int) * 2, SEEK_SET);
	for (int i = 0; i < m_Row; i++)
	{
		fread(Get_GameMap()[i], sizeof(int)*m_Col, 1, pfile);
	}
	fclose(pfile);

}
void CGameMap::DisPlayMap()
{
	for (int i = 0; i < m_Row; i++)
	{
		for (int j = 0; j < Get_Col(); j++)
		{
			switch (this->Get_GameMap()[i][j])
			{
			case 0:
				cout << "  ";
				break;
			case 1:
				cout << "■";
				break;
			case 2:
			case 7:
				cout << "♀";
				break;
			case 3:
				cout << "●";
				break;
			case 4:
				cout << "酪";
				break;
			case 5:
				cout << "入";
				break;
			case 6:
				cout << "出";
				break;
			case 9:
				cout << "☆";
				break;
			}
		}
		cout << endl;
	}

}

void CGameMap::MemeroyMap()
{
	FILE *pchar = fopen("1.Map", "wb");
	fwrite(&this->m_Row, sizeof(int), 1, pchar);
	fwrite(&this->m_Col, sizeof(int), 1, pchar);
	for (int i = 0; i < m_Row; i++)
	{
		fwrite(Get_GameMap()[i], sizeof(int)*m_Col, 1, pchar);
	}
	fclose(pchar);
	//	fwrite(GameMap, sizeof(int), row*col, pfile);//不要漏掉指针
}
CGameMap::~CGameMap()
{
    //析构没有写的哈
}

兄弟们，有问题，可以在下方评论区讨论。