Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
959 views
in Technique[技术] by (71.8m points)

c - swap in doubly linked list

I am trying to swap two nodes in a doubly linked list. Below is the part of program having swap function.

 int swap (int x, int y)
{
    struct node *temp = NULL ;
    struct node *ptr1, *ptr2;
    temp = (struct node *)malloc(sizeof(struct node));


    if (head == NULL )
    {
        printf("Null Nodes");

    }
    else
    {
        ptr1 = ptr2 = head;

        int count = 1;
        while (count != x)
        {
            ptr1 = ptr1->next;
            count++;

        }



        int count2 = 1;
        while (count2 != y)
        {
            ptr2 = ptr2->next;
            count2++;   

        }       


        ptr1->next->prev = ptr2;
        ptr1->prev->next = ptr2;
        ptr2->next->prev = ptr1;
        ptr2->prev->next = ptr1;

    temp->prev = ptr1->prev;
    ptr1->prev = ptr2->prev;
    ptr2->prev = temp->prev;

    temp->next = ptr1->next;
    ptr1->next = ptr2->next;
    ptr2->next = temp->next;


    }
    return 0;
}

When I run this program, in case of 1st and 2nd node, it crashes. while in case of any other nodes, it gives infinite loop output. (eg:- 2->4 2->4 2->4....so on)`.

I know there are some more questions about node swappings, but I didn't find any one similar to my problem. Please help me out..!!

Thanks in Advance.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The code will fail if ptr1 == head (ptr1->prev == NULL) or ptr2 == head (ptr2->prev == NULL), because it ends up trying to use head->next, which doesn't exist. There also needs to be a check for the end of a list, if ptr1->next == NULL or ptr2->next == NULL, which can be handled using a local tail pointer. Using pointers to pointer to node can simplify the code. For example the pointer to next pointer to ptr1 could be &ptr1->prev->next or &head. The pointer to prev pointer to ptr2 could be &ptr2->next->prev or &tail (and set tail = ptr2).

Using pointers to pointer to node fixes the issue with swapping adjacent nodes. Also temp can be a pointer to node.

Example code using pointers to nodes (instead of counts) to swap:

typedef struct node NODE;
/* ... */
NODE * SwapNodes(NODE *head, NODE *ptr1, NODE *ptr2)
{
NODE **p1pn;            /* & ptr1->prev->next */
NODE **p1np;            /* & ptr1->next->prev */
NODE **p2pn;            /* & b->prev->next */
NODE **p2np;            /* & b->next->prev */
NODE *tail;             /* only used when x->next == NULL */
NODE *temp;             /* temp */
    if(head == NULL || ptr1 == NULL || ptr2 == NULL || ptr1 == ptr2)
        return head;
    if(head == ptr1)
        p1pn = &head;
    else
        p1pn = &ptr1->prev->next;
    if(head == ptr2)
        p2pn = &head;
    else
        p2pn = &ptr2->prev->next;
    if(ptr1->next == NULL){
        p1np = &tail;
        tail = ptr1;
    } else
        p1np = &ptr1->next->prev;
    if(ptr2->next == NULL){
        p2np = &tail;
        tail = ptr2;
    }else
        p2np = &ptr2->next->prev;
    *p1pn = ptr2;
    *p1np = ptr2;
    *p2pn = ptr1;
    *p2np = ptr1;
    temp = ptr1->prev;
    ptr1->prev = ptr2->prev;
    ptr2->prev = temp;
    temp = ptr1->next;
    ptr1->next = ptr2->next;
    ptr2->next = temp;
    return head;
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...