LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Doubly Linked List Insertion Sort in C (https://www.linuxquestions.org/questions/programming-9/doubly-linked-list-insertion-sort-in-c-4175415860/)

fahad.anwar 07-10-2012 04:38 AM
Doubly Linked List Insertion Sort in C
 
Quote:
Hi all

I am trying to insert elements into a doubly linked list in a sorted order. However I keep getting segmentation faults. Please help me figure out where the problem is:

Thanks in advance


struct node *insert_node( struct node *head, int *value )
{
struct node *new_node = NULL;
struct node *cur_node = NULL;
struct node *last_node = NULL;
int found; /* 1 means found a place to insert the new node in, 0 means not*/
new_node = (struct node *)malloc(sizeof(struct node));
if(new_node == NULL)
{
printf("memory problem\n");
}
new_node->number = *value;
/* If the first element */
if (head == NULL)
{
new_node->next = new_node->prev = NULL;
head = new_node;
}
else if (new_node->number < head->number)
{
new_node->next = head;
head->prev = new_node;
head = new_node;
head->prev = NULL;
}
else
{
cur_node = head;
found = 0;
while (( cur_node != NULL ) && ( found == 0 ))
{
if( new_node->number < cur_node->number )
{
found = 1;
}
else
{
last_node = cur_node;
//cur_node = cur_node->next;
}
}
/* We got the right place to insert our node */
if( found == 1 )
new_node->next = cur_node;
/* Insert at the tail of the list */
else
{
last_node->next = new_node;
new_node->prev = last_node;
cur_node->prev = new_node;
cur_node->next = NULL;
cur_node = new_node;
}
}
return head;
}

thanks

visar 07-10-2012 07:24 PM
Quote:
Originally Posted by fahad.anwar (Post 4723790)
thanks
This is the correct code:

Code:
struct node
{
        int number;
        struct node * next;
        struct node * prev;
};

struct node *insert_node( struct node **head, int *value )
{
        struct node *new_node = NULL;
        struct node *cur_node = NULL;
        int found; /* 1 means found a place to insert the new node in, 0 means not*/
        new_node = (struct node *)malloc(sizeof(struct node));
        if(new_node == NULL)
        {
                printf("memory problem\n");
                exit(1);
        }
        new_node->number = *value;
/* If the first element */
        if (*head == NULL)
        {
                new_node->next = new_node->prev = new_node;
                *head = new_node;
        }
        else if (new_node->number < (*head)->number)
        {
                new_node->next = *head;
                new_node->prev = (*head)->prev;
                (*head)->prev = new_node;
                *head = new_node;
                (*head)->prev->next = *head;
        }
        else
        {
                cur_node = *head;
                found = 0;
                do
                {
                        if( new_node->number < cur_node->number )
                        {
                                found = 1;
                                break;
                        }
                        else
                        {
//                                last_node = cur_node;
                                cur_node = cur_node->next;
                        }
                }
                while ( cur_node != *head );
/* We got the right place to insert our node */
                if( found == 1 )
                {
                        new_node->next = cur_node;
                        new_node->prev = cur_node->prev;
                        cur_node->prev->next = new_node;
                        cur_node->prev = new_node;
                }
/* Insert at the tail of the list */
                else
                {
                        new_node->next = *head;
                        new_node->prev = (*head)->prev;
                        (*head)->prev->next = new_node;
                        (*head)->prev = new_node;
                }
        }
        return *head;
}

Tinkster 07-11-2012 03:36 PM
Moved: This thread is more suitable in <PROGRAMMING> and has been moved accordingly to help your thread/question get the exposure it deserves.


All times are GMT -5. The time now is 03:43 PM.