c++ 回溯算法个人笔记

1.需要使用回溯算法的问题

设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。

如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。

例如在下面的 3×4 的矩阵中包含一条字符串 “bfce”的路径（路径中的字母用下划线标出）

。但矩阵中不包含字符串“abfb”的路径，

因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，

路径不能再次进入这个格子。

A B T G

C F C S

J D E H

老师只讲了一个使用递归的方法实现在后面我用了一个栈实现的

2.回溯算法的原理

在问题的解空间中，按深度优先遍历策略，从根节点出发搜索解空间树。算法搜索至解空间

的任意一个节点时，先判断该节点是否包含问题的解。如果确定不包含，跳过对以该节点为根的

子树的搜索，逐层向其祖先节点回溯，否则进入该子树，继续深度优先搜索。

回溯法解问题的所有解时，必须回溯到根节点，且根节点的所有子树都被搜索后才结束。回

溯法解问题的一个解时，只要搜索到问题的一个解就可结束

3.回溯的基本步骤

定义问题的解空间

确定易于搜索的解空间结构

以深度优先搜索的策略搜索解空间，并在搜索过程中尽可能避免无效搜索

4.使用递归实现

源代码:

#include 
   
    using namespace std;/*****************************************函数参数: matrix -- 矩阵(一级指针 因为数组是连续存储的)*          rows -- 矩阵总的行数*		   columns -- 矩阵总的列数*          row -- 数组下标所在矩阵行*          column -- 数组下标所在矩阵列*          str -- 指定路径的字符串*          ismatrix -- 判断是否走过这个数组下标*          index --  表示str字符串的当前下标(是一个引用);*          引用: 被调函数对形参做的任何操作都影响主调函数中的实参**函数功能: 判断matrix 中是否有str中的指定的路径(使用递归)**函数返回值: 当前matrix的数组下标中的数据 != str当前下标中的数据 return  false ;*			 当 matrix 有str指定的路径return true;**********************************/bool matrixIsPath(const char* matrix, 	              int rows, 	              int columns, 				  int row, 				  int column, 	              const char* str, 	              bool* ismatrix, 	              int& index) {	//每次进入函数 判断是否符合最基本的条件 不符合直接return false;	if (!matrix || rows <= 0 || columns <= 0 || row < 0 || column < 0 		|| !str || !ismatrix) return false;	//当index 下标中的数据 == 字符串结束符'\0' return true;	if (str[index] == '\0') return true;	//数组下标所在的行 * 矩阵的总列数 + 数组下标所在列就 == 数组下标在二维数组中的位置	//数组下标没有走过 而且 该数组下标中的数据 == 当前str下标中的数据进入	if (ismatrix[row * columns + column] == false && 		matrix[row * columns + column] == str[index]){				//str 的下标++;		index++;		//该数组下标在ismatrix矩阵中置为 true (表示走过)		ismatrix[row * columns + column] = true;		//递归判断下一个数组下标== str[index] 		//|| 逻辑或只要有一个函数返回true 就是true 而且不会再往下执行下面的函数		//想要进入if语句就一定index 下标中的数据 == 字符串结束符'\0'		//向下一步		if (matrixIsPath(matrix, rows, columns, row + 1, column, str, ismatrix, index) 			//向右一步			|| matrixIsPath(matrix, rows, columns, row, column + 1, str, ismatrix, index)			//向上一步			|| matrixIsPath(matrix, rows, columns, row - 1, column, str, ismatrix, index) 			//向左一步			|| matrixIsPath(matrix, rows, columns, row, column - 1, str, ismatrix, index)) {			//如果有一个函数返回true 就表示matrix 中有 str指定路径						return true;		}	    //如果没有进入上面的if语句 index-- ; 		index--;		//这个函数没有进行任何操作 退回调用的地方 		//因为这个数组下标上下左右中的数据都没有与str下一个数据相匹配的 回溯到上一个函数		ismatrix[row * columns + column] = false;		//不是特殊的情况 退回到上面的if语句中返回false 再往下执行	}	return false;}/************************************************************************函数参数: matrix -- 矩阵*          rows -- 矩阵总的行数*		   columns -- 矩阵总的列数*          row -- 数组下标所在矩阵行*          column -- 数组下标所在矩阵列*          str -- 指定路径的字符串**函数功能: 以每个matrix数组下标为起点判断是否有str指定的路径**函数返回值: matrix矩阵中有str指定的路径return true else return false;***********************************************************************/bool ergodicmatrix(const char* matrix, 	               int rows, 	               int columns,	               const char* str) {	//防御性编程	if (!matrix || rows <= 0 || columns <= 0) return false;	if (!str) return false;	//new一个与matrix 矩阵大小的数组	bool* ismatrix = new bool[rows * columns];	//表示str字符串的下标	int index = 0;	//ismatrix 中的数据全部置为false;表示没有走过;	//只要 matrix中的数组下标 == str[index] 这个数组下标在 ismatrix 就置为true表示走过的路径	memset(ismatrix, false, rows * columns);	//每个matrix数组下标为起点判断是否有str指定的路径	for (int row = 0; row < rows; row++) {		for (int column = 0; column < columns; column++) {			if (matrixIsPath(matrix, rows, columns, row, 				column, str ,ismatrix, index )) {                delete[] ismatrix;				return true;			}		}	}	delete[] ismatrix;	return false;}/************************函数参数: testName -- 测试的名称*            matrix -- 矩阵*			 rows - 矩阵的总行数*            cols - 矩阵的总列数*            str - 指定路径(字符串)*            expected -- 期望正确的值 (true 和 false)与*            ergoodicmatrix函数返回的值相等打印Passed(通过)*            不相等打印FAILED(failed失败)*            *函数功能: 单元测试代码***函数返回值: 无*/void Test(const char* testName, 	      const char* matrix, 	      int rows, 		  int cols, 	      const char* str, 	      bool expected) { 	if (testName != nullptr) printf("%s begins: ", testName); 	if (ergodicmatrix(matrix, rows, cols, str) == expected) {		printf("Passed.\n");	}	else {		printf("FAILED.\n");	}}//ABTG //CFCS //JDEH //BFCE void Test1() { 	const char* matrix = "ABTGCFCSJDEH"; 	const char* str = "BFCE"; 	Test("功能测试 1", (const char*) matrix, 3, 4, str, true); }//ABCE //SFCS //ADEE //SEE void Test2() { 	const char* matrix = "ABCESFCSADEE"; 	const char* str = "SEE"; 	Test("功能测试 2", (const char*) matrix, 3, 4, str, true); }//ABTG //BFCS //JDEH //ABFB void Test3() { 	const char* matrix = "ABTGCFCSJDEH"; 	const char* str = "ABTCFB"; 	Test("功能测试 3", (const char*) matrix, 3, 4, str, false); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SLHECCEIDEJFGGFIE void Test4(){ 	const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS"; 	const char* str = "SLHECCEIDEJFGGFIE"; 	Test("功能测试 4",(const char*)matrix, 5, 8, str, true); }// ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEHJIGQEM void Test5() {	const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS"; 	const char* str = "SGGFIECVAASABCEHJIGQEM"; 	Test("功能测试 5", (const char*) matrix, 5, 8, str, true); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEEJIGOEM void Test6() {	const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";	const char* str = "SGGFIECVAASABCEEJIGOEM";		Test("功能测试 6", (const char*) matrix, 5, 8, str, false); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEHJIGQEMS void Test7() { 	const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";    const char* str = "SGGFIECVAASABCEHJI8G9Q7E9M4S3"; 	Test("功能测试 7", (const char*)matrix, 5, 8, str, false); }//AAAA //AAAA //AAAA //AAAAAAAAAAAA void Test8() { 	const char* matrix = "AAAAAAAAAAAA"; 	const char* str = "AAAAAAAAAAAA"; 	Test("边界值测试 8", (const char*) matrix, 3, 4, str, true); }//AAAA //AAAA //AAAA //AAAAAAAAAAAAA void Test9() { 	const char* matrix = "AAAAAAAAAAAA"; 	const char* str = "AAAAAAAAAAAAA"; 	Test("边界值测试 9", (const char*) matrix, 3, 4, str, false); }//A //A void Test10() { 	const char* matrix = "A"; 	const char* str = "A"; 	Test("边界值测试 10", (const char*) matrix, 1, 1, str, true); }//A //B void Test11() {	 const char* matrix = "A"; 	 const char* str = "B"; 	Test("边界值测试 11", (const char*)matrix, 1, 1, str, false); }void Test12() { Test("特殊情况测试 12", nullptr, 0, 0, nullptr, false); }int main(void) {		/*设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。	路径可以 从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。	如果一条路径经过了 矩阵的某一格，那么该路径不能再次进入该格子。	例如在下面的 3×4 的矩阵中包含一条字符串 “bfce”的路径（路径中的字母用下划线标出）	。但矩阵中不包含字符串“abfb”的路径，	因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，	路径不能再次进入这个格子。	A B T G 	C F C S 	J D E H 	*/		Test1(); 	Test2(); 	Test3(); 	Test4(); 	Test5(); 	Test6(); 	Test7(); 	Test8(); 	Test9(); 	Test10(); 	Test11(); 	Test12();	return 0;}

测试结果:

在这里插入图片描述

这样的测试用例更全面更准确

只要有一个测试用例打印FAILED这个函数就是有问题

5.使用栈实现

源代码

stack.h

#pragma once#include 
   
    #define MAX_SIZE 50typedef int ElementType;typedef struct _Stack {    ElementType* base; //栈底指针    ElementType* top; //栈顶指针    int capacity; //栈的容量}Stack;//初始化栈bool initStack(Stack* S,int stackSize = MAX_SIZE);//栈是否为空bool isEmpty(Stack* S);//栈是否未满bool isFull(Stack* S);//入栈bool pushStack(Stack* S,ElementType element);//出栈bool popStack(Stack* S);//查看栈顶数据bool getTopElement(Stack* S, ElementType& element);//释放栈的内存bool deleteStack(Stack* S);

stack.cpp

#include 
   
    #include "Stack.h"/**************************************函数参数: S - 栈的结构体指针*          stackSize - 指定栈的容量(默认50)**函数返回值: 初始化成功返回true; 否则返回false*********************/bool initStack(Stack* S,int stackSize ){   	S->capacity = stackSize;	S->base = new ElementType[S->capacity];	if (!S->base) return false;	S->top = S->base;	return true;}/**************************************函数参数: S - 栈的结构体指针*          **函数返回值: S是空的返回true; 否则返回false*********************/bool isEmpty(Stack* S){	if (!S) return true;	if (S->top == S->base ) {		//printf("Stack is empty\n");		return true;	}	return false;}/**************************************函数参数: S - 栈的结构体指针***函数返回值: S是的满的返回true; 否则返回false*********************/bool isFull(Stack* S){	if (!S) return true;	if (S->top - S->base == S->capacity) {		//printf("Stack is full\n");		return true;	}	return false;}/**************************************函数参数: S - 栈的结构体指针*          element - 需要入栈的元素***函数返回值: 入栈成功返回true; 否则返回false*********************/bool pushStack(Stack* S, ElementType emlement) {	if (!S) return false;	if (isFull(S)) return false;	*S->top++ = emlement;	return true;}/**************************************函数参数: S - 栈的结构体指针***函数返回值: 出栈成功返回true; 否则返回false*********************/bool popStack(Stack* S) {	if (!S) return false;	if (isEmpty(S)) return false;	S->top--;	return true;}/**************************************函数参数: S - 栈的结构体指针*		   elemlent - 一个引用保存查看的元素**函数返回值: 查看成成功返回true; 否则返回false*********************/bool getTopElement(Stack* S, ElementType& emlement) {	if (!S) return false;	if (isEmpty(S)) return false;	emlement = *(S->top-1);	return true;}/**************************************函数参数: S - 栈的结构体指针*          **函数返回值: 清理内存成功返回true; 否则返回false*********************/bool deleteStack(Stack* S) {	if (!S) return false;	if (isEmpty(S)) return false;	delete S->base;	S->base = S->top = NULL;	S->capacity = 0;	return true;}

main.cpp

#include 
   
    #include "Stack.h"using namespace std;/*****************************************函数参数: matrix -- 矩阵(一级指针 因为数组是连续存储的)*          rows -- 矩阵总的行数*		   columns -- 矩阵总的列数*          row -- 数组下标所在矩阵行*          column -- 数组下标所在矩阵列*          str -- 指定路径的字符串*          isPathMatrix -- 判断是否走过这个数组下标*          index --  表示str字符串的当前下标(0)*          S -- 栈的结构体指针*          sign -- 是否matrix矩阵中的下标全是true**函数功能: 判断matrix 中是否有str中的指定的路径(使用栈)**函数返回值:  当 matrix 有str指定的路径return true;*			否则返回false;**********************************/bool matrixIsPath1(const char* matrix, 				   int rows, 				   int columns,	               int row, 				   int column, 				   const char* str, 	               bool* isPathMatrix, 	               int index,	               Stack* S,	               bool& sign) {	//合法性判断	if (!matrix || rows <= 0 || columns <= 0 || row < 0 || column < 0		|| !str || !isPathMatrix)  return false;		//初始化栈	initStack(S, rows * columns);	//frontIndex保存的是这个matrix的下标中数据与当前的str下标中的数据相同	//但以这个下标为中心上下左右的下标中的数据没有与下一个str下标中的数据相同	int frontIndex = -2;	//element保存stack取出来的数据	int element = -1;	//先把matrix 中row行column列的下标入栈	pushStack(S, row * columns + column);	//查看栈顶的元素保存在element	getTopElement(S, element);	//element == str[index] str下标指向下一个	//element这个下标在函数开始进行了合法性判断	if (matrix[element] == str[index]) {		index++;		//这个下标在isPathmatrix 置为true		isPathMatrix[element] = true;	}	else {		return false;	}		while (!isEmpty(S) && str[index] != '\0') {			//查看栈顶元素保存在element中		getTopElement(S, element);				//查看matrix矩阵中的下标全都走过		bool flag = true;		for (int i = 0; i < rows * columns; i++) {			//如果matrix有一个下标没有走过 flag = 0 退出循环			if (isPathMatrix[i] == false) {				flag = false;				break;			}					}		//flag如果还是 == true		if(flag == true){			//sign = true;			sign = true;			//退出循环			break;		}		//nextIndex保存当前element下标中的下一个下标		//行+1		int nextIndex = element + columns;		//nextIndex 在elemet基础上加时判断
    
     = 0		//nextIndex下标中的数据与当前str下标中的数据是相等的		//nextIndex下标不能是走过的		//nextIndexx下标不能与frontIndex下标相同		if ((nextIndex < rows * columns) && (matrix[nextIndex] == str[index]) && 			(isPathMatrix[nextIndex] == false) && (nextIndex != frontIndex )) {			//nextIndex 这下标置为true			isPathMatrix[nextIndex] = true;			frontIndex = -2; //重置frontIndex			//nextIndex下标入栈			pushStack(S, nextIndex); 			//str下标index指向了下一个下标			index++;			continue;//执行完这个if语句退出本次循环		}				//行-1		nextIndex = element;		nextIndex = element - columns;		if ((nextIndex >= 0) && (matrix[nextIndex] == str[index]) &&			(isPathMatrix[nextIndex] == false) && (nextIndex != frontIndex)) {			frontIndex = -2;			isPathMatrix[nextIndex] = true;			pushStack(S, nextIndex);			index++;			continue; //退出本次循环	    }		//列+1		nextIndex = element;		nextIndex = element + 1;		if ((nextIndex < rows*columns) && (matrix[element + 1] == str[index])&& 			(isPathMatrix[nextIndex] == false) && (nextIndex != frontIndex) ) {			frontIndex = -2;			isPathMatrix[nextIndex] = true;			pushStack(S, nextIndex);			index++;			continue;//退出本次循环		}				//列-1		nextIndex = element;		nextIndex = element - 1;		if ((nextIndex >= 0) && (matrix[nextIndex] == str[index]) &&			(isPathMatrix[nextIndex] == false) && (nextIndex != frontIndex)) {			frontIndex = -2;			isPathMatrix[nextIndex] = true;			pushStack(S, nextIndex);			index++;			continue;//退出本次循环		}		//elemtent这个下标为中心上下左右的下标中的数据没有与下一个str下标中的数据相同		//str下标index退回到上一个下标		index--;		//frontIndex保存element这个下标		frontIndex = element;		//element这个下标在isPathMatrix		isPathMatrix[element] = false;  		//删除栈顶数据 		popStack(S);	}	if (str[index] == '\0') {		return true;	}	else {		return false;	}}/************************************************************************函数参数: matrix -- 矩阵*          rows -- 矩阵总的行数*		   columns -- 矩阵总的列数*          row -- 数组下标所在矩阵行*          column -- 数组下标所在矩阵列*          str -- 指定路径的字符串**函数功能: 以每个matrix数组下标为起点判断是否有str指定的路径**函数返回值: matrix矩阵中有str指定的路径return true else return false;***********************************************************************/bool ergodicmatrix1(const char* matrix, 	                int rows, 	                int columns, 	                const char* str) {	if (!matrix || rows <= 0 || columns <= 0) return false;	if (!str) return false;	Stack* S = NULL;	//构建一个栈	S = new Stack;	//new一个与matrix 矩阵大小的数组	bool* isPathMatrix = new bool[rows * columns];	//isPathMatrix 中的元素置为false	memset(isPathMatrix, false, rows * columns);	//matrix矩阵中的下标全是true时sign =true;	bool sign = false;	//表示str字符串的下标	int index = 0;	for (int row = 0; row < rows; row++) {		for (int column = 0; column < columns; column++) {			//如果matrixIsPath1函数返回true			if (matrixIsPath1(matrix, rows, columns, row, column, 							  str, isPathMatrix, index,S,sign )) {			    delete S;				delete[] isPathMatrix;				return true;			}//否则判断			else if (sign == true){ 			    delete S;				delete[] isPathMatrix;				return false; 			}		}	}    delete S;	delete[] isPathMatrix;	return false;}/************************函数参数: testName -- 测试的名称*            matrix -- 矩阵*			 rows - 矩阵的总行数*            cols - 矩阵的总列数*            str - 指定路径(字符串)*            expected -- 期望正确的值 (true 和 false)与*            ergoodicmatrix函数返回的值相等打印Passed(通过)*            不相等打印FAILED(failed失败)*            *函数功能: 单元测试代码***函数返回值: 无*/void Test(const char* testName, 	      const char* matrix, 	      int rows, 		  int cols, 	      const char* str, 	      bool expected) { 	if (testName != nullptr) printf("%s begins: ", testName); 	if (ergodicmatrix1(matrix, rows, cols, str) == expected) {		printf("Passed.\n");	}	else {		printf("FAILED.\n");	}}//ABTG //CFCS //JDEH //BFCE void Test1() { 	const char* matrix = "ABTGCFCSJDEH"; 	const char* str = "BFCE"; 	Test("功能测试 1", (const char*) matrix, 3, 4, str, true); }//ABCE //SFCS //ADEE //SEE void Test2() { 	const char* matrix = "ABCESFCSADEE"; 	const char* str = "SEE"; 	Test("功能测试 2", (const char*) matrix, 3, 4, str, true); }//ABTG //BFCS //JDEH //ABFB void Test3() { 	const char* matrix = "ABTGCFCSJDEH"; 	const char* str = "ABTCFB"; 	Test("功能测试 3", (const char*) matrix, 3, 4, str, false); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SLHECCEIDEJFGGFIE void Test4(){ 	const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS"; 	const char* str = "SLHECCEIDEJFGGFIE"; 	Test("功能测试 4",(const char*)matrix, 5, 8, str, true); }// ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEHJIGQEM void Test5() {	const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS"; 	const char* str = "SGGFIECVAASABCEHJIGQEM"; 	Test("功能测试 5", (const char*) matrix, 5, 8, str, true); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEEJIGOEM void Test6() {	const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";	const char* str = "SGGFIECVAASABCEEJIGOEM";		Test("功能测试 6", (const char*) matrix, 5, 8, str, false); }//ABCEHJIG //SFCSLOPQ //ADEEMNOE //ADIDEJFM //VCEIFGGS //SGGFIECVAASABCEHJIGQEMS void Test7() { 	const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";    const char* str = "SGGFIECVAASABCEHJI8G9Q7E9M4S3"; 	Test("功能测试 7", (const char*)matrix, 5, 8, str, false); }//AAAA //AAAA //AAAA //AAAAAAAAAAAA void Test8() { 	const char* matrix = "AAAAAAAAAAAA"; 	const char* str = "AAAAAAAAAAAA"; 	Test("边界值测试 8", (const char*) matrix, 3, 4, str, true); }//AAAA //AAAA //AAAA //AAAAAAAAAAAAA void Test9() { 	const char* matrix = "AAAAAAAAAAAA"; 	const char* str = "AAAAAAAAAAAAA"; 	Test("边界值测试 9", (const char*) matrix, 3, 4, str, false); }//A //A void Test10() { 	const char* matrix = "A"; 	const char* str = "A"; 	Test("边界值测试 10", (const char*) matrix, 1, 1, str, true); }//A //B void Test11() {	 const char* matrix = "A"; 	 const char* str = "B"; 	Test("边界值测试 11", (const char*)matrix, 1, 1, str, false); }void Test12() { Test("特殊情况测试 12", nullptr, 0, 0, nullptr, false); }int main(void) {			printf("使用栈实现!\n");	Test1(); 	Test2(); 	Test3(); 	Test4(); 	Test5(); 	Test6(); 	Test7(); 	Test8(); 	Test9(); 	Test10(); 	Test11(); 	Test12();	return 0;}