c++ - 链表中的节点可以有指向自身的指针吗？ C++

Question

这里是 CS 学生。我不会试图隐藏这是为了家庭作业的事实。我知道这个问题很尴尬所以让我解释一下，

我正在用 C++ 编写作业代码，该作业使用节点来模拟房间结构，并通过指针链接。基本上它是一个链表。我知道如何设计链表，这样这就是我的房间结构。 (只是你的平均堆栈或队列)

 +---+---+---+---+---+   | 1 | 2 | 3 | 4 | 5 |   +---+---+---+---+---+

But that structure is one dimensional and only requires links in one/two directions. One for the address of the next node and another for the address of the preceding node. I want to create a 2d structure that looks more like this:

    ____+---+      ____| R |      ____+---+      ____| H |  +---+   +---+   +---+  | L |. .| H |. .| L |   +---+   +---+   +---+  | L |  . . . . .| H |  +---+  . . . . .+---+  ........... ......^  

Where L is a lab, H is a hallway, and R is the reactor (we have to define at least 3 different types of room as subclasses of base class Room). And ^ is where you enter from.
The thing I can't straighten out in my design is if I want to be able to move in 4 directions (lets say N, S, E, W), how will I account for there being no room in a direction the user picks?
I am going to assign pointers to all adjacent rooms when a player 'enters' a room, but what should I do about the walls?
Should I assign them to point to the same room the player is in? And then print an error statement? Should I assign them to NULL? Any advice is helpful.

edit @ 7 PST 8.1.15

Wow great responses so far!. @cristophe : I like option 1. Is it possible to instantiate the entire linked list at the start of the program, linking all the rooms together by giving them N, S, E, W pointers to one another, with NULLs for walls?
Assuming I have a base/parent class Room and derived classes Lab, Hall, Reactor that act like nodes, could I have a boolean member variable in these nodes called player that returns true if the player is in the room?

edit @ 4:20 PST 8.4.15

I've coded at least a skeletal version of the structure, and the method worked! Each room is a linked node with 4 pointers for the 4 primary directions. I assign addresses of adjacent rooms to the pointers and the address of the room itself to any direction with a wall. Here is my class definition, I'll post more code when it looks better. All these pointers will hopefully by private in the end, I just haven't got around to writing the accessors yet.

room.h:

#ifndef ROOM_H
#define ROOM_H

using namespace std;

class Room {
    //protected:
    public:
            string roomname;
            int roomtemp;
            int playertemp;
            Room *up;
            Room *down;
            Room *left;
            Room *right;
            Room *player;
            virtual void temp_change(int roomtemp);
            string get_name();
            void set_room(string nameval, Room* up, Room* down, Room* left, Room* right);
            void set_temp();
            void move_player(Room*& current, char action);

};

#endif

Answer 1

您尝试将其实现为数据结构的更多是图而不是链表。你有很多方法来实现它。

第一种可能:

• 你有一个平面链表或一个房间 vector
• 每个房间都有一个指向相邻房间的指针链表
• 问题:链接应与 N、S、W、E 相关
• 解决问题:使用配对(方向+指针)，或使用 map 而不是相邻房间的链表。
• 墙是链表中没有方向。

第二种可能:

• 你有一个平面链表或一个房间 vector
• 每个房间本身都有一个指向相邻房间的 4 个指针(N、S、W、E)的 vector
• 墙由 nullptr 表示

第三种可能:

• 你有一个平面链表或一个房间 vector
• 每个房间都有 4 个指向相邻房间的指针(就像一棵树，只是它们可以循环)。
• 墙由 nullptr 表示
• 问题:这比前一个操作起来更麻烦(即你需要大量冗余代码来遍历 4 个方向)

第四种可能:

• 你有一个包含 N 个房间的 vector
• 你有一个房间之间的 N x N 邻接关系矩阵
• 房间 i 和房间 j 的矩阵值告诉你从 i 到 j 必须走哪个方向，或者一个中性值表示房间没有连接