initialize

1 files changed, 334 insertions, 0 deletions

diff --git a/c/dataStructure/线性表/线性链表/operation.c b/c/dataStructure/线性表/线性链表/operation.c
new file mode 100755
index 0000000..c0dc934
--- /dev/null
+++ b/c/dataStructure/线性表/线性链表/operation.c
@@ -0,0 +1,334 @@
+/* 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;
+}
\ No newline at end of file