在L列表中展平C

Question

我在寫這段代碼來練習鏈表。目標是將鏈表弄平。任何人都可以幫助指出這裏的錯誤嗎？謝謝。

（鏈接扁平化理論：事情是這樣的：HTTP：//code-forum.blogspot.com/2010/12/function-to-flatten-list-into-single.html）

#include <stdio.h> 


typedef struct Node { 
    struct Node *next; 
    struct Node *prev; 
    struct Node *child; 
    int   value; 
} Node; 

void print_list(Node* root) { 
    while (root) { 
    printf("%c ", root->value); 

    if(root->child){  
     printf("%c ", root->child->value); 
    } 

    root = root->next; 
    } 
    printf("\n"); 
} 

void append(Node *child, Node **tail){ 
    Node *curNode = child; 
    (*tail)->next = curNode; 
    curNode->prev = *tail; 
    *tail = curNode;  
} 

void flatten_list(Node *head, Node **tail) { 

    printf("in flatten function now\n"); 
    Node *curNode = head; 
    while (curNode) { 
     if (curNode->child){ 
      printf("current node has a child\n"); 
      append(curNode->child,tail); 
      curNode->child= NULL; 
     } 
     curNode = curNode->next;   
    } 
} 


main() 
{ 
    Node g = { 0, 0, 0, '1' }; 
    Node e = { 0, 0, 0, '9' };   
// Node f = { 0, &e, 0, '8' }; 
    Node d = { 0, 0, 0, '6' }; 
    Node c = { &d, 0, &g ,'5' }; 
    Node b = { &c, 0, 0 , '3' }; 
    Node a = { &b, 0, &e, '4' }; 


    Node* root = &a;  
    Node *tail = &g; 
    printf("Unflattened List:\n"); 
    print_list(root); 
    flatten_list(root,&tail); 
    printf("Flattened List:\n"); 
    print_list(root); 

    return 0; 
} 

Answer 1

像其他人一樣，我不知道你的問題是什麼（什麼叫「扁平化」呢？），但是這是一個錯誤：

append(curNode->child,&tail); 

應該

append(curNode->child,tail); 

Answer 2

一個問題是你print_list例程假定列表已經是平的。因此，在確定扁平列表和非平坦列表之間的差異方面不會很有幫助。

另一個問題是，當你扁平化一個孩子時，你不能使空子指針無效。我希望看到類似

if (curNode->child){ 
     printf("current node has a child\n"); 
     append(curNode->child,&tail); 
     curNode->child = NULL; 
    } 

另一個問題是，因爲你的扁平化過程追加子節點列表的末尾是不可避免的重新排序列表。這不是扁平化功能應該做的。例如，如果你壓扁

（1 2（3 4 5）6 7）

那麼你應該得到

（1 2 3 4 5 6 7）

，而你的代碼（如果我的理解對不對）會給

（1 2 6 7 3 4 5）

，對於現在夠了，祝你好運！