path: root/c/dataStructure/线性表/线性链表/operation.c

/* Operation based on pointer with head */
#include "list.h"

void append(List * A, List * B);             // Append B's elements to A
List ordered_merge(List * A, List * B);     // Merge B's elements to A orderedly
void overlap(List * A, List * B);
void ANotB(List * A, List * B);
void split(List * A, List * B, List * C);
void reverse(List * A);

// Driver
int main(void)
{
    // This comment is use for test reverse function
    ///*
    List a;
    InitList(&a);

    int d1[] = {1,2,3,4,5,6,7,8,9,10};

    for (int i = 0; i < sizeof(d1)/sizeof(int); i++)
        AddElem(&a,*(d1+i));

    TraverseList(&a);

    reverse(&a);

    TraverseList(&a);

    DestroyList(&a);

    return 0;
    //*/

    // This comment is use for test split function
    /*
    ElemType d1[] = {-3,9,-5,1,3,6,-13,0,0,-44,42,123,453,12,42,-312,-1324};

    InitList(&a);
    for (int i = 0; i < sizeof(d1)/sizeof(int); i++)
        AddElem(&a,d1[i]);

    TraverseList(&a);

    split(&a,&b,&c);
    TraverseList(&b);
    TraverseList(&c);

    DestroyList(&b);
    DestroyList(&c);

    free(a);

    return 0;
    */

    // This comment is use for test function takes 2 arguments
    /*
    ElemType d1[] = {11,22,33,44,99};
    ElemType d2[] = {44,55,66,77,88};

    // Initialize list
    InitList(&a);
    InitList(&b);

    for (int i = 0; i < sizeof(d1)/sizeof(int); i++)
        AddElem(&a,d1[i]);
    
    for (int i = 0; i < sizeof(d2)/sizeof(int); i++)
        AddElem(&b,d2[i]);

    TraverseList(&a);
    TraverseList(&b);

    
    // Check initialization
    overlap(&a,&b);

    TraverseList(&a);

    // Release list
    DestroyList(&a);
    free(a);

    return 0;
    */
}

// ------------------------------------------ list with head -----------------------------------------
void append(List * A, List * B)
{
    // Create a new pointer to point A;
    List C = *A;

    // Get next pointer until hits NULL pointer
    while (C->next)
        C = C->next;
    
    // Attach last NULL pointer to first element of B
    C->next = (*B)->next;

    // Release B's head
    free(*B);

    // Now A has both A and B's elements
}

List ordered_merge(List * A, List * B)
{
    List T1, T2;
    // For convenience, T1 is smallest one
    if ((*A)->next->data <= (*B)->next->data)
    {
        T1 = *A;
        T2 = *B;
    }
    else
    {
        T1 = *B;
        T2 = *A;
    }

    // To keep T1 still
    List T4 = T1;

    // Store next pointer of bigger one
    List T3;

    /* Both start from Head pointer. So T->next is the real data
     * we manipulate. Assume T->next is P
     *
     * If P1->data <= P2->data:
     * We use P3 to store P2->next,
     * attach P2->next with P4,
     * and attach P2 to P4.
     * This process will still P1 and move P2 to next
     * as long as condition remains true.
     * 
     * Else, if P1->data > P2->data
     * Then we move P1 to next to compare with P2 */
    while (T4->next && T2->next)
    {
        if (T4->next->data >= T2->next->data)
        {
            T3 = T2->next->next;
            T2->next->next = T4->next;
            T4->next = T2->next;
            T2->next = T3;
        }
        else
            T4 = T4->next;
    }

    /* Due to every elements are ordered.
     * so if smaller one runs out,
     * we only need to append bigger one to it.
     *
     * If bigger one runs out, We won't do anything. */
    if (!T4->next)
    {
        T4->next = T2->next;
        T2->next = NULL;

    }

    // Clear empty list
    if (!(*A)->next)
        free(*A);
    else
        free(*B);
    
    return T1;
}

void overlap (List * A, List * B)
{
    /* If A > B,    release B, moving B to next
       If B > A,    release A, moving A to next
       If A = B,    release B, moving A&B to next */
    List a = *A, b = *B, c;

    while (a->next && b->next)
    {
        if (a->next->data > b->next->data)
        {
            c = b->next->next;
            free(b->next);
            b->next = c;
        }
        else if (a->next->data < b->next->data)
        {
            c = a->next->next;
            free(a->next);
            a->next = c;
        }
        else
        {
            a = a->next;
            c = b->next->next;
            free(b->next);
            b->next = c;
        }
    }

    if (a->next)
    {
        c = a->next->next;
        free(a->next);
        a->next = c;
    }
    else if (b->next)
    {
        c = b->next->next;
        free(b->next);
        b->next = c;
    }
    free(b);
}

// Get elements appear only in A
void ANotB (List * A, List * B)
{
    /* If A > B, then release B, moving to next
     * If A < B, moving A till A == B or A > B
     * If A = B, Release B, moving both A and B
     */
    List t1 = *A, t2 = *B;
    List tmp;

    while (t1->next && t2->next)
    {
        if (t1->next->data > t2->next->data)
        {
            tmp = t2->next->next;
            free(t2->next);
            t2->next = tmp;
        }

        else if (t1->next->data == t2->next->data)
        {
            tmp = t2->next->next;
            free(t2->next);
            t2->next = tmp;

            tmp = t1->next->next;
            free(t1->next);
            t1->next = tmp;
        }
        else
            t1 = t1->next;
    }

    while (t2)
    {
        tmp = t2->next;
        free(t2);
        t2 = tmp;
    }
}

void split(List * A, List * B, List * C)
{
    /*  if A < 0
     *      if !B
     *          B get A node
     *      else
     *          bp get A node
     *  else A > 0
     *      same as B
     *  else A == 0
     *      release A node, move A to A->next
     */
    List b, c, tmp, bp, cp, op;
    tmp = (*A)->next;
    *B = NULL;
    *C = NULL;

    while (tmp)
        if (tmp->data < 0)
            if (!*B)
            {
                *B = tmp;
                tmp = tmp->next;
                (*B)->next = NULL;
                bp = *B;
            }
            else
            {
                bp->next = tmp;
                tmp = tmp->next;
                b = bp->next;
                b->next = NULL;
                bp = bp->next;
            }
        else if (tmp->data > 0)
            if (!*C)
            {
                *C = tmp;
                tmp = tmp->next;
                (*C)->next = NULL;
                cp = *C;
            }
            else
            {
                cp->next = tmp;
                tmp = tmp->next;
                c = cp->next;
                c->next = NULL;
                cp = cp->next;
            }
        else
        {
            op = tmp;
            tmp = tmp->next;
            free(op);
        }
}
// ------------------------------------------ list with head -----------------------------------------

// this function will take list without head
void reverse(List * A)
{
    List prior = NULL, current;

    while (*A)
    {
        current = *A;
        *A = (*A)->next;
        current->next = prior;
        prior = current;
    }

    *A = current;
}