一筆畫路徑生成（c/c++）-創(chuàng)新互聯(lián)

一筆畫路徑生成（c++）

練習(xí)圖的遍歷、回溯
網(wǎng)站建設(shè)公司,為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁設(shè)計(jì)及定制網(wǎng)站建設(shè)服務(wù),專注于企業(yè)網(wǎng)站建設(shè),高端網(wǎng)頁制作,對成都OPP膠袋等多個(gè)行業(yè)擁有豐富的網(wǎng)站建設(shè)經(jīng)驗(yàn)的網(wǎng)站建設(shè)公司。專業(yè)網(wǎng)站設(shè)計(jì),網(wǎng)站優(yōu)化推廣哪家好,專業(yè)seo優(yōu)化排名優(yōu)化,H5建站,響應(yīng)式網(wǎng)站。

新建一個(gè)OnePen類；
使用setNodeNum()方法設(shè)置節(jié)點(diǎn)數(shù)量；
使用setNodeJoin()設(shè)置節(jié)點(diǎn)連線；
執(zhí)行drawLine()方法即可得出該圖的一筆畫路線；

main.cpp

#include#include "OnePen.h"

void test01()
{OnePen op;
	op.setNodeNum(4);
	op.setNodeJoin(1, 2);
	op.setNodeJoin(1, 3);
	op.setNodeJoin(2, 3);
	op.setNodeJoin(2, 4);
	op.printTable();
	op.drawLine();
}

void test02()
{OnePen op;
	op.setNodeNum(5);
	op.setNodeJoin(1, 4);
	op.setNodeJoin(1, 5);
	op.setNodeJoin(2, 4);
	op.setNodeJoin(2, 5);
	op.setNodeJoin(3, 4);
	op.setNodeJoin(3, 5);
	op.setNodeJoin(4, 5);
	op.printTable();
	op.drawLine();
}

int main()
{test02();
	system("pause");
	return 0;
}

OnePen.h

#pragma once
#include#includeclass OnePen
{private:
	struct node				// 節(jié)點(diǎn)
	{int data;			// 數(shù)據(jù)域
		bool flag;			// 標(biāo)記（1已使用0未使用）
		node* next;			// 下一個(gè)
	};

	node* nodeArray;		// 節(jié)點(diǎn)數(shù)組
	int nodeNum;			// 節(jié)點(diǎn)數(shù)量
	std::vectorpath;	// 路徑

	bool checkAlone();
	bool sign(int p1, int p2, int flag);
	bool endCheck();
	int draw(int p);
public:
	OnePen();
	void setNodeNum(int num);
	void setNodeJoin(int begin, int end);
	void printTable();
	void drawLine();
};

OnePen.cpp

#include "OnePen.h"

// 構(gòu)造函數(shù)，初始化成員變量
OnePen::OnePen()
{this->nodeNum = 0;
	this->nodeArray = NULL;
}

// 設(shè)置節(jié)點(diǎn)數(shù)量，并生成初始數(shù)組
void OnePen::setNodeNum(int num)
{if (num<= 1)
	{std::cout<< "節(jié)點(diǎn)數(shù)必須大于 1。"<< std::endl;
	}
	else
	{this->nodeNum = num;
		this->nodeArray = new node[num];

		for (int i = 0; i< num; i++)
		{	this->nodeArray[i].data = i;
			this->nodeArray[i].flag = false;
			this->nodeArray[i].next = NULL;
		}
	}
}

// 連接節(jié)點(diǎn)
void OnePen::setNodeJoin(int begin, int end)
{// 首尾不能相同
	if (begin == end)
	{std::cout<< "首尾節(jié)點(diǎn)不能相同，請重新確認(rèn)！";
		std::cout<<"（Error: .setNodeJoin("<< begin<< ","<< end<< ");）"<< std::endl;
		return;
	}
	
	// 其中一節(jié)點(diǎn)不存在
	bool beginExist = false, endExist = false;
	for (int i = 0; i< this->nodeNum; i++)
	{// 數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)是從0開始，但是從用戶角度節(jié)點(diǎn)是從1開始，所以需要-1
		if (this->nodeArray[i].data == begin - 1)
			beginExist = true;
		if (this->nodeArray[i].data == end - 1)
			endExist = true;
	}
	if (!beginExist || !endExist)
	{std::cout<< "節(jié)點(diǎn)不存在，請重新確認(rèn)！";
		std::cout<< "（Error: .setNodeJoin("<< begin<< ","<< end<< ");）"<< std::endl;
		return;
	}

	// 找到 begin 節(jié)點(diǎn)的最后一個(gè)鄰接節(jié)點(diǎn)，然后插入新的鄰接節(jié)點(diǎn)
	node* beginNode = &this->nodeArray[begin - 1];	// begin節(jié)點(diǎn)
	while (NULL != beginNode->next)
	{if (beginNode->next->data == end - 1)
		{	// 已存在從 begin ->end 的路線
			break;
		}
		beginNode = beginNode->next;
	}
	if (beginNode->next == NULL)
	{node* temp = new node;
		temp->data = end - 1;
		temp->flag = 0;
		temp->next = NULL;
		beginNode->next = temp;
	}
	
	// 找到 end 節(jié)點(diǎn)的最后一個(gè)鄰接節(jié)點(diǎn)，然后插入新的鄰接節(jié)點(diǎn)
	node* endNode = &this->nodeArray[end - 1];		// end節(jié)點(diǎn)
	while (NULL != endNode->next)
	{if (endNode->next->data == begin - 1)
		{	// 已存在從 end ->begin 的路線
			break;
		}
		endNode = endNode->next;
	}
	if (endNode->next == NULL)
	{node* temp = new node;
		temp->data = begin - 1;
		temp->flag = 0;
		temp->next = NULL;
		endNode->next = temp;
	}
}

// 輸出鄰接表
void OnePen::printTable()
{std::cout<< "當(dāng)前鄰接表為："<< std::endl;
	std::cout<< "-----------------------------"<< std::endl;
	for (int i = 0; i< this->nodeNum; i++)
	{std::cout<< this->nodeArray[i].data + 1<< " | ";
		node* temp = this->nodeArray[i].next;
		while (temp != NULL)
		{	std::cout<< " ->"<< temp->data + 1;
			temp = temp->next;
		}
		std::cout<< std::endl;
	}
	std::cout<< "-----------------------------\n"<< std::endl;
}

// 檢查是否存在獨(dú)立的點(diǎn)（即出度和入度皆為0）
bool OnePen::checkAlone()
{for (int i = 0; i< this->nodeNum; i++)
	{if (this->nodeArray[i].next == NULL)
		{	return true;
		}
	}
	return false;
}

// 設(shè)置標(biāo)記（p1->p2 的 flag 設(shè)置為 flag）
bool OnePen::sign(int p1, int p2, int flag)
{node* it = this->nodeArray[p1].next;
	while (it != NULL)
	{if (it->data == p2)
		{	it->flag = flag;
			return true;
		}
		it = it->next;
	}
	return false;
}

// 最終檢查（鄰接表的全部flag都為1即返回true）
bool OnePen::endCheck()
{node* temp;
	for (int i = 0; i< this->nodeNum; i++)
	{temp = this->nodeArray[i].next;
		while (NULL != temp)
		{	if (temp->flag == 0)
			{		return false;
			}
			temp = temp->next;
		}
	}
	return true;
}

// 開始畫線
void OnePen::drawLine()
{// 檢查是否存在獨(dú)立的點(diǎn)
	if (this->checkAlone())
	{std::cout<< "- 單獨(dú)的節(jié)點(diǎn)：\n\n>>>";
		for (int i = 0; i< this->nodeNum; i++)
		{	if (this->nodeArray[i].next == NULL)
			{		std::cout<< this->nodeArray[i].data<< "\t";
			}
		}
		std::cout<< "\n\n- 請將全部節(jié)點(diǎn)連接！\n"<< std::endl;
		return;
	}

	// 統(tǒng)計(jì)有多少種方法
	int count = 1;
	// 從每個(gè)節(jié)點(diǎn)為初始節(jié)點(diǎn)依次走一次
	for (int i = 0; i< this->nodeNum; i++)
	{// 將全部標(biāo)簽置0
		for (int j = 0; j< this->nodeNum; j++)
		{	node* t = this->nodeArray[j].next;
			while (t != NULL)
			{		t->flag = 0;
				t = t->next;
			}
		}

		// 將路徑清空
		this->path.clear();

		// 開始畫線draw(i)，其中i為初始節(jié)點(diǎn)，返回結(jié)果為是否走得通
		if (this->draw(i))
		{	std::cout<< "-----------------------------"<< std::endl;
			std::cout<< ">>>第 "<< count<< " 種解法：\n>>>";
			count++;
			for (int i = 0; i< this->path.size(); i++)
			{		if (i == 0)
					std::cout<< this->path[i];
				else
					std::cout<< " ->"<< this->path[i];
			}
			std::cout<< "\n"<< std::endl;
		}
	}
}

// 以point節(jié)點(diǎn)為開始節(jié)點(diǎn)走下一步
int OnePen::draw(int point)
{// 當(dāng)前節(jié)點(diǎn)添加到路徑（由于存儲(chǔ)和顯示不同，所以+1）
	this->path.push_back(point + 1);

	// 完成（到該點(diǎn)已經(jīng)全部路線都走完了就逐層返回1）
	if (this->endCheck())
	{return 1;
	}

	node* past = new node;					// 走過節(jié)點(diǎn)列表（已經(jīng)走過并且走不通）
	node* last = past;						// 走過節(jié)點(diǎn)列表 的最后一個(gè)節(jié)點(diǎn)（方便添加新的節(jié)點(diǎn)）
	int peerNode = -1;						// 目標(biāo)節(jié)點(diǎn)（將要走的節(jié)點(diǎn)，初始化為不可能的-1）

	node* it = this->nodeArray[point].next;	// 當(dāng)前節(jié)點(diǎn)的第一個(gè)鄰接點(diǎn)
	// 找到下一個(gè)要走的節(jié)點(diǎn)，并且標(biāo)記
	while (it != NULL)
	{if (it->flag == 0)			// 尚未走過的目標(biāo)節(jié)點(diǎn)
		{	peerNode = it->data;	// 記錄目標(biāo)節(jié)點(diǎn)
			it->flag = 1;			// 標(biāo)記目標(biāo)節(jié)點(diǎn)
			past->data = peerNode;	// 目標(biāo)節(jié)點(diǎn)加入past列表
			past->next = NULL;
			break;
		}
		it = it->next;
	}

	// 此路不通（遍歷完當(dāng)前節(jié)點(diǎn)的所有鄰接點(diǎn)都沒找到flag=0的節(jié)點(diǎn)即無路可走了）
	if (it == NULL)
	{return 0;
	}

	// 將目標(biāo)節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的線標(biāo)記
	this->sign(peerNode, point, 1);

	// 開始遞歸，如果遞歸結(jié)果返回0（即此路不通）開始進(jìn)入循環(huán)找新的目標(biāo)節(jié)點(diǎn)
	while (!this->draw(peerNode))
	{// 進(jìn)入循環(huán)證明當(dāng)前past列表的最新元素走不通，移除
		this->path.pop_back();

		// 1. 將剛剛走過的標(biāo)記取消（讓其他節(jié)點(diǎn)可以走）
		this->sign(point, peerNode, 0);
		this->sign(peerNode, point, 0);

		// 2. 找到一個(gè)節(jié)點(diǎn)需要即不在past列表里，并且flag為0
		it = this->nodeArray[point].next;
		while (it != NULL)
		{	if (it->flag == 0)
			{		bool b = true; // 檢查這個(gè)節(jié)點(diǎn)是否存在past列表（1這個(gè)節(jié)點(diǎn)能走，0這個(gè)節(jié)點(diǎn)不能走）

				// 遍歷走過列表
				node* ps = past;
				while (ps != NULL)
				{// 如果當(dāng)前節(jié)點(diǎn)存在走過列表里面，這個(gè)節(jié)點(diǎn)不能走
					if (it->data == ps->data)
					{b = false;
						break;
					}
					ps = ps->next;
				}

				// 找到目標(biāo)節(jié)點(diǎn)
				if (b)
				{peerNode = it->data;

					// 添加到走過列表
					node* past2 = new node;
					past2->data = peerNode;
					past2->next = NULL;
					last->next = past2;		// 添加到past列表的最后
					last = past2;			// last指向past列表的最后元素

					// 標(biāo)記（當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路線已使用）
					this->sign(point, peerNode, 1);
					this->sign(peerNode, point, 1);

					// 退出循環(huán)
					break;
				}
			}

			it = it->next;
		}
		
		// 3. 遍歷完鄰接點(diǎn)也沒找到可用的節(jié)點(diǎn)，沒有可以走的路線了，此路不通
		if (it == NULL)
		{	return 0;
		}
	}
}

測試（上面的main.cpp的test02函數(shù)）
執(zhí)行結(jié)果

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標(biāo)題：一筆畫路徑生成（c/c++）-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接：http://muchs.cn/article14/eiige.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、網(wǎng)站導(dǎo)航、用戶體驗(yàn)、虛擬主機(jī)、網(wǎng)站設(shè)計(jì)公司、面包屑導(dǎo)航

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容