remove

8 files changed, 451 insertions, 0 deletions

diff --git a/DSAA/chap3_lists_stacks_queues/ex_2.c b/DSAA/chap3_lists_stacks_queues/ex_2.c
new file mode 100644
index 0000000..103fef6
--- /dev/null
+++ b/DSAA/chap3_lists_stacks_queues/ex_2.c
@@ -0,0 +1,64 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+Position FindNth( List L, int nth )
+{
+        int i;
+        Position P;
+        P = L;
+
+        for( i = 0; i < nth && P != NULL; i++ )
+        {
+                P = P->Next;
+        }
+
+        return P;
+}
+
+void PrintLots( List L, List P )
+{
+        int i;
+        Position Posi;
+
+        for( P = P->Next; P != NULL; P = P->Next )
+        {
+                Posi = FindNth( L, P->Element );
+
+                if (Posi != NULL)
+                {
+                        printf("%d ", Posi->Element);
+                }
+        }
+
+        printf("\n");
+}
+
+int main()
+{
+        List L, P;
+        L = malloc( sizeof( struct Node ) );
+        P = malloc( sizeof( struct Node ) );
+
+        Insert(6, P, P);
+        Insert(4, P, P);
+        Insert(3, P, P);
+        Insert(1, P, P);
+
+        Insert(8, L, L);
+        Insert(7, L, L);
+        Insert(6, L, L);
+        Insert(5, L, L);
+        Insert(4, L, L);
+        Insert(3, L, L);
+        Insert(2, L, L);
+        Insert(1, L, L);
+
+        PrintList( P );
+        PrintList( L );
+
+        PrintLots( L, P );
+
+        return 0;
+}
diff --git a/DSAA/chap3_lists_stacks_queues/ex_3.c b/DSAA/chap3_lists_stacks_queues/ex_3.c
new file mode 100644
index 0000000..6981ce9
--- /dev/null
+++ b/DSAA/chap3_lists_stacks_queues/ex_3.c
@@ -0,0 +1,45 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+void SwapSinglyAdjacentNode( Position FrontP, Position BackP , List L)
+{
+        Position TmpCell;
+
+        TmpCell = FindPrevious( FrontP->Element, L );
+        TmpCell->Next = BackP;
+
+        TmpCell = FrontP;
+        FrontP->Next = BackP->Next;
+        BackP->Next = TmpCell;
+}
+
+void SwapDoublyAdjacnetNode( Position P1, Position P2 )
+{
+
+}
+
+int main()
+{
+        List L;
+        Position Front, Back;
+
+        L = malloc( sizeof( struct Node ) );
+
+        Insert(1, L, L);
+        Insert(2, L, L);
+        Insert(3, L, L);
+        Insert(4, L, L);
+
+        PrintList( L );
+
+        Front = Find(3, L);
+        Back = Find(2, L);
+
+        SwapSinglyAdjacentNode(Front, Back, L);
+
+        PrintList( L );
+
+        return 0;
+}
diff --git a/DSAA/chap3_lists_stacks_queues/ex_4&5.c b/DSAA/chap3_lists_stacks_queues/ex_4&5.c
new file mode 100644
index 0000000..40f2802
--- /dev/null
+++ b/DSAA/chap3_lists_stacks_queues/ex_4&5.c
@@ -0,0 +1,136 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+void Intersection( List L1, List L2, List InterList )
+{
+        Position P, TmpCell;
+
+        TmpCell = InterList;
+
+        for( L1 = L1->Next; L1 != NULL; L1 = L1->Next )
+        {
+                P = Find( L1->Element, L2 );
+                if( P )
+                {
+                        TmpCell = Insert( P->Element, InterList, TmpCell);
+                }
+        }
+}
+
+/* This solution is dirty, needed to be modify */
+void Union( List L1, List L2, List UniList )
+{
+        Position P, TmpCell;
+        Position P1, P2;
+
+        TmpCell = UniList;
+        P1 = L1->Next;
+        P2 = L2->Next;
+
+        while( P1 && P2 )
+        {
+                if ( P1->Element == P2->Element )
+                {
+                        TmpCell = Insert( P1->Element, UniList, TmpCell );
+                        P1 = P1->Next;
+                        P2 = P2->Next;
+                }
+
+                while( P2 && P1->Element > P2->Element )
+                {
+                        TmpCell = Insert( P2->Element, UniList, TmpCell );
+                        P2 = P2->Next;
+                }
+
+                while( P1 && P1->Element < P2->Element )
+                {
+                        TmpCell = Insert( P1->Element, UniList, TmpCell );
+                        P1 = P1->Next;
+                }
+        }
+
+        while( P1 )
+        {
+                TmpCell = Insert( P1->Element, UniList, TmpCell );
+                P1 = P1->Next;
+        }
+
+         while( P2 )
+         {
+                 TmpCell = Insert( P2->Element, UniList, TmpCell );
+                 P2 = P2->Next;
+         }
+}
+
+void
+UnionSectionVersion( List L1, List L2, List UniList )
+{
+         Position P, TmpCell;
+
+         TmpCell = UniList;
+
+         L1 = L1->Next;
+         L2 = L2->Next;
+
+         while( L1 || L2 )
+         {
+                if( !L1 )
+                {
+                        TmpCell = Insert( L2->Element, UniList, TmpCell );
+                        L2 = L2->Next;
+                        continue;
+                }
+                if( !L2 )
+                {
+                        TmpCell = Insert( L1->Element, UniList, TmpCell );
+                        L1 = L1->Next;
+                        continue;
+                }
+                if( L1->Element == L2->Element )
+                {
+                        TmpCell = Insert( L1->Element, UniList, TmpCell );
+                        L1 = L1->Next;
+                        L2 = L2->Next;
+                        continue;
+                }
+                if( L1->Element < L2->Element )
+                {
+                        TmpCell = Insert( L1->Element, UniList, TmpCell );
+                        L1 = L1->Next;
+                        continue;
+                }
+                if( L1->Element > L2->Element)
+                {
+                        TmpCell = Insert( L2->Element, UniList, TmpCell );
+                        L2 = L2->Next;
+                        continue;
+                }
+         }
+
+}
+
+int main()
+{
+        int Arr1[10] = {7, 6, 5, 4, 3, 2, 1};
+        int Arr2[10] = {10, 8, 6, 4, 2};
+        List L1, L2, InterList, UniList;
+
+        L1 = malloc( sizeof( struct Node ) );
+        L2 = malloc( sizeof( struct Node ) );
+        InterList = malloc( sizeof( struct Node ) );
+        UniList = malloc( sizeof( struct Node ) );
+
+        ConstructList( L1, Arr1, 7 );
+        ConstructList( L2, Arr2, 5 );
+
+        Intersection( L1, L2, InterList );
+        UnionSectionVersion( L1, L2, UniList );
+        PrintList( L1 );
+        PrintList( L2 );
+        PrintList( InterList );
+        PrintList( UniList );
+
+        return 0;
+}
diff --git a/DSAA/chap3_lists_stacks_queues/ex_6.c b/DSAA/chap3_lists_stacks_queues/ex_6.c
new file mode 100644
index 0000000..2a8f565
--- /dev/null
+++ b/DSAA/chap3_lists_stacks_queues/ex_6.c
@@ -0,0 +1,6 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+
diff --git a/DSAA/chap3_lists_stacks_queues/list.c b/DSAA/chap3_lists_stacks_queues/list.c
new file mode 100644
index 0000000..23848bc
--- /dev/null
+++ b/DSAA/chap3_lists_stacks_queues/list.c
@@ -0,0 +1,145 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+/* Return true if L is empty */
+
+int
+IsEmpty( List L )
+{
+        return L->Next == NULL;
+}
+
+/* Return true if P is the last position in list L.
+ * Parameter L is unused in this implementation */
+
+int
+IsLast( Position P, List L )
+{
+        return P->Next == NULL;
+}
+
+/* Return Position of X in L; Null if not found */
+
+Position
+Find( ElementType X, List L )
+{
+        Position P;
+
+        P = L->Next;
+        while( P != NULL && P->Element != X )
+                P = P->Next;
+
+        return P;
+}
+
+/* Delete first occurrence of X from a list.
+ * Assume use of a header node */
+
+void Delete( ElementType X, List L )
+{
+        Position P, TmpCell;
+
+        P = FindPrevious(X, L);
+
+        if ( !IsLast(P, L) )
+        {
+                TmpCell = P->Next;
+                P->Next = TmpCell->Next;
+                free( TmpCell );
+        }
+}
+
+/* If X is not found, then Next field of returned.
+ * Position is NULL.
+ * Assumes a header */
+
+Position
+FindPrevious( ElementType X, List L )
+{
+        Position P;
+
+        P = L;
+        while( P->Next != NULL && P->Next->Element != X )
+        {
+                P = P->Next;
+        }
+
+        return P;
+}
+
+/* Insert (after legal position P).
+ * Header implementation assumed.
+ * Parameter L is unused in this implementation.
+ * Return the position of the inserted node */
+
+Position
+Insert( ElementType X, List L, Position P )
+{
+        Position TmpCell;
+
+        TmpCell = malloc( sizeof( struct Node ) );
+        if( TmpCell == NULL )
+                printf( "Out of space!" );
+
+        TmpCell->Element = X;
+        TmpCell->Next = P->Next;
+        P->Next = TmpCell;
+
+        return TmpCell;
+}
+
+void
+DeleteList( List L )
+{
+        Position P, Tmp;
+
+        P = L->Next;
+        L->Next = NULL;
+
+        while( P != NULL )
+        {
+                Tmp = P->Next;
+                free( P );
+                P = Tmp;
+        }
+}
+
+void ConstructList( List L, int Elements[], int Num )
+{
+        int i;
+
+        for( i = 0; i < Num; i++ )
+        {
+                Insert(Elements[i], L, L);
+        }
+}
+void
+PrintList( List L )
+{
+        Position P;
+        P = L->Next;
+
+        while( P != NULL )
+        {
+                printf( "%d->", P->Element );
+                P = P->Next;
+        }
+
+        printf( "\n" );
+}
+
+/*int*/
+/*main()*/
+/*{*/
+        /*Position P;*/
+        /*List L;*/
+
+        /*L = malloc( sizeof (struct Node) );*/
+        /*Insert(3,L, L);*/
+        /*Insert(5,L, L);*/
+        /*Insert(8, L, L);*/
+        /*P = FindPrevious(3, L);*/
+        /*PrintList(L);*/
+/*}*/
diff --git a/DSAA/chap3_lists_stacks_queues/list.h b/DSAA/chap3_lists_stacks_queues/list.h
new file mode 100644
index 0000000..04ad7df
--- /dev/null
+++ b/DSAA/chap3_lists_stacks_queues/list.h
@@ -0,0 +1,33 @@
+#ifndef _LIST_H
+#define _LIST_H
+
+struct Node;
+typedef int ElementType;
+typedef struct Node *PtrToNode;
+typedef PtrToNode List;
+typedef PtrToNode Position;
+
+List MakeEmpty( List L );
+int IsEmpty( List L );
+int IsLast( Position P, List L );
+Position Find( ElementType X, List L );
+void Delete( ElementType X, List L );
+Position FindPrevious( ElementType X, List L );
+Position Insert( ElementType X, List L, Position P );
+void DeleteList( List L );
+Position Header( List L );
+Position First( List L );
+Position Advance( Position P );
+ElementType Retrieve( Position P );
+void PrintList( List L );
+void ConstructList( List L, int Elements[], int Num );
+
+#endif  /* _LIST_H */
+
+
+/* Place in the implementation file ? */
+struct Node
+{
+        ElementType Element;
+        Position Next;
+};
diff --git a/DSAA/chap3_lists_stacks_queues/polynomial_ADT.c b/DSAA/chap3_lists_stacks_queues/polynomial_ADT.c
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/DSAA/chap3_lists_stacks_queues/polynomial_ADT.c
diff --git a/DSAA/chap3_lists_stacks_queues/polynomial_ADT.h b/DSAA/chap3_lists_stacks_queues/polynomial_ADT.h
new file mode 100644
index 0000000..f46b040
--- /dev/null
+++ b/DSAA/chap3_lists_stacks_queues/polynomial_ADT.h
@@ -0,0 +1,22 @@
+#ifndef _POLYNOMIAL_H
+#define _POLYNOMIAL_H
+
+typedef struct Node *PtrToNode;
+typedef PtrToNode Polynomial; /* Node sorted by exponent */
+
+void ZeroPolynomial( Polynomial Poly );
+void AddPolynomial( const Polynomial Poly1,
+                const Polynomial Poly2,
+                Polynomial PolySum );
+void MultPolynomial( const Polynomial Poly1,
+                const Polynomial Poly2,
+                Polynomial PolyProd );
+
+
+struct Node
+{
+        int Coefficient;
+        int Exponent;
+        PtrToNode Next;
+};
+