c++ - 在 C++ 中列出内部结构

Question

我在 C++ 的结构中有一个列表；我只想像往常一样向这个列表中插入元素。

我的结构是:

// A structure to represent an adjacency list node
struct AdjListNode
{
    int dest;
    int weight;
    std::list<int> adjacents;
    struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
    int pos;
    struct AdjListNode *head; // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};

struct Graph* createGraph(int V)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists. Size of array will be V
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));


    // Initialize each adjacency list as empty by making head as NULL
    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }

    return graph;
}

当我尝试访问时:

graph->array[position].head->adjacents->push_back(number);

它只是提示我:

进程以退出代码 139 结束(被信号 11 中断:SIGSEGV)

抱歉，我不知道这个错误。

Answer 1

段错误来自

graph->array[position].head->adjacents.push_back(number);

与

graph->array[position].head = NULL;

我假设您的代码中具有隐式结构不变性，因为您有两个可能连接的列表:从 AdjList::head 开始并遍历 AdjNode 的链表: :next 和列表 AdjNode::adjacent。

要保持连接，您可以添加一个(C 风格)函数，在两个列表中添加一个元素。

void
addAdjacent(AdjList& list, int adjacent) {
    // struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    struct AdjListNode* newNode = new AdjListNode;
    newNode->next = list.head;
    list.head = newNode;
    newNode->dest = 0;
    newNode->weight = 0;
    newNode->adjacents = std::list<int>(); // undefined behavior with malloc
    newNode->adjacents.push_back(adjacent);
}

请注意，将 C 风格(malloc/free)与 C++ 风格(尤其是标准模板库的容器)混合使用是个坏主意。我的代码的注释部分产生了段错误，因为 std::list 的字段未填充 0。

最后，下面的 main 函数即使有很多内存泄漏也能正常工作(请参阅 valgrind 工具)

int main(int argc, char** argv) {
   struct Graph* graph = createGraph(2);
   addAdjacent(graph->array[0], 1);
   addAdjacent(graph->array[1], 2);
   free(graph);
   return 0;
}

C++-98 解决方案(没有任何内存泄漏)可以是:

// A structure to represent an adjacency list node
struct AdjListNode
{
    int dest;
    int weight;
    std::list<int> adjacents;
    struct AdjListNode* next;

    AdjListNode() : dest(0), weight(0), next(NULL) {}
};

// A structure to represent an adjacency list
struct AdjList
{
    int pos;
    struct AdjListNode *head; // pointer to head node of list

    // Initialize each adjacency list as empty by making head as NULL
    AdjList() : pos(0), head(NULL) {}
    ~AdjList()
      { while (head) {
          struct AdjListNode* temp = head;
          head = head->next;
          delete temp;
        }
      }

    void addAdjacent(int adjacent)
      { struct AdjListNode* newNode = new AdjListNode;
        newNode->next = head;
        head = newNode;
        newNode->adjacents.push_back(adjacent);
      }
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;

    // Create an array of adjacency lists. Size of array will be V
    Graph(int v) : V(v), array(NULL)
      { if (v >= 0 && v <= 1000)
          array = new struct AdjList[v];
        else
          throw std::bad_alloc();
      }
    ~Graph()
      { delete [] array; }
};

int main() {
   struct Graph* graph = new Graph(2);
   graph->array[0].addAdjacent(1);
   graph->array[1].addAdjacent(1);
   delete graph;
   return 0;
}