CODEWITHSUNDEEP
csortinglinked-listmergesort
page4
page4

Reputation: 125

Mergesort on a linked-list using only one function, segmentation fault

I need to implement the function: struct listnode * mergesort(struct listnode *data) My professor provided the main() function testing code. I only need to submit the mergesort function. He told us to do it in C or C++ but the test code main() he gave us is in C.

This is my code right now: I can compile it but when I run it, it crashes. I checked debugger and it gave me segmentation fault. I am also not really sure if this function is correct since I can't get past the testing point in the main().

#include <stdio.h>
#include <stdlib.h>

struct listnode { struct listnode * next;
                         long              value; } ;


struct listnode * mergesort(struct listnode *data)
{   int temp, finished = 0;
    struct listnode *tail, *head, *ahead, *bhead, *atail, *btail;
    if ( data == NULL )
        return;
    //Split
    ahead = atail = head = data;       // first item
    btail = head->next;         // second item
    while(btail->next != NULL)  // anything left
    {
    atail = atail->next;
    btail = btail->next;
    if( btail->next != NULL)
        btail = btail->next;
    }
    bhead = atail->next;        // disconnect the parts
    atail->next = NULL;

    //sort
    mergesort(ahead);
    mergesort(bhead);

    //merge
    if(ahead->value <= bhead->value)  // set the head of resulting list
        head = tail = ahead, ahead = ahead->next;
    else
        head = tail = bhead, bhead = bhead->next;

    while(ahead && bhead)
        if(ahead->value <= bhead->value)  // append the next item
            tail = tail->next = ahead, ahead = ahead->next;
        else
            tail = tail->next = bhead, bhead = bhead->next;

    if(ahead != NULL)
        tail->next = ahead;
    else
        tail->next = bhead;
    return(head);
}


int main(void)
{
   long i;
   struct listnode *node, *tmpnode, *space;
   space =  (struct listnode *) malloc( 500000*sizeof(struct listnode));
   for( i=0; i< 500000; i++ )
   {  (space + i)->value = 2*((17*i)%500000);
      (space + i)->next = space + (i+1);
   }
   (space+499999)->next = NULL;
   node = space;
   printf("\n prepared list, now starting sort\n");
   node = mergesort(node);
   printf("\n checking sorted list\n");
   for( i=0; i < 500000; i++)
   {  if( node == NULL )
      {  printf("List ended early\n"); exit(0);
      }
      if( node->value != 2*i )
      {  printf("Node contains wrong value\n"); exit(0);
      }
      node = node->next;
   }
   printf("Sort successful\n");
   exit(0);
}

Upvotes: 0

Views: 189

Answers (2)

rcgldr
rcgldr

Reputation: 28826

Example function to merge two already sorted lists using pointer to pointer. Since your'e only allowed a single function, you'll have to merge this logic into your mergesort() function. If this is homework, it may seem like you had too much help, but I'm not sure how else to explain the ideas shown in this example.

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
    while(1){
        if(pSrc1 == NULL){
            *ppDst = pSrc2;
            break;
        }
        if(pSrc2 == NULL){
            *ppDst = pSrc1;
            break;
        }
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            continue;
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            continue;
        }
    }
    return pDst;
}

Upvotes: 0

jake
jake

Reputation: 65

if ( data == NULL )
    return;

You should return NULL.

btail = head->next;         // second item
while(btail->next != NULL)  // anything left
{

If btail is set to head->next. If head->next is NULL, you're trying to check in the loop NULL->next != NULL which isn't a thing.

if( btail->next != NULL)
    btail = btail->next;
}

You need to check if btail is NULL before you check ->next. Just above you are setting btail = btail->next; so it could be set to NULL.

Also the loop above has the same issue, you need to check null before you do stuff with next.

There may be issues with the below code, but the above code needs way more error checking.

Upvotes: 1

Related Questions