c++ - 递归算法和指针的问题

Question

所以我正在尝试制作一个算法，从第一个“房间”开始，然后递归地向外移动并开始从外到内删除所有房间。一个房间是一个有 4 个“门”(指向房间的指针)的结构: 北、南、​​东、西。

该函数有两个参数:指向当前房间的指针和一个字符(用于标识方向:北、南、东或西)。

这是我的算法逻辑 (roomDelete):

基本案例

1. 从第一个房间开始，对任何非 NULL 指针调用函数 (roomDelete)；函数调用的输入应该是指向 N/S/E/W 空间的适当指针，以及表示 N/S/E/W 方向的适当字符。
2. 检查所有指针 (N/S/E/W) 是否为 NULL --> 删除当前房间。
3. 完成/返回。

递归

1. 通过使用一个 char 来保存与方向 char 相反的值，确保不要回溯(沿你来的方向返回)。
2. 在任何非 NULL、非回溯指针/方向上调用该函数。
3. 断开与之前房间的连接。
4. 检查所有指针是否为 NULL --> 删除当前房间。

这是一张关于房间/指针的简单图片: http://i.imgur.com/btKz5JB.png

我有我试图测试的代码。如果我有一个房间(单独)，那么该功能就会起作用。但是一旦另一个房间被混入其中，该函数就永远不会返回/完成。我不确定为什么。我的逻辑合理吗？我错过了什么吗？感谢您的帮助。

代码:

#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, '\0');

    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 = '\0';

    // call function on any remaining rooms
    if(coord == '\0')   // 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 == '\0')
        {
            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
}

Answer 1

我不明白你的算法，但我可以告诉你哪里失败了。

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;”就这样。