递归算法和指针的问题

Question

所以我试图制作一个算法，从第一个 "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
}

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;" 的方式。

递归算法和指针的问题

Trouble with a recursive algorithm and pointers

c++

pointers

recursion

struct

allocation