0

I have written a program which cretates 12 tables with random capacities. I want to sort that doubly linked list by insertion. Although the code was compiled with no error, I got run-time error. I have no idea why. Is there anyone can help me?

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define MAX 12

struct Table {
      int capacity;
      struct Table *next;
      struct Table *prev;
};

typedef void (*table_func_pnt) (struct Table *table);
struct Table *add_random_number(struct Table *head);
void insertion_sort(struct Table **head);

void list_tables(struct Table *head, table_func_pnt func);
void print_capacity(struct Table *table);

int main(int argc, char **argv)
{
      srand(time(0));

      struct Table *list = NULL;

     for(int i = 0; i<MAX; ++i){
          list = add_random_number(list);
     }

     list_tables(list,print_capacity);
     printf("\n");


     insertion_sort(&list);


     list_tables(list,print_capacity);

     return EXIT_SUCCESS;

}

struct Table *add_random_number(struct Table *head){

        struct Table *table = malloc(sizeof(struct Table));
        table->capacity = 2 + rand() % 10;
        table->next = head;

        return table;
}

void list_tables(struct Table *head, table_func_pnt func)
{
        while(head){
            func(head);
            head = head->next;
        }
}

void print_capacity(struct Table *table)
{
        printf("%d ",table->capacity);
}

void insertion_sort(struct Table **head)
{
        int n;

        struct Table *curr;
        curr = *head;

        if(curr->next == NULL)
            return;

        struct Table *ptr;
        struct Table *temp;
        curr = curr->next;

        while(curr != NULL){

                n = 0;
                ptr = curr;
                temp = curr->prev;
                curr = curr->next;

                 while(temp != NULL && temp->capacity > ptr->capacity){
                        n++ ;
                        temp = temp->prev;
                 }if(n){
                        ptr->prev->next = ptr->next;
                        if(ptr->next != NULL)
                        ptr->next->prev = ptr->prev;

                        if(temp == NULL){
                            temp = *head;
                            ptr->prev = NULL;
                            ptr->next = temp;
                            ptr->next->prev =ptr;
                            *head = ptr;
                        }else{
                           temp = temp->next;
                           temp->prev->next = ptr;
                           ptr->prev = temp->prev;
                           temp->prev = ptr;
                           ptr->next = temp;
                       }
                }

       }

}
3
  • Try running in a debugger, to locate where the crash happens. Commented Apr 28, 2015 at 16:41
  • If you want a doubly linked list, you need something like if(head!=NULL){head->prev=table;} in function add_random_number() Commented Apr 28, 2015 at 16:57
  • You are right @francis Commented Apr 28, 2015 at 17:05

1 Answer 1

1

The reason you get runtime errors from insertion_sort() (but not before) is because you have forgotten to set the prev field of the linked list. So it's actually a singly linked list, and the simple parse list_tables() works. But in insertion_sort() you start using the uninitialised prev pointers, resulting in a crash.

Sign up to request clarification or add additional context in comments.

1 Comment

@Rinzler - an alternative approach would be a sort that only uses the next pointers, then after the sort is done, traversing through the sorted list to set the previous pointers. I'm not sure if this would be significantly faster or worth the effort. If speed was an issue (very large list), then a bottom up merge sort would be much faster.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.