Sorting of double linked list in C

Question

I created a program to sort double linked list in ascending order, and the result was unexpected, but when I used the same program for descending order by changing a line in it, it worked perfectly. Please tell where m going wrong

/*Structure of double linked list */ 
    struct dlink
    {
        int num;
        struct dlink *plink; //previous address
        struct dlink *nlink; //next address
    };
            void main()
            {
                clrscr();
                struct dlink *st;
                st=NULL;

                append(&st,100); //to put values in double linked list
                append(&st,32);
                append(&st,200);
                append(&st,107);
                display(st);
                ascending(&st);
                display(st);
                getch();
            }
       /* function to add values to double linked list */ 
        void append(struct dlink **q,int n)
        {
            struct dlink *temp,*r;
            temp=*q;

            if(temp==NULL)
            {
                temp=(dlink *)malloc(sizeof(dlink));
                temp->num=n;
                temp->plink=NULL;
                temp->nlink=NULL;
                *q=temp;
            }
            else
            {
                while(temp->nlink!=NULL)
                    temp=temp->nlink;
                r=(dlink *)malloc(sizeof(dlink));
                r->num=n;
                r->nlink=NULL;
                r->plink=temp;
                temp->nlink=r;
            }
        }


            void ascending(struct dlink **q)
            {
                struct dlink *temp,*s,*p=NULL;
                temp=*q;
                int a=count(*q);
                printf(" a %d ",a);

                for(int i=0;i<a;i++,temp=temp->nlink)

                {
                    s=temp->nlink;
                    for(int j=i+1;j<=a;j++,s=s->nlink)
                    {
                           if((temp->num) <  (s->num)) //for ascending i was using //if(temp->num > s->num but it is not getting desired result it is just printing //one value and by this one for descending order program is working perfectly //for descending order
                        {       
                                (s->plink)->nlink=s->nlink;
                                if(s->nlink!=NULL)
                                    (s->nlink)->plink=s->plink;

                                s->plink=temp->plink;
                                s->nlink=temp;
                                temp=s;
                                (temp->nlink)->plink=temp;
                        }
                    }
                    if(i==0)
                        *q=temp;

                      if(i!=0)
                    {
                        p->nlink=temp;
                        temp->plink=p;
                    }
                       p=temp;


                }
                temp=*q;   
                /* To see if the addresse , previous address , next address are correct */ 
                while(temp!=NULL)
                    {
                        printf("as %u %u %u\n",temp->plink,temp->nlink,temp);
                        temp=temp->nlink;
                    }   
            }

It would help if you explained what the result was. Any errors thrown? — Anna Tomanek, May 20 '15 at 09:23
[Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). — unwind, May 20 '15 at 09:25
But then it's giving error cant convert void* to dlink * @unwind — john scott, May 20 '15 at 09:41
A double linked list, having a pointer only to the first element (and having to write a loop to find the last one) definitely defeats its purpose You should represent a list as a pair of pointers, ` struct list { struct dlink *first, *last, };` — Michel Billaud, May 20 '15 at 09:43
Won't compile with MSCV - `'dlink' : undeclared identifier`. It should be `struct dlink` since you have not typedefed `dlink`. You have also omitted function prototypes so the compiler won't be able to call the functions correctly. — Weather Vane, May 20 '15 at 09:54
@johnscott : plink and nlink are for previous and next elements. First and last are another story - you could also store a count inside. You append function should be `void append(struct list *l, int n)` — Michel Billaud, May 20 '15 at 10:19

score 0 · Answer 1 · answered May 20 '15 at 10:30

Look at this part

int a=count(*q);
for(int i=0; i<a; i++,temp=temp->nlink)
   {
      s=temp->nlink;
      for(int j=i+1; j<=a; j++,s=s->nlink)
      { ....

Seems you are using indexes from 0 (first loop) to count(*q) (second) for a list with count(*g) elements.

Something is probably wrong in your algorithm - even if it doesnt cause "index out of bounds" errors (because you don't use arrays).

And it appears when you try to sort the second way, because you have not tested the first way seriously enough.

Sorting of double linked list in C

1 Answers1