How to initialize this data structure

Question

1.00/5 (1 vote)

See more:

It is a doubly linked list. In addition to next and previous pointers, each element has a child pointer, which may or may not point to a separate doubly linked list. These child lists could have their child lists on their own.

Structure like this:

C++

struct nodeT
{
   struct nodeT *prev;
   struct nodeT *next;
   struct nodeT *child;
   int value;
}

Could anyone give me a clue how may I initialize one structure like this? With given data.
Thank you guys~

Well, one way I can think is to just input a flatten version of this structure, I can transform from flatten version to target one, but I am looking for a better solution.

I implement some code myself, no idea it works or not.
I hope you guys can give me some help!

typedef struct nodeT{
struct nodeT *next;
struct nodeT *prev;
struct nodeT *child;
int value;
}node;

//flatten fn:
/*void Flatten(node *head,node **tail)
{
	node *currentNode=head;
	while(currentNode)
	{
		if(node->child)
		{
			Append(currentNode->child,**tail)
		}
		node=node->next;
	}
}
void Append(node *child,**tail)
{
	child->prev=*tail;
	(*tail)->next=child;
	node *curNode=child;
	while(curNode)
	{
		*tail=curNode;
		curNode=curNode->next;
	}
}
*/
void Initialize(node **currentNode)
{
	int data,tag_1,tag_2;
	printf("Input data of current node:\n");scanf("%d",&data);
	(*currentNode)->value=data;
	node **temp_1;node **temp_2;
	printf("Does current node have a child?(1 for yes, 0 for no)\n");scanf("%d",&tag_1);
	printf("Does current node have next node?(1 for yes, 0 for no)\n");scanf("%d",&tag_2);
	if(tag_1==1)
	{
		(*currentNode)->child=(node *)malloc(sizeof(node));
		temp_1=&((*currentNode)->child);	
		Initialize(temp_1);
	}
	if(tag_2==1)
	{
		(*currentNode)->next=(node *)malloc(sizeof(node));
		temp_2=&((*currentNode)->next);
		(*currentNode)=(*temp_1)->prev;
		Initialize(temp_2);
	}
}

Posted 7-Nov-11 10:57am

zhaoyilong1

Updated 7-Nov-11 14:12pm

v3

Add a Solution

Comments

Sergey Alexandrovich Kryukov 7-Nov-11 17:01pm

Well, C++ or C? If both, in what sense?
--SA

zhaoyilong1 7-Nov-11 18:18pm

better in C.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Answer 1 · 2011-11-07T11:04:00

Solution 1

Please see my question in my comment to the question.

If you can, make it C++, not C and initialize it using a set of constructors. Also, follow the encapsulation principles (http://en.wikipedia.org/wiki/Encapsulation_%28object-oriented_programming%29[^]), hide these members under access modifier private (private is default for classes, but default for struct is public), replace it with functions which expose only what is needed.

Does it provide you a clue?

—SA

Posted 7-Nov-11 11:04am

Sergey Alexandrovich Kryukov

Updated 7-Nov-11 11:44am

v3

Comments

lewax00 7-Nov-11 17:42pm

I think you mean default for struct is public.

Sergey Alexandrovich Kryukov 7-Nov-11 17:44pm

Yes, of course, a result of Paste, fixed, thank you for your help.
--SA

zhaoyilong1 7-Nov-11 18:19pm

Thank you, I just do not understand how to initialize or traverse this structure, use recursive fn maybe~?

Paul M Watt · Answer 2 · 2011-11-07T16:25:00

I would start by clearing out each property in your node to 0. Then you will always have a baseline to test against when you navigate to insert your next node and you have found the bottom of your tree.

You can simplify a few things in your function, then it might be a bit clearer how to initialize your node. The way you currently have the function Initialize written, you have to call it like this:

Node elt;

Initialize(&(&elt));

or

Node elt;
Node *pElt = &elt;
Initialize(&pElt);

Start with the struct that you will pass into be initialized. You are not allocating any new memory for the actual node, so you can remove one of the *, and use a single pointer rather than a pointer to a pointer:

void Initialize(node *currentNode)

You can then call the function like this:

Node elt;
Initialize(&elt);

Also, you don't have to dereference every access in your function to currentNode twice;
first time: (*currentNode)
second time: ->

You can replace all of the

(*currentNode)->

with

currentNode->

Beyond that, I am not sure exactly how you need the items to be initialized. I can tell you that if the user answers no for the first question of is there a child, but yes for a next node, temp_1 will not be initialized, and you will attempt to access an uninitialized pointer.

Also, I do not see any code that initializes your prev data member.

One final tip, just like with the call to Initialize(¤tNode), you can simplify your calls with the pointers, if you change the definitions for temp_1 and temp_2 to use a single pointer rather than a pointer to a pointer like this:

node *temp_2;

...

currentNode->next = (node *)malloc(sizeof(node));
temp_2            = currentNode->next;
currentNode       = temp_1->prev;

Initialize(temp_2);