Z Language  ( Data structures)                     Back to Summary

 

Structures

Arrays

Linked lists

Bidrectional linked lists

Queues

Piles

Binary search trees

M-ary search trees

Files

 

 

Structures      

 

A structure is a set of heterogeneous elements. An element of a structure can be a scalar or a one-dimensional array of scalars.

a structure can be complexe, i.e, consisting of scalars and/or one dimensional array of scalars.

Structures can be static or dynamic.

 

Structure declaration:

 

  LET <Li>  :  [STRUCTURE] ( Type1, type2, ... ) [DYNAMIC

 

<Li> : identifier list separated by coma.

Typei is either a scalar type or a one-dimensional array of scalars.

 

Examples

 

    S1 : (INTEGER, STRING) ;

    S2 : STRUCTURE ( CHAR, INTEGER, BOOLEAN) ;

    S3 : ( INTEGER, ARRAY(5) OF  STRING) DYNAMIC;

 

Arrays

 

An array is a set of  heteregenous elements.

An array can be simple, i.e, consisting only of scalars.

An array can be complexe, i.e, consisting of simple structures.

An array can be static or dynamic.

 

Array declaration:

 

  LET  <Li> :  ARRAY (Dim1, Dim2, ... )  OF Typec OF Typec OF  ....  OF Types  [DYNAMIC]

 

<Li> : identifier list separated by coma.

Typec dans { ARRAY, STACK, list, QUEUE, BST, BIlist, MST }

Types is a scalar or a simple type.

 

Examples

 

    V1 : ARRAY (5) DYNAMIC;

    V2, V3 : ARRAYS (3, 8) OF STRINGS ;

Linked lists

 

A linked linear list is a set of chains that are dynamically allocated (i.e. during the execution of a program) and linked together. A chain generally contains two fields: information and an address. It is the user who creates the list, who modifies it by adding or deleting chains, who browses it in order to perform a given treatment.

Champ 'Value' can be of any type.

 

Linked list declaration:

 

  LET <Li> : LISTE  [ OF Typec OF Typec OF  .... ] [ OF Types ]

 

<Li> : identifier list separated by coma.

Typec dans { ARRAY, STACK, list, QUEUE, BST, BIlist, MST }

Types is a scalar or a simple type.

 

Examples

 

    L : LIST OF (STRING, INTEGER);

    L : LIST OF STACKS OF STRINGS ;

    L : LIST OF STRINGS;

Bidirectional linked lists

 

A bilateral list is a linked linear list that can be traversed in both directions.

An element has three fields: value, left address and right address.

 

Champ 'Value' can be of any type.

 

Bidirectional linked list declaration:

 

LET <Li> :  LISTEBI  [OF Typec OF Typec OF  .... ][ OF Types]

 

<Li> : identifier list separated by coma.

Typec dans  { ARRAY, STACK, list, QUEUE, BST, BIlist, MST }

Types is a scalar or a simple type.

 

Examples

 

    Lb1 : BILIST OF (STRING, INTEGER);

    Lb2 : BILIST OF STACKS OF STRINGS ;

    Lb3 : BILIST OF STRINGS;

 -

 Queues

 

A queue obeys the 'FIFO' principle: First In First Out. It is a collection of elements such that any new element is inserted at the end and any removal of element is done at the beginning.

An element can be of any type.

 

Queue declaration:

 

 LET <Li> : QUEUE  [OF Typec OF Typec OF  .... ] [OF Types]

 

<Li> : identifier list separated by coma.

Typec dans  { ARRAY, STACK, list, QUEUE, BST, BIlist, MST}

Types is a scalar or a simple type.

 

Examples

 

    F1 : QUEUE OF  (STRING, INTEGER);

    F2 : QUEUE OF STACKS OF STRINGS ;

    F3 : QUEUE OF STRINGS;

Stacks

 

A stack obeys the 'LIFO' principle: Last In First Out. It is a collection of elements such that any new element is inserted at the beginning and any removal of element is done at the beginning.

 

An element can be of any type.

 

 

Stack declaration

 

  LET <Li> : STACK  [OF Typec OF Typec OF  .... ][ OF Types]

 

<Li> : identifier list separated by coma.

Typec dans  { ARRAY, STACK, list, QUEUE, BST, BIlist, MST}

Types is a scalar or a simple type.

 

Examples

 

    P1 ; STACK OF (STRINGS, INTEGER);

    P2 ; STACK OF STACKS OF STRINGS ;

    P3 ; STACK OF STRINGS;

 

Binary  search trees

 

A binary search tree represents a set of data with an order relation.

All data in the left sub-tree of any node with the information x are less than x, all data in the right sub-tree of any node with the information x are greater than x.

 

A node can be of any type.

 

Binary search tree declaration:

 

 LET  <Li> : BST  [OF Typec OF Typec OF  .... ] [OF Types]

 

<Li> : identifier list separated by coma.

Typec in { ARRAY, STACK, list, QUEUE, BST, BIlist, MST }

Types is a scalar or a simple type.

 

 

Examples

 

    A1 : BST OF (STRING, INTEGER);

    A2 : BST OF STACKS OF STRINGS ;

    A3 : BST OF STRINGS;

 

M-ary search trees

  

An m-ary search tree allows to represent a data set with an order relation. It is a generalization of the binary search tree. Instead of having one information and two address fields, we have p addresses and (p-1) information in which case the m-ary search tree is said to have order p. Intuitively, a node has the following form: (a1, v1, a2, v2, ......, vp-1, ap). All the data in the sub-tree of root a1 are less than v1, all the data in the sub-tree of root a2 are greater than v1 and less than v2, etc.

 

A node can be of any type.

 

M-ary search tree declarartion:

 

  LET <Li> : MST (degree) [ OF Typec OF Typec OF  ....] [ OF Types]

 

<Li> : identifier list separated by coma.

Typec in  { ARRAY, STACK, list, QUEUE, BST, BIlist, MST}

Types is a scalar or a simple type.

 

Examples

 

    M1 : MST(4) OF (STRING, INTEGER);

    M2 : MST(2) OF STACKS OF STRINGS ;

    M3 : MST(3) OF STRINGS;

 

Files

 

A file is a set of records (structures) generally stocked in disks.

For a designer, a file is a set of blocks.

The file holds a special block (Header block) for the design of file structures.

.

File declaration

 

  LET File_name :  FILE OF Type [HEADER ( Type1, Type2, .... ) ]  BUFFER <Li>

<Li> : identifier list separated by coma.

 

A file definition consists of 3 parts:

** The first part (FILE) specifies the nature of the elements in the file.

a file record can be :

- a scalar, i.e of a simple type ( INTEGER, BOOLEAN, CHAR, STRING ),

- a one-dimensional array of scalars

- a structure that can contain  scalars or one-dimensional arrays of scalars.

** The second part (HEADER) describes the file features by specifying the type of each feature. This part is mainly used for the creation of user file structures and is used to store all the information useful for the exploitation of the file.
** The third part (
BUFFER)defines the variables ( record or block ) used in reading and writing operations.

 

 

Examples

 

   F1 : FILE OF CHAINES BUFFER V1, V2;

   F2 : FILE OF VECTEUR(5) DE ENTIER BUFFER V ;

   F3  : FILE OF (INTEGER, ARRAY(3) OF CHAR HEADER(INTEGER, INTEGER) BUFFER V ;   

   F4 : FILE OF CHAR  HEADER (INTEGER, STRING, BOOLEAN BUFFER V ;