Trouble with a recursive algorithm and pointers

208 views Asked by At

So I'm trying to make an algorithm that starts at the first "room" and then recursively goes outward and starts deleting all rooms from the outside in. A room is a struct with 4 "doors" (pointers to rooms): North, South, East, and West.

The function takes two arguments: pointer to the current room and a char (to identify the direction: North, South, East, or West).

Here is my logic for the algorithm (roomDelete):

Base Case

  1. Start at the first room and call the function (roomDelete) on any non-NULL pointers; input to the function calls should be appropriate pointer to the room to the N/S/E/W, and appropriate char representing the direction N/S/E/W.
  2. Check to see that all pointers (N/S/E/W) are NULL --> delete this current room.
  3. Done/return.

Recursion

  1. Make sure not to backtrack (travel back in the direction you came from), by using a char to hold the value opposite of the direction char.
  2. Call the function on any non-NULL, non-backtrack pointers/directions.
  3. Break connection to previous room.
  4. Check to see that all pointers are NULL --> delete this current room.

Here is a simple picture on what the rooms/pointers look like: https://i.stack.imgur.com/9W1UO.png

I have code that I tried to test. If I have a room (by itself), then the function works. But as soon as another room is thrown into the mix, then the function never returns/finishes. I'm not sure why. Is my logic sound? Am I missing something? Any help is appreciated.

CODE:

#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
}
1

There are 1 answers

2
Karlis Olte On BEST ANSWER

I don't understand your algorithm, but I can tell where you are failing.

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 at this moment is a null pointer and you are thus writing at location you are not allowed to.

Maybe you don't fully understand switch statements? It has so called "fall-through" behavior , i.e. it doesn't break out by itself just because it is a new case, it will just find a place where to start executing code and keep executing it until it hits "}" or finds explicitly written "break;" in it's way.