LInked List flattening in C [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

I am writing this code to practice linked lists. The goal is to flatten the linked list. Can anyone help in pointing out the mistake's here ? THanks.

(LInk flattening theory: Something like this: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;
}

---

One problem is you print_list routine assumes that the list is already flat. So it's not going to be very helpful in determining the difference between a flattened and unflattened list.

Another problem is that when you flatten a child you don't null the child pointer. I would expect to see something like

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

Another problem is that because your flattening procedure appends child nodes to the end of the list is inevitably reorders the list. This is not what a flattening function should to. For instance if you flatten

(1 2 (3 4 5) 6 7)

then you should get

(1 2 3 4 5 6 7)

whereas your code (if I understand it right) will give

(1 2 6 7 3 4 5)

That's enough for now, good luck!

---

Like everyone else, I'm not sure what your problem is (what do you mean by "flatten"?), but this is a bug:

append(curNode->child,&tail);

should be

append(curNode->child,tail);