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