aboutsummaryrefslogtreecommitdiff
path: root/DSAA
diff options
context:
space:
mode:
Diffstat (limited to 'DSAA')
-rw-r--r--DSAA/chap3_lists_stacks_queues/ex_2.c64
-rw-r--r--DSAA/chap3_lists_stacks_queues/ex_3.c45
-rw-r--r--DSAA/chap3_lists_stacks_queues/ex_4&5.c136
-rw-r--r--DSAA/chap3_lists_stacks_queues/ex_6.c6
-rw-r--r--DSAA/chap3_lists_stacks_queues/list.c145
-rw-r--r--DSAA/chap3_lists_stacks_queues/list.h33
-rw-r--r--DSAA/chap3_lists_stacks_queues/polynomial_ADT.c0
-rw-r--r--DSAA/chap3_lists_stacks_queues/polynomial_ADT.h22
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;
+};
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-20 20:04:30 +0000