Examples of Z Algorithms

1. Simple Linked List

2. Linked List of Strings

3. Linked List of Linked Lists

4. Linked List of Stacks

5. Doubly Linked List

Simple Linked List

/*  Creates a linked list from N data, displays it and searches for a given value */

   LET

         L : LIST ;

         Tete , P , Q : POINTER TO LIST ;

         V , I , N : INTEGER ;

         Trouv : BOOLEAN ;

   BEGIN

         READ ( N ) ;

         P := NULL ;

         FOR I := 1 , N

               ALLOCATE_CELL ( Q ) ;

               READ ( V ) ;

               ASS_VAL ( Q , V ) ;

               ASS_ADR ( Q , NULL ) ;

               IF P ^= NULL

                     ASS_ADR ( P , Q ) ;

               ELSE

                     Tete := Q

               ENDIF ;

               P := Q

         EFOR ;

         WRITE ( 'List traversal ' ) ;

         P := Tete ;

         WHILE P <> NULL :

               WRITE ( CELL_VALUE ( P ) ) ;

               P := NEXT ( P )

         EWH ;

         WRITE ( 'Search for an element ' ) ;

         READ ( V ) ;

         Trouv := FALSE ;

         P := Tete ;

         WH NOT Trouv AND ( P # NULL )

               IF CELL_VALUE ( P ) = V

                     Trouv := TRUE

               ELSE

                     P := NEXT ( P )

               ENDIF

         ENDWHILE ;

         WRITE ( Trouv )

   END

Linked List of Strings

/*  Creates a linked list of strings using a high level operation, displays it and searches for a given value */

   LET

       L : LIST OF STRINGS ;

       P , Q : POINTER TO LIST OF STRINGS ;

       I : INTEGER ;

       V : STRING ;

       Trouv : BOOLEAN ;

   BEGIN

       I := 8 ;

       CREATE_LIST ( L , [ 'a' , 'ab' , 'ac' , 'ad' ] ) ;

       WRITE ( 'List Traversal ' ) ;

       P := L ;

       WHILE P <> NULL :

           WRITE ( CELL_VALUE ( P ) ) ;

           P := NEXT ( P )

       ENDWHILE ;

       WRITE ( 'Search for an element' ) ;

       READ ( V ) ;

       Trouv := FALSE ;

       P := L ;

       WHILE NOT Trouv AND ( P # NULL )

           IF CELL_VALUE ( P ) = V

               Trouv := TRUE

           ELSE

               P := NEXT ( P )

           ENDIF

       ENDWHILE ;

       WRITE ( Trouv )

   END

Linked List of Linked Lists

/*  Creates a linked list of two linked lists using a high level operation, and displays it */

   LET

       L1 , L2 : LISTS ;

       Ll : LIST OF LIST ;

   BEGIN

       CREATE_LIST ( L1 , [ 2 , 4 , 67 , 778 ] ) ;

       CREATE_LIST ( L2 , [ 12 , 14 , 167 , 1778 ] ) ;

       CREATE_LIST ( Ll , [ L1 , L2 ] ) ;

       WRITE ( 'Here, the results' ) ;

       WH Ll <> NULL :

           L1 := CELL_VALUE ( Ll ) ;

           WH L1 <> NULL :

               WRITE ( CELL_VALUE ( L1 ) ) ;

               L1 := NEXT ( L1 )

           EWH ;

           Ll := NEXT ( Ll )

       EWH

   END

Linked List of Stacks

/*  Create a linked list of stacks, and traverses it */

   LET

       L : LIST OF STACK ;

       P , Q : POINTER TO LIST OF STACK ;

       Pil : STACK ;

       V , I , N : INTEGER ;

       Trouv : BOOLEAN ;

   BEGIN

       READ ( N ) ;

       P := NULL ;

       FOR I := 1 , N :

           ALLOCATE_CELL ( Q ) ;

           CREATE_STACK ( Pil , [ 2 * I , 3 * I , 4 * I ] ) ;

           ASS_VAL ( Q , Pil ) ;

           ASS_ADR ( Q , NULL ) ;

           IF P ^= NULL

               ASS_ADR ( P , Q ) ;

           ELSE

               L := Q

           ENDIF ;

           P := Q

       EFOR ;

       WRITE ( 'Traversing Stacks ' ) ;

       P := L ;

       I := 0 ;

       WHILE P <> NULL :

           I := I + 1 ;

           WRITE ( ' Stack N ° ' , I ) ;

           Pil := CELL_VALUE ( P ) ;

           WHILE NOT EMPTY_STACK ( Pil ) :

               POP ( Pil , V ) ;

               WRITE ( V ) ;

           ENDWHILE ;

           P := NEXT ( P )

       ENDWHILE

   END

Doubly Linked List

/*  Creates a doubly linked using a high level operation, deletes a given data, and displays the list */

   LET

               L : BILIST ;

               P , Q : POINTER TO BILIST ;

               I , V : INTEGER ;

               Trouv : BOOLEAN ;

   BEGIN

               CREATE_BILIST ( L , [ 56 , 88 , 997 , 4453 , 554 ] ) ;

               WRITE ( 'Bidirectional list traversal' ) ;

               P := L ;

               WH P <> NULL :

                           WRITE ( CELL_VALUE ( P ) ) ;

                           P := NEXT ( P )

               EWH ;

               WRITE ( ' Deleting an element ' ) ;

               READ ( V ) ;

               Trouv := FALSE ;

               P := L ;

               WHILE NOT Trouv AND ( P # NULL )

                           IF CELL_VALUE ( P ) = V

                                       Trouv := TRUE

                           ELSE

                                       P := NEXT ( P )

                           ENDIF

               ENDWHILE ;

               IF NOT Trouv :

                           WRITE ( ' Element not found  ' )

               ELSE

                           IF PREVIOUS ( P ) # NULL :

                                       ASS_R_ADR ( PREVIOUS ( P ) , NEXT ( P ) )

                           ELSE

                                       L := NEXT ( P )

                           ENDIF ;

                           IF NEXT ( P ) # NULL

                                       ASS_L_ADR ( NEXT ( P ) , PREVIOUS ( P ) )

                           ENDIF ;

                           FREE ( P )

               ENDIF ;

               WRITE ( 'Traversing the list' ) ;

               P := L ;

               WHILE P <> NULL :

                           WRITE ( CELL_VALUE ( P ) ) ;

                           P := NEXT ( P )

               ENDWHILE ;

   END