单向链表数组创建邻接表失败

Question

我正在尝试通过一个单链表数组创建邻接表。

查看我的代码。

 #include<iostream>
 #include<cstdlib>

 using namespace std;

 typedef struct city
 {
      int id;
      struct city *next;
 }city;

 int main()
 {
     int num_city, index = 0, length;
     cin >> num_city;   

     length = num_city;

     city **adj_list = new city*[num_city]; // here it's the header node
     for(int index = 0 ; index < length ; index++)
             adj_list[index] = new city;
     city **temp = adj_list;

     while( num_city -- )
     {
             int a,b;
             cin >> a;
             cin >> b;

             a--;
             b--;       

             city *t1 = new city;
             t1 -> id = a;
             t1 -> next = NULL;

             city *t2 = new city;
             t2 -> id = b;
             t2 -> next = NULL;

             temp[a] -> next = t2;
             temp[b] -> next = t1;  

             temp[a] = temp[a] -> next;
             temp[b] = temp[b] -> next;
      } 
      for ( int index = 0; index < length ; index ++)
             delete []  adj_list[index];
      delete [] adj_list;

    adj_list = NULL;
    exit(0);
  }

当我试图一个一个地遍历单向链表时，它的输出是 NULL。

经过GDB这段代码，发现：开始循环，city创建成功，adj_list[index]也能指向正确的内存位置。一旦进入下一个循环，adj_list[index]意外地等于NULL。

怎么了？

Answer 1

有两个问题。您正在使用 temp 来跟踪每个列表中的最后一项。但是 temp 指向原始的 adj_list （它是 adj_list 而不是它的副本），所以结果是 adj_list 本身只保留您在每个列表中添加的最后一项。如果您将初始 adj_list 复制到 temp，则更新 temp 不会影响 adj_list.

中的现有项目

第二个问题是邻居对的数量可能多于城市的数量。 5 个城市的示例：(2,3)、(2,4)、(2,5)、(2,1)、(1,5)、(4,5)、(3,4)。所以你不能在 num_city 上循环。而是继续循环，直到用户输入城市 -1。

我添加了一个构造函数 city( int id, city* next ) 以便更容易地初始化每个新城市。 temp 重命名为 tail 以使其更清楚其用途。该功能分为 3 个部分，构建、打印和删除。

typedef struct city
{
    int id;
    struct city *next;
    city(int id, city *next) { this->id = id; this->next = next; }
} city;

// pass `adj_list` in as a reference (city **&) so you keep the changes to it when you return
int adj_list_build(city **& adj_list)
{
    int num_city, index = 0;
    cin >> num_city;

    // you need to keep track of the "tail" (end) of each list so you know where to add next item
    city **tail = new city*[num_city];

    adj_list = new city*[num_city];
    for (int index = 0; index < num_city; index++)
    {
        adj_list[index] = new city( index, NULL );
        tail[index] = adj_list[index]; // the tail starts off pointing to the first item in each list
    }

    while (true)
    {
        int a, b;
        cin >> a;               // enter `-1` to stop
        if (a == -1 ) break;
        cin >> b;

        a--;                    // convert to 0-index
        b--;

        city *t1 = new city( a, NULL );
        city *t2 = new city( b, NULL );

        tail[a]->next = t2;
        tail[b]->next = t1;

        tail[a] = t2; // or `tail[a] = tail[a]->next;` - they have same effect 
        tail[b] = t1;
    }
    return num_city;
}

void adj_list_print(city ** adj_list, int length)
{
    for (int index = 0; index < length; index++)
    {
        cout << index << ": ";
        city * item = adj_list[index];
        while (item)
        {
            cout << item->id << " " << item->next << " ";
            item = item->next;
        }
        cout << endl;
    }
}

void adj_list_delete(city ** adj_list, int length)
{
    for (int index = 0; index < length; index++)
        delete[]  adj_list[index];
    delete[] adj_list;

    adj_list = NULL;
}

void main()
{
    city ** adj_list;
    int len = adj_list_build( adj_list );
    adj_list_print(adj_list, len);
    adj_list_delete(adj_list, len);
}

单向链表数组创建邻接表失败

Failed to create adjacency list via one array of singly linked list

c++

arrays

adjacency-list

singly-linked-list