# what's wrong...

• 10-08-2003
dreamkk
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...
• 10-08-2003
DavT
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; }```
• 10-08-2003
dreamkk
i have tried your code, but it seems doesn;t work
• 10-08-2003
quzah
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.
• 10-08-2003
dreamkk
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..
• 10-08-2003
dreamkk
so should i point to NULL of the List, because the while loop is like an infinite loop , right?
• 10-09-2003
Hammer
Check to ensure your pointer isn't NULL before you derefence it.
• 10-09-2003
dreamkk
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...
• 10-09-2003
Hammer
>>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.
• 10-09-2003
dreamkk
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()
...
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