Entry
BBCBASIC: Data structure: How to create data structures using arrays? [structure]
Jul 16th, 2006 10:11
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 16 July 2021 - 02:14 pm -----------------------
BBCBASIC: Data structure: How to create data structures using arrays?
[structure]
---
One of the simplest methods is to create the common data structures and
their operations using arrays, in which you store the pointers in
columns.
Because arrays are present in almost any computer language you can
easily implement it in the different languages. Your procedures and
functions will be very portable between the different languages
(another method is to peek and poke directly in computer memory, but
this method is thus much more computer language dependent and you work
on a 'lower' level (that is closer and working more direct to the
(memory) hardware), while working with arrays is more working on a
'higher' level (you use commands to indirectly access the same memory).
The advantage of this (mostly used) method is speed)
You could maybe first implement this simpler method, then translate
it to the more involved method using peeks and pokes (using indirection
operators like ?, !, ^, ...)
Usually this arrays contain at least one value column (e.g. containing
a string (e.g. 'John Doe')) and you put your pointer values in 0 or
more pointer columns (which contain some integer number (e.g. '3')
about which row(s) of that array are involved. The other methods put
the pointers directly in memory).
So you dimension the following arrays:
1. stack (that is a table or array with 1 column)
---------------------------
ROWNR | VALUE |
---------------------------
1 John Doe
2 Vanessa Bella
...
---------------------------
To create your arrays you use something like like
If e.g. 100 rows, you dimension this array like
DIM value$( 100 )
Note:
You could more nicely group these arrays together in a 'structure'
DIM myStack{(100) value$ }
myStack{(1)}.value$ = "John Doe"
myStack{(2)}.value$ = "Vanessa Bella"
END
2. queue (that is a table or array with 1 column)
---------------------------
ROWNR | VALUE |
---------------------------
1 John Doe
2 Vanessa Bella
...
---------------------------
To create your arrays you use something like like
If e.g. 100 rows, you dimension this array like
DIM value$( 100 )
Note:
You could more nicely group these arrays together in a 'structure'
DIM myQueue{(100) value$ }
myQueue{(1)}.value$ = "John Doe"
myQueue{(2)}.value$ = "Vanessa Bella"
END
3. linked lists (that is a table or array with 2 colums: a value and a
next pointer column)
---------------------------------------
ROWNR | VALUE | POINTER |
---------------------------------------
1 John Doe 2
2 Vanessa Bella 3
...
---------------------------------------
To create your arrays you use something like like
If e.g. 100 rows, you dimension this array like
DIM value$( 100 )
DIM pointerI%( 100 )
Note:
You could more nicely group these arrays together in a 'structure'
DIM mylinkedList{(100) value$, pointerI% }
mylinkedList{(1)}.value$ = "John Doe"
mylinkedList{(1)}.pointerI% = 2
mylinkedList{(2)}.value$ = "Vanessa Bella"
mylinkedList{(2)}.pointerI% = 3
END
4. double linked list (that is a table or array with 3 columns: a value
column, a previous pointer column and a next pointer column)
---------------------------------------------------------------
ROWNR | VALUE | PREVIOUS POINTER | NEXT POINTER |
---------------------------------------------------------------
1 John Doe 2 3
2 Vanessa Bella 4 5
...
---------------------------------------------------------------
To create your arrays you use something like like
If e.g. 100 rows, you dimension this array like
DIM value$( 100 )
DIM previousPointerI%( 100 )
DIM nextPointerI%( 100 )
Note:
You could more nicely group these arrays together in a 'structure'
DIM myDoubleLinkedList{(100) value$, previousPointerI%,
nextPointerI% }
myDoubleLinkedList{(1)}.value$ = "John Doe"
myDoubleLinkedList{(1)}.previousPointerI% = 2
myDoubleLinkedList{(1)}.nextPointerI% = 3
myDoubleLinkedList{(2)}.value$ = "Vanessa Bella"
myDoubleLinkedList{(2)}.previousPointerI% = 4
myDoubleLinkedList{(2)}.nextPointerI% = 5
END
5. binary tree (that is a table or array with 3 columns: a value
column, a left pointer column and a right pointer column)
------------------------------------------------------------
ROWNR | VALUE | LEFT POINTER | RIGHT POINTER |
------------------------------------------------------------
1 John Doe 2 3
2 Vanessa Bella 4 5
...
------------------------------------------------------------
To create your arrays you use something like like
If e.g. 100 rows, you dimension this array like
DIM value$( 100 )
DIM leftPointerI%( 100 )
DIM rightPointerI%( 100 )
Note:
You could more nicely group these arrays together in a 'structure'
DIM myBinaryTree{(100) value$, leftPointerI%, rightPointerI% }
myBinaryTree{(1)}.value$ = "John Doe"
myBinaryTree{(1)}.leftPointerI% = 2
myBinaryTree{(1)}.rightPointerI% = 3
myBinaryTree{(2)}.value$ = "Vanessa Bella"
myBinaryTree{(2)}.leftPointerI% = 4
myBinaryTree{(2)}.rightPointerI% = 5
END
6. graph (the simplest implementation is a square array with as much
rows and colums as there are nodes in the graph. Each node has its
own row. In each of the rows you inform then to which other nodes
that node is connected (e.g. by putting some value, e.g. a 1, in the
corresponding column))
---------------------------
ROWNR | VALUE |
---------------------------
1 John Doe
2 Vanessa Bella
...
---------------------------
-----------------------------------------------
ROWNR | NODE 1 | NODE 2 | ...
-----------------------------------------------
1 connected not connected ...
2 connected connected
...
----------------------------------------------- ...
If e.g. 100 rows (1 row for each node), you dimension this array
like
DIM value$( 100 )
DIM adjacencyMatrixI%( 100, 100 )
Note:
You could more nicely group these arrays together in a 'structure'
DIM myGraph{(100) value$ }
DIM adjacencyMatrix{(100,100) connectedI% }
myGraph{(1)}.value$ = "John Doe"
myGraph{(2)}.value$ = "Vanessa Bella"
adjacencyMatrix{(1,1)}.connectedI% = 1
adjacencyMatrix{(1,2)}.connectedI% = 0
adjacencyMatrix{(2,1)}.connectedI% = 1
adjacencyMatrix{(2,2)}.connectedI% = 1
PRINT adjacencyMatrix{(1,1)}.connectedI%
PRINT adjacencyMatrix{(1,2)}.connectedI%
PRINT adjacencyMatrix{(2,1)}.connectedI%
PRINT adjacencyMatrix{(2,2)}.connectedI%
END
===
By adding row(s) to the array you create a new data structure
(thus operation 'New')
You supply also the starting row (you call that the 'root'). E.g. you
start at say row 1 with your actions, and then go to the previous or
next rows by reading the pointer values in that row and repeating that
in the next rows.
E.g. by reading or changing the values in the (pointer) colums you can
then create the usual operations (goto next, goto previous, search
(e.g.
by starting with the given first row, then following the integer
numbers
to the rows, and comparing the given value with the currrent value),
remove, insert, ...)
Garbage collection could then thus be going through the rows of the
array and checking for values which are marked for removal (e.g. by
giving that rows special pointer values, like -1000)
===
Internet: see also:
---
BBCBASIC: Windows: Data structure: Link: Overview: Can you give an
overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/41639/fid/768
----------------------------------------------------------------------
