Alex Smith Alex Smith - 9 days ago 4
C Question

C swapping with doubly linked list

I'm trying to swap the position of nodes in a linked list
and later on sorting with a sort function. I'm getting a logical error in either one of these functions. When I run the program it goes in infinite loop.

updated code

int adjuctNodes(struct student_record_node** n1, struct student_record_node** n2)

{
struct student_record_node* prev_;
struct student_record_node* next_;
return((*n1)->next_==(*n2) && (*n2)->prev_ == (*n1))||
( (*n1)->prev_ ==(*n2) && (*n2)->next_ == (*n1) );
}

void updateOuterPointer(struct student_record_node** n)

{
struct student_record_node* next_;
struct student_record_node* prev_;
if((*n)->next_!=NULL)
(*n)->prev_->next_=(*n);
if((*n)->next_ !=NULL)
(*n)->next_->prev_=(*n);
}


/*Swaping */

void swap(struct student_record_node** node1, struct student_record_node** node2)

{


struct student_recod_node* prev_;
struct student_recod_node* next_;
struct student_record_node* ptr=(*node1)->next_;

if(adjucntNodes((node1),(node2)))
{
(node1)->prev_=pnode2;
(node2)->prev_=pnode0;
(node1)->next_=pnode3;
(node2)->next_=pnode1;

}else{

(node1)->prev_=pnode1;
(node2)->prev_=pnode0;
(node1)->next_=pnode3;
(node2)->next_=pnode2;
}

updateOuterPointer((node1));
updateOuterPointer((node2));

}
/*Sorting linked list*/


void sort(struct student_record_node**recordsHead,int(*compare_fcn)(struct
student_record_node*,struct student_record_node*))

{

int swapped;
struct student_record_node *ptr1=*recordsHead;
struct student_record_node *lptr = NULL;

if (ptr1 == NULL)
return;

do
{
swapped = 0;
ptr1 = *recordsHead;


while (ptr1->next_ != lptr)
{
if (compare_fcn(ptr1,ptr1->next_))
{
printf("swapping\n");
swap(&ptr1,&ptr1->next_);
if(ptr1==*recordsHead)
{
(*recordsHead)=ptr1->next_;
}
swapped=1;

}

else ptr1 = ptr1->next_;
}
lptr = ptr1;
;
}
while (swapped);


}

Answer

There are two main problems in the original code, and possibly a third:

  1. The swap function does not work when the nodes being swapped are adjacent, but the sort function only swaps adjacent nodes!
  2. After swapping two nodes ptr1 and ptr1->next_, the sort function checks if the first node being swapped, ptr1, was at the head of the list, and if so makes ptr1->next_ the head of the list. However, the two nodes are now in reverse order, so it should make ptr1->prev_ the head of the list in this case.
  3. Comparison functions usually return a negative value if the first argument is less than the second argument, zero if they are equal, or a positive value if the first argument is greater than the second argument. The sort function currently seems to expect the comparison function to return 0 if the first argument is less than or equal to the second argument. This may or may not be a bug, but it is unconventional.

Additionally, the interface to the swap function can be simplified as there is no need to pass pointers to pointers to the nodes.

The following example program fixes the above problems:

#include <stdio.h>
#include <string.h>

struct student_record_node {
    struct student_record_node *next_;
    struct student_record_node *prev_;
    const char *name;
    unsigned int age;
};

void swap(struct student_record_node *node1, struct student_record_node *node2)
{
    struct student_record_node *ptr1, *ptr2;

    /* Swap the 'next_' pointers, taking adjacency into account. */
    ptr1 = node1 == node2->next_ ? node2 : node2->next_;
    ptr2 = node2 == node1->next_ ? node1 : node1->next_;
    node1->next_ = ptr1;
    node2->next_ = ptr2;
    /* Swap the 'prev_' pointers, taking adjacency into account. */
    ptr1 = node1 == node2->prev_ ? node2 : node2->prev_;
    ptr2 = node2 == node1->prev_ ? node1 : node1->prev_;
    node1->prev_ = ptr1;
    node2->prev_ = ptr2;
    /* Fix the links from other nodes. */
    if (node1->next_) node1->next_->prev_ = node1;
    if (node1->prev_) node1->prev_->next_ = node1;
    if (node2->next_) node2->next_->prev_ = node2;
    if (node2->prev_) node2->prev_->next_ = node2;
}

int compare_ages(const struct student_record_node *a,
        const struct student_record_node *b)
{
    return a->age < b->age ? -1 : a->age > b->age ? 1 : 0;
}

int compare_names(const struct student_record_node *a,
        const struct student_record_node *b)
{
    return strcmp(a->name, b->name);
}

void sort(struct student_record_node **recordsHead,
        int(*compare_fcn)(const struct student_record_node *,
                const struct student_record_node *))
{
    int swapped;
    struct student_record_node *ptr1;
    struct student_record_node *lptr = NULL;

    if (*recordsHead == NULL)
        return;

    do
    {
        swapped = 0;
        ptr1 = *recordsHead;

        while (ptr1->next_ != lptr)
        {
            if (compare_fcn(ptr1, ptr1->next_) > 0)
            {
                printf("swapping (%s:%u <=> %s:%u)\n", ptr1->name, ptr1->age,
                        ptr1->next_->name, ptr1->next_->age);
                swap(ptr1, ptr1->next_);
                if (ptr1 == *recordsHead)
                {
                    /* ptr1 is now the second node. */
                    (*recordsHead) = ptr1->prev_;
                }
                swapped = 1;
            }
            else
            {
                ptr1 = ptr1->next_;
            }
        }
        lptr = ptr1;
    }
    while (swapped);
}

void dump(const struct student_record_node *students)
{
    const struct student_record_node *prev_ = NULL;
    unsigned int pos = 0;

    while (students)
    {
        if (students->prev_ != prev_)
        {
            printf("[%u] ** Bad prev_ link!\n", pos);
        }
        printf("[%u] %s:%u\n", pos, students->name, students->age);
        pos++;
        prev_ = students;
        students = students->next_;
    }
}

int main(void)
{
    static struct student_record_node testdata[] =
    {
        { testdata + 1, NULL, "susan", 20 },
        { testdata + 2, testdata + 0, "bill", 21 },
        { testdata + 3, testdata + 1, "joe", 18 },
        { testdata + 4, testdata + 2, "tom", 19 },
        { NULL, testdata + 3, "karen", 21 },
    };
    struct student_record_node *students = testdata;

    puts("Original order:");
    dump(students);
    puts("By name:");
    sort(&students, compare_names);
    dump(students);
    puts("By age:");
    sort(&students, compare_ages);
    dump(students);
    return 0;
}

Output:

Original order:
[0] susan:20
[1] bill:21
[2] joe:18
[3] tom:19
[4] karen:21
By name:
swapping (susan:20 <=> bill:21)
swapping (susan:20 <=> joe:18)
swapping (tom:19 <=> karen:21)
swapping (susan:20 <=> karen:21)
[0] bill:21
[1] joe:18
[2] karen:21
[3] susan:20
[4] tom:19
By age:
swapping (bill:21 <=> joe:18)
swapping (karen:21 <=> susan:20)
swapping (karen:21 <=> tom:19)
swapping (bill:21 <=> susan:20)
swapping (bill:21 <=> tom:19)
swapping (susan:20 <=> tom:19)
[0] joe:18
[1] tom:19
[2] susan:20
[3] bill:21
[4] karen:21
Comments