Thread: 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...

i have tried your code, but it seems doesn;t work

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..

so should i point to NULL of the List, because the while loop is like an infinite loop , right?

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...