XOR doubly linked list ...printing elements

Question

0.00/5 (No votes)

See more:

<pre>#include<stdio.h>
typedef struct node_type{
	int data;
	struct node_type *link;
}node;

typedef node *list;
list head,temp,tail,next;

list xor(list a, list b)
{
	return (list) ((unsigned) a ^ (unsigned) b);
}

int main()
{
	char ch;
	int n;
	list head,tail,temp,prev,next,temp1;
	printf("Enter y:\n");
	scanf("%c",&ch);
	printf("Enter data:\n");
	scanf("%d",&n);
	head=tail=NULL;
	temp=(list)malloc(sizeof(node));
	temp->link=NULL;
	temp->data=n;

	head=tail=temp;
	printf("Enter again char:\n");
	scanf("\n%c",&ch);
	while(ch=='y'){
		temp1=(list)malloc(sizeof(node));
		printf("Again input data:\n");
		scanf("%d",&n);
		temp1->data=n;
		temp1->link=xor (temp->link,tail->link);
		tail=temp1;
		printf("again input char:\n");
		scanf("\n%c",&ch);
	}
	printf("\nThe list\n");


	prev=NULL;
	temp=tail;
	while(temp!=NULL)
	{
		printf("%d ",temp->data);
		next=xor( prev,temp->link);

		prev=temp;

		temp=next;

	}

}

What I have tried:

Hi expert, here the code fragment that seems wrong. What can I do here:

C++

prev=NULL;
temp=tail;
while(temp!=NULL)
{
    printf("%d ",temp->data);
    next=xor( prev,temp->link);
    prev=temp;
    temp=next;
}

Because if u input 1 2 3 4 5 44 , then the output comes as only 44. Every times all the output got missing except the last number.

Posted 19-Mar-16 22:32pm

Member 12378355we

Updated 22-Mar-16 13:41pm

v9

Add a Solution

Comments

Patrice T 20-Mar-16 6:55am

Can you explain what is the question or problem ?

Patrice T 20-Mar-16 7:53am

By the way, what is the principle of xor in doubly linked lists ?

[no name] 20-Mar-16 8:40am

Have a look here:<blockquote class="quote"><div class="op">Quote:</div>XOR linked list - Wikipedia, the free encyclopedia[^]</blockquote>

or here: algorithm - How exactly does a XOR Linked list work? - Stack Overflow[^]

and here an example how to travers an xor linked list:
C code for XOR linked list - Stack Overflow[^]

I did not dive in the Details, but it simply Looks like you should initialize "prev" also with "tail" and _not_ with NULL.

Patrice T 20-Mar-16 9:47am

Thanks

[no name] 20-Mar-16 10:09am

Your welcome. Thanks for what? :)

Patrice T 20-Mar-16 10:25am

link :)

[no name] 20-Mar-16 10:46am

Honestly, this topic was also completely new to me. I wondered also what xor and linked list do together? As usually, Google has helped me ;)
Bruno

4 solutions

Solution 2

You guess was wrong. The error is at another place:

C++

temp=(list)malloc(sizeof(node)); // here you overwrite temp!
printf("Again input data:\n");
scanf("%d",&n);
temp->data=n;
temp->link=xor (temp->link,tail->link); // and here you try to use the old temp!
tail=temp;

And the computation of temp->link is wrong anyway. Re-read the article that you mentioned and note that insert a new node you need to change the link fields of the adjacent nodes as well!

Posted 20-Mar-16 3:30am

nv3

Comments

Member 12378355we 20-Mar-16 10:58am

I input 1,2,3 4,and 44 . The output came as only 44. Why the other numbers went missing. Every times the output came with the last input number. Why? Plz explain.

nv3 20-Mar-16 11:44am

Because the linking of one node to the other was not correct. See my explanation above.

Arthur V. Ratz 21-Mar-16 2:59am

5+

Arthur V. Ratz 22-Mar-16 0:48am

+5.

Solution 1

Use the debugger to see exactly what is happening - but frankly, I don;t think XORing pointers and trying to use the intermediate results as valid links is a good idea.
Yes, you can use XOR to swap values, but you need to use more than one XOR to keep good data: Swap two variables using XOR | BetterExplained[^], and I wouldn't use it for pointers!
Just XORing two pointers once is not going to produce a good result. If you want to swap pointers, use a temporary intermediate pointer:

C++

pTemp = pOne;
pOne = pTwo;
pTwo = pTemp;

It's a lot clearer what exactly is going on, and it doesn't generate useless intermediate values.

Posted 19-Mar-16 23:12pm

OriginalGriff

Comments

Member 12378355we 20-Mar-16 5:28am

I'm not swapping values here? Are u kidding me?

OriginalGriff 20-Mar-16 5:45am

What value is in temp the third time round the loop?

[no name] 20-Mar-16 9:12am

XOR linked list is a nasty way to save up Memory. Nowadays maybe still used in the embedded world (?).
XOR linked list - Wikipedia, the free encyclopedia[^]

Arthur V. Ratz 21-Mar-16 2:59am

5+

[no name] 25-Mar-16 9:38am

Thank you :-)

Solution 4

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]

Solution 1 still apply here. Use the debugger.
The debugger will show you exactly what your code is doing, you will ensure the list is saved correctly.
Make sure that pointers are created correctly while building the list.

Advice: take a sheet of paper and write down what every fields must contain as you fill the list and a&dd it to the question (just to see if you understand the algorithm.

Posted 22-Mar-16 13:41pm

Patrice T

Updated 22-Mar-16 14:14pm

v2

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)

Member 12378355we · Accepted Answer · 2016-03-22T09:13:00

I think this is the solution what I was looking for:

C++

#include<stdio.h>

typedef struct node_type{
    
int data;
struct node_type *link;

}node;

typedef node *list;
list head,tail,temp,prev,start,curr;
void listq();

list xor(list a, list b)
{
    return (list) ((unsigned) a ^ (unsigned) b);
}

main(){
int n;
char ch;
scanf("%c",&ch);
scanf("%d\n",&n);
head=tail=start=NULL;
 if(ch=='y'){
    temp=(list)malloc(sizeof(node));
    temp->data=n;
    temp->link=NULL;
    head=start=temp;
    prev=NULL;
}
scanf("%c",&ch);
while(ch=='y')
{
    temp=(list)malloc(sizeof(node));
    scanf("%d\n",&n);
    temp->data=n;
    temp->link=xor(head,NULL);
    head->link=xor(prev,temp);
    prev=head;
    head=temp;
    scanf("%c",&ch);
}
listq();
}

 void listq()
{
    list curr = head;
    list prev = NULL, next;

    while (NULL != curr) {
        printf("%d ", curr->data);
        next = xor(prev, curr->link);
        prev = curr;
        curr = next;
}
    printf("\n");
}

XOR doubly linked list ...printing elements

4 solutions

Solution 2

Solution 1

Solution 4

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us