求用邻接链表表示的有向图的转置

青春不谢
  • 289

算法导论22.1-3有个问题,将有向图转置(原题是邻接链表和邻接矩阵,这里只讨论邻接链表)自己写了个比较复杂,觉得不好。所以去网上找答案,看到的大多跟下面这个类似:

void Transpose(VNode Adj[], VNode newAdj[], int V)
{
    int i;
    for(i = 0; i < V; i++)
    {
        VNode *p = Adj[i].next;
        while(p != NULL)
        {
            newAdj[p->data]->next = (VNode *)malloc(sizeof(VNode));
            newAdj[p->data]->next->data = Adj[i].data;
            newAdj[p->data]->next->next = NULL;
            p = p->next;
        }
    }
}

但我感觉明显不对啊。比如原有向图的邻接链表如下

1 -> 2 ->4
2 -> 5
3 -> 6 ->5
4 -> 2
5 -> 4
6 -> 6

遍历第一个链表时,对于 1 -> 2,可以将新链表的newAdj[2]->next->data = 1; 这没问题。但是后面对于 4 -> 2,newAdj[2]->next已经指向1了,再重新分配内存并赋值为4,不就把之前的1给冲掉了吗?最后的得到的转置有向图每个链表不都最多只有两个元素了吗?

请问哪里有邻接链表转置的好的代码,最好是用c++写的,谢谢!

回复
阅读 4.8k
1 个回答
DQM_2006
  • 2
新手上路,请多包涵

我也想要......如果你找到了,请告诉我

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏