adding in ascending order in double linked list

[PRadyut]

In this code i tried to add the elements in ascending order
but the output is only
0
1
2

the rest of the elements are not shown. the code
----------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct dnode
{
struct dnode *prev;
int data;
struct dnode *next;
};
void display(struct dnode *);
void append(struct dnode **, int );
void deletel(struct dnode **, int );
void reverse(struct dnode **);
int main()
{
struct dnode *p=NULL;
append(&p, 2);
append(&p, 5);
append(&p, 7);
append(&p, 6);
append(&p, 8);
append(&p, 9);
append(&p, 3);
append(&p, 1);
append(&p, 4);
append(&p, 0);
display(p);
/*deletel(&p, 0);
display(p);
reverse(&p);
display(p);*/
getch();
return 0;
}


void display(struct dnode *p)
{
while(p)
{
printf("%d\n", p->data);
p=p->next;
}
printf("\n");
}
void deletel(struct dnode **s, int num)
{
struct dnode *p;
p=*s;
if(*s==NULL)
printf("empty list");
else
{
while(p!=NULL)
{
if(p->data==num)
{
if(p==*s)
{
*s=p->next;
(*s)->prev=NULL;
free(p);
return;
}
else
{
if(p->next==NULL)
{
p->prev->next=NULL;
}
else
{
p->next->prev=p->prev;
p->prev->next=p->next;
}
free(p);
return;
}
}
p=p->next;
}
}
}

void reverse(struct dnode **x)
{
struct dnode *p, *q, *r=NULL;
p=*x;
while(p)
{
q=r;
r=p;
p=p->next;
r->next=q;
}
*x=r;
}

void append(struct dnode **s, int num)
{
struct dnode *p, *r;
p=*s;
r=(struct dnode*)malloc(sizeof(struct dnode));
r->data=num;
//if(*s==NULL)
//{
// r->prev=NULL;
// r->next=NULL;
// *s=r;
// return;
//}
//else if(p->data>num)
//{
// r->next=NULL;
// r->prev=p;
// p=r;
// return;
// /**s=r;
// (*s)->next=p;*/
//}
if(*s==NULL || p->data>num)
{
r->next=NULL;
r->prev=NULL;
*s=r;
(*s)->next=p;
}
else
{
while(p->next!=NULL)
{
if(p->next->data>num)
{

/*p->prev->next=r;
p->next->prev=r;*/
r->prev=p->prev;
r->next=p->next;
//p=r;
return;
}
p=p->next;
}
/*r->next=NULL;
r->prev=p;
p=r;*/
}
}

--------------------------------------------------------------

anyt help

thanks
Pradyut
http://pradyut.tk
http://groups.yahoo.com/group/d_dom/
http://groups-beta.google.com/group/oop_programming
India

 

[Michael Mair]

In this code i tried to add the elements in ascending order
but the output is only
0
1
2

Please give us a _full_ description, so we can understand
every aspect of your problem.

You are working with a doubly linked list, NULL-terminated, and
essentially keep only the head pointer. You want to generate new
nodes carrying some value and insert these nodes at the right
place in the list such that the linked list is always ordered
as long as this is the only operation which can add nodes to
the list.

the rest of the elements are not shown. the code
----------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

conio.h is _not_ a standard C header.
Please stick to standard C.

struct dnode
{
struct dnode *prev;
int data;
struct dnode *next;
};
void display(struct dnode *);
void append(struct dnode **, int );
void deletel(struct dnode **, int );
void reverse(struct dnode **);

The functions deletel() and reverse() have nothing to do
with your problem. It is considered polite to post _minimal_
examples exposing the erroneous behaviour.

int main()
{
struct dnode *p=NULL;
append(&p, 2);
append(&p, 5);
append(&p, 7);
append(&p, 6);
append(&p, 8);
append(&p, 9);
append(&p, 3);
append(&p, 1);
append(&p, 4);
append(&p, 0);
display(p);
/*deletel(&p, 0);
display(p);
reverse(&p);
display(p);*/
getch();

getch() probably comes from "conio.h" and should not be part of
your problem.

return 0;
}


void display(struct dnode *p)
{
while(p)
{
printf("%d\n", p->data);
p=p->next;
}
printf("\n");
}

Clear and straightforward.

void deletel(struct dnode **s, int num)
{ [snip: not germane]
}

void reverse(struct dnode **x)
{ [snip: not germane]
}

void append(struct dnode **s, int num)
{
struct dnode *p, *r;
p=*s;
r=(struct dnode*)malloc(sizeof(struct dnode));

Error-prone way of using malloc(), omitted error-checking.
See comp.lang.c archives for details and below for a
corrected version.

r->data=num;

It is a Good Idea to "initialise" r completely, i.e.
r->prev = r->next = NULL;
to make sure that you cannot forget it.

//if(*s==NULL)
//{
// r->prev=NULL;
// r->next=NULL;
// *s=r;
// return;
//}
//else if(p->data>num)
//{
// r->next=NULL;
// r->prev=p;
// p=r;
// return;
// /**s=r;
// (*s)->next=p;*/
//}

Note: Comment on what your code is _supposed_ to do.
The above is slightly clearer than your version below.
Do not use C++ style comments in C89 code.

if(*s==NULL || p->data>num)
{
r->next=NULL;
r->prev=NULL;
*s=r;
(*s)->next=p;
}
else
{
while(p->next!=NULL)
{
if(p->next->data>num)
{

/*p->prev->next=r;
p->next->prev=r;*/
r->prev=p->prev;
r->next=p->next;
//p=r;
return;
}
p=p->next;
}

You seem to have only a vague idea what linked lists are about.
The following is ASCII art, so you need a fixed width font to
see what I mean:

These are p and q=p->next (assumed to be !=NULL) and all links
they possess:

+---+ -next-> +-----------+ -next->
| p | | q=p->next |
<-prev- +---+ <-prev- +-----------+

Now you want to insert r between p and q; this means
- changing p->next, q->prev and the two links of r
.............(old next).........
. v
+---+ -next-> +---+ -next-> +-----------+ -next->
| p | | r | | q=p->next |
<-prev- +---+ <-prev- +---+ <-prev- +-----------+
^ .
............(old prev)..........

i.e.
old_next = p->next;
old_prev = q->prev;
p->next = r; r->next = old_next;
q->prev = r; r->prev = old_prev;

without the temporary variables old_next and old_prev, we have
to be careful about order but we already know p->next = q, q->prev = p.
Without q, old_next and old_prev, we can only rely on p->next->prev = p.
However, for correctness of the linked list, we always have to adjust
_four_ links.

Figure it out with pen and paper; also for the border case
of q = NULL.

/*r->next=NULL;
r->prev=p;
p=r;*/
}
}

I did not want to comment everything, so here is a corrected version
including a cleanup routine (uncommented, quite in your tradition):

Cheers
Michael

#include <stdio.h>
#include <stdlib.h>
/*
#include <conio.h>
*/

struct dnode
{
struct dnode *prev;
struct dnode *next;
int data;
};

void display(struct dnode *p);
void append (struct dnode **s, int num);
void free_all (struct dnode *p);

int main (void)
{
struct dnode *p=NULL;
append(&p, 2);
append(&p, 5);
append(&p, 7);
append(&p, 6);
append(&p, 8);
append(&p, 9);
append(&p, 3);
append(&p, 1);
append(&p, 4);
append(&p, 0);
display(p);

free_all(p);
/*
getch();
*/

return 0;
}


void display(struct dnode *p)
{
while(p)
{
printf("%d\n", p->data);
p=p->next;
}
printf("\n");
}

void append(struct dnode **s, int num)
{
struct dnode *r;

if (!s)
return;

r = malloc(sizeof *r);
if (!r)
{
fprintf(stderr, "Cannot allocate storage for dnode **s\n");
display(*s);
free_all(*s);
exit(EXIT_FAILURE);
}

r->next=NULL;
r->prev=NULL;
r->data=num;

if (*s == NULL)
{
/* first and only node: initialise list head */
*s = r;
}
else if ((*s)->data > num)
{
/* r already is in the right place, so add links
** and set r to be the new list head. */
r->next = *s;
(*s)->prev = r;

*s = r;
}
else
{
/* iterate until the right position for r is
** found, then link it in. */
struct dnode *p;

for (p=*s; p->next; p=p->next)
{
if (p->next->data > num)
{
p->next->prev = r;
break;
}
}
r->prev = p;
r->next = p->next;
p->next = r;
}
}

void free_all (struct dnode *p)
{
struct dnode *tmp;

if (p && p->next)
for (tmp = p->next; tmp; )
{
if (tmp->next)
{
tmp = tmp->next;
free(tmp->prev);
}
else
{
free(tmp);
tmp = NULL;
}
}
if (p && p->prev)
for (tmp = p->prev; tmp; )
{
if (tmp->prev)
{
tmp = tmp->prev;
free(tmp->next);
}
else
{
free(tmp);
tmp = NULL;
}
}

free(p);
}

 

[Barry Schwarz]

In this code i tried to add the elements in ascending order
but the output is only
0
1
2

the rest of the elements are not shown. the code
----------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct dnode
{
struct dnode *prev;
int data;
struct dnode *next;
};
void display(struct dnode *);
void append(struct dnode **, int );
void deletel(struct dnode **, int );
void reverse(struct dnode **);
int main()
{
struct dnode *p=NULL;
append(&p, 2);
append(&p, 5);

Your append logic is defective. If you step through it with a
debugger, you will see that this node is never added to the list.

append(&p, 7);
append(&p, 6);
append(&p, 8);
append(&p, 9);
append(&p, 3);
append(&p, 1);
append(&p, 4);
append(&p, 0);
display(p);
/*deletel(&p, 0);
display(p);
reverse(&p);
display(p);*/
getch();
return 0;
}


void display(struct dnode *p)
{
while(p)
{
printf("%d\n", p->data);
p=p->next;
}
printf("\n");
}

snip functions not used

void append(struct dnode **s, int num)
{
struct dnode *p, *r;
p=*s;
r=(struct dnode*)malloc(sizeof(struct dnode));
r->data=num;
//if(*s==NULL)
//{
// r->prev=NULL;
// r->next=NULL;
// *s=r;
// return;
//}
//else if(p->data>num)
//{
// r->next=NULL;
// r->prev=p;
// p=r;
// return;
// /**s=r;
// (*s)->next=p;*/
//}
if(*s==NULL || p->data>num)

On the second call, this is false.

{
r->next=NULL;
r->prev=NULL;
*s=r;
(*s)->next=p;
}
else

Execution continues here.

{
while(p->next!=NULL)

Since there is only one node in the list, p->next is NULL and this is
false. Where does execution continue?

{
if(p->next->data>num)
{

/*p->prev->next=r;
p->next->prev=r;*/
r->prev=p->prev;
r->next=p->next;
//p=r;
return;
}
p=p->next;
}

It would try to continue here but these are comments.

/*r->next=NULL;
r->prev=p;
p=r;*/
}
}

--------------------------------------------------------------

anyt help

thanks
Pradyut
http://pradyut.tk
http://groups.yahoo.com/group/d_dom/
http://groups-beta.google.com/group/oop_programming
India

<<Remove the del for email>>