what's wrong...

This is a discussion on what's wrong... within the C Programming forums, part of the General Programming Boards category; Code: #include <stdlib.h> #include <stdio.h> #include <time.h> #include <assert.h> typedef struct node* link; struct node { int item; link next; ...

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

    Unhappy what's wrong...

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    #include <assert.h>
    
    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 msort2(int n, link a, link b)
    {
       int n1;
       link xs1, xs2, c = NULL;
       if(n == 0)
       {
           b = a;
           return NULL;
       }
    
       if(n == 1)
       {
           b = a->next;
           a->next = NULL;
           return a;
       }
       n1 = n/2;
       xs1 = msort2(n1,a,b);
       xs2 = msort2((n-n1),b,c);
       b = c;
    
       return merge(xs1,xs2);
    }
    
    int listlength(link c)
    {
       int counter = 0;
       link list = c;
       while(list)
       {
           counter++;
           list = list->next;
       }
       return counter;
    }
    
    link merge_no_scan(link c)
    {
       link b = NULL;
       int n = listlength(c);          /* find the length of the list  */
       return msort2(n,c,b);
    }
    
    main()
    {
       link list;
       list = createList(5);
       PrintList(list);
       list = merge_no_scan(list);
       PrintList(list);
    }
    
    link createList(int size)
    {
     int i; link list;
     list = 0;
     for(i = 0;i < size; ++i)
     {
          link nw;
          nw = (link)malloc(sizeof(struct node));
          assert(nw!=0);
          nw->item = rand()%1000;
          nw->next = list;
          list = nw;
       }
     return list;
    }
    void PrintList(link list)
    {
      link p;
      printf("List:");
      for(p = list;p!=0; p=p->next)
          printf("%d ", p->item);
      printf("\n");
    }
    i can;t see any problem in main(), creatList, printList, and listlenght, where' s the problem, when i run it, it just hang...

  2. #2
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    I've only glanced at the code, but createList() looks like it is
    wrong. I'd do it something like this:
    Code:
    link createList (int size)
    {
      link list = NULL, nw = NULL;
      int i;
    
      if (size > 0){
        if ((list = malloc(sizeof(*list))) == NULL)
          errorFunction("out of mem in createList");
        list->item = rand() % 1000;
        nw = list;
    
        for (i = 1; i < size; i++){
          if((nw->next = malloc(sizeof(*(nw->next)))) == NULL)
            errorFunction("out of mem in createList");
          nw = nw->next;
          nw->item = rand() % 1000;
        }
        nw->next = NULL;
      }
    
      return list;
    }
    I haven't tried to compile it, so there maybe some bugs,
    but I think it's about right. The important point is that 'list'
    stays pointing to the top of the list, and memory is allocated
    and pointed to by the last created element.

    ::edit::
    use:
    Code:
    int main(void) /* or int main(int argc, char * argv[])  */
    {
      /* code here */
      return 0;
    }
    Last edited by DavT; 10-08-2003 at 11:45 AM.
    DavT
    -----------------------------------------------

  3. #3
    Registered User
    Join Date
    Oct 2003
    Posts
    9
    i have tried your code, but it seems doesn;t work

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    link list;
     list = 0;
     for(i = 0;i < size; ++i)
     {
          link nw;
          nw = (link)malloc(sizeof(struct node));
          assert(nw!=0);
          nw->item = rand()%1000;
          nw->next = list;
    See your problem yet? 'list' doesn't point to anything. As such, the first node you allocate's 'nw->next' points to some random spot in memory. Thus...
    Code:
    int listlength(link c)
    {
       int counter = 0;
       link list = c;
       while(list)
       {
           counter++;
           list = list->next;
    'listlength' blissfully wanders through memory hoping to encounter a null once it runs off the end of your list.

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Oct 2003
    Posts
    9
    but i use gdb shows the problem is
    Code:
     if(n == 1)
      {
          b = a->next;      /* Dereferencing a null pointer.... */
          a->next = NULL;
          return a;
      }
      n1 = n/2;
      xs1 = msort2(n1,a,b);
      xs2 = msort2((n-n1),b,c);  
      b = c;
    
      return merge(xs1,xs2);
    }
    how can i modify the code..

  6. #6
    Registered User
    Join Date
    Oct 2003
    Posts
    9
    so should i point to NULL of the List, because the while loop is like an infinite loop , right?

  7. #7
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Check to ensure your pointer isn't NULL before you derefence it.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  8. #8
    Registered User
    Join Date
    Oct 2003
    Posts
    9
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    #include <assert.h>
    
    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));
      }
    
    link msort2(int n, link a, *link b)
    {
        int n1;
        link xs1, xs2, c = NULL;
        if(n == 0)
        {
            b = a;
            return NULL;
        }
    
        if(n == 1)
        {
            b = a->next;      //problem : null pointer;
            a->next = NULL;
            return a;
        }
        n1 = n/2;
        xs1 = msort2(n1,a,b);
        xs2 = msort2((n-n1),b,c);//  problem: have invalid parameters. msort2 ( (n-n1) = 1, b = NULL, c = NULL), then msort2(1,NULL,NULL)--error
    
        b = c;
        return merge(xs1,xs2);
    }
    
    int listlength(link c)
    {
        int counter = 0;
        while(c)
        {
            counter++;
            c = c->next;
        }
        return counter;
    }
    
    link merge_no_scan(link c)
    {
        link b = NULL;
        int n = listlength(c);
        return msort2(n,c,&b);
    }
    
    link insertionSort(link list)
    {
      link k,nwlist;
      if(list==0 || list->next==0)
          return list;
      nwlist=list; k=list->next; nwlist->next=0; // 1st node is new list
    
      while(k!=0)
      {
          link ptr;
          if(nwlist->item > k->item)
          {
              link tmp;
              tmp = k;
              k=k->next;
              tmp->next = nwlist;
          }
          for(ptr=nwlist;ptr->next!=0;ptr=ptr->next) // check rest
          {
              if(ptr->next->item >k->item)
                  break;
          }
          if(ptr->next!=0)
          {
              link tmp;
              tmp=k;
              k=k->next;
              tmp->next = ptr->next;
    		  ptr->next=tmp;
              continue;
          }
          else
          {
              ptr->next=k;
              k=k->next;
    	      ptr->next->next=0;
              continue;
           }
        }
    	return nwlist;
    }
    
    link createList (int size)
    {
      link list = NULL, nw = NULL;
      int i;
    
      if (size > 0)
      {
          if ((list = malloc(sizeof(*list))) == NULL)
              printf("out of mem in createList");
          list->item = rand() % 1000;
          nw = list;
          for (i = 1; i < size ; i++)
          {
              if((nw->next = malloc(sizeof(*(nw->next)))) == NULL)
                  printf("out of mem in createList");
              nw = nw->next;
              nw->item = rand() % 1000;
          }
        nw->next = NULL;
      }
      return list;
    }
    
    void PrintList(link list)
    {
        link p;
        printf("List:");
        for(p = list;p!=0; p=p->next)
            printf("%d ", p->item);
        printf("\n");
    }
    
    main()
    {
        clock_t start, end;
        double cpu_time_used;
        link list;
        start = clock();
        list = createList(5);
        PrintList(list);
        list = merge_no_scan(list);
        PrintList(list);
        end = clock();
        cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
        printf("%f",cpu_time_used);
    
    }
    i think the main thing is it doesn;t modified the link b as i like to be....how cani fix it...

  9. #9
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>the main thing is it doesn;t modified the link b as i like to be<<
    You need to be more descriptive about your problem. I'm not going to hunt through your code and change it to what I assume your needs to be.

    Simplify the problem by restricting your code to the affected area. This will make your posts are for us to digest.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  10. #10
    Registered User
    Join Date
    Oct 2003
    Posts
    9
    Code:
    typedef struct node* link;
    struct node { int item; link next; };
    ...
    link msort2(int n, link a, link b)
    {
        int n1;
        link xs1, xs2, c = NULL;
        if(n == 0)
        {
            b = a;
            return NULL;
        }
    
        if(n == 1)
        {
            b = a->next;      //problem : null pointer;
            a->next = NULL;
            return a;
        }
        n1 = n/2;
        xs1 = msort2(n1,a,b);
        xs2 = msort2((n-n1),b,c);//  problem: have invalid parameters. msort2 ( (n-n1) = 1, b = NULL, c = NULL), then msort2(1,NULL,NULL)--error
    
        b = c;
        return merge(xs1,xs2);
    }
    
    int listlength(link c)
    {
        int counter = 0;
        while(c)
        {
            counter++;
            c = c->next;
        }
        return counter;
    }
    
    link merge_no_scan(link c)
    {
        link b = NULL;
        int n = listlength(c);
        return msort2(n,c,b);
    }
    main()
    ...
    create linked list c;
    merge_no_scan(c);
    i think the main thing is it doesn;t modified the link b as i like to be....how can i fix it...
    for example:
    i create a link list c : 5->4->3->2->1->NULL
    b:NULL
    find the lenght of the linked list:5
    so i passing msort2(5,a,b);
    msort 2 should do the following:
    if n == 0 return the list
    if n == 1 return the first node of the list,
    i assume this is something like:
    a:5->4->3->2->1->NULL
    b:NULL
    first pass:
    n1 = 2
    ...second pass
    n1 = 1;
    xs1 = msort(1,a,b)
    and a would be: 5->NULL
    b:4->3->2->1->NULL;
    and do it recursively to sort a linked list
    Last edited by dreamkk; 10-09-2003 at 07:21 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 07-15-2004, 04:30 PM
  2. Debugging-Looking in the wrong places
    By JaWiB in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 11-03-2003, 10:50 PM
  3. Confused: What is wrong with void??
    By Machewy in forum C++ Programming
    Replies: 19
    Last Post: 04-15-2003, 01:40 PM
  4. God
    By datainjector in forum A Brief History of Cprogramming.com
    Replies: 746
    Last Post: 12-22-2002, 12:01 PM
  5. Whats wrong?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 07-14-2002, 02:04 PM

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