(only in breaf - as a support for training)

Using the "array" for basic structures

The one-dimensional matrix (in computer science, a vector) can be declared as:

a : array[1..100] of integer;

We use the index for selecting element of this structure. There is typical to use the for - do cycle.

When the number of elements is not a constant, we can:

Often, the combination of this method is used.

Array as a buffer

If there are temporally more demands that we can solve, we can keep the data in some kind of buffer. This can be the queue (first in, first out, FIFO) or a stack (last in, first out, LIFO), while queue in computer is organised as circular.

The queue on the office, airport or for a doctor before half century works the way, that if one person had been served and leaved, the rest of them made step or two to move (now, we have machine to get a numbered bill for each person, allowing them to sit, or even visit a refreshments). When programming this, it is easier to move the service hatch, then all the data. Another problem is, that in the computer world, we cannot distinguish, if in the memory cell is an number (there is always some number, but we cannot decide, if it is valid). So we need another pointer to keep information, which number is the last. So, to create queue (FIFO), we have to prepare two pointers:

  1. Pointer to element to be served, the begin of the queue
  2. Pointer to end of the queue. When you try to solve the queue, you will prove, that the simpler solution is not to point to the last element in the queue, but to the next position, which is empty. Then the equality of both pointers stands for an empty queue.

By using queue, we run out of the array after while. The typical solution of this problem is to move the pointer back to start; it makes this to be

Circular queue

... or, often, circular buffer. In this case, it is possible, that the end pointer comes to position of the start pointer; in this case, we have to refuse to add a new element, because the queue is full. Typical picture of circular buffer is circle; don't forget, that in the memory, this is still linear. The next position can be count as

  i := (i+1) div n;

, if n is number of elements in the array, and the array is indexed from zero. For example, for a queue defined as

  queue : array[0..10] of integer;
  begp, endp : integer;

, it means with eleven elements, we can move pointer by

  endp := (endp+1) mod 11;

More common is to test the full queue first:

  if ((endp+1) mod 11) <> begp
    then 
      begin
        queue[endp] := StrToInt(Edit1.Text);
        endp := (endp+1) mod 11;
      end
    else showmessage('The queue is full!');

Task: create a queue and a procedure for a list of its content in a memo; prepare both functions (on buttons), with a list of current content after each queue use. Assure, that in the array, declared with eleven elements, you can use maximally ten for a queue.

Stack

is even simpler, there are only the stack's top. In the case of the stack, the elemet, which has been added as the last, is servicer as the first (last in, first out, LIFO). Again, if the pointer points to the first empty position, the functions will be simpler.

If we declare the array as in the previous example, then the zero value of the (only) stack pointer stands for empty stack (and no element can be read - we have to refuse any attempt for read). The value of the number of element means, that we have to refuse to add a value (the stack is full). In the stack of 11 position, there can be 11 values saved - from this point of view, slack is less memory consumpting (no empty position, only one pointer).

The stack is important in the machine code (assembler); the CPU contains register called "stack pointer", and the stack is declared immediately after computer starts. In this case, the stack is upside-down; starts on the end of the memory and the address is decremented while saving a value to the stack (there is a special instruction for this, "push").


The last static construction: array and array-of-pointers

We can use the array to save database-type information; we can do it, if each element of the array is the record type. The advantage of this solution against use the prepared database elements is that we don't need to install any database drivers with our application; this solution is better if we have only one table in or "database" (so, no relation between tables). We can declare an array for one hundered of employees like this:

type
  os = record
    name : string[30];
    lastname : string[39];
    addr_street : string[59];
    addr_city : string[59];
    zipcode : string[6];
    phone : string[15];
  end;

var
  people : array[0..99] of os;

To make manipulation with this data simpler (for example, sorting, add new in correct position, dropping a value), we can create only pointer for each person, and ask for a memory for the record in the dynamic area, when used; when sorting or moving (to an empty position, for example), we can just change position of pointers:

type
  uos = ^os;    {exception - we can use the name of the next structure, the "os", before its declaration,
                  because we know the variable size; for the dynamic structures, this would be only possibility}
  os = record
    name : string[30];
    lastname : string[39];
    addr_street : string[59];
    addr_city : string[59];
    zipcode : string[6];
    phone : string[15];
  end;

var
  people : array[0..99] of uos;

This method of memory save and making program faster is described on a special page.

Please, try this at home; today, we have continue with the next chapter:

Linear dynamic data structures

Dynamic data structures create background to database engines and represend important part of the algoriths theory.

Main feature is, that each element can contain a pointer to an another element. Using this, elements can contain structures; if there can be only one pointer, the rusulting "structure" is linear, so called linked list (today's theme).

If the most elements of the structure is accessible only trough an another element, then we can speak about dynamic data structure; if all the pointers are in arrays, declared in the standard (static) memory, as in the previous example, then the structure is not dynamic, even if all the data are allocated in the dynamic memory and they create stack or queue, or even contains pointers to each other.

In the Pascal, we can use an alternative declaration of the type, so theoretically, the last elements don't need to contain any pointer - but this will be very uncommon; w have special value for a pointer, the nil, which means, that pointer does not contain a value (in the PC implementation, the nil is reprezented as zero value, but we have to use the nil variable, while comparing a pointer value, to keep program working correctly.

To explain the structure, we often use the graphics representation; the pointer is represented as an arrow from the element to another (or as a big dot, if contains the nil value). The static memory (variables, declared in the var chapter) is represented as being under or above line, which splits the static and dynamic memory; in the next text, hatched part represents the fixed memory (in mechanical engineering, this symbol is used for fixed support):

Pictures are from the Czech version, so small dictionary for the each of them: "zac" means "beg"(in), "dalsi" is "the next" (part of structure, pointer with a value), the names are common names for dogs (Alik, Bart and Doly).

Beginning of the list (where is the Alik) is called head and the last element in the list is so called tail. The situation can be simpler, if there is pointer to the last element, or (even better?) if there is link in each of element to the previous element as well. This variant of a list is so called double-linked-list or bidirectional list (one of this is correct).

For the next (school) example, the element contains only one string, called the "name", and pointer to the next element, "dalsi". "u" (uos) is from the Czech "ukazatel", means pointer (you can use any name for a variable or type, except keywords; if you use the name of existing variable or procedure, you redeclare this (the original one become unaccessible):

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    Button2: TButton;
    Edit1: TEdit;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

  uos = ^tos;
  tos = record
    text : string[55];
    dalsi : uos;
  end;

var
  Form1: TForm1;
  p : uos;
const
  zac : uos = nil;

implementation

Adding of element to end of the list

Solution: Find the last element (containing the nil), create new element, using pointer in the last existing element structure, move to newly created element and fill it with new data (nil as a new value of its pointer).

For new element creation, the new procedure should be used for records; if the list contents objects, the create procedure should be used.

The Pascal realization:

procedure TForm1.Button1Click(Sender: TObject);
  var
    p : uos;
  begin
    p:=zac;
    if p=nil then
      begin
        new(zac);
        p:=zac;
      end
    else
      begin
        while p^.dalsi<>nil do p:=p^.dalsi;
        new(p^.dalsi);
        p:=p^.dalsi;
      end;
    p^.dalsi := nil;
    p^.text := Edit1.Text;
  end;

Example of source code is here.

It would be even simpler to add each new element to the beginning of the list - we do not need to check, if the list is empty (means no element yet), we can just create new element and copy the current content of zac to its pointer dalsi. Then we copy the new element address to the zac:

procedure TForm1.Button3Click(Sender: TObject);
  var
    p : uos;
  begin
    p:=zac;
    new(zac);
    zac^.dalsi := p;
    zac^.text := Edit1.Text;
  end;

Comment to this example: when tried, the Button2 executed output of the list to a memo component (important to debug). So the previous has been executed by the Button3.

The Button2 listing follows:

procedure TForm1.Button2Click(Sender: TObject);
  var
    p : uos;
  begin
    p:=zac;
    Memo1.Lines.Clear;
    while p<>nil do begin
        Memo1.Lines.Add(p^.text);
        p:=p^.dalsi;
      end;
  end;

To use linked list as a stack (LIFO) or a queue (FIFO), we need to take out the first element from the list. The element shoud be proceeded, we will represent this by the ShowMessage procedure calling. The released memory will be returned to heap by calling the dispose (for records; for objects, the done method of the object should be called):

procedure TForm1.Button4Click(Sender: TObject);
  var
    p : uos;
  begin
    if zac=nil then ShowMessage('The list is empty')
      else
        begin
          p:=zac^.dalsi;
          ShowMessage('Erased element with the text: '+zac^.text);
          dispose(zac);
          zac:=p;
        end;
  end;

In many cases, we need to keep the list sorted.

To add and erase of any element, we need to find it first. The next procedure is only trying to look for n element:

procedure TForm1.Button5Click(Sender: TObject);
  var
    p : uos;
  begin
    p:=zac;
    while (p<>nil) and (p^.text<>Edit1.Text) do p:=p^.dalsi;
    if p^.text<>Edit1.Text then ShowMessage('Cannot be found.')
                           else ShowMessage('Found.'); {or we can for example change the value}
  end;

To insert an element to sorted list, we follow the list tha same way, except we check a condition (sorting condition) after reach each of elements.

The next picture shows, how we imagine of adding next dog named 'Ben' to linked list, started with pointer zac and containing a dalsi to point the next:

This look nice, but we need to check the next element before jump to this, because we would to change the dalsi value in the previous record. It could be even easy, if we solve only problem, that the inserted element will not be either first or the last one:

procedure TForm1.Button6Click(Sender: TObject);
  var
    p, q : uos;
  begin
    p:=zac;
    q:=p^.dalsi;
    while (p<>nil) and (q<>nil) and (q^.text<Edit1.Text) do
      begin
        p:=q;
        q:=p^.dalsi;
      end;
    if q^.text>Edit1.Text then
        begin
          new(q);
          q^.text:=Edit1.Text;
          q^.dalsi:=p^.dalsi;
          p^.dalsi:=q;
        end;
  end;

When we try, that this works, we have to serve the other possibilities - adding the first or the last element:

procedure TForm1.Button6Click(Sender: TObject);
  var
    p, q : uos;
  begin
    if zac=nil then begin    {the empty list has to be solved separately}
      new(zac);
      zac^.dalsi := nil;
      zac^.text := Edit1.Text;
      exit; {the exit command leaves the procedure, because we are done}
    end;
    p:=zac;
    if p^.text>Edit1.Text then    {the case that new element will be the first one}
        begin
          new(zac);
          zac^.text:=Edit1.Text;
          zac^.dalsi:=p;
          exit; {done - leaving the procedure}
        end

    q:=p^.dalsi;
    while (p<>nil) and (q<>nil) and (q^.text<Edit1.Text) do
      begin
        p:=q;
        q:=p^.dalsi;
      end;
    if q^.text>Edit1.Text then
        begin
          new(q);
          q^.text:=Edit1.Text;
          q^.dalsi:=p^.dalsi;
          p^.dalsi:=q;
        end
      else  {no element is bigger - add the new one as the last}
        begin
          new(p^.dalsi);
          q^.text:=Edit1.Text;
          q^.dalsi:=nil;
        end;
  end;

This program has not been tested. This is too complicated, and there are two simpler solution.

As the first, "go tricky": When use only one pointer, we cannot change the previous dalsi (pointer, pointing to next). We discover, that we have found the position for the "Ben", when we come to "Dolly". The new element should point to Dolly; Solution is on the nex picture. We create new element (using a "q" pointer), but we dont to write "Ben" here, but copy there everything from the actual element ("Doly"), including the dalsi (next) pointer value. Then we have empty element (released from "Doly"), where we can write new value ("Ben"). Now set its pointer to the new one with "Doly" (q) and we are done (purple - new position in memory, red - new element):

This is part of one of the state exam question - if you got this, you should draw the picture and explain, not to write the next program:

procedure TForm1.Button6Click(Sender: TObject);
  var
    p, q : uos;
  begin
    if zac=nil then begin    {empty list solved separately}
      new(zac);
      zac^.dalsi := nil;
      zac^.text := Edit1.Text;
      exit; {in the case of empty list, exit the procedure}
    end;
    p:=zac;
    while (p^.dalsi<>nil) and (p^.text<Edit1.Text) do p:=p^.dalsi;
    if p^.text>Edit1.Text then
        begin
          new(q);
          q^.text:=p^.text;
          q^.dalsi:=p^.dalsi;
          p^.dalsi:=q;
          p^.text:=Edit1.Text;
        end
      else  {adding to the end, of there are no bigger element}
        begin
          new(p^.dalsi);
          p:=p^.dalsi;
          p^.text:=Edit1.Text;
          p^.dalsi:=nil;
        end;
  end;

The same situation for deleting an element from the list:

Again, when we found the element, it's to late to erase it. The red is, what we should delete. When we found the "Bart", we have to copy the Doly to this element (including the dalsi, the next pointer) to actual element, and release the element originally containing 'Doly'. Before copy, do not forget to keep the original dalsi (next) pointer, because it will be replaced by the new value (so we lost the pointer to the element to be deleted).

You can create this procedure yourself. Do not forget an empty list and the last element case.


The second solution - recursive.

When declare a procedure, formal parameters in the heading can look like:

procedure abc(i:byte;s:string);

Realization: compiler create a position for this two variables on the CPU stack, in the same place, as if you use local variables in your procedure. This is done when procedure is called; then the initial value of this (in a fact, local variables) is set to value from procedure calling; then the return address is added (to the next place) and program jumps to the procedure code. In this case, the i variable (byte) will use 4 bytes of memory (one stack position), while the s variable (string) will use much more memory - we should write something like "string[50]" to save memory and time. This is so called calling-by-value.

procedure abc(var i:byte; var s:string);

When use the var keyword, only the pointer to the real parameter will be passed to the procedure. Disadvantage is, that we cannot write an expression in position of formal parameter. Feature is, that we work with the original variable, so we can change its value. Advantage is, that this is fast. This is so called calling-by-reference.

In the both cases, the local variable and passed parameters (for example, addresses) are erased from the CPU stack by the special version of the return function, with the parameter, how much the CPU stack pointer should be moved (up, in the CPU, stack is upside-down).

Recursive solution is, that the procedure will call itself; the next calling should solve simpler problem to create finite algorithm.

By use recursive calling and the call-by-reference parameter, we can change the "pointer-to-the-position-where-we-are", because not the value, but the pointer itself is passed to the actual procedure. The disadvantage of the recursive solution is, that each procedure call cost us:

Memory is not problem in modern computers. You can save memory by the use of global variables while calling recursive, whenever it is possible (the q can be).

procedure addnew(var p: uos);
  var
    q : uos;   {... global variable can be used}
  begin
    if p=nil then
      begin    {end of the list - special case}
        new(p);      {the new position in the correct place - the biggest advantage}
        p^.dalsi := nil;
        p^.text := Form1.Edit1.Text;   {outside Form1 structure, we have to write complete name}
      end
    else
      if p^.text<Form1.Edit1.Text
        then addnew(p^.dalsi)    {<--- this is the recursive calling}
        else
          begin
            q:=p;
            new(p);    {the new position in the correct place - the biggest advantage}
            p^.dalsi:=q;
            p^.text:=Form1.Edit1.Text;
          end;
  end;

This procedure has to be called from some element of the Form, for example form a button (button itself cannot be recursive), with the pointer to start of the list / the zac variable:

procedure TForm1.Button7Click(Sender: TObject);
  begin
    addnew(zac);
  end;

Try to write the recursive solution of an element remove.