函數變平到單個列表

列表

給定一個鏈表結構，其中每個節點代表一個鏈表和包含其類型的兩個指針：函數變平到單個列表

（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

函數變平到單個列表

回答

相關問題