Alex Smith - 1 year ago 96
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_;

{
(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));

}

student_record_node*,struct student_record_node*))

{

int swapped;
struct student_record_node *lptr = NULL;

if (ptr1 == NULL)
return;

do
{
swapped = 0;

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

}

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

}
``````

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);
}

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;

return;

do
{
swapped = 0;

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_);
{
/* ptr1 is now the second node. */
}
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] %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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download