递归算法和指针的问题
Trouble with a recursive algorithm and pointers
所以我试图制作一个算法,从第一个 "room" 开始,然后递归地向外移动并开始从外到内删除所有房间。一个房间是一个结构,有 4 "doors"(指向房间的指针):北、南、东和西。
该函数有两个参数:指向当前房间的指针和一个字符(用于标识方向:北、南、东或西)。
这是我的算法逻辑 (roomDelete):
基本案例
- 从第一个房间开始,在任何非空指针上调用函数 (roomDelete);函数调用的输入应该是指向 N/S/E/W 空间的适当指针,以及表示 N/S/E/W.
方向的适当字符
- 检查所有指针 (N/S/E/W) 是否为 NULL --> 删除当前房间。
- Done/return.
递归
- 通过使用 char 来保存与方向 char 相反的值,确保不要回溯(沿你来的方向返回)。
- 在任何非 NULL、非回溯上调用函数 pointers/directions。
- 断开与上一个房间的连接。
- 检查所有指针是否为 NULL --> 删除当前房间。
这是 rooms/pointers 的简单图片:
http://i.imgur.com/btKz5JB.png
我有我试图测试的代码。如果我有一个房间(单独),那么该功能就会起作用。但是一旦另一个房间被混入其中,该功能就永远不会 returns/finishes。我不确定为什么。我的逻辑合理吗?我错过了什么吗?
感谢任何帮助。
代码:
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
#define NUM_DOORS 4
struct room {
struct room * north;
struct room * south;
struct room * east;
struct room * west;
} ;
int roomDelete(room *, char);
int main(void)
{
room * test_ptr = new room;
cout << "Created room at location: " << test_ptr << endl;
test_ptr->north = NULL;
test_ptr->south = NULL;
test_ptr->east = NULL;
test_ptr->west = NULL;
test_ptr->north = new room;
cout << "Created room at location: " << test_ptr->north << endl;
test_ptr->north->north = NULL;
test_ptr->north->south = test_ptr;
test_ptr->north->east = NULL;
test_ptr->north->west = NULL;
int test = roomDelete(test_ptr, '[=10=]');
cout << test << endl;
return 0;
}
int roomDelete(room * room_ptr, char coord)
{
char coordinate[NUM_DOORS] = {'N', 'S', 'E', 'W'};
char coordinate_opposite[NUM_DOORS] = {'S', 'N', 'W', 'E'};
char coord_opp = '[=10=]';
// call function on any remaining rooms
if(coord == '[=10=]') // this is the beginning/initial room
{
for(int i = 0; i < NUM_DOORS; i++)
{
switch (coordinate[i])
{
case 'N':
{
if(room_ptr->north != NULL)
roomDelete(room_ptr->north, 'N');
break;
}
case 'S':
{
if(room_ptr->south != NULL)
roomDelete(room_ptr->south, 'S');
break;
}
case 'E':
{
if(room_ptr->east != NULL)
roomDelete(room_ptr->east, 'E');
break;
}
case 'W':
{
if(room_ptr->west != NULL)
roomDelete(room_ptr->west, 'W');
break;
}
default:
cout << "There was an error deallocating for the room at location: " << room_ptr << endl;
}
}
// delete the current room
if(room_ptr->north == NULL && room_ptr->south == NULL && room_ptr->east == NULL && room_ptr->west == NULL)
{
cout << "Deleting room at location: " << room_ptr << endl;
delete room_ptr;
}
else
return 2; // outward rooms have not been deleted yet
}
else // recursion
{
// this sets the value for the door that won't be handed to the delete function
for(int j = 0; j < NUM_DOORS; j++)
{
if(coord == coordinate[j])
coord_opp = coordinate_opposite[j];
}
if(coord_opp == '[=10=]')
{
cout << "An error occurred while setting the value of the opposite coordinate.\n";
return 1;
}
// call the function on any remaining rooms
for(int k = 0; k < NUM_DOORS; k++)
{
if(coordinate[k] != coord_opp) // this is to avoid backtracking (which would cause infinite recursion)
{
switch (coordinate[k])
{
case 'N':
{
if(room_ptr->north != NULL)
roomDelete(room_ptr->north, 'N');
break;
}
case 'S':
{
if(room_ptr->south != NULL)
roomDelete(room_ptr->south, 'S');
break;
}
case 'E':
{
if(room_ptr->east != NULL)
roomDelete(room_ptr->east, 'E');
break;
}
case 'W':
{
if(room_ptr->west != NULL)
roomDelete(room_ptr->west, 'W');
break;
}
default:
cout << "There was an error deallocating for the room at location: " << room_ptr << endl;
}
}
}
// delete connection (ptr's) between current room and previous
switch(coord)
{
case 'N':
{
room_ptr->south->north = NULL;
room_ptr->south = NULL;
}
case 'S':
{
room_ptr->north->south = NULL;
room_ptr->north = NULL;
}
case 'E':
{
room_ptr->west->east = NULL;
room_ptr->west = NULL;
}
case 'W':
{
room_ptr->east->west = NULL;
room_ptr->east = NULL;
}
default:
cout << "There was a problem with severing the connection for the room at location: " << room_ptr << endl;
}
// delete current room
if(room_ptr->north == NULL && room_ptr->south == NULL && room_ptr->east == NULL && room_ptr->west == NULL)
{
cout << "Deleting room at location: " << room_ptr << endl;
delete room_ptr;
}
else
return 3; // outward rooms have not been deleted yet
}
return 0; // successful in deallocating the entire complex
}
我不明白你的算法,但我可以告诉你哪里失败了。
switch (coord)
{
case 'N':{
room_ptr->south->north = NULL;
room_ptr->south = NULL;
}
case 'S':{
room_ptr->north->south = NULL; // <-- Program Fails Here
room_ptr->north = NULL;
}
room_ptr->north 此时是一个空指针,因此您正在写入不允许的位置。
可能你还没有完全理解switch语句?它有所谓的 "fall-through" 行为,即它不会仅仅因为它是一个新案例而自行爆发,它只会找到一个开始执行代码的地方并继续执行它直到它命中“}”或找到明确写成 "break;" 的方式。
所以我试图制作一个算法,从第一个 "room" 开始,然后递归地向外移动并开始从外到内删除所有房间。一个房间是一个结构,有 4 "doors"(指向房间的指针):北、南、东和西。
该函数有两个参数:指向当前房间的指针和一个字符(用于标识方向:北、南、东或西)。
这是我的算法逻辑 (roomDelete):
基本案例
- 从第一个房间开始,在任何非空指针上调用函数 (roomDelete);函数调用的输入应该是指向 N/S/E/W 空间的适当指针,以及表示 N/S/E/W. 方向的适当字符
- 检查所有指针 (N/S/E/W) 是否为 NULL --> 删除当前房间。
- Done/return.
递归
- 通过使用 char 来保存与方向 char 相反的值,确保不要回溯(沿你来的方向返回)。
- 在任何非 NULL、非回溯上调用函数 pointers/directions。
- 断开与上一个房间的连接。
- 检查所有指针是否为 NULL --> 删除当前房间。
这是 rooms/pointers 的简单图片: http://i.imgur.com/btKz5JB.png
我有我试图测试的代码。如果我有一个房间(单独),那么该功能就会起作用。但是一旦另一个房间被混入其中,该功能就永远不会 returns/finishes。我不确定为什么。我的逻辑合理吗?我错过了什么吗? 感谢任何帮助。
代码:
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
#define NUM_DOORS 4
struct room {
struct room * north;
struct room * south;
struct room * east;
struct room * west;
} ;
int roomDelete(room *, char);
int main(void)
{
room * test_ptr = new room;
cout << "Created room at location: " << test_ptr << endl;
test_ptr->north = NULL;
test_ptr->south = NULL;
test_ptr->east = NULL;
test_ptr->west = NULL;
test_ptr->north = new room;
cout << "Created room at location: " << test_ptr->north << endl;
test_ptr->north->north = NULL;
test_ptr->north->south = test_ptr;
test_ptr->north->east = NULL;
test_ptr->north->west = NULL;
int test = roomDelete(test_ptr, '[=10=]');
cout << test << endl;
return 0;
}
int roomDelete(room * room_ptr, char coord)
{
char coordinate[NUM_DOORS] = {'N', 'S', 'E', 'W'};
char coordinate_opposite[NUM_DOORS] = {'S', 'N', 'W', 'E'};
char coord_opp = '[=10=]';
// call function on any remaining rooms
if(coord == '[=10=]') // this is the beginning/initial room
{
for(int i = 0; i < NUM_DOORS; i++)
{
switch (coordinate[i])
{
case 'N':
{
if(room_ptr->north != NULL)
roomDelete(room_ptr->north, 'N');
break;
}
case 'S':
{
if(room_ptr->south != NULL)
roomDelete(room_ptr->south, 'S');
break;
}
case 'E':
{
if(room_ptr->east != NULL)
roomDelete(room_ptr->east, 'E');
break;
}
case 'W':
{
if(room_ptr->west != NULL)
roomDelete(room_ptr->west, 'W');
break;
}
default:
cout << "There was an error deallocating for the room at location: " << room_ptr << endl;
}
}
// delete the current room
if(room_ptr->north == NULL && room_ptr->south == NULL && room_ptr->east == NULL && room_ptr->west == NULL)
{
cout << "Deleting room at location: " << room_ptr << endl;
delete room_ptr;
}
else
return 2; // outward rooms have not been deleted yet
}
else // recursion
{
// this sets the value for the door that won't be handed to the delete function
for(int j = 0; j < NUM_DOORS; j++)
{
if(coord == coordinate[j])
coord_opp = coordinate_opposite[j];
}
if(coord_opp == '[=10=]')
{
cout << "An error occurred while setting the value of the opposite coordinate.\n";
return 1;
}
// call the function on any remaining rooms
for(int k = 0; k < NUM_DOORS; k++)
{
if(coordinate[k] != coord_opp) // this is to avoid backtracking (which would cause infinite recursion)
{
switch (coordinate[k])
{
case 'N':
{
if(room_ptr->north != NULL)
roomDelete(room_ptr->north, 'N');
break;
}
case 'S':
{
if(room_ptr->south != NULL)
roomDelete(room_ptr->south, 'S');
break;
}
case 'E':
{
if(room_ptr->east != NULL)
roomDelete(room_ptr->east, 'E');
break;
}
case 'W':
{
if(room_ptr->west != NULL)
roomDelete(room_ptr->west, 'W');
break;
}
default:
cout << "There was an error deallocating for the room at location: " << room_ptr << endl;
}
}
}
// delete connection (ptr's) between current room and previous
switch(coord)
{
case 'N':
{
room_ptr->south->north = NULL;
room_ptr->south = NULL;
}
case 'S':
{
room_ptr->north->south = NULL;
room_ptr->north = NULL;
}
case 'E':
{
room_ptr->west->east = NULL;
room_ptr->west = NULL;
}
case 'W':
{
room_ptr->east->west = NULL;
room_ptr->east = NULL;
}
default:
cout << "There was a problem with severing the connection for the room at location: " << room_ptr << endl;
}
// delete current room
if(room_ptr->north == NULL && room_ptr->south == NULL && room_ptr->east == NULL && room_ptr->west == NULL)
{
cout << "Deleting room at location: " << room_ptr << endl;
delete room_ptr;
}
else
return 3; // outward rooms have not been deleted yet
}
return 0; // successful in deallocating the entire complex
}
我不明白你的算法,但我可以告诉你哪里失败了。
switch (coord)
{
case 'N':{
room_ptr->south->north = NULL;
room_ptr->south = NULL;
}
case 'S':{
room_ptr->north->south = NULL; // <-- Program Fails Here
room_ptr->north = NULL;
}
room_ptr->north 此时是一个空指针,因此您正在写入不允许的位置。
可能你还没有完全理解switch语句?它有所谓的 "fall-through" 行为,即它不会仅仅因为它是一个新案例而自行爆发,它只会找到一个开始执行代码的地方并继续执行它直到它命中“}”或找到明确写成 "break;" 的方式。