函数变平到单个列表

列表

给定一个链表结构，其中每个节点代表一个链表和包含其类型的两个指针：函数变平到单个列表

（I）指向下一个节点中的主列表。（ii）指向该节点头部的链接列表的指针。

编写一个C函数将列表平铺到单个链表中。

例如，

如果给定链表

1 -- 5 -- 7 -- 10 
    | | | 
    2 6 8 
    | | 
    3 9 
    | 
    4

然后将其转换为

1 - 2 - 3 - 4 - 5 - 6 - 9 - 7 - 8 -10

我的解决方案

struct node { 
    int data; 
    struct node *fwd; //pointer to next node in the main list. 
    struct node *down; //pointer to a linked list where this node is head. 
}*head,*temp,*temp2; 

temp=head; 
while(temp->fwd!=NULL) { 
    temp2=temp->fwd; 
    while(temp->down!=NULL) { 
     temp=temp->down; 
    } 
    temp->down=temp2; 
    temp->fwd=NULL; 
    temp=temp2; 
}

PLZ通知我如果有什么......其他的解决方案和优化是欢迎

来源

2010-12-20 algo-geeks

我的解决办法：结构节点 { int数据; struct node * fwd; //指向主列表中下一个节点的指针。 struct node * down; //指向此节点所在链接列表的指针。 } * head，* temp，* temp2; temp = head; （temp-> fwd！= NULL） temp2 = temp-> fwd; （temp-> down！= NULL） temp = temp-> down; } temp-> down = temp2; temp-> fwd = NULL; temp = temp2; } PLZ通知我，如果有任何其他解决方案和优化，欢迎 – 2010-12-20 07:56:50

:::::作业？ – wilhelmtell 2010-12-20 07:56:58

@wilhelmtell：从写作的方式来猜测你是对的。 – sjngm 2010-12-20 08:05:17

首先让它工作很重要。由于while(temp->fwd!=NULL)，您的解决方案并没有为这些方案的工作：

A) 1 -- 2  B) 1 -- 3 
     |  | | 
     3  2 4

试试这个：

#include <stdio.h> 

struct node { 
    int data; 
    struct node *fwd; //pointer to next node in the main list. 
    struct node *down; //pointer to a linked list where this node is head. 
}; 

struct node *solve(struct node *head) { 
    struct node *temp = head, *fwd; 
    while (temp != NULL) { 
     fwd = temp->fwd; 
     while (temp->down != NULL) { 
      temp = temp->down; 
     } 
     temp->down = fwd; 
     temp->fwd = NULL; 
     temp = fwd; 
    } 
    return head; 
} 

int main(int argc, char **argv) { 
    struct node 
     n12 = { 12, NULL, NULL }, 
     n11 = { 11, NULL, &n12 }, 
     n10 = { 10, NULL, &n11 }, 
     n8 = { 8, NULL, NULL }, 
     n7 = { 7, &n10, &n8 }, 
     n9 = { 9, NULL, NULL }, 
     n6 = { 6, NULL, &n9 }, 
     n5 = { 5, &n7, &n6 }, 
     n4 = { 4, NULL, NULL }, 
     n3 = { 3, NULL, &n4 }, 
     n2 = { 2, NULL, &n3 }, 
     n1 = { 1, &n5, &n2 }, 
     *result = solve(&n1); 

    while (result != NULL) { 
     printf("%d%s", result->data, result->down ? " - " : ""); 
     result = result->down; 
    } 
    puts(""); 

    return 0; 
}

注：这当然不node->down->fwd处理。你可能想用一个递归函数来解决这个问题，这个函数留作练习。

来源

2010-12-20 09:09:24 jweyrich

解决方案对我来说很合适。一个小的变化可能是从解决方案的图表中，我期望答案应该是一个“水平”列表（使用fwd指针），而不是你的解决方案产生的垂直列表（使用向下指针）

来源

2010-12-20 08:28:58

如果你把'down'链接作为左边的子指针，'forward'链接作为右边的子指针，那么你正在寻求一个简单的二叉树的有序遍历。也就是说，你访问节点;那么你访问左边（下）的孩子，然后你访问右边（前面）的孩子。把它作为一个递归函数很容易写出来。

如果第一个节点只有一个向下指针并且没有前向指针，那么您的解决方案将不会遍历任何树。如果它没有向前指针（因为它没有前向指针），它也不会从最后一个指针向下搜索。

我认为（但我不确定 - 我没有测试过）你的解决方案在比较例子中的麻烦树上遇到麻烦。如果节点2有前向指针，我认为在搜索该子树时会出现问题。

使用递归;它是微不足道的和可靠的。虽然您可以消除简单的尾部递归，但这不仅仅需要简单的尾部递归。

来源

2010-12-20 08:30:50

如果乔纳森的解决方案对你没有意义，只要看看你的列表图表，同时将你的头部向左倾斜45度。 – 2010-12-20 08:47:06

struct node* flatten_dfwalk(struct node * root) 
{ 

    struct node *lnode, *rnode, *temp; 

    if (NULL == root) 
    { 
     return NULL; 
    } 


    lnode = flatten_dfwalk(root->down); 
    rnode = flatten_dfwalk(root->next); 

    if (NULL == lnode) 
    { 
     return root; 
    } 

    temp = lnode; 
    while(lnode->next != NULL) 
    { 
     lnode = lnode->next; 
    } 

    lnode->next = root->next; 
    root->next = temp; 

    return root; 
}

来源

2014-11-11 17:51:23 user4240723

-2

struct node * last; 
    void dfs(struct node * root) 
    { 
     if(root) 
     { 
      dfs(root->down); 
      if(last!=NULL) 
      { 
       last->next=root->next; 
       last=NULL; 
      } 
      dfs(root->next); 
      if(root->down) 
      root->next=root->down; 

      if(root->next==NULL&&root->down==NULL) 
       last=root; 
     } 
    }

来源

2015-07-24 08:45:14 user4239080

函数变平到单个列表

回答

相关问题