linked list

This is a discussion on linked list within the C Programming forums, part of the General Programming Boards category; Code: typedef struct node* link; struct node { int item; link next; }; #define key(A) (A) #define less(A, B) (key(A) ...

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    9

    linked list

    Code:
    typedef struct node* link;
    struct node { int item; link next; };
    
    #define key(A) (A)
    #define less(A, B) (key(A) <= key(B)) /* stable with code below */
    
    link merge(link a, link b)
     { struct node head; link c = &head;
       while ((a != NULL) && (b != NULL))
         if (less(a->item, b->item))
           { c->next = a; c = a; a = a->next; }
         else
           { c->next = b; c = b; b = b->next; }
       c->next = (a == NULL) ? b : a;
       return head.next;
     }
    
    link msort_rs(link c)
     { link a, b;
       if (c->next == NULL) return c;
       a = c; b = c->next;
       while ((b != NULL) && (b->next != NULL))
         { c = c->next; b = b->next->next; }
       b = c->next; c->next = NULL;
       return merge(msort_rs(a), msort_rs(b));
     }
    main()
    {
    int i;
    struct node heada;
    link t = &heada;
    for(i = 0; i < 5; i++)
    {
       t->next = malloc(sizeof *t);
       t = t->next;
       t->next = NULL;
       t->item = rand() %100;
     }
     msort_rs(t);
     for(i = 0; i < 5; i++)
     {
       printf("%d", t->item);
       t = t->next;
       }
    }
    the msort_rs(t) doesn't sort linked list t, do i need a pointer to pointer here like
    and how come when i run it the first element in the list is 65536??
    Code:
    link b;
    ..
    b = msort_rs(t);
    
    for( i =0, i < 10; i++)
    {
     printf("%d", b->item);
     b = b->next;
    }

  2. #2
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    how come when i run it the first element in the list is 65536??
    you never set the value of the first element.
    Code:
    for(i = 0; i < 5; i++)
    {
       t->next = malloc(sizeof *t);
       t = t->next;                           /* t now points to the next element in the list */
       t->next = NULL;
       t->item = rand() %100;        /* set the value in *t */
    }
    try this instead
    Code:
    for(i = 0; i < 5; i++)
    {
       t->item = rand() %100;      /* set item before moving on through the list */
       t->next = malloc(sizeof *t);
       t = t->next;
    
    }
    /* set last element in the list */
    t->item = rand() % 100;
    t->next = NULL;
    note also that at the end of the loop t points to the last element in the list so if you want to sort the whole list (rather than just the last element!) you have to do something like:
    Code:
    t = &heada;  /* reset t to top of list */
    msort_rs(t);
    for(t = &heada; t != NULL; t=t->next)
    {
       printf("%d\n", t->item);
    }
    That should sort it I think...
    DavT
    -----------------------------------------------

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21